Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958948
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:51:22 PM
Last modification on : Tuesday, February 26, 2019 - 10:54:02 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:03:18 PM

File

dm040201.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958948, version 1

Collections

Citation

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

Share

Metrics

Record views

131

Files downloads

945