CSE 597A Sublinear Algorithms Fall 2015

Instructor: Sofya Raskhodnikova

Course Webpage: http://www.cse.psu.edu/~sxr48/sublinear-course/



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".
  • You may refer to the lecture notes from the previous offering of the course. In case you rely on them while preparing your lecture notes, list the name of the scribe who drafted them, along with your name.
  • 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.)

Lec
Date
Topic
Scribe
Lecture Note
Source Files
4
Sep 8, 2015
Probability Background
Nithin M Varma
Lecture4.PDF
Lecture4.ZIP
5
Sep 10, 2015

Methods for proving lower bounds: Yao's principle.

Om Thakkar
Lecture5.PDF
Lecture5.ZIP
6
Sep 15, 2015

Om Thakkar


7
Sep 22, 2015
Methods for proving lower bounds: communication complexity
Ramesh Krishnan
Lecture7.PDF
Lecture7.ZIP
8
Sep 24,2015

Meiram Murzabulatov
Lecture8.PDF
Lecture8.ZIP
9
Sep 29, 2015

Haojun Sui


10
Oct 1, 2015
Dense Graphs: Testing Bipartiteness
Sofya
Lecture9.PDF

11
Oct 6, 2015
Testing Bipartiteness (continued)
Tao-yang Fu
Lecture11.PDF
Lecture11.ZIP
12
Oct 8, 2015
Testing half-plane property
Hui-Ju Hung
Lecture12.PDF
Lecture12.ZIP
13
Oct 13, 2015





14


Eunou Lee
Lecture13-14.PDF
Lecture13-14.zip
15
Tu, Oct 20
Approximating graph parameters: average degree
Tao-yang Fu
Lecture15.PDF
Lecture15.ZIP






17
Tue, Oct 27

Nai-Hui
Lecture17-19.pdf
Lecture17-19.zip






20
Nov 3, 2015




21
Nov 5, 2015
Testing Triangle freeness
Sofya


22
Nov 10, 2015
Testing Triangle freeness
Sofya
Lecture21-22.PDF

23
Nov 17, 2015

Lower Bound on Query Complexity for Testing Triangle freeness:
Behrend's theorem
Hongyuan


24
Nov 19, 2015
Lower Bound on Query Complexity for Testing Triangle freeness:
continue
Hongyuan
Lecture23-24.PDF
Lecture23-24.ZIP



Roksana
Lecture25
Lecture25.ZIP
26
Dec. 1, 2015
Lp-testing
Hui-Ju Hung
Lecture26.PDF
Lecture26.ZIP