Improved algorithms via approximations of probability distributions
From MaRDI portal
Publication:1582012
DOI10.1006/JCSS.1999.1695zbMATH Open0960.68172OpenAlexW1982618872MaRDI QIDQ1582012FDOQ1582012
Aravind Srinivasan, Pankaj Rohatgi, Suresh Chari
Publication date: 20 May 2001
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/1f0599fd25e508b112b1a5159f39bc13141a43c6
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Simple Constructions of Almost k-wise Independent Random Variables
- Balancing vectors in the max norm
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- 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
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Approximating hyper-rectangles: Learning and pseudorandom sets
- On a set of almost deterministic k-independent random variables
- On the power of two-point based sampling
- RSA and Rabin Functions: Certain Parts are as Hard as the Whole
- The Fourth Moment Method
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- Tight Bounds for the Maximum Acyclic Subgraph Problem
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Removing randomness in parallel computation without a processor penalty
- The probabilistic method yields deterministic parallel algorithms
- Simulating (log c n )-wise independence in NC
- A Fast Derandomization Scheme and Its Applications
- Randomized algorithms and pseudorandom numbers
- Improved parallel approximation of a class of integer programming problems
Cited In (17)
- Improving and estimating the accuracy of Strassen's algorithm
- Fourier bounds and pseudorandom generators for product tests
- Bounded Indistinguishability and the Complexity of Recovering Secrets
- Paradigms for Unconditional Pseudorandom Generators
- Some improvements to the Shenoy-Shafer and Hugin architectures for computing marginals
- Bounded Independence Plus Noise Fools Products
- Title not available (Why is that?)
- Optimization of algorithm estimation of certain probabilistic characteristics
- Title not available (Why is that?)
- Deterministic Massively Parallel Connectivity
- Title not available (Why is that?)
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Algorithms for imprecise probabilities
- Near-optimal pseudorandom generators for constant-depth read-once formulas
- Entropy, Randomization, Derandomization, and Discrepancy
- Deterministic parallel algorithms for bilinear objective functions
- Improved parallel approximation of a class of integer programming problems
Recommendations
- Small-Bias Probability Spaces: Efficient Constructions and Applications 👍 👎
- Efficient approximation of product distributions 👍 👎
- Improved algorithms via approximations of probability distributions (extended abstract) 👍 👎
- (De)randomized construction of small sample spaces in \(\mathcal{NC}\) 👍 👎
- MODp-tests, almost independence and small probability spaces 👍 👎
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)
