:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Say, A. C. Cem
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2601.16695
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)

Short and useful quantum proofs for sublogarithmic-space verifiers
by: Say, A. C. Cem
Published: (2025)

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)

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

The vast world of quantum advantage
by: Huang, Hsin-Yuan, et al.
Published: (2025)

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

Has quantum advantage been achieved?
by: Hangleiter, Dominik
Published: (2026)

Entanglement-induced provable and robust quantum learning advantages
by: Zhao, Haimeng, et al.
Published: (2024)

Estimates of the modulus of continuity of the logarithmic double layer potential in the closure of domain
by: Plaksa, Sergiy, et al.
Published: (2026)

Quantum information advantage based on Bell inequalities
by: Jain, Rahul, et al.
Published: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

No distributed quantum advantage for approximate graph coloring
by: Coiteux-Roy, Xavier, et al.
Published: (2023)

Fine-grained Meta-Theorems for Vertex Integrity
by: Lampis, Michael, et al.
Published: (2021)

Exponential quantum advantage in processing massive classical data
by: Zhao, Haimeng, et al.
Published: (2026)

Quantum advantage from random geometrically-two-local Hamiltonian dynamics
by: Quek, Yihui
Published: (2025)

Efficient Pauli channel estimation with logarithmic quantum memory
by: Chen, Sitan, et al.
Published: (2023)

The continuous extension of the logarithmic double layer potential to the Ahlfors-regular boundary
by: Plaksa, Sergiy
Published: (2024)

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
by: Pirnay, Niklas, et al.
Published: (2022)

Quantum state testing beyond the polarizing regime and quantum triangular discrimination
by: Liu, Yupan
Published: (2023)

The closure of derivative tent spaces in the logarithmic Bloch-type norm
by: Yang, Rong, 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)

Quantum advantage from measurement-induced entanglement in random shallow circuits
by: Watts, Adam Bene, et al.
Published: (2024)

Direct sum theorems beyond query complexity
by: Suruga, Daiki
Published: (2024)

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
by: Alman, Josh, et al.
Published: (2023)

Approximate cycle double cover
by: Ghanbari, Babak, et al.
Published: (2025)

A learning theory for quantum photonic processors and beyond
by: Rosati, Matteo
Published: (2022)

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

Closing the complexity gap of the double distance problem
by: Cunha, Luís, et al.
Published: (2024)

Compilation and Fast Model Counting beyond CNF
by: de Colnet, Alexis, et al.
Published: (2025)

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

Tight Fine-Grained Bounds for Direct Access on Join Queries
by: Bringmann, Karl, et al.
Published: (2022)

On the logarithmic coefficients of Ma-Minda type convex functions
by: Ali, Md Firoz, et al.
Published: (2026)

Moduli difference of inverse logarithmic coefficients of univalent functions
by: Allu, Vasudevarao, et al.
Published: (2024)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

On the logarithmic terms in the asymptotic expansion of integrals
by: Hennings, Achim
Published: (2026)

On the monodromy map for the logarithmic differential systems
by: Aprodu, Marian, et al.
Published: (2022)

Fine-Grained Complexity via Quantum Natural Proofs
by: Chen, Yanlin, et al.
Published: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)