Events 2017-2018

Logic Colloquium

August 25, 2017, 4:10 PM (60 Evans Hall)

Andrew Marks
U.C. Los Angeles

A constructive solution to Tarski’s circle squaring problem

In 1925, Tarski posed the problem of whether a disc in 2 can be partitioned into finitely many pieces which can be rearranged by isometries to form a square of the same area. Unlike the Banach-Tarski paradox in 3, it can be shown that two Lebesgue measurable sets in 2 cannot be equidecomposed by isometries unless they have the same measure. Hence, the disk and square must necessarily be of the same area.

In 1990, Laczkovich showed that Tarski’s circle squaring problem has a positive answer using the axiom of choice. We give a completely constructive solution to the problem and describe an explicit (Borel) way to equidecompose a circle and a square. This answers a question of Wagon.

Our proof has three main ingredients. The first is work of Laczkovich in Diophantine approximation. The second is recent progress in a research program in descriptive set theory to understand how the complexity of a countable group is related to the Borel cardinality of the equivalence relations generated by its Borel actions. The third ingredient is ideas coming from the study of flows in networks.

This is joint work with Spencer Unger.

Logic Colloquium

September 08, 2017, 4:10 PM (60 Evans Hall)

Cameron Freer
Founder, Borelian Corporation and Chief Scientist, Remine LLC

Model theory of invariant probabilistic constructions

There is a long history of studying the logic obtained by assigning probabilities, instead of truth values, to first-order formulas. In a 1964 paper, Gaifman studied probability distributions on countable structures that are invariant under renaming of the underlying set – which he called “symmetric measure-models”, and which are essentially equivalent to what today are known as S-invariant measures. In this paper, he asked the question of which first-order theories admit invariant measures concentrated on the models of the theory.

We answer this question of Gaifman, a key first step towards understanding the model theory of these measures, which can be thought of as “probabilistic structures”. In this talk, we will also discuss related questions, such as how many probabilistic structures are models of a given theory, and when probabilistic structures are almost surely isomorphic to a single classical model.

Joint work with Nathanael Ackerman and Rehana Patel.

Logic Colloquium

September 22, 2017, 4:10 PM (60 Evans Hall)

Nadja Hempel
Assistant Adjunct Professor of Mathematics, UCLA

Mekler construction in generalized stability

Given a so called nice graph (no triangles, no squares, for any choice of two distinct vertices there is a third vertex which is connected to one and not the other), Mekler considered the 2-nilpotent subgroup generated by the vertices of the graph in which two elements given by vertices commute if and only if there is an edge between them. These groups form an interesting collection of examples from a model theoretic point of view. It was shown that such a group is stable if and only if the corresponding graph is stable and Baudisch generalized this fact to the simple theory context. In a joint work with Chernikov, we were able to verify this result for k-dependent and NTP2 theories. This leads to the existence of groups which are (k+1)-dependent but not k-dependent, providing the first algebraic objects witnessing the strictness of these hierarchy.

Logic Colloquium

October 06, 2017, 4:10 PM (60 Evans Hall)

Yann Pequignot
Postdoctoral Fellow, Department of Mathematics, UCLA

Finite versus infinite: an insufficient shift

Analytic sets enjoy a classical representation theorem based on well-founded relations. I will explain a similar representation theorem for Sigma^1_2 sets due to Marcone which is based on an intriguing topological graph: the Shift Graph. The chromatic number of this graph is 2, but its Borel chromatic number is infinite. We use this representation theorem to show that the Shift Graph is not minimal among the graphs of Borel functions which have infinite Borel chromatic number. While this answers negatively the primary outstanding question from (Kechris, Solecki and Todorcevic; 1999), our proof unfortunately does not construct any explicit example of a Borel function whose graph has infinite Borel chromatic number and admits no homomorphism from the Shift Graph.

Logic Colloquium

October 20, 2017, 4:10 PM (60 Evans Hall)

Thomas Icard
Assistant Professor of Philosophy, Stanford University

Some Philosophical Uses of Randomized Computation

The aim of this talk will be to convey some of the ways that familiar ideas and tools from randomized and probabilistic computation might bear on issues of philosophical interest, focusing especially on questions about cognition, representation, and reasoning. A first question is when it would ever make sense for an agent to employ randomization in the course of decision making. Drawing on ideas from game theory, reinforcement learning, and statistics, we tentatively propose a unified answer to the question. A second set of questions revolves around the idea of characterizing an agent’s implicit causal knowledge of the world by appeal to the explicit causal structure of a probabilistic algorithm. This second topic raises novel questions about the logic of counterfactuals beyond the usual propositional setting. Much of this is work in progress.

Logic Colloquium

November 03, 2017, 4:10 PM (60 Evans Hall)

Lenore Blum
Distinguished Career Professor of Computer Science, Carnegie Mellon University

Alan Turing and the Other Theory of Computation

Most logicians and theoretical computer scientists are familiar with Alan Turing’s 1936 seminal paper setting the stage for the foundational (discrete) theory of computation. Most however remain unaware of Turing’s 1948 seminal paper introducing the notion of condition, setting the stage for a natural theory of complexity for what I call the “other theory of computation” emanating from the classical tradition of numerical analysis, equation solving and the continuous mathematics of calculus. This talk will recognize Alan Turing’s work in the foundations of numerical computation (in particular, his 1948 paper “Rounding-Off Errors in Matrix Processes”), how it provides a unifying concept for the two major traditions of the Theory of Computation, and its influence on complexity theory today.