Variable Influences in Conjunctive Normal Forms

DOI10.1007/978-3-642-02777-2_12MaRDI QIDQ3637162zbMATH OpenOpenAlexFDO

Authors Patrick Traxler

Publication date 7 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02777-2_12

Mathematics Subject Classification ID

Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An upper bound for the relative influence of variables on Boolean functions
• Approximation of biased Boolean functions of small total influence by DNFs
• On the average sensitivity and density of k-CNF formulas
• The influence of variables in product spaces
• On the influences of variables on Boolean functions in product spaces

Cites work

• A fast deterministic algorithm for formulas that have many satisfying assignments
• A slight sharpening of LMN
• Approximation by DNF: Examples and Counterexamples
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Constant depth circuits, Fourier transform, and learnability
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Faster algorithms for computing power indices in weighted voting games
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• scientific article; zbMATH DE number 5485570 (Why is no real title available?)
• Model counting: a new stategy for obtaining good bounds
• NP-completeness for calculating power indices of weighted majority games
• NP-completeness of some problems concerning voting games
• On the complexity of k-SAT
• On the degree of Boolean functions as real polynomials
• The average sensitivity of bounded-depth circuits
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Thresholds and Expectation Thresholds

Cited in

(6)

• An upper bound for the relative influence of variables on Boolean functions
• On extremal \(k\)-CNF formulas
• On extremal k-CNF formulas
• Approximating Boolean functions with depth-2 circuits
• Approximation of biased Boolean functions of small total influence by DNFs
• Criticality of regular formulas

This page was built for publication: Variable Influences in Conjunctive Normal Forms

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