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 |