Time-space lower bounds for simulating proof systems with quantum and randomized verifiers
From MaRDI portal
Cites work
- \(\text{RL}\subseteq \text{SC}\)
- Algebrization: a new barrier in complexity theory
- Alternation-trading proofs, linear programming, and lower bounds
- BPP and the polynomial hierarchy
- Computational Complexity
- Delegation with updatable unambiguous proofs and PPAD-hardness
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
- How to delegate computations publicly
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3353257 (Why is no real title available?)
- Inductive time-space lower bounds for SAT and related problems
- Limits on alternation trading proofs for time-space lower bounds
- Lower Bounds for Swapping Arthur and Merlin
- Natural proofs
- Oracle separation of BQP and PH
- Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
- Quantum advantage with shallow circuits
- Recursive composition and bootstrapping for SNARKs and proof-carrying data
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Time-space efficient simulations of quantum computations
- Time-space lower bounds for satisfiability
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- Towards separating nondeterminism from determinism
This page was built for publication: Time-space lower bounds for simulating proof systems with quantum and randomized verifiers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7229339)
