Bücher der Reihe Foundations and Trends (R) in Theoretical Computer Science

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.

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.

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.

An interactive proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear time. This book surveys some of the known results regarding doubly-efficient interactive proof systems.

Surveys a family of algorithmic techniques for the design of scalable algorithms. These techniques include local network exploration, advanced sampling, sparsification, and geometric partitioning. They also include spectral graph-theoretical methods, such as are used for computing electrical flows and sampling from Gaussian Markov random fields.

The two primary goals of the text are to learn several canonical problems in communication complexity that are useful for proving lower bounds for algorithms (Disjointness, Index, Gap-Hamming, and so on); and to learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.

Provides an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, the book discusses non-interactive proofs and the complexity class QMA, and single-prover quantum interactive proof systems and the complexity class QIP.

Surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational short integer solution and learning with errors problems, their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.

Constraint satisfaction problems are a central pillar of modern computational complexity theory. This monograph provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity (QHC), which includes the study of quantum constraint satisfaction problems.

This self-contained tutorial presents a unified treatment of single- and multi-user problems in Shannon's information theory considering in particular the cases that depart from the requirement that the error probability decays asymptotically in the blocklength.

Discusses the meaning of differential privacy, and then explores the fundamental techniques for achieving differential privacy, and the application of these techniques in creative combinations, using the query-release problem as an ongoing example.

Illustrates how classical and modern techniques from approximation theory play a crucial role in obtaining results that are relevant to the emerging theory of fast algorithms. This book is self-contained and should be of interest to researchers and students in theoretical computer science, numerical linear algebra, and related areas.

Surveys the key problems, models, and algorithms from online matchings, as well as their implication in the practice of ad allocation. The book provides a classification of the problems in this area, an introduction into the techniques used, a glimpse into the practical impact, and ponders some questions that will be of interest in the future.

Surveys the classical economic theory of Bayesian mechanism design and recent advances from the perspective of algorithms and approximation. Classical economics gives simple characterizations of Bayes-Nash equilibrium and optimal mechanisms when the agents' preferences are linear and single-dimensional.

Illustrates the emerging paradigm of employing Laplacian solvers to design novel fast algorithms for graph problems through a small but carefully chosen set of examples. A significant part of this book is also dedicated to developing the ideas that go into the construction of near-linear time Laplacian solvers.

Studies polynomials from a computational perspective. The book illustrates that one can learn a great deal about the structure and complexity of polynomials by studying their partial derivatives. It also shows that partial derivatives provide essential ingredients in proving both upper and lower bounds for computing polynomials.

Highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compressed it to a much smaller matrix by multiplying it by a (usually) random matrix with certain properties.

Surveys the field of arithmetic circuit complexity, focusing mainly on what the authors find to be the most interesting and accessible research directions. They cover the main results and techniques, with an emphasis on works from the last two decades.

Incidence theorems describe the way lines, points and other geometric objects intersect each other. Theorems of this sort have found a large number of exciting applications in the past few decades, both in mathematics and in theoretical computer science. This book presents some of the seminal results in this area as well as recent developments.

An ideal primer for anyone with an interest in computational complexity, random structures and algorithms and theoretical computer science generally.

In the last two decades, property testing algorithms have been designed for many types of objects and properties, amongst them, graph properties, algebraic properties, geometric properties, and more. This book surveys results in property testing, with an emphasis on common analysis and algorithmic techniques.

Focuses on showing lower bounds on the communication complexity of explicit functions. The book treats different variants of communication complexity, including randomized, quantum, and multiparty models.

Describes modern applications of spectral methods, and novel algorithms for estimating spectral parameters. The first part of the book presents applications of spectral methods to problems from a variety of topics including combinatorial optimization, learning and clustering. The second part is motivated by efficiency considerations.

Introduces locally decodable codes, and discusses the central results of the subject. Locally Decodable Codes assumes basic familiarity with the properties of finite fields and is otherwise self-contained. It will benefit computer scientists, electrical engineers, and mathematicians with an interest in coding theory.

Surveys several techniques for proving lower bounds in Boolean, algebraic, and communication complexity based on certain linear algebraic approaches. The common theme among these approaches is to study robustness measures of matrix rank that capture the complexity in a given model.

This primer concentrates on three types of probabilistic proof systems: interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs. Surveying the basic results regarding these proof systems, the primer stresses the essential role of randomness in each of them.

Surveys the recently discovered lower bounds for the time and space complexity of satisfiability and closely related problems. It overviews the state-of-the-art results on general deterministic, randomized, and quantum models of computation, and presents the underlying arguments in a unified framework.

Extends the primal-dual method to the setting of online algorithms, and shows its applicability to a wide variety of fundamental problems. Among the online problems considered are the weighted caching problem, generalized caching, the set-cover problem, graph optimization problems, routing, load balancing, and the problem of allocating ad-auctions.

Introduces and motivates the problem of list decoding, and discusses the central algorithmic results of the subject, culminating with the recent results on achieving "list decoding capacity". The main technical focus is on giving a complete presentation of the recent algebraic results achieving list decoding capacity.

Provides a gentle introduction to the analytical aspects of the theory of finite Markov chain mixing times and quickly ramps up to explain the latest developments in the topic. Several theorems are revisited and often derived in simpler, transparent ways, and illustrated with examples.