Improved algorithms via approximations of probability distributions
From MaRDI portal
Recommendations
- Improved algorithms via approximations of probability distributions (extended abstract)
- \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
- (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
- Efficient approximation of product distributions
- Small-Bias Probability Spaces: Efficient Constructions and Applications
Cites work
- scientific article; zbMATH DE number 4152425 (Why is no real title available?)
- scientific article; zbMATH DE number 1256637 (Why is no real title available?)
- scientific article; zbMATH DE number 1142306 (Why is no real title available?)
- scientific article; zbMATH DE number 1559538 (Why is no real title available?)
- scientific article; zbMATH DE number 4000052 (Why is no real title available?)
- A Fast Derandomization Scheme and Its Applications
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A fast parallel algorithm for the maximal independent set problem
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Balancing vectors in the max norm
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Improved parallel approximation of a class of integer programming problems
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- On a set of almost deterministic k-independent random variables
- On the power of two-point based sampling
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- RSA and Rabin Functions: Certain Parts are as Hard as the Whole
- Randomized algorithms and pseudorandom numbers
- Removing randomness in parallel computation without a processor penalty
- Simple Constructions of Almost k-wise Independent Random Variables
- Simulating (log c n )-wise independence in NC
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- The Fourth Moment Method
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- The probabilistic method yields deterministic parallel algorithms
- Tight Bounds for the Maximum Acyclic Subgraph Problem
Cited in
(19)- Paradigms for Unconditional Pseudorandom Generators
- More on bounded independence plus noise: pseudorandom generators for read-once polynomials
- scientific article; zbMATH DE number 1222826 (Why is no real title available?)
- Sample spaces with small bias on neighborhoods and error-correcting communication protocols
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Improved parallel approximation of a class of integer programming problems
- Improved algorithms via approximations of probability distributions (extended abstract)
- Bounded indistinguishability and the complexity of recovering secrets
- Algorithms for imprecise probabilities
- Deterministic parallel algorithms for bilinear objective functions
- Bounded independence plus noise fools products
- Entropy, Randomization, Derandomization, and Discrepancy
- Optimization of algorithm estimation of certain probabilistic characteristics
- Near-optimal pseudorandom generators for constant-depth read-once formulas
- scientific article; zbMATH DE number 7561734 (Why is no real title available?)
- \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
- Improving and estimating the accuracy of Strassen's algorithm
- Some improvements to the Shenoy-Shafer and Hugin architectures for computing marginals
- Fourier bounds and pseudorandom generators for product tests
This page was built for publication: Improved algorithms via approximations of probability distributions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582012)
