Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > VINEET NAIR:
All reports by Author Vineet Nair:

TR17-021 | 11th February 2017
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

Reconstruction of full rank Algebraic Branching Programs

An algebraic branching program (ABP) A can be modelled as a product expression X_1\cdot X_2\cdot \dots \cdot X_d, where X_1 and X_d are 1 \times w and w \times 1 matrices respectively, and every other X_k is a w \times w matrix; the entries of these matrices are linear forms ... more >>>


TR15-154 | 22nd September 2015
Neeraj Kayal, Vineet Nair, Chandan Saha

Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:

1. There exists an explicit n-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) ... more >>>




ISSN 1433-8092 | Imprint