Summer Seminar
Tuesdays 12-2pm in room 402
CLICK HERE TO JOIN THE MAILING LIST
Scott Aaronson's talk at IAS.
Abstracts
June 27th - James Lee
The Gowers norms, PCPs, and arithmetic progressions
I will discuss the "Gowers uniformity" norms and how they arise in both PCP constructions (Samorodnitsky-Trevisan) and in Gowers' proof of Szemeredi's theorem on arithmetic progressions.
[More specifically: I'll talk about the relationship with long-code tests, and how S-T get an optimal PCP characterization of NP in terms of queries vs. soundness (conditional, assuming the unique games conjecture), and the resulting optimal hardness of Max-Independent-Set. Finally, I'll mention the very nice "inverse problem" of determining exactly which functions have large degree-d Gowers norm--it is conjectured that for functions defined on {0,1}^n, say, these are precisely the functions which are correlated with a degree-(d-1) polynomial, but this is known only for degrees 2 and 3.]
Jul 5 (Wednesday) - Andrej Bogdanov
Refuting dense random 3CNF instances
A random 3CNF instance on n variables is chosen by selecting at random m(n) out of the 8(n choose 3) possible clauses on n variables. When m(n) > 5n, a random 3CNF is unsatisfiable with all but negligible probability.
This talk will concern the existence of errorless heuristic algorithms for random 3SAT with respect to this distribution on formulas. Such an algorithm takes a formula as input, outputs either unsatisfiable or I don't know, is never wrong, and outputs I don't know for only a small fraction of inputs.
Much interest in this problem stems from the belief that it is intractable for a certain range of the parameter m(n). The best known errorless heuristic algorithms for the problem only work when m(n) > n1.5. Moreover, there are negative results showing that several popular approaches fail below m(n) < n1.5 - eps.
Interpreted liberally, these negative results could be viewed as evidence that random 3SAT is hard for errorless heuristics below n1.5. Very recently this intuition was debunked by Feige, Kim, and Ofek who gave a nondeterministic errorless heuristic that works whenever m(n) > n1.4.
My plan for the talk is to give an overview of the various results about this problem, explain Feige's 3XOR principle which is the basis of several fruitful approaches including the last one, and discuss the new algorithm by Feige, Kim, and Ofek.
To Spike or Not to Spike: Optimal Change-Detection in Single Neurons
Angela J. Yu
Program in Neuroscience, Princeton
Survival in a non-stationary, potentially adversarial environment
requires animals to detect sensory changes rapidly yet accurately, two
oft-competing desiderata. Neurons subserving such detections are faced
with the corresponding need to discern ``real'' changes in inputs as
quickly as possible, while ignoring noisy fluctuations. Mathematically,
this is an example of a change-detection problem that is actively
researched in the stochastic dynamic control community. In this paper,
we utilize sophisticated tools developed in that community to formalize
an instantiation of the problem faced by the nervous system, and derive
the Bayes-optimal decision policy under certain assumptions. We will
derive from this optimal strategy an information accumulation and
decision process that remarkably resembles the dynamics of a leaky
integrate-and-fire neuron. This correspondence suggests that neurons
are optimized for tracking changes in inputs, and sheds new light on the
computational import of intracellular properties such as resting
membrane potential, voltage-dependent conductance, and post-spike reset
voltage. We also explore the influence that factors such as timing,
uncertainty, neuromodulation, and reward should have on neuronal
dynamics and sensitivity, since the optimal decision strategy depends
critically on these factors.
Polynomial Identity Testing for Depth 3 Circuits / Seshadri Comandur
The problem of derandomizing polynomial identity testing (PIT) is one of the most important open problems in TCS - problems like primality testing and bipartite matching are special cases of it. Impaggliazzo and Kabanets showed that derandomizing PIT would lead to circuit lower bounds.
When the polynomial is given as an arithmetic circuit, even the most trivial case of PIT for depth 3 circuits was not known to be in P (until now, that is). I will present a recent result by Kayal and Saxena which shows that PIT for this special case is indeed decidable in polynomial time. It uses the idea of Chinese remaindering, which was successfully used for derandomizing primality testing.
Zero-knowledge against quantum attacks. / Shengyu Zhang
I will present the STOC 06 paper by Watrous proving that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich-Micali-Wigderson classical zero-knowledge protocols for Graph Isomorphism and Graph 3-Coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive protocol for a complete problem for the complexity class of problems having "honest verifier" quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: QSZK = QSZKHV. Previously no non-trivial proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest-verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.
Uniform Amplification of Hardness
The Direct Product Lemma (also called the Concatenation Lemma) says that if a function f is hard to compute on average, then the function (f, f, ..., f) is much harder to compute on average. Here, (f, f, ..., f) means applying f to (typically poly(n)) many independent inputs. The known proofs of the direct product lemma require some amount of non-uniformity, and so, without further assumptions on the function f, the lemma makes statements only about the non-uniform average-case complexity of f.
A recent work (to appear in FOCS 2006) by Impagliazzo, Jaiswal, and Kabanets makes progress in the uniform setting of the Direct Product Lemma. IJK combine three techniques to prove that if f is hard against uniform algorithms, then (f, f, ..., f) is much harder against "almost" uniform algorithms. We will describe each of these techniques: a new algorithm that learns a function f given a circuit C computing (f, f, ..., f) w.h.p. and access to a distribution that is close to (x, f(x)); a way of producing samples that are close to (x, f(x)) using a circuit C computing (f, f, ..., f); and a way to convert a circuit computing the k-fold direct product to a circuit computing the k^(3/2)-fold direct product.
We will also mention the applications of this new result, primarily in the construction of approximate locally list-decodable codes and in uniform amplification of hardness.
Learning (right) SAT solvers & finding hard instances for (lying) SAT solvers. / Mohammad Mahmoody
First I will mention briefly the result of Gutfreund et al [1] which
finds hard instances for any algorithm which claims solving SAT
(assuming NP \not \subset BPP). This results is highly non-Black Box
(I.e. the code of the algorithm is used). Then I will describe a classic
result [2] (and its proof) about learning any circuit using NP oracles.
Afterwards, we will see an application of that learning algorithm [3]
which makes the result of [1] more black-box (but not completely). The
main part of the talk will be about the learning algorithm for SAT
solvers and its proof. We will also speak about possible improvemtns
which has not been done.
[1] Danny Gutfreund, Ronen Shaltiel, Amnon Ta-Shma. If NP languages are
hard on the worst-case then it is easy to find their hard instances. In
Proceedings of the 20th Annual Conference on Computational Complexity,
(CCC), 2005.
[2] N. H. Bshouty, R. Cleve, R. Gavaldą, S. Kannan, C. Tamon, Oracles
and Queries That Are Sufficient for Exact Learning. Journal of Computer
and System Sciences, 52(3): pp. 421-433 (1996).
[3] A. Atserias. Distinguishing SAT from Polynomial-Size Circuits,
through Black-Box Queries, to appear in 21st Annual IEEE Conference on
Computational Complexity (CCC), 2006.