4 papers
Better Bounds for Frequency Moments in Random-Order Streams
Alexandr Andoni, Andrew McGregor, Krzysztof Onak +1
Estimating frequency moments of data streams is a very well studied problem and tight bounds are known on the amount of space that is necessary and sufficient when the stream is ad…
Sorting and Selection with Random Costs
Stanislav Angelov, Keshav Kunal, Andrew McGregor
There is a growing body of work on sorting and selection in models other than the unit-cost comparison model. This work is the first treatment of a natural stochastic variant of th…
On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
Andrew McGregor, Olgica Milenkovic
We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) code…
Estimating Aggregate Properties on Probabilistic Streams
Andrew McGregor, S. Muthukrishnan
The probabilistic-stream model was introduced by Jayram et al. \cite{JKV07}. It is a generalization of the data stream model that is suited to handling ``probabilistic'' data where…