Theory of Computer Science Seminar

This talk provides a gentle, high level introduction to (the beautiful) Invariant Theory, that is aimed at non-experts. It will describe some of its main objects, problems and results. Read more about CS theory seminar: Avi Wigderson (IAS) : An invitation to Invariant Theory

The geodesic flow on a normal cover of a compact hyperbolic surface admits a "random walk" on the group of decks transformations $G$. In this talk, I'll provide some recent results which connect this walk to the geometric properties of the cover and $G$.

In the last 35 years, geometric flows have proven to be a powerful tool in geometry and topology. The Mean Curvature Flow is, in many ways, the most natural flow for surfaces in Euclidean space. In this talk, which will assume no prior knowledge, I will illustrate how mean curvature flow could be used to address geometric questions.

Let u be a harmonic function on the plane. The Liouville theorem claims that if |u| is bounded on the whole plane, then u is identically constant. It appears that if u is a harmonic function on the lattice Z^2, and |u| < 1 on 99,99% of Z^2, then u is a constant function. Based on a joint work with A. Logunov, Eu. Malinnikova and M. Sodin.

Speaker: Zur Luria, JCE Title: On the threshold for simple connectivity in random 2-complexes Abstract:

Speaker: Benny Sudakov, ETH, Zurich Title: Subgraph statistics Abstract: Consider integers $k,\ell$ such that $0\le \ell \le \binom{k}2$. Given a large graph $G$, what is the fraction of $k$-vertex subsets of $G$ which span exactly $\ell$ edges? When $G$ is empty or complete, and $\ell$ is zero or $\binom k 2$, this fraction can be exactly 1. On the other hand if $\ell$ is not one these extreme values, then by Ramsey's theorem, this fraction is strictly smaller than 1. The systematic study of the above question was recently initiated by

Speaker: Wojciech Samotij, TAU Title: Subsets of posets minimising the number of chains Abstract:

The proof of decoupling grew out of an area of Fourier analysis called restriction theory. In this talk, we will describe some of the basic problems and tools of restriction theory, especially wave packets, which are a crucial idea in the proof of decoupling.

The general theme is game dynamics leading to equilibrium concepts. The plan is to deal with the following topics (all concepts will be defined, and proofs / proof outlines will be provided): (1) An integral approach to the construction of calibrated forecasts and their use for Nash equilibrium dynamics. (2) Blackwell's Approachability Theorem and its use for correlated equilibrium dynamics (regret-matching). (3) Communication complexity and its use for the speed of convergence of uncoupled dynamics.