Copertina

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Fritsch, Timo, Künnemann, Marvin, Redzic, Mirza, Stieß, Julian
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity F.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
di: Fischer, Nick, et al.
Pubblicazione: (2025)

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
di: Künnemann, Marvin, et al.
Pubblicazione: (2024)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
di: Xia, Mingji
Pubblicazione: (2026)

On Minimum Maximal Distance-k Matchings
di: Kartynnik, Yury, et al.
Pubblicazione: (2016)

Fine-Grained Classification Of Detecting Dominating Patterns
di: Dransfeld, Jonathan, et al.
Pubblicazione: (2025)

Thin Tree Verification is coNP-Complete
di: Moayyedi, Alice
Pubblicazione: (2025)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
di: Kiatchaipipat, Nattapol, et al.
Pubblicazione: (2025)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
di: Gupta, Chetan, et al.
Pubblicazione: (2025)

Fast Simulation of Cellular Automata by Self-Composition
di: Natal, Joseph, et al.
Pubblicazione: (2024)

A Polynomial Time Algorithm for 3SAT
di: Quigley, Robert
Pubblicazione: (2024)

Notes on CSPs and Polymorphisms
di: Brady, Zarathustra
Pubblicazione: (2022)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
di: Kowaluk, Miroslaw, et al.
Pubblicazione: (2025)

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

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
di: Sarriguren, Alfredo Goñi
Pubblicazione: (2024)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
di: Knop, Dušan, et al.
Pubblicazione: (2017)

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

On the Complexity of Determinations
di: Hellerstein, Joseph M.
Pubblicazione: (2026)

When Votes Change and Committees Should (Not)
di: Bredereck, Robert, et al.
Pubblicazione: (2020)

A Decomposition Approach to the Weighted $k$-server Problem
di: Ayyadevara, Nikhil, et al.
Pubblicazione: (2024)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
di: Bodirsky, Manuel, et al.
Pubblicazione: (2026)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
di: Bartlett, Celina Janet
Pubblicazione: (2025)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
di: Lagerkvist, Victor, et al.
Pubblicazione: (2025)

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

Complexity Classification Transfer for CSPs via Algebraic Products
di: Bodirsky, Manuel, et al.
Pubblicazione: (2022)

Graph Threading with Turn Costs
di: Demaine, Erik D., et al.
Pubblicazione: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
di: Dvořák, Pavel, et al.
Pubblicazione: (2017)

Realizing temporal graphs from fastest travel times
di: Klobas, Nina, et al.
Pubblicazione: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
di: Clinch, Katie, et al.
Pubblicazione: (2024)

Proving Unsatisfiability with Hitting Formulas
di: Filmus, Yuval, et al.
Pubblicazione: (2023)

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

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
di: Lingas, Andrzej
Pubblicazione: (2026)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
di: Liao, Chao, et al.
Pubblicazione: (2022)

Complexity of Firefighting on Graphs
di: Althoetmar, Julius, et al.
Pubblicazione: (2025)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
di: Phillips, Reed
Pubblicazione: (2026)

The Word Problem for Products of Symmetric Groups
di: Simon, Hans U.
Pubblicazione: (2025)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
di: Krithika, R., et al.
Pubblicazione: (2023)

Identity Testing for Circuits with Exponentiation Gates
di: Li, Jiatu, et al.
Pubblicazione: (2025)

Spanning Trees Minimizing Branching Costs
di: Gargano, Luisa, et al.
Pubblicazione: (2024)

On the difficulty of order constrained pattern matching with applications to feature matching based malware detection
di: Liyanage, Adiesha, et al.
Pubblicazione: (2025)

An Algorithm for a Variation of the Shortest Common Superstring Problem
di: Gilfanov, Arthur
Pubblicazione: (2024)