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
(22)- Not all FPRASs are equal: demystifying FPRASs for DNF-counting
- Pseudorandom generators for combinatorial checkerboards
- On polynomial approximations to \(\mathrm{AC}^0\)
- scientific article; zbMATH DE number 7561310 (Why is no real title available?)
- scientific article; zbMATH DE number 4047104 (Why is no real title available?)
- Paradigms for Unconditional Pseudorandom Generators
- On sparse approximations to randomized strategies and convex combinations
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- scientific article; zbMATH DE number 7564405 (Why is no real title available?)
- A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
- Pseudorandom generators for unbounded-width permutation branching programs
- 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 the probabilistic degree of OR over the reals
- On the relationship between -biased random variables and -dependent random variables
- On DNF approximators for monotone Boolean functions
- DNF sparsification and a faster deterministic counting algorithm
- On limitations of structured (deterministic) DNNFs
- An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs)
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Counting solutions to polynomial systems via reductions
- Approximation algorithm for DNF under distributions with limited independence
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)
