A sign pattern matrix is a matrix whose entries are from the set {+,-,0}. The minimum rank of a sign pattern matrix A is the minimum of the rank of the real matrices whose entries have signs equal to the corresponding entries of A. It is conjectured that the minimum rank of every sign pattern matrix can be realized by a rational matrix. The equivalence of this conjecture to several seemingly unrelated statements are established. For some special cases, such as when A is entrywise nonzero, or the minimum rank of A is at most 2, or the minimum rank of A is at least n - 1,(where A is mxn), the conjecture is shown to hold.Connections between this conjecture and the existence of positive rational solutions of certain systems of homogeneous quadratic polynomial equations with each coefficient equal to either -1 or 1 are explored. Sign patterns that almost require unique rank are also investigated.

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. / text

Clustering techniques play an important role in exploratory pattern analysis, unsupervised pattern recognition and image segmentation applications. Clustering algorithms are computationally intensive in nature. This thesis proposes new parallel algorithms for Single Link and Complete Link hierarchical clustering. The parallel algorithms have been mapped on a SIMD machine model with a linear interconnection network. The model consists of a linear array of N (number of patterns to be clustered) processing elements (PEs), interfaced to a host machine and the interconnection network provides inter-PE and PE-to-host/host-to-PE communication. For single link clustering, each PE maintains a sorted list of its first logN nearest neighbors and the host maintains a heap of the root elements of all the PEs. The determination of the smallest entry in the distance matrix and update of the distance matrix is achieved in O(logN) time. In the case of complete link clustering, each PE maintains a heap data structure of the inter pattern distances. This significantly reduces the computation time for the determination of the smallest entry in the distance matrix during each iteration, from O(N2) to O(N), as the root element in each PE gives its nearest neighbor. The proposed algorithms are faster and simpler than previously known algorithms for hierarchical clustering. For clustering a data set with N patterns, using N PEs, the computation time for the single link clustering algorithm is shown to be O(NlogN) and the time complexity for the complete link clustering algorithm is shown to be O(N2). The parallel algorithms have been verified through simulations on the Intel iPSC/2 parallel machine.

An n × n sign pattern A is potentially stable (PS) if there exists a real matrix A having the sign pattern A and with all its eigenvalues having negative real parts. The identification of non-trivial necessary and sufficient conditions for potential stability remains a long standing open problem. Here we review some of the previous results and give simplified proofs for some of these results. Three techniques are given for the construction of larger order PS sign patterns from given PS sign patterns. These techniques are: construction of a sign pattern that allows a nested sequence of properly signed principal minors (a nest), bordering of a PS sign pattern with additional rows and columns, and use of a similarity transformation of a matrix that is reducible with two diagonal blocks (one of which is a stable matrix and the other a negative scalar). The minimum number of nonzero entries in an irreducible minimally PS sign pattern is determined for n = 2, . . . , 6 and for an arbitrary sign pattern that allows a nest. We also determine lower bounds for the number of nonzero entries in irreducible minimally PS sign patterns having certain sign patterns for their diagonal entries. For irreducible PS sign patterns of order at least four, a bordering construction leads to a new upper bound for the minimum number of nonzero entries.

A sign pattern matrix is a matrix whose entries are from the set {+,-, 0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive respectively, negative, zero) entry of B by + (respectively, -, 0). For a sign pattern matrixA, the sign pattern class of A, denoted Q(A), is defined as { B : sgn(B)= A }. The minimum rank mr(A)(maximum rank MR(A)) of a sign pattern matrix A is the minimum (maximum) of the ranks of the real matrices in Q(A). Several results concerning sign patterns A that require almost unique rank, that is to say, the sign patterns A such that MR(A)= mr(A)+1 are established. In particular, a complete characterization of these sign patterns is obtained. Further, the results on sign patterns that require almost unique rank are extended to sign patterns A for which the spread is d =MR(A)-mr(A).

A sign pattern(matrix) is a matrix whose entries are from the set {+,-,0}. An n x n sign pattern matrix is a spectrally arbitrary pattern(SAP) if for every monic real polynomial p(x) of degree n, there exists a real matrix B whose entries agree in sign with A such that the characteristic polynomial of B is p(x). An n x n pattern A is an inertialy arbitrary pattern(IAP) if (r,s,t) belongs to the inertia set of A for every nonnegative triple (r,s,t) with r+s+t=n. Some elementary results on these two classes of patterns are first exhibited. Tree sign patterns are then investigated, with a special emphasis on 4 x 4 tridiagonal sign patterns. Connections between the SAP(IAP) classes and the classes of potentially nilpotent and potentially stable patterns are explored. Some interesting open questions are also provided.