A local decision test for sparse polynomials
An ℓ-sparse (multivariate) polynomial is a polynomial containing at most ℓ-monomials in its explicit description. We assume that a polynomial is implicitly represented as a black-box: on an input query from the domain, the black-box replies with the evaluation of the polynomial at that input. We pro...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2017
|
| Online Access: | http://hdl.handle.net/1721.1/108433 https://orcid.org/0000-0002-4353-7639 |
| _version_ | 1826206159963422720 |
|---|---|
| author | Grigorescu, Elena Jung, Kyomin Rubinfeld, Ronitt |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Grigorescu, Elena Jung, Kyomin Rubinfeld, Ronitt |
| author_sort | Grigorescu, Elena |
| collection | MIT |
| description | An ℓ-sparse (multivariate) polynomial is a polynomial containing at most ℓ-monomials in its explicit description. We assume that a polynomial is implicitly represented as a black-box: on an input query from the domain, the black-box replies with the evaluation of the polynomial at that input. We provide an efficient, randomized algorithm, that can decide whether a polynomial [MathML] given as a black-box is ℓ-sparse or not, provided that q is large compared to the polynomial's total degree. The algorithm makes only queries, which is independent of the domain size. The running time of our algorithm (in the bit-complexity model) is , where d is an upper bound on the degree of each variable. Existing interpolation algorithms for polynomials in the same model run in time . We provide a similar test for polynomials with integer coefficients. |
| first_indexed | 2024-09-23T13:25:02Z |
| format | Article |
| id | mit-1721.1/108433 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:25:02Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/1084332022-09-28T14:03:59Z A local decision test for sparse polynomials Grigorescu, Elena Jung, Kyomin Rubinfeld, Ronitt Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science rubinfeld, ronitt Grigorescu, Elena Rubinfeld, Ronitt An ℓ-sparse (multivariate) polynomial is a polynomial containing at most ℓ-monomials in its explicit description. We assume that a polynomial is implicitly represented as a black-box: on an input query from the domain, the black-box replies with the evaluation of the polynomial at that input. We provide an efficient, randomized algorithm, that can decide whether a polynomial [MathML] given as a black-box is ℓ-sparse or not, provided that q is large compared to the polynomial's total degree. The algorithm makes only queries, which is independent of the domain size. The running time of our algorithm (in the bit-complexity model) is , where d is an upper bound on the degree of each variable. Existing interpolation algorithms for polynomials in the same model run in time . We provide a similar test for polynomials with integer coefficients. 2017-04-26T20:25:21Z 2017-04-26T20:25:21Z 2010-07 2010-07 Article http://purl.org/eprint/type/JournalArticle 0020-0190 http://hdl.handle.net/1721.1/108433 Grigorescu, Elena; Jung, Kyomin and Rubinfeld, Ronitt. “A Local Decision Test for Sparse Polynomials.” Information Processing Letters 110, no. 20 (September 2010): 898–901.© 2010 Elsevier B.V. https://orcid.org/0000-0002-4353-7639 en_US http://dx.doi.org/10.1016/j.ipl.2010.07.012 Information Processing Letters Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier Prof. Rubinfeld |
| spellingShingle | Grigorescu, Elena Jung, Kyomin Rubinfeld, Ronitt A local decision test for sparse polynomials |
| title | A local decision test for sparse polynomials |
| title_full | A local decision test for sparse polynomials |
| title_fullStr | A local decision test for sparse polynomials |
| title_full_unstemmed | A local decision test for sparse polynomials |
| title_short | A local decision test for sparse polynomials |
| title_sort | local decision test for sparse polynomials |
| url | http://hdl.handle.net/1721.1/108433 https://orcid.org/0000-0002-4353-7639 |
| work_keys_str_mv | AT grigorescuelena alocaldecisiontestforsparsepolynomials AT jungkyomin alocaldecisiontestforsparsepolynomials AT rubinfeldronitt alocaldecisiontestforsparsepolynomials AT grigorescuelena localdecisiontestforsparsepolynomials AT jungkyomin localdecisiontestforsparsepolynomials AT rubinfeldronitt localdecisiontestforsparsepolynomials |