Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with time-space lower bounds:
TR08-017 | 16th December 2007
Thomas Watson, Dieter van Melkebeek

A Quantum Time-Space Lower Bound for the Counting Hierarchy

We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real $d$ and every positive real $\epsilon$ ... more >>>

TR10-147 | 22nd September 2010
Dieter van Melkebeek, Thomas Watson

Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

We give two time- and space-efficient simulations of quantum computations with
intermediate measurements, one by classical randomized computations with
unbounded error and the other by quantum computations that use an arbitrary
fixed universal set of gates. Specifically, our simulations show that every
language solvable by a bounded-error quantum algorithm running ... more >>>

TR23-018 | 1st March 2023
Qipeng Liu, Ran Raz, Wei Zhan

Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical memory or an exponential number (in~$n$) of random samples. A line of recent works continued that research direction and showed that for ... more >>>

TR24-032 | 22nd February 2024
Joshua Cook, Dana Moshkovitz

Explicit Time and Space Efficient Encoders Exist Only With Random Access

We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time $n^{1 + o(1)}$ and space $\mathop{polylog}(n)$ provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [DJM98] and the codes ... more >>>

ISSN 1433-8092 | Imprint