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
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
[引用]Talya Eden ,Saleet Mossel ,Ronitt Rubinfeld:
Sampling Multiple Edges Efficiently.APPROX-RANDOM2021:51:1-51:15
Ronitt Rubinfeld,Arsen Vasilyan :
Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples.ITCS2020:28:1-28:34
Amartya Shankha Biswas ,Ronitt Rubinfeld,Anak Yodpinyanee :
Local Access to Huge Random Objects Through Partial Sampling.ITCS2020:27:1-27:65
Christoph Grunau ,Slobodan Mitrovic ,Ronitt Rubinfeld,Ali Vakilian :
Improved Local Computation Algorithm for Set Cover via Sparsification.SODA2020:2993-3011 [引用] [引用] [引用] [引用]MIFODS workshop on Sublinear algorithms, local algorithms and robust statistics (June 2018)
[引用]https://mifods.mit.edu/sublinear.php
Course notes:
6.889 Sublinear Time Algorithms Fall 2020
https://people.csail.mit.edu/ronitt/COURSE/F20/index.html