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 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 |
|
We'll be meeting at 12:30pm every Thursday in CSB 488.
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.