Approximation algorithm for DNF under distributions with limited independence
From MaRDI portal
Publication:675867
DOI10.1007/BF02679448zbMATH Open0870.68085OpenAlexW2055561179MaRDI QIDQ675867FDOQ675867
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
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
- Title not available (Why is that?)
- The complexity of computing the permanent
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Approximate inclusion-exclusion
- On construction of \(k\)-wise independent random variables
- Constructing small sample spaces satisfying given constraints
Cited In (1)
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)
