Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DETERMINANT:
Reports tagged with determinant:
TR96-024 | 21st March 1996
Eric Allender, Robert Beals, Mitsunori Ogihara

#### The complexity of matrix rank and feasible systems of linear equations

We characterize the complexity of some natural and important
problems in linear algebra. In particular, we identify natural
complexity classes for which the problems of (a) determining if a
system of linear equations is feasible and (b) computing the rank of
an integer matrix, ... 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 >>>

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

TR98-019 | 5th April 1998
Eric Allender, Klaus Reinhardt

#### Isolation, Matching, and Counting

We show that the perfect matching problem is in the
complexity class SPL (in the nonuniform setting).
This provides a better upper bound on the complexity of the
matching problem, as well as providing motivation for studying
the complexity class SPL.

Using similar ... more >>>

TR98-023 | 16th April 1998
Eric Allender, Shiyu Zhou

#### Uniform Inclusions in Nondeterministic Logspace

We show that the complexity class LogFew is contained
in NL $\cap$ SPL. Previously, this was known only to
hold in the nonuniform setting.

more >>>

TR99-008 | 19th March 1999
Eric Allender, Vikraman Arvind, Meena Mahajan

#### Arithmetic Complexity, Kleene Closure, and Formal Power Series

The aim of this paper is to use formal power series techniques to
study the structure of small arithmetic complexity classes such as
GapNC^1 and GapL. More precisely, we apply the Kleene closure of
languages and the formal power series operations of inversion and
root ... 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 >>>

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

TR02-016 | 30th January 2002
Alina Beygelzimer, Mitsunori Ogihara

#### On the Enumerability of the Determinant and the Rank

We investigate the complexity of enumerative approximation of
two elementary problems in linear algebra, computing the rank
and the determinant of a matrix. In particular, we show that
if there exists an enumerator that, given a matrix, outputs a
list of constantly many numbers, one of which is guaranteed to
more >>>

TR07-124 | 23rd November 2007
Nitin Saxena

#### Diagonal Circuit Identity Testing and Lower Bounds

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-$3$ circuit $C(\arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only ... more >>>

TR09-103 | 26th October 2009
Vikraman Arvind, Srikanth Srinivasan

#### On the Hardness of the Noncommutative Determinant

In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below:

... more >>>

TR11-061 | 18th April 2011
Neeraj Kayal

#### Affine projections of polynomials

Revisions: 1

An $m$-variate polynomial $f$ is said to be an affine projection of some $n$-variate polynomial $g$ if there exists an $n \times m$ matrix $A$ and an $n$-dimensional vector $b$ such that $f(x) = g(A x + b)$. In other words, if $f$ can be obtained by replacing each variable ... more >>>

TR11-168 | 9th December 2011
Joshua Grochow

We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set $\mathcal{L}$ of matrices such that $A,B \in \mathcal{L}$ implies$AB - BA \in ... more >>> TR11-174 | 30th December 2011 Pavel Hrubes, Iddo Tzameret #### Short Proofs for the Determinant Identities Revisions: 1 We study arithmetic proof systems$\mathbb{P}_c(\mathbb{F})$and$\mathbb{P}_f(\mathbb{F})$operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field$\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that$\mathbb{P}_c(\mathbb{F})$proofs can be balanced: if a polynomial identity of ... more >>> TR12-098 | 3rd August 2012 Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi #### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin Revisions: 3 Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of$\times$gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>> TR12-142 | 3rd November 2012 Markus Bläser #### Noncommutativity makes determinants hard We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that$A$is fixed. We obtain the following dichotomy: If$A/rad(A)$is noncommutative, then computing the determinant over$A$is hard. Hard'' here means$\#P$-hard over fields of characteristic$0$and$ModP_p$-hard over ... more >>> TR13-026 | 11th February 2013 Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi #### Arithmetic circuits: A chasm at depth three Revisions: 1 We show that, over$\mathbb{C}$, if an$n$-variate polynomial of degree$d = n^{O(1)}$is computable by an arithmetic circuit of size$s$(respectively by an algebraic branching program of size$s$) then it can also be computed by a depth three circuit (i.e. a$\Sigma \Pi \Sigma$-circuit) of size ... more >>> TR14-105 | 9th August 2014 Craig Gentry #### Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington’s Theorem Comments: 1 We show that, for many noncommutative algebras A, the hardness of computing the determinant of matrices over A follows almost immediately from Barrington’s Theorem. Barrington showed how to express a NC1 circuit as a product program over any non-solvable group. We construct a simple matrix directly from Barrington’s product program ... more >>> TR15-141 | 26th August 2015 Pushkar Joglekar, Aravind N.R. #### On the expressive power of read-once determinants We introduce and study the notion of read-$k$projections of the determinant: a polynomial$f \in \mathbb{F}[x_1, \ldots, x_n]$is called a {\it read-$k$projection of determinant} if$f=det(M)$, where entries of matrix$M$are either field elements or variables such that each variable appears at most$k$times in ... more >>> TR20-091 | 14th June 2020 Janaky Murthy, vineet nair, Chandan Saha #### Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests Equivalence testing for a polynomial family$\{g_m\}_{m \in \mathbb{N}}$over a field F is the following problem: Given black-box access to an$n$-variate polynomial$f(\mathbb{x})$, where$n$is the number of variables in$g_m$for some$m \in \mathbb{N}$, check if there exists an$A \in \text{GL}(n,\text{F})$such that$f(\mathbb{x}) ... more >>>

TR20-158 | 26th October 2020
Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla

#### A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity

This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET ... more >>>

ISSN 1433-8092 | Imprint