English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the problem of approximating the largest root of a real-rootedpolynomial of degree $n$ using its top $k$ coefficients and give nearlymatching upper and lower bounds. We present algorithms with running timepolynomial in $k$ that use the top $k$ coefficients to approximate the maximumroot within a factor of $n^{1/k}$ and $1+O(\tfrac{\log n}{k})^2$ when $k\leq\log n$ and $k>\log n$ respectively. We also prove correspondinginformation-theoretic lower bounds of $n^{\Omega(1/k)}$ and$1+\Omega\left(\frac{\log \frac{2n}{k}}{k}\right)^2$, and show strong lowerbounds for noisy version of the problem in which one is given access toapproximate coefficients.  This problem has applications in the context of the method of interlacingfamilies of polynomials, which was used for proving the existence of Ramanujangraphs of all degrees, the solution of the Kadison-Singer problem, and boundingthe integrality gap of the asymmetric traveling salesman problem. All of theseinvolve computing the maximum root of certain real-rooted polynomials for whichthe top few coefficients are accessible in subexponential time. Our resultsyield an algorithm with the running time of $2^{\tilde O(\sqrt[3]n)}$ for allof them.

Approximating the Largest Root and Applications to Interlacing Families