On deterministic approximation of DNF
From MaRDI portal
Publication:1923857
DOI10.1007/BF01940873zbMath0857.68054OpenAlexW2114870555MaRDI QIDQ1923857
Michael Luby, Boban Velickovic
Publication date: 13 October 1996
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01940873
Related Items (13)
On the relationship between \(\varepsilon\)-biased random variables and \(\varepsilon\)-dependent random variables ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ On the probabilistic degree of OR over the reals ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ On polynomial approximations to AC ⋮ Not all FPRASs are equal: demystifying FPRASs for DNF-counting ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On sparse approximations to randomized strategies and convex combinations
Cites Work
- The complexity of computing the permanent
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Approximate inclusion-exclusion
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Parity, circuits, and the polynomial-time hierarchy
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Monte-Carlo approximation algorithms for enumeration problems
This page was built for publication: On deterministic approximation of DNF
