:: 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/2503.21582
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Short and useful quantum proofs for sublogarithmic-space verifiers
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)

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

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

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

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

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

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

Improved separation between quantum and classical computers for sampling and functional tasks
by: Marshall, Simon C., et al.
Published: (2024)

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

Arity hierarchies for quantifiers closed under partial polymorphisms
by: Dawar, Anuj, et al.
Published: (2025)

Man, these New York Times games are hard! A computational perspective
by: Alberti, Alessandro Giovanni, et al.
Published: (2025)

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

Capturing the polynomial hierarchy by second-order revised Krom logic
by: Wang, Kexu, et al.
Published: (2022)

The NPA hierarchy does not always attain the commuting operator value
by: Fanizza, Marco, et al.
Published: (2025)

A universal bound on the space complexity of Directed Acyclic Graph computations
by: Bilardi, Gianfranco, et al.
Published: (2024)

A full dichotomy for Holant$^c$, inspired by quantum computation
by: Backens, Miriam
Published: (2022)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Whether a quantum computation employs nonlocal resources is operationally undecidable
by: Fields, Chris, et al.
Published: (2025)

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
by: Ikenmeyer, Christian, et al.
Published: (2022)

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
by: Sakamoto, Kazuki, et al.
Published: (2025)

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

On the computational power of $C$-random strings
by: Milovanov, Alexey
Published: (2024)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

Limit on the computational power of $\mathrm{C}$-random strings
by: Milovanov, Alexey
Published: (2026)

On the power of counting the total number of computation paths of NPTMs
by: Bakali, Eleni, et al.
Published: (2023)

The computational two-way quantum capacity
by: Meyer, Johannes Jakob, et al.
Published: (2026)

The computational power of discrete chemical reaction networks with bounded executions
by: Doty, David, et al.
Published: (2024)

A computing machinery using a continuous memory tape
by: Oktar, Yigit
Published: (2023)

Stochastic thermodynamics of computation
by: Wolpert, David H.
Published: (2019)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
by: Colli, Giordano
Published: (2025)

Robust and optimal loading of general classical data into quantum computers
by: Zhang, Xiao-Ming
Published: (2024)

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

Geometric and computational hardness of bilevel programming
by: Bolte, Jérôme, et al.
Published: (2024)

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

Quantum computation with indefinite causal structures
by: Araújo, Mateus, et al.
Published: (2017)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Is a LOCAL algorithm computable?
by: Cruciani, Antonio, et al.
Published: (2026)

Unifying computational entropies via Kullback-Leibler divergence
by: Agrawal, Rohit, et al.
Published: (2019)