CSE 290-I, Reading Seminar on Pseudo-Randomness, Winter 2025

Pseudo-randomness is a ubitiquous area of study. An object is called "pseudo-random" if it satisfies certain properties that truly random objects satisfy. The study of this random-like behavior has many applications in computer science and mathematics. In this reading seminar, we will explore various aspects of pseudo-randomness and its applications.

Instructors:

Professor: Shachar Lovett, email: slovett@ucsd.edu

Class Times

Mondays 11:00-11:50am, Computer Science building (EBU3B), room 4258

Grading

Grades will be based on student presentations.

Reading list

This is a non-comprehensive list of some books on pseudo-randomness. You can choose some topics from them, or any other related topic.

Pseudorandomness, by Salil Vadhan.
A Primer on Pseudorandom Generators, by Oded Goldreich.
Pairwise Independence and Derandomization, by Mike Luby and Avi Wigderson.
Pseudorandomness and Cryptographic Applications, by Mike Luby.

Schedule

Date	Topic	Speaker(s)
1/6/25	Dense model theorems	Anthony Ostuni
1/13/25	No class
1/20/25	No class (Martin Luther King, Jr. Holiday)
1/27/25	Basic derandomization techniques	Tianyi Zheng
2/3/25	No class (meta-complexity workshop)
2/10/25	Pairwise independence	Eric Binnendyk
2/17/25	No class (Presidents' Day Holiday)
2/24/25	Expander graphs	Matthew Cho and Finn Southerland
3/3/25	BPL in P and catalytic space	Farzan Byramji
3/10/25	Pseudorandom Quantum States	Haemanth Velmurugan and Zihan Hao