Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PERMANENT:
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