A note on the complexity of a phaseless polynomial interpolation

被引：0
|
作者：
Przybylek, Michal R. [1 ]
Siedlecki, Pawel [2 ]
机构：
[1] Univ Warsaw, Dept Math Informat & Mech, Inst Informat, Warsaw, Poland
[2] Univ Warsaw, Dept Math Informat & Mech, Inst Appl Math & Mech, Warsaw, Poland
来源：
JOURNAL OF COMPLEXITY | 2020年 / 58卷
关键词：
Information-based complexity; Absolute value information; Group action; Polynomial interpolation;
D O I：
10.1016/j.jco.2019.101456
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper we revisit the classical problem of polynomial interpolation, with a slight twist; namely, polynomial evaluations are available up to a group action of the unit circle on the complex plane. It turns out that this new setting allows for a phaseless recovery of a polynomial in a polynomial time. (C) 2019 Elsevier Inc. All rights reserved.
引用
收藏
页数：13
相关论文
共 50 条
  • [1] A note on polynomial interpolation
    Cecilio, WAG
    Cordeiro, CJ
    Milléo, IS
    Santiago, CD
    Zanardini, RAD
    Yuan, JY
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2002, 79 (04) : 465 - 471
  • [2] Note on Equidistant Polynomial Interpolation
    Shang, Gao
    qiang, Qian
    PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON EDUCATION, MANAGEMENT, COMPUTER AND SOCIETY, 2016, 37 : 2059 - 2062
  • [3] A note on cubic polynomial interpolation
    Hu, Minghan
    Shi, Xiquan
    Wang, Tianjun
    Liu, Fengshan
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2008, 56 (05) : 1358 - 1363
  • [4] A Note on Sparse Polynomial Interpolation in Dickson Polynomial Basis
    Imamoglu, Erdal
    Kaltofen, Erich L.
    ACM COMMUNICATIONS IN COMPUTER ALGEBRA, 2020, 54 (04): : 125 - 128
  • [5] Note on polynomial interpolation to analytic functions
    Walsh, JL
    PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1933, 19 : 959 - 963
  • [6] A Reduced-Complexity Algorithm For Polynomial Interpolation
    Zhu, Yuan
    Tang, Siyun
    2013 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT), 2013, : 316 - +
  • [7] A note on the Hermite interpolation polynomial for rational functions
    Ivan, Mircea
    APPLIED NUMERICAL MATHEMATICS, 2007, 57 (02) : 230 - 233
  • [8] A NOTE ON POLYNOMIAL INTERPOLATION AT THE TSCHEBYSCHEV EXTREMA NODES
    BRUTMAN, L
    JOURNAL OF APPROXIMATION THEORY, 1984, 42 (03) : 283 - 292
  • [9] Automatic Inference of Loop Complexity Through Polynomial Interpolation
    Demontie, Francisco
    Cezar, Junio
    Bigonha, Mariza
    Campos, Frederico
    Quintao Pereira, Fernando Magno
    PROGRAMMING LANGUAGES, SBLP 2015, 2015, 9325 : 1 - 15
  • [10] THE COMPLEXITY OF SPARSE POLYNOMIAL INTERPOLATION OVER FINITE-FIELDS
    WERTHER, K
    APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 1994, 5 (02) : 91 - 103
12345