ELC Complexity Workshop


Satellite Mini-Workshp of ELC Complexity Workshop, Kyoto
(Main Workshop: Mar14--17, Tokyo http://www.al.ics.saitama-u.ac.jp/elc/ws/ )

registration not necessary; no participation fee; everybody is welcome organizers: Shin-ichi Tanigawa (RIMS), Suguru Tamaki (Kyoto U), Jun Tarui (UEC)


Tuesday, March 19, 2013


Raghu Meka: Beating the Union Bound via Gaussian Geometry
Zeev Dvir: Locally Decodable Codes: recent progress and open problems
Ketan Mulmuley: The GCT chasm


Raghu Meka: Beating the Union Bound via Gaussian Geometry:

The union bound is one of the mainstays of the probabilistic method and analysis of randomized algorithms. However, this simplistic approach does not give the full picture for many important cases, with Lovasz local lemma being a particularly salient example. In this talk I will discuss two recent results that go beyond the union bound via geometric techniques:
1) Optimal size, explicit eps-nets for computing Gaussian integrals.
2) A new elementary and constructive proof of Spencer's celebrated six
standard deviations suffice theorem.

For both problems, our methods critically exploit certain geometric and symmetry properties of the Gaussian space.

Zeev Dvir: Locally Decodable Codes: recent progress and open problems:

Locally Decodable Codes (LDCs) are error correcting codes that allow for super efficient decoding of a single message symbol using only a small number of queries to a corrupted codeword. These codes and their variants have many theoretical applications and are also starting to appear in practical scenarios. Our understanding of these codes is quite limited and this talk will attempt to survey the state of the art both in term of constructions and lower bounds.

Ketan Mulmuley: The GCT chasm:

It is shown that finite dimensional semisimple representations of any finitely generated algebra, possibly wild, can be classified explicitly (in polynomial time) assuming a standard derandomization conjecture in complexity theory. This wild classification problem of representation theory is generally regarded as "impossible" or "hopeless". It is also shown that the problem of derandomizing Noether's Normalization Lemma (NNL) for explicit varieties, the problem that lies at the heart of the more general problem of classifying algebraic varieties, can be brought down from EXPSPACE (where it is currently) to P assuming a stronger form of this standard derandomization conjecture in complexity theory.

These and related results reveal that the fundamental problems of Geometry (classification) and Complexity Theory (derandomization and lower bounds) share a common root difficulty, namely the problem of overcoming the formidable EXPSPACE vs. P gap in the complexity of NNL for explicit varieties. We call this gap the GCT chasm.