Bounded-depth circuits cannot sample good codes. (English) Zbl 1282.68125
Summary: We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of \(1 - 1/n^{\Omega(1)}\) on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a. \(\mathrm{AC}^0\)) circuit \(f:\{0, 1\}^{\mathrm{poly}(n)} \rightarrow \{0,1\}^n\), and (ii) the uniform distribution over any code \(\mathcal C \subseteq \{0, 1\}^n\) that is “good”, that is, has relative distance and rate both \(\Omega (1)\). This seems to be the first lower bound of this kind.
We give two simple applications of this result: (1) any data structure for storing codewords of a good code \(\mathcal C\subseteq \{0, 1\}^n\) requires redundancy \(\Omega (\log n)\), if each bit of the codeword can be retrieved by a small \(\mathrm{AC}^0\) circuit; and (2) for some choice of the underlying combinatorial designs, the output distribution of Nisan’s pseudorandom generator against \(\mathrm{AC}^0\) circuits of depth \(d\) cannot be sampled by small \(\mathrm{AC}^0\) circuits of depth less than \(d\).
We give two simple applications of this result: (1) any data structure for storing codewords of a good code \(\mathcal C\subseteq \{0, 1\}^n\) requires redundancy \(\Omega (\log n)\), if each bit of the codeword can be retrieved by a small \(\mathrm{AC}^0\) circuit; and (2) for some choice of the underlying combinatorial designs, the output distribution of Nisan’s pseudorandom generator against \(\mathrm{AC}^0\) circuits of depth \(d\) cannot be sampled by small \(\mathrm{AC}^0\) circuits of depth less than \(d\).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson (2003) The Quantum Communication Complexity of Sampling. SIAM J. Comput. 32(6): 1570–1585 · Zbl 1041.68002 · doi:10.1137/S009753979935476 |
| [2] | Louay M. J. Bazzi (2009) Polylogarithmic Independence Can Fool DNF Formulas. SIAM J. Comput. 38(6): 2220–2272 · Zbl 1188.68156 · doi:10.1137/070691954 |
| [3] | Ravi Boppana (1997) The average sensitivity of bounded-depth circuits. Information Processing Letters 63(5): 257–261 ISSN 00200190 · Zbl 1337.68124 · doi:10.1016/S0020-0190(97)00131-2 |
| [4] | Mark Braverman (2010). Polylogarithmic independence fools AC0 circuits. J. of the ACM 57(5). · Zbl 1327.68108 |
| [5] | Anna Gál & Peter Bro Miltersen (2007). The cell probe complexity of succinct data structures. Theoret. Comput. Sci.379(3), 405–417. ISSN 0304-3975. · Zbl 1152.68428 |
| [6] | Oded Goldreich, Shafi Goldwasser, Asaf Nussboim (2010) On the Implementation of Huge Random Objects. SIAM J. Comput. 39(7): 2761–2822 · Zbl 1225.68132 · doi:10.1137/080722771 |
| [7] | Venkatesan Guruswami, Christopher Umans & Salil P. Vadhan (2009). Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes. J. of the ACM 56(4). · Zbl 1325.68169 |
| [8] | Harper L.H. (1964) Optimal Assignments of Numbers to Vertices. SIAM Journal on Applied Mathematics 12(1): 131–135 · Zbl 0222.94004 · doi:10.1137/0112012 |
| [9] | Sergiu Hart (1976) A note on the edges of the n-cube. Discrete Mathematics 14(2): 157–163 · Zbl 0363.05058 · doi:10.1016/0012-365X(76)90058-3 |
| [10] | Johan Håstad (1987). Computational limitations of small-depth circuits. MIT Press. ISBN 0262081679. |
| [11] | Marc R. Jerrum, Leslie G. Valiant, Vijay V. Vazirani (1986) Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science 43(2–3): 169–188 · Zbl 0597.68056 · doi:10.1016/0304-3975(86)90174-X |
| [12] | Nathan Linial, Yishay Mansour & Noam Nisan (1993). Constant depth circuits, Fourier transform, and learnability. J. of the ACM 40(3), 607–620. ISSN 0004-5411. · Zbl 0781.94006 |
| [13] | Shachar Lovett & Emanuele Viola (2011). Bounded-depth circuits cannot sample good codes. In IEEE Conf. on Computational Complexity (CCC). · Zbl 1282.68125 |
| [14] | Peter Bro Miltersen (1999). Cell probe complexity - a survey. Invited talk/paper at Advances in Data Structures (Pre-conference workshop of FSTTCS’99). · Zbl 0873.68093 |
| [15] | Noam Nisan (1991). Pseudorandom bits for constant depth circuits. Combinatorica 11(1), 63–70. ISSN 0209-9683. · Zbl 0732.68056 |
| [16] | Ryan O’Donnell (2007). Analysis of Boolean Functions. Lecture notes. Available at http://www.cs.cmu.edu/\(\sim\)odonnell/boolean-analysis . |
| [17] | Alexander A. Razborov (2009). A Simple Proof of Bazzi’s Theorem. ACM Transactions on Computation Theory (TOCT) 1(1). · Zbl 1322.68108 |
| [18] | Emanuele Viola (2004) The Complexity of Constructing Pseudorandom Generators from Hard Functions. Computational Complexity 13(3-4): 147–188 · Zbl 1061.68077 |
| [19] | Emanuele Viola (2010). The complexity of distributions. SIAM J. on Computing To appear. · Zbl 1255.68077 |
| [20] | Emanuele Viola (2011). Extractors for circuit sources. In IEEE Symp. on Foundations of Computer Science (FOCS). · Zbl 1292.68117 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
