8 citations · 28 across the 39 of their papers we have counts for
5 papers · 1 filter
Circuit Lower Bounds, Help Functions, and the Remote Point Problem
Vikraman Arvind, Srikanth Srinivasan
We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the pr…
On the hardness of the noncommutative determinant
V. Arvind, Srikanth Srinivasan
In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative…
The Remote Point Problem, Small Bias Space, and Expanding Generator Sets
Vikraman Arvind, Srikanth Srinivasan
Using -bias spaces over , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an algorithm (achieving the same parameters as [APY09]).…
On Lower Bounds for Constant Width Arithmetic Circuits
V. Arvind, Pushkar S. Joglekar, Srikanth Srinivasan
The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following. 1. For every k > 1, we provide an explicit polyn…
Arithmetic Circuits and the Hadamard Product of Polynomials
V. Arvind, Pushkar S. Joglekar, Srikanth Srinivasan
Motivated by the Hadamard product of matrices we define the Hadamard product of multivariate polynomials and study its arithmetic circuit and branching program complexity. We also…