Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-086 | 30th May 2017 06:28

Linear Projections of the Vandermonde Polynomial

RSS-Feed




Revision #1
Authors: C Ramya, Raghavendra Rao B V
Accepted on: 30th May 2017 06:28
Downloads: 665
Keywords: 


Abstract:

An n-variate Vandermonde polynomial is the determinant of the n × n matrix where the ith column is the vector (1, x_i , x_i^2 , . . . , x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation as well as in the theory of error correcting codes. In this work we study structural and computational aspects of linear projections of Vandermonde polynomials. Firstly, we consider the problem of testing if a given polynomial is linearly equivalent to the Vandermonde polynomial. We obtain a deterministic polynomial time algorithm to test if f is linearly equivalent to the Vandermonde polynomial when f is given as product of linear factors. In the case when f is given as a black-box our algorithm runs in randomized polynomial time. Exploring the structure of projections of Vandermonde polynomials further, we describe the group of symmetries of a Vandermonde polynomial and obtain a basis for the associated Lie Algebra. Finally, we study arithmetic circuits built over projections of Vandermonde polynomials. We show universality property for some of the models and obtain a lower bounds against sum of
projections of Vandermonde determinant.



Changes to previous version:

The claim that associated Lie Algebra is simple (Corollary 8) is incorrect and has been removed. We thank Joseph M. Landsberg for pointing this out.


Paper:

TR17-086 | 9th May 2017 07:13

Linear Projections of the Vandermonde Polynomial





TR17-086
Authors: C Ramya, Raghavendra Rao B V
Publication: 9th May 2017 15:42
Downloads: 1081
Keywords: 


Abstract:

An n-variate Vandermonde polynomial is the determinant of the n × n matrix where the ith column is the vector (1, x_i , x_i^2 , . . . , x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation as well as in the theory of error correcting codes. In this work we study structural and computational aspects of linear projections of Vandermonde polynomials. Firstly, we consider the problem of testing if a given polynomial is linearly equivalent to the Vandermonde polynomial. We obtain a deterministic polynomial time algorithm to test if f is linearly equivalent to the Vandermonde polynomial when f is given as product of linear factors. In the case when f is given as a black-box our algorithm runs in randomized polynomial time. Exploring the structure of projections of Vandermonde polynomials further, we describe the group of symmetries of a Vandermonde polynomial and show that the associated Lie algebra is simple. Finally, we study arithmetic circuits built over projections of Vandermonde polynomials. We show universality property for some of the models and obtain a lower bounds against sum of
projections of Vandermonde determinant.



ISSN 1433-8092 | Imprint