Articles for TCShttps://www.nowpublishers.com/feed/TCSArticles for TCShttp://www.nowpublishers.com/article/Details/TCS-084On Doubly-Efficient Interactive Proof Systems<h3>Abstract</h3>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. Such proof systems, introduced by Goldwasser, Kalai, and Rothblum (JACM, 2015), make the benefits of interactive proof system available to real-life agents who are restricted to polynomial-time computation. We survey some of the known results regarding doubly-efficient interactive proof system. We start by presenting two simple constructions for t-no-CLIQUE (due to Goldreich and Rothblum (ECCC, 2017 and 2018)), where the first construction offers the benefit of being generalized to any “locally characterizable” set, and the second construction offers the benefit of preserving the combinatorial flavor of the problem. We then turn to two more general constructions of doublyefficient interactive proof system: the proof system for sets having (uniform) bounded-depth circuits (due to Goldwasser, Kalai and Rothblum (JACM, 2015)), and the proof system for sets that are recognized in polynomial-time and small space (due to Reingold, Rothblum, and Rothblum (STOC, 2016)). Our presentation of the GKR construction is quite complete (and is somewhat different from the original presentation),
but for the RRR construction we only provide an overview.<h3>Suggested Citation</h3>Oded Goldreich (2018), "On Doubly-Efficient Interactive Proof Systems", Foundations and Trends® in Theoretical Computer Science: Vol. 13: No. 3, pp 158-246. http://dx.doi.org/10.1561/0400000084Thu, 19 Apr 2018 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-079Coding for Interactive Communication: A Survey<h3>Abstract</h3>Coding for interactive communication augments coding theory to the interactive setting: instead of communicating a message from a sender to a receiver, here the parties are involved in an interactive conversation.
Coding schemes allow the parties to complete their conversation despite noise added by the channel. Similar to the unidirectional case, good coding schemes can withstand a large amount of noise and succeed with high probability, while adding only a small amount of redundant information.
We aim at giving a comprehensive view on the foundations of coding for interactive communication. In particular, we review basic features of coding schemes in the interactive setting, and survey the main techniques used in designing such schemes. Furthermore, we survey recent developments in interactive coding schemes, and their applications to other related fields.
<h3>Suggested Citation</h3>Ran Gelles (2017), "Coding for Interactive Communication: A Survey", Foundations and Trends® in Theoretical Computer Science: Vol. 13: No. 1–2, pp 1-157. http://dx.doi.org/10.1561/0400000079Tue, 17 Oct 2017 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-070Hashing, Load Balancing and Multiple Choice<h3>Abstract</h3>Many tasks in computer systems could be abstracted as distributing
items into buckets, so that the allocation of items across buckets is as
balanced as possible, and furthermore, given an item’s identifier it is
possible to determine quickly to which bucket it was assigned. A canonical
example is a dictionary data structure, where ‘items’ stands for
key-value pairs and ‘buckets’ for memory locations. Another example
is a distributed key-value store, where the buckets represent locations
in disk or even whole servers. A third example may be a distributed
execution engine where items represent processes and buckets compute
devices, and so on. A common technique in this domain is the use of
a hash-function that maps an item into a relatively short fixed length
string. The hash function is then used in some way to associate the
item to its bucket. The use of a hash function is typically the first step
in the solution and additional algorithmic ideas are required to deal
with collisions and the imbalance of hash values. In this monograph we
survey some of these techniques. We focus on multiple choice schemes
where items are placed into buckets via the use of several independent
hash functions, and typically an item is placed at the least loaded
bucket at the time of placement. We analyze the distributions obtained
in detail, and show how these ideas could be used to design basic data
structures. With respect to data structures we focus on dictionaries,
presenting linear probing, cuckoo hashing and many of their variants.<h3>Suggested Citation</h3>Udi Wieder (2017), "Hashing, Load Balancing and Multiple Choice", Foundations and Trends® in Theoretical Computer Science: Vol. 12: No. 3–4, pp 275-379. http://dx.doi.org/10.1561/0400000070Tue, 11 Jul 2017 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-051Scalable Algorithms for Data and Network Analysis<h3>Abstract</h3>In the age of Big Data, efficient algorithms are now in higher demand
more than ever before. While Big Data takes us into the asymptotic
world envisioned by our pioneers, it also challenges the classical notion
of efficient algorithms: Algorithms that used to be considered efficient,
according to polynomial-time characterization, may no longer be adequate
for solving today’s problems. It is not just desirable, but essential,
that efficient algorithms should be scalable. In other words, their complexity
should be nearly linear or sub-linear with respect to the problem
size. Thus, scalability, not just polynomial-time computability, should
be elevated as the central complexity notion for characterizing efficient
computation.
In this tutorial, I will survey a family of algorithmic techniques for
the design of provably-good scalable algorithms. These techniques include
local network exploration, advanced sampling, sparsification, and
geometric partitioning. They also include spectral graph-theoretical
methods, such as those used for computing electrical flows and sampling
from Gaussian Markov random fields. These methods exemplify
the fusion of combinatorial, numerical, and statistical thinking in network
analysis. I will illustrate the use of these techniques by a few basic
problems that are fundamental in network analysis, particularly for the
identification of significant nodes and coherent clusters/communities in
social and information networks. I also take this opportunity to discuss
some frameworks beyond graph-theoretical models for studying conceptual
questions to understand multifaceted network data that arise
in social influence, network dynamics, and Internet economics.<h3>Suggested Citation</h3>Shang-Hua Teng (2016), "Scalable Algorithms for Data and Network Analysis", Foundations and Trends® in Theoretical Computer Science: Vol. 12: No. 1–2, pp 1-274. http://dx.doi.org/10.1561/0400000051Mon, 30 May 2016 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-076Communication Complexity (for Algorithm Designers)<h3>Abstract</h3>This text collects the lecture notes from the author's course "Communication Complexity (for Algorithm Designers)," taught at Stanford in the winter quarter of 2015. The two primary goals of the text are:
(1) Learn several canonical problems in communication complexity that are useful for proving lower bounds for algorithms (disjointness, index, gap-hamming, etc.).
(2) Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.
Along the way, readers will also:
(3) Get exposure to lots of cool computational models and some famous results about them — data streams and linear sketches, compressive sensing, space-query time trade-offs in data structures, sublinear-time algorithms, and the extension
complexity of linear programs.
(4) Scratch the surface of techniques for proving communication complexity lower bounds (fooling sets, corruption arguments, etc.).<h3>Suggested Citation</h3>Tim Roughgarden (2016), "Communication Complexity (for Algorithm Designers)", Foundations and Trends® in Theoretical Computer Science: Vol. 11: No. 3–4, pp 217-404. http://dx.doi.org/10.1561/0400000076Wed, 11 May 2016 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-068Quantum Proofs<h3>Abstract</h3>Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA,
in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomial-time quantum computation. For some problems, the fact that a quantum proof state could be a superposition over
exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum
information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP* that represent natural quantum analogues of IP, SZK, and MIP. While
quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model.
In this survey we provide 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, we discuss non-interactive proofs
and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems
and the complexity classes QMIP, QMIP*, and MIP*.
<h3>Suggested Citation</h3>Thomas Vidick and John Watrous (2016), "Quantum Proofs", Foundations and Trends® in Theoretical Computer Science: Vol. 11: No. 1-2, pp 1-215. http://dx.doi.org/10.1561/0400000068Thu, 31 Mar 2016 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-074A Decade of Lattice Cryptography<h3>Abstract</h3>Lattice-based cryptography is the use of conjectured hard problems on point lattices in Rn as the foundation for secure cryptographic systems. Attractive features of lattice cryptography include apparent resistance to quantum attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under worst-case intractability assumptions, and solutions to long-standing open problems in cryptography. This work surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational short integer solution (SIS) and learning with errors (LWE) problems (and their more efficient ring-based variants), their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.<h3>Suggested Citation</h3>Chris Peikert (2016), "A Decade of Lattice Cryptography", Foundations and Trends® in Theoretical Computer Science: Vol. 10: No. 4, pp 283-424. http://dx.doi.org/10.1561/0400000074Thu, 24 Mar 2016 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-066Quantum Hamiltonian Complexity<h3>Abstract</h3>Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity,
which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a “Quantum Cook-Levin Theorem”
to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language
barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained
in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of
selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi’s polynomial time algorithm for Quantum 2-SAT.<h3>Suggested Citation</h3>Sevag Gharibian, Yichen Huang, Zeph Landau and Seung Woo Shin (2015), "Quantum Hamiltonian Complexity", Foundations and Trends® in Theoretical Computer Science: Vol. 10: No. 3, pp 159-282. http://dx.doi.org/10.1561/0400000066Tue, 13 Oct 2015 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-060Sketching as a Tool for Numerical Linear Algebra<h3>Abstract</h3>This survey 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 compresses it to a much smaller matrix
by multiplying it by a (usually) random matrix with certain properties.
Much of the expensive computation can then be performed on
the smaller matrix, thereby accelerating the solution for the original
problem. In this survey we consider least squares as well as robust regression
problems, low rank approximation, and graph sparsification.
We also discuss a number of variants of these problems. Finally, we
discuss the limitations of sketching methods.<h3>Suggested Citation</h3>David P. Woodruff (2014), "Sketching as a Tool for Numerical Linear Algebra", Foundations and Trends® in Theoretical Computer Science: Vol. 10: No. 1–2, pp 1-157. http://dx.doi.org/10.1561/0400000060Wed, 29 Oct 2014 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-042The Algorithmic Foundations of Differential Privacy<h3>Abstract</h3>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 mathematically rigorous definition of privacy, together with a computationally rich class of algorithms that satisfy this definition. Differential Privacy is such a definition.<p>After motivating and discussing the meaning of differential privacy, the preponderance of this monograph is devoted to fundamental techniques for achieving differential privacy, and application of these techniques in creative combinations, using the query-release problem as an ongoing example. A key point is that, by rethinking the computational goal, one can often obtain far better results than would be achieved by methodically replacing each step of a non-private computation with a differentially private implementation. Despite some astonishingly powerful computational results, there are still fundamental limitations — not just on what can be achieved with differential privacy but on what can be achieved with any method that protects against a complete breakdown in privacy. Virtually all the algorithms discussed herein maintain differential privacy against adversaries of arbitrary computational power. Certain algorithms are computationally intensive, others are efficient. Computational complexity for the adversary and the algorithm are both discussed.</p><p>We then turn from fundamentals to applications other than queryrelease, discussing differentially private methods for mechanism design and machine learning. The vast majority of the literature on differentially private algorithms considers a single, static, database that is subject to many analyses. Differential privacy in other models, including distributed databases and computations on data streams is discussed.</p><p>Finally, we note that this work is meant as a thorough introduction to the problems and techniques of differential privacy, but is not intended to be an exhaustive survey — there is by now a vast amount of work in differential privacy, and we can cover only a small portion of it.</p><h3>Suggested Citation</h3>Cynthia Dwork and Aaron Roth (2014), "The Algorithmic Foundations of Differential Privacy", Foundations and Trends® in Theoretical Computer Science: Vol. 9: No. 3–4, pp 211-407. http://dx.doi.org/10.1561/0400000042Mon, 11 Aug 2014 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-065Faster Algorithms via Approximation Theory<h3>Abstract</h3>
This monograph presents techniques to approximate real functions such as
<em>x</em><sup>
<em>s</em>
</sup>; <em>x</em><sup>–1</sup> and <em>e</em><sup>–</sup><sup>
<em>x</em>
</sup>
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 <em>A</em><sup>
<em>s</em>
</sup><em>v</em>;
<em>A</em><sup>–1</sup><em>v</em> and exp(–<em>A</em>)<em>v</em>, and
to compute matrix eigenvalues and eigenvectors. Indeed, many fast algorithms
reduce to the computation of such primitives, which have proved useful for
speeding up several fundamental computations such as random walk simulation,
graph partitioning and solving linear systems of equations.
<h3>Suggested Citation</h3>Sushant Sachdeva and Nisheeth K. Vishnoi (2014), "Faster Algorithms via Approximation Theory", Foundations and Trends® in Theoretical Computer Science: Vol. 9: No. 2, pp 125-210. http://dx.doi.org/10.1561/0400000065Fri, 28 Mar 2014 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-063Complexity of Linear Boolean Operators<h3>Abstract</h3>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 (the superconcentrator method). We provide a thorough survey of the research in this direction, and
prove some new results to fill out the picture. The focus is on the cases in which the addition operation is either the boolean OR or XOR,
but the model in which arbitrary boolean functions are allowed as gates is considered as well.<h3>Suggested Citation</h3>Stasys Jukna and Igor Sergeev (2013), "Complexity of Linear Boolean Operators", Foundations and Trends® in Theoretical Computer Science: Vol. 9: No. 1, pp 1-123. http://dx.doi.org/10.1561/0400000063Thu, 31 Oct 2013 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-057Online Matching and Ad Allocation<h3>Abstract</h3>Matching is a classic problem with a rich history and a significant impact, both on the theory of algorithms and in practice. Recently there has been a surge of interest in the online version of matching and its generalizations, due to the important new application domain of Internet advertising. The theory of online matching and allocation has played a critical role in designing algorithms for ad allocation. This monograph surveys the key problems, models and algorithms from online matchings, as well as their implication in the practice of ad allocation. The goal is to provide a classification of the problems in this area, an introduction into the techniques used, a glimpse into the practical impact, and to provide direction in terms of open questions. Matching continues to find core applications in diverse domains, and the advent of massive online and streaming data emphasizes the future applicability of the algorithms and techniques surveyed here.<h3>Suggested Citation</h3>Aranyak Mehta (2013), "Online Matching and Ad Allocation", Foundations and Trends® in Theoretical Computer Science: Vol. 8: No. 4, pp 265-368. http://dx.doi.org/10.1561/0400000057Thu, 17 Oct 2013 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-045Bayesian Mechanism Design<h3>Abstract</h3>Systems wherein strategic agents compete for limited resources are ubiquitous: the economy, computer networks, social networks, congestion networks, nature, etc. Assuming the agents' preferences are drawn from a distribution, which is a reasonable assumption for small mechanisms in a large system, <em>Bayesian mechanism design</em> governs the design and analysis of these systems.<p>This article 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. The mechanisms it predicts are often complex and overly dependent on details of the model. Approximation complements this theory and suggests that simple and less-detail-dependent mechanisms can be nearly optimal. Furthermore, techniques from approximation and algorithms can be used to describe good mechanisms beyond the single-dimensional, linear model of agent preferences.</p><h3>Suggested Citation</h3>Jason D. Hartline (2013), "Bayesian Mechanism Design", Foundations and Trends® in Theoretical Computer Science: Vol. 8: No. 3, pp 143-263. http://dx.doi.org/10.1561/0400000045Thu, 13 Jun 2013 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-054Lx = b<h3>Abstract</h3>The ability to solve a system of linear equations lies at the heart of areas such as optimization, scientific computing, and computer science, and has traditionally been a central topic of research in the area of numerical linear algebra. An important class of instances that arise in practice has the form <em>Lx</em> = b, where <em>L</em> is the Laplacian of an undirected graph. After decades of sustained research and combining tools from disparate areas, we now have Laplacian solvers that run in time nearly-linear in the sparsity (that is, the number of edges in the associated graph) of the system, which is a distant goal for general systems. Surprisingly, and perhaps not the original motivation behind this line of research, Laplacian solvers are impacting the theory of fast algorithms for fundamental graph problems. In this monograph, the emerging paradigm of employing Laplacian solvers to design novel fast algorithms for graph problems is illustrated through a small but carefully chosen set of examples. A part of this monograph is also dedicated to developing the ideas that go into the construction of near-linear-time Laplacian solvers. An understanding of these methods, which marry techniques from linear algebra and graph theory, will not only enrich the tool-set of an algorithm designer but will also provide the ability to adapt these methods to design fast algorithms for other fundamental problems.<h3>Suggested Citation</h3>Nisheeth K. Vishnoi (2013), "Lx = b", Foundations and Trends® in Theoretical Computer Science: Vol. 8: No. 1–2, pp 1-141. http://dx.doi.org/10.1561/0400000054Thu, 23 May 2013 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-055Evasiveness of Graph Properties and Topological Fixed-Point Theorems<h3>Abstract</h3>Many graph properties (e.g., connectedness, containing a complete subgraph) are known to be difficult to check. In a decision-tree model, the cost of an algorithm is measured by the number of edges in the graph that it queries. R. Karp conjectured in the early 1970s that all monotone graph properties are evasive—that is, any algorithm which computes a monotone graph property must check all edges in the worst case. This conjecture is unproven, but a lot of progress has been made. Starting with the work of Kahn, Saks, and Sturtevant in 1984, topological methods have been applied to prove partial results on the Karp conjecture. This text is a tutorial on these topological methods. I give a fully self-contained account of the central proofs from the paper of Kahn, Saks, and Sturtevant, with no prior knowledge of topology assumed. I also briefly survey some of the more recent results on evasiveness.<h3>Suggested Citation</h3>Carl A. Miller (2013), "Evasiveness of Graph Properties and Topological Fixed-Point Theorems", Foundations and Trends® in Theoretical Computer Science: Vol. 7: No. 4, pp 337-415. http://dx.doi.org/10.1561/0400000055Thu, 16 May 2013 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-010Pseudorandomness<h3>Abstract</h3>This is a survey of <em>pseudorandomness</em>, the theory of efficiently generating objects that "look random" despite being constructed using little or no randomness. This theory has significance for a number of areas in computer science and mathematics, including computational complexity, algorithms, cryptography, combinatorics, communications, and additive number theory. Our treatment places particular emphasis on the intimate connections that have been discovered between a variety of fundamental "pseudorandom objects" that at first seem very different in nature: expander graphs, randomness extractors, list-decodable error-correcting codes, samplers, and pseudorandom generators. The structure of the presentation is meant to be suitable for teaching in a graduate-level course, with exercises accompanying each section.<h3>Suggested Citation</h3>Salil P. Vadhan (2012), "Pseudorandomness", Foundations and Trends® in Theoretical Computer Science: Vol. 7: No. 1–3, pp 1-336. http://dx.doi.org/10.1561/0400000010Thu, 20 Dec 2012 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-056Incidence Theorems and Their Applications<h3>Abstract</h3>We survey recent (and not so recent) results concerning arrangements of lines, points, and other geometric objects and the applications these results have in theoretical computer science and combinatorics. The three main types of problems we will discuss are:<p>
<ol>
<li>
<strong>Counting incidences:</strong> Given a set (or several sets) of geometric objects (lines, points, etc.), what is the maximum number of incidences (or intersections) that can exist between elements in different sets? We will see several results of this type, such as the Szemeredi–Trotter theorem, over the reals and over finite fields and discuss their applications in combinatorics (e.g., in the recent solution of Guth and Katz to Erdos' distance problem) and in computer science (in explicit constructions of multisource extractors).</li>
<li>
<strong>Kakeya type problems:</strong> These problems deal with arrangements of lines that point in different directions. The goal is to try and understand to what extent these lines can overlap one another. We will discuss these questions both over the reals and over finite fields and see how they come up in the theory of randomness extractors.</li>
<li>
<strong>Sylvester–Gallai type problems:</strong> In this type of problems, one is presented with a configuration of points that contain many 'local' dependencies (e.g., three points on a line) and is asked to derive a bound on the dimension of the span of all points. We will discuss several recent results of this type, over various fields, and see their connection to the theory of locally correctable error-correcting codes.</li>
</ol>
</p><p>Throughout the different parts of the survey, two types of techniques will make frequent appearance. One is the polynomial method, which uses polynomial interpolation to impose an algebraic structure on the problem at hand. The other recurrent techniques will come from the area of additive combinatorics.</p><p>
<em>The author is supported under NSF grant CCF-1217416.</em>
</p><h3>Suggested Citation</h3>Zeev Dvir (2012), "Incidence Theorems and Their Applications", Foundations and Trends® in Theoretical Computer Science: Vol. 6: No. 4, pp 257-393. http://dx.doi.org/10.1561/0400000056Wed, 12 Dec 2012 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-030Locally Decodable Codes<h3>Abstract</h3>Locally decodable codes are a class of "error-correcting codes." Error-correcting codes help to ensure reliability when transmitting information over noisy channels. They allow a sender of a message to add redundancy to messages, encoding bit strings representing messages into longer bit strings called codewords, in a way that the message can still be recovered even if a certain fraction of the codeword bits are corrupted. Classical error-correcting codes however do not work well when one is working with massive messages, because their decoding time increases (at least) linearly with the length of the message. As a result in typical applications the message is first partitioned into small blocks, each of which is then encoded separately. Such encoding allows efficient random-access retrieval of the message, but yields poor noise resilience.<p>Locally decodable codes are codes intended to address this seeming conflict between efficient retrievability and reliability. They are codes that simultaneously provide efficient random-access retrieval and high noise resilience by allowing reliable reconstruction of an arbitrary bit of the message from looking at only a small number of randomly chosen codeword bits. This review introduces and motivates locally decodable codes, and discusses the central results of the subject. In particular, local decodability comes at the price of certain loss in terms of code efficiency, and this review describes the currently known limits on the efficiency that is achievable.</p><h3>Suggested Citation</h3>Sergey Yekhanin (2012), "Locally Decodable Codes", Foundations and Trends® in Theoretical Computer Science: Vol. 6: No. 3, pp 139-255. http://dx.doi.org/10.1561/0400000030Tue, 16 Oct 2012 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-043Partial Derivatives in Arithmetic Complexity and Beyond<h3>Abstract</h3>How complex is a given multivariate polynomial? The main point of this survey is that one can learn a great deal about the structure and complexity of polynomials by studying (some of) their partial derivatives. The bulk of the survey shows that partial derivatives provide essential ingredients in proving both upper and lower bounds for computing polynomials by a variety of natural arithmetic models. We will also see applications which go beyond computational complexity, where partial derivatives provide a wealth of structural information about polynomials (including their number of roots, reducibility and internal symmetries), and help us solve various number theoretic, geometric, and combinatorial problems.<h3>Suggested Citation</h3>Xi Chen, Neeraj Kayal and Avi Wigderson (2011), "Partial Derivatives in Arithmetic Complexity and Beyond", Foundations and Trends® in Theoretical Computer Science: Vol. 6: No. 1–2, pp 1-138. http://dx.doi.org/10.1561/0400000043Sat, 10 Sep 2011 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-039Arithmetic Circuits: A Survey of Recent Results and Open Questions<h3>Abstract</h3>A large class of problems in symbolic computation can be expressed as the task of computing some polynomials; and arithmetic circuits form the most standard model for studying the complexity of such computations. This algebraic model of computation attracted a large amount of research in the last five decades, partially due to its simplicity and elegance. Being a more structured model than Boolean circuits, one could hope that the fundamental problems of theoretical computer science, such as separating P from NP, will be easier to solve for arithmetic circuits. However, in spite of the appearing simplicity and the vast amount of mathematical tools available, no major breakthrough has been seen. In fact, all the fundamental questions are still open for this model as well. Nevertheless, there has been a lot of progress in the area and beautiful results have been found, some in the last few years. As examples we mention the connection between polynomial identity testing and lower bounds of Kabanets and Impagliazzo, the lower bounds of Raz for multilinear formulas, and two new approaches for proving lower bounds: Geometric Complexity Theory and Elusive Functions.<p>The goal of this monograph is to survey the field of arithmetic circuit complexity, focusing mainly on what we find to be the most interesting and accessible research directions. We aim to cover the main results and techniques, with an emphasis on works from the last two decades. In particular, we discuss the recent lower bounds for multilinear circuits and formulas, the advances in the question of deterministically checking polynomial identities, and the results regarding reconstruction of arithmetic circuits. We do, however, also cover part of the classical works on arithmetic circuits. In order to keep this monograph at a reasonable length, we do not give full proofs of most theorems, but rather try to convey the main ideas behind each proof and demonstrate it, where possible, by proving some special cases.</p><h3>Suggested Citation</h3>Amir Shpilka and Amir Yehudayoff (2010), "Arithmetic Circuits: A Survey of Recent Results and Open Questions", Foundations and Trends® in Theoretical Computer Science: Vol. 5: No. 3–4, pp 207-388. http://dx.doi.org/10.1561/0400000039Tue, 14 Dec 2010 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-029Algorithmic and Analysis Techniques in Property Testing<h3>Abstract</h3>Property testing algorithms are "ultra"-efficient algorithms that decide whether a given object (e.g., a graph) has a certain property (e.g., bipartiteness), or is significantly different from any object that has the property. To this end property testing algorithms are given the ability to perform (local) queries to the input, though the decision they need to make usually concerns properties with a global nature. 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.<p>In this monograph we survey results in property testing, where our emphasis is on common analysis and algorithmic techniques. Among the techniques surveyed are the following:
<ul><li>The <em>self-correcting</em> approach, which was mainly applied in the study of property testing of algebraic properties;</li><li>The <em>enforce-and-test</em> approach, which was applied quite extensively in the analysis of algorithms for testing graph properties (in the dense-graphs model), as well as in other contexts;</li><li>Szemerédi's <em>Regularity Lemma</em>, which plays a very important role in the analysis of algorithms for testing graph properties (in the dense-graphs model);</li><li>The approach of <em>Testing by implicit learning</em>, which implies efficient testability of membership in many functions classes; and</li><li>Algorithmic techniques for testing properties of sparse graphs, which include <em>local search</em> and <em>random walks</em>.</li></ul></p><h3>Suggested Citation</h3>Dana Ron (2010), "Algorithmic and Analysis Techniques in Property Testing", Foundations and Trends® in Theoretical Computer Science: Vol. 5: No. 2, pp 73-205. http://dx.doi.org/10.1561/0400000029Mon, 08 Feb 2010 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-033On the Power of Small-Depth Computation<h3>Abstract</h3>In this monograph we discuss selected topics on small-depth computation, presenting a few unpublished proofs along the way. The four sections contain:
<ol>
<li>(1) A unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0,1}.</li>
<li>(2) An unpublished proof that small bounded-depth circuits (AC<sup>0</sup>) have exponentially small correlation with the parity function. The proof is due to Klivans and Vadhan; it builds upon and simplifies previous ones.</li>
<li>(3) Valiant's simulation of log-depth linear-size circuits of fan-in 2 by sub-exponential size circuits of depth 3 and unbounded fan-in. To our knowledge, a proof of this result has never appeared in full.</li>
<li>(4) Applebaum, Ishai, and Kushilevitz's cryptography in bounded depth.</li>
</ol><h3>Suggested Citation</h3>Emanuele Viola (2009), "On the Power of Small-Depth Computation", Foundations and Trends® in Theoretical Computer Science: Vol. 5: No. 1, pp 1-72. http://dx.doi.org/10.1561/0400000033Tue, 24 Nov 2009 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-025Spectral Algorithms<h3>Abstract</h3>Spectral methods refer to the use of eigenvalues, eigenvectors, singular values, and singular vectors. They are widely used in Engineering, Applied Mathematics, and Statistics. More recently, spectral methods have found numerous applications in Computer Science to "discrete" as well as "continuous" problems. This monograph describes modern applications of spectral methods and novel algorithms for estimating spectral parameters. In the first part of the monograph, we present applications of spectral methods to problems from a variety of topics including combinatorial optimization, learning, and clustering. The second part of the monograph is motivated by efficiency considerations. A feature of many modern applications is the massive amount of input data. While sophisticated algorithms for matrix computations have been developed over a century, a more recent development is algorithms based on "sampling on the fly" from massive matrices. Good estimates of singular values and low-rank approximations of the whole matrix can be provably derived from a sample. Our main emphasis in the second part of the monograph is to present these sampling methods with rigorous error bounds. We also present recent extensions of spectral methods from matrices to tensors and their applications to some combinatorial optimization problems.<h3>Suggested Citation</h3>Ravindran Kannan and Santosh Vempala (2009), "Spectral Algorithms", Foundations and Trends® in Theoretical Computer Science: Vol. 4: No. 3–4, pp 157-288. http://dx.doi.org/10.1561/0400000025Tue, 20 Oct 2009 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-011Complexity Lower Bounds using Linear Algebra<h3>Abstract</h3>We survey 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. Suitably strong lower bounds on such robustness functions of explicit matrices lead to important consequences in the corresponding circuit or communication models. Many of the linear algebraic problems arising from these approaches are independently interesting mathematical challenges.<h3>Suggested Citation</h3>Satyanarayana V. Lokam (2009), "Complexity Lower Bounds using Linear Algebra", Foundations and Trends® in Theoretical Computer Science: Vol. 4: No. 1–2, pp 1-155. http://dx.doi.org/10.1561/0400000011Mon, 20 Jul 2009 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-040Lower Bounds in Communication Complexity<h3>Abstract</h3>The communication complexity of a function <em>f(x,y)</em> measures the number of bits that two players, one who knows <em>x</em> and the other who knows <em>y</em>, must exchange to determine the value <em>f(x,y)</em>. Communication complexity is a fundamental measure of complexity of functions. Lower bounds on this measure lead to lower bounds on many other measures of computational complexity. This monograph surveys lower bounds in the field of communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure, such as rank or trace norm, that serves as a lower bound to the underlying communication complexity measure. Lower bounds on this geometric complexity measure are then found using algebraic and geometric tools.<h3>Suggested Citation</h3>Troy Lee and Adi Shraibman (2009), "Lower Bounds in Communication Complexity", Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 4, pp 263-399. http://dx.doi.org/10.1561/0400000040Thu, 15 Oct 2009 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-024The Design of Competitive Online Algorithms via a Primal–Dual Approach<h3>Abstract</h3>The primal–dual method is a powerful algorithmic technique that has proved to be extremely useful for a wide variety of problems in the area of approximation algorithms for NP-hard problems. The method has its origins in the realm of exact algorithms, e.g., for matching and network flow. In the area of approximation algorithms, the primal–dual method has emerged as an important unifying design methodology, starting from the seminal work of Goemans and Williamson [60].<p>We show in this survey how to extend the primal–dual method to the setting of online algorithms, and show its applicability to a wide variety of fundamental problems. Among the online problems that we consider here are the weighted caching problem, generalized caching, the set-cover problem, several graph optimization problems, routing, load balancing, and the problem of allocating ad-auctions. We also show that classic online problems such as the ski rental problem and the dynamic TCP-acknowledgement problem can be solved optimally using a simple primal–dual approach.</p><p>The primal–dual method has several advantages over existing methods. First, it provides a general recipe for the design and analysis of online algorithms. The linear programming formulation helps detecting the difficulties of the online problem, and the analysis of the competitive ratio is direct, without a potential function appearing "out of nowhere." Finally, since the analysis is done via duality, the competitiveness of the online algorithm is with respect to an optimal fractional solution, which can be advantageous in certain scenarios.</p><h3>Suggested Citation</h3>Niv Buchbinder and Joseph (Seffi) Naor (2009), "The Design of Competitive Online Algorithms via a Primal–Dual Approach", Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 2–3, pp 93-263. http://dx.doi.org/10.1561/0400000024Fri, 15 May 2009 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-023Probabilistic Proof Systems: A Primer<h3>Abstract</h3>Various types of probabilistic proof systems have played a central role in the development of computer science in the last couple of decades. These proof systems deviate from the traditional concept of a proof by introducing randomization and interaction into the verification process. Probabilistic proof systems carry an error probability (which is explicitly bounded and can be decreased by repetitions), but they offer various advantages over deterministic proof systems.<p>This primer concentrates on three types of probabilistic proof systems: interactive proofs, zero-knowledge proofs, and Probabilistically Checkable Proofs (PCP). Surveying the basic results regarding these proof systems, we stress the essential role of randomness in each of them.</p><h3>Suggested Citation</h3>Oded Goldreich (2008), "Probabilistic Proof Systems: A Primer", Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 1, pp 1-91. http://dx.doi.org/10.1561/0400000023Fri, 08 Aug 2008 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-014Algorithms and Data Structures for External Memory<h3>Abstract</h3>Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottle-neck. In this manuscript, we survey the state of the art in the design and analysis of algorithms and data structures for <em>external memory</em> (or <em>EM</em> for short), where the goal is to exploit locality and parallelism in order to reduce the I/O costs. We consider a variety of EM paradigms for solving batched and online problems efficiently in external memory.<p>For the batched problem of sorting and related problems like permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss distribution and merging techniques for using the disks independently. We also consider useful techniques for batched EM problems involving matrices, geometric data, and graphs.</p><p>In the online domain, canonical EM applications include dictionary lookup and range searching. The two important classes of indexed data structures are based upon extendible hashing and B-trees. The paradigms of filtering and bootstrapping provide convenient means in online data structures to make effective use of the data accessed from disk. We also re-examine some of the above EM problems in slightly different settings, such as when the data items are moving, when the data items are variable-length such as character strings, when the data structure is compressed to save space, or when the allocated amount of internal memory can change dynamically.</p><p>Programming tools and environments are available for simplifying the EM programming task. We report on some experiments in the domain of spatial databases using the TPIE system (Transparent Parallel I/O programming Environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss are significantly faster than other methods used in practice.</p><h3>Suggested Citation</h3>Jeffrey Scott Vitter (2008), "Algorithms and Data Structures for External Memory", Foundations and Trends® in Theoretical Computer Science: Vol. 2: No. 4, pp 305-474. http://dx.doi.org/10.1561/0400000014Mon, 09 Jun 2008 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-012A Survey of Lower Bounds for Satisfiability and Related Problems<h3>Abstract</h3>Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a lineartime, logarithmic-space algorithm for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by Kannan, ruled out such an algorithm. Since then there has been a significant amount of progress giving non-trivial lower bounds on the computational complexity of satisfiability. In this article, we survey the known lower bounds for the time and space complexity of satisfiability and closely related problems on deterministic, randomized, and quantum models with random access. We discuss the state-of-the-art results and present the underlying arguments in a unified framework.<h3>Suggested Citation</h3>Dieter van Melkebeek (2007), "A Survey of Lower Bounds for Satisfiability and Related Problems", Foundations and Trends® in Theoretical Computer Science: Vol. 2: No. 3, pp 197-303. http://dx.doi.org/10.1561/0400000012Thu, 25 Oct 2007 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-007Algorithmic Results in List Decoding<h3>Abstract</h3>Error-correcting codes are used to cope with the corruption of data by noise during communication or storage. A code uses an encoding procedure that judiciously introduces redundancy into the data to produce an associated codeword. The redundancy built into the codewords enables one to decode the original data even from a somewhat distorted version of the codeword. The central trade-off in coding theory is the one between the data rate (amount of non-redundant information per bit of codeword) and the error rate (the fraction of symbols that could be corrupted while still enabling data recovery). The traditional decoding algorithms did as badly at correcting any error pattern as they would do for the worst possible error pattern. This severely limited the maximum fraction of errors those algorithms could tolerate. In turn, this was the source of a big hiatus between the error-correction performance known for probabilistic noise models (pioneered by Shannon) and what was thought to be the limit for the more powerful, worst-case noise models (suggested by Hamming).<p>In the last decade or so, there has been much algorithmic progress in coding theory that has bridged this gap (and in fact nearly eliminated it for codes over large alphabets). These developments rely on an error-recovery model called "list decoding," wherein for the pathological error patterns, the decoder is permitted to output a small list of candidates that will include the original message. This book 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."</p><h3>Suggested Citation</h3>Venkatesan Guruswami (2007), "Algorithmic Results in List Decoding", Foundations and Trends® in Theoretical Computer Science: Vol. 2: No. 2, pp 107-195. http://dx.doi.org/10.1561/0400000007Mon, 29 Jan 2007 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-004Average-Case Complexity<h3>Abstract</h3>We survey the average-case complexity of problems in NP.<p>We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but some-what artificial) NP problem is easy-on-average with respect to the uniform distribution, then all problems in NP are easy-on-average with respect to all samplable distributions. Applying the theory to natural distributional problems remain an outstanding open question. We review some natural distributional problems whose average-case complexity is of particular interest and that do not yet fit into this theory.</p><p>A major open question is whether the existence of hard-on-average problems in NP can be based on the P ≠ NP assumption or on related worst-case assumptions. We review negative results showing that certain proof techniques cannot prove such a result. While the relation between worst-case and average-case complexity for general NP problems remains open, there has been progress in understanding the relation between different "degrees" of average-case complexity. We discuss some of these "hardness amplification" results.</p><h3>Suggested Citation</h3>Andrej Bogdanov and Luca Trevisan (2006), "Average-Case Complexity", Foundations and Trends® in Theoretical Computer Science: Vol. 2: No. 1, pp 1-106. http://dx.doi.org/10.1561/0400000004Tue, 19 Dec 2006 00:00:00 +0100http://www.nowpublishers.com/article/Details/TCS-009Pairwise Independence and Derandomization<h3>Abstract</h3>This article gives several applications of the following paradigm, which has proven extremely powerful in algorithm design and computational complexity. First, design a probabilistic algorithm for a given problem. Then, show that the correctness analysis of the algorithm remains valid even when the random strings used by the algorithm do not come from the uniform distribution, but rather from a small sample space, appropriately chosen. In some cases this can be proven directly (giving "unconditional derandomization"), and in others it uses computational assumptions, like the existence of 1-way functions (giving "conditional derandomization").<p>The article is based on a series of lectures given by the authors in 1995, where the notes were scribed by the attending students. (The detailed list of scribes and other contributors can be found in the Acknowledgements section at the end of the manuscript.) The current version is essentially the same, with a few minor changes. We note that this publication takes place a decade after the lectures were given. Much has happened in the area of pseudorandomness and derandomization since, and perhaps a somewhat different viewpoint, different material, and different style would be chosen were these lectures given today. Still, the material presented is self contained, and is a prime manifestation of the "derandomization" paradigm. The material does lack references to newer work though. We recommend the reader interested in randomness, derandomization and their interplay with computational complexity to consult the following books and surveys, as well as their extensive bibliography: [31, 14, 36, 37, 21, 42].</p><h3>Suggested Citation</h3>Michael Luby and Avi Wigderson (2006), "Pairwise Independence and Derandomization", Foundations and Trends® in Theoretical Computer Science: Vol. 1: No. 4, pp 237-301. http://dx.doi.org/10.1561/0400000009Tue, 22 Aug 2006 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-003Mathematical Aspects of Mixing Times in Markov Chains<h3>Abstract</h3>In the past few years we have seen a surge in the theory of finite Markov chains, by way of new techniques to bounding the convergence to stationarity. This includes functional techniques such as logarithmic Sobolev and Nash inequalities, refined spectral and entropy techniques, and isoperimetric techniques such as the average and blocking conductance and the evolving set methodology. We attempt to give a more or less self-contained treatment of some of these modern techniques, after reviewing several preliminaries. We also review classical and modern lower bounds on mixing times. There have been other important contributions to this theory such as variants on coupling techniques and decomposition methods, which are not included here; our choice was to keep the analytical methods as the theme of this presentation. We illustrate the strength of the main techniques by way of simple examples, a recent result on the Pollard Rho random walk to compute the discrete logarithm, as well as with an improved analysis of the Thorp shuffle.<h3>Suggested Citation</h3>Ravi Montenegro and Prasad Tetali (2006), "Mathematical Aspects of Mixing Times in Markov Chains", Foundations and Trends® in Theoretical Computer Science: Vol. 1: No. 3, pp 237-354. http://dx.doi.org/10.1561/0400000003Fri, 07 Jul 2006 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-002Data Streams: Algorithms and Applications<h3>Abstract</h3>In the data stream scenario, input arrives very rapidly and there is limited memory to store the input. Algorithms have to work with one or few passes over the data, space less than linear in the input size or time significantly less than the input size. In the past few years, a new theory has emerged for reasoning about algorithms that work within these constraints on space, time, and number of passes. Some of the methods rely on metric embeddings, pseudo-random computations, sparse approximation theory and communication complexity. The applications for this scenario include IP network traffic analysis, mining text message streams and processing massive data sets in general. Researchers in Theoretical Computer Science, Databases, IP Networking and Computer Systems are working on the data stream challenges. This article is an overview and survey of data stream algorithmics and is an updated version of [175].<h3>Suggested Citation</h3>S. Muthukrishnan (2005), "Data Streams: Algorithms and Applications", Foundations and Trends® in Theoretical Computer Science: Vol. 1: No. 2, pp 117-236. http://dx.doi.org/10.1561/0400000002Tue, 27 Sep 2005 00:00:00 +0200http://www.nowpublishers.com/article/Details/TCS-001Foundations of Cryptography – A Primer<h3>Abstract</h3>Revolutionary developments which took place in the 1980's have transformed cryptography from a semi-scientific discipline to a respectable field in theoretical Computer Science. In particular, concepts such as computational indistinguishability, pseudorandomness and zero-knowledge interactive proofs were introduced and classical notions as secure encryption and unforgeable signatures were placed on sound grounds. The resulting field of cryptography, reviewed in this survey, is strongly linked to complexity theory (in contrast to "classical" cryptography which is strongly related to information theory).<h3>Suggested Citation</h3>Oded Goldreich (2005), "Foundations of Cryptography – A Primer", Foundations and Trends® in Theoretical Computer Science: Vol. 1: No. 1, pp 1-116. http://dx.doi.org/10.1561/0400000001Fri, 01 Apr 2005 00:00:00 +0200