Buchumschlag

Short and useful quantum proofs for sublogarithmic-space verifiers

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Say, A. C. Cem
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Time hierarchies for sublogarithmic-space quantum computation
von: Say, A. C. Cem
Veröffentlicht: (2025)

Fine-grained quantum advantage beyond double-logarithmic space
von: Say, A. C. Cem
Veröffentlicht: (2026)

Unconditional proofs of quantumness between small-space machines
von: Say, A. C. Cem, et al.
Veröffentlicht: (2024)

$\rm P$ has polynomial-time finite-state verifiers
von: Gezer, M. Utkan, et al.
Veröffentlicht: (2023)

Interactive proofs for verifying (quantum) learning and testing
von: Caro, Matthias C., et al.
Veröffentlicht: (2024)

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
von: Gezer, M. Utkan, et al.
Veröffentlicht: (2020)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
von: Liu, Zhenning, et al.
Veröffentlicht: (2024)

How hard is it to verify a classical shadow?
von: Karaiskos, Georgios, et al.
Veröffentlicht: (2025)

Classical versus quantum queries in quantum PCPs with classical proofs
von: Buhrman, Harry, et al.
Veröffentlicht: (2024)

Space-bounded quantum interactive proof systems
von: Gall, François Le, et al.
Veröffentlicht: (2024)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
von: Anand, Kartik, et al.
Veröffentlicht: (2025)

The Role of piracy in quantum proofs
von: Broadbent, Anne, et al.
Veröffentlicht: (2024)

Quantum Merlin-Arthur proof systems for synthesizing quantum states
von: Delavenne, Hugo, et al.
Veröffentlicht: (2023)

On $NP \cap coNP$ proof complexity generators
von: Krajicek, Jan
Veröffentlicht: (2025)

On the Need for (Quantum) Memory with Short Outputs
von: Hao, Zihan, et al.
Veröffentlicht: (2026)

Lower bounds for set-blocked clauses proofs
von: Yolcu, Emre
Veröffentlicht: (2024)

Quantum Merlin-Arthur with an internally separable proof
von: Bassirian, Roozbeh, et al.
Veröffentlicht: (2024)

Quantum interactive proofs using quantum energy teleportation
von: Ikeda, Kazuki, et al.
Veröffentlicht: (2023)

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
von: Antonelli, Melissa, et al.
Veröffentlicht: (2026)

An elementary proof that linking problems are hard
von: Cheng, Shannon, et al.
Veröffentlicht: (2025)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
von: Gall, François Le, et al.
Veröffentlicht: (2023)

Vulnerability Abundance: A formal proof of infinite vulnerabilities in code
von: Leverett, Eireann, et al.
Veröffentlicht: (2026)

#P-hardness proofs of matrix immanants evaluated on restricted matrices
von: Miklos, Istvan, et al.
Veröffentlicht: (2021)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

A topological proof of the Hell-Nešetřil dichotomy
von: Meyer, Sebastian, et al.
Veröffentlicht: (2024)

A proof of P!=NP
von: McCallum, Rupert
Veröffentlicht: (2020)

Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
von: Liu, Yupan, et al.
Veröffentlicht: (2026)

Peaked quantum advantage using error correction
von: Deshpande, Abhinav, et al.
Veröffentlicht: (2025)

The complexity of computing in continuous time: space complexity is precision
von: Blanc, Manon, et al.
Veröffentlicht: (2024)

A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
von: Ming, Gao
Veröffentlicht: (2022)

Experimental relativistic zero-knowledge proofs with unconditional security
von: Weng, Chen-Xun, et al.
Veröffentlicht: (2025)

Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
von: Bauwens, Bruno, et al.
Veröffentlicht: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
von: Zhuk, Dmitriy
Veröffentlicht: (2024)

A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
von: Li, Jiawei, et al.
Veröffentlicht: (2024)

Quantum-proof multi-source randomness extractors in the Markov model
von: Arnon, Rotem, et al.
Veröffentlicht: (2015)

Fast polynomial computations with space constraints
von: Grenet, Bruno
Veröffentlicht: (2025)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
von: Feller, Roman, et al.
Veröffentlicht: (2024)

New proof of the Gaussian integral using the residue theorem with links to the Riemann Zeta function
von: Quemener, Bastien Jean
Veröffentlicht: (2024)

Does Subset Sum Admit Short Proofs?
von: Włodarczyk, Michał
Veröffentlicht: (2024)