Image de couverture de livre

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Phillips, Reed
Format:	Preprint
Publié:	2026
Sujets:	Computational Complexity 68Q12 F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Quantum algorithms through graph composition
par: Cornelissen, Arjan
Publié: (2025)

Quantum walks through generalized graph composition
par: Cornelissen, Arjan
Publié: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
par: Xia, Mingji
Publié: (2026)

The Word Problem for Products of Symmetric Groups
par: Simon, Hans U.
Publié: (2025)

On Small-depth Frege Proofs for PHP
par: Håstad, Johan
Publié: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
par: Levin, Leonid A.
Publié: (2022)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
par: Eua-anant, Pakapim, et autres
Publié: (2025)

How to compute the volume in low dimension?
par: Cornelissen, Arjan, et autres
Publié: (2025)

DAG Scheduling in the BSP Model
par: Papp, Pál András, et autres
Publié: (2023)

Explicit separations between randomized and deterministic Number-on-Forehead communication
par: Kelley, Zander, et autres
Publié: (2023)

NP-hard problems are not in BQP
par: Czerwinski, Reiner
Publié: (2023)

Character Complexity: A Novel Measure for Quantum Circuit Analysis
par: Shami, Daksh
Publié: (2024)

Quantum Advantage in Computational Chemistry?
par: Gundlach, Hans, et autres
Publié: (2025)

Computational Complexity of Determining the Assembly Index
par: Masierak, Piotr
Publié: (2026)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
par: Böhnlein, Toni, et autres
Publié: (2024)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
par: Grochow, Joshua A., et autres
Publié: (2021)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
par: Lela, Marko
Publié: (2025)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
par: Grochow, Joshua A., et autres
Publié: (2025)

Induced Disjoint Paths Without an Induced Minor
par: Aboulker, Pierre, et autres
Publié: (2025)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
par: Jansen, Klaus, et autres
Publié: (2024)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
par: Dorochko, Leonid, et autres
Publié: (2026)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
par: Lela, Marko
Publié: (2025)

Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
par: Kornerup, Niels, et autres
Publié: (2021)

The Optimizer Quotient and the Certification Trilemma
par: Simas, Tristan
Publié: (2026)

NP-hardness of p-adic linear regression
par: Baker, Gregory D.
Publié: (2026)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
par: Bodirsky, Manuel, et autres
Publié: (2024)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
par: Hakoniemi, Tuomas, et autres
Publié: (2024)

Quantum Search without Global Diffusion
par: Burke, John, et autres
Publié: (2026)

Counting Martingales for Measure and Dimension in Complexity Classes
par: Hitchcock, John M., et autres
Publié: (2025)

Evolomino is NP-complete
par: Nikolaev, Andrei V.
Publié: (2025)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
par: Saffidine, Abdallah, et autres
Publié: (2025)

Quoridor is PSPACE-Complete
par: Drop, Marius, et autres
Publié: (2026)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
par: Jain, Rahul, et autres
Publié: (2019)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
par: Liao, Chao, et autres
Publié: (2022)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
par: Lobe, Elisabeth, et autres
Publié: (2021)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
par: Lela, Marko
Publié: (2025)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
par: Lagerkvist, Victor, et autres
Publié: (2026)

Count-Free Weisfeiler--Leman and Group Isomorphism
par: Collins, Nathaniel A., et autres
Publié: (2022)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
par: Chen, Yijia, et autres
Publié: (2023)

Bounded Distance Decoding for Random Lattices
par: Gao, Shuhong
Publié: (2025)