Columbia Undergraduate Learning Seminar in Theoretical Computer Science

Summer 2022

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.

Randomness in Computation

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]

Interactive Zero-Knowledge Proofs and Cryptography

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'dNP 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

Previous Semesters

Spring 2022

Fall 2021

Summer 2021