17 citations · 29 across the 5 of their papers we have counts for
4 papers · 1 filter
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…
An Equivalence Class for Orthogonal Vectors
Lijie Chen, Ryan Williams
The Orthogonal Vectors problem () asks: given vectors in , are two of them orthogonal? is easily solved in time,…
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
Lijie Chen, Erik D. Demaine, Yuzhou Gu +3
Since the introduction of retroactive data structures at SODA 2004, a major unsolved problem has been to bound the gap between the best partially retroactive data structure (where…