:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Say, A. C. Cem
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2505.08462
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Time hierarchies for sublogarithmic-space quantum computation
by: Say, A. C. Cem
Published: (2025)

Fine-grained quantum advantage beyond double-logarithmic space
by: Say, A. C. Cem
Published: (2026)

Unconditional proofs of quantumness between small-space machines
by: Say, A. C. Cem, et al.
Published: (2024)

$\rm P$ has polynomial-time finite-state verifiers
by: Gezer, M. Utkan, et al.
Published: (2023)

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
by: Gezer, M. Utkan, et al.
Published: (2020)

Interactive proofs for verifying (quantum) learning and testing
by: Caro, Matthias C., et al.
Published: (2024)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
by: Liu, Zhenning, et al.
Published: (2024)

How hard is it to verify a classical shadow?
by: Karaiskos, Georgios, et al.
Published: (2025)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

Space-bounded quantum interactive proof systems
by: Gall, François Le, et al.
Published: (2024)

The Role of piracy in quantum proofs
by: Broadbent, Anne, et al.
Published: (2024)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
by: Anand, Kartik, et al.
Published: (2025)

Quantum Merlin-Arthur proof systems for synthesizing quantum states
by: Delavenne, Hugo, et al.
Published: (2023)

Quantum interactive proofs using quantum energy teleportation
by: Ikeda, Kazuki, et al.
Published: (2023)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

Lower bounds for set-blocked clauses proofs
by: Yolcu, Emre
Published: (2024)

Quantum Merlin-Arthur with an internally separable proof
by: Bassirian, Roozbeh, et al.
Published: (2024)

An elementary proof that linking problems are hard
by: Cheng, Shannon, et al.
Published: (2025)

On the Need for (Quantum) Memory with Short Outputs
by: Hao, Zihan, et al.
Published: (2026)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

A proof of P!=NP
by: McCallum, Rupert
Published: (2020)

Vulnerability Abundance: A formal proof of infinite vulnerabilities in code
by: Leverett, Eireann, et al.
Published: (2026)

#P-hardness proofs of matrix immanants evaluated on restricted matrices
by: Miklos, Istvan, et al.
Published: (2021)

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

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

A topological proof of the Hell-Nešetřil dichotomy
by: Meyer, Sebastian, et al.
Published: (2024)

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

Peaked quantum advantage using error correction
by: Deshpande, Abhinav, et al.
Published: (2025)

Experimental relativistic zero-knowledge proofs with unconditional security
by: Weng, Chen-Xun, et al.
Published: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
by: Zhuk, Dmitriy
Published: (2024)

Quantum-proof multi-source randomness extractors in the Markov model
by: Arnon, Rotem, et al.
Published: (2015)

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

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

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

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
by: Feller, Roman, et al.
Published: (2024)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
by: Li, Jiawei, et al.
Published: (2024)

Fast polynomial computations with space constraints
by: Grenet, Bruno
Published: (2025)

Does Subset Sum Admit Short Proofs?
by: Włodarczyk, Michał
Published: (2024)

New proof of the Gaussian integral using the residue theorem with links to the Riemann Zeta function
by: Quemener, Bastien Jean
Published: (2024)