More Boolean Circuit Lower Bounds

Eyal Kushilevitz, Noam NisanCambridge 1996 · DOI · OpenAlex

Abstract

In this chapter we describe several other ways to use communication complexity for proving various results on Boolean circuits. These results differ from those in Chapter 10 in that they do not use the connection between the circuit complexity of f and the communication complexity ofthe corresponding relation Rf and in that the circuits considered here are not restricted to use only ∨ and ∧ gates but instead use richer families of gates.
BibTeX
@inproceedings{kushilevitz1996more,
  author = {Eyal Kushilevitz and Noam Nisan},
  title = {{More Boolean Circuit Lower Bounds}},
  booktitle = {Cambridge},
  year = {1996},
  doi = {10.1017/cbo9780511574948.012},
}

Loading related content...

Figure