All reports by Author V Vinay:

__
TR16-096
| 14th June 2016
__

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay#### The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revisions: 2

__
TR08-062
| 11th June 2008
__

Manindra Agrawal, V Vinay#### Arithmetic Circuits: A Chasm at Depth Four

__
TR02-066
| 24th October 2002
__

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay#### Circuits on Cylinders

__
TR01-041
| 23rd May 2001
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay#### Time-Space Tradeoffs in the Counting Hierarchy

__
TR00-088
| 28th November 2000
__

Meena Mahajan, V Vinay#### A note on the hardness of the characteristic polynomial

__
TR99-030
| 9th July 1999
__

Meena Mahajan, P R Subramanya, V Vinay#### A Combinatorial Algorithm for Pfaffians

__
TR98-012
| 2nd February 1998
__

Meena Mahajan, V Vinay#### Determinant: Old Algorithms, New Insights

__
TR97-036
| 1st August 1997
__

Meena Mahajan, V Vinay#### Determinant: Combinatorics, Algorithms, and Complexity

__
TR95-043
| 14th September 1995
__

Eric Allender, Jia Jiao, Meena Mahajan, V Vinay#### Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>

Manindra Agrawal, V Vinay

We show that proving exponential lower bounds on depth four arithmetic

circuits imply exponential lower bounds for unrestricted depth arithmetic

circuits. In other words, for exponential sized circuits additional depth

beyond four does not help.

We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay

We consider the computational power of constant width polynomial

size cylindrical circuits and nondeterministic branching programs.

We show that every function computed by a Pi2 o MOD o AC0 circuit

can also be computed by a constant width polynomial size cylindrical

nondeterministic branching program (or cylindrical circuit) and

that ...
more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay

We extend the lower bound techniques of [Fortnow], to the

unbounded-error probabilistic model. A key step in the argument

is a generalization of Nepomnjascii's theorem from the Boolean

setting to the arithmetic setting. This generalization is made

possible, due to the recent discovery of logspace-uniform TC^0

more >>>

Meena Mahajan, V Vinay

In this note, we consider the problem of computing the

coefficients of the characteristic polynomial of a given

matrix, and the related problem of verifying the

coefficents.

Santha and Tan [CC98] show that verifying the determinant

(the constant term in the characteristic polynomial) is

complete for the class C=L, ...
more >>>

Meena Mahajan, P R Subramanya, V Vinay

The Pfaffian of an oriented graph is closely linked to

Perfect Matching. It is also naturally related to the determinant of

an appropriately defined matrix. This relation between Pfaffian and

determinant is usually exploited to give a fast algorithm for

computing Pfaffians.

We present the first completely combinatorial algorithm for ... more >>>

Meena Mahajan, V Vinay

In this paper we approach the problem of computing the characteristic

polynomial of a matrix from the combinatorial viewpoint. We present

several combinatorial characterizations of the coefficients of the

characteristic polynomial, in terms of walks and closed walks of

different kinds in the underlying graph. We develop algorithms based

more >>>

Meena Mahajan, V Vinay

We prove a new combinatorial characterization of the

determinant. The characterization yields a simple

combinatorial algorithm for computing the

determinant. Hitherto, all (known) algorithms for

determinant have been based on linear algebra. Our

combinatorial algorithm requires no division and works over

arbitrary commutative rings. It also lends itself to

more >>>

Eric Allender, Jia Jiao, Meena Mahajan, V Vinay

We investigate the phenomenon of depth-reduction in commutative

and non-commutative arithmetic circuits. We prove that in the

commutative setting, uniform semi-unbounded arithmetic circuits of

logarithmic depth are as powerful as uniform arithmetic circuits of

polynomial degree; earlier proofs did not work in the ...
more >>>