home

CSE 598A Sublinear Algorithms Spring 2012

Instructor: Sofya Raskhodnikova

Course Webpage: http://www.cse.psu.edu/~sofya/sublinear598/


Scribing

Instructions:

  • Sign up for scribing lectures by updating the table below with your name corresponding to the lecture you are scribing. (You may have to add a new entry/row altogether.)
  • The latex template for scribing lectures can be found on the course webpage under the heading "Lecture Notes".
  • File Naming: Please name the main file lecture<num>.tex and their auxiliary files (e.g., with pictures) with names starting from "lecture<num>-".
  • Uploading Lecture Notes: Once lectures have been scribed in latex, upload the finished lecture notes against your entry in the table below. Also, upload the source files (that is, latex files and auxiliary files such as pictures) by creating a zip file and add it to the corresponding entry in the table.
    • How to upload and add link: While in "Edit" mode, click "Insert Images and Files" icon. Click the Upload files button to upload your file(s) if you have not already uploaded your files to the wiki. In the "Click To" drop-down menu, select "Link to file". Locate your file and click to add its link. The link to the corresponding file will get added where the cursor is at the time. For example, adding file "lecture1.pdf", will create the link: lecture1.pdf. Rename the link appropriately (PDF/ZIP) by taking the cursor to the linked text and renaming it. While renaming be careful that the link should remain a link and not become plain-text. Also, check that the link works after renaming it. (Renaming to PDF/ZIP is done for better formatting of the table.)

Sign up:

Lec
Date
Topic
Scribe
Notes
Source
1
Tu, Jan 10
Introduction. Basic models for sublinear-time computation. Simple examples of sublinear algorithms.
Madhav Jha
PDF
ZIP
2
Th, Jan 12
Testing if a list is sorted/Lipschitz, if a function is monotone
Madhav Jha
PDF
ZIP
3
Tu, Jan 17
Testing connectedness and approximating MST weight
Sofya Raskhodnikova
PDF
ZIP
4
Th, Jan 19
Background on probability
Dragos Nistor
PDF
ZIP
5
Tu, Jan 24
Methods for proving lower bounds: Yao's principle.
Youngtae Youn
PDF
ZIP
6
Th, Jan 26
Methods for proving lower bounds: communication complexity. Other models of sublinear time/space computation.
Ishan Behoora
PDF
RAR
7
Tu, Jan 31
Dense graphs: testing bipartiteness
Ye
PDF
ZIP
8
Th, Feb 2
Dense graphs: approximating Max-Cut
Sandeep
See
Lec 9
9
Tu, Feb 6
Finish approximating Max-Cut
Kashyap Dixit
PDF
RAR
10
Th, Feb 8
Testing triangle freeness; regularity lemma
Megan Heysham
PDF
ZIP
11
Tu, Feb 14
Proof of triangle removal lemma
Huiwen Yu
PDF
ZIP
12
Th, Feb 16
Dense graphs: lower bound for testing triangle-freeness.
Dragos Nistor
PDF
ZIP
13
Th, Feb 23
In class problem solving: adaptivity in the dense-graph model
Madhav Jha
PDF
ZIP
14
Tu, Feb 28
Approximating Average Degree
Kashyap Dixit
PDF
ZIP
15
Th, Mar 1
Approximating Vertex Cover and distributed algorithms
Grigory Yaroslavtsev
See
Lec 16
16
Tu, Mar 13
Approximating Vertex Cover and distributed algorithms
Grigory Yaroslavtsev
PDF
ZIP
17
Th, Mar 15
Testing monotonicity of functions on hypergrids: Range Reduction
Youngtae Youn
PDF
ZIP
18
Tu, Mar 20
Testing monotonicity of functions on hypergrids: Dimension Reduction
Fang Song
PDF
ZIP
19
Th, Mar 22
Monotonicity testing on general posets
Ye
PDF
ZIP
20
Tu, Mar 27
Lower bounds for monotonicity testing on general posets
Youngtae Youn
PDF
TeX
21
Th, Mar 29
Lower bounds for monotonicity testing on general posets
Megan Heysham
PDF
ZIP
22
Tu, Apr 3
Testing monotonicity of boolean functions on hypergrids
Grigory Yaroslavtsev
See
Lec 23
23
Th, Apr 5
Testing monotonicity of boolean functions on hypergrids
Dragos Nistor
PDF
ZIP
24
Tu, Apr 10
Resolution of monotonicity (and Lipschitz) testing conjectures
Kashyap Dixit


25
Th, Apr 12
Talk by Avrim Blum: Active (and Passive) Property Testing



26
Tu, Apr 17
Testing linearity of functions. (slides )