Separation of AC$^0[\oplus]$ Formulas and Circuits
by Ben Rossman and Srikanth Srinivasan
Theory of Computing, Volume 15(17), pp. 1-20, 2019
Bibliography with links to cited articles
[1] Kazuyuki Amano: Bounds on the size of small depth circuits for approximating majority. In Proc. 36th Internat. Colloq. on Automata, Languages and Programming (ICALP’09), pp. 59–70. Springer, 2009. [doi:10.1007/978-3-642-02927-1_7]
[2] Sanjeev Arora and Boaz Barak: Computational Complexity - A Modern Approach. Cambridge Univ. Press, 2009. [doi:10.1017/CBO9780511804090]
[3] Richard Beigel: The polynomial method in circuit complexity. In Proc. 8th IEEE Conf. on Structure in Complexity Theory (SCT’93), pp. 82–95. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SCT.1993.336538]
[4] Eric Blais and Li-Yang Tan: Approximating Boolean functions with depth-2 circuits. SIAM J. Comput., 44(6):1583–1600, 2015. Preliminary version in CCC’13. [doi:10.1137/14097402X]
[5] Prahladh Harsha and Srikanth Srinivasan: On polynomial approximations to AC0. Random Structures Algorithms, 54(2):289–303, 2019. Preliminary version in RANDOM’16. [doi:10.1002/rsa.20786, arXiv:1604.08121]
[6] Johan Håstad: Almost optimal lower bounds for small depth circuits. In Proc. 18th STOC, pp. 6–20. ACM Press, 1986. [doi:10.1145/12130.12132]
[7] Shlomo Hoory, Avner Magen, and Toniann Pitassi: Monotone circuits for the majority function. In Proc. Internat. Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM’06), pp. 410–425. Springer, 2006. [doi:10.1007/11830924_38]
[8] Stasys Jukna: Boolean Function Complexity: Advances and Frontiers. Springer, 2012. [doi:10.1007/978-3-642-24508-4]
[9] Mauricio Karchmer and Avi Wigderson: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math., 3(2):255–265, 1990. Preliminary version in STOC’88. [doi:10.1137/0403021]
[10] Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, and Mihalis Yannakakis: On monotone formulae with restricted depth. In Proc. 16th STOC, pp. 480–487. ACM Press, 1984. [doi:10.1145/800057.808717]
[11] Swastik Kopparty and Srikanth Srinivasan: Certifying polynomials for AC0[⊕] circuits, with applications to lower bounds and circuit compression. Theory of Computing, 14(12):1–24, 2018. Preliminary version in FSTTCS’12. [doi:10.4086/toc.2018.v014a012]
[12] Ryan O’Donnell and Karl Wimmer: Approximation by DNF: Examples and counterexamples. In Proc. 34th Internat. Colloq. on Automata, Languages and Programming (ICALP’07), pp. 195–206. Springer, 2007. [doi:10.1007/978-3-540-73420-8_19]
[13] Alexander Alexandrovich Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987. Russian original in Mat. Zametki 41(4), 1987, 598–607. [doi:10.1007/BF01137685]
[14] Benjamin Rossman: The average sensitivity of bounded-depth formulas. Comput. Complexity, 27(2):209–223, 2018. Preliminary version in FOCS’15. [doi:10.1007/s00037-017-0156-0, arXiv:1508.07677]
[15] Petr Savický and Alan R. Woods: The number of Boolean functions computed by formulas of a given size. Random Structures Algorithms, 13(3–4):349–382, 2000. [doi:10.1002/(SICI)1098-2418(199810/12)13:3/4¡349::AID-RSA9¿3.0.CO;2-V]
[16] 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]
[17] 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]
[18] Mario Szegedy: Algebraic Methods in Lower Bounds for Computational Models with Limited Communication. Ph. D. thesis, University of Chicago, 1989. Available at advisor’s home page.
[19] Leslie G. Valiant: Short monotone formulae for the majority function. J. Algorithms, 5(3):363–366, 1984. [doi:10.1016/0196-6774(84)90016-6]