Variable Influences in Conjunctive Normal Forms
From MaRDI portal
Publication:3637162
DOI10.1007/978-3-642-02777-2_12zbMath1247.94075OpenAlexW1577016621MaRDI QIDQ3637162
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
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