Improved algorithms via approximations of probability distributions
From MaRDI portal
Publication:1582012
DOI10.1006/jcss.1999.1695zbMath0960.68172OpenAlexW1982618872MaRDI QIDQ1582012
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
Related Items (12)
Entropy, Randomization, Derandomization, and Discrepancy ⋮ Deterministic Massively Parallel Connectivity ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Deterministic parallel algorithms for bilinear objective functions ⋮ Bounded Independence Plus Noise Fools Products ⋮ Improved parallel approximation of a class of integer programming problems ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ Bounds and constructions for the star-discrepancy via \(\delta\)-covers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved parallel approximation of a class of integer programming problems
- Balancing vectors in the max norm
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- On the power of two-point based sampling
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Removing randomness in parallel computation without a processor penalty
- The probabilistic method yields deterministic parallel algorithms
- On a set of almost deterministic k-independent random variables
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Randomized algorithms and pseudorandom numbers
- 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
- RSA and Rabin Functions: Certain Parts are as Hard as the Whole
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Simple Constructions of Almost k-wise Independent Random Variables
- Simulating (log c n )-wise independence in NC
- Tight Bounds for the Maximum Acyclic Subgraph Problem
- The Fourth Moment Method
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- A Fast Derandomization Scheme and Its Applications
This page was built for publication: Improved algorithms via approximations of probability distributions
