CU Theory Student Seminar

We are meeting at 12:30pm every Tuesday in CSB 480. The organizers for this semester are Jason and Rashida.

when	topic	presenter	notes
9/19	Fiat-Shamir for Bounded-Depth Adversaries	Tianqi
9/26	The Fine-Grained Complexity of Dynamic Programming	Hantao
10/3	On the Pauli Spectrum of QAC0	Natalie
10/17	TBD	TBD
10/24	TBD	TBD
10/31	TBD	TBD
11/7	Production Networks Resilience: Cascading Failures, Power Laws and Optimal Interventions	Marios Papachristou
11/14	TBD	TBD
11/21	TBD	TBD
11/28	TBD	TBD
12/5	TBD	TBD
12/12	TBD	TBD
12/19	TBD	TBD

We are meeting at 2pm every Thursday in CSB 453. The organizers for this semester are Jason and Rashida.

when	topic	presenter	notes
1/26	Active Learning Polynomial Threshold Functions	Hantao
2/2	Revenue-optimal auctions: the classics	Jason	The framework of DSIC auctions with bids, dominant-strategy revelation principle, welfare and revenue maximization
2/9	Revenue-optimal auctions: the continuation of the classics	Jason	virtual valuation functions, the Bulow-Klemperer theorem
2/16	Recent developments in the complexity of computing a Tarski fixed point	Yuhao
2/23	Testing Convex Truncation	Shivam
3/2	Transfer Learning and Model Selection	Yasaman
3/9	Universal Learning for Multiclass Classification	Alkis Kalavasis
3/23	Contract Theory: Introduction and Robustness	Rashida
3/30	Semidefinite Programming in Discrepancy Theory	Shyamal
4/6	Online Convex Optimization with Unbounded Memory	Raunak Kumar
4/13	Matrix Chernoff bounds	Binghui
4/20	Model Theory and Proof Complexity	Oliver
4/27	Quantum Circuit Lower Bounds	Natalie
5/4	Information Complexity	Yuval
5/11	A complexity theory for quantum problems	John
5/18	An effective description of the roots of bivariates mod pk and the related Igusa's local zeta function	Sayak

We'll be meeting at 12:30pm every Thursday in CSB 488. The organizers for this semester are Miranda, Shivam, and Jason.

when	topic	presenter	notes
10/4	Communication and Query Complexity of Bipartite Matching	Yuval
10/11	Cut Query Algorithms Using Star Contraction	Yuval
10/18	Secretary Problems via Linear Programming	Shyamal
10/25	Boolean Fourier Analysis and Mirror Descent	Manolis
11/1	An Optimal Algorithm for Certifying Monotone Functions	Naren Manoj
11/8	Log Shaving for Subset Sum	Tim
11/15	Dynamic least-squares regression	Binghui
11/22	Randomized Algorithms for Quantum OR	John
11/29	Chebyshev Polynomials in TCS	Shivam
12/6	First Order Completeness Via Decision Tree Complexity	Oliver
12/13	Online Recommendations and Adaptive Preferences	William B.

We'll be meeting at 12:30pm every Thursday in CSB 488.

when	topic	presenter	notes
2/3	Algebraic Algorithms Using Exterior Algebra	Dean
2/10	Grothendieck's Inequality	Shivam
2/17	A jumbled mess of a conversation about efficient neural network approximation	Clayton
2/24	Dynamical Systems, Games, and Topology: an introduction	Jason
3/3	Nonlocal games, compression theorems and the arithmetical hierarchy	Hamoon
3/10	Entropic Estimation of Optimal Transport Maps	Aram
3/24	Hardness of Distributed Optimization	Yuval
3/31	Markov Decision Processes and Connections to the Simplex Algorithm	Miranda
4/7	Derandomization, Pigeonhole Principles, and Space-Time Tradeoffs	Oliver
4/14	Balancing sets via random walks	Shyamal
4/21	A short survey of learning with bounded memory	Yasaman
4/28	Problem Fair	Yuval, Hamoon, Roy
5/5	Problem Fair	Dean, Pranav
5/12	Problem Fair	Misc

We'll be meeting at 12pm every Thursday in CSB 488.

when	topic	presenter	notes
10/14	Distribution Free Testing for Halfspaces (Almost) Requires PAC Learning	Shyamal
10/21	Differential Privacy in the U.S. Census	Miranda
10/28	The Platform Design Problem	Kiran	paper
11/4	Deterministic Budget-Feasible Clock Auctions	Pranav	paper
11/11	Approximating Sumset Size	Shivam	paper
11/18	Turning the clocks back: Symplectic Integrators	Manolis
12/2	Formal Barriers to Simple Algorithms for the Matroid Secretary Problem	Maryam	paper
12/9	Sharper bounds on the Fourier concentration of DNFs	Victor	paper
12/16	Near-Optimal SQ Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals	Clayton

This semester, we're meeting at 5:30pm NYC time every Monday over Zoom.

when	topic	presenter	notes
1/25	Sorting with Partial Information	Shivam
2/1	What Can You Do with 2-Layer Networks with Random Weights?	Clayton	paper
2/8	TFNP: PLS, PPP, and Friends in the Black Box	Miranda	slides
2/15	Average Case Equal Subset Sum and Many Friends :)	Tim
2/22	Polynomial Time Trace Reconstruction in the Smoothed Complexity Model	Sandip	paper
3/8	Distributed and Robust Load Balancing	Binghui
3/15	Total Functions in the Polynomial Hierarchy	Dan
3/22	Partial Match and Communication Protocols for Disjointness	Shunhua
3/29	Sharing Heaven	Victor
4/5	Learning in Multi-Player Stochastic Games	William
4/12	Royen Meets Talagrand: A Quantitative Gaussian Correlation Inequality	Shivam
4/19	No Regret Learning & FTRL: (Almost) all you need to know	Manolis
6/2	High-dimensional ML models: When do SVMs work the same as linear regression?	Clayton
6/16	The Hardest Explicit Construction	Oliver

We're meeting every Monday from 5pm to 6pm in CSB 488 (and will have food)!

when	topic	presenter	notes
1/30	Dynamic Optimality and Binary Search Trees–I	Victor
6/20	Intro to Pseudorandomness	Sandip
2/13	Dynamic Optimality and Binary Search Trees–II	Victor
2/20	Expanders and Spectral Graph Theory	Dan
2/27	Local Decodability of the Burrows-Wheeler Transform	Sandip	paper
3/5 11:30am	Lightning Talks and Q&A for prospective PhD students

We're reading classical papers from various subfields of TCS. We'll be meeting from 5pm to 6pm in CSB 488.

when	topic	presenter	notes
9/19	Computing Machinery and Intelligence (Turing, 1950)	Victor
10/10	A Mathematical Theory of Communication (Shannon, 1947)	Shunhua
10/24	The complexity of computing the permanent (Valiant, 1979)	Binghui
11/7	A new polynomial-time algorithm for linear programming (Karmarkar, 1984)	Sandip
11/21	Games against nature (Papadimitriou, 1985)	Kiran
12/5	How to Construct Random Functions (GGM, 1986)	Chengyu