Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Raghavendra Rao B V:

TR17-087 | 9th May 2017
Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar

On Weak-Space Complexity over Complex Numbers

Defining a feasible notion of space over the Blum-Shub-Smale (BSS) model of algebraic computation is a long standing open problem. In an attempt to define a right notion of space complexity for the BSS model, Naurois [CiE, 2007] introduced the notion of weak-space. We investigate the weak-space bounded computations and ... more >>>

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

TR16-153 | 28th September 2016
Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials

Revisions: 3

The power symmetric polynomial on $n$ variables of degree $d$ is defined as
$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers
of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by
... more >>>

TR15-202 | 11th December 2015
Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Building above read-once polynomials: identity testing and hardness of representation

Polynomial Identity Testing (PIT) algorithms have focused on
polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted
formulas. Read-once polynomials (ROPs) are computed by read-once
formulas (ROFs) and are the simplest of read-restricted polynomials.
Building structures above these, we show the following:
\item A deterministic polynomial-time non-black-box ... 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