4 papers
Sublinear Algorithms for MAXCUT and Correlation Clustering
Aditya Bhaskara, Samira Daruki, Suresh Venkatasubramanian
We study sublinear algorithms for two fundamental graph problems, MAXCUT and correlation clustering. Our focus is on constructing core-sets as well as developing streaming algorith…
Streaming Verification of Graph Properties
Amirali Abdullah, Samira Daruki, Chitradeep Dutta Roy +1
Streaming interactive proofs (SIPs) are a framework for outsourced computation. A computationally limited streaming client (the verifier) hands over a large data set to an untruste…
Streaming Verification in Data Analysis
Samira Daruki, Justin Thaler, Suresh Venkatasubramanian
Streaming interactive proofs (SIPs) are a framework to reason about outsourced computation, where a data owner (the verifier) outsources a computation to the cloud (the prover), bu…
Range Counting Coresets for Uncertain Data
Amirali Abdullah, Samira Daruki, Jeff M. Phillips
We study coresets for various types of range counting queries on uncertain data. In our model each uncertain point has a probability density describing its location, sometimes defi…