Approximation algorithm for DNF under distributions with limited independence

DOI10.1007/BF02679448zbMath0870.68085OpenAlexW2055561179MaRDI QIDQ675867

Kazuyuki Amano, Akira Maruoka

Publication date: 15 September 1997

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02679448

zbMATH Keywords

DNF formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• Approximate inclusion-exclusion
• On construction of k-wise independent random variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Constructing small sample spaces satisfying given constraints

This page was built for publication: Approximation algorithm for DNF under distributions with limited independence