Sublinear Algorithms Nov-Dec 2021

Part II of Advanced Algorithms Sep-Dec 2021

This is the second part of the elective course titled Advanced Algorithms. The first part of Advanced Algorithms, taught by Prajakta Nimbhorkar, covered various aspects of designing and analyzing randomized algorithms. This second part will cover topics from the field of Sublinear Algorithms.

There is no textbook for the course. Lectures will be based on research papers, which are listed under the references section. Most of these papers can be downloaded from the respective authors' webpages or public open access repositories. We have also included a non-comprehensive list of courses on sublinear algorithms offered at other universities. 

Instructor: Nithin Varma

Lectures: 17:00 to 18:15 on Wednesdays and Fridays; Lectures will be online on Zoom. The Zoom link is posted on the Moodle page for the course.

Course Schedule

Topic(s) Covered
1 29 Oct 2021 Introduction to sublinear algorithms, Sublinear algorithm to
approximate the diameter of a set of points, Property testing
connectedness of graphs in the adjacency lists model
Dana Ron's notes on
property testing
3 Nov 2021
Testing algorithm for connectedness, Estimating the
number of connected components in a graph
[GR02], [CRT05]
3 5 Nov 2021 Testing if an array is sorted, Testing if a Boolean function
over the Boolean hypercube is monotone (tester)
4 10 Nov 2021 Testing if a Boolean function over the Boolean hypercube
is monotone (analysis), Introduction to Lp testing
5 12 Nov 2021 L1-testing if a real-valued function over [n]^d is monotone [BRY14]
6 17 Nov 2021 L1-testing if a real-valued function over [n]^d is
monotone, Work investment strategies
7 19 Nov 2021 Introduction to streaming algorithms, Reservoir sampling,
Estimating the number of distinct elements in a stream
8 24 Nov 2021 k-wise independent hash functions, estimating the L2 norm
of the frequency vector of a stream
9 26 Nov 2021 Analysis of the L2 norm estimation algorithm, Morris counter [AMS99, M78]
10 1 Dec 2021 Yao's Minimax Principle - I [Y77]
11 3 Dec 2021 Yao's Minimax Principle - II [Y77]
12 8 Dec 2021 Local Computation Algorithms (LCAs) [RTVX11]
13 10 Dec 2021 LCAs contd., LCA for Maximal Independent Set [RTVX11]
14 11 Dec 2021 Sublinear Algorithm for Vertex Coloring using Delta + 1 colors [ACK19]
15 13 Dec 2021 Sublinear Algorithm for Vertex Coloring using Delta + 1 colors [ACK19]


[CRT05] Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time.
SIAM J. Comput. 34(6): 1370-1379 (2005)

[GR02] Oded Goldreich, Dana Ron: Property Testing in Bounded Degree Graphs. Algorithmica 32(2): 302-343 (2002)

[EKKRV00] Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. J. Comput. Syst. Sci. 60(3): 717-751 (2000)

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky: Improved Testing Algorithms for Monotonicity. RANDOM-APPROX 1999: 97-108

[GGLRS00] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky: Testing Monotonicity. Comb. 20(3): 301-337 (2000)

[BRY14] Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev: Lp-testing. STOC 2014: 164-173

[BJKST02] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan: Counting Distinct Elements in a Data Stream. RANDOM 2002: 1-10

[AMS99] Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137-147 (1999)

[M78] Robert Morris (Bell Labs): Counting large numbers of events in small registers. Communications of the ACM (CACM). (1978)

[Y77] Andrew Yao: Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). FOCS 1977: 222-227

[RTVX11] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie: Fast Local Computation Algorithms. ICS 2011: 223-238

[ACK19] Sepehr Assadi, Yu Chen, Sanjeev Khanna: Sublinear Algorithms for (Δ + 1) Vertex Coloring. SODA 2019: 767-786

Other courses on Sublinear Algorithms