26 citations · 107 across the 18 of their papers we have counts for
25 papers
Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, Igor C. Oliveira +2
A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on…
Making Quantum Local Verifiers Simulable with Potential Applications to Zero-Knowledge
Lijie Chen, Ramis Movassagh
Recently Chen and Movassagh proposed the quantum Merkle tree, which is a quantum analogue of the well-known classical Merkle tree. It gives a succinct verification protocol for qua…
Constructive Separations and Their Consequences
Lijie Chen, Ce Jin, Rahul Santhanam +1
For a complexity class and language , a constructive separation of gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for…
Quantum Merkle Trees
Lijie Chen, Ramis Movassagh
Committing to information is a central task in cryptography, where a party (typically called a prover) stores a piece of information (e.g., a bit string) with the promise of not ch…
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
Lijie Chen, Ce Jin, R. Ryan Williams +1
We consider low-space algorithms for the classic Element Distinctness problem: given an array of input integers with bit-length, decide whether or not all elements…
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
Lijie Chen, Gillat Kol, Dmitry Paramonov +3
For a directed graph with vertices and a start vertex , we wish to (approximately) sample an -step random walk over starting from with…