Talks

Chronological Order

• Sharp Threshold Results for Computational Complexity
  Lijie Chen, Ce Jin, Ryan Williams
  Oxford-Warwick complexity Meetings (2020)
  [slides]
  

• Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
  Lijie Chen, Hanlin Ren
  Combinatorics and TCS seminar, the University of Chicago
  Lower Bounds in Computational Complexity Reunion, the Simons Institute for the Theory of Computing
  [slides]
  

• Efficient Construction of Rigid Matrices Using an NP Oracle
  Josh Alman, Lijie Chen
  Foundations of Computer Science (FOCS 2019)
  [slides]
  

• Recent Developments in Fine-Grained Complexity via Communication Complexity
  Tsinghua University 2019
  [slides]
  

• Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity
  Lijie Chen, Ryan Williams
  CCC 2019
  [slides]
  

• Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds
  Lijie Chen, Roei Tell
  Symposium on the Theory of Computing (STOC 2019)
  [slides]
  

• Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
  Lijie Chen
  Theory Seminar of UT Austin
  Harvard TGINF
  CMU Theory Lunch
  Foundations of Computer Science (FOCS 2019)
  [slides]
  

• Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
  Lijie Chen, Ruosong Wang
  ITCS 2019
  [slides]
  

• An Equivalence Class for Orthogonal Vectors
  Lijie Chen, Ryan Williams
  SODA 2019
  [slides]
  

• Recent Structure Lemmas for Depth-Two Threshold Circuits
  Lijie Chen
  Simons Institute for the Theory of Computing 2018
  [slides]
  

• On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
  Lijie Chen
  CCC 2018
  Algorithms & Complexity Seminar, MIT
  [slides]
  

• On The Power of Statistical Zero Knowledge
  Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
  FOCS 2017
  Algorithms & Complexity Seminar, MIT
  [slides]
  

• Complexity-Theoretic Foundations of Quantum Supremacy Experiments
  Scott Aaronson, Lijie Chen
  CCC 2017
  [slides]
  

• Adaptivity vs Postselection
  Lijie Chen
  ISAAC 2016
  [slides]
  

• Pure Exploration of Multi-armed Bandit Under Matroid Constraints
  Lijie Chen, Anupum Gupta, Jian Li
  COLT 2016
  [slides]
  

• Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture
  Lijie Chen, Jian Li
  COLT 2016 Open Problem
  [slides]