Columbia Theory Student Seminar

We are meeting at 12:00pm every Wednesday in CSB 501 (the fifth floor lounge area). We still have slots open for talks, so please let us know if you're interested in giving one!

when	topic	presenter
10/14	Stable Periodic Outcomes of Learning in Games	Oliver Biggar
10/21	How to Track Qubits Through Space and Time (Or: Sailing a Quantum Boat)	Leo Orshansky
10/28	The Price of Multi-Group Learning: Statistical versus Transductive	Noah Bergam
11/4	TBA	Ashwin Padaki (visiting from Penn)

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	QMA and the Power of "Positivity"	Kunal Marwaha
10/24	Quantum versus Classical Queries and Communication	Uma Girish
10/31	Polynomial factorization mod pk	Sayak
11/7	Production Networks Resilience: Cascading Failures, Power Laws and Optimal Interventions	Marios Papachristou
11/14	Smoothed Online Learning: Theory and Applications	Adam Block
11/21	An efficient quantum parallel repetition theorem and applications	John
11/28	The Tree Evaluation Problem: Context and Recent Results	Ian Mertz
12/5	On Pigeonhole Principles and Ramsey in TFNP	Siddhartha Jain

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