Browsing by Subject "Communication complexity"

Now showing 1 - 2 of 2

Lower bounds in communication complexity and learning theory via analytic methods
(2009-08) Sherstov, Alexander Alexandrovich; Klivans, Adam R.
A central goal of theoretical computer science is to characterize the limits of efficient computation in a variety of models. We pursue this research objective in the contexts of communication complexity and computational learning theory. In the former case, one seeks to understand which distributed computations require a significant amount of communication among the parties involved. In the latter case, one aims to rigorously explain why computers cannot master some prediction tasks or learn from past experience. While communication and learning may seem to have little in common, they turn out to be closely related, and much insight into both can be gained by studying them jointly. Such is the approach pursued in this thesis. We answer several fundamental questions in communication complexity and learning theory and in so doing discover new relations between the two topics. A consistent theme in our work is the use of analytic methods to solve the problems at hand, such as approximation theory, Fourier analysis, matrix analysis, and duality. We contribute a novel technique, the pattern matrix method, for proving lower bounds on communication. Using our method, we solve an open problem due to Krause and Pudlák (1997) on the comparative power of two well-studied circuit classes: majority circuits and constant-depth AND/OR/NOT circuits. Next, we prove that the pattern matrix method applies not only to classical communication but also to the more powerful quantum model. In particular, we contribute lower bounds for a new class of quantum communication problems, broadly subsuming the celebrated work by Razborov (2002) who used different techniques. In addition, our method has enabled considerable progress by a number of researchers in the area of multiparty communication. Second, we study unbounded-error communication, a natural model with applications to matrix analysis, circuit complexity, and learning. We obtain essentially optimal lower bounds for all symmetric functions, giving the first strong results for unbounded-error communication in years. Next, we resolve a longstanding open problem due to Babai, Frankl, and Simon (1986) on the comparative power of unbounded-error communication and alternation, showing that [mathematical equation]. The latter result also yields an unconditional, exponential lower bound for learning DNF formulas by a large class of algorithms, which explains why this central problem in computational learning theory remains open after more than 20 years of research. We establish the computational intractability of learning intersections of halfspaces, a major unresolved challenge in computational learning theory. Specifically, we obtain the first exponential, near-optimal lower bounds for the learning complexity of this problem in Kearns’ statistical query model, Valiant’s PAC model (under standard cryptographic assumptions), and various analytic models. We also prove that the intersection of even two halfspaces on {0,1}n cannot be sign-represented by a polynomial of degree less than [Theta](square root of n), which is an exponential improvement on previous lower bounds and solves an open problem due to Klivans (2002). We fully determine the relations and gaps among three key complexity measures of a communication problem: product discrepancy, sign-rank, and discrepancy. As an application, we solve an open problem due to Kushilevitz and Nisan (1997) on distributional complexity under product versus nonproduct distributions, as well as separate the communication classes PPcc and UPPcc due to Babai, Frankl, and Simon (1986). We give interpretations of our results in purely learning-theoretic terms.
Models of streaming computation
(2021-08-13) Kallaugher, John M.; Price, Eric, Ph. D.; Aaronson, Scott; Zuckerman, David; Kapralov, Michael
Streaming algorithms, which process very large datasets received one update at a time, are a key tool in large-scale computing. This thesis studies the theory of streaming algorithms, and in particular the implications of how we model streaming algorithms. In constructing such a model, two questions arise: • What kinds of stream must the algorithm handle? • What is the algorithm allowed to do? We describe new streaming algorithms and prove new lower bounds in various streaming models, illustrating how the answers to these questions change which kinds of streaming problem are tractable. These include: • New algorithms for counting triangles in the insertion-only and linear sketching models, along with tight (up to log factors) lower bounds. • A quantum streaming algorithm for counting triangles, giving the first quantum advantage for a natural one-pass streaming problem. • A complete characterization of the linear sketching complexity of subgraph counting problems in constant-degree graphs. • An exponential separation between linear sketching and turnstile streaming under natural restrictions on the stream, complementing a prior series of work [Gan08, LNW14, AHLW16] that establishes equivalences between these models in the absence of such restrictions. • A new model of random-order streaming in which some correlations are allowed between edge arrival times, along with tight (up to polylog factors) upper and lower bounds for the problem of finding components in this model. A common theme in many of these results is the connection between sampling algorithms and lower bounds derived from the techniques of Boolean Fourier analysis. We give new methods for extending these techniques to settings such as linear sketching and random-order streaming.