A deterministic PTAS for the algebraic rank of bounded degree polynomials

Vishwas Bhargava, Markus Bläser, Gorav Jindal, Anurag Pandey

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

107 Lataukset (Pure)


We present a deterministic polynomial time approximation scheme (PTAS) for computing the algebraic rank of a set of bounded degree polynomials. The notion of algebraic rank naturally generalizes the notion of rank in linear algebra, i.e., instead of considering only the linear dependencies, we also consider higher degree algebraic dependencies among the input polynomials. More specifically, we give an algorithm that takes as input a set f:= {f1, . . ., fn} ⊂ F[x1, . . ., xm] of polynomials with degrees bounded by d, and a rational number > 0 and runs in time O((nmd )O(d 2) • M(n)), where M(n) is the time required to compute the rank of an n × n matrix (with field entries), and finally outputs a number r, such that r is at least (1 − ) times the algebraic rank of f. Our key contribution is a new technique which allows us to achieve the higher degree generalization of the results by Bläser, Jindal, Pandey (CCC’17) who gave a deterministic PTAS for computing the rank of a matrix with homogeneous linear entries. It is known that a deterministic algorithm for exactly computing the rank in the linear case is already equivalent to the celebrated Polynomial Identity Testing (PIT) problem which itself would imply circuit complexity lower bounds (Kabanets, Impagliazzo, STOC’03). Such a higher degree generalization is already known to a much stronger extent in the noncommutative world, where the more general case in which the entries of the matrix are given by poly-sized formulas reduces to the case where the entries are given by linear polynomials using Higman’s trick, and in the latter case, one can also compute the exact rank in polynomial time (Garg, Gurvits, Oliviera, Wigderson, FOCS’16, Ivanyos, Qiao, Subrahmanyam, ITCS’17). Higman’s trick only preserves the co-rank, hence it cannot be used to reduce the problem of rank approximation to the case when the matrix entries are linear polynomials. Thus our work can also be seen as a step towards bridging the knowledge gap between the non-commutative world and the commutative world.

OtsikkoProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
KustantajaSociety for Industrial and Applied Mathematics
ISBN (elektroninen)9781611975482
TilaJulkaistu - 1 tammik. 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM-SIAM Symposium on Discrete Algorithms - San Diego, Yhdysvallat
Kesto: 6 tammik. 20199 tammik. 2019
Konferenssinumero: 30


ConferenceACM-SIAM Symposium on Discrete Algorithms
KaupunkiSan Diego


Sukella tutkimusaiheisiin 'A deterministic PTAS for the algebraic rank of bounded degree polynomials'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä