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
| No. |
Date |
Topic(s)
Covered |
References |
| 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 |
| 2 |
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) |
[EKKRV00, DGLRRS99, GGLRS00] |
| 4 | 10 Nov 2021 | Testing if a Boolean function over the
Boolean hypercube is monotone (analysis), Introduction to Lp testing |
[DGLRRS99,
GGLRS00, BRY14] |
| 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 |
[BRY14] |
| 7 | 19 Nov 2021 | Introduction to streaming algorithms,
Reservoir sampling, Estimating the number of distinct elements in a stream |
[BJKST02] |
| 8 | 24 Nov 2021 | k-wise independent hash functions,
estimating the L2 norm of the frequency vector of a stream |
[AMS99] |
| 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] |
References
[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)
[DGLRRS99] 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