Skip to content

Lecture 6

Today we talked about Hardness-Randomness tradeoffs. We stated, without a proof, that if E requires circuits of size S(n) then one can construct a pseudorandom generator with stretch S(n)^c for some constant c < 1. We talked informally about the proof strategy and mentioned that usually the theorem is proven in two steps. In the first step one constructs the PRG under a stronger assumption, namely, that E cannot be approximated by small circuits (see Theorem 20.6 in Arora-Barak book). Then one shows that the assumption can be weakened to the desired assumption, that is, a computational assumption rather than an approximation one.

A key ingerdient in the second step is local decodable codes, or local list decodable codes (see Chapter 19 in Arora-Barak book). A somewhat more recent construction that doesn’t go through these two steps was given by Umans in a beautiful paper. This paper is one of the papers for the end of the semester talks.

As mentioned, in this course we focus on the “other direction”, namely, showing that derandomization implies circuit lower bounds. We stated a beautiful result by Impagliazzo and Wigderson (see also Theorem 20.16 in Arora-Barak book) that shows that you can get some sort of derandomization under uniform assumptions only (BPP not equal to EXP). Nevertheless, the theorem we started to prove, by Impagliazzo and Kabanets (see Theorem 20.17 in Arora-Barak and references therein) shows that derandomizing ZEROP will yield some circuit lower bound – either NEXP is not in P/poly or the permanent requires super-polynomial arithmetic circuits.

To prove this theorem we took a short detour into interactive proofs, introduced the classes MA, IP and MIP (the latter just for fun, as it equals NEXP – a star complexity class in this course). Using the famous result IP=PSPACE (Theorem 8.19 in Arora-Barak book and references therein). We deduced that PSPACE is contained in P/poly implies PSPACE = MA. We used this to improves upon Meyer to show that if EXP is in P/poly then EXP collapses to MA (and not just to the second level of PH). Finally, we used this last statement to show that MA_EXP (~NEXP + randomness) is not contained in P/poly – this is the best known uniform lower bound for P/poly to my knowledge.

We then switched to talk about succinct problems (such as succinct-SAT) and more generally, about strings that their truth table can be computed by a small circuit. For a much better non-formal description than what I gave, see Williams’ casual tour around a circuit complexity bound (which will be useful also for the rest of the course). We started to prove a theorem by Imapagliazzo, Kabanets and Wigderson (Lemma 2.20 in Arora-Barak) that shows that if NEXP is contained in P/poly then NEXP=EXP (and thus =MA). The proof uses the easy witness method introduced by Kabanets (see his paper, which also appears at the end of the semester talks). Next time we will continue the proof.

Lecture 5

For the past four lectures we studied the basics of circuits and why they are interesting. Today we finally started to talk about the first topic of the course, namely Hardness-Randomness tradeoff.

We began by defining probabilistic Turing machines and defining complexity classes that capture randomness. We further noticed that P is contained in BPP which in turn is contained in PSPACE. In fact, a cool theorem by Sipser (which was later improved by Gacs) shows that BPP is contained in the second level of PH (see Chapter 7 of Arora-Barak, which we followed for this part of the lecture). There is also an alternative proof for this (and more) by Goldreich and Zuckerman.

We then switched to talk about pseudrandom sets or equivalently pseudorandom generators (PRG) (Chapter 20 of Arora-Barak). We saw how a PRG against circuits would allow us to derandomize efficient algorithms. This is a neat applications of circuits – to derandomize uniform algorithms, we need to fool these non-uniform circuits. Next time we will see that circuits play a central role in the construction of PRG as well. We will see that a hardness generator (generator that outputs the truth table of a hard function) yields a pseudorandomness generator. Thus, improving circuit lower bounds is a route for derandomization!

But before going into that, we saw one example of a pseudorandom set, one that fools a very specific algorithm – the algorithm that computes a random parity of its input. This pseudorandom set, introduced by Naor and Naor in the early 90s, is a very important object in theoretical computer science and is called a small-bias set. We saw a construction of such a set, called the Powering Construction, mainly so to give an example of how to construct (and even more importantly – analyze) things that look random (but also because we will use small-bias sets later on). A very good talk available online about small-bias sets was given by Amir Yehudayoff.

Next lecture we will show how to construct a PRG given a hardness generator. However, in this course we are more interested in the other direction of the tradeoff, so we will only sketch the proof and start to cover a bit more theory we need so to prove the other direction, namely, prove that derandomization implies circuit lower bounds!

A great online talk about Hardness-Randomness tradeoffs was given a few years ago by Kabanets. Another more introductive and high level video lecture about pseudorandom generators by Impagliazzo was given a few years ago: part 1 and part 2. For a more formal treatment see an extensive survey about derandomization of complexity classes by Miltersen.

Lecture Notes

The lecture notes are available here. The file will be updated over time. Currently it contains the notes for the first four lectures.

Lecture 4

Most of the lecture today was devoted to prove Razborov-Smolensky Theorem ’87, following chapter 14 in Arora-Barak.

We then switched to talk about randomization in computation. The goal is to introduce the first topic of this course, which is, to my opinion, the second greatest result in complexity theory (right after the PCP Theorem – someone should convience someone to give a course on this at Weizmann..), namely, Hardness-Randomness tradeoff (or as I like to call it – Hardomness).

We gave an example of a randomized algorithm for the Polynomial Identity Testing problem, on the way introduced to algebraic circuits. The analysis is based on the famous Schwartz-Zippel Lemma. We omitted a proof for the lemma. A standard proof can be found in chapter 7 of Arora-Barak. See an alternative proof by Dana Moshkovitz (who was a Ph.D. student at Weizmann). There is a great, recent survey talk by Ran Raz about arithmetic circuits (on my computer the talk sometimes gets stuck).

We also mentioned that the Permanent is complete for the class VNP, which is an algebraic analoug (though non uniform) to the class NP, introduced by Valiant. This will be a project for the end of the semester talk. For now, you can view a great talk available online by Amir Yehudayoff on this (Amir was also a Ph.D. student at Weizmann).

Lecture 3

Today we continued to talk about classical results in circuit complexity. We saw Karp-Lipton Theorem ’80: NP has polynomial size circuits implies the collapses of the Polynomial Hierarchy to its second level, thus supporting circuit lower bounds as a route for separating P from NP.

A similar theorem, attributed to Meyer ’80, shows that if EXP has polynomial size circuits then EXP collapses to the second level of the Polynomial Hierarchy (later on we will prove something stronger). From this we deduced a neat corollary, namely, if EXP has polynomial size circuits then P is not equal to NP. That is, circuit upper bounds can potentially separate P from NP!

A third classical theorem we saw was Kannan Theorem ’81. This theorem states that there is no fixed polynomial size circuits for the second level of the Polynomial Hierarchy.

Going in a somewhat different direction, we proved a 3(n-1) lower bound for the number of AND,OR gates in any Boolean circuit that computes the PARITY function. The proof, by Schnorr ’74, is very simple and is based on an approach called gate-elimination. Unfortunately, this lower bound is not far from the best known lower bound 5n-o(n) proven by Iwama, Lachish, Morizumi and Raz. This paper appears in the end of the semester talks.

We then started to talk about subclasses of P/poly, especially AC^i and NC^i. We stated a famous result by Hastad (improving upon previous results) that an AC^0 circuit that computes PARITY has exponential size. This result also participates in the end of the semester talks (including a very recent paper of Hastad). The latter result suggests adding unbounded fan-in PARITY gates to AC^0 circuits, or more generally, adding counters to AC^0 circuits. This class is called ACC^0 (or sometimes simply ACC).

We stated Razborov-Smolensky Thoerem ’87, which shows that for distinct primes p and q, the MOD_q function is not in ACC(p), and in fact requires exponential size for constant depth. We will see the proof of this thoerem next time. Anyhow, this implies that ACC(7) is weak (as, for example, it cannot compute PARITY). What about ACC(6)? This seemingly innocent question turned out to be notorious. At this point we were finally able to state and appreciate the result by Williams.

Next lecture we will prove Razborov-Smolensky and will start to talk about randomization in computation. Also, the scribe notes for the first two lectures should be uploaded to the blog soon.

Papers for the end of the semester talks

Below are papers for the end of the semester talks. It offers both classical as well as cutting edge results. The list will grow with time. I suggest you’ll read the abstracts, choose a paper and let me know if you want it so I will reserve it for you. Recall that the talks are in individuals, are on the board (not presentations) and should take 50-90 minutes. Most importantly – they should be great!

Circuit Lower Bounds

An Explicit Lower Bound of 5n – o(n) for Boolean Circuits by Kazuo Iwama, Oded Lachish, Hiroki Morizumi and Ran RazReserved by Daniel Reichman.

Circuit Lower Bounds for Merlin-Arthur Classes by Rahul SanthanamReserved by Inbal Livni.

On the Correlation of Parity and Small-Depth Circuits (and references therein) by Johan Hastad.

Fixed-Polynomial Size Circuit Bounds by Lance Fortnow, Rahul Santhanam and Ryan Williams

The Monotone Circuit Complexity of Boolean Functions by Noga Alon and Ravi B. Boppana  / Alexander A. Razborov.

Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates by Ran Raz and Amir Shpilka.

Lower Bounds for Matrix Product by Amir ShpilkaReserved by Asaf Ziv.

Elusive Functions and Lower Bounds for Arithmetic Circuits by Ran Raz.

Lower Bounds on Arithmetic Circuits via Partial Derivatives by Noam Nisan and Avi WigdersonReserved by Ron Rothblum.

A Lower Bound on the Mod 6 Degree of the OR Function by Gabor Tardos and David A. Mix BarringtonReserved by Igor Shinkar.

Hardness Amplification within NP by Ryan O’DonnellReserved by Elazar Goldenberg.

Barriers

Natural Proofs (see also Chapter 23 in Arora-Barak book) by Alexander A. Razborov and Steven Rudich.

Algebrization: A New Barrier in Complexity Theory by Scott Aaronson and Avi WigdersonReserved by Shlomo Jozeph.

Limits on Alternation-Trading Proofs for Time-Space Lower Bound by Samuel Buss and Ryan Williams.

Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators by Andrew Drucker.

Natural Proofs versus Derandomization by Ryan WilliamsReserved by Avishay Tal.

Hardness vs. Randomness / Pseudorandom Generators / Derandomization

Hardness vs. Randomness by Noam Nisan and Avi Wigderson. Reserved by Yuval Madar.

Pseudorandomness from Shrinkage by Russell Impagliazzo, Raghu Meka and David ZuckermanReserved by Ilan Komargodski.

Better Pseudorandom Generators from Milder Pseudorandom Restrictions by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan and Salil VadhanReserved by Tal Wagner.

A Derandomized Switching Lemma and an Improved Derandomization of AC0 by Luca Trevisan and TongKe Xue.

BPSPACE(S) ⊆ DSPACE(S^{3/2}) by Michael Saks and Shiyu ZhouReserved by Dean Doron.

Undirected Connectivity in Log-Space by Omer ReingoldReserved by Yuval Tanny.

Pseudorandom Generators for CC_0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields by Shachar Lovett, Partha Mukhopadhyay and Amir Shpilka.

Poly-Logarithmic Independence Fools AC0 Circuits by Mark BravermanReserved by Eylon Yogev.

Graph NonIsomorphism has Subexponential Size Proofs unless the Polynomial-Time Hierarchy Collapses by Adam R. Klivans and Dieter van MelkebeekReserved by Sagie Benaim.

Pseudo-random Generators for All Hardnesses by Christopher UmansReserved by Bharat Ram Rangarajan.

Randomness vs. Time: De-Randomization Under a Uniform Assumption by Russell Impagliazzo and Avi WigdersonReserved by Uri Sherman.

Easiness Assumptions and Hardness Tests: Trading Time for Zero Error by Valentine KabanetsReserved by Rani Izsak

Randomness in Linear Space by Noam Nisan and David Zuckerman. Reserved by Or Lotan.

On Approximate Majority and Probabilistic Time by Emanuele Viola

Other Neat (and Related) Results in Complexity (some of which we used without a proof)

IP = PSPACE (see also Theorem 8.19 in Arora-Barak book) by Adi Shamir / Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan. (it is instructive to check out Or Meir’s proof as well). Reserved by Shani Nitzan.

Non-Deterministic Exponential Time has Two-Prover Interactive Protocols (that is, NEXP=MIP – the genesis of the PCP Theorem) by Laszlo Babai, Lance Fortnow and Carsten Lund. Reserved by Anat Ganor.

Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1 (aka Barrington’s Theorem) by David A. BarrringtonReserved by Dima Kogan.

Hierarchy Theorems for Probabilistic Polynomial Time by Lance Fortnow and Rahul Santhanam.

The Random Oracle Hypothesis is False by Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan and Pankaj Rohatgi. Reserved by Tom Gur.

PP is as hard as the Polynomial-Time Hierarchy  by Seinosuke Toda (for a proof, see also chapter 17  in Arora-Barak book). Reserved by Noa Ben-Zvi.

The Complexity of Computing the Permanent  by Leslie Valiant (for a proof, see also chapter 17 in Arora-Barak book). Reserved by Ami Mor.

Lecture 2

Today’s lecture was split into two. In the first part we learned the very basics of the Polynomial Hierarchy, introduced by Meyer and Stockmeyer ’72. For that we followed chapter 5 from Arora-Barak book. We saw that each level of PH has a complete language, though PH itself does not have such a language unless PH collapses (to some level). As a corollary, we proved that PH \neq PSPACE unless the polynomial hierarchy collpases. We briefly mentioned the language TQBF which is complete for PSPACE, and in fact, also for NPSPACE (and thus PSPACE = NPSPACE). We finished by mentioning an equivalent definition of the levels of PH using oracles, namely, Sigma_{i+1}^p = NP^{Sigma_i^p} (see Theorem 5.12 from Arora-Barak book). We will see another equivalent definition in terms of circuits, due to Papadimitriou and Yannakakis ’82, next time.

One neat application of the polynomial hierarchy, which we skipped completely, is a result regarding time/space tradeoff for SAT, first studied by Fortnow ’97. The goal of this problem is to prove that SAT cannot be solved in time n^a and space n^b simultaniously, for constants a,b. Theorem 5.11 in Arora-Barak book shows this for a=1.2, b=0.2. See a recent paper by Samuel R. Buss and Ryan Williams, and references therein. This paper, as well as some related papers, will be added to the list of papers for the end of the semester talks.

In the second part of the lecture we defined circuits, following chapter 6 of Arora-Barak book. We saw that every function on n inputs can be computed by a circuit with size n 2^n, and that most functions require 2^n / n size circuits. In fact, the latter expression is the “right” one. In 1958 Lupanov proved that every boolean function on n variables can be computed by a circuit with size (1+alpha_n) 2^n / n, where alpha_n ~ log n / n. Check out Theorem 1.15 from the wonderful recent book by Stasys Jukna. The size hierarchy theorem is Theorem 4.3 in that book.

We then defined the “P of circuits”, namely, P/poly, and proved that P is contained in P/poly (Theorem 6.6 in Arora Barak book). Thus, showing that NP is not contained in P/poly would separate P from NP. This kind of results are called circuit lower bounds, as we want to prove a lower bound on the size of (a family of) circuits that compute a language in some class (NP in this case). This approach seems to overcome the relativizing barrier we saw last time, as circuits are more amendable to white-box inquiry than Turing machines.

It is conjectured that NP should not be contained in P/poly. For one, the vast majority of functions require exponential-size circuits. What are the chances that the entire NP sits in this tiny corner of polynomial-size circuits? (but who knows, P does..) We will see other results next time that supports this conjecture. As mentioned in class, we currently don’t even know how to prove that NEXP is not contained in P/poly (or even the potentially larger class EXP^NP). We do know to prove that NEXP^NP is not contained in P/poly, and in fact, something stronger, though we do not have enough theory to describe the result at this point.

Another attempt is to look at sub-classes of P/poly (e.g., constant depth circuits), and indeed, in this course we will prove that some sub-class of P/poly, which we will meet next time, (called ACC^0) does not contain NEXP. This is a cutting-edge result proved by Ryan Williams. (in the course we will follow a web addendum for Arora Barak book).