# Caltech–UCLA Logic Seminar

## (Aka Cabal Seminar)

The Logic seminar generally meets on Fridays, 2–3:30p.m., at Caltech or UCLA. Contact Alexander Kechris or Itay Neeman if you wish to give a talk.

Schedule of talks, going back to Fall 2016, in reverse chronological order:

# Logic Seminar: 09/25/2017 - 09/25/2018

 Friday Nov 03 2017 14:00-15:30 (MS 6221) Matthew Foreman (UCI) Classifying diffeomorphisms of the torus Friday Oct 27 2017 14:00-15:30 (MS 6221) Matthew Foreman (UCI) Classifying diffeomorphisms of the torus Friday Oct 13 2017 14:00-15:30 (MS 6221) Kota Takeuchi (University of Tsukuba) Friday Sep 29 2017 14:00-15:30 (MS 6221) Dana Bartosova (University of Sao Paulo) Free actions via graphs Abstract. A topological group admits a free action if there is a compact space on which it acts without fixed points. We translate this property into colorability of graphs, which leads us to questions of combinatorial nature. This is a joint work in progress with Vladimir Pestov.Hide

# Logic Seminar: 09/1/2016 - 09/24/2017

 Friday Jun 09 2017 14:00-15:30 (MS 6221) Danny Nguyen (UCLA) Complexity of short Presburger arithmetic Abstract. We study complexity of short sentences in Presburger arithmetic. Here by "short" we mean sentences with a bounded number of variables, quantifiers, inequalities and Boolean operations; the input consists only of the integers involved in the inequalities. The problem is motivated by the earlier work on counting integer points in polytopes and their projections in spaces of bounded dimension. We completely resolve the problem. There were some surprises along the way which we also explain. Joint work with Igor Pak.Hide Friday Jun 02 2017 14:00-15:30 (MS 6221) Anush Tserunyan (UIUC) Ergodic hyperfinite decomposition of countable Borel equivalence relations Abstract. A countable Borel equivalence relation $E$ on a probability space can always be generated in two ways: as the orbit equivalence relation of a Borel action of a countable group and as the connectedness relation of a locally countable Borel graph, called a graphing of $E$. When $E$ is measure-preserving, graphings provide a numerical invariant called cost, whose theory has been largely developed and used by Gaboriau and others in establishing rigidity results. A well-known theorem of Hjorth states that when $E$ is ergodic, treeable (admits an acyclic graphing), and has integer or infinite cost $n \le \infty$, then it is generated by an a.e. free measure-preserving action of the free group $\mathbf{F}_n$ on $n$ generators. We give a simpler proof of this theorem and a further development of our technique yields a strengthening of Hjorth's theorem: the action of $\mathbf{F}_n$ can be arranged so that each of the $n$ generators alone acts ergodically. This is joint work with Benjamin Miller.Hide Friday May 26 2017 14:00-15:30 (MS 6221) Igor Pak (UCLA) Complexity of short generating functions Abstract. Short generating functions (GF) are power series defined as sums of terms $ct^k/(1-t^a)(1-t^b)\dots$. One can think of each term as a GF of a generalized arithmetic progression. The size of a short GF $A(t)$ is defined as the total bit length of the parameters $a,b,c,k,\dots$. We study the problem whether a given GF has a short GF presentation of polynomial size. This turn out to be a hard problem both mathematically and computationally. We resolve it modulo some complexity assumptions. Notably, we show that the truncated theta function \$\sum_{k