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/

Zendy Plus

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

Zendy Tools

Zendy Open

We consider the problem of recovering (that is, interpolating) and identity testing of a “hidden” monic polynomial , given an oracle access to  for , where  is finite field of  elements (extension fields access is not permitted). The naive interpolation algorithm needs  queries and thus requires . We design algorithms that are asymptotically better in certain cases; requiring only  queries to the oracle. In the randomized (and quantum) setting, we give a substantially better interpolation algorithm, that requires only  queries. Such results have been known before only for the special case of a linear , called the  problem. We use techniques from algebra, such as effective versions of Hilbert’s Nullstellensatz, and analytic number theory, such as results on the distribution of rational functions in subgroups and character sum estimates.

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields