http://home.gwu.edu/~harizanv/Logic%20Seminar%20F09.html
5:15–6:15p.m.
Speaker: Andrew Hirsch, GWU
Place: Monroe Hall (2115 G Street), Room 267
Title:
Turing Categories
Abstract: Computability theory is one of the revolutionary ideas of the
20th century, and has gone on to become one of the pillars of the foundations
of mathematics. It explores the idea of what can be done by any powerful-enough
agent. Category
theory studies objects and the connections between them. It was originally
developed for use in topology, but has come to be seen as a fundamental part of
mathematics. Today, it is recognized that much, if not all, of mathematics can
be done in category theory. However,
computability theory is just starting to be codified in category theory. We explore
this codification and show that we can find more general versions of some
results.
5:15–6:15 p.m.
Speaker: Michele Friend, Department of Philosophy, GWU
http://www.gwu.edu/~philosop/faculty/Friend.cfm
Place: Monroe Hall (2115 G Street), Room 267
Title: Using a Paraconsistent
Formal Theory of Logic Metaphorically
Abstract: A formal system of logic,
such as LP (the logic of paraconsistency), is used
metaphorically by the pluralist when he discusses together incompatible
mathematical theories and together incompatible philosophies. For the purposes
here, it is enough to think of a pluralist as someone willing to entertain
together incompatible mathematical theories, or philosophical theories, without
feeling pressure to opt for one over the other. It is essential to the
pluralist position, and possibly to many other positions, that we should be
able to make sense of these incompatible situations, and say something quite
definite about them; otherwise our claims empty or trivial.
I
look at three ways in which the pluralist makes use of a formal logical system.
The first is in direct appeal to a rule or axiom to justify a move in an
argument. The second is when the pluralist uses a formal theory in order to
reconstruct another theory. This is done to understand the theory from another
perspective. The third use is dialectical. In invoking or developing a formal theory
to represent a form of reasoning, we bring some features of that reasoning into
relief, and we obscure other features. We can evaluate the fit between the
formal theory and the informal one. In the evaluation, we might well consider
alternative formal representations. Lastly, in order to remind us that
pluralists are not the only ones who use formal logic informally, I look at how
it is that mathematicians use formal logical theories.
3:45–5:00 p.m.
Speaker: Jennifer Chubb, University of San Francisco
Place: Monroe Hall (2115 G Street), Room 267
Title: Constructing easy groups with no easy orderings
Abstract: We say that a group admits a (left-)ordering if
there is a way to linearly order its members so that the ordering is preserved
under the action of the group on itself, i.e., if a < b and c is
any member of the group, then ca
< cb. When this is the case the group is
said to be orderable. A much studied question is this: Given a computable
orderable group, does the group admit a computable ordering of its members?
In this talk, we will see a construction (due to Downey and Kurtz) of a
computable orderable abelian group for which the
answer to this question is no.
We'll start with a brief survey of some easy related results
around orderable abelian groups and, if time allows,
will consider the no-abelian case.
5:15–6:15 p.m.
Speaker: Joe
Mourad,
Georgetown University
Place: Monroe Hall (2115 G Street), Room 267
Title:
Priority arguments
Abstract: We will
finish up the series with an application of priority arguments using movable
markers (invented by Friedberg) to approximate the diagonalization
and anti-diagonalization arguments we have already
given. We will see why the priority arguments become necessary when certain
obstacles are encountered.
2:30–3:30 p.m.
Speaker: Alexandra Shlapentokh, East
Carolina University
http://personal.ecu.edu/shlapentokha/
Place: Monroe Hall
(2115 G Street), Room 267
Title: Decidability and
definability over function fields of positive characteristic
5:15–6:15 p.m.
Speaker: Joe
Mourad,
Georgetown University
Place: Monroe Hall (2115 G Street), Room 267
Title:
Diagonalizing and Equivalence Relations, Part II
5:15–6:15 p.m.
Speaker: Joe
Mourad,
Georgetown University
Place: Monroe Hall (2115 G Street), Room 267
Title:
Diagonalizing and Equivalence Relations
Abstract:
Arguably
the most important concept in computability theory is the notion of diagonalization and consequently the dual idea of a fixed
point. For a list of total functions given in some sense effectively we all
know how to generate a new function of the same or very similar level of
effectiveness. This typically involves visualizing the outputs of the list of
function as an infinite 2-dimensional matrix and constructing a new function by
changing the diagonal of the matrix. Now, this new diagonal function is
different than any function on the list because the function differs in at
least one place from any of the functions on the list. However, it can be
argued that this diagonal function is not ÒreallyÓ different than a given
function just because it differs at one measly input value. On the other hand,
it can be argued that if we really put our minds to it we can make the
ÒdiagonalÓ function different on many more inputs. So the natural problem comes
up as to how different can we make our diagonal function. What new
constructions come up naturally in this context? We will review a few simple
constructions and proceed to cases where priority arguments are needed.
3:45–5:00p.m.
Speaker: Rumen Dimitrov, Western Illinois University
http://www.wiu.edu/users/rdd104/home.htm
Place: 1957 E Street,
Room 315
Title:
Cohesive Power
Abstract: We will define the notion of a cohesive power of a
computable field over a co-maximal set. We will demonstrate that the cohesive
power of the rationals is a non-Archimedean field and
will establish some interesting properties. We will also
show how different cohesive powers of the rationals
appear in the structure of the lattice of recursively enumerable vector spaces modulo finite
dimension.
5:15–6:15p.m.
Speaker: Claire Monteleoni, GWU
(Computer Science)
http://faculty.cs.gwu.edu/~cmontel/C._Monteleoni.html
Place: Monroe Hall (2115 G Street), Room 267
Title:
Clustering Algorithms for Streaming and Online Settings
Abstract: Clustering techniques are widely used
to summarize large quantities of data (e.g. aggregating similar news stories),
however their outputs can be hard to evaluate. While a
domain expert could judge the quality of a clustering, having a human in the
loop is often impractical. Probabilistic assumptions have been used to analyze
clustering algorithms, for example i.i.d. data, or even data generated by a well-separated mixture of
Gaussians. Without any distributional assumptions, one can analyze clustering
algorithms by formulating some objective function, and proving that a
clustering algorithm either optimizes or approximates it. The k-means
clustering objective, for Euclidean data, is simple, intuitive, and widely-cited, however it is NP-hard to optimize, and few
algorithms approximate it, even in the batch setting (the algorithm known as
"k-means" does not have an approximation guarantee). Dasgupta (2008) posed open problems for approximating it on
data streams.
In this talk, I will discuss my ongoing work on designing
clustering algorithms for streaming and online settings. First I will present a
one-pass, streaming clustering algorithm which
approximates the k-means objective on finite data streams. This involves
analyzing a variant of the k-means++ algorithm, and extending a
divide-and-conquer streaming clustering algorithm from the k-medoid objective. Then I will turn to endless data streams,
and introduce a family of algorithms for online clustering with experts. We
extend algorithms for online learning with experts, to the unsupervised
setting, using intermediate k-means costs, instead of prediction errors, to
re-weight experts. When the experts are instantiated as k-means approximate
(batch) clustering algorithms run on a sliding window of the data stream, we
provide novel online approximation bounds that combine regret bounds extended
from supervised online learning, with k-means approximation guarantees.
Notably, the resulting bounds are with respect to the optimal k-means cost on
the entire data stream seen so far, even though the algorithm is online. I will
also present encouraging experimental results.
This talk is based on joint work with Nir
Ailon, Ragesh Jaiswal, and Anna Choromanska.
Bio: Claire Monteleoni is an assistant professor of Computer Science at
The George Washington University, which she joined in 2011. Previously, she was
research faculty at the Center for Computational Learning Systems, and adjunct
faculty in the Department of Computer Science, at Columbia University. She was
a postdoc in Computer Science and Engineering at the
University of California, San Diego, and completed her PhD and Masters in
Computer Science, at MIT. Her research focus is on machine learning algorithms
and theory for problems including learning from data streams, learning from raw
(unlabeled) data, learning from private data, and Climate Informatics:
accelerating discovery in Climate Science with machine learning. Her papers
have received several awards. In 2011, she co-founded the International
Workshop on Climate Informatics, which she co-chaired again this year. She
serves on the Editorial Board of the Machine Learning Journal, and recently
served on the Senior Program Committees of ICML and UAI, 2012.
3:45–5:00p.m.
Speaker: Andrew Hirsch, GWU
Place: Monroe Hall (2115 G Street), Room 267
Title:
Mechanized Metatheory for Authorization Logic
Abstract: Authorization logics are concerned with determining
which principals in a system are securely permitted to take what actions. This
talk presents ongoing work on verifying the metatheory
of an authorization logic (Nexus Authorization Logic, derived from CDD and DCC)
in Coq, including a natural-deduction proof system, a Kripke-style semantics, and a proof of soundness.
The verification process exposed subtle issues with the semantics. The
talk also presents some experience and lessons learned from using Coq to
express complex semantic models. Joint work with
Michael Clarkson.
1:00–2:00p.m.
Speaker: Russell Miller, City University of New York
http://qcpages.qc.cuny.edu/~rmiller/
Place: Monroe Hall (2115 G Street), Room 267
Title:
Computable
Categoricity for Fields
Abstract:
The topic of
computable categoricity considers the possibility of building computable
isomorphisms between two computable structures, given that the two structures
are already known to be (classically) isomorphic. A computable structure A is said to be computably categorical
if every computable structure B which
is isomorphic to A is in fact
computably isomorphic to A. For
fields which are algebraic over the rationals, we
give an exact description of the complexity of this property: it is
Pi^0_4-complete. For non-algebraic fields, much less is
known, but we show that the question is nontrivial: many fields of
infinite transcendence degree were already known not to be computably
categorical, but we give the first example of one which is computably
categorical.
Part of this work is joint with Denis Hirschfeldt, Ken Kramer, and Alexandra Shlapentokh,
while the rest is joint with Hans Schoutens.
5:15–6:15p.m.
Speaker: Jack H. Lutz, Iowa State University
http://www.cs.iastate.edu/~lutz/
Place: Monroe Hall
(2115 G Street), Room 267
Title:
The Dimensions of Individual Points in Euclidean Space
Abstract: Recent developments in the theory of computing
assign a dimension to every individual point in Euclidean space. These
dimensions appear to be geometrically useful. For example, the fractal
dimension of any ÒreasonableÓ set is simply the least upper bound of the
dimensions of its individual elements. This talk will survey these
developments, including recent applications to fractal geometry and computable
curves, connections with data compression, and directions for future research.
This talk is aimed at a general math/logic audience. No background in
fractal geometry will be assumed.
5:15–6:15p.m.
Speaker: Rumen Dimitrov, Western Illinois University
http://www.wiu.edu/users/rdd104/home.htm
Place: Phillips Hall (at Academic
Center), 801 22nd St, Room 414B
Title:
Maximal Vector Spaces
Abstract: The existence of maximal
recursively enumerable sets was established by Friedberg in 1958. According to G. Sacks,
this result Òignited interest in the lattice of recursively enumerable sets
under inclusion modulo finite sets.Ó There are several notions of maximality for recursively enumerable vector spaces. We will give the constructions of some
of the types of maximal spaces and will examine their importance in the study
of the lattice of recursively enumerable vector spaces modulo finite dimension.
3:00–4:00p.m.
Speaker: Areski Nailt-Abdallah, University of Western Ontario and INRIA Paris
http://www.csd.uwo.ca/People/areski.shtml
Place: Monroe Hall
(2115 G Street), Room 267
Title: On the
Logical Formalization of Single Photon Self-Interference
Abstract: We consider the particle interference problem in
quantum physics, and discuss a Curry-Howard isomorphism based logical analysis
of this problem. This approach is applied to a photon traversing a Mach-Zehnder interferometer.
5:15–6:15p.m.
Speaker: Rumen Dimitrov, Western Illinois University
http://www.wiu.edu/users/rdd104/home.htm
Place: Phillips Hall (at Academic
Center), 801 22nd St, Room 414B
Title: Effective
Vector Spaces: Dependence and Structure
Abstract: We consider algorithmic version of a traditional
question of finding a basis of a vector space. Metakides
and Nerode set up a suitable framework for
investigating this and similar questions. They showed that the study of
computably presented vector spaces can be reduced to
the study of one particular countably-dimensional
vector space. Finding an effective basis requires a dependence algorithm, but
will every computable vector space have such an algorithm? I will introduce
this vector space and talk about some interesting and unexpected results in the
area of modular computability theory.
5:30–6:30p.m.
Speaker: Jozef
Przytycki, GWU
http://home.gwu.edu/~przytyck/
Place: Phillips Hall (at Academic
Center), 801 22nd St, Room 414B
Title: An Introduction to Entropic
Homology
Abstract: Magma is a structure with a single
binary operation. I
will offer a gentle introduction to entropic magmas ((a*b)*(c*d)=(a*c)*(b*d)),
starting from the work of A. Sushkevich (1937) and K.
Toyoda (1940). I will further discuss my work with P. Traczyk
on Homflypt polynomial of links, and our Conway
algebra approach. I will end with my work on extensions of magmas by
affine entropic magmas, which gives hints to entropic homology that M. Niebrzydowski
and I are currently developing.
Other logic talks
Saturday, December 8, 2012;
2:00–3:30p.m.
Media &
Public Affairs Building (805 21st Street), Room 309
Speaker: Kai Maeda, GWU (graduate
student)
Time: 2:00–2:25p.m.
Title: Non-Associative Structures and Their Computability Theoretic
Complexity
Abstract at: http://atlas-conferences.com/cgi-bin/abstract/cbfw-39
Speaker: Rumen Dimitrov, Western Illinois University
Time:
2:30–2:55p.m.
Title: Algorithmic Content and Structure in Effective Vector Spaces
Abstract at: http://atlas-conferences.com/cgi-bin/abstract/cbfw-23
Speaker: Sebastian
Wyman,
University of Florida (graduate student)
Time: 3:05–3:30p.m.
Title: Symbolic Dynamics in the Arithmetic Hierarchy
Abstract at: http://atlas-conferences.com/cgi-bin/abstract/cbfw-40