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

dmtcs:283 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, Vol. 4 no. 2 - https://doi.org/10.46298/dmtcs.283
On a hierarchy of Boolean functions hard to compute in constant depthArticle

Authors: Anna Bernasconi 1

  • 1 Dipartimento di Informatica [Pisa]

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.


Volume: Vol. 4 no. 2
Published on: January 1, 2001
Imported on: March 26, 2015
Keywords: Boolean functions,AC^0 circuits,size complexity,harmonic analysis,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 292 times.
This article's PDF has been downloaded 269 times.