Exact Structural Abstraction and Tractability Limits

• URL: http://arxiv.org/abs/2604.07349v5
• Date: Thu, 16 Apr 2026 16:15:00 GMT
• Title: Exact Structural Abstraction and Tractability Limits
• Abstract summary: Exact correctness depends only on the induced classes $s sim_R simation' iff mathrmAdm_R(s)$.<n>Decision, search, approximation, statistical, randomized horizon, and distributional guarantees all reduce to this same quotient-recovery problem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Any rigorously specified problem determines an admissible-output relation $R$, and exact correctness depends only on the induced classes $s \sim_R s' \iff \mathrm{Adm}_R(s)=\mathrm{Adm}_R(s')$. Exact relevance certification asks which coordinates recover those classes. Decision, search, approximation, statistical, randomized, horizon, and distributional guarantees all reduce to this same quotient-recovery problem. Tractable cases still admit a finite primitive basis, but optimizer-quotient realizability is maximal, so quotient shape alone cannot mark the frontier. For frontier theorems, orbit gaps are the exact obstruction. Exact classification by closure-law-invariant predicates succeeds exactly when the target is constant on closure orbits; on a closure-closed domain, this is equivalent to disjointness of the positive and negative orbit hulls, and when it holds there is a least exact closure-invariant classifier. Across four natural candidate tractability predicates, a uniform pair-targeted affine witness produces same-orbit disagreements and rules out exact structural classification on the full binary pairwise domain. Because the canonical optimizer-set exact specifications of that witness class are already rigorously specified problems, no universal exact-certification characterization over formal problems escapes the same obstruction; this is by internal witness class, not by asserting that every problem is binary pairwise. Restricting the domain helps only by removing orbit gaps. Approximation also has a strict limit: without explicit gap control, arbitrarily small perturbations can flip relevance and sufficiency.

Related papers

• Discretization and Statistical Consistency of Functional Flow Matching [0.0]
  We prove strong $L2$ convergence of finite conditional velocity targets for every strongly consistent sequence of finite-rank reconstructions.<n>For learned flows, coupling directly to a population superposition path yields an end-to-end Wasserstein bound.
  arXiv  Detail & Related papers  (2026-08-05T07:05:47Z)
• When Quantum States over Spacetime Have No Common Process [0.0]
  We prove that settingwise realizability implies common-process realizability for every finite family.<n>For bipartite qubits we identify a $63$-dimensional hidden fiber and construct definite-order separations.<n>These results identify the boundary between spacetime tomography and global process composition.
  arXiv  Detail & Related papers  (2026-07-28T15:57:11Z)
• Maximal Classicalization of Finite-Group Quantum Reference-Frame Noise [0.0]
  A finite quantum reference token with group-valued misalignment induces a random-unitary channel.<n>We prove that the following conditions are equivalent for a unitary representation U of a finite group G.
  arXiv  Detail & Related papers  (2026-07-14T17:07:57Z)
• Byzantine Accountability Without Consensus: Strong Eventual Consistency for Non-Associative, Stochastic, Robust Aggregation [0.0]
  ACFA replicates a content-addressed OR-Set of signed contributions and a grow-only set of self-authenticating equivocation proofs.<n>A prototype (10 nodes, 3 Byzantine) passes 16/16 falsification checks.
  arXiv  Detail & Related papers  (2026-07-11T13:23:06Z)
• How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings? [58.740078141879984]
  Machine learning models often degrade when they are deployed on a target distribution that differs from the source distributions they were trained on.<n>Recent work in causality-based domain generalization has shown how shared causal structure can induce invariant predictors.<n>In this paper, we study when full or partial causal knowledge can provably improve supervised domain adaptation.
  arXiv  Detail & Related papers  (2026-06-10T21:07:49Z)
• The conditional-mean barrier: From deterministic regression to conditional distribution learning [6.160113667162026]
  This tutorial develops a self-contained module centered on the conditional-mean barrier.<n>Adding latent randomness to a squared-loss predictor collapses it back to the conditional mean.<n>We briefly organize common distributional objectives, including negative log-likelihood, moment and observable matching, variational objectives, adversarial divergences, and score matching.
  arXiv  Detail & Related papers  (2026-05-27T07:31:42Z)
• Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression [65.82017723631897]
  We show that scale-invariant upper bounds on self-normalized martingales are possible.<n>We derive a self-normalized concentration inequality free of the usual regularization penalties.
  arXiv  Detail & Related papers  (2026-05-02T22:39:00Z)
• The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability [0.0]
  A fixed probe family of finite-state controllers induces a closed-loop Wasserstein pseudometric on observation histories and a probe-exact quotient merging histories that no controller in the family can distinguish.<n>For clock-aware probes, it is exactly decision-sufficient for objectives that depend only on the agent's observations and actions.<n> scalable deterministic-stationary experiments study a tractable coarsening with gap measured on small exact cases and explored empirically at larger scale.
  arXiv  Detail & Related papers  (2026-03-22T20:59:31Z)
• Operationally induced preferred basis in unitary quantum mechanics [0.0]
  The preferred-basis problem and the definite-outcome aspect of the measurement problem persist even if the detector is modeled unitarily.<n>A change of mathematical type constitutes the core of the 'cut': a structurally necessary interface from group-based kinematics to set-based counting.
  arXiv  Detail & Related papers  (2026-01-26T17:22:03Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Transfinite Fixed Points in Alpay Algebra as Ordinal Game Equilibria in Dependent Type Theory [0.0]
  This paper contributes to the Alpay Algebra by demonstrating that the stable outcome of a self referential process is identical to the unique equilibrium of an unbounded revision dialogue between a system and its environment.<n>By unifying concepts from fixed point theory, game semantics, ordinal analysis, and type theory, this research establishes a broadly accessible yet formally rigorous foundation for reasoning about infinite self referential systems.
  arXiv  Detail & Related papers  (2025-07-25T13:12:55Z)
• On the Theory of Conditional Feature Alignment for Unsupervised Domain-Adaptive Counting [27.44207520673983]
  Object counting models suffer when deployed across domains with differing density variety.<n>We propose a theoretical framework of conditional feature alignment and provide a straightforward implementation.
  arXiv  Detail & Related papers  (2025-06-20T16:37:48Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Latent Veracity Inference for Identifying Errors in Stepwise Reasoning [78.29317733206643]
  We introduce Veracity Search (VS), a discrete search algorithm over veracity assignments.<n>It performs otherwise intractable inference in the posterior distribution over latent veracity values.<n>It generalizes VS, enabling accurate zero-shot veracity inference in novel contexts.
  arXiv  Detail & Related papers  (2025-05-17T04:16:36Z)
• When Does Confidence-Based Cascade Deferral Suffice? [69.28314307469381]
  Cascades are a classical strategy to enable inference cost to vary adaptively across samples. A deferral rule determines whether to invoke the next classifier in the sequence, or to terminate prediction. Despite being oblivious to the structure of the cascade, confidence-based deferral often works remarkably well in practice.
  arXiv  Detail & Related papers  (2023-07-06T04:13:57Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• GroupifyVAE: from Group-based Definition to VAE-based Unsupervised Representation Disentanglement [91.9003001845855]
  VAE-based unsupervised disentanglement can not be achieved without introducing other inductive bias. We address VAE-based unsupervised disentanglement by leveraging the constraints derived from the Group Theory based definition as the non-probabilistic inductive bias. We train 1800 models covering the most prominent VAE-based models on five datasets to verify the effectiveness of our method.
  arXiv  Detail & Related papers  (2021-02-20T09:49:51Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46:14Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Distribution-free binary classification: prediction sets, confidence intervals and calibration [106.50279469344937]
  We study three notions of uncertainty quantification -- calibration, confidence intervals and prediction sets -- for binary classification in the distribution-free setting. We derive confidence intervals for binned probabilities for both fixed-width and uniform-mass binning. As a consequence of our 'tripod' theorems, these confidence intervals for binned probabilities lead to distribution-free calibration.
  arXiv  Detail & Related papers  (2020-06-18T14:17:29Z)

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.