We propose an “analytical” framework for studying parallel
repetitions of one-round two-prover games. We define a new
relaxation of the value of a game, val+, and prove that it is both
multiplicative and a good approximation for the true value
of...
We all know Shannon's entropy of a discrete probability
distribution. Physicists define entropy in thermodynamics and in
statistical mechanics (there are several competing schools), and
want to prove the Second Law, but they didn't succeed yet
(very...
We give an arithmetic version of the recent proof of the
improved triangle removal lemma by Fox [Fox11], for the group
$F_2^n$.
A triangle in $F_2^n$ is a tuple (x,y,z) such that $x+y+z = 0$. The
triangle removal lemma for $F_2^n$ states that for...
A trusted source of independent and uniform random bits is a
basic resource in many computational tasks, such as cryptography,
game theoretic protocols, algorithms and physical simulations.
Implementing such a source presents an immediate challenge...
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.
