Abstract
In a seminal work, Williams [22] showed that \(\mathsf {NEXP}\) (non-deterministic exponential time) does not have polynomial-size \(\mathsf {ACC}^0\) circuits. Williams’ technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known. We show that there is a language L in \(\mathsf {NEXP}\) and a function \(\varepsilon (n) = 1/\log (n)^{\omega (1)}\) such that no sequence of polynomial size \(\mathsf {ACC}^0\) circuits solves L on more than a \(1/2+\varepsilon (n)\) fraction of inputs of length n for all large enough n. Complementing this result, we give a nontrivial pseudo-random generator against polynomial-size \(\mathsf {AC}^0[6]\) circuits. We also show that learning algorithms for quasi-polynomial size \(\mathsf {ACC}^0\) circuits running in time \(2^n/n^\omega (1)\) imply lower bounds for the randomised exponential time classes \(\mathsf {RE}\) (randomized time \(2^{O(n)}\) with one-sided error) and \(\mathsf {ZPE}/1\) (zero-error randomized time \(2^{O(n)}\) with 1 bit of advice) against polynomial size \(\mathsf {ACC}^0\) circuits. This strengthens results of Oliveira and Santhanam [15].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This corresponds to monotone error-correcting codes, which cannot have good distance. We refer to [4] for more details.
- 2.
- 3.
In other words, the non-deterministic algorithm, when given the correct advice bit (that only depends on the input length parameter), outputs either “abort” of the correct string, and outputs the correct string in at least one computation path. We refer to Sect. 3.1 for more details.
- 4.
For a concrete example of the benefits of improving an \(\mathsf {NEXP}\) lower bound to randomized exponential time classes such as \(\mathsf {REXP}\), we refer the reader to [15].
- 5.
The design of concrete non-trivial learning algorithms for some circuit classes and in some alternative but related learning models has been recently investigated in [17].
- 6.
Note that the process of amplifying the success probability of randomized algorithms and fixing the randomness can be done with only an \(\mathsf {AC}^0\) overhead on the overall complexity, since approximate majority functions can be computed in this circuit class.
References
TCS Stack Exchange: How powerful is \(\sf ACC^0\) circuit class in average case? https://cstheory.stackexchange.com/q/37232. Accessed 27 Sept 2017
Ajtai, M.: \(\varSigma ^{1}_{1}\)-formulae on finite structures. Ann. Pure Appl. Logic 24(1), 1–48 (1983). https://doi.org/10.1016/0168-0072(83)90038-6
Arora, S., Barak, B.: Complexity Theory: A Modern Approach. Cambridge University Press, Cambridge (2009)
Buresh-Oppenheim, J., Kabanets, V., Santhanam, R.: Uniform hardness amplification in NP via monotone codes. In: Electronic Colloquium on Computational Complexity (ECCC) TR06-154 (2006). https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-154/
Carmosino, M.L., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Learning algorithms from natural proofs. In: Conference on Computational Complexity (CCC), pp. 10:1–10:24 (2016). https://doi.org/10.4230/LIPIcs.CCC.2016.10
Chen, R., Oliveira, I.C., Santhanam, R.: An average-case lower bound against ACC\(^0\). In: Electronic Colloquium on Computational Complexity (ECCC) TR17-173 (2017). https://eccc.weizmann.ac.il/report/2017/173/
Fefferman, B., Shaltiel, R., Umans, C., Viola, E.: On beating the hybrid argument. Theory Comput. 9, 809–843 (2013). https://doi.org/10.4086/toc.2013.v009a026
Furst, M., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13–27 (1984). https://doi.org/10.1007/BF01744431
Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.N.: Verifying and decoding in constant depth. In: Symposium on Theory of Computing (STOC), pp. 440–449 (2007). https://doi.org/10.1145/1250790.1250855
Gutfreund, D., Rothblum, G.N.: The complexity of local list decoding. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX/RANDOM -2008. LNCS, vol. 5171, pp. 455–468. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85363-3_36
Håstad, J.: Almost optimal lower bounds for small depth circuits. In: Symposium on Theory of Computing (STOC), pp. 6–20 (1986). https://doi.org/10.1145/12130.12132
Impagliazzo, R., Kabanets, V., Volkovich, I.: The power of natural properties as oracles. In: Electronic Colloquium on Computational Complexity (ECCC) TR17-023 (2017). https://eccc.weizmann.ac.il/report/2017/023/
Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. 49(2), 149–167 (1994). https://doi.org/10.1016/S0022-0000(05)80043-1
Oliveira, I.C., Santhanam, R.: Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In: Computational Complexity Conference (CCC), pp. 18:1–18:49 (2017). https://doi.org/10.4230/LIPIcs.CCC.2017.18
Oliveira, I.C., Santhanam, R.: Pseudodeterministic constructions in subexponential time. In: Symposium on Theory of Computing (STOC), pp. 665–677 (2017). https://doi.org/10.1145/3055399.3055500
Razborov, A.A.: Lower bounds on the size of bounded-depth networks over the complete basis with logical addition. Math. Notes Acad. Sci. USSR 41(4), 333–338 (1987)
Servedio, R., Tan, L.Y.: What circuit classes can be learned with non-trivial savings? In: Innovations in Theoretical Computer Science Conference (ITCS), pp. 1–23 (2017)
Shaltiel, R., Viola, E.: Hardness amplification proofs require majority. SIAM J. Comput. 39(7), 3122–3154 (2010). https://doi.org/10.1137/080735096
Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Symposium on Theory of Computing (STOC), pp. 77–82 (1987). https://doi.org/10.1145/28395.28404
Srinivasan, S.: On improved degree lower bounds for polynomial approximation. In: Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 201–212 (2013). https://doi.org/10.4230/LIPIcs.FSTTCS.2013.201
Sudan, M., Trevisan, L., Vadhan, S.P.: Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci. 62(2), 236–266 (2001). https://doi.org/10.1006/jcss.2000.1730
Williams, R.: Nonuniform ACC circuit lower bounds. J. ACM 61(1), 2:1–2:32 (2014). https://doi.org/10.1145/2559903
Williams, R.: Natural proofs versus derandomization. SIAM J. Comput. 45(2), 497–529 (2016). https://doi.org/10.1137/130938219
Yao, A.C.: Separating the polynomial-time hierarchy by oracles (preliminary version). In: Symposium on Foundations of Computer Science (FOCS), pp. 1–10 (1985). https://doi.org/10.1109/SFCS.1985.49
Acknowledgements
We would like to thank Marco Carmosino for posing the question of proving average-case hardness against \(\mathsf {ACC}^0\), and for useful discussions. This work was supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2014)/ERC Grant Agrement no. 615075.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Chen, R., Oliveira, I.C., Santhanam, R. (2018). An Average-Case Lower Bound Against \(\mathsf {ACC}^0\) . In: Bender, M., Farach-Colton, M., Mosteiro, M. (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science(), vol 10807. Springer, Cham. https://doi.org/10.1007/978-3-319-77404-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-77404-6_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-77403-9
Online ISBN: 978-3-319-77404-6
eBook Packages: Computer ScienceComputer Science (R0)