Foundations and Trends® in Theoretical Computer Science

Volume 9, issue 2

Faster Algorithms via Approximation Theory

This monograph presents techniques to approximate real functions such as xs; x–1 and e–x by simpler functions and shows how these results can be used for the design of fast algorithms. The key lies in the fact that such results imply faster ways to approximate primitives such as Asv; A–1v and
Volume 9, issue 1

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