CU 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 theoryphd mailing list. 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!
Fall 2023
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 
FiatShamir for BoundedDepth Adversaries 
Tianqi 

9/26 
The FineGrained 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 p^{k} 
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 
Revenueoptimal auctions: the classics 
Jason 
The framework of DSIC auctions with bids, dominantstrategy revelation principle, welfare and revenue maximization 
2/9 
Revenueoptimal auctions: the continuation of the classics 
Jason 
virtual valuation functions, the BulowKlemperer 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 p^{k} 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 leastsquares 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 SpaceTime 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 BudgetFeasible 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 
NearOptimal 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 2Layer 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 MultiPlayer 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 
Highdimensional 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 BurrowsWheeler 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.