CS590 Sublinear algorithms

Tu/Th 9-10:15 pm, Krannert Building G007

Instructor

Elena Grigorescu, elena-g purdue.edu

TA: Abram Magner, anmagner purdue.edu

Office Hours: upon appointment.

Announcements

Welcome to CS590 Sublinear algorithms!

Please sign up on Piazza. The lecture notes and other resources will be posted there.

Course description
Sublinear time algorithms allow one to read only a small fraction of the input. They play an important role in the design of algorithms for big data and are typically randomized algorithms generating approximate solutions. This course will introduce techniques for designing and analyzing sublinear time algorithms including combinatorial and graph algorithms, and algorithms for error-correcting codes and other algebraic objects. These algorithms provide extremely fast approximations for classical optimization problems and also for decision problems studied in the so-called property testing model.

Prerequisites: A course on discrete math and undergraduate algorithms.

Grading
  • 30% for class discussions and participation
  • 70% for the project (Instructions)
Schedule
  • Jan. 13 1. Intro to sublinear models
  • Jan. 15 2. Basic probability review
  • Jan. 20 3. Testing triangle freeness Paper
  • Jan. 22 4. Testing triangle freeness (contd)
  • Jan. 27 5. Lower bounds for triangle freeness
  • Jan 29 6. Lower bounds for testing trianglefreeness (contd)
  • Feb 3 7. Testing monotonicity
  • Feb 5 8. Testing monotonicity (contd) Paper
  • Feb. 10 9. PAC learning. Density estimation
  • Feb. 12 10. Learning transformed distributions Paper
  • Feb. 17 11. Graph streaming. Streaming algorithms for VC Paper
  • Feb. 19 12. Streaming algorithms for VC (contd).
  • Feb. 24 13. Approximate nearest neighbor search Paper
  • Feb. 26 14. ANN (contd). Projects discussions.
  • Mar 3 15. Sublinear-time algorithms for Min Vertex Cover Paper
  • Mar 5 16. Sublinear-time algorithms for Min VC (contd).
  • Mar. 10 17. Testing cluster structure
  • Mar. 12 18. Testing cluster structure (contd).
  • Mar. 17 Spring break.
  • Mar. 19 Spring break (contd)
  • Mar. 24 19. Streaming algorithms for sparse spanners Paper
  • Mar. 26 20. Streaming sparse spanners (contd.)
  • Mar 31 21. Count-Min Sketch Paper
  • Apr. 2 22 Count-Min Sketch (contd) Notes
  • Apr. 7 23 PAC Learnign and VC dimension
  • Apr. 9 24 Sublinear Algorithms for Modern Graph Analysis. Colloquium talk by Michael Kapralov
  • Apr. 14 25 Sample complexity via VC dimension
  • Apr. 16 26 Projects updates
  • Apr. 21 27 Projects updates
  • Apr. 23 28 Testing linearity. The Fourier analysis method.
  • Apr. 28 29 Locally testable/correctable/decodable codes.Connections to PCPs.
  • Apr 30 30 Local decoding of RM codes. Projects outcomes.