Tight bounds on the average sensitivity of k-CNF

DOI10.4086/TOC.2011.V007A004zbMATH Open1213.68416OpenAlexW2278710187MaRDI QIDQ3002829FDOQ3002829

Authors: Kazuyuki Amano 

Publication date: 24 May 2011

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

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

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

zbMATH Keywords

sensitivityinfluenceBoolean functionsconjunctive normal form

Mathematics Subject Classification ID

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

Cited In (13)

• Criticality of regular formulas
• Expander-based cryptography meets natural proofs
• Approximating Boolean Functions with Depth-2 Circuits
• 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
• The simplified weighted sum function and its average sensitivity

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)