463 citations · 1k across the 47 of their papers we have counts for
4 papers · 1 filter
When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
Nikhil Bansal, Anupam Gupta, Jian Li +3
Consider a random graph model where each possible edge is present independently with some probability . Given these probabilities, we want to build a large/heavy matching…
Data Stream Algorithms for Codeword Testing
Atri Rudra, Steve Uurtamo
Motivated by applications in storage systems and property testing, we study data stream algorithms for local testing and tolerant testing of codes. Ideally, we would like to know w…
When LP is the Cure for Your Matching Woes: Approximating Stochastic Matchings
Nikhil Bansal, Anupam Gupta, Viswanath Nagarajan +1
This results in this paper have been merged with the result in arXiv:1002.3763v1 The authors would like to withdraw this version. Please see arXiv:1008.5356v1 for the merged versio…
Two Theorems in List Decoding
Atri Rudra, Steve Uurtamo
We prove the following results concerning the list decoding of error-correcting codes: (i) We show that for \textit{any} code with a relative distance of (over a large enough a…