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

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.

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.

Exploring further the power of negations in Boolean circuits, in this paper we study the effect of interdependency of negation gates in circuits in terms of computational power. As a starting point, we study the power of independent negations (where no negation feeds into another, even via other gates) in circuits and show the following results. The minimum number of independent negations required to compute a Boolean function is exactly characterized by the decrease of the function. We also provide an additional characterization by a generalization of orientation[9], which we call the monotone orientation.We define a new measure called the thickness of a Boolean function, and show that if f has thickness at most t and has a circuit of depth d, then f can be computed using (independent) negations in depth. When the function is monotone, we also show a parameterized version of this result, where the depth is expressed in terms of thickness and d. Our techniques include a natural generalization of the Karchmer-Widgerson games to include a switch step.For functions with thickness t, we show that the monotone and non-monotone circuit depths are related by the factor of thickness and an extra additive factor. This generalizes the fact[16] that for slice functions, the monotone and non-monotone circuit depth complexities are related by an additive factor of. To go further, we study the dependency between negations in the circuit by modeling the same using a negation graph with negation gates (and root) as vertices and directed edges representing pair of negation gates which feed into each other through a path which does not have negations. We associate a measure of decrease capacity with the negation graph, denoted. We show the following results:For a negation graph N, is the maximum decrease of any circuit which has this negation graph. Using this as a tool, we derive necessary conditions on the structure of negation graphs when the circuit is negation optimal.We show how to construct circuits for a function f, given a negation tree with decrease capacity at least. En route this result, we show that if f and g are two Boolean functions on n variables with and, then any circuit for g can be used (with substitution of variables with monotone functions) to compute f without using any extra negation. This may be of independent interest.

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.

Alternation of Boolean functions is a measure of non-monotonicity of the function. In this paper, we asymptotically characterize the VC-dimension of family of Boolean functions parameterized by the maximum alternation of the Boolean functions in the family. Enroute to our main result, we show exact bounds for VC-dimension of functions which has alternation 1, which strictly contains monotone functions and hence generalizes the bounds in [3]. As an application, we show tightness of VC-dimension bounds for k-fold union, by explicitly constructing a family F of subsets of { 0, 1 }n such that k-fold union of the family, Fk={⋃i=1kFi∣Fi∈F} must have VC-dimension at least Ω(dk) and that this bound holds even when the union is over disjoint sets from F. This provides a non-geometric set system achieving this bound.

In this paper we initiate study of the computational power of adaptive and non-adaptive monotone decision trees - decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree height (or size) can be viewed as a measure of non-monotonicity of a given Boolean function. We also study the restriction of the model by restricting (in terms of circuit complexity) the monotone functions that can be queried at each node. This naturally leads to complexity classes of the form for any circuit complexity class, where the height of the tree is, and the query functions can be computed by monotone circuits in class. In the above context, we prove the following characterizations and bounds. We show that the decision tree height can be exactly characterized (both in the adaptive and non-adaptive versions of the model) in terms of the alternation of a function (defined as the maximum number of times that the function value changes, in any chain in the Boolean lattice). We also characterize the non-adaptive decision tree height with a natural generalization of certification complexity of a function. We also show upper bounds and characterizations for non-deterministic and randomized variants of the monotone decision trees in terms of. We show that when contains monotone circuits for the threshold functions. For, we show that any function in can be computed by a sub-linear height monotone decision tree with queries having monotone circuits.To explore the logarithmic height case - we show that for any f (on n bits) in, and for any constant, there is an circuit for f with negation gates. In contrast, it can be derived from[14] that for every with, and for every, any circuit computing it with negations will need at least depth. En route the main results, as a tool, we study the monotone variant of the decision list model, and prove corresponding characterizations in terms of and also derive as a consequence that if has appropriate closure properties (where is defined similar to but for decision lists).

Comparator circuit model was originally introduced in [4] (and further studied in [2]) to capture problems which 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 [2] showed that CC is also the class of languages decided by polynomial size comparator circuits. 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 that general (resp. skew) comparator circuits of polynomial size over fixed finite distributive lattices characterizes CC (resp. LOG). Complementing this, we show that general comparator circuits of polynomial size over arbitrary fixed finite lattices exactly characterizes P and that when the comparator circuit is skew they characterize NLOG. In addition, we show a characterization of the class NP by a family of polynomial sized comparator circuits over fixed finite bounded posets. These results generalize the results in [2] regarding the power of comparator circuits. As an aside, we consider generalizations of Boolean formulae over arbitrary lattices. We show that Spira’s theorem[5] can be extended to this setting as well and show that polynomial sized Boolean formulae over finite fixed lattices capture exactly NC1. 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 gives new methods to establish CC upper bound for problems also indicate potential new approaches towards the problems P vs CC and NLOG vs LOG using lattice theoretic methods.