Theory Reading Group

Subscribe to the mailing list of the reading group to get involved!

Fall 2017: Biweekly on Wednesday 10:00-11:00 am at SAL 246

  • 09/27 Trace reconstruction for the deletion channel
  • 10/11 Hashing-based-Estimators for Kernel Density in High Dimensions
  • 10/25 A Time Hierarchy Theorem for the LOCAL Model
  • 11/08
  • 11/15

Spring 2017: Every Thursday 12:00-13:30 am at SAL 213

  • 02/02 Yu SODA/ITCS recap
  • 02/09 PhD social lunch
  • 02/16 No Meeting
  • 02/23 Alana Interior-Point Methods
  • 03/09 Ehsan Graph Stream Algorithms
  • 03/23 Ruixin A Duality Based Unified Approach to Bayesian Mechanism Design
  • 03/30 Haifeng Introduction to Coding Theory
  • 04/06 Brendan Differential Privacy 101
  • 04/13 A Reverse Minkowski Theorem

Fall 2016: Biweekly on Wednesday 10:00-11:00 am at SAL 213

  • 09/14 Fast Approximate Gaussian Elimination for Laplacians
  • 09/28 High rate locally-correctable codes and locally-testable codes with subpolynomial query complexity
  • 10/19 Kernel-based methods for Bandit Convex Optimization
  • 10/26 Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics
  • 11/09 Informational Substitutes
  • 11/23 The Magic of Extremely Lossy Functions
  • 12/07 Robust Estimators in High Dimensions without the Computational Intractability

Spring 2016: Every Thursday 12:00-1:00 pm at SAL 213

  • 01/28 Markov Chain Mixing Times and Applications I
  • 02/04 Markov Chain Mixing Times and Applications II
  • 02/11 Yu Fun with Hardness Proofs
  • 02/18 No Meeting
  • 02/25 Yu Query Complexity of Nash in large games
  • 03/03 No Meeting
  • 03/10 Phd Social Lunch
  • 03/17 Spring Break
  • 03/24 Complexity in AGT Update: Nash Approximability and Simultaneous Auctions
  • 03/31 Joe Sum of squares
  • 04/07 Sum of squares 2
  • 04/14 Sum of squares 3
  • 04/21 Sum of squares 4

Fall 2015: Every Wednesday 12:00-1:00 pm at SAL 246

  • 09/07 Complexity and Algorithmic Game Theory I
  • 09/14 Complexity and Algorithmic Game Theory II
  • 09/23 Spectral Sparsification of Graphs I
  • 09/30 Spectral Sparsification of Graphs II
  • 10/07 Yu Mixture Selection, Mechanism Design, and Signaling
  • 10/14 No Meeting
  • 10/21 No Meeting
  • 10/28 Xinran Random algorithms for Numerical Linear Algebra
  • 11/04 Xinran Random algorithms for Numerical Linear Algebra II
  • 11/11 The Sample Complexity of Revenue Maximization
  • 12/02 Ruixin Incentivizing Exploration with Heterogeneous Value of Money

Spring 2015: Every Wednesday 1:00-2:00 pm at SAL 213

  • 02/04 Lian Lattices, basis reduction and applications
  • 02/11 Ruixin Ellipsoid method and its consequences in combinatorial optimization
  • 02/18 CS PhD Lunch
  • 02/25 Alana Provable Bounds for Learning Some Deep Representations
  • 03/03 Yu Selfish Routing
  • 03/10 Haifeng Jointly Private Convex Programming
  • 03/17 Spring Break
  • 03/24 No meeting
  • 04/01 CS PhD Lunch
  • 04/08 No meeting
  • 04/15 Li Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis

Fall 2014: Every Wednesday 12:30-2:00 pm at SAL 213

  • 09/10 Joe Hardness of approximation on 3-SAT
  • 09/17 Ehsan On Complexity Classes, Some Theorems and Conjectures
  • 09/24 Ruixin Economic Efficiency Requires Interaction
  • 10/01 Ho Yee Subcubic Equivalences between Path, Matrix and Triangle Problems
  • 10/08 Yu Popular conjectures imply strong lower bounds for dynamic problems
  • 10/15 Ho Yee Polynomial Identitiy Testing and Graph Matching
  • 10/22 Yu Some Applications of Expander Graphs
  • 10/29 No Reading Group
  • 11/05 Joe Parallel Repetition
  • 11/12 Haifeng Uniform Sampling for Matrix Approximation

Spring 2014: Every Wednesday 12-2 pm at SAL 222

  • 02/26 Haifeng Xu Lovasz Local Lemma
  • 03/05 Li Han Optimal Algorithms and Inapproximability Results for Every CSP?
  • 03/25 Li Han Optimal Algorithms and Inapproximability Results for Every CSP? (Part 2)
  • 04/02 Yu Cheng Cheeger's inequality
  • 04/16 Ho Yee Cheung Multi-way spectral partitioning and higher-order Cheeger inequalities
  • 04/23 Ho Yee Cheung Multi-way spectral partitioning and higher-order Cheeger inequalities (Part 2)
  • 04/30 Ruixin Qiang A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

Fall 2013: Every Wednesday 2-4 pm at SAL 222

  • 09/25 Li Han Intro to Compressed Sensing
  • 10/02 Haifeng Xu Deterministic construction of compressed sensing matrices
  • 10/16 Ho Yee Cheung Survey on max flow
  • 10/23 Yu Cheng Near linear time Max-flow for undirected graphs
  • 10/30 Ben Reichdart Simple near-linear time algorithm for solving SDD systems
  • 11/13 Joe Bebel Graph isomorphisms in Steiner systems and strongly regular graphs
  • 12/04 Joe Bebel Graph isomorphisms in Steiner systems and strongly regular graphs (Part 2)