University Seminar: Logic Across Disciplines

Spring 2018

Title:Working seminar about developing a formal system representing reasoning in chemistry
Speaker: Prof. Michele Friend, Department of Philosophy.
Date and Time:  Thursday, April 27, 2018 11:00am–12:00noon
Place: Phillips Hall (801 22nd Street), Room 736

Title:Scott Ranks of Scattered Linear Orders
Speaker: Rachael Alvir, University of Notre Dame
Date and Time:  Thursday, April 26, 2018 12:30PM-1::30 PM
Place: Rome Hall(801 22nd Street), Room 351

Abstract: The logic L(omega1, omega) is obtained from regular finitary first-order logic by closing under countable conjunctions and disjunctions. There is a kind of normal form for such sentences. The Scott rank of a countable structure A is the least complexity of a sentence A of L(omega1, omega), which describes A up to isomorphism among countable structures. Every scattered linear order is associated with an ordinal known as its Hausdorff rank. We give sharp upper bounds on the Scott rank of a scattered linear order given its Hausdorff rank, along the way calculating some of the back-and-forth relations on this class. These results generalize previously obtained results on the Scott ranks of ordinals and Hausdorff rank 1 linear orders.

Title:Detecting Nilpotence in Classes of Groups
Speaker: Iva Bilanovic, GWU
Date and Time:  Friday, March 30, 2018 11:00AM-12::00 PM
Place: Phillips Hall (801 22nd Street), Room 736

Abstract: Detecting an arbitrary Markov property is π2-hard in the class of recursively presented groups and is π1-hard in the class of computable groups. In other words, even when a computable description of a group is given we cannot algorithmically decide whether the group has some property. Certain properties attain even higher level of complexity. We will investigate nilpotence and precisely locate its undecidability in the arithmetical hierarchy.  

Title: Structural Properties of Spectra and Omega-Spectra
Speaker:Alexandra Soskova, Sofia University, Bulgaria
Date and Time: Thursday, March 22, 2018, 12:30-1:30 PM
Place: Rome Hall (801 22nd Street), Room 531

Abstract: We consider the degree spectrum of a structure from the point of view of enumeration reducibility and omega-enumeration reducibility. We will give an overview of several structural properties of degree spectra and their co-spectra, such as a minimal pair theorem and the existence of quasi-minimal degrees for degree spectra and receive as a corollary some fundamental theorems in enumeration degrees. We will show that every countable ideal of enumeration degrees is a co-spectrum of a structure and if a degree spectrum has a countable base then it has a least enumeration degree. Next we investigate the omega-enumeration co-spectra and show that not every countable ideal of omega-enumeration degrees is an omega-co-spectrum of a structure.

TitleTransforming Machine Learning Heuristics into Provable Algorithms: Classical, Stochastic, and Neural
Speaker: Cheng Tang, GWU, Computer Science
Date and Time: Friday February 23, 11:00-12:00 noon
Place: Phillips Hall (801 22nd Street), Room 736

Abstract: A recurring pattern in many areas of machine learning is the empirical success of a handful of “heuristics”, i.e., any simple learning procedure favored by practitioners. Many of these heuristic techniques lack formal theoretical justification. For unsupervised learning, Lloyd's k-means algorithm, while provably exponentially slow in the worst-case, remains popular for clustering problems arising from different applications. For supervised learning, random forest is another example of a winning heuristic with many variants and applications. But the most prominent example is perhaps the blossoming field of deep learning, which is almost entirely composed of heuristics; the practical success of a deep learning algorithm usually relies on an experienced user skillfully and creatively combining heuristics. In this talk, I will discuss some of my thesis work in advancing the theoretical understanding of some of the most widely used machine learning heuristics.

Title: Effective Ultraproducts and Their Applications
Speaker: Rumen Dimitrov, Western Illinois University
Date and Time: Thursday February 8, 12:30-1:30
Place: Phillips Hall (801 22nd Street), Room 730

Abstract: We use cohesive (effectively indecomposable) sets to build nonstandard versions of the field of rational numbers. We study the isomorphism types of these models when the complements of the cohesive sets are computably enumerable. Using Koenigsmann’s work on Hilbert's Tenth Problem we give a new proof that these fields are rigid.

Title:  Topological Spaces of Orderings of Algebraic Structures
Speaker:   Jennifer Chubb, University of San Francisco and GWU
Date and Time:  Friday, February 2 2018 11:00 am-12 noon
Place: Phillips Hall (801 22nd Street), Room 736

Abstract: A left- or bi- partial ordering of an algebraic structure is a partial ordering of the elements of the structure that is invariant under the structure acting on itself on the left or, respectively, both on the left and on the right.  In this talk, we will consider the spaces of total left and bi-orderings of a group, how these spaces can be visualized as the paths of binary trees, and their computational and topological properties.

Title:  Encoding Noncomputable Sets into Orders on Computable Structures
Speaker:   Valentina Harizanov, GWU
Date and Time:  Friday, January 26, 2018 11:00 am-12 noon
Place: Phillips 736

Abstract: We consider a structure with a binary operation, which admits orders that are invariant under the operation. The space of these orders is compact under a natural topology, and in many cases homeomorphic to the Cantor set. For such computable structures, including many groups, we show when it is possible to encode an arbitrary set into an order so that their Turing degrees are preserved.