On a hierarchy of Boolean functions hard to compute in constant depth - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2001

On a hierarchy of Boolean functions hard to compute in constant depth

Résumé

Any attempt to find connections between mathematical properties and complexity has a strong relevance to the field of Complexity Theory. This is due to the lack of mathematical techniques to prove lower bounds for general models of computation.\par This work represents a step in this direction: we define a combinatorial property that makes Boolean functions ''\emphhard'' to compute in constant depth and show how the harmonic analysis on the hypercube can be applied to derive new lower bounds on the size complexity of previously unclassified Boolean functions.
Fichier principal
Vignette du fichier
dm040201.pdf (77.76 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00958948 , version 1 (13-03-2014)

Identifiants

Citer

Anna Bernasconi. On a hierarchy of Boolean functions hard to compute in constant depth. Discrete Mathematics and Theoretical Computer Science, 2001, Vol. 4 no. 2 (2), pp.79-90. ⟨10.46298/dmtcs.283⟩. ⟨hal-00958948⟩

Collections

TDS-MACS
47 Consultations
866 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More