DNF sparsification and a faster deterministic counting algorithm
From MaRDI portal
Publication:354649
DOI10.1007/s00037-013-0068-6zbMath1286.68230arXiv1205.3534OpenAlexW2153408986MaRDI QIDQ354649
Omer Reingold, Parikshit Gopalan, Raghu Meka
Publication date: 19 July 2013
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1205.3534
Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (16)
Quantified Derandomization: How to Find Water in the Ocean ⋮ Fooling Polytopes ⋮ Complexity theory. Abstracts from the workshop held November 11--17, 2012. ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ Amplification and Derandomization without Slowdown ⋮ Not all FPRASs are equal: demystifying FPRASs for DNF-counting ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Coding for Sunflowers ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Improved bounds for quantified derandomization of constant-depth circuits and polynomials ⋮ Monotone circuit lower bounds from robust sunflowers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Pseudorandom bits for constant depth circuits
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- Approximate inclusion-exclusion
- Boolean functions with low average sensitivity depend on few coordinates
- Hardness vs randomness
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- On deterministic approximation of DNF
- A Simple Proof of Bazzi’s Theorem
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Constant depth circuits, Fourier transform, and learnability
- Intersection Theorems for Systems of Sets
- Parity, circuits, and the polynomial-time hierarchy
- Polylogarithmic independence fools AC 0 circuits
- Improved Pseudorandom Generators for Depth 2 Circuits
- Polylogarithmic Independence Can Fool DNF Formulas
- Monte-Carlo approximation algorithms for enumeration problems
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Pseudorandom generators for combinatorial shapes
- Reducing the complexity of reductions
This page was built for publication: DNF sparsification and a faster deterministic counting algorithm
