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

In Heintz-Schnorr (1982), the authors introduced the notion of correct testsequence and since then it has been widely used to design probabilisticalgorithms for Polynomial Equality Test. The aim of this manuscript is to studythe foundations and generalizations of this notion. We show that correct testsequences are almost omnipresent and appear in many different forms in themathematical literature: As identity sequences for Function Identity Test, asnorming sets in the field of Banach algebras or as samples in the context ofReproducing Kernel Hilbert Spaces. As main outcome, we generalize the mainstatement of Heintz-Schnorr (1982) proving that short correct test sequencesfor constructible sets of lists of polynomials do exist and are denselydistributed in any constructible set of accurate dimension and degree. The maintool used to prove this result is the theory of degree of constructible sets,which we introduce and develop in this manuscript, generalizing the results ofHeintz (1983) and proving two Bezout's Inequalities for two different notionsof degree. We present a ${\bf BPP}_K$ algorithm to exhibit the power of correcttest sequences, this algorithm decides whether a list of polynomials is asecant sequence by just evaluating the input list at some well-suited points.We show the differences between correct test sequences andDemillo-Lipton-Schwartz-Zippel probabilistic tests and we reformulate, proveand generalize two well-known results of the Polynomial Method: We prove Dvir'sexponential lower bounds for Kakeya sets from lower bounds for the length ofcorrect test sequences and generalize Alon's Combinatorial Nullstellensatz.

A promenade through Correct Test Sequences I: Degree of constructible sets, B\'ezout's Inequality and density