Publication View

A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent (2009)

Abstract

We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.

Publication details

Download	http://hal.archives-ouvertes.fr/hal-00360507/en/
Publisher	HAL - CCSD
Repository	INRIA a CCSD electronic archive server based on P.A.O.L (France)
Keywords	Computer Science/Computational Complexity, permanent, lower bound, threshold circuits, uniform circuits, non-constant depth circuits, arithmetic circuits
Language	English
Relation	http://hal.archives-ouvertes.fr/docs/00/36/05/07/PDF/permanent.pdf