Copertina

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Geniet, Colin, Goubault-Larrecq, Aliénor, Perrot, Kévin
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Discrete Mathematics Logic in Computer Science
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Rice-like complexity lower bounds for Boolean and uniform automata networks
di: Goubault-Larrecq, Aliénor, et al.
Pubblicazione: (2024)

Hardness of monadic second-order formulae over succinct graphs
di: Gamard, Guilhem, et al.
Pubblicazione: (2023)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
di: Goubault-Larrecq, Aliénor, et al.
Pubblicazione: (2025)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
di: Zhang, Tianwei, et al.
Pubblicazione: (2024)

First-Order Logic and Twin-Width for Some Geometric Graphs
di: Geniet, Colin, et al.
Pubblicazione: (2025)

The Unit Gap: How Sharing Works in Boolean Circuits
di: Krinkin, Kirill
Pubblicazione: (2026)

Transducing Linear Decompositions of Tournaments
di: Geniet, Colin, et al.
Pubblicazione: (2026)

The Rise of Plurimorphisms: Algebraic Approach to Approximation
di: Barto, Libor, et al.
Pubblicazione: (2024)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
di: Dwivedi, Prateek, et al.
Pubblicazione: (2026)

Complexity of Boolean automata networks under block-parallel update modes
di: Perrot, Kévin, et al.
Pubblicazione: (2024)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
di: Seppelt, Tim
Pubblicazione: (2024)

Restricted CSPs and F-free Digraph Algorithmics
di: Guzmán-Pro, Santiago, et al.
Pubblicazione: (2025)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
di: Seppelt, Tim
Pubblicazione: (2023)

The Richness of CSP Non-redundancy
di: Brakensiek, Joshua, et al.
Pubblicazione: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
di: Kiefer, Sandra, et al.
Pubblicazione: (2025)

Separability Properties of Monadically Dependent Graph Classes
di: Bonnet, Édouard, et al.
Pubblicazione: (2025)

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
di: Concha-Vega, Pablo, et al.
Pubblicazione: (2025)

Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints
di: Callard, Antonin, et al.
Pubblicazione: (2024)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
di: Černý, Marek
Pubblicazione: (2026)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
di: Černý, Marek, et al.
Pubblicazione: (2025)

Smaller Circuits for Bit Addition
di: Goncharov, Mikhail, et al.
Pubblicazione: (2025)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
di: Roberson, David E., et al.
Pubblicazione: (2023)

Graph Homomorphisms and Universal Algebra
di: Bodirsky, Manuel
Pubblicazione: (2026)

Algorithmic methods of finite discrete structures. Graph clique problem
di: Kurapov, Sergey, et al.
Pubblicazione: (2024)

On the consistency of stronger lower bounds for NEXP
di: Thapen, Neil
Pubblicazione: (2025)

On the complexity of freezing automata networks of bounded pathwidth
di: Goles, Eric, et al.
Pubblicazione: (2025)

CMSO-transducing tree-like graph decompositions
di: Campbell, Rutger, et al.
Pubblicazione: (2024)

Weighted basic parallel processes and combinatorial enumeration
di: Clemente, Lorenzo
Pubblicazione: (2024)

Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
di: Adler, Isolde, et al.
Pubblicazione: (2025)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
di: Majewski, Konrad, et al.
Pubblicazione: (2021)

Hypergraph rewriting and Causal structure of $λ-$calculus
di: Bajaj, Utkarsh
Pubblicazione: (2024)

An unconditional lower bound for the active-set method on the hypercube
di: Disser, Yann, et al.
Pubblicazione: (2025)

Characterizations of monadically dependent tree-ordered weakly sparse structures
di: Buffière, Hector, et al.
Pubblicazione: (2026)

On classes of bounded tree rank, their interpretations, and efficient sparsification
di: Gajarský, Jakub, et al.
Pubblicazione: (2024)

Verifying Sampling Algorithms via Distributional Invariants
di: Zilken, Daniel, et al.
Pubblicazione: (2025)

An unconditional lower bound for the active-set method in convex quadratic maximization
di: Bach, Eleon, et al.
Pubblicazione: (2025)

Symmetric Arithmetic Circuits
di: Dawar, Anuj, et al.
Pubblicazione: (2020)

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

A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes
di: Fuchser, Janne, et al.
Pubblicazione: (2025)

Nested Sequents for Intuitionistic Grammar Logics via Structural Refinement
di: Lyon, Tim S.
Pubblicazione: (2022)