Computational fair division

Ariel Procaccia
Carnegie Mellon University
November 24, 2014
I will present an exciting new interaction between computer science and fair division theory, with the goal of giving the audience a taste of different fair division challenges and the role computational thinking plays in addressing them. Among other things, I will talk about a complexity-theoretic approach to the question of why envy-free cake cutting has been so elusive; and will explain how the notion of worst-case approximation gives rise to a provably feasible notion of fairness in the context of the allocation of indivisible goods.

\(P = W\): a strange identity for \(\mathrm{GL}(2,\mathbb C)\)

Mark deCataldo
Stony Brook University; Member, School of Mathematics
November 24, 2014
Start with a compact Riemann surface \(X\) and a complex reductive group \(G\), like \(\mathrm{GL}(n,\mathbb C)\). According to Hitchin-Simpson's ``non abelian Hodge theory", the pair \((X,G)\) comes with two new complex manifolds: the character variety \(\mathcal M_B\) and the Higgs moduli space \(\mathcal{M}_\text{Dolbeault}\). When \(G= \mathbb C^*\), these manifolds are two instances of the usual first cohomology group of \(X\) with coefficients in the abelian \(\mathbb C^*\).

Sum-of-squares lower bounds for the planted clique problem

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
November 25, 2014
Finding large cliques in random graphs and the closely related "planted" clique variant, where a clique of size \(k\) is planted in a random \(G(n,1/2)\) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for \(k = \Theta(\sqrt{n})\). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-Of-Squares hierarchy.

Parallel Repetition From Fortification

Dana Moshkovitz
Massachusetts Institute of Technology
December 1, 2014
The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and show that for fortified games, the value of the repeated game decreases perfectly exponentially with the number of repetitions, up to an arbitrarily small additive error. Our proof is combinatorial and (very) short.

As corollaries, we obtain:

Graphs, vectors and integers

Noga Alon
Tel Aviv University; Visiting Professor, School of Mathematics
December 1, 2014
The study of Cayley graphs of finite groups is related to the investigation of pseudo-random graphs and to problems in Combinatorial Number Theory, Geometry and Information Theory. I will discuss this topic, describing the motivation and focusing on several results that illustrate the interplay between Graph Theory, Geometry and Number Theory.

Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression

Timothy Riley
Cornell University; Member, School of Mathematics
December 2, 2014
For a finitely presented group, the Word Problem asks for an algorithm which declares whether or not words on the generators represent the identity. The Dehn function is the time-complexity of a direct attack on the Word Problem by applying the defining relations. I will survey these topics and their interrelationships. A "hydra phenomenon" gives rise to novel groups with extremely fast growing (Ackermannian) Dehn functions. I will explain why, nevertheless, there are efficient (polynomial time) solutions to the Word Problems of these groups.