Mathematics of the impossible, Chapter 10, Constant-depth circuits

Thoughts 2023-05-03

In this chapter we further investigate circuits of constant depth, focusing on two pervasive classes, which indeed we have already encountered under different names.

Note on notation: I here use “AC” for AltCkt a.k.a. alternating circuits. I also use AC for the class of functions $f$ computable by an AC of depth $d$ and size $n^{d}$ .

10.1 Threshold circuits

Definition 10.1. A threshold circuit, abbreviated TC, is a circuit made of Majority gates (of unbounded fan-in). We also denote by TC the class of functions $f$ computable by a TC of depth $d$ and size $n^{d}$ for some constant $d$ .

TCs are one of the frontiers of our knowledge. It isn’t known how to prove impossibility results even for TCs of depth $3$ and size, say, $n^{2}$ .

Exercise 10.1. Prove that $\text {AC}\subseteq \text {TC}\subseteq \text {NC}^{1}$ .

Exercise 10.2. A function $f:\{0,1\} ^{*}\to \{0,1\}$ is symmetric if it only depends on the weight of the input. Prove that any symmetric function is in $\text {TC}$ .

The result $\text {PH}\text {\ensuremath {\subseteq \text {Maj}\cdot \text {Maj}\cdot \text {P}}}$ obtained in 6.13 in particular yields the following.

Theorem 10.1. [5]Any function $f$ in AC has TCs of depth $3$ and size $2^{\log ^{c_{f}}n}$ .

Theorem 10.2. The following problems are in TC:

Addition of two input integers.
Iterated addition: Addition of any number of input integers.
Multiplication of two input integers.
Iterated multiplication: Multiplication of any number of input integers.
Division of two integers.

The proof follows closely that for NC $^{1}$ in section �9.1 (which in turn was based on that for L). Only iterated addition requires a new idea.

Exercise 10.3. Prove the claim about iterated addition. (Hint: Write input as $n\times n$ matrix, one number per row. Divide columns into blocks of $t=c\log n$ .)

10.2 TC vs. NC $^{1}$

Another great question is whether $\text {TC}=\text {NC}^{1}.$ For any $d$ , we can show that functions in $\text {NC}^{1}$ , such as Parity, require depth- $d$ TCs of size $\ge n^{1+c\log d}$ , and this is tight up to constants.[34] A natural question is whether we can prove stronger bounds for harder functions in $\text {NC}^{1}$ . A natural candidate is iterated multiplication of 3×3 matrices. The following result shows that, in fact, stronger bounds would already prove “the whole thing,” that is, $\text {TC}\ne \text {NC}^{1}.$

Theorem 10.3. [7, 17] Let $G$ be the set of 3×3 matrices of $\mathbb {F}_{2}$ . Suppose that the product of $n$ elements in $G$ can be computed by TCs of size $n^{k}$ and depth $d$ . Then for any $\epsilon$ the product can also be computed by TCs of size $d'n^{1+\epsilon }$ and depth $d':=cdk\log 1/\epsilon$ .

The same result applies to any constant-size group $G$ – we state it for matrices for concreteness.

Proof. Exploiting the associativity of the problem, we compute the product recursively according to a regular tree. The root is defined to have level $0$ . At Level $i$ we compute $n_{i}$ products of $(n^{1+\epsilon }/n_{i})^{1/k}$ matrices. At the root $(i=0)$ we have $n_{0}=1$ .

By the assumption, each product at Level $i$ has TCs of size $n^{1+\epsilon }/n_{i}$ and depth $d$ . Hence Level $i$ can be computed by TCs of size $n^{1+\epsilon }$ and depth $d$ .

We have the recursion

$\begin{aligned} n_{i+1}=n_{i}\cdot (n^{1+\epsilon }/n_{i})^{1/k}. \end{aligned}$

The solution to this recursion is $n_{i}=n^{(1+\epsilon )(1-(1-1/k)^{i})}$ , see below.

For $i=ck\log (1/\epsilon )$ we have $n_{i}=n^{(1+\epsilon )(1-\epsilon ^{2})}>n$ ; this means that we can compute a product of $\ge n$ matrices, as required.

Hence the total depth of the circuit is $d\cdot ck\log (1/\epsilon )$ , and the total size is the depth times $n^{1+\epsilon }$ .

It remains to solve the recurrence. Letting $a_{i}:=\log _{n}n_{i}$ we have the following recurrence for the exponents of $n_{i}$ .

$\begin{aligned} a_{0} & =0\\ a_{i+1} & =a_{i}(1-1/k)+(1+\epsilon )/k=a_{i}\alpha +\gamma \end{aligned}$

where $\alpha :=(1-1/k)$ and $\gamma :=(1+\epsilon )/k$ .

This gives

$\begin{aligned} a_{i}=\gamma \sum _{j\le i}\alpha {}^{j}=\gamma \frac {1-\alpha ^{i+1}}{1-\alpha }=(1+\epsilon )(1-\alpha ^{i+1}). \end{aligned}$

QED

Were the recursion of the form $a'_{i+1}=a'_{i}+(1+\epsilon )/k$ then obviously $a'_{ck}$ would already be $\ge 1+\epsilon$ . Instead for $a_{i}$ we need to get to $ck\log (1/\epsilon )$ .

10.3 Impossibility results for AC

In this section we prove impossibility results for ACs, matching several settings of parameters mentioned earlier (cf. section �7.3).

To set the stage, let’s prove strong results for depth 2, that is, DNFs.

Exercise 10.4. Prove that Majority requires DNFs of size $\ge 2^{cn}$ . Hint: What if you have a term with less than $n$ variables?

As discussed, $2^{cn}$ bounds even for depth 3 ACs are unknown, and would imply major separations. The following is close to the state-of-the-art for depth $d$ .

Theorem 10.4. [52, 63] Let C be an AC of depth $d$ and size $s$ computing Majority on $n$ bits. Then $\log ^{d}s\ge c\sqrt {n}$ .

Recall from section �7.3 that a stronger bound for an explicit function would have major consequences; in particular the function cannot be in L.

The proof uses the simulation of circuits by low-degree polynomials which we saw in Theorem 6.5. Specifically, we use the following corollary:

Corollary 10.1. Let $C:\{0,1\} ^{n}\to \{0,1\}$ be an alternating circuit of depth $d$ and size $s$ . Then there is a polynomial $p$ over $\mathbb {F}_{2}$ of degree $\log ^{d}s/\epsilon$ such that $\mathbb {P}_{x}[C(x)\ne p(x)]\le \epsilon$ .

Proof. Theorem 6.5 gave a distribution $P$ on polynomials s.t. for every $x$ we have

$\begin{aligned} \mathbb {P}_{P}[C(x)\ne P(x)]\le \epsilon . \end{aligned}$

Averaging over $x$ we also have

$\begin{aligned} \mathbb {P}_{x,P}[C(x)\ne P(x)]\le \epsilon . \end{aligned}$

Hence we can fix a particular polynomial $p$ s.t. the probability over $x$ is $\le \epsilon$ , yielding the result. QED

We then show that Majority cannot be approximated by such low-degree polynomials.

The key result is the following:

Lemma 10.1. Every function $f:\{0,1\}^n \to \{0,1\}$ can be written as $f(x)=p_{0}(x)+p_{1}(x)\cdot \text {Maj}(x)$ , for some polynomials $p_{0}$ and $p_{1}$ of degree $\le n/2$ . This holds for every odd $n$ .

Proof. Let $M_{0}$ be the set of strings with weight $\le n/2$ . We claim that for every function $f:M_{0}\to \{0,1\}$ there is a polynomial $p_{0}$ of degree $\le n/2$ s.t. $p_{0}$ and $f$ agree on $M_{0}$ .

To verify this, consider the monomials of degree $\le n/2$ . We claim that (the vectors corresponding to) their truth tables over $M_{0}$ are linearly independent. This means that any polynomial gives a different function over $M_{0}$ , and because the number of polynomials is the same as the number of functions, the result follows. QED

Exercise 10.5. Prove the claim in the proof.

Proof of Theorem 10.4. Apply Corollary 10.1 with $\epsilon =1/10$ to obtain $p$ . Let $S$ be the set of inputs on which $p(x)=C(x)$ . By Lemma 10.1, any function $f:S\to \{0,1\}$ ca be written as

$\begin{aligned} f(x)=p_{0}(x)+p_{1}(x)\cdot p(x). \end{aligned}$

The right-hand size is a polynomial of degree $\le d':=n/2+\log ^{d}(cs)$ . The number of such polynomials is the number of possible choices for each monomial of degree $i$ , for any $i$ up to the degree. This number is

$\begin{aligned} \prod _{i=0}^{d'}2^{{n \choose i}}=2^{\sum _{i}^{d'}{n \choose i}}. \end{aligned}$

On the other hand, the number of possible functions $f:S\to \{0,1\}$ is

$\begin{aligned} 2^{|S|}. \end{aligned}$

Since a polynomial computes at most one function, taking logs we have

$\begin{aligned} |S|\le \sum _{i}^{d'}{n \choose i}. \end{aligned}$

The right-hand side is at most $2^{n}(1/2+c\log ^{d}(s)/\sqrt {n})$ , since each binomial coefficient is $\le c2^{n}/\sqrt {n}$ .

On the other hand, $|S|\ge 0.9\cdot 2^{n}.$

Combining this we get

$\begin{aligned} 0.9\cdot 2^{n}\le 2^{n}(1/2+c\log ^{d}(s)/\sqrt {n}). \end{aligned}$

This implies

$\begin{aligned} 0.4\le c\log ^{d}(s)/\sqrt {n}, \end{aligned}$

proving the theorem. QED

Exercise 10.6. Explain why Theorem 10.4 holds even if the circuits have Parity gates (in addition to Or and And gates).

[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. $\Sigma \sp {1}\sb {1}$ -formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983.

[4] Mikl�s Ajtai. A non-linear time lower bound for boolean branching programs. Theory of Computing, 1(1):149–176, 2005.

[5] Eric Allender. A note on the power of threshold circuits. In 30th Symposium on Foundations of Computer Science, pages 580–584, Research Triangle Park, North Carolina, 30 October–1 November 1989. IEEE.

[6] Eric Allender. The division breakthroughs. Bulletin of the EATCS, 74:61–77, 2001.

[7] Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. of the ACM, 57(3), 2010.

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

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

[10] 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.

[11] 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.

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

[13] Paul Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM J. Comput., 15(4):994–1003, 1986.

[14] Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. of the ACM, 50(2):154–195, 2003.

[15] Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. on Computing, 21(1):54–58, 1992.

[16] Samuel R. Buss and Ryan Williams. Limits on alternation trading proofs for time-space lower bounds. Comput. Complex., 24(3):533–600, 2015.

[17] Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits “just beyond” known lower bounds. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 34–41. ACM, 2019.

[18] Richard Cleve. Towards optimal simulations of formulas by bounded-width programs. Computational Complexity, 1:91–105, 1991.

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

[20] L. Csanky. Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623, 1976.

[21] Lance Fortnow. Time-space tradeoffs for satisfiability. J. Comput. Syst. Sci., 60(2):337–353, 2000.

[22] 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.

[23] Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In ACM Symp. on the Theory of Computing (STOC), pages 345–354, 1989.

[24] Anka Gajentaan and Mark H. Overmars. On a class of ${O}(n^2)$ problems in computational geometry. Comput. Geom., 5:165–185, 1995.

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

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

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

[28] Raymond Greenlaw, H. James Hoover, and Walter Ruzzo. Limits to Parallel Computation: P-Completeness Theory. 02 2001.

[29] David Harvey and Joris van der Hoeven. Integer multiplication in time $O(n\mathrm {log}\, n)$ . Annals of Mathematics, 193(2):563 – 617, 2021.

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

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

[32] John E. Hopcroft, Wolfgang J. Paul, and Leslie G. Valiant. On time versus space. J. ACM, 24(2):332–337, 1977.

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

[34] Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-depth tradeoffs for threshold circuits. SIAM J. Comput., 26(3):693–707, 1997.

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

[36] Russell Impagliazzo and Avi Wigderson. $\mathit {P} = \mathit {BPP}$ if $E$ requires exponential circuits: Derandomizing the XOR lemma. In 29th ACM Symp. on the Theory of Computing (STOC), pages 220–229. ACM, 1997.

[37] 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.

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

[39] Kasper Green Larsen, Omri Weinstein, and Huacheng Yu. Crossing the logarithmic barrier for dynamic boolean data structure lower bounds. SIAM J. Comput., 49(5), 2020.

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

[41] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. of the ACM, 39(4):859–868, October 1992.

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

[43] Wolfgang Maass and Amir Schorr. Speed-up of Turing machines with one work tape and a two-way input tape. SIAM J. on Computing, 16(1):195–202, 1987.

[44] David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC $^1$ . J. of Computer and System Sciences, 38(1):150–164, 1989.

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

[46] E. I. Nechiporuk. A boolean function. Soviet Mathematics-Doklady, 169(4):765–766, 1966.

[47] Valery A. Nepomnjaščiĭ. Rudimentary predicates and Turing calculations. Soviet Mathematics-Doklady, 11(6):1462–1465, 1970.

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

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

[50] 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.

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

[52] Alexander Razborov. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Akademiya Nauk SSSR. Matematicheskie Zametki, 41(4):598–607, 1987. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.

[53] Omer Reingold. Undirected connectivity in log-space. J. of the ACM, 55(4), 2008.

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

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

[56] Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970.

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

[58] Adi Shamir. IP = PSPACE. J. of the ACM, 39(4):869–877, October 1992.

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

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

[61] Alan Siegel. On universal classes of extremely random constant-time hash functions. SIAM J. on Computing, 33(3):505–543, 2004.

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

[63] Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In 19th ACM Symp. on the Theory of Computing (STOC), pages 77–82. ACM, 1987.

[64] 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.

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

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

[67] Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In 6th Symposium on Mathematical Foundations of Computer Science, volume 53 of Lecture Notes in Computer Science, pages 162–176. Springer, 1977.

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

[69] Dieter van Melkebeek. A survey of lower bounds for satisfiability and related problems. Foundations and Trends in Theoretical Computer Science, 2(3):197–303, 2006.

[70] Dieter van Melkebeek and Ran Raz. A time lower bound for satisfiability. Theor. Comput. Sci., 348(2-3):311–320, 2005.

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

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

[73] Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1–72, 2009.

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

[75] Emanuele Viola. Lower bounds for data structures with space close to maximum imply circuit lower bounds. Theory of Computing, 15:1–9, 2019. Available at http://www.ccs.neu.edu/home/viola/.

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