August 25, 2017, 4:10 PM (60 Evans Hall)
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.
September 08, 2017, 4:10 PM (60 Evans Hall)
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.
September 22, 2017, 4:10 PM (60 Evans Hall)
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.
October 06, 2017, 4:10 PM (60 Evans Hall)
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.
October 20, 2017, 4:10 PM (60 Evans Hall)
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.
November 03, 2017, 4:10 PM (60 Evans Hall)
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.