Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression

by Swastik Kopparty and Srikanth Srinivasan

Theory of Computing, Volume 14(12), pp. 1-24, 2018

Bibliography with links to cited articles

[1]   Miklós Ajtai: Approximate counting with uniform constant-depth circuits. In Jin-Yi Cai, editor, Advances in Computational Complexity Theory, volume 13 of DIMACS Ser. in Discr. Math. and Theoret. Comput. Sci., pp. 1–20. Amer. Math. Soc., 1993.

[2]   Miklós Ajtai and Michael Ben-Or: A theorem on probabilistic constant depth computations. In Proc. 16th STOC, pp. 471–474. ACM Press, 1984. [doi:10.1145/800057.808715]

[3]   Michael Alekhnovich and Alexander A. Razborov: Lower bounds for polynomial calculus: Non-binomial case. In Proc. 42nd FOCS, pp. 190–199. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959893]

[4]   Kazuyuki Amano: k-subgraph isomorphism on AC0 circuits. Comput. Complexity, 19(2):183–210, 2010. Preliminary version in CCC’09. [doi:10.1007/s00037-010-0288-y]

[5]   Ian Anderson: Combinatorics of Finite Sets. Dover, 2011.

[6]   Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ACM DL.

[7]   James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich: The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994. Preliminary version in STOC’91. [doi:10.1007/BF01215346]

[8]   Mark Braverman: Polylogarithmic independence fools AC0 circuits. J. ACM, 57(5):28:1–28:10, 2010. Preliminary version in CCC’09. [doi:10.1145/1754399.1754401]

[9]   Claude Carlet, Deepak Kumar Dalai, Kishan Chand Gupta, and Subhamoy Maitra: Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction. IEEE Trans. Inform. Theory, 52(7):3105–3121, 2006. [doi:10.1109/TIT.2006.876253]

[10]   Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova: Learning algorithms from natural proofs. In Proc. 31st Computational Complexity Conf. (CCC’16), pp. 10:1–10:24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.10]

[11]    Shiva Chaudhuri and Jaikumar Radhakrishnan: Deterministic restrictions in circuit complexity. In Proc. 28th STOC, pp. 30–36. ACM Press, 1996. [doi:10.1145/237814.237824]

[12]   Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman: Mining circuit lower bound proofs for meta-algorithms. Comput. Complexity, 24(2):333–392, 2015. Preliminary version in CCC’14. [doi:10.1007/s00037-015-0100-0]

[13]   David A. Cox, John Little, and Donal O’Shea: Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, 1992. [doi:10.1007/978-3-319-16721-3]

[14]   Merrick L. Furst, James B. Saxe, and Michael Sipser: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13–27, 1984. Preliminary version in FOCS’81. [doi:10.1007/BF01744431]

[15]   Frederic Green: A complex-number Fourier technique for lower bounds on the Mod-m degree. Comput. Complexity, 9(1):16–38, 2000. [doi:10.1007/PL00001599]

[16]   Venkatesan Guruswami, Atri Rudra, and Madhu Sudan: Essential Coding Theory. 2013-17. Available at author’s webpage.

[17]    Prahladh Harsha and Srikanth Srinivasan: On polynomial approximations to AC0. In Proc. 19th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’16), pp. 32:1–32:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.APPROX-RANDOM.2016.32, arXiv:1604.08121]

[18]   Johan Hĺstad: Computational Limitations of Small-depth Circuits. MIT Press, 1987.

[19]   Swastik Kopparty and Srikanth Srinivasan: Certifying polynomials for AC0(parity) circuits, with applications. In Proc. 32nd IARCS Ann. Conf. on Foundations of Software Technology and Theoret. Computer Sci. (FSTTCS’12), pp. 36–47. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012. [doi:10.4230/LIPIcs.FSTTCS.2012.36]

[20]   Francis S. Macaulay: Some properties of enumeration in the theory of modular systems. Proc. London Math. Soc., 26(1):531–555, 1927. [doi:10.1112/plms/s2-26.1.531]

[21]   Zipei Nie and Anthony Y. Wang: Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry. J. Combin. Theory Ser. A, 134:196 – 220, 2015. [doi:10.1016/j.jcta.2015.03.011, arXiv:1402.3018]

[22]    Igor Carboni Oliveira and Rahul Santhanam: Majority is incompressible by AC0[p] circuits. In Proc. 30th Computational Complexity Conf. (CCC’15), pp. 124–157. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.CCC.2015.124]

[23]   Prabhakar Ragde and Avi Wigderson: Linear-size constant-depth polylog-threshold circuits. Inform. Process. Lett., 39(3):143–146, 1991. [doi:10.1016/0020-0190(91)90110-4]

[24]   Alexander A. Razborov: Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41(4):598–607, 1987.

[25]   Alexander A. Razborov and Steven Rudich: Natural proofs. J. Comput. System Sci., 55(1):24–35, 1997. Preliminary version in STOC’94. [doi:10.1006/jcss.1997.1494]

[26]   Benjamin Rossman: On the constant-depth complexity of k-clique. In Proc. 40th STOC, pp. 721–730. ACM Press, 2008. [doi:10.1145/1374376.1374480]

[27]   Roman Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. 19th STOC, pp. 77–82. ACM Press, 1987. [doi:10.1145/28395.28404]

[28]   Roman Smolensky: On representations by low-degree polynomials. In Proc. 34th FOCS, pp. 130–138. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SFCS.1993.366874]

[29]   Srikanth Srinivasan: A compression algorithm for AC0[] circuits using certifying polynomials. Electron. Colloq. on Comput. Complexity (ECCC), 22:142, 2015. LINK.

[30]   Avishay Tal: Tight bounds on the Fourier spectrum of AC0. In Proc. 32nd Computational Complexity Conf. (CCC’17), pp. 15:1–15:31. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.15]

[31]   Emanuele Viola: On approximate majority and probabilistic time. Comput. Complexity, 18(3):337–375, 2009. Preliminary version in CCC’07. [doi:10.1007/s00037-009-0267-3]

[32]   Ingo Wegener: The Complexity of Boolean Functions. John Wiley & Sons, Inc., 1987.

[33]   Ryan Williams: New algorithms and lower bounds for circuits with linear threshold gates. In Proc. 46th STOC, pp. 194–202. ACM Press, 2014. [doi:10.1145/2591796.2591858, arXiv:1401.2444]

[34]   Andrew Chi-Chih Yao: Separating the polynomial-time hierarchy by oracles. In Proc. 26th FOCS, pp. 1–10. IEEE Comp. Soc. Press, 1985. [doi:10.1109/SFCS.1985.49]