Sublinear Algorithms

As the sizes of datasets grow to enormous proportions,  there is a need for analyzing data with sublinear constraints -- that is, for the design of algorithms which require only sublinear time, space, measurements and/or samples.    Our work has designed sublinear algorithms for estimating parameters of graphs, combinatorial objects, functions and distributions. 

Faculty:  Costis Daskalakis, Piotr Indyk, Mohsen Ghaffari, Ronitt Rubinfeld

Postdocs:  Talya Eden

Students:  Amartya Shankha Biswas, Justin Chen, Jane Lange, Shyam Narayanan, 

Sandeep Silwal, Nicholas Schiefer, Arsen Vasilyan

 
Alumni:
PhD: Funda Ergun, S. Ravi Kumar, Tugkan Batu, Kevin Matulef, Krzysztof Onak, Arnab Bhattacharyya, Ning Xie, Reut Levi, Badih Ghazi, Themis Gouleakis, Anak Yodpinyanee, Pritish Kamath, John Peebles, Maryam Aliakbarpour
Postdocs: Shivani Agarwal, Eric Blais, Irit Dinur, Edlar Fischer, Tali Kaufman, Slobodan Mitrovic, Kobbi Nissim, Ning Xie
 

 

, , :
Sampling Multiple Edges Efficiently. APPROX-RANDOM : 51:1-51:15

, :
Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples. ITCS : 28:1-28:34

, , :
Local Access to Huge Random Objects Through Partial Sampling. ITCS : 27:1-27:65

, , , :
Improved Local Computation Algorithm for Set Cover via Sparsification. SODA : 2993-3011

 

 

 

MIFODS workshop on Sublinear algorithms, local algorithms and robust statistics (June 2018)