Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | https://doi.org/10.1007/s00453-016-0273-1 | Algorithmica |
Keywords | Field | DocType |
Hidden polynomial power,Black-box interpolation,Nullstellensatz,Rational function,Deterministic algorithm,Randomised algorithm,Quantum algorithm,11T06,11Y16,68Q12,68Q25 | Discrete mathematics,Finite field,Combinatorics,Polynomial interpolation,Mathematical analysis,Interpolation,Character sum,Oracle,Monic polynomial,Analytic number theory,Rational function,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1502.06631 | 2 | 0178-4617 |
Citations | PageRank | References |
1 | 0.41 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Ivanyos | 1 | 257 | 28.02 |
| Marek Karpinski | 2 | 2895 | 302.60 |
| Miklos Santha | 3 | 728 | 92.42 |
| Nitin Saxena | 4 | 280 | 26.72 |
| Igor E. Shparlinski | 5 | 1339 | 164.66 |