Tight Bounds on the Average Sensitivity of k-CNF

by Kazuyuki Amano

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]