Talks

Chronological Order

  • 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]

  • 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]