Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with permanent:
TR00-036 | 29th May 2000
Carsten Damm, Markus Holzer, Pierre McKenzie

The Complexity of Tensor Calculus

Tensor calculus over semirings is shown relevant to complexity
theory in unexpected ways. First, evaluating well-formed tensor
formulas with explicit tensor entries is shown complete for $\olpus\P$,
for $\NP$, and for $\#\P$ as the semiring varies. Indeed the
permanent of a matrix is shown expressible as ... more >>>

TR00-079 | 12th September 2000
Mark Jerrum, Eric Vigoda

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

We present a fully-polynomial randomized approximation scheme
for computing the permanent of an arbitrary matrix
with non-negative entries.

more >>>

TR02-071 | 6th June 2002
Bruno Codenotti, Igor E. Shparlinski

Non-approximability of the Permanent of Structured Matrices over Finite Fields

We show that for several natural classes of ``structured'' matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime $p$ is as hard as computing the exact value. Results of this kind are well known for the class of arbitrary matrices; however the techniques used do ... more >>>

TR04-003 | 22nd December 2003
Pascal Koiran

Valiant's model and the cost of computing integers

Let $\tau(k)$ be the minimum number of arithmetic operations
required to build the integer $k \in \N$ from the constant 1.
A sequence $x_k$ is said to be ``easy to compute'' if
there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$
for all $k \geq ... more >>>

TR05-098 | 4th September 2005
Oded Goldreich

Bravely, Moderately: A Common Theme in Four Recent Results

We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
more >>>

TR06-025 | 19th January 2006
Leonid Gurvits

Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\\ Sharper Bounds , Simpler Proofs and Algorithmic Applications

Let $p(x_1,...,x_n) = p(X) , X \in R^{n}$ be a homogeneous polynomial of degree $n$ in $n$ real variables ,
$e = (1,1,..,1) \in R^n$ be a vector of all ones . Such polynomial $p$ is
called $e$-hyperbolic if for all real vectors $X \in R^{n}$ the univariate polynomial
equation ... more >>>

TR06-113 | 25th August 2006
Peter Buergisser

On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity

Let $\tau(n)$ denote the minimum number of arithmetic operations sufficient to build the integer $n$ from the constant~$1$. We prove that if there are arithmetic circuits for computing the permanent of $n$ by $n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $\log n$. Under the ... 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 >>>

TR10-078 | 27th April 2010
Holger Dell, Thore Husfeldt, Martin Wahlén

Exponential Time Complexity of the Permanent and the Tutte Polynomial

Revisions: 1

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting ... more >>>

TR10-105 | 29th June 2010
Scott Aaronson, Dieter van Melkebeek

A note on circuit lower bounds from derandomization

We present an alternate proof of the result by Kabanets and Impagliazzo that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.

more >>>

TR10-170 | 11th November 2010
Scott Aaronson, Alex Arkhipov

The Computational Complexity of Linear Optics

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a
model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count ... more >>>

TR11-043 | 25th March 2011
Scott Aaronson

A Linear-Optical Proof that the Permanent is #P-Hard

One of the crown jewels of complexity theory is Valiant's 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing---and in particular, a universality theorem due to Knill, Laflamme, and Milburn---one can give a different and ... 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-133 | 4th October 2011
Maurice Jansen, Rahul Santhanam

Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

TR12-007 | 28th January 2012
Ruiwen Chen, Valentine Kabanets

Lower Bounds against Weakly Uniform Circuits

Revisions: 1

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if
there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,
given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one
to interpolate between complete uniformity (when $\gamma(n)=0$) ... more >>>

TR12-094 | 19th July 2012
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Testing Permanent Oracles -- Revisited

Suppose we are given an oracle that claims to approximate the permanent for most matrices $X$, where $X$ is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task.

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

TR12-170 | 30th November 2012
Scott Aaronson, Travis Hance

Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... more >>>

TR13-135 | 27th September 2013
Scott Aaronson

BosonSampling Is Far From Uniform

Revisions: 2

BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random ... more >>>

TR13-141 | 8th October 2013
Leonid Gurvits

Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications

Revisions: 1

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with
boolean matrices with prescribed row and (uniformly bounded) column sums within simply ... 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 >>>

TR15-171 | 28th October 2015
Joshua Grochow

Monotone projection lower bounds from extended formulation lower bounds

Revisions: 2 , Comments: 1

In this short note, we show that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. In particular, we show that Hamilton Cycle polynomial and the cut polynomials are not monotone p-projections of the permanent. To prove this we introduce a new connection between monotone projections ... more >>>

TR16-002 | 18th January 2016
Ryan Williams

Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,
$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ... more >>>

TR16-159 | 18th October 2016
Daniel Grier, Luke Schaeffer

New Hardness Results for the Permanent Using Linear Optics

In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact ... more >>>

ISSN 1433-8092 | Imprint