Columbia CS Theory Student Seminar

This group is a setting for PhD students and postdocs in the theory group at Columbia to get together once a week to socialize and learn from each other. Our meetings are a mix of research and paper presentations, practice talks, and open problem sessions. We communicate primarily on the theory-phd mailing list (and also on the Columbia CS PhD Slack). Feel free to reach out to Jason, or Rashida if you'd like to give a talk, join the mailing list, or have any questions!

Spring 2023

We are meeting at 2pm every Thursday in CSB 453.

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	TBD	Binghui
4/20	TBD	Oliver
4/27	TBD	TBD
5/4	TBD	TBD
5/11	TBD	TBD

Fall 2022

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

when	topic	presenter
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.

Spring 2022

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

when	topic	presenter
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

Fall 2021

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

Spring 2021

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

Spring 2020

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

Fall 2019

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

when	topic	presenter
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

CU Theory Student Seminar