0368.4622 Seminar in derandomization

CS dept, Tel-Aviv University, Spring 2018


We meet at Orenstein 110.






Class Topic




February 28

Presenting the papers




March 7

The NW generator




March 14

List decoding RS codes

[Sud97, GRS15]


March 28

Trevisans extractor



April 4

Worst-case to Avg-case reduction for MinKT



April 11

Worst-case to Avg-case reduction for PSPACE




April 15

Avg-Case complexity for NP. Impagliazzos five worlds.

[BT06a], [Imp95]


May 2

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



May 16

Hardness amplification for NP



May 23

Curve Samplers



May 30

The Shaltiel-Umans Extractor



June 6

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




June 13







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


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].



20. Constructive proofs of concentration bounds [IK10].




[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.