Under the auspices of the Computational Complexity Foundation (CCF)

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

ISSN 1433-8092 | Imprint