Complexity Lower Bounds Using Linear Algebra PDF Download

Author: Satyanarayana V. Lokam
Publisher: Now Publishers Inc
ISBN: 1601982429
Category : Computers
Languages : en
Pages : 177

View

Book Description
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.

Author: Troy Lee
Publisher: Now Publishers Inc
ISBN: 1601982585
Category : Computers
Languages : en
Pages : 152

View

Book Description
The communication complexity of a function f(x, y) measures the number of bits that two players, one who knows x and the other who knows y, must exchange to determine the value f(x, y). 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.

Author: Sivaramakrishnan Natarajan Ramamoorthy
Publisher:
ISBN:
Category : Algebra
Languages : en
Pages : 133

View

Book Description
In this thesis, we study basic lower bound questions in communication complexity, data structures and depth-2 threshold circuits, and prove lower bounds in these models by devising new techniques in information theory, algebra and combinatorics. Communication Complexity: A central open problem in communication complexity is to determine whether the messages exchanged by two parties can be compressed if we know that the amount of information revealed by the parties about their inputs is small. We consider the compression question when the information revealed by one of the parties is much less than the information revealed by the other. In this setting, we prove two new improved compression schemes. Data Structures: Our contribution to data structure lower bounds is threefold: (a) Consider the Vector-Matrix-Vector problem, in which the data structure stores a \sqrt{n} \times \sqrt{n} bit matrix and provides an algorithm to compute uMv (mod 2) for \sqrt{n}-bit vectors u, v. We prove new static data structure lower bounds for this problem, which improve upon the previous work of Chattopadhyay, Kouck\'{y}, Loff, and Mukhopadhyay by a factor of log n. Our proof uses a new technique by combining the discrepancy method from communication complexity with a modification of cell sampling. This technique turns out to be more general, and can be used to prove strong lower bounds for data structures that err and have a binary query output. (b) We show new connections between systematic linear data structures, linear data structures and matrix rigidity. Specifically, we prove the equivalence between systematic linear data structures and set rigidity, a relaxation of matrix rigidity that was defined by Alon, Panigrahy and Yekhanin. This equivalence not only sheds light on the difficulty of proving strong lower bounds against data structures but also suggests candidate rigid sets from data structures. We also use this equivalence to relate linear data structures and rigidity. (c) We study data structures that maintain a set from {1,2,...,n}, allow insertion of new elements and report the median, minimum or predecessors of the set. In particular, we prove that if one of the operations of the data structure is non-adaptive and each cell in memory stores O(log n) bits, then some operation must take time Omega(log n/ log log n). This bound nearly matches the guarantees of binary search trees, whose insertions and predecessor operations can be made non-adaptive. Our lower bounds are obtained via the sunflower lemma from combinatorics. Balancing Sets and Depth-2 Threshold Circuits: Majority and threshold circuits are important sub-classes of Boolean circuits. Kulikov and Podoslkii asked the question of finding the minimum fan-in required to compute the majority of n-bits using a depth-2 majority circuit. We identify a connection between this circuit question and Galvin's balancing sets problem from combinatorics, a well studied discrepancy-type question that was initiated by the work of Frankl and R{\"o}dl. We use this finding to prove tight bounds for both the circuit question and Galvin's problem. The proofs use polynomials over finite fields.In this thesis, we study basic lower bound questions in communication complexity, data structures and depth-2 threshold circuits, and prove lower bounds in these models by devising new techniques in information theory, algebra and combinatorics. Communication Complexity: A central open problem in communication complexity is to determine whether the messages exchanged by two parties can be compressed if we know that the amount of information revealed by the parties about their inputs is small. We consider the compression question when the information revealed by one of the parties is much less than the information revealed by the other. In this setting, we prove two new improved compression schemes. Data Structures: Our contribution to data structure lower bounds is threefold: (a) Consider the Vector-Matrix-Vector problem, in which the data structure stores a \sqrt{n} \times \sqrt{n} bit matrix and provides an algorithm to compute uMv (mod 2) for \sqrt{n}-bit vectors u, v. We prove new static data structure lower bounds for this problem, which improve upon the previous work of Chattopadhyay, Kouck\'{y}, Loff, and Mukhopadhyay by a factor of log n. Our proof uses a new technique by combining the discrepancy method from communication complexity with a modification of cell sampling. This technique turns out to be more general, and can be used to prove strong lower bounds for data structures that err and have a binary query output. (b) We show new connections between systematic linear data structures, linear data structures and matrix rigidity. Specifically, we prove the equivalence between systematic linear data structures and set rigidity, a relaxation of matrix rigidity that was defined by Alon, Panigrahy and Yekhanin. This equivalence not only sheds light on the difficulty of proving strong lower bounds against data structures but also suggests candidate rigid sets from data structures. We also use this equivalence to relate linear data structures and rigidity. (c) We study data structures that maintain a set from {1,2,...,n}, allow insertion of new elements and report the median, minimum or predecessors of the set. In particular, we prove that if one of the operations of the data structure is non-adaptive and each cell in memory stores O(log n) bits, then some operation must take time Omega(log n/ log log n). This bound nearly matches the guarantees of binary search trees, whose insertions and predecessor operations can be made non-adaptive. Our lower bounds are obtained via the sunflower lemma from combinatorics. Balancing Sets and Depth-2 Threshold Circuits: Majority and threshold circuits are important sub-classes of Boolean circuits. Kulikov and Podoslkii asked the question of finding the minimum fan-in required to compute the majority of n-bits using a depth-2 majority circuit. We identify a connection between this circuit question and Galvin's balancing sets problem from combinatorics, a well studied discrepancy-type question that was initiated by the work of Frankl and R{\"o}dl. We use this finding to prove tight bounds for both the circuit question and Galvin's problem. The proofs use polynomials over finite fields.

Author: Peter Bürgisser
Publisher: Springer Science & Business Media
ISBN: 3662033380
Category : Mathematics
Languages : en
Pages : 630

View

Book Description
The algorithmic solution of problems has always been one of the major concerns of mathematics. For a long time such solutions were based on an intuitive notion of algorithm. It is only in this century that metamathematical problems have led to the intensive search for a precise and sufficiently general formalization of the notions of computability and algorithm. In the 1930s, a number of quite different concepts for this purpose were pro posed, such as Turing machines, WHILE-programs, recursive functions, Markov algorithms, and Thue systems. All these concepts turned out to be equivalent, a fact summarized in Church's thesis, which says that the resulting definitions form an adequate formalization of the intuitive notion of computability. This had and continues to have an enormous effect. First of all, with these notions it has been possible to prove that various problems are algorithmically unsolvable. Among of group these undecidable problems are the halting problem, the word problem theory, the Post correspondence problem, and Hilbert's tenth problem. Secondly, concepts like Turing machines and WHILE-programs had a strong influence on the development of the first computers and programming languages. In the era of digital computers, the question of finding efficient solutions to algorithmically solvable problems has become increasingly important. In addition, the fact that some problems can be solved very efficiently, while others seem to defy all attempts to find an efficient solution, has called for a deeper under standing of the intrinsic computational difficulty of problems.

Author: J. M. Landsberg
Publisher: Cambridge University Press
ISBN: 110819141X
Category : Computers
Languages : en
Pages : 353

View

Book Description
Two central problems in computer science are P vs NP and the complexity of matrix multiplication. The first is also a leading candidate for the greatest unsolved problem in mathematics. The second is of enormous practical and theoretical importance. Algebraic geometry and representation theory provide fertile ground for advancing work on these problems and others in complexity. This introduction to algebraic complexity theory for graduate students and researchers in computer science and mathematics features concrete examples that demonstrate the application of geometric techniques to real world problems. Written by a noted expert in the field, it offers numerous open questions to motivate future research. Complexity theory has rejuvenated classical geometric questions and brought different areas of mathematics together in new ways. This book will show the beautiful, interesting, and important questions that have arisen as a result.

Author: J. M. Landsberg
Publisher: Cambridge University Press
ISBN: 1107199239
Category : Computers
Languages : en
Pages : 353

View

Book Description
This comprehensive introduction to algebraic complexity theory presents new techniques for analyzing P vs NP and matrix multiplication.

Author: Joshua H. Alman
Publisher:
ISBN:
Category :
Languages : en
Pages : 224

View

Book Description
We develop linear algebraic techniques in algorithms and complexity, and apply them to a variety of different problems. We focus in particular on matrix multiplication algorithms, which have surprisingly fast running times and can hence be used to design fast algorithms in many settings, and matrix rank methods, which can be used to design algorithms or prove lower bounds by analyzing the ranks of matrices corresponding to computational tasks. First, we study the design of matrix multiplication algorithms. We define a new general method, called the Universal Method, which subsumes all the known approaches to designing these algorithms. We then design a suite of techniques for proving lower bounds on the running times which can be achieved by algorithms using many tensors and the Universal Method. Our main limitation result is that a large class of tensors generalizing the Coppersmith-Winograd tensors (the family of tensors used in all record-holding algorithms for the past 30+ years) cannot achieve a better running time for multiplying n by n matrices than O(n2[superscript .]168). Second, we design faster algorithms for batch nearest neighbor search, the problem where one is given sets of data points and query points, and one wants to find the most similar data point to each query point, according to some distance measure. We give the first subquadratic time algorithm for the exact problem in high dimensions, and the fastest known algorithm for the approximate problem, for various distance measures including Hamming and Euclidean distance. Our algorithms make use of new probabilistic polynomial constructions to reduce the problem to the multiplication of low-rank matrices. Third, we study rigid matrices, which cannot be written as the sum of a low rank matrix and a sparse matrix. Finding explicit rigid matrices is an important open problem in complexity theory with applications in many different areas. We show that the Walsh-Hadamard transform, previously a leading candidate rigid matrix, is in fact not rigid. We also give the first nontrivial construction of rigid matrices in a certain parameter regime with applications to communication complexity, using an efficient algorithm with access to an NP oracle.

Author: Leslie Hogben
Publisher: CRC Press
ISBN: 1466507292
Category : Mathematics
Languages : en
Pages : 1838

View

Book Description
With a substantial amount of new material, the Handbook of Linear Algebra, Second Edition provides comprehensive coverage of linear algebra concepts, applications, and computational software packages in an easy-to-use format. It guides you from the very elementary aspects of the subject to the frontiers of current research. Along with revisions and

Author: Stasys Jukna
Publisher: Springer Science & Business Media
ISBN: 3642245080
Category : Mathematics
Languages : en
Pages : 618

View

Book Description
Boolean circuit complexity is the combinatorics of computer science and involves many intriguing problems that are easy to state and explain, even for the layman. This book is a comprehensive description of basic lower bound arguments, covering many of the gems of this “complexity Waterloo” that have been discovered over the past several decades, right up to results from the last year or two. Many open problems, marked as Research Problems, are mentioned along the way. The problems are mainly of combinatorial flavor but their solutions could have great consequences in circuit complexity and computer science. The book will be of interest to graduate students and researchers in the fields of computer science and discrete mathematics.

Author: Oded Goldreich
Publisher: Springer Nature
ISBN: 3030436624
Category : Computers
Languages : en
Pages : 391

View

Book Description
This volume contains a collection of studies in the areas of complexity theory and property testing. The 21 pieces of scientific work included were conducted at different times, mostly during the last decade. Although most of these works have been cited in the literature, none of them was formally published before. Within complexity theory the topics include constant-depth Boolean circuits, explicit construction of expander graphs, interactive proof systems, monotone formulae for majority, probabilistically checkable proofs (PCPs), pseudorandomness, worst-case to average-case reductions, and zero-knowledge proofs. Within property testing the topics include distribution testing, linearity testing, lower bounds on the query complexity (of property testing), testing graph properties, and tolerant testing. A common theme in this collection is the interplay between randomness and computation.