0368.4622 Seminar in derandomization

CS dept, Tel-Aviv University, Spring 2018

 

We meet at Orenstein 110.


 

 

 


 

Date

Class Topic

Lecturer

Links

1

February 28

Presenting the papers

-

 

2

March 7

The NW generator

 

[NW94]

3

March 14

List decoding RS codes

[Sud97, GRS15]

4

March 28

Trevisans extractor

[Tre01]

5

April 4

Worst-case to Avg-case reduction for MinKT

[Hir18]

6

April 11

Worst-case to Avg-case reduction for PSPACE

[STV01]

7

Monday

April 15

Avg-Case complexity for NP. Impagliazzos five worlds.

[BT06a], [Imp95]

8

May 2

No black-box worst-case to Avg-case reductions for NP

[BT06a],[FF?]

9

May 16

Hardness amplification for NP

[ODo04]

10

May 23

Curve Samplers

[DW11]

11

May 30

The Shaltiel-Umans Extractor

[SU05]

12

June 6

The INW PRG, and the BCG pseudo-random pseudo-generator

?

[INW],[BCG]

13

June 13

 

 

 

 

 

Lecture

Thursday, 15:00-17:00, Orenstein 110

Instructor

Amnon Ta-Shma | Schreiber 127 | 5364

 

Open for Undergrad and grad students.

Grading policy Based on presentation

 

 

 

 

 

 

Tentative Syllabus

 

Below is a tentative list of papers for the seminar. There are more papers then meetings, and you can choose those papers that you like most (or are interested in most). Some papers can be taken in pairs.

 

Hardness vs. Randomness

1. The NW generator [NW94].

2. List decoding RS codes [Sud97, GRS15].

3. Worst-case to average case reduction for PSPACE [STV01].

 

Average-case Hardness

4. Background and Definitions [BT06a, BT06b].

5. Negative results for Black-box worst-case to average-case reductions for NP [BT06a, BT06b].

6. Worst-case to average-case reduction for MINKT [Hir18].

7. Impagliazzo five worlds [Imp95].

8. The easy witness method [IKW02].

9. Hardness amplification within NP [OD04].

 

Extractors, coding, PRG

 

10. Trevisans extractor [Tre01].

11. The SU extractor [SU05].

12. The Umans PRG [Uma02].

13. The beautiful curve mergers [DW11].

14. Subspace Evasive Sets [DL12].

15. Arithmetic Hardness vs. Randomness [KI04, Section 7].

16. A Welch-Berlekamp Like Algorithm for Decoding Gabidulin Codes, [Loi06].

 

 

Space-bounded PRG

17. Pseudorandom Generators from Polarizing Random Walks [CHHL18].

18. Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates [CHLT18].

19. Bounding the Fourier spectrum of small width branching programs [CHRT18].

 

Miscellaneous

20. Constructive proofs of concentration bounds [IK10].

 

 

References

[BT06a] Andrej Bogdanov and Luca Trevisan. Average-case complexity. Foundations and Trends in Theoretical Computer Science, 2(1):1106, 2006.

[BT06b] Andrej Bogdanov and Luca Trevisan. Average-case complexity. arXiv preprint cs/0606037, 2006.

[CHHL18] Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudo- random generators from polarizing random walks. In LIPIcs-Leibniz International Pro- ceedings in Informatics, volume 102. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[CHLT18] EshanChattopadhyay,PooyaHatami,ShacharLovett,andAvishayTal.Pseudorandom generators from the second fourier level and applications to ac0 with parity gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[CHRT18] Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal. Improved pseudorandomness for unordered branching programs through local monotonicity. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 363375. ACM, 2018.

[DL12] Zeev Dvir and Shachar Lovett. Subspace evasive sets. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 351358. ACM, 2012.

[DW11] Zeev Dvir and Avi Wigderson. Kakeya sets, new mergers, and old extractors. SIAM Journal on Computing, 40(3):778792, 2011.

[GRS15] Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential Coding Theory. 2015. Available at http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/ book.

[Hir18] Shuichi Hirahara. Non-black-box worst-case to average-case reductions within np. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 247258. IEEE, 2018.

[IK10] Russell Impagliazzo and Valentine Kabanets. Constructive proofs of concentration bounds. In Approximation, Randomization, and Combinatorial Optimization. Algo- rithms and Techniques, pages 617631. Springer, 2010.

[IKW02] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672694, 2002.

[Imp95] Russell Impagliazzo. A personal view of average-case complexity. In Structure in Com- plexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE, pages 134147. IEEE, 1995.

[KI04] Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):146, 2004.

[Loi06] Pierre Loidreau. A welchberlekamp like algorithm for decoding gabidulin codes. In Coding and cryptography, pages 3645. Springer, 2006.

[NW94] Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of computer and System Sciences, 49(2):149167, 1994.

[OD04] Ryan ODonnell. Hardness amplification within np. Journal of Computer and System Sciences, 69(1):6894, 2004.

[STV01] Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the xor lemma. Journal of Computer and System Sciences, 62(2):236266, 2001.

[SU05] Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM (JACM), 52(2):172216, 2005.

[Sud97] Madhu Sudan. Decoding of reed solomon codes beyond the error-correction bound. Journal of complexity, 13(1):180193, 1997.

[Tre01] Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM, 48(4):860879, 2001.

[Uma02] Christopher Umans. Pseudo-random generators for all hardnesses. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC 02, pages 627634, New York, NY, USA, 2002. ACM.