Cover Image

Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dawar, Anuj, Shah, Nihil
Format:	Preprint
Published:	2026
Subjects:	Quantum Physics Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set
by: Li, Zhengyu, et al.
Published: (2026)

The Pebble-Relation Comonad in Finite Model Theory
by: Montacute, Yoàv, et al.
Published: (2021)

Satisfiability of Quantified Boolean Announcements
by: van Ditmarsch, Hans, et al.
Published: (2022)

Linear Arboreal Categories
by: Abramsky, Samson, et al.
Published: (2023)

Satisfiability of commutative vs. non-commutative CSPs
by: Bulatov, Andrei A., et al.
Published: (2024)

GaloisSAT: Differentiable Boolean Satisfiability Solving via Finite Field Algebra
by: Kim, Curie, et al.
Published: (2026)

Rings and Boolean Algebras as Algebraic Theories
by: De Faveri, Arturo
Published: (2025)

Kochen--Specker Contextuality and the Tetralemmatic Calculus of Quantum Mechanics
by: Borom, Santos
Published: (2026)

Arity hierarchies for quantifiers closed under partial polymorphisms
by: Dawar, Anuj, et al.
Published: (2025)

A categorical account of composition methods in logic (extended version)
by: Jakl, Tomáš, et al.
Published: (2024)

Preservation Theorems in Semiring Semantics
by: Brinke, Sophie, et al.
Published: (2026)

Game Comonads & Generalised Quantifiers
by: Conghaile, Adam Ó, et al.
Published: (2020)

Preservation theorems on sparse classes revisited
by: Dawar, Anuj, et al.
Published: (2024)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

Non-Kochen-Specker Contextuality
by: Pavicic, Mladen
Published: (2023)

The simplest Kochen-Specker set
by: Cabello, Adán
Published: (2025)

Graphical Symplectic Algebra
by: Booth, Robert I., et al.
Published: (2024)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

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

On Simplest Kochen-Specker Sets
by: Pavicic, Mladen
Published: (2025)

Entailment vs. Verification for Partial-assignment Satisfiability and Enumeration
by: Sebastiani, Roberto
Published: (2025)

Basic interactive algorithms: Preview
by: Gurevich, Yuri
Published: (2025)

An algebraic characterisation of Kochen-Specker contextuality
by: Frembs, Markus
Published: (2024)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

From Partial to Monadic: Combinatory Algebra with Effects
by: Cohen, Liron, et al.
Published: (2025)

Power Term Polynomial Algebra for Boolean Logic
by: Sansone, Emanuele, et al.
Published: (2026)

Maximal Non-Kochen-Specker Sets and a Lower Bound on the Size of Kochen-Specker Sets
by: Williams, Tom, et al.
Published: (2024)

Model Checking Matrix Product States against Linear Chain Logic
by: Xu, Ming, et al.
Published: (2026)

A Complete Equational Presentation of Qudit Circuits via Polycontrolled PROPs
by: Blake, Colin
Published: (2026)

End-to-End Formalization of Quantum Error Correction
by: Ehatamm, Mattias, et al.
Published: (2026)

Simpler Presentations for Many Fragments of Quantum Circuits
by: Blake, Colin
Published: (2026)

Algebraic Structure of Quantum Controlled States and Operators
by: Agnew, Edwin, et al.
Published: (2026)

Planted-solution SAT and Ising benchmarks from integer factorization
by: Hen, Itay
Published: (2026)

A Complete Equational Theory for Real-Clifford+CH Quantum Circuits
by: Clément, Alexandre
Published: (2026)

Formalizing CHSH Rigidity in Lean 4
by: Zhao, Tianrun, et al.
Published: (2026)

Commutation Groups and State-Independent Contextuality
by: Abramsky, Samson, et al.
Published: (2026)

Formally Verifying Quantum Phase Estimation Circuits with 1,000+ Qubits
by: Govindankutty, Arun, et al.
Published: (2026)

Classical Explanations in (and of) General Probabilistic Theories
by: Harding, John, et al.
Published: (2026)

Quantum Petri Nets with Event Structures semantics
by: Joachim, Julien Saan, et al.
Published: (2025)