Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author C Ramya:

TR17-086 | 9th May 2017
C Ramya, Raghavendra Rao B V

Linear Projections of the Vandermonde Polynomial

Revisions: 1

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 ... more >>>

TR15-201 | 10th December 2015
C Ramya, Raghavendra Rao B V

Limitations of sum of products of Read-Once Polynomials

Revisions: 1

We study limitations of polynomials computed by depth two circuits built over read-once polynomials (ROPs) and depth three syntactically multi-linear formulas.
We prove an exponential lower bound for the size of the $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over syntactically multi-linear $\Sigma\Pi\Sigma^{[N^{8/15}]}$ arithmetic circuits computing a product of variable ... more >>>

ISSN 1433-8092 | Imprint