On deterministic approximation of DNF
From MaRDI portal
Recommendations
- Approximation algorithm for DNF under distributions with limited independence
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- DNF sparsification and a faster deterministic counting algorithm
- An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs)
Cites work
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Approximate inclusion-exclusion
- Monte-Carlo approximation algorithms for enumeration problems
- Parity, circuits, and the polynomial-time hierarchy
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- The complexity of computing the permanent
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(21)- An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs)
- Paradigms for Unconditional Pseudorandom Generators
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- scientific article; zbMATH DE number 4047104 (Why is no real title available?)
- On limitations of structured (deterministic) DNNFs
- On the relationship between \(\varepsilon\)-biased random variables and \(\varepsilon\)-dependent random variables
- DNF sparsification and a faster deterministic counting algorithm
- On sparse approximations to randomized strategies and convex combinations
- scientific article; zbMATH DE number 7564405 (Why is no real title available?)
- Pseudorandom generators for combinatorial checkerboards
- Approximation algorithm for DNF under distributions with limited independence
- A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
- Counting solutions to polynomial systems via reductions
- Not all FPRASs are equal: demystifying FPRASs for DNF-counting
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- scientific article; zbMATH DE number 7650112 (Why is no real title available?)
- On polynomial approximations to \(\mathrm{AC}^0\)
- On DNF approximators for monotone Boolean functions
- scientific article; zbMATH DE number 7561310 (Why is no real title available?)
- On the probabilistic degree of OR over the reals
This page was built for publication: On deterministic approximation of DNF
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923857)
