This is a place for theory-minded people to gather for a weekly lunch seminar. This semester (Spring '25), we (mostly) meet on Thursdays at 11:45 am (for lunch) and the talk starts at noon. The presentations are on papers, results, conjectures, or anything theory-oriented. In order to keep things more casual and interactive, presentations are on the board. We meet at the FDS common room (i.e. room 1307) in Kline Tower.
If you are interested in joining the mailing list, please reach out to {xifan.yu,felix.zhou}@yale.edu.
Past organizers:
2023-24: Marco Pirazzini, Siddharth Mitra
2024-25: Marco Pirazzini, Xifan Yu
January 16: Jane Lee
Title: Variational Method of Moments
January 30: Jinghua Sun
Title: Spectral Independence and Applications to Markov Chain Mixing Time
February 6: Grigoris Velegkas, Antares Chen, Felix Zhou, Vikram Kher
Lightning Talks
February 13: Shuchen Li
Title: Hardness of Learning One Hidden Layer Neural Networks
February 20: Grigoris Velegkas
Title: Understanding the Trade-Offs Between Hallucinations and Mode Collapse in Language Generation
February 27: Felix Zhou
Title: Area Convexity: Multicommodity Flow, Ell-Infinity Regression, Box-Simplex Games, Monotone Variational Inequalities, and Beyond
March 6: Matthew Zhang (UofT)
Title: Shifted Composition Rule
March 23: Anay Mehrotra
Title: Learning from Missing and Imperfect Data
April 3: Xifan Yu
Title: Inference of Ranked Community in Random Directed Graphs
April 17: Antares Chen (UChicago)
Title: Variational Principles for First-Order Methods
September 13: Marco Pirazzini
Title: An Iterative Algorithm for Generalized Eigenvalue Problems
September 27: Xifan Yu
Title: Introduction to Sum-of-Squares and Applications to Proof Complexity
Oct 4: Felix Zhou
Title: Correlation Clustering & Fast Combinatorial Algorithms
Oct 11: Asaf Etgar
Title: Metric Repair: Hardness, Approximation, and more Hardness
Oct 25: Katerina Mamali
Title: A Smoothed Analysis Framework for Learning
Nov 1: Weiqiang Zheng
Title: Tractable $\Phi$-Equilibria in Non-Concave Games
Nov 8: Vikram Kher
Title: Breaking the 3-Distortion Barrier in Metric Voting
Nov 15: Anay Mehrotra
Title: Can SGD Select Good Fishermen? Local Convergence Under Self-Selection Biases
Nov 22: Ben Foxman
Title: An Introduction to Quantum Computation and Complexity
January 25: Felix Zhou
Title: Applications of Uniform Sampling for Densest Subgraph
February 1: Marco Pirazzini
Title: An Approach to Computing the log-Sobolev Constant of Graphs
February 8: Curtis McDonald
Title: Using Log Concavity and Differential Expressions to Compute Score Diffusions
February 22: Gal Yehuda
Title: Lower Bounds in Circuit Complexity and Proof Complexity via Slicing the Hypercube
February 29: Max Ovsiankin (TTIC)
Title: Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
March 5: Geelon So (UCSD)
Title: Optimization on Pareto sets: Geometry of Multi-objective Optimization
March 14: Siyu Chen
Title: Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality
March 26: Jane Shi (MIT)
Title: The Generalized Fermat Equation and Platonic Solids
March 28: George Li (UMD)
Title: Exact Emulators for Planar Graphs
April 4: Heejune Sheen
Title: Implicit Regularization of Gradient Flow for One-layer Softmax Attention
April 9: Anay Mehrotra
Title: Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond Gaussians
April 18: Jonas Katona
Title: Connections between Symplectic Integration and Algorithmic Game Theory: A Symplectic Analysis of Alternating Mirror Descent
April 25: Xizhi Tan (Drexel)
Title: Learning-augmented Metric Distortion
May 9: Xifan Yu
Title: Detecting Planted Subgraphs via Counting Stars
May 16: Reuben Drogin
Title: The Solovay-Kitaev Algorithm and the Diophantine Property
May 23: Marco Pirazzini
Title: Differentially private MWU
May 30: Dan Spielman
Title: The Impact of Ramanujan Graphs
June 6: Tim Kunisky
Title: Quiet Planting: a Strategy for Showing Hardness of General-Purpose Computation
August 30: Gaurav Mahajan
Title: Some Open Problems in TCS
September 6: Alkis Kalavasis
Title: Some Open Problems in TCS
September 13: Xifan Yu
Title: From an Interview Probability Question to Expansion Properties of Some 0/1 Polytopes
September 27: Anay Mehrotra
Title: Selection with Implicit Bias: Evaluating the Efficacy of Interventions
October 4: Grigoris Velegkas
Title: Statistical Indistinguishability of Learning Algorithms
October 11: Felix Zhou
Title: Replicable Clustering
October 18: Binghui Peng (Columbia)
Title: Memory-Query Tradeoffs for Randomized Convex Optimization
November 1: Zihan Tan (DIMACS)
Title: On (1 + \eps)-Approximate Flow Sparsifiers
November 8: Peiyuan Zhang
Title: The Minimax Theorem and Algorithms in Geodesic Metric Space
November 15: Alkis Kalavasis
Title: Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods
November 22: Siddharth Mitra
Title: On System Identification in Linear Dynamical Systems
November 29: Tianhao Wang
Title: Algorithm Dynamics in Modern Statistical Learning: Universality and Implicit Bias
May 24: Xifan Yu
Title: Algorithmic Lower Bounds for Expansion Profile of Regular Graphs
May 31: Asaf Etgar
Title: On the Connectivity and Diameter of Geodetic Graphs
June 7: Jane Lee
Title: Statistics Without iid Samples: Learning From Truncated Data
June 14: Jinzhao Wu
Title: On the Optimal Fixed-Price Mechanism in Bilateral Trade
July 5: Siddharth Mitra
Title: On Single-cell Trajectory Inference
July 12: Asaf Etgar
Title: On Graphs and Geometry
July 19: Marco Pirazzini
Title: On the Small Set Expansion Hypothesis
July 26: Khashayar Gatmiry (MIT)
Title: Sampling with Barriers: Faster Mixing via Lewis Weights
August 16: John Lazarsfeld
Title: Decentralized Learning Dynamics in the Gossip Model
August 23: Aditi Laddha
Title: Determinant Maximization via Local Search