Time and location: Tuesday/Thursday 1:00PM-2:15PM, 121 Earth And Engr Sci
Instructor:
Sofya Raskhodnikova
Office hours: Tuesdays, 2:30PM-3:30PM, IST 343F
CSE 565; STAT 318 or MATH 318
This course will cover the design and analysis of algorithms that are restricted to run in sublinear time. Such algorithms are typically randomized and produce only approximate answers. A characteristic feature of sublinear algorithms is that they do not have time to access the entire input. Therefore, input representation and the model for accessing the input play an important role. We will study different models appropriate for sublinear algorithms. The course will cover sublinear algorithms discovered in a variety of areas, including graph theory, algebra, geometry, image analysis and discrete mathematics, and introduce many techniques that are applied to analyzing sublinear algorithms.
Students will be evaluated based on class participation, solutions to about 4 homework assignments, taking lecture notes about 2-3 times per person, and the final project.
| Lec | Date | Topics | References | Reading/Homework |
|---|---|---|---|---|
| 1 | Tu, Aug 25 | Introduction. Basic models for sublinear-time computation. Simple examples of sublinear algorithms. (Slides for lectures 1 & 2 ) | RS96, GGR98, Ras03, EKKRV00, Fis04 | Ras03, Ras15 |
| Th, Aug 27 | No lecture; students are encouraged to attend the DIMACS workshop on sublinear algorithms | |||
| 2 | Tu, Sep 1 | Properties of lists and functions. Testing if a list is sorted/Lipschitz and if a function is monotone. (See slides posted for previous lecture.) | DGLRRS99, BGJRW09, Ras10, JR13 | |
| 3 | Th, Sep 3 | Testing a bounded-degree graph is connected. Approximating the number of connected components and MST weight. (Slides ) | GR02, CRT05 | Homework 1 out; HW template files: Sample Homework Solution (pdf), Sample Homework Solution (latex), Example HW image, HW class file |
| 4 | Tu, Sep 8 | Background on probability | Handouts on probability by Dana Ron and from MIT lecture and recitation | |
| 5 | Th, Sep 10 | Discussion of HW 1. Methods for proving lower bounds: Yao's principle. (Slides for lectures 5 & 6 ) | FLNRRS02 | |
| 6 | Tu, Sep 15 | Discussion of course projects. Yao's principle (see slides posted for previous lecture). | Homework 1 due | |
| Th, Sep 17 | No lecture | |||
| 7 | Tu, Sep 22 | Methods for proving lower bounds: communication complexity. (Slides for lectures 7 & 8 ) | BBM11 | First project meeting |
| 8 | Th, Sep 24 | Other models of sublinear time/space computation (see slides posted for previous lecture). Two-distribution version of Yao's Principle. | Project proposal due (10 am on Angel); Homework 2 out | |
| 9 | Tu, Sep 29 | Application of Yao's Principle: limits of nonadaptive algorithms in the bounded-degree model. | RS06 | |
| 10 | Th, Oct 1 | Dense graphs: testing bipartiteness. | GGR98, AK02 | |
| 11 | Tu, Oct 6 | Dense graphs: finish testing bipartiteness. | GGR98 | Homework 2 due (10am on Angel) |
| 12 | Th, Oct 8 | Image properties: Testing if an image is a half-plane under the uniform distribution. | BMR | |
| 13 | Tu, Oct 13 | Image properties: learning and testing convexity under the uniform distribution. | BMR | |
| 14 | Th, Oct 15 | Image properties: finish testing convexity under the uniform distribution. | ||
| 15 | Tu, Oct 20 | A connection between proper learning and testing. Image properties: adaptive convexity tester. | Alon02 | Project progress reports due (10am on Angel); second project meeting | 16 | Th, Oct 22 | Image properties: connectedness. | GR08 |
| 17-19 | Tu, Oct 27; Th, Oct 29; Tu, Nov 3 | Dense graphs: approximating max-cut. | GGR98 | |
| 20 | Th, Nov 5 | Testing dense graphs: discuss characterization. Testing triangle-freeness. Regularity lemma. | AFKS00 | |
| 21 | Tu, Nov 10 | Testing triangle-freeness. Triangle-removal lemma. | Homework 3 out | |
| 22 | Th, Nov 12 | Dense graphs: lower bound for testing triangle-freeness. | Alon02 | 23 | Tu, Nov 17 | Approximating graph parameters: average degree | GR08 | 24 | Th, Nov 19 | Approximating graph parameters | GR08 | HW3 due | 25 | Tu, Nov 24 | Testing properties of functions: linearity. (Slides ) | BLR93, BCHKS96 | 26 | Th, Nov 26 | Testing properties of functions: monotonicity and the Lipschitz property |
| 27 | Tu, Dec 1 | Testing properties of functions: monotonicity and the Lipschitz property | Project final reports due | |
| 28 | Th, Dec 3 | L_p-testing | ||
| 29 | Tu, Dec 8 | Final project presentations | ||
| 30 | Th, Dec 10 | Final project presentations |
Most papers from the list below can be downloaded from the Princeton archive or my webpage.
| RS96 | Ronitt Rubinfeld, Madhu Sudan, Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal of Computing 1996. |
| GGR98 | Oded Goldreich, Shafi Goldwasser, Dana Ron, Property Testing and its Connection to Learning and Approximation. Journal of ACM 1998, FOCS 1996. |
| Ras03 | Sofya Raskhodnikova, Approximate Testing of Visual Properties. RANDOM-APPROX 2003. |
| Ras15 | Sofya Raskhodnikova, Testing if an Array Is Sorted. Encyclopedia of Algorithms 2015. |
| RS06 | Sofya Raskhodnikova, Adam Smith A Note on Adaptivity in Testing Properties of Bounded Degree Graphs. Electronic Colloquium on Computational Complexity, Report No. 89, 2006. |
| EKKRV00 | Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan, Spot-Checkers. Journal of Computer System and Sciences 2000, STOC 1998. |
| Fis04 | Eldar Fischer, On the strength of comparisons in property testing. Information and Computation 2004. |
| DGLRRS99 | Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky, Improved Testing Algorithms for Monotonicity. RANDOM-APPROX 1999. |
| BFJRW09 | Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff, Transitive-Closure Spanners. SODA 2009. |
| Ras10 | Sofya Raskhodnikova, Transitive-Closure Spanners: a Survey. In O. Goldreich, editor, Property Testing, LNCS 6390, LNCS State-of-the-Art Surveys, Springer, Heidelberg, 167--196, 2010. |
| JR13 | Madhav Jha, Sofya Raskhodnikova, Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. SIAM Journal on Computing 2013, STOC 11. |
| GR02 | Oded Goldreich, Dana Ron, Property testing in bounded degree graphs. Algorithmica 2002, STOC 1997. |
| CRT05 | Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan, Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM Journal of Computing 2005, ICALP 2001. |
| FLNRRS02 | Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky Monotonicity Testing Over General Poset Domains. STOC 2002. |
| BBM11 | Eric Blais, Joshua Brody, Kevin Matulef, Property Testing Lower Bounds via Communication Complexity. CCC 2011. |
| AK02 | Noga Alon, Michael Krivelevich, Testing k-colorability. SIAM J. Discrete Math. 15 (2002), 211-227. |
| Alon02 | Noga Alon, Testing subgraphs in large graphs. Random Structures and Algorithms 21 (2002), 359-370. |
| AFKS02 | Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451-476. |
| GT03 | Oded Goldreich, Luca Trevisan, Three theorems regarding testing graph properties, Random Struct. Algorithms 23(1): 23-57 (2003) |
| GR08 | Oded Goldreich, Dan Ron, Approximating average parameters of graphs, Random Struct. Algorithms 32(4): 473-493 (2008) |
| PaRo07 | Michal Parnas, Dan Ron, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Theor. Comput. Sci., 381(1-3):183--196 (2007) |
| NO08 | Huy N. Nguyen and Krzysztof Onak, Constant-Time Approximation Algorithms via Local Improvements, FOCS (2008) |
| ORRR12 | Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld, A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size, In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1123--1131 (2012) |
| Ras99 | Sofya Raskhodnikova, Monotonicity Testing, Master's Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1999 |
| CS12 | Deeparnab Chakrabarty, C. Seshadhri Optimal bounds for monotonicity and Lipschitz testing over the hypercube. ECCC, TR12-030, 2012. |
| BBBY12 | Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang, Active Property Testing. Manuscript, 2012. |
| BLR93 | Manuel Blum, Michael Luby, Ronitt Rubinfeld, Self-Testing/Correcting with Applications to Numerical Problems. Journal of Computer System and Sciences 1993, STOC 1990. |
| BCHKS96 | Linearity testing in characteristic two. IEEE Transactions on Information Theory, Vol. 42, No. 6, pp. 1781--1795, 1996, FOCS 95. |
