|
Publications (by Years)
Google Scholar Page
2024
2023
Polynomial-Time Pseudodeterministic Construction of Primes [eccc] [my slides]
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
Foundations of Computer Science (FOCS 2023)
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting [eccc] [William's talk at IAS]
Lijie Chen, William Hoza, Xin Lyu, Avishay Tal and Hongxun Wu
Foundations of Computer Science (FOCS 2023)
New PRGs for Unbounded-width/Adaptive-order Read-once Branching Programs
Lijie Chen, Xin Lyu, Avishay Tal and Hongxun Wu
International Colloquium on Automata, Languages and Programming (ICALP 2023)
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut [eccc]
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
2022
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs [eccc]
Lijie Chen, Jiatu Li, Tianqi Yang
Computational Complexity Conference (CCC 2022)
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity [eccc] [video by Ce at ITCS 2022]
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams
Innovations in Theoretical Computer Science (ITCS 2022)
Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions [eccc] [video by Neekon at ITCS 2022]
Lijie Chen, Shuichi Hirahara, Neekon Vafa
Innovations in Theoretical Computer Science (ITCS 2022)
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions [arxiv] [Hongxun's slides] [my slides]
Lijie Chen, Ce Jin, Ryan Williams, Hongxun Wu
ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
2021
Constructive Separations and Their Consequences [eccc] [video by Ryan at FOCS 2021]
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
Foundations of Computer Science (FOCS 2021)
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise [eccc] [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, Roei Tell
Foundations of Computer Science (FOCS 2021). Invited to the SICOMP Special Issue for FOCS 2021
Majority vs. Approximate Linear Sum and average-case complexity below NC1 [eccc] [slides by Igor] [video by Xin]
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Oliveira
International Colloquium on Automata, Languages and Programming (ICALP), 2021
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs [arxiv] [video by Raghuvansh]
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
International Colloquium on Automata, Languages and Programming (ICALP), 2021
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability [eccc]
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Symposium on the Theory of Computing (STOC 2021). Invited to the SICOMP Special Issue for STOC 2021
On Distributed Differential Privacy and Counting Distinct Elements [arxiv] [long slides] [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, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
Innovations in Theoretical Computer Science (ITCS 2021)
2020
Almost Everywhere Circuit Lower Bounds from Non-Trivial Derandomization [eccc] [video by Xin Lyu at FOCS 2020] [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
Foundations of Computer Science (FOCS 2020)
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds [eccc] [video by Roei Tell in FOCS 2020]
Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev
Foundations of Computer Science (FOCS 2020)
2019
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity [slides] [proceeding version]
Lijie Chen, Ryan Williams
Computational Complexity Conference (CCC 2019). This paper subsumes a previous manuscript [arxiv]
2018
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures [arxiv]
Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Improved Algorithms for Maintaining DFS Tree in Undirected Graphs [arxiv]
Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product [eccc] [arxiv] [slides] [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
Computational Complexity Conference (CCC 2018). Invited to the Toc Special Issue for CCC 2018
2017
On The Power of Statistical Zero Knowledge [eccc] [arxiv] [slides]
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
Foundations of Computer Science (FOCS 2017). Invited to the SICOMP Special Issue for FOCS 2017
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration [arxiv] [conference version]
Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao and Ruosong Wang
Conference on Learning Theory (COLT 2017)
Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection [arxiv] [conference version]
Lijie Chen, Jian Li, Mingda Qiao
International Conference on Artificial Intelligence and Statistics (AISTATS 2017)
K-Memory Strategies in Repeated Games
Lijie Chen, Fangzhen Lin, Pingzhong Tang, Kangning Wang, Ruosong Wang, Shiheng Wang
Extended abstract, International Conference on Antonomous Agents and Multiagent Sytems (AAMAS 2017)
2016
Notes
Old Manuscripts
|