Adversarial Wronskians: A proof of the Kung--Traub conjecture
Auteurs : Matthew J. Colbrook
Résumé scientifique
We prove the Kung--Traub conjecture: a deterministic stationary root-finding method without memory, using at most $n$ real scalar function or derivative evaluations per iteration, cannot have local order greater than $2^{n-1}$ on every real analytic function with a simple zero. For $n\geq2$, the bound is attained by the methods of Kung and Traub. The local estimate is required at every sufficiently close starting point, with constants that may depend on the function. Evaluation points and derivative orders may be chosen adaptively, and the rules for choosing them and processing the data are unrestricted. The proof uses a localisation property of polynomial Wronskians to obtain a lower bound at each fixed scale. A diagonal construction then gives one entire function, with derivative bounded above and below on the real line, for which every larger order fails. We also obtain a sharper bound when evaluations are made in prescribed groups, and prove the corresponding result for complex scalar evaluations. The results of this paper are also formally verified in Lean.
Les articles autour de lui, par date et par proximité
Plus haut, c’est plus proche de cet article ; à gauche, c’est plus ancien. Les traits relient les articles proches entre eux : les groupes de traits sont des sous-thèmes. Sélectionnez un point pour voir pourquoi il est là. Retour au résumé de cet article
Les articles autour de celui-ci
Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.
Les articles les plus proches
-
An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphsMatthew Kwan, Lisa Sauermann · 2019 · Combinatorics · cité 7 fois · Résumé IA disponible
« An algebraic inverse theorem » étudie la concentration de polynômes quadratiques de variables de Bernoulli, sans traiter la convergence des méthodes de recherche de zéros.
Résumé scientifique
Consider a quadratic polynomial $f\left(\xi_{1},\dots,\xi_{n}\right)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/\sqrt{n}$, but still poorly understood is the "inverse" question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this paper we prove some results of an algebraic flavour, showing that if $f$ has point probabilities much larger…
-
Certified homotopy tracking using the Krawczyk methodTimothy Duff, Kisun Lee · 2024 · Numerical Analysis · cité 14 fois · Résumé IA disponible
« Certified homotopy tracking » certifie des trajectoires de solutions de systèmes polynomiaux, tandis que l’article étudie l’ordre des méthodes de recherche de zéros.
Résumé scientifique
We revisit the problem of certifying the correctness of approximate solution paths computed by numerical homotopy continuation methods. We propose a conceptually simple approach based on a parametric variant of the Krawczyk method from interval arithmetic. Unlike most previous methods for certified path-tracking, our approach is applicable in the general setting of parameter homotopies commonly used to solve polynomial systems of equations. We also describe a novel preconditioning strategy and give theoretical correctness and termination results. Experiments using a preliminary implementation of the method indicate that our approach is competitive with specialized methods appearing previousl…
-
Weak Poincaré Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick ModelEwan Davies, Holden Lee, Juspreet Singh Sandhu et al. · 2026 · Probability · cité 3 fois · Résumé IA disponible
« Weak Poincaré Inequalities » établit une inégalité fonctionnelle pour le modèle de Sherrington-Kirkpatrick, sans étudier les méthodes de recherche de zéros.
Résumé scientifique
We develop a new method for proving a weak functional inequality by first proving it for a sufficiently regular sequence of distributions approximating the stochastic localization (SL) process, and then transferring it to the desired distribution via regularity of the SL process and conductance arguments. We use this strategy to prove a weak Poincaré inequality (WPI) holds for the Gibbs measure of the Sherrington-Kirkpatrick model when $β< \frac{1}{2}$. A prior result of the authors [arXiv:2605.03718, 2026] proves the ASL process for the Sherrington-Kirkpatrick model satisfies the required regularity conditions. A consequence of the WPI is that a much simpler algorithm -- Glauber dynamics wi…
-
Oblivious Sketching of High-Degree Polynomial KernelsMichael Kapralov, Rasmus Pagh, Ameya Velingker et al. · 2019 · Data Structures and Algorithms · Résumé IA disponible
« Oblivious Sketching » accélère des calculs de noyaux polynomiaux en apprentissage automatique, plutôt que la convergence des méthodes de recherche de zéros.
Résumé scientifique
Kernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimensional spaces. A major disadvantage of kernel methods is their poor scalability: primitives such as kernel PCA or kernel ridge regression generally take prohibitively large quadratic space and (at least) quadratic time, as kernel matrices are usually dense. Some methods for speeding up kernel linear algebra are known, but they all invariably take time exponential in either the dimension of the input point set (e.g., fast multipole methods suffer from the curse of dimensionality) or in the degree of the kernel functi…
-
Potential Hessian Ascent: The Sherrington-Kirkpatrick ModelDavid Jekel, Juspreet Singh Sandhu, Jonathan Shi · 2024 · Probability · preprint, non relu par les pairs · cité 8 fois · Résumé IA disponible
« Potential Hessian Ascent » propose un algorithme spectral pour optimiser un objectif quadratique sur l’hypercube, non pour trouver des zéros de fonctions analytiques.
Résumé scientifique
We provide the first iterative spectral algorithm to find near-optima of a random quadratic objective over the discrete hypercube. The algorithm is a randomized Hessian ascent in the solid cube, where we modify the objective by subtracting a specific instance-independent potential function [Chen et al., Communications on Pure and Applied Mathematics, 76(7), 2023]. This extends Subag's algorithmic program of Hessian ascent from the sphere [Subag, Communications on Pure and Applied Mathematics, 74(5), 2021] to the more complex geometry of the cube. Utilizing tools from free probability theory, we construct an approximate projector into the top-eigenspaces of the Hessian with well-behaved diago…
-
The Hamel-Nadirashvili conjecture for the Fisher-KPP equationHongjun Guo, Kelei Wang, Maolin Zhou · 2026 · Analysis of PDEs · Résumé IA disponible
« The Hamel-Nadirashvili conjecture » classe des solutions entières d’équations Fisher-KPP, un problème distinct de la convergence des méthodes de recherche de zéros.
En bref
L’article démontre la conjecture de Hamel–Nadirashvili pour Fisher–KPP à réaction concave : toute solution entière entre 0 et 1 s’approche par des mélanges finis de fronts.
-
Matrix anti-concentration inequalities with applicationsZipei Nie · 2021 · Probability · cité 22 fois · Résumé IA disponible
« Matrix anti-concentration inequalities » borne la plus petite valeur singulière de matrices aléatoires, sans traiter l’ordre de convergence des méthodes de recherche de zéros.
Résumé scientifique
We provide a polynomial lower bound on the minimum singular value of an $m\times m$ random matrix $M$ with jointly Gaussian entries, under a polynomial bound on the matrix norm and a global small-ball probability bound $$\inf_{x,y\in S^{m-1}}\mathbb{P}\left(\left|x^* M y\right|>m^{-O(1)}\right)\ge \frac{1}{2}.$$ With the additional assumption that $M$ is self-adjoint, the global small-ball probability bound can be replaced with a weaker version. We establish two matrix anti-concentration inequalities, which lower bound the minimum singular values of the sum of independent positive semidefinite self-adjoint matrices and the linear combination of independent random matrices with independent Ga…
-
Fast Multivariate Multipoint Evaluation Over All Finite FieldsVishwas Bhargava, Sumanta Ghosh, Zeyu Guo et al. · 2022 · Data Structures and Algorithms · cité 21 fois · Résumé IA disponible
« Fast Multivariate Multipoint Evaluation » accélère l’évaluation de polynômes multivariés sur des corps finis, contrairement à l’étude de convergence locale des méthodes de recherche de zéros.
Résumé scientifique
Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of degree less than $d$ in each variable at $N$ points in time \[ (d^m+N)^{1+o(1)}\cdot\poly(m,d,\log|\mathbb{F}|) \] for all $m\in\N$ and all sufficiently large $d\in\mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables $m$ is at most $d^{o(1)}$ and…
Aller plus loin
Comment ces articles sont-ils trouvés ?
Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.
Mis à jour le 2 novembre 2026.