# jemdoc: menu{MENU}{index.html}, showsource, analytics{UA-31107207-1} = Publications (by Years) [https://scholar.google.com/citations?user=T_OhvOsAAAAJ&hl=en Google Scholar Page] == 2023 - *New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method* [https://eccc.weizmann.ac.il/report/2022/183/ \[eccc\]]\n Lijie Chen\n /Innovations in Theoretical Computer Science/ (ITCS 2023)\n - *Black-box Constructive Proofs are Unavoidable*\n Lijie Chen, Ryan Williams, Tianqi Yang\n /Innovations in Theoretical Computer Science/ (ITCS 2023)\n - *Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut* [https://eccc.weizmann.ac.il/report/2022/161/ \[eccc\]]\n Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu\n /ACM-SIAM Symposium on Discrete Algorithms/ (SODA 2023)\n == 2022 - *Unstructured Hardness to Average-Case Randomness* [https://eccc.weizmann.ac.il/report/2022/097/ \[eccc\]]\n Lijie Chen, Ron D. Rothblum, Roei Tell\n /Foundations of Computer Science/ (FOCS 2022)\n - *Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs* [https://eccc.weizmann.ac.il/report/2022/086/ \[eccc\]]\n Lijie Chen, Jiatu Li, Tianqi Yang\n /Computational Complexity Conference/ (CCC 2022)\n - *Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity* [https://eccc.weizmann.ac.il/report/2021/165/ \[eccc\]] [https://www.youtube.com/watch?v=jTIgQd6Qy_g \[video by Ce at ITCS 2022\]]\n Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams\n /Innovations in Theoretical Computer Science/ (ITCS 2022)\n - *Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions* [https://eccc.weizmann.ac.il/report/2021/166/ \[eccc\]] [https://www.youtube.com/watch?v=aQZEsmpbWE0 \[video by Neekon at ITCS 2022\]]\n Lijie Chen, Shuichi Hirahara, Neekon Vafa\n /Innovations in Theoretical Computer Science/ (ITCS 2022)\n - *Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions* [https://arxiv.org/abs/2111.01759 \[arxiv\]]\n Lijie Chen, Ce Jin, Ryan Williams, Hongxun Wu\n /ACM-SIAM Symposium on Discrete Algorithms/ (SODA 2022)\n == 2021 - *Constructive Separations and Their Consequences* [https://eccc.weizmann.ac.il/report/2021/159/ \[eccc\]] [https://www.youtube.com/watch?v=QAd2gc5mCpg \[video by Ryan at FOCS 2021\]]\n Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams\n /Foundations of Computer Science/ (FOCS 2021)\n - *Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise* [https://eccc.weizmann.ac.il/report/2021/080/ \[eccc\]] [nonbb-derand-final.pptx \[slides\] ] {{ [short summary]
}} Lijie Chen, [https://sites.google.com/site/roeitell/ Roei Tell]\n /Foundations of Computer Science/ (FOCS 2021). {{}}Invited to the SICOMP Special Issue for FOCS 2021{{}}\n - *Majority vs. Approximate Linear Sum and average-case complexity below NC1* [https://eccc.weizmann.ac.il/report/2021/040/ \[eccc\]] [MAJ-apxSUM-dagstuhl.ppsx \[slides by Igor\]] [https://www.youtube.com/watch?v=3sA1lfwfHO8 \[video by Xin\]]\n Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Oliveira\n /International Colloquium on Automata, Languages and Programming/ (ICALP), 2021 \n - *Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs* [https://arxiv.org/abs/2102.11251 \[arxiv\]] [https://www.youtube.com/watch?v=NbI1lbcjfDg \[video by Raghuvansh\]]\n Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu\n /International Colloquium on Automata, Languages and Programming/ (ICALP), 2021 \n - *Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability* [https://eccc.weizmann.ac.il/report/2021/027/ \[eccc]]\n Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu\n /Symposium on the Theory of Computing/ (STOC 2021). {{}}Invited to the SICOMP Special Issue for STOC 2021{{}}\n - *Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost* [https://eccc.weizmann.ac.il/report/2020/148/ \[eccc\]] [http://www.wisdom.weizmann.ac.il/~oded/MC/294.html \[Oded's choice\]] [optimalderand-2020-ICT-CAS.pptx \[slides\]]\n Lijie Chen, [https://sites.google.com/site/roeitell/ Roei Tell]\n /Symposium on the Theory of Computing/ (STOC 2021)\n - *Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma* [Derand-XOR.pdf \[paper\]] [https://eccc.weizmann.ac.il/report/2021/003/ \[eccc]]\n Lijie Chen, Xin Lyu\n /Symposium on the Theory of Computing/ (STOC 2021)\n - *On Distributed Differential Privacy and Counting Distinct Elements* [https://arxiv.org/abs/2009.09604 \[arxiv]] [countDistinct-long.pptx \[long slides\]] [countDistinct-short.pptx \[short slides\]] {{ [summary]
}} Lijie Chen, [https://sites.google.com/view/badihghazi/home Badih Ghazi], [https://sites.google.com/site/ravik53/ Ravi Kumar], [https://pasin30055.github.io/ Pasin Manurangsi]\n /Innovations in Theoretical Computer Science/ (ITCS 2021)\n == 2020 - *Almost Everywhere Circuit Lower Bounds from Non-Trivial Derandomization* [https://eccc.weizmann.ac.il/report/2020/150/ \[eccc\]] [https://www.youtube.com/watch?v=vpyoZdv--nw&list=PL3DbynX8gwfJLYrm4EoZn6aK7IAACiTKa&index=6 \[video by Xin Lyu at FOCS 2020\]] [Ryan-slides-ae-lowerbound.pdf \[slides by Ryan\]] {{ [short highlight]
}} Lijie Chen, Xin Lyu, Ryan Williams\n /Foundations of Computer Science/ (FOCS 2020)\n - *On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds* [https://eccc.weizmann.ac.il/report/2019/169 \[eccc\]] [https://www.youtube.com/watch?v=6xmE9e5m9WA&list=PL3DbynX8gwfJLYrm4EoZn6aK7IAACiTKa \[video by Roei Tell in FOCS 2020\]] \n Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev\n /Foundations of Computer Science/ (FOCS 2020)\n - *Sharp Threshold Results for Computational Complexity* [https://eccc.weizmann.ac.il/report/2020/065/ \[eccc\]] [sharp-threshold.pptx \[slides\]] \n Lijie Chen, Ce Jin, Ryan Williams\n /Symposium on the Theory of Computing/ (STOC 2020)\n - *Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization* [https://eccc.weizmann.ac.il/report/2020/010/ \[eccc\]] [Reunion_Talk.pptx \[slides at Simons (for complexity theorist)\]] [IAS_Talk.pptx \[slides at IAS (intense version)\]] [Warwick_Talk.pptx \[slides at Warwick (lightweight version)\]] \n Lijie Chen, [https://hanlin-ren.github.io/ Hanlin Ren]\n /Symposium on the Theory of Computing/ (STOC 2020). {{}}Invited to the SICOMP Special Issue for STOC 2020{{}}\n - *Beyond Natural Proofs: Hardness Magnification and Locality* [https://eccc.weizmann.ac.il/report/2019/168/ \[eccc\]] [https://arxiv.org/abs/1911.08297 \[arxiv\]] [https://www.dcs.warwick.ac.uk/~igorcarb/documents/papers/magnification-note.pdf \[notes by Igor\]]\n Lijie Chen, [https://researchmap.jp/shuichi.hirahara/ Shuichi Hirahara],[https://www.dcs.warwick.ac.uk/~igorcarb/ Igor Oliveira], [http://users.ox.ac.uk/~coml0742/ Jan Pich], [https://www.cs.ox.ac.uk/people/ninad.rajgopal/ Ninad Rajgopal], [https://www.cs.ox.ac.uk/people/rahul.santhanam/ Rahul Santhanam]\n /Innovations in Theoretical Computer Science/ (ITCS 2020)\n == 2019 - *Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits* [Austin-NQP-Average-Case-Lower-Bound.pptx \[Talk at UT Austin's Theory Seminar\]] [https://eccc.weizmann.ac.il/report/2019/031/ \[eccc\]] [Che19-journal-version.pdf \[draft of journal version\]]\n Lijie Chen\n /Foundations of Computer Science/ (FOCS 2019). {{}}Invited to the SICOMP Special Issue for FOCS 2019{{}}\n - *Efficient Construction of Rigid Matrices Using an NP Oracle* [FOCS_2019_rigidmatrix.pdf \[pdf\]] [FOCS_2019_rigidmatrix_slides.pptx \[slides\]] [http://www.wisdom.weizmann.ac.il/~oded/MC/281.html \[Oded's choice\]]\n [http://joshalman.com/ Josh Alman], Lijie Chen\n /Foundations of Computer Science/ (FOCS 2019). {{}}Machtey Award for Best Student Paper. Invited to the SICOMP Special Issue for FOCS 2019{{}}\n - *Hardness Magnification for all Sparse NP Languages* [https://eccc.weizmann.ac.il/report/2019/118/ \[eccc\]] \n Lijie Chen, Ce Jin, Ryan Williams\n /Foundations of Computer Science/ (FOCS 2019)\n - *Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators* [https://eccc.weizmann.ac.il/report/2019/072/ \[eccc\]]\n Lijie Chen, Ofer Grossman\n /Symposium on Principles of Distributed Computing/ (PODC 2019)\n - *Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems* [https://eccc.weizmann.ac.il/report/2019/075/ \[eccc\]] [http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=10852 \[proceeding version\]]\n Lijie Chen, [http://www.dylanmmckay.com/ Dylan McKay], Cody Murray, [https://people.csail.mit.edu/rrw/ Ryan Williams]\n /Computational Complexity Conference/ (CCC 2019)\n - *Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity* [CCC_2019_PCPP.pptx \[slides\]] [http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=10841 \[proceeding version\]]\n Lijie Chen, [https://people.csail.mit.edu/rrw/ Ryan Williams]\n /Computational Complexity Conference/ (CCC 2019). This paper subsumes a previous manuscript [https://arxiv.org/abs/1805.10698 \[arxiv\] ]\n - *Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds* [https://eccc.weizmann.ac.il/report/2018/199/ \[eccc\]] [http://www.wisdom.weizmann.ac.il/~oded/MC/256.html \[Oded's choice\]]\n Lijie Chen, [https://sites.google.com/site/roeitell/ Roei Tell]\n /Symposium on the Theory of Computing/ (STOC 2019). {{}}Danny Lewin Best Student Paper Award{{}}\n - *Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols* [https://arxiv.org/abs/1811.07515 \[arxiv\]] [ITCS_2019_CC_PPT.pptx \[slides\]]\n Lijie Chen, Ruosong Wang\n /Innovations in Theoretical Computer Science/ (ITCS 2019)\n - *An Equivalence Class for Orthogonal Vectors* [SODA_2019_OV-Equiv.pdf \[proceeding version\]] [SODA_2019_OV-Equiv-Fullversion.pdf \[full version\]] [SODA_2019_OV_PPT.pptx \[slides\]]\n Lijie Chen, [https://people.csail.mit.edu/rrw/ Ryan Williams]\n /ACM-SIAM Symposium on Discrete Algorithms/ (SODA 2019)\n - *Fine-grained Complexity Meets IP = PSPACE* [https://arxiv.org/abs/1805.02351 \[arxiv\] ]\n Lijie Chen, [http://people.csail.mit.edu/shafi/ Shafi Goldwasser], Kaifeng Lyu, [https://guyrothblum.wordpress.com/ Guy N. Rothblum], [https://cs.stanford.edu/~aviad/ Aviad Rubinstein]\n /ACM-SIAM Symposium on Discrete Algorithms/ (SODA 2019)\n == 2018 - *Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures* [https://arxiv.org/abs/1804.06932 \[arxiv\] ]\n Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu\n /Scandinavian Symposium and Workshops on Algorithm Theory/ (SWAT 2018)\n - *Improved Algorithms for Maintaining DFS Tree in Undirected Graphs* [https://arxiv.org/abs/1607.04913 \[arxiv\] ]\n Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang\n /Scandinavian Symposium and Workshops on Algorithm Theory/ (SWAT 2018)\n - *On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product* [https://eccc.weizmann.ac.il/report/2018/026/ \[eccc\] ] [https://arxiv.org/abs/1802.02325 \[arxiv\]] [CCC_2018_MaxIP.pptx \[slides\] ] [https://theoryofcomputing.org/articles/v016a004/ \[journal version\]] {{ [short highlight]
}} Lijie Chen\n /Computational Complexity Conference/ (CCC 2018). {{}} Invited to the Toc Special Issue for CCC 2018{{}}\n == 2017 - *On The Power of Statistical Zero Knowledge* [http://eccc.hpi-web.de/report/2016/140/ \[eccc\]] [http://arxiv.org/abs/1609.02888 \[arxiv\]] [FOCS_2017_SZKPP.pdf \[slides\]]\n Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan\n /Foundations of Computer Science/ (FOCS 2017). {{}}Invited to the SICOMP Special Issue for FOCS 2017{{}}\n - *Towards Instance Optimal Bounds for Best Arm Identification* [http://arxiv.org/abs/1608.06031 \[arxiv\]] [http://proceedings.mlr.press/v65/chen17b.html \[conference version\] ]\n Lijie Chen, Jian Li, Mingda Qiao\n /Conference on Learning Theory/ (COLT 2017)\n - *Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration* [https://arxiv.org/abs/1706.01081 \[arxiv\] ] [http://proceedings.mlr.press/v65/chen17a.html \[conference version\] ]\n Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao and Ruosong Wang\n /Conference on Learning Theory/ (COLT 2017)\n - *Complexity-Theoretic Foundations of Quantum Supremacy Experiments* [http://eccc.hpi-web.de/report/2016/200/ \[eccc\]] [https://arxiv.org/abs/1612.05903 \[arxiv\]] [CCC_2017_QuantumSupremacy.pdf \[slides\]]\n [https://www.scottaaronson.com/ Scott Aaronson], Lijie Chen\n /Computational Complexity Conference/ (CCC 2017). {{}}Invited to the Toc Special Issue for CCC 2017{{}}\n - *Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection* [http://arxiv.org/abs/1702.03605 \[arxiv\] ] [http://proceedings.mlr.press/v54/chen17a/chen17a.pdf \[conference version\] ]\n Lijie Chen, Jian Li, Mingda Qiao\n /International Conference on Artificial Intelligence and Statistics/ (AISTATS 2017)\n - *K-Memory Strategies in Repeated Games*\n Lijie Chen, Fangzhen Lin, Pingzhong Tang, Kangning Wang, Ruosong Wang, Shiheng Wang\n Extended abstract, /International Conference on Antonomous Agents and Multiagent Sytems/ (AAMAS 2017)\n - *Bounded rationality of restricted Turing machines* [https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14300 \[conference version\] ]\n Lijie Chen, Pingzhong Tang, Ruosong Wang\n AAAI 2017\n == 2016 - *Adaptivity vs Postselection* [http://arxiv.org/abs/1606.04016 \[arxiv\] ] [http://drops.dagstuhl.de/opus/volltexte/2016/6796/pdf/LIPIcs-ISAAC-2016-26.pdf \[conference version\] ] [ISAAC_2016_AdaPost.pdf \[slides\] ]\n Lijie Chen\n /International Symposium on Algorithm and Computation/ (ISAAC 2016) Best Student Paper Award\n - *Pure Exploration of Multi-armed Bandit Under Matroid Constraints* [http://arxiv.org/abs/1605.07162 \[arxiv\] ] [http://www.jmlr.org/proceedings/papers/v49/chen16a.pdf \[conference version\]] [COLT_2016_Matroid.pdf \[slides\]]\n Lijie Chen, Anupum Gupta, Jian Li\n /Conference on Learning Theory/ (COLT 2016)\n - *Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture* [http://arxiv.org/abs/1605.08481 \[arxiv\] ] [http://www.jmlr.org/proceedings/papers/v49/chen16b.pdf \[conference version\]] [COLT_2016_OpenProblem.pdf \[slides\]]\n Lijie Chen, Jian Li\n /Conference on Learning Theory Open Problem/ (COLT 2016 Open Problem)\n == Notes - *A Note on Oracle Separations for BQP*\n Lijie Chen\n [http://arxiv.org/abs/1605.00619 \[arxiv\] ]\n == Old Manuscripts - *On the Optimal Sample Complexity for Best Arm Identification*\n Lijie Chen, Jian Li\n [http://arxiv.org/abs/1511.03774 \[arxiv\] ]\n