• August 15st: Mohammad Mahmoody on Learning (right) SAT solvers & finding hard instances for (lying) SAT solvers.

• August 15st: Mohammad Mahmoody on Learning (right) SAT solvers & finding hard instances for (lying) SAT solvers.

Learning (right) SAT solvers & finding hard instances for (lying) SAT solvers. / Mohammad Mahmoody

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.

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.

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.

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 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.

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 uniform algorithms. We will describe these techniques, focusing on a new algorithm that learns a function f given access to a circuit C that only approximately computes (f, f, ... , f) with some significant probability.

• August 1st: David Xiao on Uniform Amplification of Hardness.

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 show that if f is hard against 'uniform' algorithms, then (f, f, ..., f) is much harder against 'uniform' algorithms. We will describe these techniques, focusing on a new algorithm that learns a function f given access to a circuit C that only 'approximately' computes (f, f, ... , f) with some significant probability.

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.

• July 18th: Polynomial Identity Testing for Depth 3 Circuits / Seshardi Comandur

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.

• July 25th: Zero-knowledge against quantum attacks / Shengyu Zhang

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

This paper proves 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.

• July 18th: Polynomial Identity Testing for Depth 3 Circuits / Seshardi Comandur

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.

• Wednesday July 12th: To Spike or Not to Spike: Optimal Change-Detection in Single Neurons Angela J. Yu - Program in Neuroscience, Princeton

• Wednesday July 12th: To Spike or Not to Spike: Optimal Change-Detection in Single Neurons

• Wednesday July 12th: [[#angela | To Spike or Not to Spike: Optimal Change-Detection in Single Neurons ]

/ Angela J. Yu - Program in Neuroscience, Princeton

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.

• July 12th: Open
• July 18th: Open
• July 25th: Open
• August 1st: David Xiao on (Uniform) Amplification of Hardness in NP. Abstract coming soon.

• July 11th: No talk due to

Instead we will meet on Wednesday July 12th.

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.

• July 5th (Note: we meet Wednesday instead of Tuesday because of the 4th of July) Andrej Bogdanov on Refuting dense random instances of 3SAT

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 don't know, is never wrong, and outputs 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) > n^1.5. Moreover, there are negative results showing that several popular approaches fail below m(n) < n^{1.5 - eps}.

Interpreted liberally, these negative results could be viewed as evidence that random 3SAT is hard for errorless heuristics below n^1.5. Very recently this intuition was debunked by Feige, Kim, and Ofek who gave a nondeterministic errorless heuristic that works whenever m(n) > n^1.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.

• July 5th (Note: we meet Wednesday instead of Tuesday because of the 4th of July)

• July 5th (Note: we meet Wednseday instead of Tuesday because of the 4th of July)

• July 5th (Note: we meet Wed instead of Tue because of the 4th of July)

Andrej Bogdanov on Refuting random instances of 3SAT.

• July 11th: We'll start at 12:30, to allow people time to come from

Scott Aaronson's talk at IAS.