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

Trevisan’s 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. Impagliazzo’s 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

âåø

[O’Do04]

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. Impagliazz’o five worlds [Imp95].


8. The easy witness method [IKW02].


9. Hardness amplification within NP [O’D04].

 

Extractors, coding, PRG

 

10. Trevisan’s 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):1–106, 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 363–375. 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 351–358. ACM, 2012.

[DW11] Zeev Dvir and Avi Wigderson. Kakeya sets, new mergers, and old extractors. SIAM Journal on Computing, 40(3):778–792, 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 247–258. IEEE, 2018.

[IK10] Russell Impagliazzo and Valentine Kabanets. Constructive proofs of concentration bounds. In Approximation, Randomization, and Combinatorial Optimization. Algo- rithms and Techniques, pages 617–631. 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):672–694, 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 134–147. IEEE, 1995.

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

[Loi06] Pierre Loidreau. A welch–berlekamp like algorithm for decoding gabidulin codes. In Coding and cryptography, pages 36–45. Springer, 2006.

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

[O’D04] Ryan O’Donnell. Hardness amplification within np. Journal of Computer and System Sciences, 69(1):68–94, 2004.

[STV01] Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the xor lemma. Journal of Computer and System Sciences, 62(2):236–266, 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):172–216, 2005.

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

[Tre01] Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM, 48(4):860–879, 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 627–634, New York, NY, USA, 2002. ACM.