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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We extend the "method of multiplicities" to get the following results, ofinterest in combinatorics and randomness extraction. (A) We show that everyKakeya set (a set of points that contains a line in every direction) in$\F_q^n$ must be of size at least $q^n/2^n$. This bound is tight to within a $2+ o(1)$ factor for every $n$ as $q \to \infty$, compared to previous boundsthat were off by exponential factors in $n$. (B) We give improved randomnessextractors and "randomness mergers". Mergers are seeded functions that take asinput $\Lambda$ (possibly correlated) random variables in $\{0,1\}^N$ and ashort random seed and output a single random variable in $\{0,1\}^N$ that isstatistically close to having entropy $(1-\delta) \cdot N$ when one of the$\Lambda$ input variables is distributed uniformly. The seed we require is only$(1/\delta)\cdot \log \Lambda$-bits long, which significantly improves uponprevious construction of mergers. (C) Using our new mergers, we show how toconstruct randomness extractors that use logarithmic length seeds whileextracting $1 - o(1)$ fraction of the min-entropy of the source.  The "method of multiplicities", as used in prior work, analyzed subsets ofvector spaces over finite fields by constructing somewhat low degreeinterpolating polynomials that vanish on every point in the subset {\em withhigh multiplicity}. The typical use of this method involved showing that theinterpolating polynomial also vanished on some points outside the subset, andthen used simple bounds on the number of zeroes to complete the analysis. Ouraugmentation to this technique is that we prove, under appropriate conditions,that the interpolating polynomial vanishes {\em with high multiplicity} outsidethe set. This novelty leads to significantly tighter analyses.

Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers