Communication complexity towards lower bounds on circuit depth |
| |
Authors: | J Edmonds R Impagliazzo S Rudich J Sgall |
| |
Affiliation: | (1) Department of Computer Science, York University, North York, Ontario M3J 1P3, Canada, e-mail: jeff@cs.yorku.ca, CA;(2) Department of Computer Science, UC San Diego, La Jolla CA 92093, U.S.A., e-mail: russell@cs.ucsd.edu, US;(3) Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, U.S.A., e-mail: rudich@theory.cs.cmu.edu, US;(4) Mathematical Institute, AS CR, Zitná 25, 115 67 Praha 1, Czech Republic, e-mail: sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, CZ |
| |
Abstract: | Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC1 . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for
this problem requires depth. This would separate AC1 from NC1. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using
communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem
which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d
2(k log k)1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function
on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof
will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds.
Received: July 30, 1999. |
| |
Keywords: | , Communication complexity, Boolean complexity, lower bounds, |
本文献已被 SpringerLink 等数据库收录! |
|