Now showing 1 - 10 of 26
  • Placeholder Image
    Publication
    On directed tree realizations of degree sets
    (04-02-2013)
    Kumar, Prasun
    ;
    ;
    Sawlani, Saurabh
    Given a degree set D = {a1 < a2 < ... < an} of non-negative integers, the minimum number of vertices in any tree realizing the set D is known [11]. In this paper, we study the number of vertices and multiplicity of distinct degrees as parameters of tree realizations of degree sets. We explore this in the context of both directed and undirected trees and asymmetric directed graphs. We show a tight lower bound on the maximum multiplicity needed for any tree realization of a degree set. For the directed trees, we study two natural notions of realizability by directed graphs and show tight lower bounds on the number of vertices needed to realize any degree set. For asymmetric graphs, if μA (D) denotes the minimum number of vertices needed to realize any degree set, we show that a1 + a n + 1 ≤ μA(D) ≤ an-1 + an + 1. We also derive sufficiency conditions on ai 's under which the lower bound is achieved. We study the following related algorithmic questions. (1) Given a degree set D and a non-negative integer r (as 1r), test whether the set D can be realized by a tree of exactly μT (D) + r number of vertices. We show that the problem is fixed parameter tractable under two natural parameterizations of
  • Placeholder Image
    Publication
    Characterization and lower bounds for branching program size using projective dimension
    (01-12-2016)
    Dinesh, Krishnamoorthy
    ;
    Koroth, Sajin
    ;
    We study projective dimension, a graph parameter (denoted by pd(G) for a graph G), introduced by Pudlák and Rödl (1992). For a Boolean function f(on n bits), Pudlák and Rödl associated a bipartite graph Gf and showed that size of the optimal branching program computing f (denoted by bpsize(f)) is at least pd(Gf) (also denoted by pd(f)). Hence, proving lower bounds for pd(f) imply lower bounds for bpsize(f). Despite several attempts (Pudlák and Rödl (1992), Rónyai et.al, (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We observe that there exist a Boolean function f for which the gap between the pd(f) and bpsize(f)) is 2Ω(n). Motivated by the argument in Pudlák and Rödl (1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by upd(f)) and bitwise decomposable projective dimension (denoted by bpdim(f)). We show the following results: (a) We observe that there exist a Boolean function f for which the gap between upd(f) and bpsize(f) is 2Ω(n). In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a large constant c > 0 and for any function f, bpdim(f)/6 ≤ bpsize(f) ≤ (bpdim(f))c. (b) We introduce a new candidate function family f for showing super-polynomial lower bounds for bpdim(f). As our main result, we demonstrate gaps between pd(f) and the above two new measures for f: pd(f) = O(√n) upd(f) = Ω(n) bpdim(f) = Ω(n1.5/log n). (c) Although not related to branching program lower bounds, we derive exponential lower bounds for two restricted variants of pd(f) and upd(f) respectively by observing that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.
  • Placeholder Image
    Publication
    Using Elimination Theory to Construct Rigid Matrices
    (01-12-2014)
    Kumar, Abhinav
    ;
    Lokam, Satyanarayana V.
    ;
    Patankar, Vijay M.
    ;
    The rigidity of a matrix A for target rank r is the minimum number of entries of A that must be changed to ensure that the rank of the altered matrix is at most r. Since its introduction by Valiant (1977), rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all n × n matrices over an infinite field have a rigidity of (n − r)2. It is a long-standing open question to construct infinite families of explicit matrices even with superlinear rigidity when r = Ω(n).
  • Placeholder Image
    Publication
    Testing polynomial equivalence by scaling matrices
    (01-01-2017)
    Bläser, Markus
    ;
    ;
    In this paper we study the polynomial equivalence problem: test if two given polynomials f and g are equivalent under a non-singular linear transformation of variables. We begin by showing that the more general problem of testing whether f can be obtained from g by an arbitrary (not necessarily invertible) linear transformation of the variables is equivalent to the existential theory over the reals. This strengthens an NP-hardness result by Kayal [9]. Two n-variate polynomials f and g are said to be equivalent up to scaling if there are scalars a1, …, an F\{0} ∈such that f(a1, …, an) = g(x1, …, xn). Testing whether two polynomials are equivalent by scaling matrices is a special case of the polynomial equivalence problem and is harder than the polynomial identity testing problem. As our main result, we obtain a randomized polynomial time algorithm for testing if two polynomials are equivalent up to a scaling of variables with black-box access to polynomials f and g over the real numbers. An essential ingredient to our algorithm is a randomized polynomial time algorithm that given a polynomial as a black box obtains coefficients and degree vectors of a maximal set of monomials whose degree vectors are linearly independent. This algorithm might be of independent interest. It also works over finite fields, provided their size is large enough to perform polynomial interpolation.
  • Placeholder Image
    Publication
    Depth lower bounds against circuits with sparse orientation
    (01-01-2014)
    Koroth, Sajin
    ;
    We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function f is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing f. We prove trade-off results between the depth and the weight/structure of the orientation vectors in any circuit C computing the CLIQUE function on an n vertex graph. We prove that if C is of depth d and each gate computes a Boolean function with orientation of weight at most w (in terms of the inputs to C), then d ×w must be Ω(n). In particular, if the weights are,(equation present) then C must be of depth ω(log k n). We prove a barrier for our general technique. However, using specific properties of the CLIQUE function (used in [4]) and the Karchmer-Wigderson framework [11], we go beyond the limitations and obtain lower bounds when the weight restrictions are less stringent. We then study the depth lower bounds when the structure of the orientation vector is restricted. We demonstrate that this approach reaches out to the limits in terms of depth lower bounds by showing that slight improvements to our results separates NP from NC. As our main tool, we generalize Karchmer-Wigderson game [11] for monotone functions to work for non-monotone circuits parametrized by the weight/structure of the orientation. We also prove structural results about orientation and prove connections between number of negations and weight of orientations required to compute a function. © 2014 Springer International Publishing Switzerland.
  • Placeholder Image
    Publication
    Min/Max-Poly Weighting Schemes and the NL versus UL Problem
    (01-05-2017)
    Dhayal, Anant
    ;
    ;
    Sawlani, Saurabh
    For a graph G(V, E) (|V| = n) and a vertex s ∈ V, a weighting scheme (W : E ↔→ Z +) is called a min-unique (resp. max-unique) weighting scheme if, for any vertex v of the graph G, there is a unique path of minimum (resp. maximum) weight from s to v, where weight of a path is the sum of the weights assigned to the edges. Instead, if the number of paths of minimum (resp. maximum) weight is bounded by nc for some constant c, then the weighting scheme is called a min-poly (resp. max-poly) weighting scheme. In this article, we propose an unambiguous nondeterministic log-space (UL) algorithm for the problem of testing reachability graphs augmented with a min-poly weighting scheme. This improves the result in Reinhardt and Allender [2000], in which a UL algorithm was given for the case when the weighting scheme is min-unique. Our main technique involves triple inductive counting and generalizes the techniques of Immerman [1988], Szelepcśenyi [1988], and Reinhardt and Allender [2000], combined with a hashing technique due to Fredman et al. [1984] (also used in Garvin et al. [2014]).We combine this with a complementary unambiguous verification method to give the desired UL algorithm. At the other end of the spectrum, we propose a UL algorithm for testing reachability in layered DAGs augmented with max-poly weighting schemes. To achieve this, we first reduce reachability in layered DAGs to the longest path problem for DAGs with a unique source, such that the reduction also preserves the max-unique and max-poly properties of the graph. Using our techniques, we generalize the double inductive counting method in Limaye et al. [2009], in which the UL algorithm was given for the longest path problem on DAGs with a unique sink and augmented with a max-unique weighting scheme. An important consequence of our results is that, to show NL = UL, it suffices to design log-space computable min-poly (or max-poly) weighting schemes for layered DAGs.
  • Placeholder Image
    Publication
    Comparator Circuits over Finite Bounded Posets
    (01-08-2018)
    Komarath, Balagopal
    ;
    ;
    Sunil, K. S.
    The comparator circuit model was originally introduced by Mayr et al. (1992) (and further studied by Cook et al. (2014)) to capture problems that are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem and we know that NLOG⊆CC⊆P. Cook et al. (2014) showed that CC is also the class of languages decided by polynomial size comparator circuit families. We study generalizations of the comparator circuit model that work over fixed finite bounded posets. We observe that there are universal comparator circuits even over arbitrary fixed finite bounded posets. Building on this, we show the following: • Comparator circuits of polynomial size over fixed finite distributive lattices characterize the class CC. When the circuit is restricted to be skew, they characterize LOG. Noting that (uniform) polynomial sized Boolean circuits (resp. skew) characterize P (resp. NLOG), this indicates a comparison between P vs CC and NLOG vs LOG problems.• Complementing this, we show that comparator circuits of polynomial size over arbitrary fixed finite lattices characterize the class P even when the comparator circuit is skew.• In addition, we show a characterization of the class NP by a family of polynomial sized comparator circuits over fixed finite bounded posets. As an aside, we consider generalizations of Boolean formulae over arbitrary lattices. We show that Spira's theorem (Spira, 1971) can be extended to this setting as well and show that polynomial sized Boolean formulae over finite fixed lattices capture the class NC1.These results generalize results in Cook et al. (2014) regarding the power of comparator circuits. Our techniques involve design of comparator circuits and finite posets. We then use known results from lattice theory to show that the posets that we obtain can be embedded into appropriate lattices. Our results give new methods to establish CC upper bounds for problems and also indicate potential new approaches towards the problems P vs CC and NLOG vs LOG using lattice theoretic methods.
  • Placeholder Image
    Publication
    Arithmetic circuit lower bounds via MaxRank
    (23-07-2013)
    Kumar, Mrinal
    ;
    Maheshwari, Gaurav
    ;
    We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results : - As our first main result, we prove that any homogeneous depth-3 circuit for computing the product of d matrices of dimension n x n requires Ω(nd-1/2d) size. This improves the lower bounds in [9] for d = ω(1). - As our second main result, we show that there is an explicit polynomial on n variables and degree at most n/2 for which any depth-3 circuit C of product dimension at most n/10 (dimension of the space of affine forms feeding into each product gate) requires size 2Ω(n). This generalizes the lower bounds against diagonal circuits proved in [14]. Diagonal circuits are of product dimension 1. - We prove a nΩ(log n) lower bound on the size of product-sparse formulas. By definition, any multilinear formula is a product-sparse formula. Thus, this result extends the known super-polynomial lower bounds on the size of multilinear formulas [11]. - We prove a 2 Ω(n) lower bound on the size of partitioned arithmetic branching programs. This result extends the known exponential lower bound on the size of ordered arithmetic branching programs [7]. © 2013 Springer-Verlag.
  • Placeholder Image
    Publication
    Characterization and lower bounds for branching program size using projective dimension
    (01-02-2019)
    Dinesh, Krishnamoorthy
    ;
    Koroth, Sajin
    ;
    We study projective dimension, a graph parameter, denoted by pd(G) for a bipartite graph G, introduced by Pudlák and Rödl (1992). For a Boolean function f (on n bits), Pudlák and Rödl associated a bipartite graph G f and showed that size of the optimal branching program computing f , denoted by bpsize(f ), is at least pd(G f ) (also denoted by pd(f )). Hence, proving lower bounds for pd(f ) implies lower bounds for bpsize(f ). Despite several attempts (Pudlák and Rödl (1992), Rónyai et al. (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We observe that there exist a Boolean function f for which the gap between the pd(f ) and bpsize(f )) is 2 Ω( n ) . Motivated by the argument in Pudlák and Rödl (1992), we define two variants of projective dimension: projective dimension with intersection dimension 1, denoted by upd(f ), and bitwise decomposable projective dimension, denoted by bitpdim(f ). We show the following results: (a) We observe that there exist a Boolean function f for which the gap between upd(f ) and bpsize(f ) is 2 Ω( n ) . In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a constant c > 0 and for any function f , bitpdim(f )/6 ≤ bpsize(f ) ≤ (bitpdim(f )) c . (b) We introduce a new candidate family of functions f for showing super-polynomial lower bounds for bitpdim(f ). As our main result, for this family of functions, we demonstrate gaps between pd(f ) and the above two new measures for f : . We adapt Nechiporuk's techniques for our linear algebraic setting to prove the best-known bpsize lower bounds for bitpdim. Motivated by this linear algebraic setting of our main result, we derive exponential lower bounds for two restricted variants of pd(f ) and upd(f ) by observing that they are exactly equal to well-studied graph parameters-bipartite clique cover number and bipartite partition number, respectively.
  • Placeholder Image
    Publication
    On isomorphism testing of groups with normal hall subgroups
    (01-07-2012)
    Qiao, You Ming
    ;
    ;
    Tang, Bang Sheng
    A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index. Schur-Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish the framework, we first observe that a proof of Schur-Zassenhaus theorem is constructive, and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products, and isomorphisms of the normal parts and complement parts. We then focus on the case when the normal subgroup is abelian. Utilizing basic facts of representation theory of finite groups and a technique by Le Gall (STACS 2009), we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators. For the case when the complement subgroup is elementary abelian, which does not necessarily have bounded number of generators, we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem, which asks whether two linear subspaces are the same up to permutation of coordinates. A solution to the latter can be obtained by a mild extension of the singly exponential (in the number of coordinates) time algorithm for code isomorphism problem developed recently by Babai et al. (SODA 2011). Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups: given two representations ? and ? of a group H over Z dp , p a prime, determine if there exists an automorphism φ : H → H, such that the induced representation ?φ = ? 0 φ and ? are equivalent, in time poly(