SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set

• URL: http://arxiv.org/abs/2604.19947v1
• Date: Tue, 21 Apr 2026 19:50:20 GMT
• Title: SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set
• Abstract summary: We present a search for small Kochen-Specker (KS) sets in dimension 3.<n>We target extensions of the 13-ray Yu-Oh set, which has been proven to be the minimal witness to state-independent contextuality.
• Score: 9.824030987991497
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a search for small Kochen-Specker (KS) sets in dimension 3, specifically targeting extensions of the 13-ray Yu-Oh set, which has been proven to be the minimal witness to state-independent contextuality. To enable this search, we introduce a novel SAT-based orderly generation framework integrating recursive canonical labeling (RCL) with the graph isomorphism tool NAUTY. We demonstrate that previous SAT approaches relying on lexicographical canonicity suffer from exponential scaling on canonical graphs. This limitation renders them intractable on the large instances (25 to 33 vertices) encountered in our search, whereas our RCL check maintains consistent millisecond-level performance, effectively eliminating the bottleneck. Overcoming this bottleneck allows us to perform the first exhaustive enumeration of all KS sets with up to 33 rays containing the complete 25-ray state-independent contextuality (SI-C) set obtained by rigid extensions of the Yu-Oh set in 1,641 CPU hours. We found and verified that the 33-ray set discovered by Schütte is the smallest three-dimensional KS set containing the complete 25-ray SI-C set. All non-existence results are backed by independently verifiable proof certificates via an extension of the DRAT proof format.

Related papers

• Real-Time Video Anomaly Detection Using YOLO Pose Estimation and CLIP-Based Semantic Scoring [0.3784545047113015]
  We propose a lightweight two-stage framework for real-time video anomaly detection.<n>The first stage employs YOLO v11n-pose to detect persons and extract seventeen skeletal keypoints in a single forward pass.<n>The second stage encodes each cropped person region through CLIP ViT-B/32 and computes cosine similarity.
  arXiv  Detail & Related papers  (2026-08-31T16:47:29Z)
• When Do Supervised UQ Ensembles Improve LLM Hallucination Detection? A Robustness Study [0.0]
  Uncertainty quantification (UQ) methods are widely used for hallucination detection in large language models (LLMs)<n>We study a supervised ensembling framework that trains a classifier over heterogeneous UQ-based scorer outputs.<n>We find that supervised ensembles outperform the best individual scorer in 30 of 32 settings, with gains realized from as few as 100 labeled instances.
  arXiv  Detail & Related papers  (2026-08-25T12:43:07Z)
• Finding Belief Geometries with Sparse Autoencoders [0.0]
  We introduce a pipeline for discovering candidate simplex-structured subspaces in transformer representations.<n>We validate the pipeline on a transformer trained on a hidden Markov model with known belief-state geometry.<n>Preliminary evidence that genuine belief-like geometry exists in Gemma-2-9B's representation space.
  arXiv  Detail & Related papers  (2026-04-03T03:29:48Z)
• On Simplest Kochen-Specker Sets [0.0]
  We analyze the meaning, origin, and significance of the simplest contextual sets in any dimension.<n>We show that automatic generation of contextual sets from basic vector components automatically yields all known minimal contextual sets of any kind in any dimension.<n>In the end, we discuss varieties of contextual sets, in particular Kochen-Specker (KS), extended KS, and non-KS sets as well as ambiguities in their definitions.
  arXiv  Detail & Related papers  (2025-12-11T10:01:34Z)
• Grouping Nodes With Known Value Differences: A Lossless UCT-based Abstraction Algorithm [64.43268969806098]
  A core challenge of Monte Carlo Tree Search (MCTS) is its sample efficiency, which can be improved by grouping state-action pairs.<n>We break with the paradigm of grouping value-equivalent states or state-action pairs and instead group states and state-action pairs with possibly different values.<n>We call this abstraction framework Known Value Difference Abstractions ( KVDA), which infers the value differences by analysis of the immediate rewards.
  arXiv  Detail & Related papers  (2025-10-29T11:03:44Z)
• CLUE: Non-parametric Verification from Experience via Hidden-State Clustering [64.50919789875233]
  We show that correctness of a solution is encoded as a geometrically separable signature within the trajectory of hidden activations.<n>ClUE consistently outperforms LLM-as-a-judge baselines and matches or exceeds modern confidence-based methods in reranking candidates.
  arXiv  Detail & Related papers  (2025-10-02T02:14:33Z)
• Light-SQ: Structure-aware Shape Abstraction with Superquadrics for Generated Meshes [60.92139345612904]
  We present Light-SQ, a novel superquadric-based optimization framework.<n>We propose a block-regrow-fill strategy guided by structure-aware volumetric decomposition.<n>Experiments demonstrate that Light-SQ enables efficient, high-fidelity, and editable shape abstraction with superquadrics.
  arXiv  Detail & Related papers  (2025-09-29T16:18:32Z)
• SeqCSIST: Sequential Closely-Spaced Infrared Small Target Unmixing [7.09321729956876]
  We propose a novel task, Sequential CSIST Unmixing, for detecting all targets in the form of sub-pixel localization from a highly dense CSIST group.<n>We contribute an open-source ecosystem, including SeqCSIST, a sequential benchmark dataset, and a toolkit that provides objective evaluation metrics for this special task.<n>Our method outperforms the state-of-the-art approaches with mean Average Precision (mAP) metric improved by 5.3%.
  arXiv  Detail & Related papers  (2025-07-13T09:59:48Z)
• Two fundamental solutions to the rigid Kochen-Specker set problem and the solution to the minimal Kochen-Specker set problem under one assumption [0.0]
  We show that two fundamental structures of quantum theory define two rigid KS sets.<n>The second construction provides a clue to solve the minimal KS problem.<n>We conjecture that 31 is the solution to the minimal KS set problem.
  arXiv  Detail & Related papers  (2025-01-20T18:13:28Z)
• ExpressivE: A Spatio-Functional Embedding For Knowledge Graph Completion [78.8942067357231]
  ExpressivE embeds pairs of entities as points and relations as hyper-parallelograms in the virtual triple space. We show that ExpressivE is competitive with state-of-the-art KGEs and even significantly outperforms them on W18RR.
  arXiv  Detail & Related papers  (2022-06-08T23:34:39Z)
• Accelerating DETR Convergence via Semantic-Aligned Matching [50.3633635846255]
  This paper presents SAM-DETR, a Semantic-Aligned-Matching DETR that greatly accelerates DETR's convergence without sacrificing its accuracy. It explicitly searches salient points with the most discriminative features for semantic-aligned matching, which further speeds up the convergence and boosts detection accuracy as well.
  arXiv  Detail & Related papers  (2022-03-14T06:50:51Z)
• Tensor Representations for Action Recognition [54.710267354274194]
  Human actions in sequences are characterized by the complex interplay between spatial features and their temporal dynamics. We propose novel tensor representations for capturing higher-order relationships between visual features for the task of action recognition. We use higher-order tensors and so-called Eigenvalue Power Normalization (NEP) which have been long speculated to perform spectral detection of higher-order occurrences.
  arXiv  Detail & Related papers  (2020-12-28T17:27:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.