Source author record

R. Ryan Williams

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers

A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the $\mathsf{SAT}$ problem and related problems within the polynomial-time hierarchy. For example, for the $\mathsf{SAT}$ problem, the state-of-the-art is that the problem cannot be solved by random-access machines in $n^c$ time and $n^{o(1)}$ space simultaneously for $c < 2\cos(\fracπ{7}) \approx 1.801$ . We extend this lower bound approach to the quantum and randomized domains. Combining Grover's algorithm with components from $\mathsf{SAT}$ time-space lower bounds, we show that there are problems verifiable in $O(n)$ time with quantum Merlin-Arthur protocols that cannot be solved in $n^c$ time and $n^{o(1)}$ space simultaneously for $c < \frac{3+\sqrt{3}}{2} \approx 2.366$ , a super-quadratic time lower bound. This result and the prior work on $\mathsf{SAT}$ can both be viewed as consequences of a more general formula for time lower bounds against small-space algorithms, whose asymptotics we study in full. We also show lower bounds against randomized algorithms: there are problems verifiable in $O(n)$ time with (classical) Merlin-Arthur protocols that cannot be solved in $n^c$ randomized time and $n^{o(1)}$ space simultaneously for $c < 1.465$ , improving a result of Diehl. For quantum Merlin-Arthur protocols, the lower bound in this setting can be improved to $c < 1.5$ .

preprint2016arXiv

Deterministic Time-Space Tradeoffs for k-SUM

Given a set of numbers, the $k$ -SUM problem asks for a subset of $k$ numbers that sums to zero. When the numbers are integers, the time and space complexity of $k$ -SUM is generally studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point. We present a time and space efficient deterministic self-reduction for the $k$ -SUM problem which holds for both models, and has many interesting consequences. To illustrate: * $3$ -SUM is in deterministic time $O(n^2 \lg\lg(n)/\lg(n))$ and space $O\left(\sqrt{\frac{n \lg(n)}{\lg\lg(n)}}\right)$ . In general, any polylogarithmic-time improvement over quadratic time for $3$ -SUM can be converted into an algorithm with an identical time improvement but low space complexity as well. * $3$ -SUM is in deterministic time $O(n^2)$ and space $O(\sqrt n)$ , derandomizing an algorithm of Wang. * A popular conjecture states that 3-SUM requires $n^{2-o(1)}$ time on the word-RAM. We show that the 3-SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every $O(n^{.51})$ -space algorithm for $3$ -SUM requires at least $n^{2-o(1)}$ time on the word-RAM. * For $k \ge 4$ , $k$ -SUM is in deterministic $O(n^{k - 2 + 2/k})$ time and $O(\sqrt{n})$ space.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.