Jayalal Sarma

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

This paper explores the power of catalytic computation when the catalytic space (c(n), the full memory whose content needs to be restored to the original by the end of computation) is much more than exponential in the pure space (s(n), the empty memory which does not have any access/restoration constraints). We study the following three regimes of the relation between s(n) and c(n) and explore the class CSPACE(s(n),c(n)) in each of them. • High-end regime - s(n)=O(c(n)ϵ): We show an implementation of incremental dynamic program using catalytic machines, thus showing that Knapsack problem (with n items, sum of their costs as C and the capacity of the bag as K) can be solved in O(nlog⁡nlog⁡C+log⁡(nKC)) pure space and O(n2KC3log2⁡Klog⁡n) catalytic space. Hence, catalytic algorithms can lead to a non-trivial saving in the pure space required for computation when K is Ω(n2). • Low-end regime - s(n)=O(1): We define the classes CR and CNR (nondeterministic variant of CR) where s(n)=O(1) and c(n)=poly(n). Exploring the connection between computational power of one counter machines (OC) and constant pure space catalytic Turing machines, we observe that OC⊆CR and show that CR⊆OC⇒CR≠CNR. We prove that L⊈CSPACE(O(1),o(n)). We also study the effect of adding additional read-only tapes to the model and show that: For any k∈N, (k+1)-CSPACE(O(1),O(nc))⊆CSPACE(klog⁡n,nc)⊆(4k+1)-CSPACE(O(1),O(nc)). • Low-end non-constant regime - s(n)=o(log⁡log⁡n): Let M be an oblivious catalytic Turing machine using s(n) pure space and c(n) catalytic space such that s(n)+log⁡c(n)=o(log⁡log⁡n) then L(M) is regular. This strengthens the classical theorem on s(n)=o(log⁡log⁡n) to the case of catalytic Turing machines. Our techniques include interesting generalizations of crossing sequence arguments and implementations of incremental dynamic programs using catalytic algorithms. These may be of independent interest.

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.

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).

Computing the rotation distance between two binary trees with n internal nodes efficiently (in poly(n) time) is a long standing open question in the study of height balancing in tree data structures. In this paper, we initiate the study of this problem bounding the rank of the trees given at the input (defined in [6] in the context of decision trees). We define the rank-bounded rotation distance between two given binary trees T1 and T2 (with n internal nodes) of rank at most r, denoted by dr(T1, T2), as the length of the shortest sequence of rotations that transforms T1 to T2 with the restriction that the intermediate trees must be of rank at most r. We show that the rotation distance problem reduces in polynomial time to the rank bounded rotation distance problem. This motivates the study of the problem in the combinatorial and algorithmic frontiers. Observing that trees with rank 1 coincide exactly with skew trees (binary trees where every internal node has at least one leaf as a child), we show the following results in this frontier: We present an O(n2) time algorithm for computing d1(T1, T2). That is, when the given trees are skew trees (we call this variant as skew rotation distance problem) - where the intermediate trees are restricted to be skew as well. In particular, our techniques imply that for any two skew trees d(T1, T2) ≤ n2.We show the following upper bound: for any two trees T1 and T2 of rank at most r1 and r2 respectively, we have that: dr(T1, T2) ≤ n2(1 + (2 n+ 1 ) (r1+ r2- 2 ) ) where r= max { r1, r2}. This bound is asymptotically tight for r= 1. En route our proof of the above theorems, we associate binary trees to permutations and relate the rotation operation on trees to transpositions in the corresponding permutations. We give exact combinatorial characterizations of permutations that correspond to binary trees and skew binary trees under this association. We also precisely characterize the transpositions that correspond to the set of rotations in binary trees.

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.

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.

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.

The separating words problem asks - given two words w, x∈ { 0, 1 }n, the size of the smallest automaton (in terms of number of states, expressed as a function of n) which accepts one of them and rejects the other. The best lower bound known for the problem is Ω(log n), whereas the best upper bound known is O(n1 / 3log7n), due to (Chase 2021). Motivated by the applications to this problem, we study separating in the context of groups - a finite group G is said to separate w and x, if there is a substitution function from ϕ: Σ→ G such that the expressions ϕ(w) and ϕ(x) yield different elements in the group G. We show the following results: By a result of Robson [6], there is a permuting automaton of size O(n) states which separate any two words w and x of length n. Hence, there is a group of size 2O(nlogn) which separate w and x. Using basic properties of one dimensional representations of the groups, we improve this to O(n2n).A class of groups G is said to be universal if for any two words w, x∈ Σ∗, there exists a group G∈ G for which a separating substitution map exists such that the yields of the words under the map are distinct. We show that the class of permutation groups, solvable groups, nilpotent groups and, in particular, p-groups, are universal.Class of Abelian groups and Dihedral groups are not universal. En route to this result, we derive sufficiency conditions for a class of groups to be non-universal.We can also translate separation using groups to separation using automaton. Any two words w, x∈ Σn which are separated by a group G can be separated using an automaton of size |G|. We show better bounds for permutation groups. We also study the natural computational problem in the context and show it to be NP -complete.

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.