Geodesic
On a hierarchy of Boolean functions hard to compute in constant depth
Discrete mathematics & theoretical computer science, Tome 4 (2000-2001) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2001_4_2_a10,
     author = {Bernasconi, Anna},
     title = {On a hierarchy of {Boolean} functions hard to compute in constant depth},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {4},
     number = {2},
     year = {2000-2001},
     doi = {10.46298/dmtcs.283},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.283/}
}
TY  - JOUR
AU  - Bernasconi, Anna
TI  - On a hierarchy of Boolean functions hard to compute in constant depth
JO  - Discrete mathematics & theoretical computer science
PY  - 2000-2001
VL  - 4
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.283/
DO  - 10.46298/dmtcs.283
LA  - en
ID  - DMTCS_2001_4_2_a10
ER  - 
%0 Journal Article
%A Bernasconi, Anna
%T On a hierarchy of Boolean functions hard to compute in constant depth
%J Discrete mathematics & theoretical computer science
%D 2000-2001
%V 4
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.283/
%R 10.46298/dmtcs.283
%G en
%F DMTCS_2001_4_2_a10
Bernasconi, Anna. On a hierarchy of Boolean functions hard to compute in constant depth. Discrete mathematics & theoretical computer science, Tome 4 (2000-2001) no. 2. doi : 10.46298/dmtcs.283. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.283/

Cité par Sources :