Mathematics of the impossible: Computational Complexity, Chapter 6, Alternation

We placed one quantifier “in front” of computation and got something interesting: NP. So let’s push the envelope.

Definition 6.1. Time is the set of functions for which there is a RAM such that on input stops within steps and

Time is defined similarly except that we start with a quantifier. We also define

We refer to such computation and the corresponding machines as alternating, since they involve alternation of quantifiers and we will soon see a connection with alternating circuits.

As for NP, Definition 5.1, note that the running time of is a function of only. Again, this difference is inconsequential for , since the composition of two powers is another power. But it is important for a more fine-grained analysis.

Exercise 6.1. Min-Ckt is the problem of deciding if an input circuit has an equivalent circuit which is smaller. It is not known to be in NP. In which of the above classes can you place it?

6.1 Does the PH collapse?

We refer to the event that as “the PH collapses.” It is unknown if the PH collapses. Most people appear to believe that it does not, and to consider statements of the type

as evidence that is false. Examples of such statements are discussed next.

Theorem 6.1. .

The idea in the proof is simply that if you can remove a quantifier then you can remove more.

Proof. We prove by induction on that .

The base case follows by assumption and the fact that P is closed under complement.

Next we do the induction step. We assume the conclusion is true for and prove it for . We will show . The result about P follows again by complementing.

Let , so and a power-time TM such that for any ,

(As discussed after Definition 6.1 we don’t need to distinguish between time as a function of or of when considering power times as we are doing now.)

Now the creative step of the proof is to consider

Note . By induction hypothesis . So let TM solve in power time. So . And so , again using the hypothesis. QED

Exercise 6.2. Prove the following strengthening of Theorem 6.1:

Exercise 6.3. Show that if for some then the PH collapses to , that is, .

Theorem 6.2. [21] .

Proof. We’ll show and then appeal to Exercise 6.3. Let and be a corresponding machine s.t. 

We claim the following equivalent expression for the right-hand side above:

where ranges over circuits of size for some . If the equivalence is established the result follows, since evaluating a circuit can be done in power time.

To prove the equivalence, first note that the the direction is obvious, by setting . The interesting direction is the . We claim that under the assumption, there is a circuit that given outputs a string that makes accept, if there is such a string.

To verify this, consider the problems CktSat and Search-CktSat which are analogous to the 3Sat and Search-3Sat problems but for general circuits rather than 3CNF. CktSat is in NP, and so by assumption has power-size circuits. By the reduction in Theorem 4.5, Search-CktSat has power-size circuits as well. Hence, the desired circuit may, on input and produce a new circuit mapping an input to , and run on . QED

Exercise 6.4. Prove that , for any . (Hint: Existentially guess the truth table of a hard function.)

Improve this to .

Exercise 6.5. Prove .

6.2 PH vs. alternating circuits

As suggested by the word alternation in Definition 6.1, the power hierarchy PH and its subclasses can be seen as alternating circuits. Before presenting this connection it is useful to write problems in PH in a specific format. The next lemma shows that we can restrict the machine in Definition 6.1 to read only one bit of the input . The price for this is that we are going to have to introduce an extra quantifier, however this new quantifier will only range over bits.

Lemma 6.1. Let . Then there exists a RAM s.t.:

and on input stops within steps and only reads one bit of .

Note the first quantifiers are over bits and unchanged from Definition 6.1, the next one is over bits, written as a pair , and the last is over . The idea is… you guessed it! We are going to guess the bits read from the input, and verify that each of them is correct.

Proof. Let be the machine corresponding to in Definition 6.1. We assume that , i.e., is odd. The case is left for exercise.

We enlarge to quantify over additional bits which correspond to the bits of read by . The desired machine simulates with the following change. At any time step , if reads bit of :

(1) If then does not read and instead uses bit ,

(2) If then reads the corresponding bit of , and it also checks that this bit equals . If it doesn’t rejects.

By inspection, reads at most one bit of .

Correctness is argued as follows. For any , if accepts then there are values for the bits read from the input that cause to accept. Conversely, if accepts for some then this matches the bits read from by , for else would reject in (2). Hence accepts as well. QED

We now show how to simulate computation in PH by small-depth circuits. The size of the circuit is exponential in the time; such a simulation would not be interesting if the circuit is not explicit and the time is more than the input length, since every function on bits has circuits of size (Theorem 2.3). By contrast, the simulation will give explicit circuits and also apply to running times less than the input length. The setting of running time less than the input length makes the simulation interesting even for non-explicit circuits, and is soon to play a critical role.

Lemma 6.2. Any function in has on inputs of length alternating circuits of depth and gates. The fan-in of each gate is and the fan-in of the gates closest to the input is . Moreover, the circuit is explicit in the following sense: Given an index to a gate of fan-in and a number we can compute the index of child of in .

In fact, most of this circuit only depends on . The only thing that depends on the actual function being computed are the connections between the gates closest to the input and the input.

Proof. We apply Lemma 6.1. Then an (resp. ) quantifier on bits corresponds to an Or (resp. And) gate with fan-in . A gate closest to the input correspond to the computation of the RAM for fixed quantified variables. This computation depends on at most one bit of . If this computation is a constant independent of , we simply replace this gate with the appropriate constant. Otherwise, if it depends on a bit of then the computation of the RAM is either or . Thus we can connect gate to either input gate or input gate .

An index to a gate next to the input is just an assignment to the quantified variables . Given such an index and we can compute in linear time which input bit it depends on. This is done by simulating the machine until the -th time it reads an input bit. Note this simulation runs in time which is linear in the length of an index to the gate. QED

6.3 BPP in PH

It is not known if BPP is contained in NP. However, we can show that BPP is in PH. More precisely, the following two simulations are known. The first optimizes the number of quantifiers, the second the time. This should be contrasted with various conditional results suggesting that in fact a quasilinear deterministic simulation (with no quantifiers) is possible.

Theorem 6.3. For every function we have:

(1) [35] , and

(2) [4
1] .

A good way to think of these results is as follows. Fix a machine and an input . Now the alternating machine is trying to decide if for most choices of the random bits we have , or if for most choices we have . This can be seen as a version of the Majority problem, with two critical features. The first is that it is succinct in the sense of section 5.4.1, that is, the alternating machine does not have access to the exponentially-long majority instance, but rather has access to a small circuit s.t.  is bit of the majority instance. The second is that instances have a gap. We define this gap-majority problem next. We define the non-succinct version which is of independent interest, and so use the letter to indicate input length. But recall that for the application later in this section the input is given succinctly, as just remarked, so the gap majority instance will actually be on a number of bits that is exponential in the input length to the alternating machine.

Definition 6.2. is the problem of deciding if an input has weight or .

As discussed in section º6.2, it is useful to think of alternating computation as alternating circuits. Indeed, the circuit result that is the starting point of all these simulations is the following somewhat surprising construction of small-depth alternating circuits for Gap-Maj. By contrast, (non-gap) Maj does not have small constant-depth alternating circuits, as we will prove in Chapter ??.

Lemma 6.3. [3] has alternating circuits of depth and size . Moreover, the gates at distance from the input have fan-in .

Proof. This is a striking application of the probabilistic method. For a fixed pair of inputs we say that a distribution on circuits gives if and ; and we similarly define gives with reverse inequalities. Our goal is to have a distribution that gives

for every pair where and . Indeed, if we have that we can apply a union bound over the inputs to obtain a fixed circuit that solves Gap-Maj.

We construct the distribution incrementally. Fix any pair as above. Begin with the distribution obtained by picking bits uniformly from the input and computing their And. This gives

Let and note . So we can say that gives

Now consider the distribution obtained by complementing the circuits in . This gives

Next consider the distribution obtained by taking the And of independent samples of . This gives

To make sense of these quantities we use the basic approximations

valid for all . These imply and Summarizing, this gives

Next consider the distribution obtained by complementing the circuits in . This gives

Finally, consider the distribution obtained by taking the And of independent samples of . This gives

To make sense of the rightmost quantity we can use the approximation

valid for all and . Thus this gives

We have . Thus this distribution in particular gives equation (??). The bounds on the number of gates and the fan-in holds by inspection. QED

Exercise 6.6. Prove has alternating circuits of depth and size .

Exercise 6.7. Assume the circuit in Lemma 6.3 is explicit in the sense of Lemma 6.2. Prove Theorem 6.3.

There remains to construct explicit circuits for Gap-Maj. We give a construction which has worse parameters than Lemma 6.3 but is simple and suffices for (1) in Theorem 6.3. The idea is that if the input weight of is large, then we can find a few shifts of the ones in that cover each of the bits. But if the weight of is small we can’t. By “shift” by we mean the string , obtained from by permuting the indices by xoring them with . (Other permutations would work just as well.)

Lemma 6.4. Let . The following circuit solves on every :

Note that

means that every bit is covered by some shift of the input .

Proof. Assume . Each shift contributes at most ones. Hence all the shifts contribute ones, and we do not cover every bit .

Now assume . We show the existence of shifts that cover every bit by the probabilistic method. Specifically, for a fixed we pick the shifts uniformly at random and aim to show that the probability that we do not cover every bit is . Indeed:

as desired. QED

Exercise 6.8. Prove (1) in Theorem 6.3.

Lemma 6.4 is not sufficient for (2) in Theorem 6.3. One can prove (2) by derandomizing the shifts in Lemma 6.4. This means generating their bits using a seed of only bits (instead of the trivial in Lemma 6.4.).

Exercise 6.9. Prove:

(1) .

(2) .

6.4 The quantifier calculus

We have extended with and quantifiers. We have also extended it with randomness to obtain . As alluded to before, we can also think of BPP as a quantifier applied to . The Unique-3Sat problem (Theorem 5.8) also points to a new quantifier, “exists unique.” We now develop a general calculus of quantifiers, and examine fundamental relationships between then. For simplicity, we only consider power-time computation.

Definition 6.3. Let be a class of functions mapping . We define if there is and such that

• 
  
• 
  
• (read: parity)
  
• 
  
• 
  

With this notation we have: , .

6.5 PH is a random low-degree polynomial

In this section we prove the following result.

Theorem 6.4. [37]

This is saying that any constant number of and quantifier can be replaced by a BP quantifier followed by a quantifier. Let’s see what this has to do with the title of this section. Where is the polynomial? Consider polynomials over . Recall that such a polynomial over bits is an object like

Because we are only interested in inputs in we have for any and any variable , so we don’t need to raise variables to powers bigger than one.

Example 6.1. The And function on bits can be written as the polynomial

The Or function on bits can be written as the polynomial

For we have

The polynomial corresponding to a PH computation will have an exponential number of terms, so we can’t write it down. The big sum over all its monomials corresponds to the in Theorem 6.4. The polynomial will be sufficiently explicit: we will be able to compute each of its monomials in P. Finally, there won’t be just one polynomial, but we will have a distribution on polynomials, and that’s the BP part.

Confusing? Like before, a good way to look at this result is in terms of alternating circuits. We state the basic circuit result behind Theorem 6.4 after a definition. The result is of independent interest and will be useful later.

Definition 6.4. A distribution on polynomials computes a function with error if for every we have

Theorem 6.5. Let be an alternating circuit of depth and size . Then there is a distribution on polynomials over of degree that computes with error .

Ultimately we only need constant error, but the construction requires small error. Jumping ahead, this is because we construct distributions for each gate separately, and we need the error to be small enough for a union bound over all gates in the circuit.

The important point in Theorem 6.5 is that if the depth is small (e.g., constant) (and the size is not enormous and the error is not too small) then the degree is small as well. For example, for power-size alternating circuits of constant depth the degree is power logarithmic for constant error.

Let us slowly illustrate the ideas behind Theorem 6.5 starting with the simplest case: is just a single Or gate on bits.

Lemma 6.5. For every and there is a distribution on polynomials of degree in variables over that computes Or with error .

Proof. For starters, pick the following distribution on linear polynomials: For a uniform output the polynomial

Let us analyze how behaves on a fixed input :

• If then ;
• If then .

While the error is large in some cases, a useful feature of is that it never makes mistakes if . This allows us to easily reduce the error by taking polynomials and combining them with an Or.

The analysis is like before:

• If then ;
• If then

It remains to bound the degree. Each has degree . The Or on bits has degree by Example 6.1. Hence the final degree is . QED

Exercise 6.10. Obtain the same result for .

Now we would like to handle general circuits which have any number of And and Or gates. As mentioned earlier, we apply the construction above to every gate, and compose the polynomials. We pick the error at each gate small enough so that we can do a union bound over all gates.

Proof of Theorem 6.5.  We apply Lemma 6.5 to every gate in the circuit with error . By a union bound, the probability that any gate makes a mistake is , as desired.

The final polynomial is obtained by composing the polynomials of each gate. The composition of a polynomial of degree with another of degree results in a polynomial of degree . Since each polynomial has degree , the final degree is . QED

6.5.1 Back to PH

We have proved Theorem 6.5 which is a circuit analogue of Theorem 6.4. We now go back to the PH. First, we have to come up with a more explicit description of the polynomials, instead of picking them at random. This is similar to the way we proceeded in section º6.3: After a non-explicit construction (Lemma 6.3) we then obtained an explicit construction (Lemma 6.4).

Let us go back to the simplest case of Or. Recall that the basic building block in the proof of Lemma 6.5 was the construction of a distribution on linear polynomials which are zero on the all-zero input (which just means that they do not have constant terms), and are often non-zero on any non-zero input. We introduce a definition, since now we will have several constructions with different parameters.

Definition 6.5. A distribution on linear polynomials with no constant term has the Or property if for any . We identify with the bits corresponding to its coefficients.

The next lemma shows that we can compute distributions on linear polynomials with the Or property from a seed of just bits, as opposed to the bits that were used for in the proof of Lemma 6.5. Recall that for our application to Lemma 6.5 the polynomials have an exponential number of monomials and so we cannot afford to write them down. Instead we shall guarantee that given a seed and an index to a monomial we can compute the monomial via a function in P. In this linear case, for a polynomial in variables we have monomials . So the function takes as input and a number and outputs the coefficient to .

Lemma 6.6. [25] Given , , and we can compute in P a function such that for uniform the distribution

has the Or property.

Proof. [4] Let and identify the field with bit strings of length . We view as a pair . Then we define

where is exponentiation in and is defined as over .

To show that this has the Or property, pick any non-zero . We have to show that

The critical step is to note that

Now, if , then the probability over that is . This is because any that gives a zero is a root of the non-zero, univariate polynomial of degree over , and so the bound follows by Theorem 5.8.

Whenever , the probability over that is . Hence our target probability above satisfies

as desired. QED

Exercise 6.11. Give an alternative construction of a distribution with the Or property following this guideline.

(1) Satisfy the Or property for every input with weight .

(2) For any , satisfy the Or property for every input with weight between and . Use Lemma 5.2.

(3) Combine (2) with various to satisfy the Or property for every input.

(4) State the seed length for your distribution and compare it to that of Lemma 6.6.

With this in hand, we can now reduce the error in the same way we reduced it in the proof of Lemma 6.5.

Lemma 6.7. Given , a seed , and we can compute in P a monomial of degree such that the distribution

for uniform computes Or with error .

Proof. We use the construction

from the proof of Lemma 6.5, except that each is now generated via Lemma 6.5, and that (as opposed to before). The bound on the degree is the same as before, as is the proof that it computes Or: The error will be .

There remains to show that the monomials can be computed in P. For this we can go back to the polynomial for Or in Example 6.1. Plugging that gives

We can use to index a choice of and then a choice for a monomial in each of the linear factors . For each factor we can use Lemma 6.6 to compute the monomials. QED

We can now use Lemma 6.7 to prove Theorem 6.4. As in the proof Theorem 6.5 we will convert each gate to a polynomial.

Proof of Theorem 6.4.  Let . Apply Lemma 6.2 to obtain a corresponding alternating circuit of depth and size for a constant . Replace each gate with the distribution on polynomials given by Lemma 6.7. Note each of these polynomials is on variables and has degree . We set the error in Lemma 6.7 to be . This guarantees that the seed length in each application of Lemma 6.7 is . Moreover, the seed used to sample the polynomials is re-used across all gates. We can afford this because we use a union bound in the analysis. Hence the seed length for all the polynomials is again just . We can quantify over this many bits using the BP quantifier.

Finally, we have to compose the polynomials at each gate. We are going to show how we can compute the monomials of the composed polynomial in the same way as we computed monomials in Lemma 6.7. Once we have a monomial in the input variables we simply evaluate it in P on the input bits.

Start at the output gate. We use bits in the quantifier to choose a monomial in the corresponding polynomial. We write down this monomial, using Lemma 6.7. This monomial is over the variables corresponding to the children of the output gate, and only contains variables. To each there corresponds a polynomial . Choose a monomial from and replace with that monomial; do this for every . The choice of the monomials is done again using bits quantified by the quantifier. We continue in this way until we have monomials just in the input variables . Because each monomial is over variables, and the depth is constant, the total number of bits in the quantifier, which are needed to choose monomials, is . QED

Exercise 6.12. A set of size is called linear if there exists an matrix over such that .

1. Recall error-correcting codes from Exercise 2.18. Prove that a linear set is an error-correcting code iff the weight of any non-zero string in is at least
2. Prove the existence of linear error-correcting codes matching the parameters in Exercise 2.18.
3. Let be a subset of s.t. the uniform distribution over has the Or property. Define matrix where the rows are the elements of . Prove that is an error-correcting code.
4. Give explicit error-correcting codes over bits of size .
5. This motivates improving the parameters of distributions with the Or property. Improve the seed length in Lemma 6.6 to . Hint: What property you need from ?
6. Give explicit error-correcting codes over bits of size .

6.6 The power of majority

Exercise 6.13. [The power of majority] Prove:

1. .
2. 
3. The same as but with replaced by .
4. .
5. Maj . (Hint: This is confusing if you don’t have the right angle, otherwise is not too bad. For starters, forget everything and imagine you have an integer in some range and you want to know if is odd by just asking questions of the type and , for various . You want that the number of questions with answer “yes” only depends on whether is odd or even.)
6. 

It is not known if has linear-size circuits. We saw in Exercise 6.4 that PH does not have circuits of size , for any . By Exercise 6.13 this holds for as well. The following result improves this Maj P. It is particularly interesting because it cannot be established using a well-studied class of techniques which includes all the results about PH we have encountered so far.

Theorem 6.6. [40] , for any .

References

[1]   Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59–78. IEEE Computer Society, 2015.

[2]   Leonard Adleman. Two theorems on random polynomial time. In 19th IEEE Symp. on Foundations of Computer Science (FOCS), pages 75–83. 1978.

[3]   Mikl≤s Ajtai. -formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983.

[4]   Noga Alon, Oded Goldreich, Johan Hσstad, and RenΘ Peralta. Simple constructions of almost -wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.

[5]   Dana Angluin and Leslie G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. Syst. Sci., 18(2):155–193, 1979.

[6]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. of the ACM, 45(3):501–555, May 1998.

[7]   Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput., 47(3):1087–1097, 2018.

[8]   Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, volume 32, pages 307–314, 1968.

[9]   Stephen A. Cook. A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences, 7(4):343–353, 1973.

[10]   Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199–214, 1981.

[11]   Anka Gajentaan and Mark H. Overmars. On a class of problems in computational geometry. Comput. Geom., 5:165–185, 1995.

[12]   M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

[13]   K. G÷del. ▄ber formal unentscheidbare sΣtze der Principia Mathematica und verwandter systeme I. Monatsh. Math. Phys., 38, 1931.

[14]   Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.

[15]   David Harvey and Joris van der Hoeven. Integer multiplication in time . Annals of Mathematics, 193(2):563 – 617, 2021.

[16]   F. C. Hennie. One-tape, off-line turing machine computations. Information and Control, 8(6):553–578, 1965.

[17]   Fred Hennie and Richard Stearns. Two-tape simulation of multitape turing machines. J. of the ACM, 13:533–546, October 1966.

[18]   Russell Impagliazzo and Ramamohan Paturi. The complexity of -sat. In IEEE Conf. on Computational Complexity (CCC), pages 237–, 1999.

[19]   Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Computer & Systems Sciences, 63(4):512–530, Dec 2001.

[20]   Russell Impagliazzo and Avi Wigderson. if requires exponential circuits: Derandomizing the XOR lemma. In 29th ACM Symp. on the Theory of Computing (STOC), pages 220–229. ACM, 1997.

[21]   Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L’Enseignement MathΘmatique. Revue Internationale. IIe SΘrie, 28(3-4):191–209, 1982.

[22]   Kojiro Kobayashi. On the structure of one-tape nondeterministic turing machine time hierarchy. Theor. Comput. Sci., 40:175–193, 1985.

[23]   Leonid A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115–116, 1973.

[24]   O. B. Lupanov. A method of circuit synthesis. Izv. VUZ Radiofiz., 1:120–140, 1958.

[25]   Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. on Computing, 22(4):838–856, 1993.

[26]   NEU. From RAM to SAT. Available at http://www.ccs.neu.edu/home/viola/, 2012.

[27]   Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425–440, 1991.

[28]   Wolfgang J. Paul, Nicholas Pippenger, Endre SzemerΘdi, and William T. Trotter. On determinism versus non-determinism and related problems (preliminary version). In IEEE Symp. on Foundations of Computer Science (FOCS), pages 429–438, 1983.

[29]   Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. of the ACM, 26(2):361–381, 1979.

[30]   J. M. Robson. N by N checkers is exptime complete. SIAM J. Comput., 13(2):252–267, 1984.

[31]   Rahul Santhanam. On separators, segregators and time versus space. In IEEE Conf. on Computational Complexity (CCC), pages 286–294, 2001.

[32]   Arnold Sch÷nhage. Storage modification machines. SIAM J. Comput., 9(3):490–508, 1980.

[33]   Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell System Tech. J., 28:59–98, 1949.

[34]   Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189):435–447, 1990.

[35]   Michael Sipser. A complexity theoretic approach to randomness. In ACM Symp. on the Theory of Computing (STOC), pages 330–335, 1983.

[36]   Larry Stockmeyer and Albert R. Meyer. Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM, 49(6):753–784, 2002.

[37]   Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. on Computing, 20(5):865–877, 1991.

[38]   Alan M. Turing. On computable numbers, with an application to the entscheidungsproblem. Proc. London Math. Soc., s2-42(1):230–265, 1937.

[39]   Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986.

[40]   N. V. Vinodchandran. A note on the circuit complexity of PP. Theor. Comput. Sci., 347(1-2):415–418, 2005.

[41]   Emanuele Viola. On approximate majority and probabilistic time. Computational Complexity, 18(3):337–375, 2009.

[42]   Emanuele Viola. Reducing 3XOR to listing triangles, an exposition. Available at http://www.ccs.neu.edu/home/viola/, 2011.

[43]   Emanuele Viola. Pseudorandom bits and lower bounds for randomized turing machines. Theory of Computing, 18(10):1–12, 2022.