CS Paper Radar

Choosing What to Observe: Higher-Order Obstructions in Horn Abduction

Yukun Yang

cs.LO ·submitted 2026-10-23 15:44 UTC · v1

Abstract

An explanation may exist in every complete context yet be impossible to select from the information observed. We study this distinction in finite propositional Horn abduction with integrity constraints. Observations are sufficient when each report admits one hypothesis set that is consistent and entails the manifestation in every compatible context. We characterize sufficiency by minimal context families with no common explanation. Their variable spans form a canonical hypergraph whose transversals are exactly the sufficient observation sets. The characterization recovers classical discernibility for unique explanations and supports composition across independent components. Minimal obstructions have unbounded cardinality even for acyclic rules, while rectangular explanation families admit a tight bound given by their largest choice domain. With circuit-defined contexts, sufficiency is $Π_3^P$-complete and selecting at most $k$ observable variables is $Σ_4^P$-complete, already for unrestricted contexts and acyclic rules. The selection reduction makes observation choices enforce globally fixed existential commitments. Explicit contexts reduce both tasks to NP-complete problems; tabulated explanation families make sufficiency polynomial. These results connect explanatory choice, information requirements, and representation cost.

Comment
9 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

A Polynomial Time Approximation for the Minimization of Implication Systems and Horn CNFs

cs.DM ·2026-11-15 ·Endre Boros, Ondrej Cepek, Kazuhisa Makino
similarity 0.64
Abstract

An implication system is a collection of rules of the form $B \imp H$, where the set $B$ of Boolean variables is the {\em body} of the rule, while $H$ is the set of its {\em heads}. Such a rule is an aggregate representation of individual implications $B\imp h$, for $h\in H$ which correspond to the clauses of an equivalent CNF representation of a Horn Boolean function. An implication system is {\em body-minimum}/{\em clause-minimum} if it has the minimum number of bodies/clauses among all logically equivalent implication systems. The corresponding minimization problems appear not only in the context of implication systems, but also as problems for closure systems, directed hypergraphs, representation of dependencies in relational databases, or in Horn CNF minimization. While body-minimization is known to be solvable in polynomial time (and there are several algorithms in the literature that solve this task), clause-minimization is known to be NP-hard. In fact, body-minimization has a particular canonical solution, called the GD-basis of the underlying Horn function that also can be computed efficiently. In this paper, we utilize a known connection between the two minimization problems stating that for every implication system there always exists a logically equivalent clause-minimum implication system which has the same bodies as its canonical GD-basis, see (B{é}rczi and B{é}rczi-Kov{á}cs, 2017), and (Adaricheva and Nation, 2014). We use this fact to design a polynomial time approximation algorithm which for any $δ>0$ outputs a $(\frac{1}{4} + δ)n$-factor approximation of the logically equivalent clause-minimum implication system on $n$ variables. This is an improvement from the best known algorithm so far that provides only an $(n-1)$-factor approximation, see (Hammer and Kogan, 1993).

0.30

On the Limits of Sufficient Explanations

cs.LG ·2026-11-13 ·Klaus Weinbauer, Peter F. Stadler, Thomas Gärtner, Sagar Malhotra
similarity 0.63
Abstract

We formally characterize the conditions under which sufficient explanations exist for classifiers on structured data such as graphs and strings. We focus on post-hoc explainers that select parts of the input as sufficient explanations. An explanation is sufficient if the selected part alone ensures the predicted label. Sufficient explanations have been widely adopted across data modalities, including graphs, strings, and images. However, a unified formal analysis of sufficient explanations remains missing. We bridge this gap with four main contributions: (i) We define a general explanation formalism consisting of an instance space, a classifier, and a select relation. The select relation specifies which potential sub-instances or feature subsets can be selected as explanations from each instance; (ii) We show that the existence of sufficient explainers is fully characterized by the interplay between the classifier and the select relation; (iii) We extend this analysis to practically relevant variants of sufficiency, including probabilistic sufficiency and deletion sufficiency; (iv) Based on the formal analysis, we devise statistics that bound the maximum achievable sufficiency for a given task. We evaluate these statistics on language, protein, and molecular classification datasets and find that full sufficiency is unattainable on most of them. Since these bounds hold for every explainer, they provide a task-level reference against which any explainer's sufficiency can be judged in absolute terms.

0.31

Cores Characterize the One-Pass Streaming Complexity of CSPs

cs.CC cs.DMcs.DS ·2026-10-05 ·Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy
similarity 0.60
Abstract

We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied; $\textsf{Min}$-$\textsf{CSP}(R)$, approximately minimizing the number of unsatisfied constraints; and $\textsf{Exact-CSP}(R)$, exactly computing the maximum number of satisfied constraints. Sharma and Velusamy (ESA 2026) characterized the streaming complexity of satisfiability for CSPs with literals using the non-redundancy parameter $\textsf{NRD}_n(R)$, which roughly measures the largest instance in which every constraint is independently necessary. For the most general setting without literals, they obtained the corresponding characterization for Boolean relations and showed obstacles to extending their techniques to larger domains. Kol, Paramonov, Saxena, and Yu (ITCS 2023) similarly characterized the streaming complexity of $\textsf{Exact-CSP}(R)$ for Boolean CSPs with literals in terms of the degree deg$(R)$ of the relation when written as a polynomial, while without literals, the corresponding result was known only for $\textsf{Max-Cut}$. For all three of the objectives we study, we give tight characterizations for unweighted CSP instances over arbitrary finite domains. The streaming algorithms we provide are deterministic, while the corresponding bounds are tight up to polylogarithmic factors, even against randomized algorithms. The central idea in all three results is a reduction of $R$ to its core, a canonical subrelation of $R$ which admits gadgets that allow for the hard-pinning (or fixing) of variables.

0.15

Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders

cs.LG ·2026-08-14 ·Faizanuddin Ansari, Debanjan Dutta, Swagatam Das
theory similarity 0.60
Abstract

In-context learning is commonly formalized as inference from examples of a function. Partial orders instead combine transitivity, antisymmetry, and incomparability, so a finite prompt may not determine a queried comparison. We develop a theory of in-context learning on partial orders that separates logical identifiability, prompt teaching cost, structural complexity, and the exact capacity of a formal coordinate-decoder class. A version-space semantics makes background knowledge and open- versus closed-world assumptions explicit. For finite open-world prompts with positive and negative comparisons, we prove an exact completion trichotomy: after taking the reflexive transitive closure of the positive demonstrations, a query is forced true, forced false because every true completion creates a cycle or violates a negative demonstration, or remains genuinely ambiguous. For a known $n$-element universe, we characterize the open-world teaching number as the number of covers plus a blocker-set hitting number, prove that its maximum over all $n$-element posets is $n(n-1)$ and is uniquely attained by the antichain, and identify the blocker term as the exact cost of open-world rather than complete-Hasse semantics. We formalize prompt-dependent $s$-coordinate decoders and use the classical coordinate-order equivalence to obtain an exact representation boundary: dimension at most $s$ is necessary and sufficient, while width at most $s$ is a convenient sufficient condition.

0.04

Minimum-Cost Robust Evidence Certificates for Horn Reasoning under Correlated Source Failures

cs.AI ·2026-10-19 ·Yukun Yang
theory similarity 0.60
Abstract · 9 pages, 2 figures

A small justification for a rule-based conclusion may disappear when a source is withdrawn, and multiple derivations need not provide independent evidence. We study minimum-cost certificates that preserve a Horn conclusion under every withdrawal of at most k source domains. Evidence records remain distinct from asserted facts, supporting replicated attestations and overlapping failure dependencies. Transversals of minimal-support footprints characterize robustness and explain why disjoint-proof requirements can reject valid certificates. An exact procedure alternates weighted evidence selection with a source-failure oracle. A rule-closed counterinterpretation yields a globally valid selection cut without enumerating supports or failure scenarios. We prove correctness, finite termination, and cost optimality, establish coNP-completeness of unrestricted verification and NP-completeness of synthesis for every fixed budget, and identify a tractable reachability restriction. Experiments on controlled benchmarks, reachability graphs, and ontology-derived instances demonstrate that our counterinterpretation-guided synthesis achieves up to 92% optimum coverage within practical resource bounds, outperforming scenario expansion and general abduction while confirming the necessity of transversal-based reasoning over proof-packing heuristics.

0.22

A hierarchy of faithfulness criteria for knowledge base completion

cs.AI ·2026-08-20 ·Olga Mashkova, Robert Hoehndorf
publishedcode/data similarity 0.60
Abstract · Accepted at NeSy 2026

Knowledge graph completion is evaluated by ranking observed triples above randomly corrupted ones, which treats every unobserved fact as false. When the object being completed is a description logic knowledge base rather than a plain graph, the open world assumption and deductive closure make this inadequate: relative to the knowledge base, a candidate axiom is entailed, contradictory, or undetermined, and a model that cannot separate a logically impossible axiom from a plausible novel one is not merely less accurate but semantically incorrect. We ask what it means for a knowledge base completion model to be logically faithful, and whether current embedding models are. We define a hierarchy of four increasingly strict criteria, discrimination, logical admissibility, monotonic logical faithfulness, and probabilistic logical faithfulness, and prove that they form a strict chain of implications. We ground the strongest criterion in the relative model count $P(α\mid\mathcal{O}) = \#(\mathcal{O}\cup\{α\})/\#(\mathcal{O})$, which recovers the trichotomy at its endpoints and ranks undetermined axioms in between. Evaluating knowledge graph and logic-geometric embedding models on $\mathcal{EL}$ ontologies, with entailed, contradictory, and undetermined test sets generated by a reasoner, we find that ranking accuracy does not imply logical faithfulness and that none of the evaluated models is faithful across the hierarchy. The code is available at https://github.com/bio-ontology-research-group/kbc.

0.42

Causal Explanations for Stratified Datalog

cs.DB ·2026-08-21 ·Ratan Bahadur Thapa, Steffen Staab
theory similarity 0.60
Abstract

Rule-based reasoning with exceptions requires causal explanations that account for both present and absent facts. For positive Datalog, monotonicity allows minimal supports to determine deletion causality. Stratified negation removes that property because inserting or deleting a fact may create or destroy an answer. We study actual causes, responsibility, and robustness for safe and stratified Datalog under perfect-model semantics and interventions over a finite set of mutable extensional facts. We prove that minimal supports and inclusion-minimal outcome-changing interventions do not determine causality, while robustness radius one may coexist with unbounded minimum contingencies. Our main result characterizes the minimum contingency size of a candidate fact by compatible prime implicants for the observed and opposite outcomes. The characterization conservatively recovers support-based causality for positive Datalog and yields path--cut characterizations for blocked recursive reachability. For fixed nonrecursive stratified programs, we establish data-complexity NP-completeness for cause recognition, robustness, and responsibility, and coNP-completeness for intervention-response equivalence between two such programs.

0.51

Constraint Tree Exploration for Learning from Language Feedback

cs.AI cs.CL ·2026-10-06 ·Shaoang Li, Daniel R. Jiang, Jian Li
theory similarity 0.59
Abstract

Natural-language feedback in interactive learning often explains why an action failed by pointing to violated requirements. Misinterpreting this feedback can lead an agent to rule out valid solutions. We study this setting by modeling user intent as latent constraints over an action space and formulating learning from language feedback as pure exploration over feasible regions. We introduce TRACE, an algorithm that organizes candidate constraints in a tree and tests each proposed refinement by generating actions that satisfy it. TRACE commits to the refinement only if the resulting feedback does not contradict it over repeated tests. We distinguish two ways of using the same feedback: (i) falsification, which detects contradictions to the constraint set currently being tested, and (ii) identification, which may additionally name a violated constraint. We prove high-probability coverage bounds with dependence on the candidate class size $H$ for TRACE-Falsification. With reliable identification, TRACE-Identification can replace this dependence by $K/p_{\mathrm{ext}}$, where $K$ is the number of latent constraints and $p_{\mathrm{ext}}$ lower-bounds the probability of extracting a missing true constraint from informative feedback. We evaluate TRACE across six language-feedback tasks. On RecMovie, TRACE-Identification achieves 73% and 86% final-output success under caps of 20 and 60 evaluated outputs, compared with at most 42% and 48% for the evaluated prompting baselines given the same feedback and output caps. Controlled identity-corruption experiments further show greater robustness than direct accumulation when the falsification detector remains reliable.

0.24