123 citations · 366 across the 30 of their papers we have counts for
7 papers · 1 filter
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…
Sketching, Embedding, and Dimensionality Reduction for Information Spaces
Amirali Abdullah, Ravi Kumar, Andrew McGregor +2
Information distances like the Hellinger distance and the Jensen-Shannon divergence have deep roots in information theory and machine learning. They are used extensively in data an…
Rectangular Layouts and Contact Graphs
Adam L. Buchsbaum, Emden R. Gansner, Cecilia M. Procopiuc +1
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their…
Restricted Strip Covering and the Sensor Cover Problem
Adam L. Buchsbaum, Alon Efrat, Shaili Jain +2
Given a set of objects with durations (jobs) that cover a base region, can we schedule the jobs to maximize the duration the original region remains covered? We call this problem t…
Streaming and Sublinear Approximation of Entropy and Information Distances
Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian
In many problems in data mining and machine learning, data items that need to be clustered or classified are not points in a high-dimensional space, but are distributions (points o…