Locally decodable codes (LDCs) are error-correcting codes that
allow for highly-efficient recovery of "pieces" of information even
after arbitrary corruption of a codeword. Locally testable codes
(LTCs) are those that allow for highly-efficient...
There are two important measures of the complexity of a boolean
function: the sensitivity and block sensitivity. Whether or not
they are polynomial related remains a major open question. In this
talk I will survey some known results on this...
The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every
NP-proof can be encoded to another proof, namely, a
probabilistically checkable proof (PCP), which can be tested by a
verifier that queries only a small part of the PCP. A
natural...
There are two important measures of the complexity of a boolean
function: the sensitivity and block sensitivity. Whether or not
they are polynomial related remains a major open question. In this
talk I will survey some known results on this...
We discuss three areas of algorithmic game theory that have
grappled with intractability. The first is the complexity of
computing game-theoretic equilibria, like Nash equilibria. There is
an urgent need for new ideas on this topic, to enable...
I will continue the exposition of different derandmization
techniques for probabilistic logspace algorithms.
The material of this talk will assume only little knowledge from
the first talk.
Since the foundational results of Thomason and
Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there
has been a lot of effort by many researchers to extend the theory
to hypergraphs. I will present some of this history, and
then...
I will survey some of the basic approaches to derandomizing
Probabilistic Logspace computations, including the "classical"
Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the
Saks-Zhou algorithm and some more recent approaches. We'll...
Polar codes have recently emerged as a new class of
low-complexity codes achieving Shannon capacity. This talk
introduces polar codes with emphasis on the probabilistic
phenomenon underlying the code construction. New results and
connections to...
I will describe the very recent breakthrough result by Gupta,
Kamath, Kayal and Saptharishi which shows that every polynomial P
in n variables, of degree d which is polynomial in n, and which can
be computed by a polynomial sized arithmetic circuit...
