Sublinear Algorithms Workshop

MIT. Cambridge, MA. August 3-5, 2022 (summer school August 1-2)

Synopsis

With the emergence of big data, and the huge combinatorial objects that make up this data, there is a need for understanding data that is too large to store or view in its entirety. Determining the scope of what is possible to understand in such settings is a basic and fundamental endeavor, that has been addressed in multiple ways within the communities of statistics, mathematics, computer science, and information theory. Models that have been studied include: streaming algorithms, where big data streams by, and the algorithm has limited space in which to store information and intermediate computations; sketching algorithms, where the input is compressed (sketched) into a smaller domain in a way that certain operations can be supported on the sketches; compressive sensing algorithms, where a signal is recovered from noisy measurements; sublinear time algorithms, in which algorithms approximate a parameter of the data after viewing a miniscule fraction of the data; local algorithms that compute and make decisions on parts of the output considering only a portion of the input; property testing algorithms, in which a quick determination of what properties the data has must be made in sublinear time in the size of the data; and distribution property testing algorithms, in which properties of the distribution must be understood in time sublinear in the size of the sampled domain.

Program

The workshop will take place at MIT on August 3-5, 2022. We will also have a summer school August 1-2.

Current confirmed workshop speakers

  • Maryam Aliakbarpour (UMass Amherest)
  • Vincent Cohen-Addad (Google Research)
  • Elena Grigorescu (Purdue)
  • Michael Kapralov (EPFL)
  • Sanjeev Khanna (UPenn)
  • Sepideh Mahabadi (Microsoft Research)
  • Andrew McGregor (UMass Amherst)
  • C. Seshadhri (UC Santa Cruz)
  • Madhu Sudan (Harvard)
  • Erik Waingarten (UPenn)
  • David Woodruff (CMU)

Confirmed summer school speakers

  • Guy Bresler (MIT)
  • Sam Hopkins (MIT)
  • Michael Mitzenmacher (Harvard)
  • Jelani Nelson (UC Berkeley)
  • Ronitt Rubinfeld (MIT)

Organizers

  • Piotr Indyk (MIT)
  • Michael Mitzenmacher (Harvard)
  • Jelani Nelson (UC Berkeley)
  • Huy Nguyen (Northeastern)
  • Ronitt Rubinfeld (MIT)

Program

Day 1: Wednesday, August 3, 2022

Day 2: Thursday, August 4, 2022

Day 3: Friday, August 5, 2022

Please see the 2021 FODSI workshop on ML 4 Algorithms here.