Last updated: September 22. 2010

Speakers and their talks

Talks are 30-40 minutes.

A. Blass (University of Michigan, USA),
Developments from Specker's work in and near set theory
Abstract:
I plan to describe a few of Ernst Specker's contributions to set theory and nearby topics, and to indicate some recent work connected with these contributions.
E. Fischer (Technion-Israel Institute of Technology, Israel),
Modular recurrence relations for combinatorial sequences:
Reflections on a Theorem of C. Blatter and E. Specker.
Abstract:
While many results in combinatorics provide asymptotic estimates for the number of structures satisfying a given property, a theorem from 1981 by C. Blatter and E. Specker is one of the few results dealing with the "low-order digits". This result exhibits a modular recurrence relation for counting the number of ways a set with n elements can be equipped with unary and binary relations satisfying a property definable in monadic second order logic. We survey the theorem and some later developments. In particular we outline a proof from 2003 showing that the theorem does not hold over quaternary relations, and proofs for some additional cases in which it does hold.
J. Flum (University of Freiburg, Germany),
On optimal proof systems and logics for PTIME
Abstract:
A proof system for propositional logic is optimal if it simulates any other proof system in polynomial time. A logic captures PTIME if a property of finite structures is decidable in polynomial time if and only if it is expressible in the logic. It is open whether there are optimal propositional proof systems and whether there are logics capturing PTIME. In the talk we present a relationship between these two open questions.
M. Fuerer (The Pennsylvania State University, USA)
How fast can we multiply?
Abstract:
In 1962, Karatsuba has presented an integer multiplication algorithm which multiplies two binary or decimal numbers in less than quadratic time, showing that school multiplication is not optimal. Faster methods have been designed quickly. All are based on some version of the Chinese Remainder Theorem. Most methods reduce integer multiplication to fast polynomial multiplication, which itself is a scheme for the evaluation of polynomials, followed by multiplication of their values and interpolation.
For more than 35 years, the fastest known multiplication method has been the Schoenhage-Strassen algorithm. It is based on the fast Fourier transform (FFT) and runs in time O(n log n log log n). Only in 2007 has a faster algorithm come closer to the conjectured optimal running time of O(n log n). The running time bounds hold for multi-tape Turing machines. The same bounds are valid for the size of Boolean circuits. Interestingly, this latest improvement would have come much earlier and more natural if there were infinitely many Fermat primes F[j] and the jumps in the sequence log log log F[j] (for j = 0,1,2,...) were bounded by a constant.
H. Gaifman (Columbia University, New York, USA)
A simple semantic modeling of the Principia and its non-standard models
Abstract:
Principia Mathematica is a system of intensional logic, based on proposition and propositional functions, intended to reconstruct extensional mathematics, based on classes. Existing rigorous modeling of it are syntactically oriented and use a complex system of terms. I propose a relatively simple Tarskian modeling that separates between the intensional and extensional aspects. Details regarding intensional distinctions can be left open (as they are left in the Principia). This makes possible a systematic analysis of ramified types and the reducibility axiom. The analysis makes wide use of non-standard models of arithmetic and various extensions of it. It also leads to a formulation within the Principia of the predicativity principle in the form of an "anti reducibility" axiom. With this axiom, the Principia is equivalent to a system whose standard model is $L_{\omega^+,\omega}$ over an infinite class of urelements.
E. Graedel (RWTH Aachen, Germany)
Simple Winning Strategies for Banach Mazur-Games on Graphs
Abstract:
Infinite games where two players take turns to move a token through a directed graph, thus tracing out an infinite path, have numerous applications in different branches of mathematics and computer science. In the usual format, the possible moves of the players are given by the edges of the graph; in each move a player takes the token from its current position along an edge to a next position. In Banach-Mazur games the players instead select in each move a \emph{path} of arbitrary finite length rather than just an edge. In both cases the outcome of a play is an infinite path. A winning condition is given by a set of infinite paths, often specified by a logical formula.
Banach-Mazur games have a long tradition in descriptive set theory and topology, and they have recently been shown to have interesting applications also in computer science, for instance for planning in nondeterministic domains, for the study of fairness in concurrent systems, and for the semantics of timed automata.
It turns out that Banach-Mazur games behave quite differently than the usual graph games. Often they admit simpler winning strategies and more efficient algorithmic solutions. For instance, Banach-Mazur games with $\omega$-regular winning conditions always admit winning strategies that only depend on the current position, and not on the history of the play.
N. Hungerbuehler (University of Fribourg und ETH Zurich, Switzerland)
Remarks on polyfunctions
Abstract:
A function $f:R \to R$ on a ring $R$ which can be represented as a polynomial is called a polyfunction. These functions obviously form a ring. We will discuss some of the properties of this ring, in particular for the case $R=\mathbb Z_n$.
R. Kossak (CUNY, New York, USA)
The MacDowell-Specker Theorem.
Abstract: Much of model theory of Peano Arithmetic originated for the theorem of
MacDowell and Specker on elementary end extensions. I will give a survey of generalizations and applications of the theorem including some recent results of Ali Enayat and Saharon Shelah.
K. Tent (University of Muenster, Germany) and M. Ziegler (University of Freiburg, Germany)
Computable functions on the reals
Abstract:
Starting from a definition due to Specker we explore a new hierarchy of computable functions on $\R^N$ and prove some basic properties. In particular, we prove that the low complex numbers form an algebraically closed field closed under exponentiation and some other special functions.
S. Wolf (ETH Zurich, Switzerland)
The Kochen-Specker Theorem and Quantum Non-Locality
Abstract:
We believe today that quantum-physical behavior has no classical description by so-called "hidden variables." The most important milestones on the way to this insight are famous results by Kochen and Specker on one hand, and John Bell's non-local correlations on the other. We discuss a close connection between these results.