A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent
| Autor: | Sylvain Perifel, Pascal Koiran |
|---|---|
| Přispěvatelé: | Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL) |
| Jazyk: | angličtina |
| Rok vydání: | 2009 |
| Předmět: |
FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] Polynomial Computational complexity theory Arithmetic circuits uniform circuits 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) 01 natural sciences Upper and lower bounds permanent Combinatorics Log-log plot arithmetic circuits TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0202 electrical engineering electronic engineering information engineering lower bound Mathematics Electronic circuit Discrete mathematics threshold circuits non-constant depth circuits Computer Science - Computational Complexity 010201 computation theory & mathematics Logic gate 020201 artificial intelligence & image processing Constant (mathematics) MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | IEEE Conference on Computational Complexity |
| Popis: | We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size. Comment: 11 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|