Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DETERMINANTAL COMPLEXITY:
Reports tagged with determinantal complexity:
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 >>>


TR17-028 | 17th February 2017
Mrinal Kumar

A quadratic lower bound for homogeneous algebraic branching programs

Revisions: 1

An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex $s$, and end vertex $t$ and each edge having a weight which is an affine form in $\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of ... more >>>


TR20-129 | 5th September 2020
Mrinal Kumar, Ben Lee Volk

A Lower Bound on Determinantal Complexity

The determinantal complexity of a polynomial $P \in \mathbb{F}[x_1, \ldots, x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1, \ldots, x_n]$ such that $P = Det(M)$. We prove that the determinantal complexity of the polynomial $\sum_{i = 1}^n x_i^n$ ... more >>>


TR24-015 | 9th January 2024
Harpreet Bedi

Degree 2 lower bound for Permanent in arbitrary characteristic

An elementary proof of quadratic lower bound for determinantal complexity of the permanent in positive characteristic is stated. This is achieved by constructing a sequence of matrices with zero permanent, but the rank of Hessian is bounded below by a degree two polynomial.

more >>>

TR25-099 | 17th July 2025
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff

The Algebraic Cost of a Boolean Sum

It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression.
We study the question of why the VNP-completeness proof of the permanent fails for the determinant.
We ... more >>>




ISSN 1433-8092 | Imprint