Guidelines for a reading group in introduction to computational complexity

Oded Goldreich

Quick links: The notes on P, NP, and NPC, P/poly and PH, space complexity, randomness and counting, hardness amplification, pseudorandomness, probabilistic proof systems, and average-case complexity.

GENERAL NOTES ABOUT THE COURSE

This guided reading course is based on my book Computational Complexity: A Conceptual Perspective. (All sections and exercises refer to this book.) An e-copy of the book will be sent to you upon request. In addition, I have a few hard copies that I can lend out.

The conceptual perspective. This guided reading course (as the book it uses) is not aimed at merely teaching technical material, but rather also aims at addressing the question of why are certain questions asked. The answers are rooted in natural (intuitive) concepts and concerns, and we shall pay attention to how these intuitive concepts (resp., concerns) are formalized in definitions (resp., rigorous questions).

Thus, even if you know some material from other studies, please read the assigned material (and, especially, the high level discussion). In general, don't "fast-forward" over the "easy" conceptual discussions, but rather read them carefuly, think them over, and even criticize (but not for the sake of critique or posing clever -- we have no time for poses...).

Overview versus details. Sometimes, details are crucial, but the overview comes first. Don't get too entangled in the details, always keep in touch with the overview. If you fail to understand some details, make sure first that you understand the overview. Then, try to "locate" your difficulty.

The homework assignments. The "homework assignments" (about 4 per semester) are meant to provide a framework for the course. They are meant to be light load, so don't ever spend too much time on them (i.e., more than a few hours). If you cannot do the homework assignment in a couple of hours, then it may be the case that you got entangled in some low-level details, which is not my intention. In such a case, please consult other students, and if necessary consult me. But do so before wasting too much time on it!

The reading assignments. The required reading for the next meeting will be called reading assignment (and this is what you should not skip, even if you learned the material before). In addition, I will offer optional reading (which is not mandatory).

Varying difficulty. The reading assignments vary in their difficulty, and I am providing my estimates based on past experience. In the few exceptionally difficulty assignments (estimated at 4 and above on a scale of 5), I suggest inviting me to join your meeting.

Errors and additions to the book. As any text, the book contains some unfortunate errors. In case of doubts, please consult the list of currently detectable errors, gaps and missing clarifications in the webpage of the book. Needless to say, I'd be grateful for pointing out add'l errors, which I'm sure exist, unfortunately.

These notes were prepared for prior incarnations of this reading group, which involved closer involvement of myself. Currently, you are more on your own, but still don't hesitate to ask me for help whenever you really need it.

NOTES FOR 1ST MEETING

Topic: P-versus-NP.
Estimated difficulty: 1 in the scale of 5.

Indeed, the P-vs-NP question will be our first topic. I do expect that almost all of you heard these terms before, but I guess that most did not get an adequate perspective on it. Therefore, I insist that you read the relevant Section 2.1, and test yourself with the quiz provided below. (Specifically, this section contains a formulation of the P-vs-NP question/conjecture in terms of search problems as well as a definition of NP in terms of proof systems.)

If you care, see my handwritten preparation notes (partially in Hebrew): Sheets 1 and 2.

BACKGROUND BEING ASSUMED: Familarity with the notion of an algorithm, and the basic formulations of computability theory. Take a look at Section 1.2.1-1.2.3 of the book and read it if you don't know it. [This is not a reading assignment, but rather the "prerequisite".] (A more detailed description of the background, with some exercises, is provided in chapter 1 of my Basic Complexity book available at ~oded/bc-book.html.)

READING ASSIGNMENT:

  1. A short section on Universal Algorithms (Sec 1.2.3.4)
  2. A short section on Time Complexity (Sec 1.2.3.5)
  3. The P-vs-NP Problem in its two formulations (Sec 2.1.0-2.1.4 and Sec 2.1.6, where Sec 2.1.0 means the part of Sec 2.1 that comes before Sec 2.1.1).
A revision of Sec 2.1 appears as Chapter 2 of my Basic Complexity book (available HERE); the pace there is a bit slower and more details are given.

SUGGESTED OPTIONAL READING

  1. The "traditional definition of NP" and how it fits in (Sec 2.1.5).
  2. Meditations, only if you are philosophically inclinded! (Sec 2.1.7).
SUGGESTED QUIZ FOR THE BACKGROUND MATERIAL (not to be submitted): SUGGESTED QUIZ FOR SEC 2.1 (not to be submitted): SUGGESTED EXERCISES FOR SEC 2.1 (not to be submitted):

NOTES FOR 2ND MEETING

Topic: Polynomial-time reductions.
Estimated difficulty: 1 in the scale of 5.

The topics of the reading assignment (for next meeting) refer to poly-time reductions. As stressed in prior meeting, I wish to stress that there is nothing fundamental in using polynomials as bounds on efficient computation. This is merely a natural and convenient convention; the phenomena that we discuss (e.g., finding vs checking, deciding vs verifying based on proofs, reductions, etc) are independent of this convention, but are best captured by using it.

I wish to highlight the general notion of a reduction (and poly-time reduction), which is fundamental beyond its role in the theory of NPC. The general notion of an oracle machine [Sec 1.2.3.6] is the basis of the general definition of a reduction, sometimes called Turing-reductions, and we focus on poly-time reductions, which are called Cook-reductions. Note that Karp-reductions (i.e., reduction by mapoping/translation/encoding) as used in the theory of NPC are a restricted/special case of Cook-reductions.

The notion of Cook-reductions is used in discussing the reduction of optimization problems to search problems, and the reduction of search problems to decision problems. Each search problem $R$ is reducible to $S'_R = \{\pair{x,y'} \exists y'' (x,y'y'')\in R\}$ (which is a decision problem...), but in some cases $R$ is reducible to $S_R = \{x: R(x)\neq\emptyset\}$. In the latter case, we say that $R$ is self-reducible.

READING ASSIGNMENT

  1. A short section on oracle machines (Sec 1.2.3.6)
  2. Polynomial-time reductions (Sec 2.2.0-2.2.3).
Section 2.2.3.2 assumes you know the definition of NP-completeness; if you don't please read Sec 2.3.1 before.

SUGGESTED OPTIONAL READING

SUGGESTED QUIZ FOR SEC 2.2 (not to be submitted): SUGGESTED EXERCISES FOR SEC 2.2 (not to be submitted):

NOTES FOR 3RD MEETING

Topic: NP-completeness (NPC).
Estimated difficulty: 1 in the scale of 5.

Yes, I know most of you heard about NP-completeness, but I wish to highlight a few things. Firstly, the very existence of NP-complete problems, which is non-obvious a priori! Secondly, it is easier to establish the existence of NPC than to prove that natiral problems such as SAT are NPC. (Indeed, SAT and other famous NPC problems are very natural computational problems, more natural than "bounded halting", although the latter is not as unnatural as usually perceived...) Thirdly, when proving that SAT is NPC, I advocate decoupling the reduction of NP to SAT into two reductions: The 1st reduction is from NP to CSAT, and the 2nd from CSAT to SAT. The 1st reduction relies on the fact that circuits can emulate the computation of Turning machins (TMs) on inputs of fixed length, while the 2nd reduction shows that CNFs with auxiliary variables can "emulate" the computation of arbitrary circuits. These are important "lessons to take home".

Note that assuming that $P\neq NP$, there exist problems in $NP-P$ that are not NPC. Make a picture of the "world" under this assumption, and ask what does the "world" look if $P=NP$.

READING ASSIGNMENT

  1. NP-completeness (Sec 2.3.0-2.3.3.1); this covers the definitions, existence of NPC, and NPC of CSAT/SAT.
  2. When reading Sec 2.3.3.1, read also Sec 1.2.4.0-1.2.4.1 (for perspective).
  3. Read the first page of Sec 2.3.4 (i.e., Thm 2.28). Reading the proof sketch is not required. I want you to understand Thm 2.28 and its meaning, and I don't care if you have no clue re how to prove it.
SUGGESTED OPTIONAL READING
  1. If you did not see other NP-completeness proofs before, then you may want to read Sec 2.3.3.2.
  2. Read and think (but don't overdo nor submit) Exer 2.28, 2.29, and 2.30, which discuss add'l features of some (standard/modified) Karp-reductions.
  3. Meditations (Sec 2.2.4 and 2.3.5).
  4. The proof sketch of Thm 2.28 may be hard to get. It is better to read it after reading simpler proofs "by diagonalization" such as the proof of Thm 4.3 (which you may read now...). In any case, if you decide to look at the proof sketch of Thm 2.28, be prepared to only get a vague feeling of how it is proved (see first page of this sketch). That is, try to get the basic idea. It is likely that if you want to get the proof in all its details, this may require much time (possibly consulting other sources...), and I do not recommend spending so much time on it.
SUGGESTED QUIZ FOR SEC 2.3 (not to be submitted): SUGGESTED EXERCISES FOR SEC 2.3 (not to be submitted):

NOTES FOR 4TH MEETING

Topics: promise problems, optimal search algorithms, and coNP.
Estimated difficulty: 1.5 in the scale of 5.

This time you get a homework assignment, to be submitted by DATE1. (This is more time than you need, so please do not ask for extensions.) Also bear in mind my warning regarding not spending too much time on homework and/or exercises.

The following reading assignment consists of three parts.

The FIRST part (Sec 2.4.1 on "promise problems") is mainly conceptual, and it elaborates on an important issue that were mentioned already (in prior sections of the book). Specifically, the point is that natural computational problems are actually promise problems (with an efficiently recognizable promise), although they are computationally equivalent to computational problems with a trivial promise (i.e, standard decision and search problems). This issue will be ignored in the rest of the course. You should understand what are they issues involved and why (and when) we can ignore them. Furthermore, the formalism of promise problems is essential in some places (see an example next).

One special type of promise problems that is of interest is the notion of a "candid search problem", which is a promise problem consisting of finding solutions when promised that such exist. Note that the promise may not be poly-time decidable.

The SECOND part (sec 2.4.2) is an intriguing claim asserting that we do know the best (i.e., optimal in a natural sense) algorithm for any candid search problem in PC, we just don't know its running time. But you may be diappointed when seeing what this algorithm does.

The theorem states that for every $R\in\PC$, there exists a polynomial $p$ and an algorithm $A$ that solves the candid search problem of $R$ such that for every $A'$ that solves the candid search problem of $R$ it holds that $t_A(x) = \tildeO(t_{A'}(x)+p(|x|))$, where $t_B(x)$ denotes the number of steps of $B(x)$ and $\tildeO(n) = n\cdot \poly(\log n)$. (The $\tildeO$ expression in $t_A(x) = \tildeO(t_{A'}(x)+p(|x|))$ depends on $A'$.)

The LAST part (Sec 2.4.3) introduces the class coNP, and sheds light on the difference between Karp and Cook reduction in the context of reductions among decision problems. In particular, it is proved that (i) NP-complete sets cannot be in coNP, where completeness is under Karp-reductions; and (ii) that NP-complete sets cannot be Cook-reduced to a set in NP intersection coNP. (Note that (i) talks about being in some class, whereas (ii) talks about being Cook-reducible to some class.)

READING ASSIGNMENT: Basically it is to read Sec 2.4 (i.e., "Three Advanced Topics"). Please read Exercise 2.36 (without the guideline and Part 3).

HOMEWORK ASSIGNMENT (to be submitted by DATE1):

  1. Exercises 2.10 and 2.11, which I discussed shortly in the Nov 7th meeting.
  2. Exercise 2.13 and Part (1) of Exercise 2.14. See add'l guidelines in the correction list at the book's webpage
  3. Bonus (not required!): Exercise 2.36.
SUGGESTED *OPTIONAL* READING -- REPEATING THE LAST ONE:
  1. Digest and general perspectives re poly-time reductions (Sec 2.2.4).
  2. If you did not see other NP-completeness proofs before, then you may want to read Sec 2.3.3.2.
  3. Read and think (but don't overdo nor submit) Exer 2.28, 2.29, and 2.30, which discuss add'l features of some (standard/modified) Karp-reductions.
  4. Meditations, only if you are philosophically inclided! (Sec 2.1.7).
  5. The proof sketch of Thm 2.28 may be hard to get. It may be better to read it after reading simpler proofs "by diagonalization" such as the proof of Thm 4.3 (which you may read now...). In any case, if you decide to look at the proof sketch of Thm 2.28, be prepared to only get a vague feeling of how it is proved (see first page of this sketch). That is, try to get the basic idea. It is likely that if you want to get the proof in all its details, this may require much time (possiblly consulting other sources...), and I do not recommend spending so much time on it.
SUGGESTED QUIZ FOR SEC 2.4 (not to be submitted):

NOTES FOR 5TH MEETING

Topic: P/poly and the Polynomial-time Hierarchy (PH).
Estimated difficulty: 2.5 in the scale of 5.

The following reading assignment consists of three small parts.

The FIRST part (Sec. 3.1) presents two alternative definition of the class P/poly (via poly-size circuits and via "machines that take advice"), proves their equivalence (Thm 3.6), and shows that P/poly (and in fact even P/1) contains P as well as some undecidable sets (Thm 3.7). The formalism of "machines that take advice" offer a way of measuring the amount of non-uniformity.

The SECOND part (Sec. 3.2.1) presents a definition of the "Polynomial-time Hierarchy" (PH) and its various levels. The main definition is in terms of "quantifier alternation", but an alternative using "non-deterministic poly-time oracle machines" is also presented (in optional reading -- see Sec 3.2.2).

The LAST part (Sec 3.2.3) links the two first parts. Specifically, Thm 3.12 (known as "Karp-Lipton Thm"), states that if NP is in P/poly then PH collapses to its 2nd level. The proof (sketched next) has inspired many follow-ups and is important to internalize. 

The initial observation is that it suffices to prove that Pi_2=Sigma_2
(and in fact this is the formulation used in Thm 3.12).
Thus, starting with $S\in\Pi_2$ and using the hypothesis
(i.e., "NP in P/poly"), we shall show that $S\in\Sigma_2$.
The second observation is that $S=\{x:\forall y, (x,y)\in S'\}$,
where $S'$ is an NP-set (and $|y|=\poly(|x|)$).
Now comes the main step of the proof:
It is that $x$ is in $S$ if and only if there exists
a polynomial-size circuit $C$ that "decides $S'$ correctly
on *all* inputs of length $m=\poly(|x|)$" and $C(x,y)=1$
for *all* strings $y$ of length $m-|x|$. Note that the condition
has the form "there exists such that for all" (i.e., a Sigma_2-form),
but the issue is whether the 1st condition (i.e., the one in quotes)
is poly-time decidable. The traditional proof appears in Exer 3.11, 
but we prefer the following alternative.

Since NP is in P/poly, it follows that PC is in the serach version of P/poly
(because PC is Cook-reducible to NP). 
Now, letting $R'$ be the witness relation of $S'$
(i.e., $S' = \{(x,y):\exists z ((x,y),z)\in R'$), 
we have (schematically) $x\in S$ iff $\forall y \exists z ((x,y),z)\in R'$.
Now, *if* the circuit $C$ solves the search problem $R'$,
then we have $x\in S$ iff $\forall y ((x,y),C(x,y))\in R'$
(because $(x,y)\in S'$ iff $((x,y),C(x,y)) \in R'$).
Furthermore, and this is a crucial observation, if $x\not\in S$,
then no matter what $C'$ you take, there exists $y$ s.t. $C(x,y)$
is not a solution to $(x,y)$ wrt $R'$ (because no solutions exist).
Hence (ignoring details (*)), $x\in S$
iff $\exists C\forall y ((x,y),C(x,y)) \in R'$
(which can be written as $\exists C\forall y \Phi(x,C,y)$,
where $\Phi$ is a condition that can be evaluated in polynmial-time).

*) ignoring details such as the fact that we are quantifying 
over strings of adequate length.
Indeed, the foregoing proof is the sole reason for my estimate that this meeting is significantly more difficult than all prior ones.

READING ASSIGNMENT: Read almost all of Chapter 3 (on the classes P/poly and PH). You may skip Sec 3.2.2 (PH defined by ND poly-time oracle machines).

SUGGESTED EXERCISES FOR Chap 3 (not to be submitted):

All these exercises are supposed to be easy.

SUGGESTED *OPTIONAL* READING:

  1. Read also Sec 3.2.2. Note the warning on the "non-generic" meaning of the notation ${C_1}^{C_2}$ (bottom of page 118).
  2. Exercise 3.11.
SUGGESTED QUIZ (which is actually a digest) FOR CHAPTER 3
Since the answers are not explicit in the text, they are provided HERE.

NOTES FOR 6TH MEETING

Topic: Do more resources yield more power?
Estimated difficulty: 1 in the scale of 5.

In the context of non-uniform computation the answer is a definite YES: Sec 4.1 asserts that $P/(\ell+\omega(1))$ strictly contains $P/\ell$, provided that $\log_2 \ell(n) \leq n-\omega(n)$.
[Actually, a stronger statement holds -- see corrections on the web-site of the book (or text): It holds that $P/(\ell+1)$ strictly contains $P/\ell$, provided that $\log_2 \ell(n) \leq n$.]

In the context of uniform computation, the answer is yes *provided* that these resources are "self measureable" (i.e., measured by an algorithm that does not use more than the measured amount of resources). Intuitively, if a resource is not self-measurable, then it cannot be used "safely" (i.e., you cannot use the specified amount of resources without risking exceeding it).

Def (for any reasonable and general model of computation): we denote by $DTIME(t)$ the class of sets that can de decided within time complexity $t$ (in this model, which "should" appear as subscript in DTIME, if we are pedantic).

Recall (the Cobham-Edmonds thesis): Upto a polynomial composition, the class $DTIME(t)$ is the same for all reasonable models. Note that the exact class (without the aforementioned slackness) are not model independent...

Def (time constructability): $f:\N\to\N$ is *time constructible* (in the model) if there exists an algorithm that on input $n$ computes $t(n)$ within $t(n)$ steps.

EXER: For every algorithm $A$, the function f(n) that equals the number of steps of A on input $1^n$ is time constructible (by running $A$ itself + mapping $n$ to $1^n$, where the latter overhead can be compensated by linear speed-up).

Cor 4.4: For every reasonable and general model of computation, there exists a polynomial $p$ such that for every time constructible $t_1$ (that is at least linear) it holds that DTIME(t_1) is strictly contained in $DTIME(p\circ t_1)$. 

PROOF: The idea is that in such a model, $t_1$ steps of any machine $M$ 
can be emulated by less than $p \circ t_1 /2$ steps of an emulating machine.

Fixing $t_1$, for each machine $M$ we define a "truncated emulation" $M'$
such that $M'(x)=1$ iff $M(x)$ halts within $t_1(|x|)$ steps with output 1.
Otherwise, $M'(x)=0$ (e.g., if $M(x)$ does not halt within $t_1(|x|)$ steps).
By the above, $M'$ has running time smaller than $p\circ t_1/2$.

For any (simple) mapping of machines $M$ to inputs $x_M$,
define $f(x_M) = 1-M'(x_M)$. Then $f$ is in DTIME(p \circ t_1 /2)$,
but cannot be in DTIME(t_1)$ as otherwise we derive a contradiction
by considering the machine $M_f$ that computes $f$ in time $t_1$
(and, specifically, considering what this machine does 
on the corresponding input $x_{M_f}$).  QED

Regarding the terminoloy: Hierarchy Theorems refer to the "normal" case in which more resources provide more power (or more ability; i.e., ability to perform more tasks = solve more problems). In contrast, Gap Theorems assert that under some weird circumstances, resources does not provide more power; this is viewed as a "gap" in the (computing) power as a function of resources (where within the "gapped" region, power does not increase).

READING ASSIGNMENT: Read almost all of Chapter 4, skipping Sec 4.2.1.3.

  1. Sec 4.1 (non-uniform hierarchy) is a very easy read.
  2. Sec 4.2.0-4.2.1.2 (Time hierarchy) is the core of the current assignment.
  3. Sec 4.2.2 (Gaps and Speedups) is more important for the stated results, not their proofs. Make sure you understand what Thms 4.7 and 4.8 say.
  4. Sec 4.2.3 merely discusses analogues for space complexity. Note that emulation is "easier" wrt *space* (compared to *time*).
SUGGESTED OPTIONAL READING
  1. Sec 4.2.1.3 (Thm 4.6: NTIME hierarchy) is recommended as a good warm-up towards the proof of Thm 2.28 ("NPI").
  2. Now, one can try to read the proof of Thm 2.28 (i.e., on NP-sets that are neither in P nor NP-complete). Although it does *not* build on the proof of Thm 4.6, it uses the idea of "delayed diagonalization" which is easier to grasp in the context of the proof of Thm 4.6.
I'm not sure about suggesting to look for the proof of Thm 4.8 in other sources.

SUGGESTED EXERCISES FOR Chap 4 (not to be submitted):

SUGGESTED QUIZ (which is actually a digest) FOR CHAPTER 4
Since the answers are not explicit in the text, they are provided HERE.

NOTES FOR 7TH MEETING

Topic: Space complexity - Part 1 (basics).
Estimated difficulty: 1 in the scale of 5.

Space complexity is of intrinsic interest, but is also interesting as offering a perspective (and sometimes a contrast) to issues w.r.t time complexity.

When studying space complexity, we wish to account for the storage ("space") used for the actual computation as opposed to the storage taken by the input and output. This is crucial since we are often interested in sub-linear space complexity, and conventions should be introduced in order to distinguish space used for ("active") computation from space used for ("passive") storage of the input and output. This is done by using separate storage for each of the three roles. That is, we use a read only input device, a write only output device, and a storage device for performing the actual computation (i.e., for storing the intermediate results of the computation), called the work space device. Only the work space device is charged for space consumed by computation, and the read-only and write-only conventions prevent abuse of the other (i.e., input and output) devices for conducting computation.

While one may conjecture that the minimal amount of (super-constant) storage that can be useful for computation is logarithmic (since it seems that one needs to "compute" the input length in order to allocate the space consumption), this turns out wrong (i.e., double-logarithmic is the correct lower bound for computations that cannot be performed in constant amount of space). Nevertheless, we shall only consider space complexity that is at least logarithmic (in the input length).

Issue to discuss: The "instantaneous configuration" (of a machine during a computation) is often decoupled into a fixed part and a variable part, where the partition is application-dependent. E.g., in the proof of Thm 5.3, the input is fixed, and the location of the head on it as well as the contents of the work space (and the location on it) are the variable parts. In such cases, one often ignores the fixed part, and refers to the variable part as the instantaneous configuration.

READING ASSIGNMENT:

  1. Sec 5.1 ("space complexity -- general issues"), but *skip* most of Sec 5.1.3.3 ("subtleties re space-bounded reductions") from the Teaching Note on p. 150 (i.e., start skipping there). Do read Sec 5.1.4 and also the laconic sections 5.1.3.4-5.1.3.6.
  2. Sec 5.2.0-5.2.3 (see, in particular, Thm 5.4 and 5.5).
SUGGESTED *OPTIONAL* READING:
  1. Look at Exer 5.3 and 5.4 (on double-logarithmic space complexity), but do *not* exhaust yourself with attempts to provide all low-level details for these exercises.
  2. Read all of Sec 5.1.3.3 (i.e., including the part skipped in the main assignment).
SUGGESTED EXERCISES (not to be submitted): SUGGESTED QUIZ (for Sec 5.1)

NOTES FOR 8TH MEETING

Topic: Space complexity - Part 2 (UCONN in L).
Estimated difficulty: 5 in the scale of 5. Highly recommended to ask me to attend the meeting.

[Class of 2018/19 recommendation: Split this meeting into two. One of expander graphs and one on the actual UCONN algorithm. (Oded: If you do so, then you may want to read all of Apdx E.2 for wider perspective and more comfort with expander graphs).]

[NOTE: I was debating with myself whether to assign you first the NL=coNL (incl reading about NSPACE) or to start with the log-space algorithm for deciding undirected connectivity of graphs (UCONN). The latter algorithm (especially its details) is far more complex, but the setting (unlike NSPACE) is more familiar and less problematic (from a conceptual point of view). So I still tend to suggest starting with UCONN, but you should feel free to take the alternative route.]

Warning: This reading assignment is significantly more difficult than any of the material covered so far; it is focused on a rather sophisticated algorithm and analysis.

The reading sequence that I propose starts with the overview of the UCONN algorithm (Sec 5.2.4.0). They key observation is that if the input graph were of (1) bounded degree and (2) logarithmic diameter, then a simple log-space algorithm can solve the problem by "enumerating" all possible paths. But, of course, the graph may not satisfy these conditions and so the idea is to transform it to a graph that does satisfy these condition while preserving the relevant connectivity property. (Needless to say, this conversion should be performed in log-space.)

As a warm-up, note that we can easily transform the graph into one that supports one of the properties but not the other. (1) We can make the graph 3-regular by replacing each vertex $v$ of degree $d(v)$ by a $d(v)$-cycle and connect edges between "representatives". (2) We can reduce the diamater of a graph by "raising it to a power". But we wish to transform (each connected component of) the graph into one that has both bounded degree and logarithmic diameter.

Sec 5.2.4.1 present the foregoing transformation at an abstract level (i.e., avoiding the question of effecting it in log-space). You will need to read first about expander graphs and about the zig-zag product (Apdx E.2.1.1 and E.2.2.2 will do!). Once you read these, read Sec 5.2.4.1 (again or for the 1st time).

Basically, what is done is interleaving steps of reducing the diameter (or actually increasing expansion) with steps of decreasing the degree. The expansion is increased by raising the graph to a constant power, and the degree is reduced by the zig-zag product. We take a logarithmic number of such iterations, to increase expansion from (the trivial) 1/poly to a constant.

Surely, implementing the above sequence of transformations in the straighforward way will not do (as it will yield a space bound of log-square). The key ideas presented in Sec 5.2.4.2 are (i) implementing an "oracle access to the current graph" rather then actually printing it. (ii) using a "global" accounting for the space used by recursive calls of a subroutine (see the notion of "global-tape oracle machine"). The relevant computation in that model are illustrated HERE.

ADD'L INTUITION

Recall that the algorithm is motivatied by considering the diameter of the graph, but the actual analysis cannot be carried out in these terms. This is the case because the diameter reduction effect of the powering is undone (as far as a local analysis goes) by the diameter increase caused by the degree reduction.

However, it is common in mathematics (incl in TCS) to use an invariance and/or a parameter that is stronger than the one that we actually want. Hence, instead of diameter, we may consider the "mixing time" (of the graph), defined as the minimum number of random steps you need to take (when starting from any fixed vertex) till you get to a distribution that is close to the uniform (say get to a distribution in which each vertex is reached with probability $(1\pm0.1)/n$). So "mixing time" can be viewed as a strengthening of diameter; in particular, the diameter is upper bounded by the mixing time... Also note that in a few weeks we shall see than any $n$-vertex graph has mixing time that is at most $n^3$ (or so).

So it would be great if we could directly prove that the cover time shrinks by a constant factor in each iteration of the foregoing procedure. The mixing time is closely related to the "spectral gap" (or "gap"), which is the gap between the 1st eigenvalue (i.e. 1) and the 2nd eigenvalue (which is "bounded away" from 1). Roughly speaking, the 2nd eigenvalue (i.e., 1 minus the gap) equals the rate of convergence of a random walk (to the stationary distribution), and the mixing time is inversely proportional to the gap, where the factor of proportion is logarithmic (i.e., the mixing time is $O(log n)/gap$). Hence, by showing that the spectral gap increases by a factor of two in each iteration, we would be showing that mixing time shrinks in that manner.

I will try to provide some intuition regarding expander graphs, and in particular their algebraic definition. The key point is to note the following:

Thus, if you start from any distribution over $V(G)$ and take a random step, then you end up in a distribution closer to uniform over $V(G)$. In particular, if you start from a uniform distribution over a set $A$ (of less than half $V(G)$), then you get to a distribution that has a significantly larger support. This is the "expansion" property (*). Also, if you take $O(\log_{1/\lambda_G} n) = O(\log n)/(1-\lambda_G)$ random steps from any start vertex, then you reach almost uniform distribution (over $V(G)$). Hence, $lambda_G$ is the rate of convergence of a random walk (to the stationary distribution).

*) The fact that eigenvalue gap implies expansion is closely related to the Expander Mixing Lemma (i.e., Lemma E.8, page 558). Note that in the special case of $B=V-A$, we can use $\sqrt{|A|\cdot|B|} \leq N/2$, and so the number of edges going out of $A$ is at least $((1-\rho(A))\cdot d - \lambda/2)\cdot|A|$. It follows that for $|A| \leq N/2$, it holds that $|\Gamma(A)-A| \geq ((1/2)-(\lambda/2d))\cdot|A|$.

READING ASSIGNMENT:

  1. Sec 5.2.4.0 (overview of the UCONN algorithm).
  2. Apdx E.2.1.1 (two equivalent defs of expanders).
  3. Apdx E.2.2.2 (the ZigZag product).
  4. Sec 5.2.4.1 (the transformation to an expander)
  5. Sec 5.2.4.2 (a log-space implementation)
HOMEWORK ASSIGNMENT (to be submitted by DATE2): SUGGESTED *OPTIONAL* READING:
  1. Read the entire section on expander graphs: All of Apdx E.2.
  2. Think of Exer 5.17.
SUGGESTED QUIZ (for UCONN in L)
It seems quite hard to design a meaningful quiz for this meeting. So I'll present a pseudo-quiz, which is a kind of digest.

NOTES FOR 9TH MEETING

Topic: Space complexity - Part 3 (NL).
Estimated difficulty: 1.5 in the scale of 5.

The reading assignment has two parts: (1) a mainly conceptual part that discusses on-line vs off-line non-determinism, and (2) a technical part about NL and Directed Connectivity (st-CONN).

Re (1). As explained in Sec 5.3.1, these two non-deterministic models are significantly different in the context of space complexity, since (intuitively) an off-line non-deterministic device can be used as an unaccounted work space. For this reason, the on-line model is the model of choice (but results for the off-line model follow).

Re (2). In a sense, st-CONN "encodes" all of NL; it is definitely NL-complete under log-space reductions. It is easy to see that st-CONN can be solve in space log-squared (and in general $NSPACE(s)$ is contained in $DSPACE(s^2)$). Finally, there is the celebarated theorem NL=coNL (or, equivalently, directed st-non-connectivity is in NL), which is the most challenging part in the current reading assignment.

The key idea (in the proof that NL=coNL) is an "NL machine" for enumerating all vertices that are at a given distance from a given vertex in a given graph, where an non-deterministic machine is said to compute a function if (i) it always outputs either the correct value or an error message (*), and (ii) it sometimes outputs the correct value (rather than an error message). Now, let $R_G(v,k)$ denote the set of vertices that are at distance at most $k$ from $v$ in the graph $G$, then it holds that $R_G(v,k)$ equals the set of vertices that are either in $R_G(v,k-1)$ or are adjecent to a vertex in $R_G(v,k-1)$. Thus, if you can non-deterministically enumerate $R_G(v,k-1)$, then you can enumerate $R_G(v,k)$. This is done by going over all $V(G)$, and checking for each target vertice whether it is in $R_G(v,k)$ by (re-)enumerating $R_G(v,k-1)$ on-the-fly (for each target vertex), and testing whether the target vertex should be taken per its neighboring some vertex in $R_G(v,k-1)$.
*) When saying that the machine may output an error message, we do not insist on a single error sybmol but rather allow it to output any message that ends with a special error symbol. This more liberal notion allows the machine to start producing bits of the output and declare the output as erronious 9and halt) at any point.

READING ASSIGNMENT: Basically read all of Sec 5.3.

  1. Sec 5.3.1: two model of non-determinstic space complexity.
  2. Sec 5.3.2: NL and Directed Connectivity (denoted st-CONN), including the completeness of st-CONN, NSPACE vs DSPACE, and NL=coNL (or solving st-non-connectivity in NL).
  3. Sec 5.3.3: a "philosophical" discussion.
SUGGESTED *OPTIONAL* READING AND THINKING: Read and think of Exer 5.18 relating the on-line and off-line models.

SUGGESTED *OPTIONAL* EXERCISES (do not submit)

SUGGESTED QUIZ (which is actually a digest for NL=coNL) Hint for item 2 in the 2nd bullet: We proceed in iterations so that in the $i$-th iteration we produce and record some function $F$ of $x$ and $i$. We can store both $i$ and $F(x,i)$ on our work space, provided that both have length logarithmic in $|x|$, and we should be able to compute $F(x,i+1)$ from $x,i$ and $F(x,i)$.
Hint for the 3rd bullet: Let $x=(G,s,i)$, where $G$ is a directed graph, $s$ is a vertex in $G$, and $i$ is an integer. Consider the problem of finding the set of vertices that are reachable from $s$ within $i$ steps.

NOTES FOR 10TH MEETING

Topic: Space complexity (last part) and randomized complexity classes (introduction).
Estimated difficulty: 1 in the scale of 5.

The next reading assignment consists of two unrelated topics. The 1st topic is the last topic we shall learn regarding space complexity, and the 2nd topic is actually a set of basic issues regarding randomized complexity classes.

The 1st topic is showing that QBF is complete for PSPACE under Karp reductions. We shall show how the acceptance condition of any polynomial-space computation can be encoded by a Quantified Boolean Formula of polynomial length. The underlying idea resembles/mimics the proof that NSPACE(s) is contained in DSPACE(s^2); essentially, we shall "re-use" formulas in a way analogous to the re-usage of space.

The 2nd topic enters the study of the complexity of randomized algorithms. We start with introducing the notion of randomized algorithms and various issues and conventions related to them. We will discuss the equivalence on-line and off-line formulations (which are useful for thinking about randomized algorithms) as well as the type and magnitude of the failure probability in such algorithms. We then move to discuss the class BPP capturing two-sided error PPT (probabilistic polynomial time) decision procedures. We shall prove that BPP is (strictly) contained in P/poly, and postpone to later showing that BPP is in PH (see Sec 6.1.3).

In addition, please read Appendix D.1, which presents probabilistic preliminaries that we need for this chapter (on randomized algorithms). Sec D.1.2.4 is not important at this point, but it is very important in many other settings, and so I strongly recommend reading it too.

READING ASSIGNMENT

  1. Sec 5.4 (on PSPACE).
  2. Sec 6.1.0-6.1.2 ("Introduction to PPT" and BPP). Sec 6.1.2.2 is an illustration -- please don't get entangled in it, and do take the two stated facts as given (i.e., don't worry about proving them, although this is not a "big deal").
  3. Apdx D.1 (probabilistic preliminaries).
SUGGESTED EXERCISES (not to be submitted): SUGGESTED QUIZ FOR THE BASICS OF PROBABILISTIC POLYNOMIAL TIME

NOTES FOR 11TH MEETING

Topic: randomized complexity classes.
Estimated difficulty: 1.5 in the scale of 5.

The next reading assignment consists of several issues relating to PPT. The highlights include a proof that BPP is reducible via a one-sided error randomized Karp reduction to coRP and a discussion of RL (randomized log-space).

The aforementioned randomized reduction is typically use to establish a weaker result, stating that BPP is in PH (or, more specifically, that BPP is in Sigma2). In our meeting, I may present the ideas in these weaker terms. Actaully, I currently tend to present them in terms of MA2 vs MA1, where MA denotes a generic randomized versuion of NP, and MA2 (resp., MA1) are two-sided error (resp., one sided-error) version of it.

Specifically, $S\in MA2$ (resp., $S\in MA1$) if there exists a probabilistic polynomial-time machine $V$ such that

  1. If $x\in S$, then there exists $y$ of $\poly(|x|)$ length such that $\Prob[V(x,y)=1] \geq 2/3$ (resp., equals 1);
  2. If $x\not\in S$, then for every $y$ it holds that $\Prob[V(x,y)=1] \leq 1/3$ (resp., $\leq 1/2$).
(Note that, like for BPP and RP, error-reduction applies here too.)
Obviously, both BPP and MA1 are contained in MA2, and NP is contained in MA1; but recall that it is not know whether BPP is in NP. The proof to be presented shows that MA2 is contained in MA1; that is, we can eliminate the error in the completeness condition. The proof, due to Lautemann, is based on providing some freedom to the verification process; specifically, its randomness may be shifted in one of polynomially many options provided as part of the proof. A sketch of this proof follow. 
 
Let $V$ be as in the definition of MA2.
Applying error-reduction, we may assume that
for every $x\not\in S$ and $y$ 
it holds that $Prob_{r\in\{0,1\}^m}[V_r(x,y)=1] \leq 1/3m$,
where $r$ denotes the randomness of $V$.
Now, the new prover will augment $y$ with a sequence $s_1,...,s_m$
and the new verifier $V'$ will accept when tossing coins $r$
if and only if for some $i\in[m]$ it holds that $V_{r\xor s_i}(x,y)=1$. 
The point is that for every $x\in S$ and $y$
such that $\Prob[V(x,y)=1] \geq 2/3$,
there exists $s=(s_1,...,s_m)$ such that $Prob[V'_r(x,(y,s))=1] = 1$.  
On the other hand, for every $x\not\in S$ and every $y,s$ 
it holds that $Prob[V'_r(x,(y,s))=1] \leq m/3m$
(since for every $i\in[m]$ and every $s_i$ 
it holds that $Prob_r[V_{r\xor s_i}(x,y)=1]\leq1/3m$).
When discussing RL, I will stress the importance of restricting computation to polynomial-time (which was the case "automatically" in the cases of L and NL). Without these restriction, the "bad RL" contains all of NL (and the proof of this fact contains an interesting idea: an "approximate randomized step-counter" (see Exer 6.18), which allows counting $Omega(T)$ steps at the cost of $\log\log T$ space).

READING ASSIGNMENT: The rest of Section 6.1. Specifically:

  1. Sec 6.1.3: One-Sided Error and the proof that BPP is reducible with a one-sided error Karp reduction to coRP.
  2. Sec 6.1.4: Zero-error PPT (ZPP) and "ZPP = RP intersection coRP".
  3. Sec 6.1.5: RL, issues in its definition, and UCONN in RL.
SUGGESTED EXERCISES (not to be submitted):
  1. Exer 6.4-6.6: about error reduction, easy but very important. (The point is merely defining the random variables on which the probabilistic inequalities are to be applied. You should be in a state in which you consider such an exercises trivial.)
  2. Exer 6.7: about an alternative definition of ZPP, very important!
  3. Exercises 6.10 and 6.11: Add'l details for the illustrative paragraph in the proof of Thm 6.9. Exec 6.10 is good to know in general!
  4. Exer 6.14-6.15: Exer 6.14 is easy, but Exer 6.15 is tedious. They show completeness and hierarchies for promise problem version of BPP.
SUGGESTED QUIZ (Hint: For $m=|r|$, suppose that $g_1(r),...,g_{m}(r)$ are each computable in log-space when given on-line access to $r$, is $\vee_{i\in[m]}g_i(r)$ computable in log-space given on-line access to $r$?)

NOTES FOR 12TH MEETING

Topic: Counting classes - Part 1 (exact and approximate).
Estimated difficulty: 1 in the scale of 5.

The issues that I'd like to highlight include

READING ASSIGNMENT
  1. Pages 202-205: Exact Counting (not including the proofs of Props 6.21 and 6.22 (in pages 206-211)).
  2. Sec 6.2.2.0: The notion of Approximate counting.
  3. Sec 6.2.2.1: Approximate counting for DNF.
PREPARING FOR THE NEXT READING ASSIGNMENT
(You do not need this now, but you'll need it for next time; so if you have time, then you may start looking at the following): Read Appendix D.2 on Hashing Functions. ADD'L READING (NOT MANDATORY): I do recommend reading the proofs of Props 6.21 and 6.22 (pages 206-211), see more details below. These proofs are independent of one another, and so you may read one but not the other. I'd give priority to the proof of Prop 6.22.
  1. The proof of Prop 6.21 (which spans 4 pages and 3 exercises) is via an ingenious gadget reduction; the main lesson from it is that sometimes one just needs ingenuity. Actually, this refers to the original ("structured") proof; the alternative proof (via Fig 6.3) was found retrospectively by using an automatic search for a solution.
  2. The (1 page) proof of Prop 6.22 is via a couple of reductions, which offer some concrete technical lessons.
SUGGESTED QUIZ (for Sec 6.2.1-6.2.2.1)

NOTES FOR 13TH MEETING

Topic: Counting classes - Part 2 (approximation reduces to NP).
Estimated difficulty: 4 in the scale of 5. Recommended to ask me to attend the meeting.

[Class of 2018/19 recommendation: It seems that the difficulty is over estimated, and should be reduced to 3, which means that it is possible but not really needed to ask me to attend. (Oded: Actually, I had the same feeling when going over the material for this meeting.)]

The issues that I'd like to highlight include

READING ASSIGNMENT
  1. Appendix D.2 on Hashing Functions.
  2. Sec 6.2.2.2: Approximating #P via a PPT reduction to NP.
  3. Sec 6.2.3: Unique solution problems.
ADD'L READING (NOT MANDATORY):

NOTES FOR 14TH MEETING

Topic: Counting classes - Part 3 (uniform generation).
Estimated difficulty: 3 in the scale of 5. You may want to ask me to attend the meeting.

This is the last meeting of the current semester. However, if you wish to set up another meeting to discuss the current reading assignment or anything else, just let me know.

The issues that I'd like to highlight this time include

READING ASSIGNMENT: Section 6.2.4 (uniform generation). Note that you'll need Lemma D.6 (at the end of Apdx D.2).

HOMEWORK ASSIGNMENT:

Try to do all without looking at the guidelines.

NOTES FOR the 15TH MEETING

Topic: Hardness amplification - part 1 (One-Way Function)
Estimated difficulty: 1 in the scale of 5.

The material we'll cover in this semester has a significant overlap with the material taught in a course on the "Foundations of Cryptography" (especially, when using my own book). Specifically, one-way functions (see current Section 7.1) general-purpose pseudorandom generators (Sec 8.2), and zero-knowledge interactive proof systems (Sec 9.1-9.2) are covered in both cources; however, the perspective is different.

We start with Chapter 7, titled "the bright side of hardness". Although this hints to the applications of computational hardness, the actual focus would be on "hardness amplification"; that is, turning moderate levels of hardness into stronger levels, which, in turn, are the ones useful (e.g., for pseudorandomness and Cryptography).

Regarding the current reading assignment (sec 7.1.0-7.1.2), I will discuss three topics.

  1. Moving from P-vs-NP (and NP-vs-BPP), which are worst-case assumptions, to "instances that we can put our hands on" (i.e., average-case), and to "instances generated with solutions" (which "we can use"), and how the latter lead to the definition of OWF (= One-Way Function).
  2. The actual definition of OWF. Issues include probability of inverting, the need to provide the preimage-length in unary, etc.
  3. Hardness amplification from "weak OWF" to (strong/normal) OWF. We cannot assume a "direct product" attacker/inverter, and so the proof is more complex than the Information Theoretic analogue. We use a "reducibility argument" (reduction w. an average-case analysis), and (unlike the IT analogue) it has a cost (see the running-time analysis)!
READING ASSIGNMENT: Section 7.1.0--7.1.2. I am/was tempted to suggest all of Sec 7.1 for this reading, which is not too much in terms of pages (i.e., about a dozen pages). But, in 2nd thought, I feel that Sec 7.1.2 and 7.1.3 may contain too much of a "new mindset" that is good to digest slowly and discuss. Anyhow, those who are bored can try reading Sec 7.1.3 too.

SUGGESTED EXERCISES (not to be submitted):

All these are good both for geting into the mindset (i.e., "practice") and for the facts they communicated.

NOTES FOR the 16TH MEETING

Topic: Hardness amplification - part 2 (Hard-core predicates)
Estimated difficulty: 3 in the scale of 5. You may want to ask me to attend the meeting.

The current assignment consists of two parts:

  1. Hard-core predicates (Sec 7.1.3),
  2. Starting to discuss hardness in E (Sec 7.2.0-7.2.1.1).
[NOTE: It may be better to split this material and do each part in a separate meeting. I suggest to decide which way to go after trying to read all, possiblly stopping at a point in which it feels too much.]

Regarding the 1st part (hard-core predicates), I plan to

The proof starts with the case that the predicate can be approximated with success probability 0.76 (i.e., noticeablly above 3/4), distills the problem of "error doubling", presents a "dream" in which this problem can be solved, and "materialize the dream". I will probably be "pulled" to showing the entire proof sketch. But it will be good if time is left also for the next topic... 
One may present the dream as a model in which
we obtain a random sample of labelled examples. 
Recall that the problem can be cast as computing $b_x:\{0,1\}^n\to\{0,1\}$,
where $b_x(r)=b(x,r)=\sum_ix_ir_i$, 
when giving an oracle access to $B_x$ that agrees with $b_x$ 
on a $0.5+\epsilon$ fraction of the possible instances. 
The dream refers to a model in which we are given a sample $R$ 
of random points $r$'s along with the correct values of the $b_x(r)$'s. 
Furthermore, when solving the problem in this dream-model, 
we note that our solution holds also when the sample $R$ consists of 
pairwise independent points that are uniformly distributed in $\{0,1\}^n$. 
This observation will allow to implement the dream-model in the standard model.
(On the other hand, a dream that asserts totally independent $r$'s
is too good to be implementable -- since it allows to find $x$
without querying $B_x$ at all.)
Regarding the 2nd part (hardness amplification in E), I will focus on the amazing result that asserts that worst-case hardness implies mild average-case hardness. The key steps are (i) considering a low-degree extension $f'$ of the original "worst-case hard" function $f\in E$, and (ii) using "self correction" (a randomized reduction of $f'$ to itself) to show that if $f'$ is easy on "much" of its domain then it is easy on each point in its domain.

QnA (by Ori Sberlo): Can one not establish average-case hardness unconditionally, by diagonalization? In fact, one can (see Goldmann, Grape, and Hastad, IPL 1994), but this will hold only with respect to uniform classes, whereas here we seek hardness wrt non-uniform circuits.

READING ASSIGNMENT: Read the following, including the specified exercises.

  1. Hard-core predicates (Sec 7.1.3). See Exer 7.5 regarding the underlying pairwise independent construction.
  2. Preliminaries re hard functions in E (Sec 7.2.0).
  3. Hardness Amplification from Worst-case to mild average-case (Sec 7.2.1.1). See Exer 7.11 ("self correction" of low degree polynomials) and Exer 7.12 ("low degree extension"). These are basic tools, often used in very different contexts of theory of computation, so I strongly recommend getting familiar with them.
If you feel this was too much and/or that you want to discuss some issue(s) in our next meeting, do let me know before next time!

SUGGESTED EXERCISES (not to be submitted):

NOTES FOR the 17TH MEETING

Topic: Hardness amplification - part 3 (the XOR lemma)
Estimated difficulty: 5 in the scale of 5. Highly recommended to ask me to attend the meeting.

[WARNING: This reading may be the most difficult in the course]

[Class of 2018/19 recommendation: Remind the students that the point in this chapter is starting from an assumption that is as weak as possible and deriving useful tools, which do seem stronger from the starting assumption (although their derivation proves that they are not). The usefulness of these tools will be demonstrated in Chapter 8, and is further demonstrated in Apdx C.]

The current reading assignment refers to hardness amplification (in E); specifically, the amplification is from mild average-case hardness to very strong level of average-case hardness. In addition, there is a homework assignment and optional reading.

My plan for the meeting would include:

  1. Discussing the XOR Lemma and the Direct Product Lemma (DPL).
  2. Reducing the XOR Lemma to the DPL. This includes
  3. Proving the DPL by induction on the number of inputs, while relying on a quantitative two-input version. Warn against "unquantitative induction" (for a non-constant number of iterations).
Add'l ideas to highlight include the observation that any distribution (on strings of feasible length) can be "generated" by small (non-uniform) circuits.

READING ASSIGNMENT: Read Section 7.2.1.2 ("Yao's XOR Lemma").

SUGGESTED ADDITIONAL READING (not mandatory):

  1. Hardness amplification via "list decoding" (Sec 7.2.1.3); this goes directly from worst-case to strong average-case (rather than going via the mild level as we've done). The 1st priority is the more concrete treatment on pages 266-7 (the abstraction on pages 268-9 is less important and hard to follow).
  2. Tighter amplification (wrt exponential size circuits): Sec 7.2.2. The amplification in prior sections moved from input-length $n$ to input-length $m=\poly(n)$, while the circuit sizes only decreased (and so hardness for circuit size $s(n)$ yields hardness for sircuit size $s'(m)=s(m^{1/O(1)})$. The 1st priority is the notion of "hard region" (Sec 7.2.2.1). The 2nd priority is its use for amplification (Sec 7.2.2.2). Note that Sec 7.2.2.2 is intentionally sketchy (especially Lem 7.23).
I think it is good to have a vague idea of what is going on here, even if one does not follow all details (which would indeed require reading beyond this text).

HOMEWORK ASSIGNMENT:

SUGGESTED EXERCISES (not to be submitted):

NOTES FOR the 18TH MEETING

Topic: Pseudorandom generator - part 1 (the general paradigm and more)
Estimated difficulty: 1 in the scale of 5.

Your last reading assignment was by far the most difficulty and technical one for this course. So no need to fear anything that may be coming in the next months.

The current reading assignment starts a series on pseudorandom generartors. I suggest to view "pseudorandom generators" (PRGs) as a general paradigm with many incarnations (or as a family name with many members).

I am a bit unsure about the organization and partition of the material for the next two meeting. So I'll provide what is planned for both as well as my recommendation and hesitations.

In the (current/1st) meeting, I will focus on three issues.

READING ASSIGNMENT (for the next two meeting):
[the default suggestion is to read the following five items for the 1st/current meeting] [and read the rest for the second/next meeting] [NOTE: Indeed, my suggestion is to read Sec 8.0-8.2.3 for the 1st meeting, and the rest for the next (i.e., 2nd) meeting; that is, proceed by the actual order of the sections, and break after Sec 8.2.3. Yet, a good alternative is to take Secs 8.2.2 and 8.2.6 out of the order and use the following order instead: (i) Read Sec 8.0-8.2.1 and 8.2.3 first, (ii) Read Sec 8.2.4, 8.2.5, and 8.2.7.2 next, and only then (iii) read Sec 8.2.6, Sec 8.2.2, and 8.3.1. The justification for this alternative is that Sec 8.2.6 demonstrates the point of Sec 8.2.2 in a non-uniform context, while using a much simpler proof.]

In any case, pay close attention to Sec 8.2.3.3 (see the "hybrid method") and to Sec 8.2.5.2 (see "the next bit test" -- Exer 8.12).

SUGGESTED EXERCISES (not to be submitted):

NOTES FOR the 19TH MEETING

Topic: Pseudorandom generator - part 2 (general-purpose PRGs)
Estimated difficulty: 1 in the scale of 5.

The current reading assignment is the 2nd part of the double assigment that I gave last time -- see below. We shall finish dealing with general purpose PRGs and turn to "canonical derandomizers".

In the meeting, I will focus on four issues.

READING ASSIGNMENT
The second half of whatever you did not read so far in the following. [the following repeats the text of last time]

[the default suggestion is to read the following five items for the 1st/previous meeting]

[and the rest for 2nd/current meeting] [NOTE: The justification for the suggested order and the alternative were presented in the note for the previous meeting.]

Recall: In any case, pay close attention to Sec 8.2.3.3 (see the "hybrid method") and to Sec 8.2.5.2 (see "the next bit test" -- Exer 8.12).

SUGGESTED EXERCISES (reapted from previous meeting, not to be submitted):

NOTES FOR the 20TH MEETING

Topic: Pseudorandom generator - part 3 (canonical derandomizers)
Estimated difficulty: 4 in the scale of 5. Recommended to ask me to attend the meeting.

The current reading assignment has two parts, the main one being the construction of canonical derandomizers, and the other is background material for the next meeting (i.e., Meeting 21).

In the meeting, I will focus on the first part. I will describe the construction (known as the Nisan-Wigderson construction), its analysis, and maybe (i.e., if time and energy suffices) also how these ideas extend to other settings.

The construction consists of applying a hard to approximate function, which is computable in E but hard to approximate by smaller-han-exponential circuits, to many different projections of the seed. We cannot afford pairwise disjoint projections (since this violates the stretching requirement), whereas identical projections are obviously bad. So we need a family of projections (or sets) with small pairwise intersections, and we need to construct this family in time exponential in the seed. The analysis shows that this yields a PRG, provided that the pairwise intersections are smaller than the logarithm of the size bound that we allow in the inapproximability hypothesis.

READING ASSIGNMENT -- these are three unrelated items:

  1. The construction of canonical derandomizers: Sec 8.3.2. This is the main part of the current reading assignment.

    [The next two items are technical background that you'll need for the next reading assignment (i.e., Meeting 21).]

  2. Take another look at Apdx D.2.3, and focus on the generalization called mixing (see Item 1 in the homework assignment).
  3. Introduction to Randomness Extractors: Apdx D.4.0-D.4.1.1.
[We shall use (2) and (3) in our next reading assignment (of Lecture 21, on space bounded distinguishers), but it is good to read this material now since the next reading will be more "dense".]

HOMEWORK ASSIGNMENT (to be submitted):

  1. Prove the Mixing Lemma stated in the middle of page 530 (i.e., the paragraph "A generalization (called mixing)" that follows the proof of Lemma D.4).
  2. Exer 8.24 (canonical derandomizers imply hardness). Try to do it without looking at the guidelines.
SUGGESTED ADDITIONAL READING (not mandatory):
[The following four items will not be used in this course, but they are very useful to know! The first two items are an offspring of the NW-construction, but the other two items are unrelated to it.]
  1. Sec 8.3.3.1 (the NW-construction as a general paradigm).
    This will lead into the following item (2)
  2. Using the NW-construction paradigm for randomness extractors: Apdx D.4.2.

    Having been introduced to Randomness Extractors (in Apdx D.4.0-D.4.1.1) and having seen a way of constructing them (in Apdx D.4.2), you may as well see two of their (non-direct) applications (to randomness-efficient error-reduction and to sampling).

  3. Randomness extraction and randomness-efficient error-reduction: Apdx D.4.1.3
  4. Randomness extraction and Sampling: Start with Apdx D.3 and then read D.4.1.2
SUGGESTED EXERCISES (not to be submitted):
[The first two items are most useful.]

NOTES FOR the 21ST MEETING

Topic: Pseudorandom generator - part 4 (the space-bounded case)
Estimated difficulty: 4 in the scale of 5. Recommended to ask me to attend the meeting.

The current reading assignment is PRGs fooling space-bounded distinguishers. The topics include:

READING ASSIGNMENT -- basically, entire Section 8.4. The following description of the first construction is inspired by a recent work and differs from the presentation in the book. Specifically, the construction is the same (and one may start by describing it using Fig 8.3), but rather than being analyzed by looking at contracted versions of the distinguisher (see page 321), we consider a sequence of distributions that this distinguisher may examine. 
The first sequence we consider is the uniform sequence
$U_{\ell'n} \equiv U_n^{(1)}U_n^{(2)} \cdots U_n^{(\ell'-1)}U_n^{(\ell')}$
and the second sequence is 
$U_n^{(1)} h(U_n^{(1)}) \cdots U_n^{(\ell'/2)} h(U_n^{(\ell'/2)})$,
where $h$ is a random hash function. 
We show that these two sequences are indistinguishable
by a $s(k)$-space bounded automaton exactly as done on page 320.
The point is that the same argument applies to the sequences
$G_i(U_n^{(1)}) G_i(U_n^{(2)}) 
  \cdots G_i(U_n^{({\ell'/2^i}-1)}) G_i(U_n^{(\ell'/2^i)})$
and 
$G_i(U_n^{(1)}) G_i(h(U_n^{(1)})) 
  \cdots G_i(U_n^{(\ell'/2^{i+1})}) G_i(h(U_n^{(\ell'/2^{i+1})}))$,
where $G_i$ is an arbitrary mapping of $n$-bit strings 
to $2^{i}\cdot n$-bit strings. 
(Note that each of these sequences has length 
$(\ell'/2^i) \cdot 2^{i}\cdot n = \ell$.) 
To see that these sequences are indistinguishable by the said automaton, 
consider sets of the form $L_{u,v}^{(j)} \subseteq \{0,1\}^n$
such that $s \in L_{u,v}^{(j)}$
if the automaton moves from vertex $u$ in layer $j\cdot 2^i$
to vertex $v$ in layer $(j+1)\cdot 2^i$ upon reading the sequence $G_i(s)$. 
Now, note that for almost all $h$'s it holds that
$\Prob[U_n \in L_{u,v}^{j)} \wedge h(U_n) \in L_{v,w}^{j+1)}]
 \approx \Prob[U_n \in L_{u,v}^{j)}] \cdot \Prob[U_n \in L_{v,w}^{j+1)}]$
and continue as in the text.
Note that the initial transformation of $D_k$ to $D'_k$ (presented in top of page 320) can be avoided; that is, one can argue directly about the original distinguisher $D_k$. (See more detailed description, which is meant to replace pages 320-321.) Also, given this analysis, it may be good to start by describing the construction (using Fig 8.3), and identify it with the last hybrid of the analysis.

SUGGESTED ADDITIONAL READING (not mandatory):
[Very recommended. All these notions and constructions are extremely useful to know!]

They are used a lot, and you already encountered the 1st (i.e., limited independence PRG) and maybe also the 3rd (i.e., expander walks).

SUGGESTED EXERCISES (not to be submitted):

Both are intended to promote understanding of the model; the second may be better for that.

NOTES FOR the 22nd MEETING

Topic: Probabilistic proof systems - part 1 (interactive proofs)
Estimated difficulty: 1 in the scale of 5.

We step into a new chapter, one on probabilistic proof systems. The common theme is introducing randomization and even (bounded) error probability into the verification process, with the aim of achieving some features that are impossible (or very unlikely) to achieve by deterministic systems. Hence, randomness does help wrt proof verification!

A common convention: all complexity measures are stated in terms of the length of the main input (i.e., the "assertion being verified").

We start with interactive proof systems (ips, and the class IP). The definition highlights verification (personalized by a verifier), and views proofs as a dynamic process (rather than a static object). Hence, the prover becomes explicit. Soundness (and sometimes completeness) is given a probabilistic interpretation. Still, verification remains efficient; that is, performed in (probabilistic) polynomial-time.

IP extends NP by both randomization and interaction, but interaction is "useless" without randomness. Actually, the soundness error is essential. 

Prop: If $S$ has an ips with zero error, then $S\in\NP$.

Pf: (1) zero-error --> deterministic verification (and prover), 
(2) deterministic interaction --> fixed transcript (which can be sent).
The power of IP is demonstrated in three steps: Shoing interactive proof systems for GNI, coNP, and PSPACE. READING ASSIGNMENT SUGGESTED ADDITIONAL READING (not mandatory):

SUGGESTED EXERCISES (not to be submitted):

NOTES FOR the 23RD MEETING

Topic: Probabilistic proof systems - part 2 (zero-knowledge proofs)
Estimated difficulty: 1 in the scale of 5.

The material from this point on (if not for a couple of weeks now) is presented in the form of high-level overviews. You may view them as introductions to some research directions/sub-areas. The presentation clarifies the definitions and issues, but typically only sketches the constructions and/or proofs.

The meeting will be devoted to zero-knowledge proofs. I will discuss the definition and present some simple constructions.

READING ASSIGNMENT:
On zero-knowledge (ZK) proofs (Sec 9.2.0--9.2.2, pages 368-377).

SUGGESTED ADDITIONAL READING (not mandatory):
Sec 9.2.3 (p. 378-9): Introduction to "proofs of knowledge". This is really unrelated to the rest of the course; read it only if you are truly interested in this puzzling notion.

SUGGESTED EXERCISES (not to be submitted):

NOTES FOR The 24TH MEETING

Topic: Probabilistic proof systems - part 3 (PCP)
Estimated difficulty: 2 in the scale of 5. This pressumes that this meeting only covers (0)+(1). For (2)+(3) the estimate is 4 in the sacle of 5, and it is recommended to invite me.

[NOTE: It may be much better to split this material into two meetings. Do (0)+(1) in one meeting and (2)+(3) in another. Indeed, this is what was done in the last incarnations of this group (see also notes for the 25th meeting).]

I will present (0) the definition of PCP and the PCP Theorem, and then try to give a taste of the proof. At best I will do two of the following three things

  1. Show that NP is in PCP[poly,O(1)], which is already amazing.
  2. Describe the "proof/PCP composition" paradigm.
  3. Outline Irit's gap amplification approach.
[NOTE: Actually, only (1) was done.]

I think I will present (1) slightly differently from in the book. After reducing NP to QE (satisfiability of Quadratic Equations over GF(2)), I will suggest to use as a proof-oracle the sequence of the evaluations of all ($2^{n^2}$) quadratic expressions on some satisfying assignment $x$ to the $n$ variables. The verification will be performed as follows. First, rather than checking $m$ equations, we shall check a random linear combination of these equations. Second, we shall not just fetch the corresponding value from the adequate point in the proof, but rather use self-correction, and this will be done in addition to testing that the proof-oracle is (close to) a valid encoding (which is a Hadamard encoding of the outer-product of $x$ with itself). Hence, testing and self-correcting the Hadamard code will be our first task, and from there we shall proceed to testing and self-correcting the sub-code corresponding of a Hadamard code of an $n^2$-bit long string obtained by an outer-product of an $n$-bit message with itself.

READING ASSIGNMENT:

On the other hand, reading Sec 9.3.3 before Sec 9.3.2.3 may be a good idea, mainly for sake of wider perspective on "gaps". If you don't read Sec 9.3.3 (re "PCP, gaps, and approximation") now, then you'll read it in next assignment. It is a relatively easy reading anyhow (and only 2 pages).

SUGGESTED ADDITIONAL READING (not mandatory):
Sec 9.3.4 ("more on PCP itself").

HOMEWORK ASSIGNMENT (to be submitted):

  1. Exer 9.17 (e.g., PCP[log,poly] is contained in NP).
  2. Exer 9.24 (note a correction on the book's webpage) and 9.26; they deal with the two directions of PCP vs gapCSP.
SUGGESTED EXERCISES (not to be submitted):

NOTES FOR the 25TH MEETING

Topic: Probabilistic proof systems - part 4 (PCP, cont)
Estimated difficulty: 4 in the scale of 5. Recommended to ask me to attend the meeting.

Indeed, the previous reading assignment was "cut shorter" to include only (i) the PCP model and the PCP theorem (statement only) and (ii) the proof that NP is contained in PCP[poly,O(1)]; that is, Sec 9.3.0-9.3.2.1.

The current reading assignment will consist of the overviews of the two different proofs of the PCP Theorem (i.e., NP in PCP[log,O(1)]), which are briefly reviewed next. (Recall that PCP[log,poly] is in NP.)

Recall that we have seen (in Sec 9.3.2.1) that NP is in PCP[poly,O(1)], which is already amazing. This result will be an ingredient in both alternative proofs of the PCP Theorem.

The 1st proof of the PCP Theorem is based on two additional ingredients.

  1. The proof composition paradigm, which composes an outer PCP[r',q'] system with an inner PCP[r'',q''] system to obtain a PCP[r,q] system such that $r(n) = r'(n) + r''(q(n))$ and $q(n) = q''(q'(n))$. The composition relies on additional features of the PCPs such as (i) non-adaptiveness of the outer, (ii) small decision circuits of the outer, (iii) the inner being a "proof of proximity", and (iv) "robustness" of the outer. [Of course, each of these notions needs to be defined and obtained...]
    We stress that composition is non-trivial since the query complexity of the resulting scheme is lower than that of the 1st one, and indeed this is the aim of the proof composition paradigm. So we wish to verify a claim about a (residual) input that we cannot even read in full. So we need the inner PCP to be a proof of proximity (which guarantees that this partially read input is close to a valid one) and the outer PCP should be robust (in the sense that typicaly when it rejects it is the case that the sequence of answers is far from satisfying its residual decision predicate).
  2. Showing that NP is in PCP[log,polylog].
Now, composing (2) with itself you get NP in PCP[r,q]. where $r(n) = O(\log n) + O(\log \polylog n) = O(\log n)$ and $q(n) = \polylog(\polylog n) = \poly(\log\log n)$. Next, we compose this system with the PCP[poly,O(1)] system and conclude that NP is in PCP[log,O(1)], since we obtain randomness $O(\log n) + \poly(\polyloglog n) = O(\log n)$ and query complexity $O(1)$.

Note that the above proof is obtained by composing two highly non-trivial PCP systems (i.e., PCP[poly,O(1)] and PCP[log,polylo]) using a sophisticated composition theorem (see the add'l features...). In contrast, the 2nd proof of the PCP Theorem evolves via (logarithmically many) repeated applications of an intuitive "gap amplification" step, which is sketched next. 

Let $\PCP_{1,s}[r,q]$ denote a PCP system with perfect completeness
and soundness error $s(n)$, where so far we focused on $s(n)=1/2$.
Clearly, NP is in $\PCP_{1,1-(1/n)}[log,3]$ (a trivial PCP) 
and the basic (gap) amplification step (which amplifies $1-s$) 
is captured by $\PCP_{1,1-\e(n)}[r,q]$ in $\PCP_{1,1-2\e(n)}[r+O(1),q]$,
provided that $\e(n)$ is smaller than some (small) positive constant $c$.
(N.B.: The query complexity $q=O(1)$ is preserved,
whereas the randomness complexity only increased by an additive constant.)
Hence, starting from the trivial PCP and applying logarithmically many steps, 
we obtain NP in $\PCP_{1,1-c}[log,O(1)]$ (which yields the PCP Theorem). 
The point, of course, is proving the amplification step.
Here, for clarity, we move to a gapCSP (for two variables over $[O(1)]$),
and will also use "NP in PCP[poly,O(1)]".

READING ASSIGNMENT:

Actually, reading Sec 9.3.3 before Sec 9.3.2.3 may be a good idea, mainly for sake of wider perspective on "gaps".

SUGGESTED ADDITIONAL READING (not mandatory):
Sec 9.3.4 ("more on PCP itself").

HOMEWORK ASSIGNMENT (to be submitted, repeated/reminder):

  1. Exer 9.17 (e.g., PCP[log,poly] is contained in NP).
  2. Exer 9.24 and 9.26 (PCP vs gapCSP, two directions)

NOTES FOR the 26TH MEETING

Topic: Notions of approximation
Estimated difficulty: 1 in the scale of 5.

If you did not cover Sec 9.3.3 (PCP and gap provblems) yet, please do it now. Note that the terminology og gap problems was used in Irit's proof of the PCP Thm (i.e., Sec 9.3.2.3). Here we use it to capure the notion of hardness of approximation; that is, saying that a gap problem is NP-Hard means that approximating the corresponding parameter up-to the the corresponding factor is NP-Hard.

READING ASSIGNMENT (for July 1st):

  1. Sec 9.3.3 -- PCP, gap problems, and Inapproximability
  2. Sec 10.1.1 -- Approximate Search (aka approximate optimization)
  3. Sec 10.1.2 -- Approximate Decision (aka Property Testing)
Section 10.1 as a whole is technically light, since most results are only stated but not proved. I suggest to compensate for this by doing the suggested exercises.

SUGGESTED ADDITIONAL READING (not mandatory):
Sec 9.3.4 ("more on PCP itself"). If you did not read it already.

SUGGESTED EXERCISES (not to be submitted):

NOTES FOR the 27TH MEETING

Topic: Average-case complexity
Estimated difficulty: 1 in the scale of 5.

Various notions of approximation constitute one type of relaxation (intended to reduce the complexity of computational tasks). Another is average-case analysis of algorithms (indeed: the relaxation is in the analysis not in the problem). As with approximation, the issue of meaningfulness arises, and here it is more acute (see definitional issues below).

I will discuss several definitional issues:

  1. Why "average-case" (as naively understood) is inadequate (from a conceptual perspective), and what "typical case" means.
  2. What are natural problems (i.e., distributional version of NP)?
    Avoiding the extremes (of all distrubutions or a single distribution). Simple (P-computable) distributions vs P-sampleable ones.
  3. A notion of reduction that preserves typical ease; the role of domination (a notion to be defined).
If we want to see "reduction that preserves typical ease", then we better look for new ones...
Indeed, we shall present such reductions when proving the following results:

THM 1 (easy): completeness for (NP,P-sampleable).
THM 2 (main material -- Sec 10.2.1.2): completeness for (NP,simple).
THM 3 (advanced material -- Sec 10.2.2.2): reducing (NP,P-sample) to (NP,simple).

Combining THM 2 and 3, we have a problem in a restricted class ("simple") that is complete for the larger class ("sampleable").

READING ASSIGNMENT (last one):

  1. Sec 10.2.0 -- motivation, please don't skip it!
  2. Sec 10.2.1 -- the basic theory. Pay attention to the first two paragraphs of Sec 10.2.1.2 (bot p. 435) and the two "Reflection" paragaphs on pages 439-440.
  3. Page 451 (reflections and relation to OWF).
SUGGESTED ADDITIONAL READING (not mandatory):
  1. Sec 10.2.2.1 -- search vs decision
  2. Sec 10.2.2.2 -- P-sampleable vs simple, skipping the proof of Thm 10.26.
  3. Advanced (be warned!): The proof of Thm 10.26 (pages 447-450).
SUGGESTED EXERCISES (not to be submitted):

Back to the Computation Complexity (book).