LOGIC SEMINAR

 

Previous seminars at:

http://home.gwu.edu/~harizanv/Logic%20Seminar%20F09.html

 

Campus map

Foggy Bottom Campus Map.pdf

 

Spring 2013

 

Senior Thesis Defense

Thursday, April 25, 2013

5:156: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.

 

 

Thursday, March 28, 2013

5:156: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.

 

Tuesday, March 19, 2013

3:45–5:00 p.m.

Speaker:  Jennifer Chubb, University of San Francisco

http://cs.usfca.edu/~jcchubb/

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.

 

Thursday, March 7, 2013

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.

 

(with Mathematics Colloquium)

Friday, March 1, 2013

2:303: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 

Abstract: We prove that the existential theory of any function field K of characteristic p > 0 is undecidable in the language of rings provided the constant field does not contain the algebraic closure of a finite field. (In the case K is uncountable we consider equations with coefficients in a finitely generated subfield.) We also complete the proof of the characteristic 2 higher transcendence degree case left out from the main theorem of to show that the first-order theory of any function field of positive characteristic is undecidable in the language of rings without parameters.

 

Thursday, February 21, 2013

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

Abstract: This talk will continue our discussion of diagonalization whereby we try to make the diagonal function as different on as many inputs as possible. We will proceed to look at the case where we try to diagonalize over functions that may be partial, meaning that they may be forever undefined on a given input. The fact that the function remains “quiet” at least some of the time will provide certain advantages. We will see how arguments that worked in the total case can be nonetheless modified and proceed to the cases where priority arguments are needed.

 

Thursday, February 14, 2013

5:156: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.

 

 

Fall 2012

 

Monday, December 10, 2012

3:455: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.

 

Monday, December 3, 2012

5:156: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.

 

Monday, November 12, 2012

3:455: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.

 

Friday, November 9, 2012

1:002: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.

 

Monday, October 15, 2012

5:156: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.

 

Monday, October 8, 2012

5:156: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.

 

Logic-Quantum Computing Seminar

Friday, September 28, 2012

3:004: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. 

 

Monday, September 24, 2012

5:156: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.  

 

Logic-Topology Seminar

Monday, September 10, 2012

5:306: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

Knots in Washington XXXV

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