Buchumschlag

Fully Characterizing Lossy Catalytic Computation

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Folkertsma, Marten, Mertz, Ian, Speelman, Florian, Tupker, Quinten
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity 68Q15
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
von: Lin, Tianrong
Veröffentlicht: (2023)

The Separation of $NP$ and $PSPACE$
von: Lin, Tianrong
Veröffentlicht: (2021)

Linear Matroid Intersection is in Catalytic Logspace
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
von: Hu, Ivan, et al.
Veröffentlicht: (2022)

Some derivations among Logarithmic Space Bounded Counting Classes
von: Janaki, V., et al.
Veröffentlicht: (2023)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
von: Edwards, Darren J.
Veröffentlicht: (2025)

Unifying lower bounds for algebraic machines, semantically
von: Seiller, Thomas, et al.
Veröffentlicht: (2018)

Quantum Catalytic Space
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

Weighted Automata and Logics Meet Computational Complexity
von: Kostolányi, Peter
Veröffentlicht: (2023)

Completeness classes in algebraic complexity theory
von: Bürgisser, Peter
Veröffentlicht: (2024)

Beyond the Existential Theory of the Reals
von: Schaefer, Marcus, et al.
Veröffentlicht: (2022)

The Complexity of Iterated Reversible Computation
von: Eppstein, David
Veröffentlicht: (2021)

Counting Martingales for Measure and Dimension in Complexity Classes
von: Hitchcock, John M., et al.
Veröffentlicht: (2025)

Resolution of The Linear-Bounded Automata Question
von: Lin, Tianrong
Veröffentlicht: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
von: Lin, Tianrong
Veröffentlicht: (2021)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
von: Abdullah, Duaa, et al.
Veröffentlicht: (2025)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
von: Tzameret, Iddo, et al.
Veröffentlicht: (2023)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
von: Lin, Tianrong
Veröffentlicht: (2024)

Meta Theorem for Hardness on FCP-Problem
von: Nagao, Atsuki, et al.
Veröffentlicht: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
von: Hirsch, Edward A., et al.
Veröffentlicht: (2025)

Oracle Separations for RPH
von: Hamm, Thekla, et al.
Veröffentlicht: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
von: Göös, Mika, et al.
Veröffentlicht: (2025)

A Note on Avoid vs MCSP
von: Hirsch, Edward A., et al.
Veröffentlicht: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
von: Garcia, Baruch
Veröffentlicht: (2026)

Computational Complexity of Model-Checking Quantum Pushdown Systems
von: Lin, Deren, et al.
Veröffentlicht: (2025)

On the Low Weight Polynomial Multiple Problem
von: Ţiplea, Ferucio Laurenţiu, et al.
Veröffentlicht: (2024)

Generalisations of Matrix Partitions : Complexity and Obstructions
von: Barsukov, Alexey, et al.
Veröffentlicht: (2021)

Recent Advances in Debordering Methods
von: Dutta, Pranjal, et al.
Veröffentlicht: (2025)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
von: Zhang, Weikun K., et al.
Veröffentlicht: (2026)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
von: Shalunov, Yakov
Veröffentlicht: (2023)

The Optimizer Quotient and the Certification Trilemma
von: Simas, Tristan
Veröffentlicht: (2026)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
von: Ahn, Jungho, et al.
Veröffentlicht: (2022)

A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems
von: Duchnowski, Alex, et al.
Veröffentlicht: (2025)

Computational Complexity of Determining the Assembly Index
von: Masierak, Piotr
Veröffentlicht: (2026)

No Constant-Cost Protocol for Point--Line Incidence
von: Göös, Mika, et al.
Veröffentlicht: (2026)

Barriers for rectangular matrix multiplication
von: Christandl, Matthias, et al.
Veröffentlicht: (2020)

The Self-Replication Phase Diagram: Mapping Where Life Becomes Possible in Cellular Automata Rule Space
von: Yin, Don
Veröffentlicht: (2026)

Shifted Partial Derivative Polynomial Rank and Codimension
von: Edwards, Darren J.
Veröffentlicht: (2025)

A study of distributional complexity measures for Boolean functions
von: Köhler-Schindler, Laurin, et al.
Veröffentlicht: (2024)

P not equal to NP
von: Delgado, Daniel Cardona
Veröffentlicht: (2023)