Tight bounds on the average sensitivity of k-CNF

DOI10.4086/TOC.2011.V007A004MaRDI QIDQ3002829zbMATH OpenOpenAlexFDO

Authors Kazuyuki Amano

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2011.v007a004

zbMATH Keywords

sensitivityinfluenceBoolean functionsconjunctive normal form

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On extremal \(k\)-CNF formulas
• On extremal \(k\)-CNF formulas
• On the average sensitivity and density of \(k\)-CNF formulas
• The average sensitivity of bounded-depth circuits
• The average sensitivity of bounded-depth formulas

Cited in

(15)

• The simplified weighted sum function and its average sensitivity
• Criticality of regular formulas
• Expander-based cryptography meets natural proofs
• The average sensitivity of bounded-depth circuits
• Pseudo-average block sensitivity equals average sensitivity
• The average sensitivity of square-freeness
• The average sensitivity of bounded-depth formulas
• DNF sparsification and a faster deterministic counting algorithm
• Minterm-transitive functions with asymptotically smallest block sensitivity
• On extremal \(k\)-CNF formulas
• On the average sensitivity and density of \(k\)-CNF formulas
• On extremal \(k\)-CNF formulas
• Boolean nested canalizing functions: a comprehensive analysis
• On the average sensitivity of the weighted sum function
• Approximating Boolean functions with depth-2 circuits

This page was built for publication: Tight bounds on the average sensitivity of k-CNF

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3002829)