# Seminars and Colloquia

## Logic Seminar

Monday, September 21, 2015

04:45 pm - 06:00 pm

CT Logic Seminar, Vincent Guingona (Wes): "A Local Characterization of VC-Minimality"

Abstract : ( Joint work with Uri Andrews ) This talk is in the intersection of computable model theory and neostability theory. I discuss VC-minimality, a model-theoretic notion of complexity for theories that generalizes o-minimality and is generalized by dp-minimality and NIP. Unlike o-minimality and dp-minimality, a priori , it is difficult to determine if a given theory is VC-minimal. In computability terms, the definition of VC-minimality, in its original form, is Sigma_1^1. However, my coauthor and I show that VC-minimality is, in fact, Pi^0_4-complete by giving a local characterization (for countable languages). This leads to a list of examples of theories whose VC-minimality is determined.

Exley Science Center (Tower)

Monday, September 14, 2015

04:45 pm - 05:45 pm

Logic Seminar, Reed Solomon (UConn): "Strong reducibilities, RT^1_3 and SRT^2_2"

Abstract: Various strong reductions between Pi^1_2 principles have been used in recent years to shed light on difficult problems in reverse mathematics. I will introduce some of these reductions and discuss their connection to reverse math. The main theorem of the talk is that RT^1_3 is not strongly computably reducible to SRT^2_2. This result is joint work with Damir Dzhafarov, Ludovic Patey and Linda Brown Westrick.

Monday, April 27, 2015

04:45 pm - 06:00 pm

Logic Seminar, Petr Glivicky (Charles University): 'Definability in linear fragments of Peano Arithmetic'

Abstract: In this talk, I will give an overview of recent results on linear arithmetics with main focus on definability in their models. Here, for a cardinal k, the k-linear arithmetic (LAk) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). The hierarchy of linear arithmetics lies between Presburger and Peano arithmetics and stretches from tame to wild. I will present a quantifier elimination result for LA1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA2 (or any LAk with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no similar quantifier elimination is possible). There is a close connection between models of linear arithmetics and certain discretely ordered modules (as each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars) which allows to construct wild (e.g. non-NIP) ordered modules. On the other hand, the quantifier elimination result for LA1 implies interesting properties of the structure of saturated models of Peano arithmetic.

ESC 638

Monday, March 30, 2015

04:45 pm - 06:00 pm

Logic Seminar, Reed Solomon (UConn): 'Revisiting EM and ADS'

Abstract: In this talk, I will present recent work by Ludovic Patey which simplifies and extends the proof that the Erdos-Moser principle (that every infinite tournament has an infinite transitive sub tournament) does not imply ADS (that every linear order contains either an infinite ascending sequence or an infinite descending sequence).

ESC 638

Tuesday, March 24, 2015

04:15 pm - 05:30 pm

Computer Science Seminar, Marc Liberatore (UMass): 'BitCoin: WTF is it, and is it really anonymous?'

Abstract: In this talk, we'll (re-)develop the BitCoin protocol step-by-step. We'll start with a simple centralized service for digital cash, and end up with a sketch of the distributed consensus system that we all love -- or love to hate. We will briefly survey the state of BitCoin and related systems, with a focus on how much privacy they really provide to their users. Then, we'll present the problem of mixing BitCoin to increase user privacy. We will see that centralized mix systems based on protocols like CoinJoin have the same problems found in centralized proxies for general communications, and more besides. We'll show that the Sybil attack is one such problem -- a critical one -- and present Xim, our distributed approach to Sybil-resistant matchmaking. (While this talk will be technical, you won't need a deep knowledge of cryptography or protocols to follow it. My goal is for undergraduate liberal arts majors with some math or computer science background to be comfortable in following along and in asking questions as they come up.) Marc Liberatore is a research scientist and occasional lecturer in the School of Computer Science at the University of Massachusetts Amherst, and the associate director of the Center for Forensics at UMass. Prior to his current appointment, he was a Mellon Fellow and Visiting Assistant Professor at Wesleyan University. His research interests include network, cellular, and filesystem forensics, anonymous communication systems, and peer-to-peer architectures.

ESC 638

Tuesday, March 24, 2015

04:15 pm - 05:30 pm

Computer Science Seminar, Marc Liberatore (UMass): 'BitCoin: WTF is it, and is it really anonymous?'

Abstract: In this talk, we'll (re-)develop the BitCoin protocol step-by-step. We'll start with a simple centralized service for digital cash, and end up with a sketch of the distributed consensus system that we all love -- or love to hate. We will briefly survey the state of BitCoin and related systems, with a focus on how much privacy they really provide to their users. Then, we'll present the problem of mixing BitCoin to increase user privacy. We will see that centralized mix systems based on protocols like CoinJoin have the same problems found in centralized proxies for general communications, and more besides. We'll show that the Sybil attack is one such problem -- a critical one -- and present Xim, our distributed approach to Sybil-resistant matchmaking.(While this talk will be technical, you won't need a deep knowledge of cryptography or protocols to follow it. My goal is for undergraduate liberal arts majors with some math or computer science background to be comfortable in following along and in asking questions as they come up.)Marc Liberatore is a research scientist and occasional lecturer in the School of Computer Science at the University of Massachusetts Amherst, and the associate director of the Center for Forensics at UMass. Prior to his current appointment, he was a Mellon Fellow and Visiting Assistant Professor at Wesleyan University. His research interests include network, cellular, and filesystem forensics, anonymous communication systems, and peer-to-peer architectures.

ESC 638

Monday, March 23, 2015

04:45 pm - 06:00 pm

Logic Seminar, Stephen Flood (UConn): 'Separating Decomposability and Tree- Decomposability'

Abstract: The theory of graph decompositions studies the infinite graphs that can be built using a sequence of irreducible graphs which are pasted together at complete subgraphs. In this theory, there are several combinatorial characterizations of the tree-decomposable graphs, but a combinatorial characterization of general decomposable graphs has proved elusive.In this talk, we approach this question from the perspective of mathematical logic. We show that there is indeed a difference between characterizing decomposable and tree-decomposable graphs. More precisely, we show that the index set of computable decomposable graphs is $\Pi^1_1$ hard and $\Sigma^1_2$ definable, whereas the index set of computable tree-decomposable graphs is $\Sigma^1_1$ definable.

ESC 638

Monday, November 17, 2014

04:45 pm - 06:00 pm

CT Logic Seminar, Linda Brown Westrick (UConn): 'Effective Dimension in Subshifts'

Abstract: A subshift is a subset of Cantor space that is both topologically closed and closed under the shift operation. Any element of a subshift can be viewed as a trajectory in a discrete dynamical system. One way a trajectory can be complicated is to have a large effective dimension. We consider the effective dimension spectrum of a subshift X, defined as {dim x : x in X}, where dim is the effective dimension. Most commonly, the dimension spectrum of X is [0,h(X)], where h(X) is the entropy of X. We give examples where the dimension spectrum does not follow this pattern, and discuss partial results and open questions related to the problem of characterizing the dimension spectra of subshifts. No prior knowledge about subshifts will be assumed.

ESC 638

Monday, November 10, 2014

04:45 pm - 06:00 pm

CT Logic Seminar, Gwyneth Harrison-Shermoen (Wes): 'Independence, via limits'

Abstract: Given a large model $M$ of some theory $T$, I will describe a method for lifting well-behaved notions of independence from the theories of substructures of $M$ to a reasonably well-behaved notion of independence in $M$. (In essence, we take the limit of the independence relations in the substructures.) The motivating example - two-sorted theories of infinite-dimensional vector spaces over an algebraically closed field and with a bilinear form - was worked out by N. Granger in his thesis. I will outline this example before launching into the more general framework.

ESC 638

Monday, October 27, 2014

04:45 pm - 06:00 pm

CT Logic Seminar, Cameron Hill (Wes): 'Some Remarks on Certain 0,1-Laws'

Abstract: I will begin by reminding everyone what a Fra\iss\e class is, and I will introduce a certain family of ultrafilters related to such a class. After that, I will review what is (usually) intended when one says that a Fra\iss\e class has a 0,1-law for first-order sentences. Finally, I will propose a method of indexing asymptotic distributions on a Fra\iss\e class by elements of a certain compact space, and I will discuss some results that can be proved using this method.

ESC 638

Monday, September 22, 2014

04:45 pm - 06:00 pm

CT Logic Seminar, Jim Schmerl (UConn): 'The Automorphism Group of Countable Recursively Saturated Model of PA'

Abstract: I will discuss the question: To what extent does the automorphism group of a countable recursively saturated model of Peano Arithmetic determine the model?

ESC 638

Monday, September 15, 2014

04:45 pm - 06:00 pm

CT Logic Seminar, Philip Scowcroft (Wes): 'Continuous Model Theory for C(X)'

Abstract: In the continuous logic recently developed by Ben Yaacov and others, the class of lattice-ordered groups isomorphic to C(X) with X compact is an elementary class. The theory T of this class has convenient model-theoretic properties: for example, T has a model-completion T(+) which is countably categorical and admits elimination of quantifiers. One may establish also a corresponding Nullstellensatz and determine which models of T have prime-model extensions to models of T(+).

ESC 638

Monday, September 08, 2014

04:45 pm - 06:00 pm

CT Logic Seminar, Reed Solomon (UConn): Reverse mathematics and the Dual Ramsey Theorem

Abstract: This talk will be an introduction to the Dual Ramsey Theorem and to the (relatively few) results in reverse mathematics known about it.

ESC 638

Monday, January 20, 2014

04:45 pm - 06:00 pm

Logic Seminar, Neil Immerman (UMass): 'Descriptive and Dynamic Complexity'

Abstract: An increasing percentage of modern computation is dynamic: a fairly large object is being worked on over a period of time. The object is repeatedly modified and computations are performed. Using auxiliary data structures we can sometimes maintain the ability to very quickly answer certain queries about the object as it changes. dynFO is the set of properties that can be maintained and queried in First-Order logic. Much progress has been made understanding when graph reachability is in dynFO and related classes, but the general question remains open.

ESC 638

Monday, November 25, 2013

04:45 pm - 06:00 pm

Logic Seminar, Philip Scowcroft (Wesleyan): ' Existentially closed prime-model extensions of Abelian lattice-ordered groups.'

Abstract: Existentially closed (ec) Abelian lattice-ordered groups are to Abelian lattice-ordered (l-) groups as algebraically closed fields are to fields. An ec prime-model extension of the Abelian l-group G is an ec Abelian l-group that extends G and embeds over G into any ec Abelian l-group extending G. So the Abelian l-group G is to an ec prime-model extension of G as a field F is to its algebraic closure. This talk will consider the extent to which Abelian l-groups have ec prime-model extensions.

ESC 638

Monday, October 21, 2013

04:45 pm - 05:45 pm

Logic Seminar, Lynn Scow (Vassar): 'Ramsey transfer theorems'

Abstract: We survey some of the known approaches to transfer a Ramsey theorem for one class of finite structures to another. We will isolate some easy consequences and point to further directions.

ESC 638

Monday, October 14, 2013

04:45 pm - 05:45 pm

LogicSeminar, Henry Towsner (Univeristy of Pennsylvania): 'Models of Reverse Mathematics'

Abstract: Most recent work in reverse mathematics has focused on the consequences of Pi12 sentences. One family of questions asks, given a Pi12 sentence, what its first-order consequences are---what the Pi12 sentence implies about the underlying first-order model of arithmetic. Turning this around, once we have a theory of reverse mathematics, we can ask about the collection of all Pi12 sentences which are conservative over it for first-order consequences. When our theory T is the theory ACA0 (or, in fact, any computably axiomatized theory containing ACA0), the collection of such sentences is as complicated as possible their Godel numbers form a Pi02 complete set). Over weaker theories, however, the method of proof fails. We show that for the most important class of weaker theories, those of the form RCA0 plus Sigma_n induction for some n, the same result holds. Our method is completely different than the proof for ACA0, and has the side benefit of sharply constraining what the theories RCA0+ISigma_n can prove about formulas more complicated than ISigma_n.

ESC 638

Monday, October 07, 2013

04:45 pm - 06:00 pm

Logic Seminar, Russell Miller (Queens College, CUNY): 'Fields and Computable Categoricity'

Abstract: We give an overview of the current understanding of computable categoricity for fields. A computable field F is computably categorical if, for every computable field E which is isomorphic to F (via any isomorphism), there exists a computable isomorphism from E onto F. Characterizations of computable categoricity are known for various other classes of computable structures, and for certain subclasses of computable fields, but have proven elusive for fields. We give an analysis of the reasons why, considering both the complexity of the definition of computable categoricity and the amount of information needed to compute field isomorphisms when they exist.

ESC 638

Monday, September 16, 2013

04:45 pm - 06:00 pm

Logic Seminar, Damir Dzhafarov (UCONN): Limits to joining with generics and randoms

Abstract: It is a fundamental theorem of computability theory that the Turing jump of a set A always has strictly greater Turing degree than A itself, i.e., deg(A) 1. Our result applies generally to many other forcing notions commonly used in computability theory. I will also mention a variant of our result, showing that the set G cannot be chosen to be 2-random.

ESC 638

Monday, September 09, 2013

04:45 pm - 06:00 pm

Logic Seminar, Reed Solomon (UCONN): Separating ADS and CAC

Abstract: We examine the relationship between ADS and CAC in reverse mathematics. ADS says that every infinite linear order has either an infinite ascending chain or an infinite descending chain. CAC says that every infinite partial order has either an infinite chain or an infinite antichain. It is known that CAC implies ADS. In this talk, we show that ADS does not imply CAC over RCA_0. This work is joint with Manny Lerman and Henry Towsner.

ESC 638

Monday, December 03, 2012

04:45 pm - 06:00 pm

Logic Seminar, Brett Townsend - Wesleyan: 'The Structure of Ordered Abelian Groups with Finite Prime Invariants'

Abstract: A dense regular group is a densely ordered group elementarily equivalent to a subgroup of R. In this talk I will discuss the structure of definable sets in such groups with arbitrary finite prime invariants. In particular, I will present a cell-decomposition theorem similar to that which is known for o-minimal structures, and describe how one may then derive a coherent dimension theory for such groups.

ESC 638

Monday, November 26, 2012

04:45 pm - 06:00 pm

Logic Seminar, Koushik Pal - University of Maryland: 'Unstable Theories with an Automorphism'

Abstract: Kikyo and Shelah showed that if T is a first-order theory in some language L with the strict-order property, then the theory T_\sigma, which is the old theory T together with an L-automorphism \sigma, does not have a model companion in L_\sigma, which is the old language L together with a new unary predicate symbol \sigma. However, it turns out that if we add more restrictions on the automorphism, then T_\sigma can have a model companion in L_\sigma. I will show some examples of this phenomenon in two different context - the linear orders and the ordered abelian groups. In the context of the linear orders, we even have a complete characterization of all model complete theories extending T_\sigma in L_\sigma. This is joint work with Chris Laskowski.

ESC 638

Monday, November 12, 2012

04:45 pm - 06:00 pm

Logic Seminar, Jean-Martin Albert - Marlboro College: 'Continuous Logical Categories'

Abstract: In this talk I will introduce Continuous Logical Categories. These are an analogue of the notion of Logical Category introduced by Makkai and Reyes in the context of First-Order Continuous Logic. We will also establish a correspondence between theories in First-Order Continuous Logic and Continuous Logical Categories.

ESC 638

Thursday, November 08, 2012

04:15 pm - 06:00 pm

Math Colloquium, Michel Dekking - Delft: 'A simple stochastic model for kinetic transport'

Abstract: We introduce a discrete time microscopic single particle model for kinetic transport. The kinetics is modeled by a two-state Markov chain, the transport by deterministic advection plus a random space step. The position of the particle after n time steps is given by a random sum of space steps, where the size of the sum is given by a Markov binomial distribution (MBD). We prove that by letting the length of the time steps and the intensity of the switching between states tend to zero linearly, we obtain a random variable S(t), which is closely connected to a well known (deterministic) PDE reactive transport model from the civil engineering literature. Our model explains (via bimodality of the MBD) the double peaking behavior of the concentration of the free part of solutes in the PDE model. Moreover, we show for instantaneous injection of the solute that the partial densities of the free and adsorbed part of the solute at time t do exist, and satisfy the partial differential equations.

ESC 638

Monday, November 05, 2012

04:45 pm - 06:00 pm

Logic Seminar, Paul Baginski - Smith: 'Stability and Countable Categoricity in Nonassociative Rings'

Abstract: A classic result due to Felgner and to Baur, Cherlin and Macintyre in the 1970s states that a stable, $\aleph_0$-categorical group is nilpotent by finite. At around the same time, Baldwin and Rose proved that a stable, $\aleph_0$-categorical associative ring is nilpotent by finite. Recently, Wagner, Krupinski and others have renewed interest in these two results by proving analogous statements where stability is replaced by other model theoretic properties. In all cases, the rings being considered are associative. However, Rose extended many of his results with Baldwin in a second paper to a class of nonassociative rings called alternative rings. However, the question of whether a stable, $\aleph_0$-categorical alternative ring was nilpotent by finite remained open. In this talk, I shall outline a proof of Baldwin and Rose's theorem using a modern perspective and then discuss the obstacles that occur when one tries to use the same methods for nonassociative rings. I will then present my current progress towards proving Baldwin and Rose's theorem for nonassociative rings.

ESC 638

Friday, October 19, 2012

04:45 pm - 06:00 pm

Logic Seminar, Maryanthe Malliaris, University of Chicago: 'Saturation of Ultrapowers and the Structure of Unstable Theories

Abstract: The talk will be about some very recent progress on Keisler's order, a far-reaching program of understanding basic model-theoretic structure through the lens of regular ultrapowers. I will explain Keisler's order and the perspective it gives on classifying the unstable theories, and discuss a recent paper of Malliaris and Shelah which applies model-theoretic techniques developed for the study of Keisler's order to solve the oldest problem on cardinal invariants of the continuum. I will assume basic familiarity with ultraproducts, Los's theorem, and saturation, and plan to give most other relevant definitions. Papers mentioned in the talk are available at http://math.uchicago.edu/~mem. NOTE UNUSUAL DAY OF THE WEEK FOR LOGIC SEMINAR

ESC 638