Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR08-062 | 11th June 2008
Manindra Agrawal, V Vinay

Arithmetic Circuits: A Chasm at Depth Four

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

TR02-066 | 24th October 2002
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay

Circuits on Cylinders

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

TR01-041 | 23rd May 2001
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay

Time-Space Tradeoffs in the Counting Hierarchy

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

TR00-088 | 28th November 2000
Meena Mahajan, V Vinay

A note on the hardness of the characteristic polynomial

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

Santha and Tan [CC98] show that verifying the determinant
(the constant term in the characteristic polynomial) is
complete for the class C=L, ... more >>>

TR99-030 | 9th July 1999
Meena Mahajan, P R Subramanya, V Vinay

A Combinatorial Algorithm for Pfaffians

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

TR98-012 | 2nd February 1998
Meena Mahajan, V Vinay

Determinant: Old Algorithms, New Insights

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

TR97-036 | 1st August 1997
Meena Mahajan, V Vinay

Determinant: Combinatorics, Algorithms, and Complexity

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

TR95-043 | 14th September 1995
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay

Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

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

ISSN 1433-8092 | Imprint