Mar19(Tue) Satellite Mini-Workshp, Kyoto
venue: Room 111, RIMS, Kyoto Univ, Kyoto
http://www.kurims.kyoto-u.ac.jp/en/access-01.html   http://goo.gl/aCgSE
registration not necessary; no participation fee; everybody is welcome
organizers: Shin-ichi Tanigawa(RIMS), Suguru Tamaki(Kyoto U), Jun Tarui(UEC)

13:15--14:15 Raghu Meka: Beating the Union Bound via Gaussian Geometry
14:15--14:30 break
14:30--15:30 Zeev Dvir: Locally Decodable Codes: recent progress and open problems
15:30--15:45 break
15:45--17:15 Ketan Mulmuley: The GCT chasm
18:00--      impropmtu dinner party around Sanjo-Kawara-machi
             (We will move to a dinner place from the workshop venue.
              Please note that dinner is not free of charge, 
              and you are kindly asked to come on time.)


Abstracts:

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 derandomization of Noether's Normalization Lemma (NNL) for explicit varieties
is essentially  equivalent to black-box derandomization of Polynomial Identity Testing (PIT). This and
related results reveal that the fundamental problems in Geometry (classification
of algebraic varieties) 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.