Approximation algorithm for DNF under distributions with limited independence

DOI10.1007/BF02679448MaRDI QIDQ675867zbMATH OpenOpenAlexFDO

Authors Kazuyuki Amano, A. 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)

Recommendations

• On deterministic approximation of DNF
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• On the complexity of approximating the independent set problem
• Exact learning of random DNF over the uniform distribution
• On the complexity of approximating the independent set problem (extended abstract)
• On learning random DNF formulas under the uniform distribution
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation of biased Boolean functions of small total influence by DNFs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• On the approximation resistance of a random predicate

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Approximate inclusion-exclusion
• Constructing small sample spaces satisfying given constraints
• On construction of \(k\)-wise independent random variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• The complexity of computing the permanent

Cited in

(1)

• Polylogarithmic independence can fool DNF formulas

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q675867)