Foundations and Trends® in Theoretical Computer Science > Vol 9 > Issue 1

Complexity of Linear Boolean Operators

By Stasys Jukna, Vilnius University, Lithuania and Frankfurt University, Germany, jukna@online.de | Igor Sergeev, Lomonosov Moscow State University, Russia, isserg@gmail.com

 
Suggested Citation
Stasys Jukna and Igor Sergeev (2013), "Complexity of Linear Boolean Operators", Foundations and Trends® in Theoretical Computer Science: Vol. 9: No. 1, pp 1-123. http://dx.doi.org/10.1561/0400000063

Publication Date: 31 Oct 2013
© 2013 S. Jukna and I. Sergeev
 
Subjects
Computational aspects of combinatorics and graph theory,  Computational complexity,  Computational Models and Complexity
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction 
2. General Upper Bounds 
3. General Lower Bounds 
4. Complexity of Some Basic Matrices 
5. Complexity Gaps 
6. Bounds for General Circuits 
7. Conclusion and Open Problems 
Acknowledgements 
References 

Abstract

How to compute a linear Boolean operator by a small circuit using only unbounded fanin addition gates? Because this question is about one of the simplest and most basic circuit models, it has been considered by many authors since the early 1950s. This has led to a variety of upper and lower bound arguments—ranging from algebraic (determinant and matrix rigidity), to combinatorial (Ramsey properties, coverings, and decompositions) to graph-theoretic (the superconcentrator method). We provide a thorough survey of the research in this direction, and prove some new results to fill out the picture. The focus is on the cases in which the addition operation is either the boolean OR or XOR, but the model in which arbitrary boolean functions are allowed as gates is considered as well.

DOI:10.1561/0400000063
ISBN: 978-1-60198-726-6
136 pp. $90.00
Buy book (pb)
 
ISBN: 978-1-60198-727-3
136 pp. $115.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. General Upper Bounds
3. General Lower Bounds
4. Complexity of Some Basic Matrices
5. Complexity Gaps
6. Bounds for General Circuits
7. Conclusion and Open Problems
Acknowledgements
References

Complexity of Linear Boolean Operators

How to compute a linear Boolean operator by a small circuit using only unbounded fanin addition gates? Because this question is about one of the simplest and most basic circuit models, it has been considered by many authors since the early 1950s. This has led to a variety of upper and lower bound arguments—ranging from algebraic (determinant and matrix rigidity), to combinatorial (Ramsey properties, coverings, and decompositions) to graph-theoretic (the superconcentrator method).

Complexity of Linear Boolean Operators is the first thorough survey of the research in this area. The focus is on cases where the addition operation is either the Boolean OR or XOR, but the model in which arbitrary Boolean functions are allowed as gates is considered as well. The survey is intended for students and researchers in discrete mathematics and theoretical computer science. No special background in computational complexity is assumed and the text is also accessible to senior undergraduates. The insightfulness of the arguments presented here invites the reader to delve deeper and hopefully conquer this "complexity Waterloo": to prove a superlinear lower bound for XOR circuits.

 
TCS-063