English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

A line of work initiated by Fortnow in 1997 has proven model-independenttime-space lower bounds for the $\mathsf{SAT}$ problem and related problemswithin the polynomial-time hierarchy. For example, for the $\mathsf{SAT}$problem, the state-of-the-art is that the problem cannot be solved byrandom-access machines in $n^c$ time and $n^{o(1)}$ space simultaneously for $c< 2\cos(\frac{\pi}{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-spacelower bounds, we show that there are problems verifiable in $O(n)$ time withquantum 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$, asuper-quadratic time lower bound. This result and the prior work on$\mathsf{SAT}$ can both be viewed as consequences of a more general formula fortime lower bounds against small-space algorithms, whose asymptotics we study infull.  We also show lower bounds against randomized algorithms: there are problemsverifiable in $O(n)$ time with (classical) Merlin-Arthur protocols that cannotbe 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, thelower bound in this setting can be improved to $c < 1.5$.

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