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 Notes
  • Jan. 15 2. Basic probability review Notes
  • Jan. 20 3. Testing triangle freeness PaperNotes
  • Jan. 22 4. Testing triangle freeness (contd) Notes
  • Jan. 27 5. Lower bounds for triangle freeness Notes
  • Jan 29 6. Lower bounds for testing trianglefreeness (contd)
  • Feb 3 7. Testing monotonicity Notes
  • Feb 5 8. Testing monotonicity (contd) Paper
  • Feb. 10 9. PAC learning. Density estimation Notes
  • Feb. 12 10. Learning transformed distributions PaperNotes
  • Feb. 17 11. Graph streaming. Streaming algorithms for VC Paper Notes
  • Feb. 19 12. Streaming algorithms for VC (contd).
  • Feb. 24 13. Approximate nearest neighbor search Paper Notes
  • Feb. 26 14. ANN (contd). Projects discussions.Notes
  • Mar 3 15. Sublinear-time algorithms for Min Vertex Cover Paper Notes
  • 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 Notes
  • 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.