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	CCSd/HAL : e-articles server (based on gBUS) (France)
Keywords	Computer Science/Computational Complexity, permanent, lower bound, threshold circuits, uniform circuits, non-constant depth circuits, arithmetic circuits
Type	text
Language	English
Relation	http://hal.archives-ouvertes.fr/docs/00/36/05/07/PDF/permanent.pdf