Variable Influences in Conjunctive Normal Forms

DOI10.1007/978-3-642-02777-2_12zbMath1247.94075OpenAlexW1577016621MaRDI QIDQ3637162

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

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

Related Items (4)

Approximating Boolean Functions with Depth-2 Circuits ⋮ Unnamed Item ⋮ On extremal \(k\)-CNF formulas ⋮ Criticality of regular formulas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average sensitivity of bounded-depth circuits
• NP-completeness of some problems concerning voting games
• On the degree of Boolean functions as real polynomials
• A slight sharpening of LMN
• Faster algorithms for computing power indices in weighted voting games
• Counting truth assignments of formulas of bounded tree-width or clique-width
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Constant depth circuits, Fourier transform, and learnability
• Thresholds and Expectation Thresholds
• A fast deterministic algorithm for formulas that have many satisfying assignments
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation by DNF: Examples and Counterexamples
• NP-completeness for calculating power indices of weighted majority games
• On the complexity of \(k\)-SAT

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