0368.4159 Seminar on Derandomization

CS dept, Tel-Aviv University, Fall 2016

Our first meeting is on 28/2/16, 15:00 at Orenstein 111.

Lecture Sunday, 15:00-17:00, Orenstein 111

Instructor Amnon Ta-Shma | Schreiber 127 | 5364

Open for Undergrad and grad students.

Grading policy

Paper presentation and participation in class.

List of suggested papers

· Bipartite Perfect Matching is in quasi-NC

· Perfect Bipartite matching in pseudo-deterministic RNC

· List decoding RS codes
Decoding Reed-Solomon codes beyond the error-correction diameter. Also, in:
Madhu Sudan’s lecture notes, Lecture 12.
Chapter 13 of Essential coding theory by Guruswami, Rudra and Sudan.

· Better list decoding for RS codes: The method of multiplicities
Improved decoding of Reed-Solomon and algebraic-geometry codes. Also, in:
Madhu Sudan’s lecture notes, Lecture 13.
Chapter 13 of Essential coding theory by Guruswami, Rudra and Sudan.
This lecture should include a presentation of Hasse derivatives which can be found, e.g., in Section 2 here.

· Parvaresh Vardy codes
Correcting errors beyond the Guruswami-Sudan radius in polynomial time. Also, in:
Lectures 15 and 16 in Madhu Sudan’s lecture notes.

· The folded RS code: Achieving List Decoding Capacity Using Folded Reed-Solomon Codes. Also, in:
Chapter 14 of Essential coding theory by Guruswami, Rudra and Sudan.

· Unbalanced Expanders and Randomness Extractors

· On the size of Kakeya sets in finite fields

· Dvir-Wigderson mergers: Kakeya Sets, New Mergers, and Old Extractors, Section 5 of Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.

· Proving a variant of Weil’s bound using the Stepanov method: Chapter 8 of Partial Derivatives in Arithmetic Complexity and Beyond.

· An Exposition of Bourgain’s 2-Source Extractor (unscheduled).

· Communication is bounded by root of rank (unscheduled).

· Pseudo-random generators for all hardnesses (unscheduled).

Schedule

Date	Class Topic	Lecturer	Supplementary Material
Feb. 28	Exposition	Amnon
March 6	Bipartite perfect matching is in quasi-NC	Ron, Eliran, Alon	Presentation
March 13	Bipartite perfect matching is in quasi-NC
March 20	Bipartite perfect matching is in quasi-NC
March 27	List decoding RS codes, Better list decoding for RS codes	Elinor, Dana, Matan	RS – Error correcting
April 3			RS – List decoding
April 10			RS – Better List decoding
May 1	Parvaresh-Vardy codes	Guy	Presentation
May 8	Folded RS codes	Or
May 15	Unbalanced expanders and randomness extractors	Nir
May 22	On the size of Kakeya sets in finite fields	Omer
May 29	Dvir-Wigderson mergers	Aviv	Presentation
June 5	Proving a variant of Weil’s bound using the Stepanov method	Grisha