Complexity Seminar Home-Page
Hi All.
The complexity seminar will be held on the fall semester
2001-2002. The seminar is to discuss complexity and PCP with relations to
topics from combinatorics and analysis, such as compression, extremal
set-theory, hyper-contractivity, sensitivity, and Fourier analysis over
discrete groups.
Procedural
Details:
·
Time: Thrusdays,
· Place:
· Mailing
List: Join it here –
registration is free!
· Organized
by: Guy Kindler.
Talks:
Date
|
Speaker |
Subject |
Abstract |
|
|
The LP
bound - continued |
|
|
|
|
Omer Reingold |
Constant
Degree Lossless Expanders |
We present the first explicit construction of constant degree
"lossless" expanders. In these graphs, the expansion factor is
almost as large as possible: (1-e)D, where D is the
degree and e is an arbitrarily small constant. The best previous explicit
constructions gave expansion factor D/2. The D/2 bound was obtained via the eigenvalue method, and is the best possible using this
method [Kahale95]. We also discuss the applications of our lossless expanders. In
particular, we give new explicit linear codes of relative rate (1-delta) and
minimum distance (delta / polylog(1/delta)). For small delta, this beats the Zyablov bound and is quite close to the Gilbert-Varshamov bound. Moreover, the losslessness
of our graphs implies a very simple linear-time decoding algorithm (taken
from [Sipser-Spielman]). Joint work with Michael Capalbo, Salil Vadhan and Avi Wigderson |
|
|
Alex Samorodnitski |
The LP
bound - continued |
Talk Canceled |
|
|
Learning
Boolean functions via the Fourier Transform |
Two main areas are to be surveyed: 1. Show that many simple complexity classes can be represented
by few coefficients. 2. Show a polynomial time algorithm for recovering the
"heavy" Fourier coefficients. The results will be mainly from [Kushilevtiz
Mansour 19991] and also [Linial,
Mansour, Nisan 1989] and [Mansour
1992] |
|
|
|
Scott Aaronson |
Quantum
Lower Bound for the Collision Problem |
The collision problem is to decide whether a
function X:{1,..,n}->{1,..,n} is one-to-one or two-to-one,
given that one of these is the case. We show a lower bound of Theta(n^1/5}) on the number of queries needed by a quantum
computer to solve this problem with bounded error probability. The best known
upper bound is O(n^{1/3}), but obtaining any lower
bound better than Theta(1) was an open problem since 1997. Our proof uses the polynomial method augmented
by some new ideas. We also give a lower bound of Theta(n^{1/7})
for the problem of deciding whether two sets are equal or disjoint on a
constant fraction of elements. Finally we give implications of these results
for quantum complexity theory. |
|
|
The LP
bound on the rate of a code |
|
|
|
|
Fourier
Theoretic Perspective for Arrow's Theorem |
Arrow's theorem asserts that, under reasonable
conditions, in a voting system where the society is to choose between at
least three candidates, any voting method, except dictatorship, gives rise to
non-rational outcomes. That is, the society may prefer A to B, B to C and C
to A. We describe a Fourier theoretic formula for the
probability of rational outcome in an election between three candidates.
Among application for this formula, we show that if the outcomes are rational
with high probability, then the society follows the decision of a single
member with high probability. |
|
|
|
Beckner’s Inequality |
In this talk we shall go further into hard core Analysis. We
will discuss some properties of L_p norms, and
prove Beckner's celebrated hyper-contractive
estimate. If time remains, we shall discuss Junta tests that are even simpler
than the long-code test we discussed. These tests perform worse than the
long-code test, though, and they are harder to analyze. |
|
|
|
Juntas,
and Continuous Versions of KKL |
The talk will cover the following subjects: 1)Juntas: Easy fact: A balanced
Boolean function f: {0,1}^n --> {0,1}
where the sum of influences is 1 must be a dictatorship, i.e. there exists
an i such that f(x_1 ,...x_n) = x_i. More advanced: If the sum of the influences is small then
there exists a Junta, a small set of coordinates, that
can determine the outcome of the function w.h.p.
regardless of what the other variables do. 2)BKKKL is
the continuous analog of KKL. It turns out that some of the theorems in the
continuous case follow easily from the discrete case. Other problems are
still wide open and can be translated to elementary discrete questions. |
|
|
|
This week's talk is based on a result by Jeff Kahn, Gil Kalai, and Nathan Linial. Consider a Boolean function f over the discrete cube. The
influence of the i-th
coordinate on f is the probability that for a random x, the value of f(x) is
changed when the i-th coordinate in x is
flipped. We will prove that Boolean
functions on n variables, that yield one on exactly half of the elements of
the n-dimensional cube, always have at least one coordinate with influence \Omega(log n /n). This is true although the average of the
influences may be as small as 1/n. This implies that if the average of
influences of the coordinates on f is small, f cannot be symmetric
coordinate-wise: some coordinates must be substantially more influential than
others. For the proof we will need tools such as the $L_p$ norm of a function, and Beckner's
operator, which we already used, implicitly, in the long-code test. We will
present Beckner's hyper-contractive estimate, which
plays a major, yet mysterious, role in this and many other combinatorial
proofs. |
||
|
|
The talk will provide some motivation for the code-tests we
have been looking at so far. A clear one being a tool utilized to construct
extremely efficient Probabilistically-Checkable-Proof-Systems (PCP's). The starting point for such a construction is the PCP theorem,
which states that it is possible to verify the correctness of a given
mathematical proof with high probability, by reading only a constant number
of bits, provided the proof is written in a certain prescribed format. Utilizing the long-code test we've seen, one can extend the
PCP theorem (following Hastad) as follows: Given a mathematical proof, written
in a certain, prescribed, format, it is possible to test its correctness by randomly accessing three bits, such that: a) If the proof is correct, the test accepts with probability
1-\epsilon b) If the claim of the proof is false, the test accepts with probability
at most 0.5+\epsilon. We will also show how this proof-system implies hardness of
approximation for the E3-LIN problem, namely, given a set of linear equations
over a common set of variables, each depending on 3 variables, what is the
maximum fraction of equations satisfied. If time permits, we will describe how the iterated test may be
utilized to obtain other proof-verification techniques. |
||
|
|
We shall continue last week's talk, analyzing
the iteration version of Hastad's linearity test. We will follow Hastad and
Wigderson's proof of a result by Samorodnitsky and Trevisan, showing that it
is possible to read 2k+k^2 bits of a supposed code-word, achieving an almost
optimal error probability of roughly 2^{-k^2}+d, where d is the correlation
between the given word and the nearest correct code-word. We will also show another analysis by Hastad and
Wigderson, of the same test, showing a bound on the error probability where the 'd' part decreases exponentially with k as well. The
talk will be independent of last week's talk, and will include a short review
of the basic notions. |
||
|
|
We will discuss a result by Hastad, showing a non-adaptive PCP test that queries three bits, uses logarithmic randomness, and has completeness 1-\epsilon and soundness 1/2+\epsilon. The test verifies that the three bits read, satisfy a certain linear-equation over Z_2. This result can be
interpreted as follows: Given a set of linear equations over Z_2, where there
are exactly 3 variables in each equation, it is NP-hard to distinguish
between the case where there exists an assignment satisfying a
(1-\epsilon)-fraction of the equations, and the case where no assignment can
satisfy more than a (1/2+\epsilon)-fraction. Another result by Hastad and Wigderson gives a
simple proof, for the properties of a PCP test of Luca Trevisan and Alex
Samorodnitsky. Their test reads 2k+k^2 bits of the proof, f_1,..,f_k, g_1,..,g_k, h_11,..,h_kk, and for every i and j, it
verifies a linear equation over f_i, g_j, and h_ij. The error probability of
the test, roughly |
||
|
|
Introductory
Talk |
We will discuss Fourier analysis
over discrete groups, especially over Z_2. We shall then describe the
long-code and the Hadamard code, show simple tests for them, and analyze the
performance of these tests using Fourier analysis. |
