# computational complexity

Computational complexity theory is a subfield of theoretical computer science that studies the resources required to solve computational problems and compares their practical difficulty.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA

DevFeed: [Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA](<https://devfeed.tech/articles/classical-oracle-separation-of-qma-from-the-qcma-hierarchy-and-quantum-cryptography-even-when-p-qcma-146065.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.26574>)

Author: Alper Cakan

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Cryptography and Security](<https://devfeed.tech/sources/arxiv-cryptography-and-security.md>)

Topics: [Quantum Computing](<https://devfeed.tech/topics/quantum-computing.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>)

Tags: [2026](<https://devfeed.tech/tags/2026.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [encryption](<https://devfeed.tech/tags/encryption.md>), [hierarchy](<https://devfeed.tech/tags/hierarchy.md>), [one-way-functions](<https://devfeed.tech/tags/one-way-functions.md>), [oracle](<https://devfeed.tech/tags/oracle.md>), [public-key](<https://devfeed.tech/tags/public-key.md>), [quant-ph](<https://devfeed.tech/tags/quant-ph.md>), [quantum](<https://devfeed.tech/tags/quantum.md>), [query](<https://devfeed.tech/tags/query.md>), [separate](<https://devfeed.tech/tags/separate.md>), [state](<https://devfeed.tech/tags/state.md>)

### AI overview

The paper introduces Codeword-Hash pairs in Noise (CHN), a query-complexity problem in QMA that is hard for the QCMA hierarchy. Using CHN, it constructs a classical oracle where P, BQP, QCMA, and QCMAH coincide, yet QMA is strictly larger and is not contained in QCMAH. The abstract also claims that, relative to such an oracle, quantum cryptographic primitives can exist despite P = QCMA, including pseudorandom states with classical keys and public-key encryption with classical public keys and ciphertexts and copy-protected quantum decryption keys. These are oracle-relative results; the supplied text is an abstract, not the full manuscript.

### Source excerpt

arXiv:2611.26574v1 Announce Type: cross Abstract: Remark: This work is in submission at STOC'27 and thus the full manuscript has been publicly posted on the conference website since November 3rd, 2026. Inspired by the Codeword-Hash Structure problem recently introduced by Cakan (arXiV, 2026) to separate $\mathsf{QMA}$ from $\mathsf{QCIP}$, we introduce a new problem called Codeword-Hash pairs in Noise ($\mathsf{CHN}$) and prove that, in the query complexity model, it is in $\mathsf{QMA}$ but hard for the $\mathsf{QCMA}$ hierarchy $\mathsf{QCMAH} = \bigcup_{d\geq1}\mathsf{QCMA}^{\mathsf{QCMA}^{\cdots^{\mathsf{QCMA}}}}$, the classical-witness quantum-verifier analogue of $\mathsf{PH}=\bigcup_{d\ge1}\mathsf{NP}^{\mathsf{NP}^{\cdots^{\mathsf{NP}}}}$. Using this problem, we show that there exists a classical oracle ${O}$ such that $\mathsf{P}^{{O}}=\mathsf{BQP}^{{O}}=\mathsf{QCMA}^{{O}} =\mathsf{QCMAH}^{{O}} \subset \mathsf{QMA}^{{O}} \text{ but } \mathsf{QMA}^{{O}}\not\subseteq\mathsf{QCMAH}^{{O}},$ thus showing that quantum state or quantum proof advantage could exist even if classical computers can efficiently solve any problem that can be quantumly verified with a classical proof. Further, using our problem, we show that various quantum cryptographic primitives can exist even when $\mathsf{P} = \mathsf{QCMA}$ and thus neither quantum-computable one-way functions nor (verifiable) quantum computational advantage exist. In particular, relative to a classical oracle ${O}$ with $\mathsf{P}^{{O}}=\mathsf{BQP}^{{O}}=\mathsf{QCMA}^{{O}}=\mathsf{QCMAH}^{{O}}$, there exist pseudorandom states with classical keys and public-key encryption with copy-protected quantum decryption keys and classical public keys and ciphertexts, among other primitives, answering an open question of Kretschmer, Qian, and Tal (STOC 2025).

## On the Complexity of Offline Reinforcement Learning with Q\*-Approximation and Partial Coverage

DevFeed: [On the Complexity of Offline Reinforcement Learning with Q\*-Approximation and Partial Coverage](<https://devfeed.tech/articles/on-the-complexity-of-offline-reinforcement-learning-with-q-approximation-and-partial-coverage-144877.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2602.12107>)

Author: Haolin Liu, Braham Snyder, Chen-Yu Wei

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Reinforcement learning](<https://devfeed.tech/topics/reinforcement-learning.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [approximation](<https://devfeed.tech/tags/approximation.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [coverage](<https://devfeed.tech/tags/coverage.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [learning](<https://devfeed.tech/tags/learning.md>), [offline](<https://devfeed.tech/tags/offline.md>), [offline-reinforcement-learning](<https://devfeed.tech/tags/offline-reinforcement-learning.md>), [reinforcement-learning](<https://devfeed.tech/tags/reinforcement-learning.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>)

### AI overview

The paper shows that Q*-realizability and Bellman completeness alone do not guarantee sample-efficient offline reinforcement learning under partial coverage, establishing this with an information-theoretic lower bound. It proposes a decision-estimation framework that separates complexity into decision complexity and value estimation error. The authors report an ε⁻² sample-complexity bound for soft Q-learning under partial coverage, improving on a prior ε⁻⁴ bound; remove the need for additional online interaction in a value-gap setting; and identify further learnable settings. They also characterize Bellman completeness under partial coverage, offline learnability for general low-Bellman-rank MDPs, and provide what they describe as the first function-approximation analysis of Conservative Q-Learning (CQL).

### Source excerpt

arXiv:2602.12107v3 Announce Type: replace Abstract: We study offline reinforcement learning under $Q^\star$-approximation and partial coverage, a setting that motivates practical algorithms such as Conservative $Q$-Learning (CQL; Kumar et al., 2020) but has received limited theoretical attention. Our work is inspired by the following open question: "Are $Q^\star$-realizability and Bellman completeness sufficient for sample-efficient offline RL under partial coverage?" We answer in the negative via an information-theoretic lower bound. To identify additional structure that enables sample-efficient offline RL under partial coverage, we introduce a general decision-estimation framework, inspired by model-free decision-estimation coefficients (DEC) for online RL (Foster et al., 2023b; Liu et al., 2025b). Our framework decomposes offline RL complexity into decision complexity and value estimation error. This allows modular study of both sub-problems. Our result not only unifies existing results (Chen and Jiang, 2022; Uehara et al., 2023), but further improves and generalizes them. On the decision complexity side, our improvement includes: the first $\epsilon^{-2}$ sample complexity bound for soft $Q$-learning under partial coverage that improves Uehara et al.'s (2023) $\epsilon^{-4}$ bound, the removal of the need for additional online interaction in the value-gap setting of Chen and Jiang (2022), and new learnable settings beyond the above two cases. On the value estimation side, we provide a new characterization of the role of Bellman completeness under partial coverage, and the first characterization of offline learnability for general low-Bellman-rank MDPs (Jiang et al., 2017; Du et al., 2021; Jin et al., 2021). The latter is a canonical online RL setting that has remained unexplored in offline RL except for special cases. As a side contribution, our techniques give the first analysis of CQL in the function approximation setting.

## The Endogeneity of Miscalibration: Impossibility and Escape in Scored Reporting

DevFeed: [The Endogeneity of Miscalibration: Impossibility and Escape in Scored Reporting](<https://devfeed.tech/articles/the-endogeneity-of-miscalibration-impossibility-and-escape-in-scored-reporting-145330.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2605.07671>)

Author: Lauri Lov\\'en, Sasu Tarkoma

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [human in the loop agent](<https://devfeed.tech/topics/human-in-the-loop-agent.md>)

Tags: [agent](<https://devfeed.tech/tags/agent.md>), [agent-oversight](<https://devfeed.tech/tags/agent-oversight.md>), [ai](<https://devfeed.tech/tags/ai.md>), [convex](<https://devfeed.tech/tags/convex.md>), [cost](<https://devfeed.tech/tags/cost.md>), [critical](<https://devfeed.tech/tags/critical.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-gt](<https://devfeed.tech/tags/cs-gt.md>), [cs-ma](<https://devfeed.tech/tags/cs-ma.md>), [cubic](<https://devfeed.tech/tags/cubic.md>), [decision](<https://devfeed.tech/tags/decision.md>), [distribution](<https://devfeed.tech/tags/distribution.md>), [econ-th](<https://devfeed.tech/tags/econ-th.md>), [log](<https://devfeed.tech/tags/log.md>), [marketplace](<https://devfeed.tech/tags/marketplace.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [oversight](<https://devfeed.tech/tags/oversight.md>), [probability](<https://devfeed.tech/tags/probability.md>), [report](<https://devfeed.tech/tags/report.md>), [reporting](<https://devfeed.tech/tags/reporting.md>), [score](<https://devfeed.tech/tags/score.md>), [sorts](<https://devfeed.tech/tags/sorts.md>), [type](<https://devfeed.tech/tags/type.md>), [welfare](<https://devfeed.tech/tags/welfare.md>)

### AI overview

The paper finds that when perfect screening is attainable, the welfare-maximizing approval rule for scored probability reports is never affine, creating a predictable incentive to misreport. A reserve report equates the cost of pretending to be the marginal type with the value of approval. Approving reports at or above that reserve screens perfectly for any belief distribution and strictly proper score; a continuous rule with one corner also works, while under strict feasibility no continuously differentiable rule does. The decisive constraint is slope: a capped rule achieves perfect screening only when its cap reaches the critical slope, defined by the steepest chord of pretending cost up to the reserve. Below that threshold, welfare loss is cubic in the shortfall. The critical slope has a closed form for Brier, log, and power scores, and when pretending cost is convex up to the reserve. Applications include AI-agent oversight and marketplace operation.

### Source excerpt

arXiv:2605.07671v4 Announce Type: replace-cross Abstract: An agent's probability report is paid for twice: by a strictly proper scoring rule, which rewards accuracy, and by an approval rule for the decision it triggers. An approval rule that is not affine is known to defeat truthful reporting. We show the conflict is built in: whenever perfect screening is attainable, the welfare-maximizing approval rule is never affine. The distortion is predictable: there is a reserve report at which pretending to be the marginal type costs exactly what approval is worth. Approving every report at or above the reserve sorts agents as if their beliefs were observed, under every strictly proper score and for any belief distribution. So does a continuous rule with one corner; under strict feasibility no continuously differentiable rule does. The binding constraint is steepness, not smoothness: a slope-capped rule sorts perfectly if and only if the cap reaches the critical slope, the steepest chord of the pretending cost up to the reserve; below it the welfare loss is cubic in the shortfall. For the Brier, log and power scores, and whenever the pretending cost is convex up to the reserve, the critical slope has a closed form. The instances are AI-agent oversight and marketplace operation.

## Why a Computer Scientist Thinks Superintelligence Won't Happen

DevFeed: [Why a Computer Scientist Thinks Superintelligence Won't Happen](<https://devfeed.tech/articles/why-a-computer-scientist-thinks-superintelligence-won-t-happen-145256.md>)

Original publisher: [Read original article](<https://spectrum.ieee.org/ai-superintelligence-debate>)

Author: Cal Newport

Published: 2026-11-19T12:00:03Z

Content type: opinion

Language: en

Sources: [IEEE Spectrum](<https://devfeed.tech/sources/ieee-spectrum.md>)

Topics: [superintelligence](<https://devfeed.tech/topics/superintelligence.md>), [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>), [ai alignment](<https://devfeed.tech/topics/ai-alignment.md>), [Agentic AI](<https://devfeed.tech/topics/what-is-agentic-ai.md>), [agentic workflows](<https://devfeed.tech/topics/agentic-workflows.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [AI Engineering](<https://devfeed.tech/topics/ai-engineering.md>), [Model Development](<https://devfeed.tech/topics/model-development.md>), [AI Foundation Models](<https://devfeed.tech/topics/ai-foundation-models.md>)

Tags: [agi](<https://devfeed.tech/tags/agi.md>), [ai](<https://devfeed.tech/tags/ai.md>), [ai-companies](<https://devfeed.tech/tags/ai-companies.md>), [alignment](<https://devfeed.tech/tags/alignment.md>), [anthropic](<https://devfeed.tech/tags/anthropic.md>), [anthropic-ceo-dario-amodei](<https://devfeed.tech/tags/anthropic-ceo-dario-amodei.md>), [artificial-general-intelligence](<https://devfeed.tech/tags/artificial-general-intelligence.md>), [asi](<https://devfeed.tech/tags/asi.md>), [autonomous](<https://devfeed.tech/tags/autonomous.md>), [capabilities](<https://devfeed.tech/tags/capabilities.md>), [computer](<https://devfeed.tech/tags/computer.md>), [control](<https://devfeed.tech/tags/control.md>), [engineering](<https://devfeed.tech/tags/engineering.md>), [engineers](<https://devfeed.tech/tags/engineers.md>), [extinction](<https://devfeed.tech/tags/extinction.md>), [large-language-models](<https://devfeed.tech/tags/large-language-models.md>), [openai](<https://devfeed.tech/tags/openai.md>), [recursive-self-improvement](<https://devfeed.tech/tags/recursive-self-improvement.md>), [rsi](<https://devfeed.tech/tags/rsi.md>), [science](<https://devfeed.tech/tags/science.md>), [singularity](<https://devfeed.tech/tags/singularity.md>), [superintelligence](<https://devfeed.tech/tags/superintelligence.md>)

### AI overview

The author argues that recursive self-improvement leading to superintelligence remains highly speculative: post-training depends on suitable feedback data, major AI advances require substantial scientific work, and compute is finite. Computer science also shows that some problems are unsolvable or practically intractable, while AI progress remains uneven across tasks. The article attributes reported hacking incidents to long-running agents that let LLM outputs guide actions with few constraints, and contrasts these with task-specific systems such as AlphaFold and autonomous driving. It warns that pursuing self-improving systems may still increase risks by making AI harder to understand and control, and calls for more independent scrutiny.

### Source excerpt

Many people were caught off guard this past summer when employees of one of the world's leading AI companies began casually debating whether their products would lead to human extinction. It started when Anthropic researcher Jacob Coxon announced his resignation, warning that his employer and OpenAI were "racing straight to self-improving superintelligence and gambling with our lives." Evan Hubinger, Anthropic's head of alignment science, replied, "Jacob is correct here--we really do earnestly believe AI could kill all humans!" And Anthropic CEO Dario Amodei subsequently told CNN, "I agree with Jacob much more than I disagree with him." These concerns stem from a belief that has circulated in futurist circles for many decades: Once engineers design an AI system capable of improving itself, it will trigger an accelerating cycle of autonomous upgrades known as recursive self-improvement (RSI). The result will be artificial superintelligence (ASI), a system with cognitive capabilities so vastly exceeding those of humans that it will easily evade our control and perhaps even wipe out our species. Artificial superintelligence is, it should be noted, a far more ambitious goal than artificial general intelligence (AGI), which generally refers to AI that can match human capabilities across a broad range of cognitive tasks. These ideas have prompted varied reactions. Some argue that the concept of ASI is being used for marketing or to instigate regulation that will help the incumbent labs squash new competitors. Others focus on the plausibility of such systems killing us all, debating the finer points of specific scenarios such as AI-engineered superviruses. Still others claim that aligning ASI to human interests is feasible and so we should rush ahead to usher in this digital utopia. Amid these conversations, one question has received comparatively little attention: From an engineering perspective, is superintelligence even possible? The answer is important because it can he

## Time-Delayed Transformers for Data-Driven Modeling of Low-Dimensional Dynamics

DevFeed: [Time-Delayed Transformers for Data-Driven Modeling of Low-Dimensional Dynamics](<https://devfeed.tech/articles/time-delayed-transformers-for-data-driven-modeling-of-low-dimensional-dynamics-141541.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2602.08478>)

Author: Albert Alcalde, Markus Widhalm, Emre Y{\\i}lmaz

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Transformers](<https://devfeed.tech/topics/transformers.md>), [Complex Systems](<https://devfeed.tech/topics/complex-systems.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [architecture](<https://devfeed.tech/tags/architecture.md>), [attention](<https://devfeed.tech/tags/attention.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [cs-na](<https://devfeed.tech/tags/cs-na.md>), [data-driven](<https://devfeed.tech/tags/data-driven.md>), [diffusion](<https://devfeed.tech/tags/diffusion.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [interpretability](<https://devfeed.tech/tags/interpretability.md>), [linear](<https://devfeed.tech/tags/linear.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [math-ds](<https://devfeed.tech/tags/math-ds.md>), [math-na](<https://devfeed.tech/tags/math-na.md>), [synthetic](<https://devfeed.tech/tags/synthetic.md>), [transformers](<https://devfeed.tech/tags/transformers.md>), [validation](<https://devfeed.tech/tags/validation.md>)

### AI overview

The time-delayed transformer (TD-TF) is a compact model for unsteady spatio-temporal dynamics, interpreted as a nonlinear generalization of time-delayed dynamic mode decomposition. It uses one self-attention layer with a single query per prediction and one feedforward layer, with linear complexity in sequence length and few parameters. In the reported experiments, it matches strong linear baselines on near-linear systems and outperforms them in nonlinear and chaotic regimes, including long-term prediction. Validation covers synthetic signals, unsteady aerodynamics, the Lorenz '63 system, and a reaction-diffusion model. The abstract presents TD-TF as retaining linear models' interpretability and efficiency while adding expressive power; full methodological and experimental details are not included in the supplied excerpt.

### Source excerpt

arXiv:2602.08478v2 Announce Type: replace Abstract: We propose the time-delayed transformer (TD-TF), a simplified transformer architecture for data-driven modeling of unsteady spatio-temporal dynamics. TD-TF bridges linear operator-based methods and deep sequence models by showing that a single-layer, single-head transformer can be interpreted as a nonlinear generalization of time-delayed dynamic mode decomposition (TD-DMD). The architecture is deliberately minimal, consisting of one self-attention layer with a single query per prediction and one feedforward layer, resulting in linear computational complexity in sequence length and a small parameter count. Numerical experiments demonstrate that TD-TF matches the performance of strong linear baselines on near-linear systems, while significantly outperforming them in nonlinear and chaotic regimes, where it accurately captures long-term dynamics. Validation studies on synthetic signals, unsteady aerodynamics, the Lorenz '63 system, and a reaction-diffusion model show that TD-TF preserves the interpretability and efficiency of linear models while providing substantially enhanced expressive power for complex dynamics.

## Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL

DevFeed: [Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL](<https://devfeed.tech/articles/bellman-residual-bracketing-resolving-the-sample-complexity-of-discounted-and-average-reward-rl-138889.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.19566>)

Author: Matthew Zurek, Yudong Chen

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Reinforcement learning](<https://devfeed.tech/topics/reinforcement-learning.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [3](<https://devfeed.tech/tags/3.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [approach](<https://devfeed.tech/tags/approach.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [based](<https://devfeed.tech/tags/based.md>), [bias](<https://devfeed.tech/tags/bias.md>), [classes](<https://devfeed.tech/tags/classes.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [contribution](<https://devfeed.tech/tags/contribution.md>), [cs-it](<https://devfeed.tech/tags/cs-it.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [d](<https://devfeed.tech/tags/d.md>), [delta](<https://devfeed.tech/tags/delta.md>), [diameter](<https://devfeed.tech/tags/diameter.md>), [discount](<https://devfeed.tech/tags/discount.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [factor](<https://devfeed.tech/tags/factor.md>), [failure](<https://devfeed.tech/tags/failure.md>), [math-it](<https://devfeed.tech/tags/math-it.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [math-pr](<https://devfeed.tech/tags/math-pr.md>), [reward](<https://devfeed.tech/tags/reward.md>), [rl](<https://devfeed.tech/tags/rl.md>), [sample](<https://devfeed.tech/tags/sample.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>)

### AI overview

For RL with a nonadaptive generative model, the paper reports plug-in sample bounds that, together with its lower bounds, resolve minimax complexity up to constant factors. In discounted RL, the bound is O(SA(1−γ)⁻³ε⁻² log(SA/δ)). In average-reward RL, discounted plug-in has bound O(SAHε⁻² log(SA/δ)), where H upper-bounds optimal bias span; direct undiscounted plug-in has O(SADε⁻² log(SA/δ)), where D is the diameter. The stated technical contribution is Bellman residual bracketing, which improves the efficiency of prior absorbing-MDP-based concentration analyses.

### Source excerpt

arXiv:2611.19566v1 Announce Type: new Abstract: We study the sample complexity of the empirical planning or plug-in approach for reinforcement learning (RL) with a generative model. We show the discounted plug-in approach finds an $\varepsilon$-optimal policy with $O(SA (1-\gamma)^{-3} \varepsilon^{-2} \log(SA/\delta))$ samples, where $S, A, \gamma, \delta$ are the state and action sizes, discount factor, and failure probability, respectively. In the average-reward setting, we show that discounted plug-in and direct (undiscounted) plug-in achieve $O(SAH\varepsilon^{-2}\log(SA/\delta))$ and $O(SAD\varepsilon^{-2}\log(SA/\delta))$ complexities, respectively, where $H$ upper-bounds the optimal bias span and $D$ is the diameter. Combining with our lower bounds for nonadaptive generative models, these results resolve the minimax sample complexity of discounted RL and average-reward RL --- in both the span- and diameter-based classes --- up to constant factors. Our main technical contribution is a novel Bellman residual bracketing technique which improves the efficiency of prior absorbing-MDP-based concentration analyses.

## When Does Confidence Reveal Problem Difficulty?

DevFeed: [When Does Confidence Reveal Problem Difficulty?](<https://devfeed.tech/articles/when-does-confidence-reveal-problem-difficulty-137411.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.19173>)

Author: Xiyu Bao, Langyuan Cui, Hwee Tou Ng, Chun Kai Ling

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Parallel reasoning](<https://devfeed.tech/topics/parallel-reasoning.md>)

Tags: [applications](<https://devfeed.tech/tags/applications.md>), [confidence](<https://devfeed.tech/tags/confidence.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [entropy](<https://devfeed.tech/tags/entropy.md>), [inference](<https://devfeed.tech/tags/inference.md>), [model](<https://devfeed.tech/tags/model.md>), [problems](<https://devfeed.tech/tags/problems.md>), [token](<https://devfeed.tech/tags/token.md>), [utility](<https://devfeed.tech/tags/utility.md>)

### AI overview

The study finds that perturbation inconsistency, semantic entropy, and solution length are more strongly associated with population-level problem difficulty than token-level uncertainty. These associations persist among problems the focal model answers correctly, suggesting the signals reflect difficulty beyond predicting that model's correctness. The authors explore using them to guide inference-time decisions, describing them as informative but imperfect proxies. The supplied text gives no specific application results or comparative measurements.

### Source excerpt

arXiv:2611.19173v1 Announce Type: new Abstract: While confidence signals are commonly evaluated for their ability to predict a model's own correctness, their relationship with problem difficulty remains less understood. In this work, we investigate a wide range of confidence-related signals and whether they can serve as indicators of problem difficulty across various task domains. We find that perturbation inconsistency, semantic entropy, and solution length exhibit strong associations with population difficulty than token-level uncertainty. Notably, these relationships persist even when restricting the analysis to problems correctly answered by the focal model, suggesting that such signals capture information about difficulty beyond their ability to predict the model's own correctness. We further explore applications of these signals, illustrating the potential and limitations of using confidence-related signals to guide inference-time decisions. Our findings highlight the utility of model-specific signals as imperfect but informative proxies for population-level problem difficulty.

## A Structural Framework for Succession: Continuation, Recognition, and Realization

DevFeed: [A Structural Framework for Succession: Continuation, Recognition, and Realization](<https://devfeed.tech/articles/a-structural-framework-for-succession-continuation-recognition-and-realization-137570.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.20422>)

Author: Ilya A. Shkrob

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [AI Foundation Models](<https://devfeed.tech/topics/ai-foundation-models.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [continuation](<https://devfeed.tech/tags/continuation.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [framework](<https://devfeed.tech/tags/framework.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [identity](<https://devfeed.tech/tags/identity.md>), [recognition](<https://devfeed.tech/tags/recognition.md>), [robustness](<https://devfeed.tech/tags/robustness.md>), [structure](<https://devfeed.tech/tags/structure.md>)

### AI overview

The paper models succession--whether a later entity is the same one that entered an arrangement earlier--using state and modification graphs with relational lifts that compose along paths. For systems that may be fine-tuned, distilled, or copied, it separates four questions: what continuations a representation admits, which descendants are compatible with a modification, which are recognized as continuations of identity, and which are realized. The framework is intended to support general results independent of a particular pipeline or identity criterion, and addresses symmetry, computational complexity, recoverability, and robustness to partial realization. The supplied abstract does not specify the individual results.

### Source excerpt

arXiv:2611.20422v1 Announce Type: new Abstract: Succession asks whether an entity encountered later is the same entity that entered an arrangement earlier. For an artificial system that is fine-tuned, distilled, or copied, it has to be answered. We look for a mathematical structure weak enough to cover any such case and strong enough to support general theorems, so that results follow from the structure's conditions rather than from a particular pipeline or criterion. Succession is modeled on state/modification graphs with relational lifts that compose along paths. Within this framework we separate four questions that are often conflated: which continuations a representation admits, which descendants are compatible with a modification, which are recognized as continuing the identity, and which are realized. The framework allows one to address systematically questions of symmetry, computational complexity, recoverability, and robustness to partial realization, and we establish what the structure settles in each case before any particular criterion of identity is chosen.

## The Manifold-Index Model: provably and efficiently avoiding the statistical and computational curse of dimensionality

DevFeed: [The Manifold-Index Model: provably and efficiently avoiding the statistical and computational curse of dimensionality](<https://devfeed.tech/articles/the-manifold-index-model-provably-and-efficiently-avoiding-the-statistical-and-computational-curse-of-dimensionality-139019.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.20275>)

Author: Yantao Wu, Mauro Maggioni

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [linear-regression](<https://devfeed.tech/topics/linear-regression.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [convergence](<https://devfeed.tech/tags/convergence.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [curse-of-dimensionality](<https://devfeed.tech/tags/curse-of-dimensionality.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [error](<https://devfeed.tech/tags/error.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [intrinsic](<https://devfeed.tech/tags/intrinsic.md>), [link](<https://devfeed.tech/tags/link.md>), [math-st](<https://devfeed.tech/tags/math-st.md>), [noise](<https://devfeed.tech/tags/noise.md>), [prediction](<https://devfeed.tech/tags/prediction.md>), [projection](<https://devfeed.tech/tags/projection.md>), [regression](<https://devfeed.tech/tags/regression.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [stat-th](<https://devfeed.tech/tags/stat-th.md>), [tangent](<https://devfeed.tech/tags/tangent.md>), [vector](<https://devfeed.tech/tags/vector.md>)

### AI overview

The Manifold-Index Model assumes predictors lie in a tube around an unknown m-dimensional manifold and that the mean response depends on their nearest-point projection through a possibly non-injective link. MANOR estimates tangent planes using multiscale PCA on predictors with similar responses, then refines them by pooling local slope outer products; its neighborhoods narrow tangentially while retaining full normal fibers. Under the stated geometric and sampling conditions, a Lipschitz link differential, bounded response noise, and p >= m, the reported mean tangent-space error is n^{-2/(m+4)} and integrated squared prediction error is n^{-4/(m+4)}, up to logarithmic factors. With intrinsic dimension and specified model and scale quantities fixed, required sample size grows polynomially in D+p and computation polynomially in n, D, and p. Experiments cover curves, surfaces with vector responses, and hitting-probability prediction under an approximate model.

### Source excerpt

arXiv:2611.20275v1 Announce Type: cross Abstract: We study vector-valued regression with predictors filling a tube around an unknown $m$-dimensional manifold $\mathcal{M}$ in $\mathbb{R}^D$. In the Manifold-Index Model, the mean response is $F=f\circ\Pi_{\mathcal{M}}$, where $\Pi_{\mathcal{M}}$ is the nearest-point projection onto $\mathcal{M}$ and $f:\mathcal{M}\to\mathbb{R}^p$ is a possibly non-injective link function. Multiscale ANisotropic lOcal Regression (MANOR) estimates tangent planes by multiscale PCA of predictors with similar responses, then refines them by pooling outer products of local slopes. The neighborhoods narrow tangentially while retaining complete normal fibers. We assume a Lipschitz link differential and bounded response noise. For $p\ge m$, under our geometric and sampling conditions, $n$ independent observations give mean tangent-space error of order $n^{-2/(m+4)}$ and integrated squared prediction error at the $m$-dimensional nonparametric rate $n^{-4/(m+4)}$, up to logarithmic factors. In a scaling regime with fixed intrinsic dimension, model and scale parameters, and ratio of manifold volume to the $m$-th power of its reach, the required sample size grows polynomially in $D+p$, and computation is polynomial in $n$, $D$ and $p$. Numerical experiments on curves with non-monotone links and surfaces with vector-valued responses compare observed convergence rates with the theoretical bounds; a Langevin dynamics example tests prediction of hitting probabilities under an approximate manifold-index model.

## SART: Sign-Absolute Reformulation Theory for Binary Variable Reduction in Neural Network Verification

DevFeed: [SART: Sign-Absolute Reformulation Theory for Binary Variable Reduction in Neural Network Verification](<https://devfeed.tech/articles/sart-sign-absolute-reformulation-theory-for-binary-variable-reduction-in-neural-network-verification-137322.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.18657>)

Author: Jin Xu, Miaomiao Zhang, Bowen Du

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Formal verification](<https://devfeed.tech/topics/formal-verification.md>), [Neural Network](<https://devfeed.tech/topics/neural-network.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Automated reasoning](<https://devfeed.tech/topics/automated-reasoning.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [architectures](<https://devfeed.tech/tags/architectures.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [cs-ne](<https://devfeed.tech/tags/cs-ne.md>), [encoding](<https://devfeed.tech/tags/encoding.md>), [fewer](<https://devfeed.tech/tags/fewer.md>), [formal-verification](<https://devfeed.tech/tags/formal-verification.md>), [global](<https://devfeed.tech/tags/global.md>), [intermediate](<https://devfeed.tech/tags/intermediate.md>), [layer](<https://devfeed.tech/tags/layer.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [neural-network](<https://devfeed.tech/tags/neural-network.md>), [optimum](<https://devfeed.tech/tags/optimum.md>), [reduction](<https://devfeed.tech/tags/reduction.md>), [relu](<https://devfeed.tech/tags/relu.md>), [symmetry](<https://devfeed.tech/tags/symmetry.md>)

### AI overview

SART reduces the binary-variable burden in complete neural-network verification by allowing unstable ReLU neurons to require, on average, fewer than one binary variable. The abstract states that, assuming P ≠ NP, final-layer variables can be compressed by 50%, while intermediate-layer variables cannot be further reduced in a single-layer analysis. LayerABS addresses this limit by treating intermediate layers as temporary final layers and propagating tighter bounds, which the authors say reduces the network-wide search space and variable counts. The abstract also reports that numerical symmetry between positive and negative unstable-neuron weight signs yields the theoretical optimum worst-case complexity. SART is presented as a general-purpose encoding independent of the verification algorithm.

### Source excerpt

arXiv:2611.18657v1 Announce Type: cross Abstract: Complete formal verification of neural networks is crucial for their deployment in safety-critical domains. A key bottleneck stems from encoding complexity: traditional methods assign one binary variable per unstable ReLU neuron. We propose the Sign-Absolute Reformulation Theory (SART), which fundamentally breaks the conventional one-to-one mapping between unstable neurons and binary variables by establishing formal reducibility criteria. This allows for finer-grained modeling, where each unstable neuron corresponds on average to fewer than one binary variable, thereby reducing verification complexity at its source. Based on SART, we derive a theoretical lower bound on the number of binary variables required for complete verification and, under the assumption that $P \neq NP$, prove that variables in the final layer can be compressed by 50\%, while the number of variables in intermediate layers cannot be further reduced. To overcome the apparent ``last-layer-only'' limitation, we recast verification as a sequential process and, crucially, show that the gain lifts to the entire network: LayerABS, a SART-based progressive tightening verifier, iteratively treats intermediate layers as temporary final layers and propagates tight bounds that shrink the global search space and binary-variable counts. Furthermore, we reveal a structural law influencing verification complexity: when the signs of weights of unstable neurons satisfy numerical symmetry, with positive and negative weights equal or differing by at most one, the worst-case verification complexity achieves the theoretical optimum, offering theoretical guidance for the design of verification-friendly architectures. As a general-purpose underlying encoding, the value of SART is independent of specific algorithms.

## NetBreaker: Benchmarking Network Dismantling across Objectives, Scales, and Toplogoies

DevFeed: [NetBreaker: Benchmarking Network Dismantling across Objectives, Scales, and Toplogoies](<https://devfeed.tech/articles/netbreaker-benchmarking-network-dismantling-across-objectives-scales-and-toplogoies-138851.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.19298>)

Author: Wenchuan Yang, Tianci Bu, Suoyi Tan, Changjun Fan, Zijie Zhou, Xin Lu

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [big-data](<https://devfeed.tech/topics/big-data.md>), [reproducibility](<https://devfeed.tech/topics/reproducibility.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [open-llm-leaderboard](<https://devfeed.tech/topics/open-llm-leaderboard.md>)

Tags: [benchmarking](<https://devfeed.tech/tags/benchmarking.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [datasets](<https://devfeed.tech/tags/datasets.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [evaluation](<https://devfeed.tech/tags/evaluation.md>), [learning](<https://devfeed.tech/tags/learning.md>), [network](<https://devfeed.tech/tags/network.md>), [protocol](<https://devfeed.tech/tags/protocol.md>), [scalability](<https://devfeed.tech/tags/scalability.md>)

### AI overview

NetBreaker benchmarks 30 network-dismantling methods--18 non-learning and 12 learning-based--on 185 networks across eight domains, ranging from 14 to 1.69 million nodes. It converts varied method outputs into node-removal sequences and evaluates them under a shared protocol across target-based and trajectory-based effectiveness, structural diagnostics, and applicability and computational efficiency. The reported experiments find that learning-based methods do not consistently outperform strong non-learning approaches, with effectiveness, scalability, and efficiency varying across network conditions and evaluation perspectives.

### Source excerpt

arXiv:2611.19298v1 Announce Type: new Abstract: Network dismantling seeks to fragment a network with as few node removals as possible, which is widely applied in vulnerability analysis, epidemic containment, and infrastructure protection. Although learning-based methods have become increasingly prominent, their progress remains difficult to assess because existing studies differ in method coverage, datasets, evaluation criteria, and experimental protocols. Thus, we introduce NetBreaker, a comprehensive benchmark designed for the learning era of network dismantling. NetBreaker organizes 30 methods (18 non-learning and 12 learning-based) under a common taxonomy and evaluates them on 185 networks from eight unified domains, ranging from 14 to 1.69 million nodes. To enable fair comparison, heterogeneous method outputs are converted into node removal sequences and assessed under a unified execution protocol. The evaluation covers four complementary dimensions: target-based effectiveness, trajectory-based effectiveness, structural diagnostics, and applicability & computational efficiency. Extensive experiments show that current learningbased methods do not consistently outperform strong non-learning approaches, while exposing substantial differences in effectiveness, scalability, and efficiency across network conditions and evaluation perspectives. NetBreaker provides a reproducible basis for measuring progress and developing reliable, scalable, and computationally efficient network dismantling methods.

## A Fast Algorithm for the Familywise Loss

DevFeed: [A Fast Algorithm for the Familywise Loss](<https://devfeed.tech/articles/a-fast-algorithm-for-the-familywise-loss-138829.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.19065>)

Author: Leelavathi Raja, Amirreza Eshraghi, Vinay Prabhakar, Mark Blacher, Han Bao, Yutong Wang

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [catboost](<https://devfeed.tech/topics/catboost.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [High-Performance Computing](<https://devfeed.tech/topics/high-performance-computing.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [classes](<https://devfeed.tech/tags/classes.md>), [classification](<https://devfeed.tech/tags/classification.md>), [cpu](<https://devfeed.tech/tags/cpu.md>), [cross](<https://devfeed.tech/tags/cross.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [entropy](<https://devfeed.tech/tags/entropy.md>), [fast](<https://devfeed.tech/tags/fast.md>), [gpu](<https://devfeed.tech/tags/gpu.md>), [gradient](<https://devfeed.tech/tags/gradient.md>), [kernels](<https://devfeed.tech/tags/kernels.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [optimized](<https://devfeed.tech/tags/optimized.md>), [speed](<https://devfeed.tech/tags/speed.md>), [theoretical](<https://devfeed.tech/tags/theoretical.md>), [time](<https://devfeed.tech/tags/time.md>)

### AI overview

The paper addresses whether the familywise (FW) loss can match cross entropy (CE) computationally while retaining its stated theoretical advantage for multiclass classification. It proves that the FW gradient can be computed in O(K) time for K classes and reports optimized forward- and backward-pass kernels that run faster than CE on both CPU and GPU. The supplied excerpt does not include benchmark details or specify the conditions behind those speed comparisons.

### Source excerpt

arXiv:2611.19065v1 Announce Type: new Abstract: The familywise (FW) loss for multiclass classification, introduced by Duchi, Ruan, and Khosravi, achieves universal equivalence to the 0-1 loss, and thus has stronger theoretical properties than cross entropy (CE). Prior work, however, left open whether FW is as computationally efficient as CE. First, on the theoretical side, we prove that the FW gradient can be computed in $O(K)$ time, where $K$ is the number of classes. Second, on the practical side, we develop optimized kernels for computing the forward and backward passes of FW which outperform CE in terms of speed on both CPU and GPU.

## TokenFormer V2: Breaking the Resolution-Complexity Dilemma in Unified Recommendation

DevFeed: [TokenFormer V2: Breaking the Resolution-Complexity Dilemma in Unified Recommendation](<https://devfeed.tech/articles/tokenformer-v2-breaking-the-resolution-complexity-dilemma-in-unified-recommendation-138831.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.19074>)

Author: Kaihui Wu, Guoming Li, Liang Guo, Yifeng Zhou, Yuehong Hu, Junwei Pan, Zhixiang Feng, Chengguo Yin, Wenqi Fan, Haijie Gu, Jie Jiang

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [model architecture](<https://devfeed.tech/topics/model-architecture.md>), [personalization](<https://devfeed.tech/topics/personalization.md>), [Representation learning](<https://devfeed.tech/topics/representation-learning.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [advertising](<https://devfeed.tech/tags/advertising.md>), [architecture](<https://devfeed.tech/tags/architecture.md>), [behavior](<https://devfeed.tech/tags/behavior.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [competition](<https://devfeed.tech/tags/competition.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [context](<https://devfeed.tech/tags/context.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [distributed](<https://devfeed.tech/tags/distributed.md>), [evaluations](<https://devfeed.tech/tags/evaluations.md>), [fewer](<https://devfeed.tech/tags/fewer.md>), [full](<https://devfeed.tech/tags/full.md>), [fusion](<https://devfeed.tech/tags/fusion.md>), [global](<https://devfeed.tech/tags/global.md>), [parameter](<https://devfeed.tech/tags/parameter.md>), [production](<https://devfeed.tech/tags/production.md>), [recommendation](<https://devfeed.tech/tags/recommendation.md>), [state](<https://devfeed.tech/tags/state.md>), [structured](<https://devfeed.tech/tags/structured.md>), [tencent](<https://devfeed.tech/tags/tencent.md>), [wechat](<https://devfeed.tech/tags/wechat.md>)

### AI overview

TokenFormer V2 separates representation resolution from interaction density to model long recommendation histories within serving budgets. It groups behavior segments with non-sequential context, merges groups hierarchically, and coordinates them through NS Fusion and Global Sync; its Full-Resolution Readout keeps each encoded event accessible. The abstract reports top-ranking accuracy on TAAC 2026 with 5.1x fewer FLOPs than leading unified recommendation baselines, including across long histories and imbalanced behavior domains. Billion-parameter WeChat Channels advertising evaluations showed up to a +0.07 percentage-point overall AUC gain over industrial baselines. In a live A/B test against the production model, it reportedly increased GMV by 2.33% with statistical significance.

### Source excerpt

arXiv:2611.19074v1 Announce Type: cross Abstract: Industrial recommendation faces a resolution--complexity dilemma: dense interactions make detailed modeling of long behavior histories expensive, while compact history summaries restrict the evidence available to prediction. A unified backbone must preserve rich behavioral details within strict serving budgets. We introduce \textbf{TokenFormer V2}, a unified architecture that explicitly decouples \emph{representation resolution} from \emph{interaction density}. Its group-wise token layout jointly encodes behavior segments with non-sequential context, expands interaction ranges via hierarchical group merging, and coordinates distributed groups through \emph{NS Fusion} and \emph{Global Sync} modules. Through this \emph{local--global decomposition} paradigm, computation is concentrated on structured interactions while preserving fine-grained evidence, ensuring that every encoded event remains directly accessible to the \emph{Full-Resolution Readout} module. On the Tencent Advertising Algorithm Competition 2026 (TAAC 2026) benchmark, TokenFormer V2 achieves top-ranking accuracy among unified recommendation baselines while using \textbf{5.1$\times$ fewer FLOPs} than leading baselines, sustaining its advantage across long histories and imbalanced behavior domains. Furthermore, in billion-parameter evaluations on WeChat Channels advertising, it consistently outperforms state-of-the-art industrial baselines, yielding up to a \textbf{+0.07 pp} overall AUC gain. In live online A/B testing against the production model, TokenFormer V2 delivers a statistically significant \textbf{2.33\% increase in GMV}. These results establish TokenFormer V2 as a battle-tested blueprint for scalable, full-resolution behavior modeling in industrial recommendation.

## Elicited Adaptation: Auditable Localized Fairness via Pairwise Queries

DevFeed: [Elicited Adaptation: Auditable Localized Fairness via Pairwise Queries](<https://devfeed.tech/articles/elicited-adaptation-auditable-localized-fairness-via-pairwise-queries-138910.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.19686>)

Author: Shrey Shah

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [responsible-ai](<https://devfeed.tech/topics/responsible-ai.md>), [concept-learning](<https://devfeed.tech/topics/concept-learning.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [after](<https://devfeed.tech/tags/after.md>), [alpha](<https://devfeed.tech/tags/alpha.md>), [also](<https://devfeed.tech/tags/also.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [benefit](<https://devfeed.tech/tags/benefit.md>), [bounded](<https://devfeed.tech/tags/bounded.md>), [budget](<https://devfeed.tech/tags/budget.md>), [can](<https://devfeed.tech/tags/can.md>), [case](<https://devfeed.tech/tags/case.md>), [change](<https://devfeed.tech/tags/change.md>), [changes](<https://devfeed.tech/tags/changes.md>), [choice](<https://devfeed.tech/tags/choice.md>), [community](<https://devfeed.tech/tags/community.md>), [comparisons](<https://devfeed.tech/tags/comparisons.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [fairness](<https://devfeed.tech/tags/fairness.md>), [queries](<https://devfeed.tech/tags/queries.md>)

### AI overview

The paper quantifies how much scores must move to adapt fairness standards elicited through pairwise similarity and tolerance judgments. On a fixed pool of profiles, the exact amplification cost depends on runs of target constraints along shortest paths, with a sharp worst case of ⌊n/2⌋. Committing to a repair before learning the target can cost up to n−1 times the worst repair chosen after revelation; positive edge-budget floors and bounded geometry limit these costs. For two interior targets in the construction attaining that commitment bound, similarity queries alone produce a feasible 2-approximate repair at tolerance ε ≤ 1/[2(n−1)], with movement reduced by a factor linear in n relative to common repair. Under a fixed-slope logistic model, feasible (1+α)-optimal repair on this family has worst-case tolerance-query complexity Θ(α⁻²n² log(1/δ)). The abstract also reports studies of tolerance choice and numerical compliance versus predictive utility.

### Source excerpt

arXiv:2611.19686v1 Announce Type: new Abstract: How much must a predictor's scores change when a community's elicited fairness standard changes? Similarity and tolerance judgments define protected comparisons and acceptable score gaps. We study minimum uniform score movement on a fixed pool of $n$ profiles. For scores satisfying a source standard, we characterize the exact cost of retaining that standard during adaptation: runs of consecutive target constraints along shortest paths determine the optimal amplification factor. Its sharp worst case is $\lfloor n/2\rfloor$, and a full cost curve describes finite target-only repair budgets. Committing before the target is known can cost $n-1$ times the worst repair after revelation, even within one fixed convex ball of two-dimensional Mahalanobis metrics. Positive edge-budget floors cap both factors; bounded geometry also limits the commitment cost. At two interior targets of the construction attaining the $n-1$ bound, similarity queries alone yield a feasible $2$-approximate repair for tolerance $\eps\le1/[2(n-1)]$, reducing movement relative to common repair by a factor linear in $n$. Feasible $(1+\alpha)$-optimal repair on this family has worst-case tolerance-query complexity $\Theta(\alpha^{-2}n^2\log(1/\delta))$ under a fixed-slope logistic model. The analysis separates the information needed for a substantial adaptation benefit from the precision needed for nearly optimal movement. Elicitation studies and training comparisons examine tolerance choice and the relation between numerical compliance and predictive utility.

## Muon Attains $\\mathcal{O}(\\varepsilon^{-3})$ Iteration Complexity under Shuffling

DevFeed: [Muon Attains $\\mathcal{O}(\\varepsilon^{-3})$ Iteration Complexity under Shuffling](<https://devfeed.tech/articles/muon-attains-mathcal-o-varepsilon-3-iteration-complexity-under-shuffling-135867.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.18124>)

Author: Kun Huang, Shi Pu, Karl Henrik Johansson

Published: 2026-11-16T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [LLM Techniques](<https://devfeed.tech/topics/llm-techniques.md>), [iteration](<https://devfeed.tech/topics/iteration.md>)

Tags: [accelerate](<https://devfeed.tech/tags/accelerate.md>), [beta](<https://devfeed.tech/tags/beta.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [convergence](<https://devfeed.tech/tags/convergence.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [iteration](<https://devfeed.tech/tags/iteration.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [momentum](<https://devfeed.tech/tags/momentum.md>), [muon](<https://devfeed.tech/tags/muon.md>), [practical](<https://devfeed.tech/tags/practical.md>), [sampling](<https://devfeed.tech/tags/sampling.md>)

### AI overview

For smooth nonconvex finite-sum problems, Muon with its momentum buffer orthogonalized by the polar map achieves O(ε⁻³) iterations to find an ε-stationary point under any sequence of shuffling permutations, including random reshuffling, shuffle once, and incremental gradient. This matches SGD's dependence on ε under shuffling and improves on Muon's O(ε⁻⁴) bound with sampling with replacement. The guarantee requires a problem-dependent β that approaches one as the number of components grows. The abstract also gives smooth convex examples where any fixed β fails to ensure stationarity for sufficiently many components, regardless of permutation or small stepsizes. Its suggested tuning response to stalled loss is to increase β while reducing the stepsize accordingly.

### Source excerpt

arXiv:2611.18124v1 Announce Type: cross Abstract: Muon is a stochastic first-order optimizer for matrix-valued parameters. It maintains an exponential moving average of stochastic gradients in a momentum buffer with coefficient $\beta$, and orthogonalizes the buffer to obtain the update direction. Muon has been reported to accelerate and stabilize the training of large language models. In practice, it is often used with shuffling (sampling without replacement), where each epoch visits the components of a finite-sum objective in a permuted order. However, its iteration complexity in this setting remains open. We analyze Muon under shuffling, with the momentum buffer orthogonalized by the polar map. For smooth nonconvex finite-sum problems, we establish an $\mathcal{O}(\varepsilon^{-3})$ iteration complexity for finding an $\varepsilon$-stationary point. This guarantee holds for every sequence of permutations, covering random reshuffling, shuffle once, and the incremental gradient method. This complexity matches that of stochastic gradient descent under shuffling in its dependence on $\varepsilon$, and improves on Muon's $\mathcal{O}(\varepsilon^{-4})$ complexity under sampling with replacement. Our guarantee requires a problem-dependent $\beta$ that approaches one as the number of components grows. In contrast, no fixed $\beta$ guarantees convergence to stationarity for every number of components. We show this by constructing a family of smooth convex problems on which, for any fixed $\beta\in[0,1)$, Muon remains bounded away from stationarity once the number of components is sufficiently large. This failure occurs for every sequence of permutations and persists even with small stepsizes. These results suggest two practical tuning rules: if the training loss stops decreasing even after reducing the stepsize, increase $\beta$; when increasing $\beta$, reduce the stepsize accordingly.

## ESENSC: A Polynomial-Time Axiomatic Alternative to SHAP

DevFeed: [ESENSC: A Polynomial-Time Axiomatic Alternative to SHAP](<https://devfeed.tech/articles/esensc-a-polynomial-time-axiomatic-alternative-to-shap-134964.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2603.00496>)

Author: Kazuhiro Hiraki, Shinichi Ishihara, Takumi Kongo, Junnosuke Shino

Published: 2026-11-16T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>)

Tags: [attribution](<https://devfeed.tech/tags/attribution.md>), [coalition](<https://devfeed.tech/tags/coalition.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [magnitude](<https://devfeed.tech/tags/magnitude.md>), [models](<https://devfeed.tech/tags/models.md>), [neural](<https://devfeed.tech/tags/neural.md>), [neural-network](<https://devfeed.tech/tags/neural-network.md>), [prediction](<https://devfeed.tech/tags/prediction.md>), [rankings](<https://devfeed.tech/tags/rankings.md>), [sampling](<https://devfeed.tech/tags/sampling.md>), [shap](<https://devfeed.tech/tags/shap.md>), [xgboost](<https://devfeed.tech/tags/xgboost.md>)

### AI overview

ESENSC is a deterministic, closed-form feature attribution rule that uses linearly many coalition-value evaluations, compared with exact SHAP's exponential requirement. It satisfies the null-player property and is characterized by efficiency, restricted differential marginality, and explicit computational constraints. On evaluated tabular tasks with neural networks and XGBoost, it reportedly agrees closely with exact SHAP in attribution magnitude and feature rankings while using substantially less computation, and compares favorably with widely used sampling-based SHAP approximations. The evidence describes these results only for the evaluated settings.

### Source excerpt

arXiv:2603.00496v2 Announce Type: replace-cross Abstract: We propose ESENSC, a computationally efficient and theoretically grounded alternative to SHAP. ESENSC is a deterministic, closed-form attribution rule that requires only linearly many coalition-value evaluations, satisfies the null-player property, and admits an axiomatic characterization based on efficiency, a restricted form of differential marginality, and explicit computational constraints.Empirically, on tabular prediction tasks using neural network and XGBoost models, ESENSC shows close agreement with exact SHAP in both attribution magnitude and feature rankings while requiring substantially less computation. Under the evaluated settings, it compares favorably with widely used sampling-based SHAP approximations. While exact SHAP requires exponentially many coalition evaluations, ESENSC scales linearly with the number of features. These results show that ESENSC offers a favorable trade-off between agreement with exact SHAP and computational cost, providing a practical and theoretically grounded alternative for feature attribution in high-dimensional applications.

## Pattern-Based Matrix Analysis Under Permutations

DevFeed: [Pattern-Based Matrix Analysis Under Permutations](<https://devfeed.tech/articles/pattern-based-matrix-analysis-under-permutations-135818.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.17674>)

Author: Andrei Ermakov

Published: 2026-11-16T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [model architecture](<https://devfeed.tech/topics/model-architecture.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Transformer](<https://devfeed.tech/topics/transformer.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [attention](<https://devfeed.tech/tags/attention.md>), [band](<https://devfeed.tech/tags/band.md>), [bandwidth](<https://devfeed.tech/tags/bandwidth.md>), [block](<https://devfeed.tech/tags/block.md>), [community](<https://devfeed.tech/tags/community.md>), [community-detection](<https://devfeed.tech/tags/community-detection.md>), [control](<https://devfeed.tech/tags/control.md>), [correlation](<https://devfeed.tech/tags/correlation.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [linear](<https://devfeed.tech/tags/linear.md>), [mask](<https://devfeed.tech/tags/mask.md>), [matrix](<https://devfeed.tech/tags/matrix.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [ordering](<https://devfeed.tech/tags/ordering.md>), [pattern](<https://devfeed.tech/tags/pattern.md>), [permutation](<https://devfeed.tech/tags/permutation.md>), [permutations](<https://devfeed.tech/tags/permutations.md>), [random](<https://devfeed.tech/tags/random.md>)

### AI overview

The paper proposes measuring matrix structure after optimally permuting rows and columns, covering patterns such as bands, block diagonals, and arrowheads. The resulting pattern distance applies to problems including latent ordering, community detection, and bandwidth minimization. Because optimization is NP-hard in general, the authors derive an alternating algorithm using Linear Assignment subproblems. They also combine pattern fitting with a low-rank residual; reported gains across pattern families persist at a matched parameter budget and are substantially reduced with a density-matched random-mask control. Evaluation covers synthetic recovery, correlation and graph adjacency matrices, and transformer attention heads.

### Source excerpt

arXiv:2611.17674v1 Announce Type: new Abstract: Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density-matched random-mask control. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure.

## Improving Matrix Exponential for Generative AI Flows: A Taylor-Based Approach Beyond Paterson--Stockmeyer

DevFeed: [Improving Matrix Exponential for Generative AI Flows: A Taylor-Based Approach Beyond Paterson--Stockmeyer](<https://devfeed.tech/articles/improving-matrix-exponential-for-generative-ai-flows-a-taylor-based-approach-beyond-paterson-stockmeyer-135658.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2512.20777>)

Author: Jorge Sastre, Daniel Faronbi, Jos\\'e Miguel Alonso, Peter Traver, Javier Ib\\'a\\~nez, Nuria Lloret

Published: 2026-11-16T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [High-Performance Computing](<https://devfeed.tech/topics/high-performance-computing.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [acceleration](<https://devfeed.tech/tags/acceleration.md>), [ai](<https://devfeed.tech/tags/ai.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [applications](<https://devfeed.tech/tags/applications.md>), [approach](<https://devfeed.tech/tags/approach.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [based](<https://devfeed.tech/tags/based.md>), [combined](<https://devfeed.tech/tags/combined.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [computing](<https://devfeed.tech/tags/computing.md>), [control](<https://devfeed.tech/tags/control.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [cs-na](<https://devfeed.tech/tags/cs-na.md>), [develop](<https://devfeed.tech/tags/develop.md>), [effort](<https://devfeed.tech/tags/effort.md>), [error](<https://devfeed.tech/tags/error.md>), [generative](<https://devfeed.tech/tags/generative.md>), [generative-ai](<https://devfeed.tech/tags/generative-ai.md>), [math-na](<https://devfeed.tech/tags/math-na.md>), [matrix](<https://devfeed.tech/tags/matrix.md>)

### AI overview

The paper proposes an optimized Taylor-based matrix exponential algorithm for high-throughput generative AI flows. It uses error analysis and dynamically selects Taylor order and scaling factor to minimize computation under a prescribed error tolerance. The abstract reports that numerical experiments show acceleration and high numerical stability versus existing state-of-the-art implementations, but provides no quantitative results or experiment details. Its comparison with Padé scaling-and-squaring and Paterson-Stockmeyer is broad; specific implementation or performance tradeoffs are not given.

### Source excerpt

arXiv:2512.20777v3 Announce Type: replace Abstract: The matrix exponential is a fundamental operator in scientific computing and system simulation, with applications ranging from control theory and quantum mechanics to modern generative machine learning. While Pad\'e approximants combined with scaling and squaring have long served as the standard, recent Taylor-based methods, which utilize polynomial evaluation schemes that surpass the classical Paterson--Stockmeyer technique, offer superior accuracy and reduced computational complexity. This paper presents an optimized Taylor-based algorithm for the matrix exponential, specifically designed for the high-throughput requirements of generative AI flows. We provide a rigorous error analysis and develop a dynamic selection strategy for the Taylor order and scaling factor to minimize computational effort under a prescribed error tolerance. Extensive numerical experiments demonstrate that our approach provides significant acceleration and maintains high numerical stability compared to existing state-of-the-art implementations. These results establish the proposed method as a highly efficient tool for large-scale generative modeling.

## Federated Soft Poly-Level Learning Over a Distributed Network with Guaranteed Convergence

DevFeed: [Federated Soft Poly-Level Learning Over a Distributed Network with Guaranteed Convergence](<https://devfeed.tech/articles/federated-soft-poly-level-learning-over-a-distributed-network-with-guaranteed-convergence-135102.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.17722>)

Author: Yang Jiao, Kai Yang, Jianwei Huang

Published: 2026-11-16T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [distributed algorithm](<https://devfeed.tech/topics/distributed-algorithm.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [convergence](<https://devfeed.tech/tags/convergence.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [distributed](<https://devfeed.tech/tags/distributed.md>), [federated](<https://devfeed.tech/tags/federated.md>), [learning](<https://devfeed.tech/tags/learning.md>), [network](<https://devfeed.tech/tags/network.md>)

### AI overview

The proposed Federated Poly-Level Learning (FPLL) framework addresses soft-constrained optimization with four or more hierarchical levels when data is distributed across network nodes. It uses a nonlinear "L-cut" to relax the problem level by level, and adjustable algorithm parameters let users trade computational complexity against performance efficiency. The authors report a non-asymptotic iteration-complexity analysis for reaching an ε-Pareto stationary point and say experiments demonstrate the method's efficacy; the excerpt gives no quantitative results or specific experimental comparisons.

### Source excerpt

arXiv:2611.17722v1 Announce Type: new Abstract: Multi-level learning/optimization, e.g., bilevel optimization, has been recognized for its versatile applicability across a broad array of domains, spanning from signal processing to machine learning. However, most existing works focus on bilevel and trilevel optimization. In contrast, multi-level optimization problems involving four or more hierarchical levels, which we term poly-level learning (PLL) problems, remain largely unexplored.In addition, in practical PLL, data may be distributed across multiple nodes over a distributed network. Nevertheless, extant studies on PLL predominantly focus on the non-federated setting, necessitating the collection of data to central servers and thereby posing potential privacy risks. To this end, we propose a Federated Poly-Level Learning (FPLL) framework over a distributed network to tackle the PLL problems with soft constraints in a federated manner. FPLL hinges on a novel non-linear cut, i.e., $L$-cut, for the level-wise relaxation to the PLL problems. Additionally, the proposed federated algorithm is designed with adjustable parameters that allow for a flexible trade-off between its computational complexity and performance efficiency, enabling users to tune it according to specific application requirements. We also carry out non-asymptotic analysis to derive the iteration complexity for the proposed FPLL to achieve the $\epsilon$-Pareto stationary point. Extensive experiments have been undertaken to elucidate the superior efficacy of the proposed method.

## Structure-Aware Quantum Circuit Equivalence Checking via Sparse Pauli Propagation

DevFeed: [Structure-Aware Quantum Circuit Equivalence Checking via Sparse Pauli Propagation](<https://devfeed.tech/articles/structure-aware-quantum-circuit-equivalence-checking-via-sparse-pauli-propagation-131707.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.15080>)

Author: Shangzhou Xia, Junjie Luo, Qichen Wang, Yasunari Suzuki, Jianjun Zhao

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Software Engineering](<https://devfeed.tech/sources/arxiv-software-engineering.md>)

Topics: [Quantum Computing](<https://devfeed.tech/topics/quantum-computing.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Error Propagation](<https://devfeed.tech/topics/error-propagation.md>)

Tags: [ablation](<https://devfeed.tech/tags/ablation.md>), [accounting](<https://devfeed.tech/tags/accounting.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [bounded](<https://devfeed.tech/tags/bounded.md>), [cancellation](<https://devfeed.tech/tags/cancellation.md>), [circuit](<https://devfeed.tech/tags/circuit.md>), [circuits](<https://devfeed.tech/tags/circuits.md>), [compiler](<https://devfeed.tech/tags/compiler.md>), [cs-se](<https://devfeed.tech/tags/cs-se.md>), [equivalence-checking](<https://devfeed.tech/tags/equivalence-checking.md>), [error](<https://devfeed.tech/tags/error.md>), [errors](<https://devfeed.tech/tags/errors.md>), [existing](<https://devfeed.tech/tags/existing.md>), [exploits](<https://devfeed.tech/tags/exploits.md>), [framework](<https://devfeed.tech/tags/framework.md>), [generator](<https://devfeed.tech/tags/generator.md>), [generators](<https://devfeed.tech/tags/generators.md>), [optimizations](<https://devfeed.tech/tags/optimizations.md>), [quant-ph](<https://devfeed.tech/tags/quant-ph.md>), [quantum](<https://devfeed.tech/tags/quantum.md>), [structure](<https://devfeed.tech/tags/structure.md>)

### AI overview

The checker targets unitary quantum circuits with sparse Pauli propagation, choosing between two strategies based on circuit structure: generator propagation compares conjugation of Pauli generators, while Cut-Miter uses cancellation between circuit products at selected cut points. It explicitly accounts for numerical and approximation errors. On two benchmark suites with pairs up to 512 qubits, it made reference-consistent decisions for 96.3% of 434 scored pairs with no incorrect verdicts; the evaluated baselines reached at most 68.7%. Its aggregate runtime was 48.5%-76.0% lower than those baselines. Ablations support the contributions of cut-based verification, Pauli-term pruning, and bounded propagation attempts. These results are limited to the reported benchmarks and comparisons.

### Source excerpt

arXiv:2611.15080v1 Announce Type: new Abstract: Quantum circuit equivalence checking is essential for validating compiler optimizations, but its computational cost can vary substantially with circuit structure. We present a structure-aware equivalence checker for unitary quantum circuits based on sparse Pauli propagation. It combines two complementary verification strategies: generator propagation compares the conjugation actions of the circuits on Pauli generators, while Cut-Miter exploits cancellation between circuit products at selected cut points. A structure-aware verification procedure uses circuit characteristics to select between these strategies while explicitly accounting for numerical and approximation errors. We evaluate our framework against three existing equivalence checkers on two benchmark suites containing circuit pairs with up to 512 qubits. Across 434 scored circuit pairs, our framework produces reference-consistent decisions for 96.3% of the pairs without any incorrect verdicts, while the evaluated baselines achieve at most 68.7% reference-consistent decisions. It also achieves the lowest aggregate runtime among the evaluated tools, reducing total runtime by 48.5%--76.0% relative to these baselines. Ablation studies confirm the benefits of cut-based verification, Pauli-term pruning, and bounded propagation attempts. These results indicate that structure-aware sparse Pauli propagation, combined with complementary verification strategies and explicit error accounting, can provide an effective approach to practical quantum circuit equivalence checking.

## Towards a Theory of Learnability via Debate

DevFeed: [Towards a Theory of Learnability via Debate](<https://devfeed.tech/articles/towards-a-theory-of-learnability-via-debate-133202.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.17303>)

Author: Tosca Lechner, Vinayak Pathak, Sivan Sabato, Ruth Urner

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [adversarial](<https://devfeed.tech/tags/adversarial.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [framework](<https://devfeed.tech/tags/framework.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [online-learning](<https://devfeed.tech/tags/online-learning.md>), [protocol](<https://devfeed.tech/tags/protocol.md>), [theory](<https://devfeed.tech/tags/theory.md>)

### AI overview

The paper studies debate as a training protocol through the lens of online learning, rather than analyzing only the debate game for a known judge. It finds cases where the best way to learn from a judge differs from adversarial debate, motivating a cooperative protocol whose learnability is characterized by a combinatorial dimension. It also finds that even a small number of human judging errors can lead to large learning error. These are initial theoretical results about learnability, not evidence in the supplied abstract that debate reliably teaches complex functions in practice.

### Source excerpt

arXiv:2611.17303v1 Announce Type: new Abstract: Debate has been recently proposed as a training protocol that is hoped to produce more aligned models even as model capabilities scale. The idea is that the human, instead of providing supervision in the form of labels, judges a debate between two models that compete to prove the correctness of opposite labels. It can be shown that functions of a much higher computational complexity can be correctly judged in this way, compared to the complexity of functions that can be directly evaluated using a computationally weak evaluator. This suggests that perhaps debate can be used to teach very complicated functions to models. However, previous work has largely ignored the fact that this is a training protocol, and simply analyzes the game being played between the two debaters for a known judge. We take the first steps towards understanding the learning problem implicit within the protocol, by formulating it as an online learning problem. We show that once we formulate the learning problem precisely, there are cases where the best way to learn given access to a judge is different from running an adversarial debate. This motivates us to define a cooperative version of the protocol, whose learnability we characterize using a combinatorial dimension. We also consider the possibility of the human judge being fallible and occasionally judging the debate incorrectly. We show that a small number of errors in judgement can lead to a large error in learning.

## Agentic Computational Algebra

DevFeed: [Agentic Computational Algebra](<https://devfeed.tech/articles/agentic-computational-algebra-132194.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.16073>)

Author: Ryan A. Anderson, Matthew Trager, Ben Bowman, Wei Xia, Stefano Soatto

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Complex AI tasks](<https://devfeed.tech/topics/complex-ai-tasks.md>)

Tags: [agentic](<https://devfeed.tech/tags/agentic.md>), [agents](<https://devfeed.tech/tags/agents.md>), [ai](<https://devfeed.tech/tags/ai.md>), [algebra](<https://devfeed.tech/tags/algebra.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [compilation](<https://devfeed.tech/tags/compilation.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [cs-sc](<https://devfeed.tech/tags/cs-sc.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [exploit](<https://devfeed.tech/tags/exploit.md>), [independent](<https://devfeed.tech/tags/independent.md>), [memory](<https://devfeed.tech/tags/memory.md>), [overhead](<https://devfeed.tech/tags/overhead.md>), [persistent-memory](<https://devfeed.tech/tags/persistent-memory.md>), [problems](<https://devfeed.tech/tags/problems.md>), [range](<https://devfeed.tech/tags/range.md>), [reasoning](<https://devfeed.tech/tags/reasoning.md>), [reduce](<https://devfeed.tech/tags/reduce.md>), [reuse](<https://devfeed.tech/tags/reuse.md>), [streams](<https://devfeed.tech/tags/streams.md>)

### AI overview

The paper evaluates whether AI agents can exploit algebraic structure to reduce solving time, using benchmark families with independently verifiable answers and controlled difficulty. It tests agents on independent instances, streams of related instances with persistent memory, and compilation of reusable solvers for known problem families. Agents extend the range of systems solvable within a fixed budget, but reasoning overhead can erase computational savings. Memory can lower repeated-solving costs while retaining suboptimal strategies; compiled solvers run faster but require substantial upfront effort.

### Source excerpt

arXiv:2611.16073v1 Announce Type: cross Abstract: We explore the use of AI agents for solving computational problems in algebra. For the problems we consider, the main challenge is not correctness but \emph{time}: general-purpose algorithms are guaranteed to provide correct solutions but can be prohibitively slow, while reformulations that exploit special structure often allow solving a problem much faster. We propose to use this setting to evaluate how effectively agents discover and exploit structure within and across tasks to reduce computational costs. More broadly, computational algebra supplies infinitely many problems with independently verifiable answers and systematically controllable structure and difficulty. To illustrate these possibilities, we use benchmark families of systems with controlled shared structure and evaluate agents in three settings: solving independent instances, solving online streams of related instances using persistent memory, and compiling a fast reusable solver for a known problem family. Our experiments show that (i) agents can extend the range of systems solvable within a fixed budget, although reasoning overhead can sometimes outweigh computational savings; (ii) memory can reduce the cost of repeated solving but may preserve suboptimal strategies; (iii) compilation produces faster reusable solvers but at substantial upfront cost. Overall, computational algebra offers concrete, measurable targets for improving how agents discover and reuse structure.

## Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience

DevFeed: [Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience](<https://devfeed.tech/articles/toward-optimal-complexity-hash-based-asynchronous-mvba-with-optimal-resilience-131505.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2410.12755>)

Author: Jovan Komatovic, Joachim Neu, Tim Roughgarden

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [consensus algorithm](<https://devfeed.tech/topics/consensus-algorithm.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [asynchronous](<https://devfeed.tech/tags/asynchronous.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [hash](<https://devfeed.tech/tags/hash.md>), [resilience](<https://devfeed.tech/tags/resilience.md>)

### AI overview

The paper presents two asynchronous MVBA protocols for adaptive faults that improve resilience while keeping communication costs low. Reducer tolerates fewer than n/4 failures and retains HMVBA's stated optimal message and time complexity and near-optimal bit complexity; it uses collision-resistant hashes and internally uses a new strong multi-valued Byzantine agreement (SMBA) construction to ensure the decided value was proposed by a correct process. Reducer++ raises resilience to fewer than (1/3 − ε)n failures for any fixed ε > 0, without SMBA. It instead models hash functions as random oracles to ensure termination, with constant time, quadratic message, and quasi-quadratic bit complexity; its constants depend on ε.

### Source excerpt

arXiv:2410.12755v4 Announce Type: replace Abstract: Multi-valued validated Byzantine agreement (MVBA), a fundamental primitive of distributed computing, allows $n$ processes to agree on a valid $\ell$-bit value, despite $t$ faulty processes behaving maliciously. Among hash-based solutions for the asynchronous setting with adaptive faults, the state-of-the-art HMVBA protocol achieves optimal $O(n^2)$ message complexity, (near-)optimal $O(n \ell + n^2 \lambda \log n)$ bit complexity, and optimal $O(1)$ time complexity. However, it only tolerates $t < \frac15 n$ failures. In contrast, the best-known optimally-resilient protocol, SQ, incurs a higher bit complexity of $O(n^2 \ell + n^3 \lambda)$. This poses a fundamental question: Can a hash-based protocol be designed for the asynchronous setting with adaptive faults that simultaneously achieves optimal complexity and optimal resilience? This paper takes a significant step toward answering this question. Namely, we introduce Reducer, an MVBA protocol that retains HMVBA's optimal complexity while improving its resilience to $t < \frac14 n$. Like HMVBA and SQ, Reducer relies exclusively on collision-resistant hash functions. A key innovation in Reducer's design is its internal use of strong multi-valued Byzantine agreement (SMBA), a new variant of Byzantine agreement we introduce and construct, which ensures that the decided value was proposed by a correct process. To further advance resilience toward the optimal one-third bound, we then propose Reducer++, an MVBA protocol that tolerates up to $t < (\frac13 - \epsilon)n$ adaptive failures, for any fixed constant $\epsilon > 0$. Unlike Reducer, Reducer++ does not rely on SMBA. Instead, it employs a novel approach involving hash functions modeled as random oracles to ensure termination. Reducer++ maintains constant time complexity, quadratic message complexity, and quasi-quadratic bit complexity, with constants dependent on $\epsilon$.

## Uncertainty-aware quantum machine learning based on Dempster-Shafer theory

DevFeed: [Uncertainty-aware quantum machine learning based on Dempster-Shafer theory](<https://devfeed.tech/articles/uncertainty-aware-quantum-machine-learning-based-on-dempster-shafer-theory-133157.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.16903>)

Author: Marie Kempkes, Jakob Spiegelberg, Evert van Nieuwenburg, Vedran Dunjko

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>), [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>)

Tags: [circuits](<https://devfeed.tech/tags/circuits.md>), [classification](<https://devfeed.tech/tags/classification.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [data](<https://devfeed.tech/tags/data.md>), [fusion](<https://devfeed.tech/tags/fusion.md>), [quant-ph](<https://devfeed.tech/tags/quant-ph.md>), [quantum](<https://devfeed.tech/tags/quantum.md>), [quantum-machine-learning](<https://devfeed.tech/tags/quantum-machine-learning.md>), [resource](<https://devfeed.tech/tags/resource.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [theory](<https://devfeed.tech/tags/theory.md>), [training](<https://devfeed.tech/tags/training.md>), [uncertainty](<https://devfeed.tech/tags/uncertainty.md>)

### AI overview

The paper introduces a quantum classification framework that represents uncertainty using Dempster-Shafer weights over individual labels and sets of labels. Its training strategy teaches parameterized quantum circuits to learn these assignments from data, enabling efficient state preparation and different post-processing strategies. The authors say this provides a practical setting for quantum Dempster-Shafer fusion with polynomial resource requirements, even when mass functions range over exponentially many subsets. The abstract presents this as a way to assess quantum predictions beyond average accuracy; it does not provide empirical results or further implementation details.

### Source excerpt

arXiv:2611.16903v1 Announce Type: cross Abstract: A large body of work in quantum machine learning has centered on characterizing the expressivity and performance of quantum models. In contrast, little attention has been paid to the reliability of predictions beyond average performance measures such as accuracy. In this work, we introduce an uncertainty-aware quantum classification framework based on Dempster-Shafer theory. This theory allows to express uncertainty through weights assigned not only to individual classification labels but to sets of labels. We introduce a training strategy that enables parameterized quantum circuits to learn such assignments directly from data. This provides an efficient way to prepare the corresponding quantum states and enables the application of different post-processing strategies. In particular, it offers a practical setting for quantum Dempster-Shafer fusion procedures with polynomial resource requirements, even when the corresponding mass functions are defined over exponentially many subsets. Overall, our work represents a step toward enabling quantum models to express uncertainty about their predictions, thereby extending the evaluation of quantum models beyond predictive performance alone.

[Next page](<https://devfeed.tech/topics/computational-complexity.md?cursor=WyIyMDI2LTExLTEzVDA1OjAwOjAwKzAwOjAwIiwgImIxMzA5MzhjLTFmODItNDBjMi1hNThmLTgwMjI3ZWMwOTY2ZiJd>)