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