Image de couverture de livre

Quantum Time-Space Tradeoffs for Matrix Problems

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Beame, Paul, Kornerup, Niels, Whitmeyer, Michael
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity Quantum Physics 68Q17 F.2.3
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

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

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
par: Rossman, Benjamin
Publié: (2024)

Quantum Sabotage Complexity
par: Cornelissen, Arjan, et autres
Publié: (2024)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
par: von Liechtenstein, Maximilian R. P.
Publié: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
par: Bodnar, Levente
Publié: (2024)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
par: Susukita, Kosuke, et autres
Publié: (2026)

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

Finitely (In)tractable Promise Constraint Satisfaction Problems
par: Asimi, Kristina, et autres
Publié: (2020)

Generalisations of Matrix Partitions : Complexity and Obstructions
par: Barsukov, Alexey, et autres
Publié: (2021)

Limitation of Quantum Walk Approach to the Maximum Matching Problem
par: Júnior, Alcides Gomes Andrade, et autres
Publié: (2025)

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

Quantum walks through generalized graph composition
par: Cornelissen, Arjan
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)

Completeness classes in algebraic complexity theory
par: Bürgisser, Peter
Publié: (2024)

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

Separation of PSPACE and EXP
par: Czerwinski, Reiner
Publié: (2021)

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

On the computational complexity of Data Flow Analysis
par: Sood, Gaurav, et autres
Publié: (2013)

Shifted Partial Derivative Polynomial Rank and Codimension
par: Edwards, Darren J.
Publié: (2025)

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)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
par: Ye, Lixi
Publié: (2026)

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

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

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

The Polynomial Hierarchy does not collapse
par: Czerwinski, Reiner
Publié: (2024)

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

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

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

Quantum Lower Bounds by Sample-to-Query Lifting
par: Wang, Qisheng, et autres
Publié: (2023)

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)

I/O complexity and pebble games with partial computations
par: Sobczyk, Aleksandros
Publié: (2024)

Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization
par: Vidakovic, Brani
Publié: (2025)

A correspondence between the time and space complexity
par: Latkin, Ivan V.
Publié: (2023)

Hive is PSPACE-Hard
par: Andel, Daniël, et autres
Publié: (2025)

The Computational Complexity of Variational Inequalities and Applications in Game Theory
par: Kapron, Bruce M., et autres
Publié: (2024)

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

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