Improved algorithms via approximations of probability distributions

DOI10.1006/jcss.1999.1695zbMath0960.68172MaRDI QIDQ1582012

Aravind Srinivasan, Suresh Chari, Pankaj Rohatgi

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

zbMATH Keywords

probability distributions; method of conditional probabilities

Mathematics Subject Classification ID

68W25: Approximation algorithms

60E99: Distribution theory

68W20: Randomized algorithms

Related Items

Entropy, Randomization, Derandomization, and Discrepancy, Improved parallel approximation of a class of integer programming problems, 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