Copertina

On the Complexity of Determinations

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Hellerstein, Joseph M.
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity F.1.3; F.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Lower Bounds for CSP Hierarchies Through Ideal Reduction
di: Conneryd, Jonas, et al.
Pubblicazione: (2025)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
di: Salas, Jesus
Pubblicazione: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
di: Conneryd, Jonas, et al.
Pubblicazione: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
di: Håstad, Johan, et al.
Pubblicazione: (2022)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
di: de Rezende, Susanna F., et al.
Pubblicazione: (2024)

Supercritical Tradeoffs for Monotone Circuits
di: Göös, Mika, et al.
Pubblicazione: (2024)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
di: de Rezende, Susanna F., et al.
Pubblicazione: (2019)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
di: Anand, Emile, et al.
Pubblicazione: (2024)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
di: Saha, Barna, et al.
Pubblicazione: (2024)

On the Satisfaction Probabilities of $k$-CNF Formulas
di: Tantau, Till
Pubblicazione: (2022)

Battle Sheep is PSPACE-complete
di: Burke, Kyle, et al.
Pubblicazione: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2024)

On the Complexity of Problems on Graphs Defined on Groups
di: Das, Bireswar, et al.
Pubblicazione: (2025)

NP-hardness of p-adic linear regression
di: Baker, Gregory D.
Pubblicazione: (2026)

Quantum algorithms through graph composition
di: Cornelissen, Arjan
Pubblicazione: (2025)

Quantum walks through generalized graph composition
di: Cornelissen, Arjan
Pubblicazione: (2025)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
di: Burke, Kyle, et al.
Pubblicazione: (2024)

Col is PSPACE-complete on Triangular Grids
di: Burke, Kyle, et al.
Pubblicazione: (2025)

Anyone but Him: The Complexity of Precluding an Alternative
di: Hemaspaandra, Edith, et al.
Pubblicazione: (2005)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
di: Antonelli, Melissa, et al.
Pubblicazione: (2025)

Quoridor is PSPACE-Complete
di: Drop, Marius, et al.
Pubblicazione: (2026)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
di: Pavlov, Gorgi
Pubblicazione: (2026)

Nonuniform Deterministic Finite Automata over finite algebraic structures
di: Idziak, Paweł M., et al.
Pubblicazione: (2025)

Arithmetic Complexity of Solutions of the Dirichlet Problem
di: Boche, Holger, et al.
Pubblicazione: (2026)

Algorithmic hardness of the partition function for nucleic acid strands
di: Ducloz, Gwendal, et al.
Pubblicazione: (2025)

Graph-Based Deterministic Polynomial Framwork for NP Problems
di: Lee, Changryeol
Pubblicazione: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
di: Kelley, Zander, et al.
Pubblicazione: (2023)

Search versus Search for Collapsing Electoral Control Types
di: Carleton, Benjamin, et al.
Pubblicazione: (2022)

Direct Sums for Parity Decision Trees
di: Besselman, Tyler, et al.
Pubblicazione: (2024)

Hive is PSPACE-Hard
di: Andel, Daniël, et al.
Pubblicazione: (2025)

Lower Bounds for Symmetric Circuits for the Determinant
di: Dawar, Anuj, et al.
Pubblicazione: (2021)

Imperative process algebra and models of computation
di: Middelburg, C. A.
Pubblicazione: (2022)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
di: van Brügge, Jan
Pubblicazione: (2024)

Quantum Sabotage Complexity
di: Cornelissen, Arjan, et al.
Pubblicazione: (2024)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
di: Grochow, Joshua A., et al.
Pubblicazione: (2025)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
di: Wulf, Lasse
Pubblicazione: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
di: Bodnar, Levente
Pubblicazione: (2024)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
di: Lela, Marko
Pubblicazione: (2025)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
di: Anand, Emile
Pubblicazione: (2025)