Foundations and Trends® in Theoretical Computer Science

Volume 9, issue 3–4

The Algorithmic Foundations of Differential Privacy

The problem of privacy-preserving data analysis has a long history spanning multiple disciplines. As electronic data about individuals becomes increasingly detailed, and as technology enables ever more powerful collection and curation of these data, the need increases for a robust, meaningful, and m...
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