Lower Bounds in Computational Complexity from Information Theory, Algebra and Combinatorics PDF Download

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

Get Book

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.