Copertina

Collapsing Catalytic Classes

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Koucký, Michal, Mertz, Ian, Pyne, Edward, Sami, Sasha
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Understanding Robust Catalytic Computing
di: Koucký, Michal, et al.
Pubblicazione: (2026)

Frontier Space-Time Algorithms Using Only Full Memory
di: Chmel, Petr, et al.
Pubblicazione: (2026)

Efficient Catalytic Graph Algorithms
di: Cook, James, et al.
Pubblicazione: (2025)

The Structure of In-Place Space-Bounded Computation
di: Cook, James, et al.
Pubblicazione: (2025)

Bipartite Matching is in Catalytic Logspace
di: Agarwala, Aryan, et al.
Pubblicazione: (2025)

Fully Characterizing Lossy Catalytic Computation
di: Folkertsma, Marten, et al.
Pubblicazione: (2024)

Catalytic Computing and Register Programs Beyond Log-Depth
di: Alekseev, Yaroslav, et al.
Pubblicazione: (2025)

A Fast Coloring Oracle for Average Case Hypergraphs
di: Marcussen, Cassandra, et al.
Pubblicazione: (2025)

Lossy Catalytic Computation
di: Gupta, Chetan, et al.
Pubblicazione: (2024)

Derandomizing Isolation In Catalytic Logspace
di: Arvind, V., et al.
Pubblicazione: (2025)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
di: Bhattacharya, Sudatta, et al.
Pubblicazione: (2025)

Maximum Matching and Related Problems in Catalytic Logspace
di: Chakraborty, Srijan, et al.
Pubblicazione: (2026)

Topological Collapse: P = NP Implies #P = FP via Solution-Space Homology
di: Alasli, M.
Pubblicazione: (2026)

The Entangled Quantum Polynomial Hierarchy Collapses
di: Grewal, Sabee, et al.
Pubblicazione: (2024)

The Complexity of Logarithmic Space Bounded Counting Classes
di: Vijayaraghavan, T. C.
Pubblicazione: (2025)

On the Parameterized Complexity of Semitotal Domination on Graph Classes
di: Retschmeier, Lukas
Pubblicazione: (2025)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
di: Orzel, Ian
Pubblicazione: (2025)

Low Sets and Closure Properties of Counting Function Classes
di: Ivanashev, Yaroslav
Pubblicazione: (2025)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2025)

Structure in Communication Complexity and Constant-Cost Complexity Classes
di: Hatami, Hamed, et al.
Pubblicazione: (2024)

On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes
di: Kolář, Martin
Pubblicazione: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
di: Przybyłek, Michał R., et al.
Pubblicazione: (2026)

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
di: Gay, William, et al.
Pubblicazione: (2026)

Coherence in Property Testing: Quantum-Classical Collapses and Separations
di: Jeronimo, Fernando Granha, et al.
Pubblicazione: (2024)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
di: Ostonov, Azimkhon, et al.
Pubblicazione: (2024)

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
di: Nagy, Tomáš, et al.
Pubblicazione: (2025)

On the Complexity of Target Set Selection in Simple Geometric Networks
di: Dvořák, Michal, et al.
Pubblicazione: (2023)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
di: Miloschewsky, David, et al.
Pubblicazione: (2024)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
di: Ostonov, Azimkhon, et al.
Pubblicazione: (2023)

Minimum Selective Subset on Some Graph Classes
di: Manna, Bubai
Pubblicazione: (2025)

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

A note on Jerabek's paper "A simplified lower bound for implicational logic"
di: Gordeev, Lev, et al.
Pubblicazione: (2026)

On Bounded Advice Classes
di: Marshall, Simon, et al.
Pubblicazione: (2024)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
di: Grüne, Christoph
Pubblicazione: (2022)

New Direct Sum Tests
di: Westover, Alek, et al.
Pubblicazione: (2024)

Uniformity within Parameterized Circuit Classes
di: Hegeman, Steef, et al.
Pubblicazione: (2025)

Testing for Renamability to Classes of Clause Sets
di: Brandl, Albert, et al.
Pubblicazione: (2025)

Structural Origin and the Minimal Syntax of NP-Hardness: Analysis of SAT from Syntactic Generativity and Compositional Collapse
di: Nishiyama, Yumiko
Pubblicazione: (2025)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
di: Garg, Abhibhav, et al.
Pubblicazione: (2025)

On the Complexity of Problems on Tree-structured Graphs
di: Bodlaender, Hans L., et al.
Pubblicazione: (2022)