Books in the Foundations and Trends (R) in Theoretical Computer Science series

Surveys the emerging area of algorithms for processing data streams and associated applications. An extensive bibliography with over 200 entries points the reader to further resources for exploration.

Provides an introduction to the field of higher-order Fourier analysis with an emphasis on its applications to theoretical computer science. Higher-order Fourier analysis is an extension of the classical Fourier analysis.

Details the interplay between proof systems and efficient algorithm design and surveys the state-of-the-art for two of the most important semi-algebraic proof systems: Sherali-Adams and Sum-of-Squares. The book provides the readers with a rigorous treatment of these systems both as proof systems, and as a general family of optimization algorithms.

Presents a series of ten lectures divided into two parts. Part 1, referred to as the Solar Lectures, focuses on the communication and computational complexity of computing an (approximate) Nash equilibrium. Part 2, the Lunar Lectures, focuses on applications of computational complexity theory to game theory and economics.