Image de couverture de livre

Notes on CSPs and Polymorphisms

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Brady, Zarathustra
Format:	Preprint
Publié:	2022
Sujets:	Rings and Algebras Computational Complexity Discrete Mathematics Logic in Computer Science Logic 08A70 F.2.2; F.4.1; F.1.3
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Complexity Classification Transfer for CSPs via Algebraic Products
par: Bodirsky, Manuel, et autres
Publié: (2022)

On the Satisfaction Probabilities of $k$-CNF Formulas
par: Tantau, Till
Publié: (2022)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
par: Bodirsky, Manuel, et autres
Publié: (2024)

Hardness of busy beaver value BB(15)
par: Stérin, Tristan, et autres
Publié: (2021)

Hereditary First-Order Logic: the tractable quantifier prefix classes
par: Bodirsky, Manuel, et autres
Publié: (2024)

On the Computational Power of Extensional ESO
par: Bodirsky, Manuel, et autres
Publié: (2025)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
par: de Rezende, Susanna F., et autres
Publié: (2019)

Symmetric Arithmetic Circuits
par: Dawar, Anuj, et autres
Publié: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
par: Dawar, Anuj, et autres
Publié: (2021)

Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
par: Schindling, Georg
Publié: (2025)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
par: Kazakov, Yevgeny, et autres
Publié: (2009)

Deducibility in the full Lambek calculus with weakening is HAck-complete
par: Greati, Vitor, et autres
Publié: (2024)

Hypersequent Calculi Have Ackermannian Complexity
par: Balasubramanian, A. R., et autres
Publié: (2026)

Constant time testability of first-order logic with modulo counting on finitary graphs
par: Adler, Isolde, et autres
Publié: (2026)

Polynomial definability in constraint languages with few subpowers
par: Bulín, Jakub, et autres
Publié: (2023)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
par: Bodirsky, Manuel, et autres
Publié: (2023)

Polynomial-time Tractable Problems over the $p$-adic Numbers
par: Fehm, Arno, et autres
Publié: (2025)

Semantics out of context: nominal absolute denotations for first-order logic and computation
par: Gabbay, Murdoch J.
Publié: (2013)

A correspondence between the time and space complexity
par: Latkin, Ivan V.
Publié: (2023)

Structure-Guided Automated Reasoning
par: Bannach, Max, et autres
Publié: (2023)

Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof
par: Borzechowski, Manfred, et autres
Publié: (2025)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
par: Grochow, Joshua A., et autres
Publié: (2022)

New Bounds for the Ideal Proof System in Positive Characteristic
par: Behera, Amik Raj, et autres
Publié: (2025)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
par: Iturralde, Paúl Risco
Publié: (2025)

A Complete Finitary Refinement Type System for Scott-Open Properties
par: Riba, Colin, et autres
Publié: (2026)

Introducing The Maximum Common Bigraph Problem
par: Burns, Kyle, et autres
Publié: (2026)

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic
par: Barroso-Nascimento, Victor, et autres
Publié: (2025)

Interpreting De Finetti's theorem in the Category of Integrable Cones (long version)
par: Raphaëlle, Crubillé
Publié: (2026)

One Energy Game for the Spectrum between Branching Bisimilarity and Weak Trace Semantics
par: Bisping, Benjamin, et autres
Publié: (2024)

A Fibrational Perspective on Differential Linear Logic
par: Koleilat, Jad
Publié: (2026)

On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear Logic
par: Lago, Ugo Dal, et autres
Publié: (2026)

Relational Dualities and Bisimulation
par: Kozicki, Piotr, et autres
Publié: (2026)

On bounded depth proofs for Tseitin formulas on the grid; revisited
par: Håstad, Johan, et autres
Publié: (2022)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
par: Conneryd, Jonas, et autres
Publié: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
par: de Rezende, Susanna F., et autres
Publié: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
par: de Rezende, Susanna F., et autres
Publié: (2024)

Supercritical Tradeoffs for Monotone Circuits
par: Göös, Mika, et autres
Publié: (2024)

Infinitary Refinement Types for Temporal Properties in Scott Domains
par: Riba, Colin, et autres
Publié: (2025)

Thoughts on sub-Turing interactive computability
par: Japaridze, Giorgi
Publié: (2024)

Formally Verifying the Safety of Pipelined Moonshot Consensus Protocol
par: Praveen, M., et autres
Publié: (2024)