Theses most similar to Constant time algorithms in sparse graph model (Nguyen, Huy Ngo; 2010) read it

Probabilistic methods in combinatorial and stochastic optimization

Vondrák, Jan, 1974- (2005)

  • Advisor: Michel Goemans
  • Department of Mathematics
Read it

Approximate nearest neighbor problem in high dimensions

Andoni, Alexandr (2005)

  • Advisor: Piotr Indyk
  • Department of Electrical Engineering and Computer Science
Read it

Interactive proof system variants and approximation algorithms for optical networks

Sundaram, Ravi, 1968- (1996)

  • Advisor: Michael Sipser
  • Department of Electrical Engineering and Computer Science
Read it

Matchings, matroids and submodular functions

Harvey, Nicholas James Alexander (2008)

  • Advisor: Michel Goemans
  • Department of Electrical Engineering and Computer Science
Read it

New sublinear methods in the struggle against classical problems

Onak, Krzysztof (Krzysztof Piotr) (2010)

  • Advisor: Ronitt Rubinfeld
  • Department of Electrical Engineering and Computer Science
Read it

From graphs to matrices, and back : new techniques for graph algorithms

Mądry, Aleksander (2011)

  • Advisors: Jonathan A. Kelner; Michel Goemans
  • Department of Electrical Engineering and Computer Science
Read it

Local computation algorithms for graphs of non-constant degrees

Yodpinyanee, Anak (2014)

  • Advisor: Ronitt Rubinfeld
  • Department of Electrical Engineering and Computer Science
Read it

LP/SDP hierarchy lower bounds for decoding random LDPC codes

Ghazi, Badih (2015)

  • Advisor: Madhu Sudan
  • Department of Electrical Engineering and Computer Science
Read it

Sublinear-time algorithms for counting star subgraphs with applications to join selectivity estimation

Peebles, John Lee Thompson, Jr (2016)

  • Advisors: Jon Kelne; Ronitt Rubinfeld
  • Department of Electrical Engineering and Computer Science
Read it

Computational metric embeddings

Sidiropoulos, Anastasios (2008)

  • Advisor: Piotr Indyk
  • Department of Electrical Engineering and Computer Science
Read it