Complexity of Linear Boolean Operators

by Igor Sergeev and Stasys Jukna

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...

• Format: Paperback
• Language: English
• ISBN: 1601987269
• ISBN13: 9781601987266
• Release Date: October 2013
• Publisher: Now Publishers
• Length: 138 Pages
• Weight: 0.45 lbs.
• Dimensions: 0.3" x 6.1" x 9.2"