Copertina

Hardness of monadic second-order formulae over succinct graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Gamard, Guilhem, Goubault-Larrecq, Aliénor, Guillon, Pierre, Ohlmann, Pierre, Perrot, Kévin, Theyssier, Guillaume
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Computational Complexity Logic in Computer Science
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
di: Geniet, Colin, et al.
Pubblicazione: (2026)

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

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

A positional $\mathbfΠ^0_3$-complete objective
di: Casares, Antonio, et al.
Pubblicazione: (2024)

On the Dynamics of Bounded-Degree Automata Networks
di: Aracena, Julio, et al.
Pubblicazione: (2025)

Capturing the polynomial hierarchy by second-order revised Krom logic
di: Wang, Kexu, et al.
Pubblicazione: (2022)

Trees in graphs of large linear cliquewidth
di: Bojańczyk, Mikołaj, et al.
Pubblicazione: (2025)

Hard Clique Formulas for Resolution
di: Atserias, Albert
Pubblicazione: (2026)

Flipper games for monadically stable graph classes
di: Gajarský, Jakub, et al.
Pubblicazione: (2023)

An order out of nowhere: a new algorithm for infinite-domain CSPs
di: Mottet, Antoine, et al.
Pubblicazione: (2023)

Complete and tractable machine-independent characterizations of second-order polytime
di: Hainry, Emmanuel, et al.
Pubblicazione: (2022)

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
di: Krebs, Andreas, 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)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
di: Amir, Guy, et al.
Pubblicazione: (2024)

Complexity classification of counting graph homomorphisms modulo a prime number
di: Bulatov, Andrei A., et al.
Pubblicazione: (2021)

Solving promise equations over monoids and groups
di: Larrauri, Alberto, et al.
Pubblicazione: (2024)

FO logic on cellular automata orbits equals MSO logic
di: Theyssier, Guillaume
Pubblicazione: (2024)

Positionality in $Σ_0^2$ and a completeness result
di: Ohlmann, Pierre, et al.
Pubblicazione: (2023)

Rank-decreasing transductions
di: Bojańczyk, Mikołaj, et al.
Pubblicazione: (2024)

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

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
di: Nechesov, Andrey
Pubblicazione: (2024)

Proof Complexity of Linear Logics
di: Tabatabai, Amirhossein Akbar, et al.
Pubblicazione: (2026)

The Proof Analysis Problem
di: Arteche, Noel, et al.
Pubblicazione: (2025)

Proof complexity of positive branching programs
di: Das, Anupam, et al.
Pubblicazione: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
di: Ježil, Ondřej, et al.
Pubblicazione: (2026)

Effective Versions of Strong Measure Zero
di: Rayman, Matthew
Pubblicazione: (2025)

The complete classification for quantified equality constraints
di: Zhuk, Dmitriy, et al.
Pubblicazione: (2021)

Meta-Mathematics of Computational Complexity Theory
di: Oliveira, Igor C.
Pubblicazione: (2025)

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

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
di: Atserias, Albert, et al.
Pubblicazione: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
di: Zhuk, Dmitriy
Pubblicazione: (2024)

Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations
di: Blanc, Manon, et al.
Pubblicazione: (2023)

Hard QBFs for Merge Resolution
di: Beyersdorff, Olaf, et al.
Pubblicazione: (2020)

Just Previsions
di: Goubault-Larrecq, Jean
Pubblicazione: (2026)

Semitopological Barycentric Algebras
di: Goubault-Larrecq, Jean
Pubblicazione: (2025)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
di: Khalife, Sammy, et al.
Pubblicazione: (2024)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
di: Halftermeyer, Pierre
Pubblicazione: (2026)

Spectra of Cardinality Queries over Description Logic Knowledge Bases
di: Manière, Quentin, et al.
Pubblicazione: (2024)

Local consistency as a reduction between constraint satisfaction problems
di: Dalmau, Victor, et al.
Pubblicazione: (2023)