# 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]
Textbook hardness-to-randomness converts circuit lower bounds into PRGs. But is this black-box approach really necessary for derandomization? In this new work we revamp the classical hardness-to-randomness framework, showing how to convert new types of uniform lower bounds into non-black-box derandomization, deducing conclusions such as promiseBPP = promiseP without PRGs. Moreover, we show that the same types of lower bounds are in fact necessary for any type of derandomization! This reveals a tight connection between any derandomization of promiseBPP (i.e., not necessarily a black-box one) and the foregoing new types of uniform lower bounds.
Our framework also allows a flexible trade-off between hardness and randomness. In an extreme setting, we show that plausible uniform lower bounds imply that "randomness is indistinguishable from useless". That is, every randomized algorithm can be derandomized with an arbitrarily small polynomial overhead, such that no polynomial-time algorithm can find a mistake with non-negligible probability.
}}
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]
Problem: We study the CountDisticnt problem where there are $n$ users each holding an element in a distributed setting, and the goal is to (approximately) count the total number of distinct elements.
Non-interactive Local Model: We show that no (1) $(\ln n - 7 \ln\ln n, n^{-\omega(1)})$-DP Local protocol can solve CountDisticnt with error $n/(\ln n)^{\omega(1)}$ and (2) there is an $(\ln n)$-DP Local protocol solving CountDisticnt with error $\tilde{O}(\sqrt{n})$.
Shuffle Model: We show that no (1) $(O(1), 2^{-\log^9 n})$-DP single-message shuffle protocol can solve CountDisticnt with error $n/(\ln n)^{\omega(1)}$ and (2) there is an $(O(1), 2^{-\log^9 n})$-DP shuffle protocol solving CountDisticnt with error $\tilde{O}(\sqrt{n})$, where each user sends at most $1$ messages in expectation.
Two-Party Model: We also established an $\tilde{\Omega}(n)$ vs. $O(1)$ separation between error in two-party DP and global sensitivity, answering an open question of McGregor et al. (2011).
Dominated Protocols: We also introduce a relaxation of local-DP protocols called dominated-protocols, and show that multi-message shuffle-DP protocols are dominated. By proving lower bounds against dominated protocols, we also prove lower bounds for selection and learning-parity against multi-message shuffle-DP protocols.
Moment Matching and Poissonization: Inspired by the Poissonization and moment matching techniques in the context of property testing. Our lower bounds are proved by (1) constructing two hard distributions on datasets (2) expressing the histogram of applying any $(\ln n - 7 \ln\ln n, n^{-\omega(1)})$-DP on a distribution of datasets as a sum of many independent mixtures of multi-dimensional Poisson distributions. (3) Using the moment-matching technique to bound the statistical distance between two mixtures of multi-dimensional Poisson distributions.
}}
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]
(Among many other things), we show that there is a function $f \in \mathsf{E}^{\mathsf{NP}}$ such that $f_n$ ($f$ restricted to $n$-bit inputs) cannot be ($1/2 + 2^{-n^{\varepsilon}}$)-approximated by $2^{n^{\varepsilon}}$-size $\mathsf{ACC}^0$ circuits, for all sufficiently large input lengths $n$.
Our lower bounds come from a generic framework showing that non-trivial derandomization of a circuit class $\mathcal{C}$ implies $\mathsf{E}^{\mathsf{NP}}$ is almost-everywhere hard for $\mathcal{C}$.
}}
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]
Under $\mathsf{SETH}$, we give a characterization on when approxiamte Boolean Max-IP is hard (w.r.t approxiamtion ratios and vector dimensions). We also show quadratic time hardness for Z-Max-IP with $2^{\log^*n}$ dimensions (Recall that $\log^* n$ is the number of logs it takes to reduce $n$ to at most $1$. It is an extremely slow-growing function.)
One notable corollary is that finding the furthest pair among $n$ points in $2^{\log^*n}$ dimension Euclidian space requires essentialy $n^2$ time under $\mathsf{SETH}$.
}}
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