This thesis studies some combinatorial, topological and linear algebraic parameters associated with Boolean and Arithmetic circuits. It is mainly divided into two parts.
The first part describes a study of combinations of graph-theoretic or circuit-theoretic restrictions that we can impose on Boolean circuits to obtain complexity-theoretic characterisations for the circuit value problem (CVP). We first address the question of evaluating monotone planar circuits (MPCVP). Using recent insights developed in the context of topological constraints in small-width circuits, we - in this thesis - review the developments leading up to and beyond the ``MPCVP is in NC'' result, and make some improvements on the known bounds for general MPCVP as well as some special cases. Our main improvements are obtained while considering circuits with cylindrical embeddings. Another contribution is that we are able to extend the $\NC$ upper bound on MPCVP to toroidal (genus one) monotone circuits.
Exploring how topological restrictions interfere with those in circuit theoretic parameters, we show that unless P=NC in the non-uniform setting, there are P-computable functions requiring super-polylogarithmic number of negation gates in any poly-sized planar circuit computing them. In order to achieve this we prove that any circuit C with poly-logarithmic number of negation gates can be evaluated in NC. In a similar spirit, we prove an NC upper bound for evaluating a circuit which has poly-logarithmic crossing height when presented along with an embedding which achieves this crossing height. Combining these results, we show that any circuit C which has at most polylog crossing number and use polylog number of negations can be evaluated in NC when presented with along with an embedding which achieves this crossing height.
Motivated by applications in circuit complexity bounds, in the second part of the thesis we study the complexity of some linear algebraic parameters associated with the circuits. We first explore the circuit and computational complexity of matrix rank. This problem, in general is known to characterise a complexity class inside $\P$. We study several restricted cases of the problem to obtain algebraic characterisations of the complexity classes. For instance we prove that computing the rank, over $Q$, of matrices that are symmetric, non-negative and diagonally dominant, exactly characterises deterministic log-space computation by Turing machines.
We next turn to optimisation problems associated with matrix rank. and briefly survey the applications of these problems in proving lower bounds in circuit complexity theory. Motivated by these applications we study the complexity of computing the rigidity of a matrix : the minimum number of entries of the matrix that need to be changed in order to bring down the rank below a given value. We consider several variants of the problem, and characterise them in terms of complexity classes. In particular, we prove complexity theoretic characterisations for the problem when restricted to 0-1 matrices, and k is bounded by a constant. We also note that, in general, over F_2, approximating the minimum number of changes needed up to a constant factor is NP-hard. We then consider the bounded norm variant of the problem, where changed matrix entries can differ from the original entries by at most a pre-specified amount. We note that it is NP-hard to compute this too.
We next attempt to construct explicit matrices which have super-linear rigidity. In this setting, we formulate the problem using the language of algebraic geometry, and prove tight maximal bounds for a specific family of matrices over $\C$. We then study continuity properties of matrix rigidity function, and prove that rigidity function is not semi-conituous in general, but for some special families of matrices, there is semi-continuity property. In the setting of the lower bounds, we apply and extend some known combintorial techniques to show almost optimal lower and upper bounds that for rigidity of a restricted triangular matrices.
Table of Contents:
1 Introduction
Part - I : Topological Constraints in Boolean Circuits
2 Monotone Planar Circuit Value Problem
2.1 Introduction
2.2 Basic definitions
2.2.1 Circuits
2.2.2 Topological Embeddings and Drawings
2.2.3 Representing embeddings
2.3 Graphs on cylinders
2.4 Circuits on cylinders
2.5 Improved Upper bounds for MPCVP
2.6 Discussion
3 Extensions of Topological restrictions to other parameters
3.1 Monotone Circuits on the Torus
3.2 Monotone Multi-cylindrical circuits
3.3 Circuits with Limited Negations
3.4 Circuits with Limited Crossing Number
4 On the Thickness of Branching Programs
4.1 Preliminaries
4.2 Thickness of Branching Programs
4.2.1 Thickness characterisation of NC1 and L
4.2.2 Page Characterisation of NC1 and L
4.2.3 Book-thickness characterisation of NC1 and L
Part - II : Linear Algebraic Concepts Related to Circuit Complexity 56
5 Circuit Complexity of Matrix Rank
5.1 Basic Definitions
5.2 Rank Computation for Diagonally Dominant Matrices
5.3 Determinant Computation of Special Matrices
6 Optimising Matrix rank
6.1 Basic Definitions and Properties
6.2 Matrix Rigidity
6.3 Applications to Lower bounds
6.4 Previous Attempts on Lower Bounds
6.5 An Almost Tight Bound for the Full 1s ELT Matrix
7 Lower bounds for Matrix Rigidity
7.1 Introduction
7.2 Notations & Background
7.2.1 Elimination Theory: Closure Theorem
7.3 Use of Elimination Theory
7.3.1 Determinantal Ideals and their Elimination Ideals
7.3.2 Valiants Theorem
7.3.3 Rigid Matrices over C
7.4 Reduction to Determinantal Ideals
7.5 Semi-continuity of Rigidity
7.6 Conclusions and Open Questions
8 Complexity of Computing Matrix Rigidity
8.1 Introduction
8.2 Basic complexity results in rigidity
8.2.1 Some Basic Approaches
8.2.2 Connection with Matrix Completion Problems
8.2.3 Characterisations when k is a constant
8.2.4 Inapproximability results on Rigidity
8.2.5 A Maximisation Version of Rigidity
8.3 Computing Bounded Rigidity
Appendix A : Complexity Theory Preliminaries 128
Appendix B : Algebraic Geometry Preliminaries 132
Appendix C : Algebraic Number Theory Preliminaries 137
Number of pages: 167