1 citations · 1 across the 2 of their papers we have counts for
2 papers
cs.DS2021★ 1 cited
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…
cs.CC2021
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers
Abhijit S. Mudigonda, R. Ryan Williams
A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the problem and related problems within the polynomial-time hier…