Tight Bounds on the Average Sensitivity of k-CNF
Theory of Computing, Volume 7(4), pp. 45-48, 2011
Bibliography with links to cited articles
[1] Ravi B. Boppana: The average sensitivity of bounded-depth circuits. Inform. Process. Lett., 63(5):257–261, 1997. [doi:10.1016/S0020-0190(97)00131-2]
[2] Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi: The complexity of unique k-SAT: An isolation lemma for k-CNFs. J. Comput. System Sci., 74(3):386–393, 2008. (Conference version in CCC ’03, pp. 135–141, 2003). [doi:10.1016/j.jcss.2007.06.015]
[3] Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Number 1 in Graduate Surveys. Theory of Computing Library, 2008. [doi:10.4086/toc.gs.2008.001]
[4] Ehud Friedgut: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998. [doi:10.1007/PL00009809]
[5] Nathan Linial, Yishay Mansour, and Noam Nisan: Constant depth circuits, Fourier transform and learnability. J. ACM, 40(3):607–620, 1993. [doi:10.1145/174130.174138]
[6] Ryan O’Donnell: The lecture notes of the course “analysis of Boolean Functions”: Lecture 29: Open problems. http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture29.pdf, 2007.
[7] Ryan O’Donnell: Some topics in analysis of Boolean functions. In Proc. 40th STOC, pp. 569–578. ACM Press, 2008. [doi:10.1145/1374376.1374458]
[8] Ramamohan Paturi, Pavel Pudlák, and Francis Zane: Satisfiability coding lemma. Chicago Journal of Theoretical Computer Science, 1999(115):1–18, 1999. (Conference version in FOCS ’97, pp. 566–574, 1997). [doi:10.4086/cjtcs.1999.011]
[9] Patrick Traxler: Variable influences in conjunctive normal forms. In Proc. 12th Internat. Conf. on Theory and Appl. of Satisfiability (SAT’09), volume 5584 of LNCS, pp. 101–113. Springer, 2009. [doi:10.1007/978-3-642-02777-2_12]