# polynomials

A mathematical expression formed from constants and nonnegative integer powers of variables; in complexity theory, polynomial bounds describe computation measures such as time or memory as a function of problem size.

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

## Statistical Inference with Ill-Conditioned Random Weight Neural Network Sieves

DevFeed: [Statistical Inference with Ill-Conditioned Random Weight Neural Network Sieves](<https://devfeed.tech/articles/statistical-inference-with-ill-conditioned-random-weight-neural-network-sieves-145176.md>)

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

Author: Giovanni Ballarin, Lyudmila Grigoryeva, Lukas Gonon

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

Content type: article

Language: en

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

Topics: [Neural Network](<https://devfeed.tech/topics/neural-network.md>), [linear-regression](<https://devfeed.tech/topics/linear-regression.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [based](<https://devfeed.tech/tags/based.md>), [behavior](<https://devfeed.tech/tags/behavior.md>), [beta](<https://devfeed.tech/tags/beta.md>), [condition](<https://devfeed.tech/tags/condition.md>), [conditional](<https://devfeed.tech/tags/conditional.md>), [consistency](<https://devfeed.tech/tags/consistency.md>), [covariance](<https://devfeed.tech/tags/covariance.md>), [covering](<https://devfeed.tech/tags/covering.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [develop](<https://devfeed.tech/tags/develop.md>), [econ-em](<https://devfeed.tech/tags/econ-em.md>), [inference](<https://devfeed.tech/tags/inference.md>), [network](<https://devfeed.tech/tags/network.md>), [neural](<https://devfeed.tech/tags/neural.md>), [neural-network](<https://devfeed.tech/tags/neural-network.md>), [random](<https://devfeed.tech/tags/random.md>), [stat-me](<https://devfeed.tech/tags/stat-me.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [weight](<https://devfeed.tech/tags/weight.md>), [with](<https://devfeed.tech/tags/with.md>)

### AI overview

The paper shows that random weight neural network sieves become increasingly ill-conditioned as their dimension grows: under polynomial covering and Lipschitz conditions, the population covariance eigenvalues have geometry-dependent polynomial upper bounds, so the smallest eigenvalue vanishes. It develops theory that accounts for this behavior, including faster-than-Monte-Carlo L² approximation and stratified-sampling L∞ bounds under a β-Hölder source condition, plus ridge least-squares consistency guarantees based on effective dimension and stability conditions. For inference, it establishes asymptotic linearity and Gaussian limits for linear directions despite the vanishing eigenvalue; directional nondegeneracy is expressed through a ridge-normalized Rayleigh quotient and extended to smooth functionals using Riesz representation. Consistent ridge-adjusted variance estimation enables feasible studentized inference. The abstract reports numerical experiments on conditioning and finite-sample behavior.

### Source excerpt

arXiv:2611.26410v1 Announce Type: cross Abstract: Random weight neural networks (RWNNs) are shallow networks whose hidden-layer parameters are randomly generated and then kept fixed, while only the output coefficients are estimated. Conditional on the sampled parameters, RWNN regression is a linear sieve problem with random approximation space. We show that such random sieves cannot remain uniformly well-conditioned as their dimension grows. For parametrized feature families satisfying polynomial covering and Lipschitz conditions, the eigenvalues of the population covariance matrix are proven to have polynomial upper bounds determined by the covering geometry of the parameter space, leading to a vanishing smallest eigenvalue. We develop approximation, estimation, and inference theory that explicitly treats the ill-conditioning. Under a $\beta$-H\"older source condition, we obtain both faster-than-Monte-Carlo $L^2$ approximation rates and new $L^\infty$ approximation bounds based on stratified sampling. We then derive improved consistency guarantees for ridge-regularized least squares driven by ridge effective dimension, spectral, and leverage-based stability conditions. For inference, we establish asymptotic linearity and Gaussian limits for linear functional directions while allowing the smallest eigenvalue of the population covariance matrix to vanish. Nondegeneracy is directional: we characterize it with a ridge-normalized Rayleigh quotient and extend it to smooth functionals via Riesz representation. Consistency of ridge-adjusted variance estimators is proved, yielding feasible studentized inference. Numerical experiments illustrate the deterioration of random-feature conditioning and the finite-sample behavior of the resulting estimation and inference procedures.

## Near-Quadratic Sample Compression for All VC Classes

DevFeed: [Near-Quadratic Sample Compression for All VC Classes](<https://devfeed.tech/articles/near-quadratic-sample-compression-for-all-vc-classes-145003.md>)

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

Author: Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Shay Moran, Grigoris Velegkas, Di Wang, Manfred K. Warmuth

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: [concept-learning](<https://devfeed.tech/topics/concept-learning.md>), [compression and generalization](<https://devfeed.tech/topics/compression-and-generalization.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [compression](<https://devfeed.tech/tags/compression.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [learning-algorithms](<https://devfeed.tech/tags/learning-algorithms.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [math-co](<https://devfeed.tech/tags/math-co.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [vc](<https://devfeed.tech/tags/vc.md>)

### AI overview

The paper proves the weaker sample compression conjecture: every binary concept class with VC dimension d admits a sample compression scheme of size O(d² log² d). Such schemes describe a predictor consistent with the training sample using only a subset of that sample, connecting compression with generalization. The stronger conjecture seeks size O(d); the abstract notes that the earlier bound depending only on d was exponential, and does not claim to resolve the stronger conjecture.

### Source excerpt

arXiv:2611.25011v1 Announce Type: new Abstract: The sample compression conjecture is a longstanding open problem in learning theory, originating in the work of Littlestone and Warmuth in the 1980s. At its heart is a connection between simplification and generalization: if a predictor consistent with a training sample is defined using only a small part of that sample, then it is likely to generalize. Sample compression schemes formalize this idea, and many natural learning algorithms can be analyzed this way. The sample compression conjecture of Floyd and Warmuth (1995) asserts that every binary concept class of VC dimension $d$ admits a sample compression scheme of size $O(d)$; a weaker conjecture asks only for size polynomial in $d$. Both have remained open: the first bound depending only on $d$, due to Moran and Yehudayoff (2016), is exponential in $d$. We prove the weaker conjecture by constructing a sample compression scheme of size $O(d^2 \log^2 d)$.

## BeFit: Shifting Complexity from Weights to Bernstein Activations for Resource-Constrained Sensing

DevFeed: [BeFit: Shifting Complexity from Weights to Bernstein Activations for Resource-Constrained Sensing](<https://devfeed.tech/articles/befit-shifting-complexity-from-weights-to-bernstein-activations-for-resource-constrained-sensing-142668.md>)

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

Author: Malak Gamal El-Din, Yasser Shoukry, Salma Elmalaki

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

Content type: article

Language: en

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

Topics: [Neural Network](<https://devfeed.tech/topics/neural-network.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>)

Tags: [architecture](<https://devfeed.tech/tags/architecture.md>), [compression](<https://devfeed.tech/tags/compression.md>), [convolutional-neural-networks](<https://devfeed.tech/tags/convolutional-neural-networks.md>), [cortex-m4](<https://devfeed.tech/tags/cortex-m4.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ar](<https://devfeed.tech/tags/cs-ar.md>), [flash](<https://devfeed.tech/tags/flash.md>), [framework](<https://devfeed.tech/tags/framework.md>), [kernels](<https://devfeed.tech/tags/kernels.md>), [knowledge-distillation](<https://devfeed.tech/tags/knowledge-distillation.md>), [latency](<https://devfeed.tech/tags/latency.md>), [microcontrollers](<https://devfeed.tech/tags/microcontrollers.md>), [mlperf](<https://devfeed.tech/tags/mlperf.md>), [projection](<https://devfeed.tech/tags/projection.md>), [recognition](<https://devfeed.tech/tags/recognition.md>), [relu](<https://devfeed.tech/tags/relu.md>), [risc-v](<https://devfeed.tech/tags/risc-v.md>), [sensing](<https://devfeed.tech/tags/sensing.md>), [tasks](<https://devfeed.tech/tags/tasks.md>), [tensorflow-lite](<https://devfeed.tech/tags/tensorflow-lite.md>), [transformers](<https://devfeed.tech/tags/transformers.md>), [weight](<https://devfeed.tech/tags/weight.md>)

### AI overview

BeFit shifts model capacity from weights to learnable Bernstein polynomial activations to enable compact neural networks with multiplication-free weights for resource-constrained sensing. It uses hardware-aware architecture search and knowledge distillation, projects and freezes weights as multiplication-free codes, then uses learnable activations to recover accuracy; generated kernels exploit those codes. On human activity recognition, BeCNNs averaged 2.75 percentage points higher accuracy than same-architecture ReLU CNNs. On a TI CC3220SF, projection made BeCNNs 2.2x faster with a 0.8-point accuracy loss, compared with a 2.4-point loss for ReLU CNNs. Against the MLPerf Tiny DS-CNN on TensorFlow Lite Micro with CMSIS-NN, the unprojected BeCNN had 1.0-point higher accuracy, 2.2x lower latency, and 6.4x lower flash use; the projected model stayed within 1.0 point of reference accuracy and ran 5.9x faster. RISC-V emulation without a hardware multiplier showed instruction-count reduction rising from 5.2x on Cortex-M4 to 147x. The abstract also reports extensions to transformers and MLPs and a 1.56-point average gap from float32 teachers across tasks.

### Source excerpt

arXiv:2611.23520v1 Announce Type: new Abstract: Time-series sensing increasingly relies on neural networks, yet deployment on resource-constrained microcontrollers remains challenging. Aggressive model compression can reduce accuracy, while restricting weights to multiplication-free representations introduces further losses. We present BeFit, an end-to-end framework that shifts model capacity from weights to learnable Bernstein polynomial activations. BeFit (i) finds compact Bernstein-activated convolutional neural networks (BeCNNs) through hardware-aware neural architecture search and trains them via knowledge distillation; (ii) projects their weights to multiplication-free codes, freezes the codes, and recovers the resulting accuracy loss through the learnable activations; and (iii) generates model-specific kernels that exploit the projected weights for multiplication-free convolutions. On human activity recognition, BeCNNs are 2.75 percentage points (pp) more accurate on average than ReLU CNNs of identical architecture. On a TI CC3220SF (Cortex-M4), weight projection speeds BeCNNs up by 2.2x on average while losing 0.8 pp, compared with 2.4 pp for ReLU CNNs. Against the MLPerf Tiny DS-CNN reference model running on TensorFlow Lite Micro with CMSIS-NN, the unprojected BeCNN achieves 1.0 pp higher accuracy, 2.2x lower latency, and 6.4x lower flash, while the projected model remains within 1.0 pp of the reference accuracy and runs 5.9x faster. In emulation on a RISC-V core without a hardware multiplier, the instruction-count reduction relative to the DS-CNN increases from 5.2x on the Cortex-M4 to 147x. BeFit also extends to transformers and MLPs, and across all tasks the final models stay within 1.56 pp of their float32 teachers on average.

## A Little Advice Suffices: Diffie-Hellman Is as Hard as Discrete Logarithm

DevFeed: [A Little Advice Suffices: Diffie-Hellman Is as Hard as Discrete Logarithm](<https://devfeed.tech/articles/a-little-advice-suffices-diffie-hellman-is-as-hard-as-discrete-logarithm-141484.md>)

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

Author: Yuwen Zhou

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

Content type: article

Language: en

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

Topics: [Mathematics](<https://devfeed.tech/topics/mathematics.md>), [primes](<https://devfeed.tech/topics/primes.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [advice](<https://devfeed.tech/tags/advice.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [diffie-hellman](<https://devfeed.tech/tags/diffie-hellman.md>), [discrete-logarithm](<https://devfeed.tech/tags/discrete-logarithm.md>), [math-nt](<https://devfeed.tech/tags/math-nt.md>), [number-theory](<https://devfeed.tech/tags/number-theory.md>)

### AI overview

The paper removes a 30-year smoothness assumption from a reduction showing that, with advice, computing Diffie-Hellman keys is as hard as computing discrete logarithms. For every prime p, an O(log p)-bit advice string depending only on p lets a Diffie-Hellman oracle compute discrete logarithms in every group of order p in polynomial time. The key input is a proof that every interval [x, x+x^θ], for θ>17/30, contains the expected number of integers smooth with bound (log x)^K, derived from a known zero-free half-plane for the Riemann zeta function. Orders of genus-2 Jacobians provide the auxiliary group. The same result removes the smoothness assumption in two related results and makes Wolf's characterization unconditional: generic equivalence holds exactly when the group order has no large repeated prime factor.

### Source excerpt

arXiv:2611.22290v1 Announce Type: cross Abstract: Is computing a Diffie-Hellman key as hard as computing a discrete logarithm? Maurer showed that it is, given a few bits of advice, provided that short intervals contain enough integers with only small prime factors; that proviso has stood for thirty years. We remove it. For every prime $p$ there is an advice string of $O(\log p)$ bits, depending only on $p$, with which discrete logarithms in every group of order $p$ are computed in polynomial time from a Diffie-Hellman oracle. The reduction is the classical one; what was missing was a proof that short intervals contain polylogarithmically smooth integers. We show that a zero-free half-plane for the Riemann zeta function, which is now known, gives the expected number of $(\log x)^K$-smooth integers in every interval $[x,x+x^\theta]$ with $\theta>17/30$. With smoothness this small the saddle point of the counting integral lies just to the left of the line $\mathrm{Re}\,s=1$, and a zero-free strip of any fixed width absorbs the shift once $K$ is large. Genus-2 Jacobians, whose orders fill such intervals, then turn one of these integers into the order of an auxiliary group. The same input removes the smoothness assumption from Maurer and Raub's impossibility of field-homomorphic one-way permutations and from the yes/no-query reduction of Koblitz, Menezes and Shparlinski. It also makes Wolf's characterisation unconditional: discrete logarithm and Diffie-Hellman are generically equivalent exactly when the group order has no large repeated prime factor.

## Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

DevFeed: [Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse](<https://devfeed.tech/articles/tight-bounds-for-non-monotone-submodular-maximization-under-a-cardinality-constraint-with-constant-recourse-139013.md>)

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

Author: Vaneet Aggarwal

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

Content type: news

Language: en

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

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [3](<https://devfeed.tech/tags/3.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [after](<https://devfeed.tech/tags/after.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [also](<https://devfeed.tech/tags/also.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [best](<https://devfeed.tech/tags/best.md>), [budget](<https://devfeed.tech/tags/budget.md>), [cardinality](<https://devfeed.tech/tags/cardinality.md>), [constraint](<https://devfeed.tech/tags/constraint.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [elements](<https://devfeed.tech/tags/elements.md>), [fixed](<https://devfeed.tech/tags/fixed.md>), [function](<https://devfeed.tech/tags/function.md>), [graph](<https://devfeed.tech/tags/graph.md>), [groups](<https://devfeed.tech/tags/groups.md>), [half](<https://devfeed.tech/tags/half.md>), [inequality](<https://devfeed.tech/tags/inequality.md>), [under](<https://devfeed.tech/tags/under.md>), [with](<https://devfeed.tech/tags/with.md>)

### AI overview

For online maximization of a nonnegative, non-monotone submodular function under a cardinality constraint, the paper gives an algorithm with recourse O(ε⁻²) and expected value at least (1/4−ε) times the best feasible set of arrived elements at every step. It makes polynomially many function evaluations, only on sets of arrived elements. The authors prove 1/4 is the optimal limiting ratio for constant recourse, even with advance knowledge of the function and arrival order and unlimited computation; any fixed ratio above 1/4 requires recourse growing as a positive power of the cardinality budget. The method caps selection probabilities at one half, maintains a bound relating feasible-set values to the expected value of a random set, and gradually replaces elements to round those probabilities. The excerpt reports an improvement over the previous constant-recourse ratio of about 0.172.

### Source excerpt

arXiv:2611.20257v1 Announce Type: cross Abstract: We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every $\epsilon>0$, we give an algorithm with recourse $O(\epsilon^{-2})$ whose reported set has, at every time, expected value at least $1/4-\epsilon$ times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above $1/4$, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above $1/4$ requires recourse that grows as a positive power of the cardinality budget. Thus $1/4$ is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was $3-2\sqrt2\approx0.172$. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.

## A Quasipolynomial Quantum Algorithm for the Vector Dihedral Coset Problem with Smooth Modulus

DevFeed: [A Quasipolynomial Quantum Algorithm for the Vector Dihedral Coset Problem with Smooth Modulus](<https://devfeed.tech/articles/a-quasipolynomial-quantum-algorithm-for-the-vector-dihedral-coset-problem-with-smooth-modulus-139260.md>)

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

Author: Aparna Gupte

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

Content type: article

Language: en

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

Topics: [Quantum Enablement](<https://devfeed.tech/topics/quantum-enablement.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [quant-ph](<https://devfeed.tech/tags/quant-ph.md>), [quantum](<https://devfeed.tech/tags/quantum.md>), [quasipolynomial](<https://devfeed.tech/tags/quasipolynomial.md>), [vector](<https://devfeed.tech/tags/vector.md>)

### AI overview

The paper presents a quantum algorithm that recovers the hidden vector in the vector dihedral coset problem when the modulus is B-smooth. It reduces the modulus one prime factor at a time and uses a sieving procedure to cancel nonlinear phase terms modulo each prime. The stated sample and time complexity is n^{O(B^{1+o(1)} log q)}B^{O(B^{2+o(1)} log q)}; for B=polylog(n) and q=poly(n), both are quasipolynomial. The approach also applies to EDCP, but does not give a new LWE attack: the known LWE-to-EDCP reduction supplies only polynomially many clean samples, fewer than this algorithm requires. The abstract says concurrent work gives similar guarantees for prime-power moduli.

### Source excerpt

arXiv:2611.18857v1 Announce Type: cross Abstract: We give a quantum algorithm for the vector dihedral coset problem over $\mathbb{Z}_q^n$, in which the goal is to recover $\mathbf{s} \in \mathbb{Z}_q^n$ given independent samples of the form $\frac{1}{\sqrt{2}}\bigl(|{0,\mathbf{x}}\rangle+|{1,\mathbf{x}+\mathbf{s}}\rangle\bigr)$, for $\mathbf{x}\sim \mathbb{Z}_q^n$. When the modulus $q$ is $B$-smooth, the algorithm uses $n^{O(B^{1+o(1)}\log q)}B^{O(B^{2+o(1)}\log q)}$ samples and time. For $B = \mathrm{polylog}(n)$ and $q=\mathrm{poly}(n)$, this gives a quasipolynomial time- and sample-complexity. This extends the previously known quasipolynomial-time result for power-of-two moduli (Bonnetain, Naya-Plasencia, ASIACRYPT 2018; Bai, Jangir, Kirshanova, Ngo, Youmans, CRYPTO 2025). The algorithm proceeds by reducing the modulus one prime factor $p | q$ at a time. The key ingredient is a sieving procedure that clears the non-linear terms in the phase modulo $p$ via an algorithm of Ivanyos, Santha (TCS 2017) that finds non-zero $\mathbf{u} \in \mathbb{F}_p^\ell$ such that $\sum_{i \in [\ell]} u_i^d \mathbf{a}_i = 0 \mod p$ for degrees $1 \le d \le p-1$, given vectors $\mathbf{a}_1, \ldots, \mathbf{a}_\ell \in \mathbb{F}_p^n$ as input. The algorithm also applies to the extrapolated dihedral coset problem (EDCP) introduced by Brakerski, Kirshanova, Stehl\'e, Wen (PKC 2018), which is known to be equivalent to LWE in the polynomial sample regime. However, our result does not yield a new attack on LWE in any regime, precisely because the known reduction from LWE to EDCP provides only polynomially many clean samples, whereas our algorithm requires quasipolynomially many samples. The main algorithm was obtained in a GPT-5.6 Sol conversation prompted by the author; the author is responsible for all statements, proofs, and correctness. Concurrent work of Boucher, Fouque, Shen gives an algorithm with similar guarantees for prime-power moduli.

## Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields

DevFeed: [Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields](<https://devfeed.tech/articles/vectorised-hashing-based-on-bernstein-rabin-winograd-polynomials-over-prime-order-fields-139222.md>)

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

Author: Kaushik Nath, Palash Sarkar

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

Content type: article

Language: en

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

Topics: [hashing](<https://devfeed.tech/topics/hashing.md>), [vectorization techniques](<https://devfeed.tech/topics/vectorization-techniques.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>), [primes](<https://devfeed.tech/topics/primes.md>)

Tags: [assembly](<https://devfeed.tech/tags/assembly.md>), [avx2](<https://devfeed.tech/tags/avx2.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [faster](<https://devfeed.tech/tags/faster.md>), [fields](<https://devfeed.tech/tags/fields.md>), [hashing](<https://devfeed.tech/tags/hashing.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [prime](<https://devfeed.tech/tags/prime.md>), [simd](<https://devfeed.tech/tags/simd.md>), [speed](<https://devfeed.tech/tags/speed.md>)

### AI overview

decBRWHash is an AXU hash based on Bernstein-Rabin-Winograd polynomials; choosing parameter c greater than 1 enables c-way SIMD implementation. The authors report hand-optimized AVX2 assembly for 4-decBRWHash and, for comparison, polyHash over the prime fields 2^127−1 and 2^130−5. For 2^130−5, their AVX2 4-decBRWHash implementation is faster than Poly1305 on messages of a few hundred bytes, with reported speedups of about 16% for a few kilobytes and 23% for a few megabytes. These are reported implementation results for the stated field and AVX2 setting.

### Source excerpt

arXiv:2507.06490v3 Announce Type: replace Abstract: We introduce the new AXU hash function decBRWHash, which is parameterised by the positive integer $c$ and is based on Bernstein-Rabin-Winograd (BRW) polynomials. Choosing $c>1$ gives a hash function which can be implemented using $c$-way single instruction multiple data (SIMD) instructions. We report a set of very comprehensive hand optimised assembly implementations of 4-decBRWHash using avx2 SIMD instructions available on modern Intel processors. For comparison, we also report similar carefully optimised avx2 assembly implementations of polyHash, an AXU hash function based on usual polynomials. Our implementations are over prime order fields, specifically the primes $2^{127}-1$ and $2^{130}-5$. For the prime $2^{130}-5$, for avx2 implementations, compared to the famous Poly1305 hash function, 4-decBRWHash is faster for messages which are a few hundred bytes long and achieves a speed-up of about 16% for message lengths in a few kilobytes range and improves to a speed-up of about 23% for message lengths in a few megabytes range.

## 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.

## Axiomatic Positivstellensaetze for Function Algebras over Ordered Fields

DevFeed: [Axiomatic Positivstellensaetze for Function Algebras over Ordered Fields](<https://devfeed.tech/articles/axiomatic-positivstellensaetze-for-function-algebras-over-ordered-fields-137280.md>)

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

Author: Nayoon Kim, Allen Gehret, Shenyuan Ma, Jakub Marecek

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

Content type: article

Language: en

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

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>), [mlp](<https://devfeed.tech/topics/mlp.md>)

Tags: [activation](<https://devfeed.tech/tags/activation.md>), [algebra](<https://devfeed.tech/tags/algebra.md>), [certificate](<https://devfeed.tech/tags/certificate.md>), [certificates](<https://devfeed.tech/tags/certificates.md>), [closure](<https://devfeed.tech/tags/closure.md>), [continuous](<https://devfeed.tech/tags/continuous.md>), [core](<https://devfeed.tech/tags/core.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cubic](<https://devfeed.tech/tags/cubic.md>), [field](<https://devfeed.tech/tags/field.md>), [fields](<https://devfeed.tech/tags/fields.md>), [fixed](<https://devfeed.tech/tags/fixed.md>), [framework](<https://devfeed.tech/tags/framework.md>), [function](<https://devfeed.tech/tags/function.md>), [functions](<https://devfeed.tech/tags/functions.md>), [global](<https://devfeed.tech/tags/global.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [networks](<https://devfeed.tech/tags/networks.md>), [neural](<https://devfeed.tech/tags/neural.md>), [neural-networks](<https://devfeed.tech/tags/neural-networks.md>), [number](<https://devfeed.tech/tags/number.md>)

### AI overview

The paper gives an axiomatic framework for constructive strict and weak Positivstellensätze over ordered fields and algebras of functions, extending positivity certificates beyond polynomials and smooth functions. With five auxiliary function symbols and closure axioms, it constructs witnesses by substituting the problem data into fixed terms depending only on the number of constraints. The framework recovers Fischer's results for definable C^r functions and covers additional algebras, including those with arbitrary auxiliary functions, continuous functions with criteria tied to common activation functions, and continuous functions valued in fields such as Q that are not closed under square roots. It derives certificates for lower bounds and global optimality; expanded term length is cubic in the number of constraints for strict certificates and quadratic for weak ones.

### Source excerpt

arXiv:2609.08736v2 Announce Type: replace Abstract: Positivstellensaetze furnish algebraic certificates of positivity, and hence of lower bounds and of global optimality, but the classical ones concern polynomials, whereas many problems of current interest, among them the training of neural networks, involve functions that are neither polynomial nor smooth. We isolate an axiomatic core of the constructive Positivstellensaetze of Fischer. The setting consists of an ordered field expanded by five auxiliary function symbols, subject to a few first-order axioms, together with an algebra of functions on an arbitrary set, subject to closure axioms. In this setting we prove a strict and a weak Positivstellensatz in which the witnesses are obtained by substituting the data into fixed terms that depend only on the number of constraints. The framework recovers Fischer's theorems for definable $C^r$-functions, and yields new instances: algebras of definable functions with arbitrary auxiliary functions, such as the binary step function; algebras of continuous functions, for which we give simple sufficient criteria and auxiliary functions derived from common activation functions; and algebras of continuous functions with values in an ordered field that is not closed under square roots, such as $\mathbb{Q}$. We derive certificates of lower bounds and of global optimality, and show that their expanded term length is cubic in the number of constraints for the strict certificate and quadratic for the weak one.

## Finite speed Ornstein-Uhlenbeck-Kac processes and their applications in generative modeling

DevFeed: [Finite speed Ornstein-Uhlenbeck-Kac processes and their applications in generative modeling](<https://devfeed.tech/articles/finite-speed-ornstein-uhlenbeck-kac-processes-and-their-applications-in-generative-modeling-135810.md>)

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

Author: Richard Duong, Janis Auffenberg, Gabriele Steidl

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

Content type: article

Language: en

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

Topics: [3D](<https://devfeed.tech/topics/3d.md>), [stable-diffusion](<https://devfeed.tech/topics/stable-diffusion.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Image](<https://devfeed.tech/topics/image.md>)

Tags: [applications](<https://devfeed.tech/tags/applications.md>), [bounded](<https://devfeed.tech/tags/bounded.md>), [cifar-10](<https://devfeed.tech/tags/cifar-10.md>), [conditional](<https://devfeed.tech/tags/conditional.md>), [convergence](<https://devfeed.tech/tags/convergence.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [data](<https://devfeed.tech/tags/data.md>), [diffusion](<https://devfeed.tech/tags/diffusion.md>), [diffusion-models](<https://devfeed.tech/tags/diffusion-models.md>), [fields](<https://devfeed.tech/tags/fields.md>), [flow](<https://devfeed.tech/tags/flow.md>), [flow-matching](<https://devfeed.tech/tags/flow-matching.md>), [framework](<https://devfeed.tech/tags/framework.md>), [generation](<https://devfeed.tech/tags/generation.md>), [generative](<https://devfeed.tech/tags/generative.md>), [image](<https://devfeed.tech/tags/image.md>), [image-generation](<https://devfeed.tech/tags/image-generation.md>), [law](<https://devfeed.tech/tags/law.md>), [math-ap](<https://devfeed.tech/tags/math-ap.md>), [math-pr](<https://devfeed.tech/tags/math-pr.md>), [modeling](<https://devfeed.tech/tags/modeling.md>), [processes](<https://devfeed.tech/tags/processes.md>), [speed](<https://devfeed.tech/tags/speed.md>)

### AI overview

The Ornstein-Uhlenbeck-Kac (OU-K) process replaces Brownian driving noise with a finite-speed Kac process. The authors relate it to a rescaled, time-inhomogeneous Kac process whose law solves the Euler-Poisson-Darboux wave equation; for specified switching rates, they derive an explicit solution using Legendre polynomials between the wave fronts. Using piecewise-deterministic Markov processes, they obtain conditional velocity fields bounded by the Kac speed and apply them in a generative flow model, removing the need for the usual diffusion-model time truncations. They report sharper generation on singular data sets than diffusion and flow-matching models, and competitive CIFAR-10 image-generation results.

### Source excerpt

arXiv:2611.17625v1 Announce Type: cross Abstract: We study the Ornstein-Uhlenbeck-Kac (OU-K) process, where instead of a Brownian motion, a finite-speed Kac process defines the driving process. The OU-K process can be analyzed through a rescaled, time-inhomogeneous Kac process, characterized by a switching rate from the Kac part, and a convergence rate from the Ornstein-Uhlenbeck (OU) part. The law of this inhomogeneous Kac process describes the solution of a wave equation, the Euler-Poisson-Darboux (EPD) equation. For Kac switching rates being multiples of the OU convergence rate, we can explicitly derive this EPD solution via the sum of (the derivative of) two Legendre polynomials, restricted between two Dirac points representing the wave fronts. Using the framework of piecewise-deterministic Markov processes (PDMP), we describe the conditional velocity fields of the OU-K process via our polynomial-law-formula. This allows us to apply the OU-K process in a generative flow model. Since the OU-K velocity fields prove to be bounded by the finite Kac speed, the usual time truncations of diffusion models become unnecessary. We demonstrate advantages over diffusion and flow matching models in terms of generation sharpness on singular data sets, while achieving competitive results on CIFAR-10 image generation.

## Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS

DevFeed: [Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS](<https://devfeed.tech/articles/sparse-pca-with-overlapping-supports-np-hardness-and-an-fptas-133040.md>)

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

Author: Alberto Del Pia, Dekun Zhou

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

Content type: article

Language: en

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

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [approximation](<https://devfeed.tech/tags/approximation.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [dynamic-programming](<https://devfeed.tech/tags/dynamic-programming.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [orthogonality](<https://devfeed.tech/tags/orthogonality.md>), [overlap](<https://devfeed.tech/tags/overlap.md>), [principal-component-analysis](<https://devfeed.tech/tags/principal-component-analysis.md>), [sparsity](<https://devfeed.tech/tags/sparsity.md>)

### AI overview

The paper studies sparse PCA with multiple orthogonal components, individual sparsity limits, and arbitrary overlap between supports. It proves the problem is NP-hard even with rank and component count both 2, yet gives an FPTAS when rank and component count are fixed. The algorithm returns exactly orthonormal columns represented by real algebraic numbers; for fixed ε, its number of steps is linear in the data dimension up to polylogarithmic factors. The approach reduces the problem to sparse orthogonal Procrustes optimization and combines approximate row-wise dynamic programming, two-column updates to restore exact orthogonality, and exact computation for the few variables those updates cannot handle.

### Source excerpt

arXiv:2611.15810v1 Announce Type: new Abstract: In sparse principal component analysis (SPCA) with several components, each must be sparse and all must be pairwise orthogonal. When the supports of the components overlap, these two requirements interact. For a covariance matrix of fixed rank, polynomial-time algorithms with optimality or approximation guarantees are known for one component, and for several components with disjoint supports or with a common support. We study the general model, with individual sparsity constants and arbitrary support overlaps. We are given a rational $n\times r$ matrix $R$ and $d$ sparsity constants $s_i \le n$, and the goal is to find an $n\times d$ matrix $X$ with orthonormal columns that maximizes $\|R^\top X\|_F^2$, such that column $i$ has at most $s_i$ non-zero entries. Here $RR^\top$ plays the role of the covariance matrix and has rank at most $r$. We show that SPCA is NP-hard even when $r = d = 2$, but admits a fully polynomial-time approximation scheme (FPTAS) when $r$ and $d$ are fixed. The returned solution has exactly orthonormal columns, and its entries are real algebraic numbers in an exact representation. For fixed $\epsilon$, the number of steps of the algorithm is linear in $n$ up to a polylogarithmic factor. Our approach reduces SPCA to a sparse version of the orthogonal Procrustes problem, that is, to maximizing a linear function over the feasible region of SPCA. We show that this problem is NP-hard even for $d = 2$, and we give an FPTAS for it when $d$ is fixed. This FPTAS combines approximate dynamic programming over the rows, two-column updates that restore exact orthogonality, and an exact computation of the few variables for which these updates are not available.

## Learning-augmented smooth integer programs with PAC-learnable oracles

DevFeed: [Learning-augmented smooth integer programs with PAC-learnable oracles](<https://devfeed.tech/articles/learning-augmented-smooth-integer-programs-with-pac-learnable-oracles-131874.md>)

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

Author: Hao-Yuan He, Jiang-Tian Xue, Ming Li, Zhi-Hua Zhou

Published: 2026-11-13T05: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>), [Predictive AI](<https://devfeed.tech/topics/predictive-ai.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [boolean](<https://devfeed.tech/tags/boolean.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [error](<https://devfeed.tech/tags/error.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [framework](<https://devfeed.tech/tags/framework.md>), [guarantees](<https://devfeed.tech/tags/guarantees.md>), [learning](<https://devfeed.tech/tags/learning.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [oracles](<https://devfeed.tech/tags/oracles.md>)

### AI overview

LEAP improves predicted Boolean assignments for fixed-degree smooth integer programs, including MAX-CUT and MAX-k-SAT. It linearizes the objective around each predicted assignment, solves an error-budgeted linear program, then rounds the fractional solution. Its approximation loss degrades with prediction error according to an error footprint measuring how mispredicted coordinates affect local coefficients. A bound on the pseudo-dimension of LEAP's induced cost class supports PAC-style oracle learning by empirical risk minimization, with an end-to-end guarantee separating the best in-class oracle's expected footprint loss from learning error. Experiments report substantial repair of imperfect predictions and scaling to benchmarks with up to two million clauses.

### Source excerpt

arXiv:2602.02505v2 Announce Type: replace-cross Abstract: We study an end-to-end learning-augmented framework for smooth integer programs, a broad class of Boolean polynomial optimization problems including MAX-CUT and MAX-k-SAT. An oracle learned from sampled instances predicts a full Boolean assignment for each unseen instance. For fixed-degree objectives, our polynomial-time pipeline, LEAP, linearizes the objective around the predicted assignment, solves an error-budgeted linear program, and rounds the fractional solution. We establish two guarantees. First, for any prediction, the approximation loss of LEAP degrades gracefully with prediction error: it is controlled by an error footprint that quantifies how much mispredicted coordinates can perturb the objective's local coefficients. Second, we bound the pseudo-dimension of the LEAP-induced cost class, yielding a PAC-style guarantee for learning an oracle from a predictor class via empirical risk minimization on instances from an unknown distribution. Together, these results give an end-to-end bound that separates the expected footprint loss of the best oracle in the class from the statistical error of learning. In experiments on MAX-CUT and MAX-SAT, LEAP substantially repairs imperfect predictions, empirical risk minimization selects effective oracle candidates, and the pipeline scales to application benchmarks with up to two million clauses.

## A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces

DevFeed: [A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces](<https://devfeed.tech/articles/a-near-optimal-sq-lower-bound-for-smoothed-agnostic-learning-of-boolean-halfspaces-132775.md>)

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

Author: Tim Sinen

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>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [boolean](<https://devfeed.tech/tags/boolean.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [continuous](<https://devfeed.tech/tags/continuous.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [gaussian](<https://devfeed.tech/tags/gaussian.md>), [learning](<https://devfeed.tech/tags/learning.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [polynomial-regression](<https://devfeed.tech/tags/polynomial-regression.md>), [query](<https://devfeed.tech/tags/query.md>), [regression](<https://devfeed.tech/tags/regression.md>), [runtime](<https://devfeed.tech/tags/runtime.md>), [sample](<https://devfeed.tech/tags/sample.md>)

### AI overview

For smoothed agnostic learning of Boolean halfspaces on {±1}ⁿ with uniform marginals and independently flipped coordinates at rate σ, the paper gives nearly matching upper and lower complexity bounds. L¹ polynomial regression achieves runtime and sample complexity Õ(n^{O(log(1/ε)/σ)}), while the Statistical Query complexity is at least n^{Ω(log(1+σ/ε²)/σ)}. The result complements analogous bounds for Gaussian marginals in the continuous setting.

### Source excerpt

arXiv:2605.02350v3 Announce Type: replace Abstract: We study the complexity of smoothed agnostic learning of halfspaces on $\{\pm 1\}^n$ under uniform marginals in the model of~\cite{KM25}, where each input coordinate is independently flipped with probability $\sigma \in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\tilde{O}(n^{O(\log(1/\varepsilon)/\sigma)})$, and prove a nearly matching Statistical Query complexity lower bound of $n^{\Omega(\log(1+\sigma/\varepsilon^2)/\sigma)}$. This complements the recent work of~\cite{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.

## Combinatorial Bernoulli Factories with Polynomially Many Coins

DevFeed: [Combinatorial Bernoulli Factories with Polynomially Many Coins](<https://devfeed.tech/articles/combinatorial-bernoulli-factories-with-polynomially-many-coins-133191.md>)

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

Author: Renato Paes Leme, Rad Niazadeh

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

Content type: article

Language: en

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

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [2021](<https://devfeed.tech/tags/2021.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [bernoulli](<https://devfeed.tech/tags/bernoulli.md>), [boundary](<https://devfeed.tech/tags/boundary.md>), [class](<https://devfeed.tech/tags/class.md>), [coin](<https://devfeed.tech/tags/coin.md>), [coins](<https://devfeed.tech/tags/coins.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-gt](<https://devfeed.tech/tags/cs-gt.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [cube](<https://devfeed.tech/tags/cube.md>), [deep](<https://devfeed.tech/tags/deep.md>), [delta](<https://devfeed.tech/tags/delta.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [expectation](<https://devfeed.tech/tags/expectation.md>), [factory](<https://devfeed.tech/tags/factory.md>), [gives](<https://devfeed.tech/tags/gives.md>), [i](<https://devfeed.tech/tags/i.md>), [implementation](<https://devfeed.tech/tags/implementation.md>), [math-pr](<https://devfeed.tech/tags/math-pr.md>), [stat-co](<https://devfeed.tech/tags/stat-co.md>), [with](<https://devfeed.tech/tags/with.md>)

### AI overview

The paper presents a single combinatorial Bernoulli factory for every affine slice of the cube, producing a random vertex whose mean equals the unknown coin-bias vector. At any interior point, its expected coin flips and running time are polynomial in the dimension and in 1/δ*, where δ* is the minimum distance of any bias from 0 or 1 and need not be given to the algorithm. For perfect matchings, it uses O(n⁸δ*⁻² log(n/δ*)) flips; the cited Niazadeh-Paes Leme-Schneider factory requires at least n^(2n−1) expected flips at the uniform doubly stochastic matrix. For other polytopes, exact rounding is guaranteed when given a point deep inside the polytope and a promise that the input is far from its boundary.

### Source excerpt

arXiv:2611.17223v1 Announce Type: cross Abstract: We provide an efficient implementation of combinatorial Bernoulli factories. Such a factory turns coins of unknown biases $x$ into a random vertex of a polytope $P$ whose mean is exactly $x$. For every affine slice of the cube (the class of polytopes that admit a factory), we give a single algorithm whose expected number of coin flips and running time at every interior $x$ are polynomial in the dimension and in $1/{\delta_*}$, where ${\delta_*}=\min_i\{x_i,1-x_i\}$ is never supplied to the algorithm. For perfect matchings this gives $O(n^{8}{\delta_*}^{-2}\log(n/{\delta_*}))$ flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least $n^{2n-1}$ flips in expectation at the uniform doubly stochastic matrix. For other polytopes, our method rounds exactly given a point deep inside $P$ and the promise that $x$ is far from the boundary of $P$.

## Low-degree lower bounds via almost orthonormal bases

DevFeed: [Low-degree lower bounds via almost orthonormal bases](<https://devfeed.tech/articles/low-degree-lower-bounds-via-almost-orthonormal-bases-128484.md>)

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

Author: Alexandra Carpentier (LMO, CELESTE), Simone Maria Giancola (LMO, CELESTE), Christophe Giraud (LMO, CELESTE), Nicolas Verzelen (MISTEA)

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

Content type: article

Language: en

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

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

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [block](<https://devfeed.tech/tags/block.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [detection](<https://devfeed.tech/tags/detection.md>), [hidden](<https://devfeed.tech/tags/hidden.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [machine](<https://devfeed.tech/tags/machine.md>), [models](<https://devfeed.tech/tags/models.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [random-graph](<https://devfeed.tech/tags/random-graph.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>)

### AI overview

For random graph models, the authors construct polynomial bases that are almost orthonormal under the null distribution in regimes where statistical-computational gaps arise. This offers a direct way to prove low-degree lower bounds in settings where the standard orthonormal-family approach breaks down, such as estimation or testing with planted structure in the null. The basis also identifies polynomials optimizing the low-degree criterion, potentially informing polynomial-time algorithm design. The abstract says the method recovers known lower bounds and establishes new ones for hidden subcliques, stochastic block models, and seriation models; it does not provide the technical details of the constructions or bounds.

### Source excerpt

arXiv:2509.09353v3 Announce Type: replace-cross Abstract: Low-degree polynomials have emerged as a powerful paradigm for providing evidence of statistical--computational gaps across a variety of high-dimensional statistical models [Wein25]. For detection problems---where the goal is to test a planted distribution $\mathbb{P}'$ against a null distribution $\mathbb{P}$ with independent components---the standard approach is to bound the advantage using an $\mathbb{L}^2(\mathbb{P})$-orthonormal family of polynomials. However, this method breaks down for estimation tasks or more complex testing problems where $\mathbb{P}$ has some planted structures, so that no simple $\mathbb{L}^2(\mathbb{P})$-orthogonal polynomial family is available. To address this challenge, several technical workarounds have been proposed [SW22,SW25], though their implementation can be delicate. In this work, we propose a more direct proof strategy. Focusing on random graph models, we construct a basis of polynomials that is almost orthonormal under $\mathbb{P}$, in precisely those regimes where statistical--computational gaps arise. This almost orthonormal basis not only yields a direct route to establishing low-degree lower bounds, but also allows us to explicitly identify the polynomials that optimize the low-degree criterion. This, in turn, provides insights into the design of optimal polynomial-time algorithms. We illustrate the effectiveness of our approach by recovering known low-degree lower bounds, and establishing new ones for problems such as hidden subcliques, stochastic block models, and seriation models.

## Tropical Gaussian Anticoncentration: Optimal Instance-Dependent Bounds for Online Learning in Extensive-Form Games

DevFeed: [Tropical Gaussian Anticoncentration: Optimal Instance-Dependent Bounds for Online Learning in Extensive-Form Games](<https://devfeed.tech/articles/tropical-gaussian-anticoncentration-optimal-instance-dependent-bounds-for-online-learning-in-extensive-form-games-125465.md>)

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

Author: Ashkan Soleymani, Zhiyuan Fan, Lillian J. Ratliff, Patrick Jaillet, Gabriele Farina

Published: 2026-11-10T05: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>), [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>), [decision-making](<https://devfeed.tech/topics/decision-making.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [advice](<https://devfeed.tech/tags/advice.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [correlation](<https://devfeed.tech/tags/correlation.md>), [cs-gt](<https://devfeed.tech/tags/cs-gt.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [decision](<https://devfeed.tech/tags/decision.md>), [decision-making](<https://devfeed.tech/tags/decision-making.md>), [distribution](<https://devfeed.tech/tags/distribution.md>), [entropy](<https://devfeed.tech/tags/entropy.md>), [experts](<https://devfeed.tech/tags/experts.md>), [games](<https://devfeed.tech/tags/games.md>), [gaussian](<https://devfeed.tech/tags/gaussian.md>), [index](<https://devfeed.tech/tags/index.md>), [information](<https://devfeed.tech/tags/information.md>), [learning](<https://devfeed.tech/tags/learning.md>), [log](<https://devfeed.tech/tags/log.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [minimax](<https://devfeed.tech/tags/minimax.md>), [mirror](<https://devfeed.tech/tags/mirror.md>), [online](<https://devfeed.tech/tags/online.md>), [online-learning](<https://devfeed.tech/tags/online-learning.md>), [reward](<https://devfeed.tech/tags/reward.md>)

### AI overview

The paper proves that treeplex online learning has worst-case full-information minimax regret Θ(√(T log|𝒱|)), matching the known upper-bound dependence achieved by KOMWU and online mirror descent with weight-one dilated entropy. The challenge is that pure plans' rewards are correlated by recursive decisions and observations. The authors model this with tropical Gaussian formulae and prove a Gaussian-width lower bound for log-balanced formulas using a spherical entropy profile, Turán's theorem, and Sudakov minoration. Applied to treeplexes, this yields an oblivious hard distribution with valid transition outcomes and Rademacher terminal rewards, showing the dependence on reduced normal-form complexity is unavoidable up to universal constants.

### Source excerpt

arXiv:2611.11877v1 Announce Type: new Abstract: We study the minimax regret of full-information online decision making in extensive-form games. For prediction with expert advice, the optimal regret is $\Theta(\sqrt{T\log K})$, where $K$ is the number of experts, or equivalently, the number of normal-form actions. For treeplex strategy spaces, existing efficient algorithms, including KOMWU and online mirror descent with the weight-one dilated entropy regularizer, achieve regret $\mathcal{O}(\sqrt{T\log|\mathcal{V}|})$, where $\mathcal{V}$ is the set of reduced normal-form strategies. We prove that this logarithmic dependence is minimax optimal in the worst-case full-information reward model. The main difficulty is that pure plans in a treeplex are not independent experts: their rewards are correlated through the recursive structure of decisions and observations. To capture this correlation, we introduce tropical Gaussian formulae, recursive Gaussian expressions built from maxima and normalized sums which preserve the variance. The index count of such a formula matches the number of reduced normal-form continuation plans in the corresponding subtree. Our main analytic result shows that every log-balanced tropical Gaussian formula with index count $N$ has Gaussian width $\Omega(\sqrt{\log N})$. While a direct approach struggles to recover this lower bound, our proof uses a spherical entropy profile to measure scale-dependent separation among the Gaussian directions, and then applies Tur\'an's theorem and Sudakov minoration to obtain the width lower bound. Applying this result to treeplexes gives an oblivious hard distribution with valid transition outcome and Rademacher terminal rewards, establishing a regret lower bound of $\Omega(\sqrt{T\log|\mathcal{V}|})$. This matches known upper bounds up to universal constants and shows that the DilEnt/KOMWU dependence on the reduced normal-form complexity is unavoidable.

## Expanding Codes with Polynomial Stretch

DevFeed: [Expanding Codes with Polynomial Stretch](<https://devfeed.tech/articles/expanding-codes-with-polynomial-stretch-126879.md>)

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

Author: Isaac M Hair, Amit Sahai

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

Content type: article

Language: en

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

Topics: [homomorphic encryption](<https://devfeed.tech/topics/homomorphic-encryption.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [2016](<https://devfeed.tech/tags/2016.md>), [2018](<https://devfeed.tech/tags/2018.md>), [2026](<https://devfeed.tech/tags/2026.md>), [applications](<https://devfeed.tech/tags/applications.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [encryption](<https://devfeed.tech/tags/encryption.md>), [generator](<https://devfeed.tech/tags/generator.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [locality](<https://devfeed.tech/tags/locality.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [matrix](<https://devfeed.tech/tags/matrix.md>), [noise](<https://devfeed.tech/tags/noise.md>), [public-key](<https://devfeed.tech/tags/public-key.md>), [stretch](<https://devfeed.tech/tags/stretch.md>), [test](<https://devfeed.tech/tags/test.md>), [vector](<https://devfeed.tech/tags/vector.md>), [weight](<https://devfeed.tech/tags/weight.md>), [xor](<https://devfeed.tech/tags/xor.md>)

### AI overview

For each constant ε in (0, 1/2), the authors construct binary matrices with n columns, polynomially many rows, and row weight k = O(ε⁻⁶). Any set of at most n^(1−ε) rows has supports whose union covers at least (1−ε)k times the number of rows. Despite this expansion, a polynomial-time test accepts codewords corrupted on up to a 1/2−ε fraction of coordinates and rejects a uniformly random vector with high probability. Applications include distinguishing Goldreich's XOR-MAJ generator from uniform on nearly lossless constant-locality expanders, and public-key encryption based on stated kXOR, Goldreich, or planted-hypergraph conjectures. The authors also report low-degree and Schur-product dimension-test lower bounds; the planting lower bounds provide evidence for subexponential hardness.

### Source excerpt

arXiv:2604.10479v2 Announce Type: replace Abstract: We give a polynomial-stretch, constant-arity counterpart to the expanding-code construction of Blasiok, Lou, Rosen, and Sudan (FOCS 2026). For every constant $\varepsilon\in(0,1/2)$, we construct binary matrices with $n$ columns and polynomially many rows, each of weight $k=O(\varepsilon^{-6})$, such that the union of the supports of any set of at most $n^{1-\varepsilon}$ rows has size at least $(1-\varepsilon)k$ times the number of rows. Nevertheless, a polynomial-time test accepts every codeword (generated by the columns of this matrix) corrupted in at most a $1/2-\varepsilon$ fraction of its coordinates, while rejecting a uniformly random vector with high probability. We give two applications. First, we obtain a family of (nearly lossless) constant locality expanders on which Goldreich's pseudorandom generator with the XOR-MAJ predicate can be distinguished from uniform in polynomial time, well within the small-bias parameter regime and the hard regime for known algebraic-immunity/annihilator attacks and algebraic-degree linearization attacks described by Applebaum and Lovett (STOC 2016, SICOMP 2018). Second, we obtain public key encryption from either the constant-noise $k$XOR conjecture over random graphs or the Goldreich conjecture with XOR-MAJ over random graphs, together with a new planted-hypergraph conjecture. We prove low-degree lower bounds for the planting conjecture, providing evidence for subexponential hardness, and give lower bounds against dimension tests based on coordinatewise products (Schur products) of public-code vectors. The PKE schemes and lower bounds were discovered by the authors. The code construction was discovered by Codex / ChatGPT 6 Astra Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

## Polynomial Denoisers on the Image Manifold: Volterra Networks for Self-Contained Pixel Diffusion

DevFeed: [Polynomial Denoisers on the Image Manifold: Volterra Networks for Self-Contained Pixel Diffusion](<https://devfeed.tech/articles/polynomial-denoisers-on-the-image-manifold-volterra-networks-for-self-contained-pixel-diffusion-126033.md>)

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

Author: Siddharth Roheda, Rohit Chowdhury, Amit Satish Unde, Aniruddha Bala

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

Content type: article

Language: en

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

Topics: [diffusion-transformers](<https://devfeed.tech/topics/diffusion-transformers.md>), [model architecture](<https://devfeed.tech/topics/model-architecture.md>), [ai-image-generator](<https://devfeed.tech/topics/ai-image-generator.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>), [ImageNet](<https://devfeed.tech/topics/imagenet.md>)

Tags: [activation](<https://devfeed.tech/tags/activation.md>), [activation-function](<https://devfeed.tech/tags/activation-function.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [architecture](<https://devfeed.tech/tags/architecture.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [attention](<https://devfeed.tech/tags/attention.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [denoising](<https://devfeed.tech/tags/denoising.md>), [diffusion](<https://devfeed.tech/tags/diffusion.md>), [diffusion-models](<https://devfeed.tech/tags/diffusion-models.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [embedding](<https://devfeed.tech/tags/embedding.md>), [function](<https://devfeed.tech/tags/function.md>), [gaussian](<https://devfeed.tech/tags/gaussian.md>), [image](<https://devfeed.tech/tags/image.md>), [images](<https://devfeed.tech/tags/images.md>), [layer](<https://devfeed.tech/tags/layer.md>), [layers](<https://devfeed.tech/tags/layers.md>), [linear](<https://devfeed.tech/tags/linear.md>), [networks](<https://devfeed.tech/tags/networks.md>), [pixel](<https://devfeed.tech/tags/pixel.md>)

### AI overview

The abstract argues that Volterra layers can model polynomial denoisers that normalized mixing rules such as softmax and linear attention cannot represent beyond affine maps. The proposed self-contained pixel-space diffusion model embeds raw image patches through a bottleneck, then applies cascaded low-rank Volterra layers, with no attention, convolution, pretrained components, or residual-path activations. The authors say its approximation rates on a data manifold depend on manifold dimension, and report competitive ImageNet results at 256x256 and 512x512 against self-contained pixel-space diffusion models with matched parameter and FLOP budgets.

### Source excerpt

arXiv:2611.10857v1 Announce Type: new Abstract: Natural images are often conjectured to lie on a low-dimensional manifold within the high-dimensional pixel space. Recent work leverages this to build self-contained pixel-space diffusion models without specialized machinery or pretrained components. A plain Transformer on raw image patches suffices, provided it predicts the clean image rather than the noise and compresses each patch through an aggressive bottleneck. The mixing operator, however, has remained softmax attention, inherited from sequence modeling rather than derived from denoising. For Gaussian noise, the optimal denoiser admits a canonical expansion in polynomial functionals of the observation, the Wiener--Volterra series. We prove that softmax attention, and any normalized mixing rule (including linear attention), cannot realize any polynomial map beyond an affine one. In contrast, Volterra layers realize this class directly and, on a data manifold, achieve approximation rates governed by the manifold dimension rather than the ambient pixel dimension. We therefore propose the architecture these results prescribe; raw image patches passed through a bottleneck embedding, followed by cascaded low-rank Volterra layers, which carry no activation function because each layer is nonlinear in its own right. To our knowledge this is the first pixel-space diffusion architecture whose mixing operators are Volterra layers throughout, with no attention, no convolution, no pretrained components, and no activation function on the residual path. On ImageNet $256 \times 256$ and $512 \times 512$, the resulting model is competitive with self-contained pixel-space diffusion at matched parameter and FLOP budgets.

## Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

DevFeed: [Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead](<https://devfeed.tech/articles/optimal-polynomial-query-approximation-for-consistent-submodular-maximization-with-short-lookahead-125327.md>)

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

Author: Vaneet Aggarwal

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

Content type: article

Language: en

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

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [3](<https://devfeed.tech/tags/3.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [after](<https://devfeed.tech/tags/after.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [all](<https://devfeed.tech/tags/all.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [best](<https://devfeed.tech/tags/best.md>), [bounded](<https://devfeed.tech/tags/bounded.md>), [can](<https://devfeed.tech/tags/can.md>), [changes](<https://devfeed.tech/tags/changes.md>), [combined](<https://devfeed.tech/tags/combined.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [element](<https://devfeed.tech/tags/element.md>), [elements](<https://devfeed.tech/tags/elements.md>), [evaluations](<https://devfeed.tech/tags/evaluations.md>), [lookahead](<https://devfeed.tech/tags/lookahead.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [query](<https://devfeed.tech/tags/query.md>), [with](<https://devfeed.tech/tags/with.md>)

### AI overview

For streaming monotone submodular maximization with a held set of at most k arrived elements and bounded changes per arrival, short lookahead raises the best polynomial-query approximation ratio from 2−√2 to the optimal 1−1/e. For any ε>0, a deterministic algorithm seeing the next ⌈εk/3⌉ arrivals achieves at least 1−1/e−ε of the current optimum at every time, with O(ε⁻³) changes per arrival and (n+1)^O(ε⁻²) evaluations. Knowing the full sequence in advance reduces deterministic changes to O(ε⁻²) per arrival; a randomized short-lookahead algorithm also uses O(ε⁻²) changes, with O(n²k) evaluations and the guarantee in expectation at each fixed time. The abstract states that no polynomial-evaluation algorithm exceeds 1−1/e, even with all elements available at once.

### Source excerpt

arXiv:2611.11124v1 Announce Type: cross Abstract: Elements arrive one at a time, and after each arrival an algorithm holds a set of at most $k$ arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that $k$ arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of $k$ and of the number $n$ of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is $2-\sqrt{2}\approx0.5858$. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to $1-1/e\approx0.6321$, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds $1-1/e$, even when all elements are available at once. For every $\varepsilon>0$, a deterministic algorithm that sees the next $\lceil\varepsilon k/3\rceil$ arrivals keeps a set of value at least $1-1/e-\varepsilon$ times the optimum at every time, changes $O(\varepsilon^{-3})$ elements per arrival and makes $(n+1)^{O(\varepsilon^{-2})}$ evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with $O(\varepsilon^{-2})$ changes per arrival. A randomized algorithm with the same short lookahead makes $O(n^2k)$ evaluations, changes $O(\varepsilon^{-2})$ elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.

## Evidence or Marginal? What Moment-Vector Propagation Computes in Polynomial Density Neurons

DevFeed: [Evidence or Marginal? What Moment-Vector Propagation Computes in Polynomial Density Neurons](<https://devfeed.tech/articles/evidence-or-marginal-what-moment-vector-propagation-computes-in-polynomial-density-neurons-125547.md>)

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

Author: Przemys{\\l}aw Spyra

Published: 2026-11-10T05: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: [Neural Network](<https://devfeed.tech/topics/neural-network.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [all](<https://devfeed.tech/tags/all.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [bayesian](<https://devfeed.tech/tags/bayesian.md>), [beta](<https://devfeed.tech/tags/beta.md>), [cd](<https://devfeed.tech/tags/cd.md>), [conditional](<https://devfeed.tech/tags/conditional.md>), [correlation](<https://devfeed.tech/tags/correlation.md>), [costs](<https://devfeed.tech/tags/costs.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [d](<https://devfeed.tech/tags/d.md>), [data](<https://devfeed.tech/tags/data.md>), [eu](<https://devfeed.tech/tags/eu.md>), [exceptions](<https://devfeed.tech/tags/exceptions.md>), [factor](<https://devfeed.tech/tags/factor.md>), [fall](<https://devfeed.tech/tags/fall.md>), [family](<https://devfeed.tech/tags/family.md>), [flat](<https://devfeed.tech/tags/flat.md>), [vector](<https://devfeed.tech/tags/vector.md>)

### AI overview

Moment-vector propagation, p_CD = E_q[N]/E_q[D], answers a different question from p_EU = E_q[N/D]: in a density model, p_CD treats belief q as virtual evidence, while p_EU installs q as a new marginal via Jeffrey's rule. When an input is missing, p_CD returns the model's conditional; p_EU generally does not. The post hoc interpretation is proved and illustrated beyond pair neurons up to eight inputs, but has no preregistered test and only one exploratory real-data pilot. Closed forms were within a factor of two of 112 measured gaps, and negative density began near input correlation 1/k. In a preregistered synthetic study up to 32 inputs, 5 of 15 hypotheses were supported, 2 inconclusive, and 8 unsupported, including all three about transfer beyond equicorrelated Gaussians. Where p_EU is defined, truncation usually outweighed the gap for Beta beliefs in pair neurons; triple neurons with flat or data beliefs were exceptions.

### Source excerpt

arXiv:2611.12339v1 Announce Type: new Abstract: When a neuron's input is lost, or known through a belief $q$, what should it output? For a neuron storing a joint polynomial density $N$ with input density $D$, two formulas compete. $p_\mathrm{CD}=E_q[N]/E_q[D]$ costs one matrix-vector product; Hierarchical Correlation Reconstruction introduces it as a constant-denominator approximation to $p_\mathrm{EU}=E_q[N/D]$. For a density model both are exact answers to different questions: $p_\mathrm{CD}$ is Bayesian updating with the belief as virtual evidence; $p_\mathrm{EU}$ installs the belief as a new marginal (Jeffrey's rule). With a missing input $p_\mathrm{CD}$ returns the model's conditional; $p_\mathrm{EU}$ generally does not. This post hoc reading is proved, and illustrated outside the pair family up to $k=8$ inputs; it has no pre-registered test, only one exploratory real-data pilot. Post hoc, closed forms fall within a factor 2 of all 112 measured gaps, and negative density begins near input correlation $1/k$. In a pre-registered synthetic study (up to 32 inputs), 5 of 15 hypotheses are supported, 2 inconclusive and 8 not supported, including all three on transfer beyond equicorrelated Gaussians. Post hoc, where $p_\mathrm{EU}$ is defined, truncation usually outweighs the gap for Beta beliefs in pair neurons; triple neurons under flat and data beliefs are exceptions.

## An Improved Algorithm for Quantified Boolean Formulas

DevFeed: [An Improved Algorithm for Quantified Boolean Formulas](<https://devfeed.tech/articles/an-improved-algorithm-for-quantified-boolean-formulas-125984.md>)

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

Author: Zhiyang Chen, Hailong Yao

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

Content type: article

Language: en

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

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [boolean](<https://devfeed.tech/tags/boolean.md>), [boolean-satisfiability](<https://devfeed.tech/tags/boolean-satisfiability.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [constraint](<https://devfeed.tech/tags/constraint.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [data-structures-and-algorithms](<https://devfeed.tech/tags/data-structures-and-algorithms.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [parameter](<https://devfeed.tech/tags/parameter.md>), [pspace](<https://devfeed.tech/tags/pspace.md>), [search](<https://devfeed.tech/tags/search.md>), [space](<https://devfeed.tech/tags/space.md>), [time](<https://devfeed.tech/tags/time.md>), [variables](<https://devfeed.tech/tags/variables.md>), [vertex](<https://devfeed.tech/tags/vertex.md>), [vertex-cover](<https://devfeed.tech/tags/vertex-cover.md>)

### AI overview

The paper presents a memoized-search algorithm for quantified Boolean formulas (QBF), solving instances with n variables and m clauses in 1.685^m-poly(n) time and space. The authors say this improves on Williams's 1.709^m-poly(n) bound, the first improvement in over 20 years. Their method extends the use of minimum vertex covers of conflict graphs from SAT to QBF, and they show QBF is slicewise polynomial-time solvable with this parameter.

### Source excerpt

arXiv:2611.10633v1 Announce Type: cross Abstract: Quantified Boolean formula (QBF), the quantified version of Boolean satisfiability (SAT), is a fundamental problem in constraint solving. Due to the $\mathsf{PSPACE}$-complete nature of QBF, designing theoretically efficient QBF algorithms is much harder and receives less attention in academia. In this work, we present a new algorithm based on memoized search, which solves QBF with $n$ variables and $m$ clauses in $1.685^m\cdot\text{poly}(n)$ time and space. This is the first improvement over the $1.709^m\cdot\text{poly}(n)$ bound by Williams in over 20 years. Our technique is based on the minimum vertex cover of the conflict graphs, which was proposed to study the parameterized complexity of SAT. We extend this idea to QBF and further show that QBF is slicewise polynomial-time solvable using this parameter.

## Minimal Filling Architectures for Polynomial Neural Networks

DevFeed: [Minimal Filling Architectures for Polynomial Neural Networks](<https://devfeed.tech/articles/minimal-filling-architectures-for-polynomial-neural-networks-120420.md>)

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

Author: Kevin Dao, Jose Israel Rodriguez

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

Content type: article

Language: en

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

Topics: [Deep neural networks](<https://devfeed.tech/topics/deep-neural-networks.md>), [Neural Network](<https://devfeed.tech/topics/neural-network.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [architectures](<https://devfeed.tech/tags/architectures.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [field](<https://devfeed.tech/tags/field.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [math-ag](<https://devfeed.tech/tags/math-ag.md>), [neural-networks](<https://devfeed.tech/tags/neural-networks.md>), [search](<https://devfeed.tech/tags/search.md>)

### AI overview

Minimal filling architectures are the smallest hidden-layer width configurations for which a polynomial neural network's neurovariety fills its ambient function space. The paper refutes the conjecture that all such architectures have unimodal widths: it finds counterexamples with a frontier search and certifies its main example using finite-field Jacobian computations and recursive dimension bounds. It also proves unimodality for every minimal filling architecture of depth at most three, while a nonunimodal example at depth four shows that this bound is sharp.

### Source excerpt

arXiv:2605.09609v3 Announce Type: replace Abstract: Minimal filling architectures describe the smallest hidden-layer widths for which the neurovariety of a polynomial neural network fills its ambient function space. It was conjectured that every such architecture has unimodal hidden widths. We construct counterexamples to this conjecture using a frontier search and certify the main example through finite-field Jacobian computations and recursive dimension bounds. In the opposite direction, we prove that every minimal filling architecture of depth at most three is unimodal. A nonunimodal minimal filling architecture of depth four shows that the depth bound is sharp.

## Exact $\\ell\_p$-CVP via Euclidean SVP in Polynomial Space

DevFeed: [Exact $\\ell\_p$-CVP via Euclidean SVP in Polynomial Space](<https://devfeed.tech/articles/exact-ell-p-cvp-via-euclidean-svp-in-polynomial-space-119910.md>)

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

Author: Jiseung Kim, Minkyu Kim, Hyung Tae Lee

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

Content type: article

Language: en

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

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [lattice](<https://devfeed.tech/tags/lattice.md>), [reduce](<https://devfeed.tech/tags/reduce.md>), [reduction](<https://devfeed.tech/tags/reduction.md>), [search](<https://devfeed.tech/tags/search.md>), [space](<https://devfeed.tech/tags/space.md>)

### AI overview

The paper presents a randomized, rank-preserving reduction from exact ℓp closest vector search to exact Euclidean shortest vector search for integer p >= 2. On rational full-rank lattices in dimension N, it uses (Cp)^N poly(p, ℓ) oracle calls, polynomial working space outside the oracle, and rank-N queries of polynomial bit complexity. It searches cosets of 2L, tracking the objective's excess over the optimum; midpoint inequalities identify short corrections that shrink this excess, and a sparsification-based sampler finds them using at most one SVP call per sample. For p = 2, the reduction gives a 2^{O(N)} poly(ℓ) time overhead and, with cited SVP algorithms, polynomial-space CVP runtimes of N^{N/(2e)+o(N)} or N^{N/(4e)+o(N)}. For fixed p >= 3, it gives either randomized 2^{O(N)} time and space or randomized N^{N/(4e)+o(N)} time with polynomial space, up to polynomial factors in ℓ. The extension for p >= 3 uses a diagonal weighted norm based on the current point.

### Source excerpt

arXiv:2611.07313v1 Announce Type: cross Abstract: We give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$. For rational inputs of bit length $\ell$ on full-rank lattices $L\subset\mathbb R^N$, the reduction uses $(Cp)^N\poly(p,\ell)$ oracle calls and additional bit operations, where $C$ is an absolute constant. It uses $\poly(p,\ell)$ working space outside the oracle, and all oracle queries have rank $N$ and $\poly(p,\ell)$ bit complexity. For $p=2$, the reduction transfers polynomial-space exact SVP algorithms to exact CVP with $2^{O(N)}\poly(\ell)$ time overhead. Instantiating it with the SVP algorithms of Kannan and of Feng, Gao and Liu yields randomized polynomial-space CVP algorithms running in time $N^{N/(2e)+o(N)}$ and $N^{N/(4e)+o(N)}$, respectively. For every fixed integer $p\ge3$, the same reduction yields exact $\ell_p$-CVP algorithms for arbitrary rational targets either in randomized time and space $2^{O(N)}$, or in randomized time $N^{N/(4e)+o(N)}$ and polynomial space. These algorithmic bounds are up to polynomial factors in $\ell$. The reduction performs local search sequentially over the cosets of \(2L\), where \(L\) is the input lattice, while tracking the excess of the current objective value over the optimum. Within a coset containing a closest vector, midpoint inequalities bound the unknown correction in terms of this excess, which in turn allows us to construct many short corrections that reduce the excess bound by a factor of four. A counting argument shows that these improving corrections form a sufficiently large fraction of the lattice points in a known search region, and a sparsification-based sampler assigns sufficiently large probability to every nonzero vector in that region, using at most one SVP call per sample. For \(p\ge3\), the same framework is extended using a diagonal weighted norm computed from the current point.

## Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

DevFeed: [Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation](<https://devfeed.tech/articles/optimistic-hedge-in-general-sum-games-fundamental-limits-and-regret-bounds-via-temporal-approximation-120550.md>)

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

Author: Yuval Dagan, Nadav Eisen, Liad Erez, Tomer Koren

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

Content type: article

Language: en

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

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [actions](<https://devfeed.tech/tags/actions.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [cs-gt](<https://devfeed.tech/tags/cs-gt.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [framework](<https://devfeed.tech/tags/framework.md>), [game](<https://devfeed.tech/tags/game.md>), [games](<https://devfeed.tech/tags/games.md>), [hedge](<https://devfeed.tech/tags/hedge.md>), [horizon](<https://devfeed.tech/tags/horizon.md>), [learning](<https://devfeed.tech/tags/learning.md>), [limits](<https://devfeed.tech/tags/limits.md>), [log](<https://devfeed.tech/tags/log.md>), [number](<https://devfeed.tech/tags/number.md>), [open](<https://devfeed.tech/tags/open.md>), [temporal](<https://devfeed.tech/tags/temporal.md>), [variance](<https://devfeed.tech/tags/variance.md>)

### AI overview

Optimistic Hedge's horizon-independent regret guarantee depends sharply on the number of players. In two-player finite general-sum games, a suitable learning rate yields regret O(n log n), where n is the number of actions per player. For three or more players, the paper constructs games with regret exponential in the game size: for m >= 3, some player's regret reaches 2^{Ω(mn)} for sufficiently large horizons, and for learning rates above 2^{-Ω(mn)} it can grow linearly with the horizon. The upper-bound analysis uses temporal approximation: it approximates losses on localized time windows with functions whose total variation is a small fraction of cumulative variance. The same framework also simplifies a recent O(√m log n log T) regret proof.

### Source excerpt

arXiv:2611.07078v1 Announce Type: new Abstract: Optimistic Hedge, a multiplicative weight update with one step of extrapolation, is one of the most natural regret-minimizing dynamics for games, and characterizing its regret has been a longstanding open question. Daskalakis, Fishelson and Golowich proved that if all $m$ players in a finite general-sum game follow Optimistic Hedge with a fixed learning rate, each player's regret is polylogarithmic in the horizon $T$. Subsequently, Ha showed that an appropriate choice of learning rate makes each player's regret bounded independently of $T$. This bound, however, is non-constructive and its dependence on the number of actions $n$ is not explicit, leaving open whether Optimistic Hedge can achieve a constant regret bound which is polynomial in the size of the game. We show that the answer hinges on the number of players. In two-player games, there is a learning rate for which Optimistic Hedge guarantees $O(n\log n)$ regret independent of the horizon. In three-player games, however, no such bound is possible: for any learning rate up to an absolute constant and for sufficiently large horizon $T$, there is a game with $n$ actions per player in which some player's regret is $2^{\Omega(n)}$, and more generally, for every $m\ge3$ we construct $m$-player games in which some player's regret is $2^{\Omega(mn)}$; for learning rates above $2^{-\Omega(mn)}$, that player's regret even grows linearly in $T$. Our upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge. Starting from the variance-based RVU bound of Daskalakis et al., we approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance. In $m$-player games, the same framework gives a significantly simplified proof of the recent $O(\sqrt{m}\log n\log T)$ regret bound due to Ha.

[Next page](<https://devfeed.tech/topics/polynomials.md?cursor=WyIyMDI2LTExLTA2VDA1OjAwOjAwKzAwOjAwIiwgImM3N2ZmYTE4LTViZmQtNDliNS1hNzNjLTM4ZjAzMDBkMzI4ZSJd>)