On deterministic approximation of DNF

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

zbMATH Keywords

quasi-polynomial-time deterministic algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

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