Improved algorithms via approximations of probability distributions

DOI10.1006/JCSS.1999.1695zbMATH Open0960.68172OpenAlexW1982618872MaRDI QIDQ1582012FDOQ1582012

Authors: Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan 

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

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

zbMATH Keywords

probability distributionsmethod of conditional probabilities

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Distribution theory (60E99)

Cites Work

• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Simple Constructions of Almost k-wise Independent Random Variables
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

Cited In (20)

• Improving and estimating the accuracy of Strassen's algorithm
• Fourier bounds and pseudorandom generators for product tests
• \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
• Paradigms for Unconditional Pseudorandom Generators
• Some improvements to the Shenoy-Shafer and Hugin architectures for computing marginals
• Title not available (Why is that?)
• Optimization of algorithm estimation of certain probabilistic characteristics
• Deterministic Massively Parallel Connectivity
• Improved algorithms via approximations of probability distributions (extended abstract)
• Title not available (Why is that?)
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• Algorithms for imprecise probabilities
• Bounded independence plus noise fools products
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Sample spaces with small bias on neighborhoods and error-correcting communication protocols
• Entropy, Randomization, Derandomization, and Discrepancy
• Bounded indistinguishability and the complexity of recovering secrets
• Deterministic parallel algorithms for bilinear objective functions
• Improved parallel approximation of a class of integer programming problems

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)