During Summer 2022, we held two groups, each focused on a different topic within TCS. The groups were: Randomness in Computation and Interactive Zero-Knowledge Proofs. Each group was run by an undergraduate student organizer, and some groups had a graduate student mentor.
Please see the descriptions and tables below for a summary and the list of talks for each of the groups.
This was the fourth iteration of the TCS seminar. The seminar was run by Alex Lindenbaum.
Organizer: Alex and Ari.
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| June 15th | Randomized Algorithms, Las Vegas and Monte Carlo, Probability Basics | Alex | Randomized Algorithms Chap. 1 |
| June 22nd | Complexity of Randomized Algorithms | Ryan | Computational Complexity Chap. 7 [Arora-Barak] |
| June 29th | Markov Chains | Mark | Markov Chains and Mixing Times Chap. 1 [Levin-Peres-Wilmer] |
| July 20th | 2-SAT, Markov Chain Monte Carlo, S-T Connectivity with Random Walks | Tianqi | Probability and Computing Chap. 7 [Mizenmacher-Upfal] |
| July 27th | Primality Testing, PRIMES is in P | Ekene | Randomized Algorithms Chap. 7; [AKS'04] |
| August 3rd | Expander Graphs and S-T Connectivity is in LOGSPACE | Hongshuo | Pseudorandomness Chap. 4 [Vadhan]; O'Donnell Lecture 12 |
| August 10th | Pseudorandom Generators, P vs. BPP | Yicheng | A Primer on Pseudorandom Generators Chaps. 2, 3 [Goldreich] |
Organizer: Yunya. Graduate student mentor: Miranda.
Description: We explored interactive ZK-proofs and their applications. The first two to three weeks were a "crash course" on basic cryptography as well as interactive proof systems, and then we dived into ZK-proofs.
| Resource | Title | Link |
|---|---|---|
| Pass and Shelat | A Course in Cryptography | Link |
| Thaler | Proofs, Arguments, and Zero-Knowledge | Link |
| Lysyanskaya | Advanced Cryptography | Link |
| Date | Topic | Discussion Leader | Reading |
|---|---|---|---|
| June 19th | Crypto 101: Provable security, Shannon's Theorem, One Way Functions | Yunya | Pass and Shelat Chaps. 1, 2; Pass'09 Lecture |
| June 26th | Crypto 101: Indistinguishability, pseudorandom generators | Quintus | Pass and Shelat, Chap. 3 |
| July 3rd | Knowledge, interactive proofs, and argument systems | Ekene | Pass and Shelat, Chap. 4; Thaler, Chaps. 3, 4; Goldreich tutorial, Sec. 2 |
| July 10th | Interactive ZK proof: Introduction, definitions, properties | Luisa | Pass and Shelat, Chap. 4; Thaler, Chaps. 3, 4; Goldreich tutorial, Sec. 3; [GMR'89] |
| July 17th | Interactive ZK proof: properties cont'd—NP and ZK |
Goldreich tutorial, Sec. 3; [GMW'91] | |
| July 24th | Interactive ZK proof: complexity and lower bounds | [GK'90]; [Barak'08] | |
| July 31st | Interactive ZK proof: round complexity | [GK'95]; [FS'01]; [Katz'07] | |
| August 7th | Interactive ZK proof: sigma protocols and discrete-log based protocols | Thaler, Chap. 12; [Schnorr'90]; [Damgard'10] | |
| August 14th | Applications | Quintus | |
| August 28th | Applications | Jiahui |