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

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.

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.

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.

For a Boolean function (Formula Presented) computed by a circuit C over a finite basis (Formula Presented), the energy complexity of C (denoted by (Formula Presented)) is the maximum over all inputs (Formula Presented) the numbers of gates of the circuit C (excluding the inputs) that output a one. Energy complexity of a Boolean function over a finite basis (Formula Presented) denoted by where C is a circuit over (Formula Presented) computing f. We study the case when (Formula Presented), the standard Boolean basis. It is known that any Boolean function can be computed by a circuit (with potentially large size) with an energy of at most (Formula Presented) for a small (Formula Presented) (which we observe is improvable to (Formula Presented)). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions. For all Boolean functions f, (Formula Presented) where (Formula Presented) is the optimal decision tree depth of f.We define a parameter positive sensitivity (denoted by (Formula Presented)), a quantity that is smaller than sensitivity and defined in a similar way, and show that for any Boolean circuit C computing a Boolean function f, (Formula Presented).Restricting the above notion of energy complexity to Boolean formulas, denoted (Formula Presented), we show that (Formula Presented) where L(f) is the minimum size of a formula computing f. We next prove lower bounds on energy for explicit functions. In this direction, we show that for the perfect matching function on an input graph of n edges, any Boolean circuit with bounded fan-in must have energy (Formula Presented). We show that any unbounded fan-in circuit of depth 3 computing the parity on n variables must have energy is (Formula Presented).

Fix an algebraic structure (A, ∗). Given a graph G = (V, E) and the labelling function φ (φ: E → A) for the edges, two nodes s, t ∈ V, and a subset F ⊆ A, the A-Reach problem asks if there is a path p (need not be simple) from s to t whose yield (result of the operation in the ordered set of the labels of the edges constituting the path) is in F. On the complexity frontier of this problem, we show the following results. – When A is a group whose size is polynomially bounded in the size of the graph (hence equivalently presented as a multiplication table at the input), and the graph is undirected, the A-Reach problem is in L. Building on this, using a decomposition in [4], we show that, when A is a fixed quasi-group, and the graph is undirected, the A-Reach problem is in L. In contrast, we show NL-hardness of the problem over bidirected graphs, when A is a matrix group over ℚ. When A is a fixed aperiodic monoid, we show that the problem is NL-complete. – As our main theorem, we prove a dichotomy for graphs labelled with fixed aperiodic monoids by showing that for every fixed aperiodic monoid A, A-Reach problem is either in L or is NL-complete. – We show that there exists a monoid M, such that the reachability problem in general DAGs can be reduced to A-Reach problem for planar non-bipartite DAGs labelled with M. In contrast, we show that if the planar DAGs that we obtain above are bipartite, the problem can be further reduced to reachability testing in planar DAGs and hence is in UL.

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function (Formula presented), block sensitivity of f is polynomially related to sensitivity of f (denoted by s(f)). From the complexity theory side, the Xor Log-Rank Conjecture states that for any Boolean function, (Formula presented) the communication complexity of a related function (Formula presented), (defined as (Formula presented)) is bounded by polynomial in logarithm of the sparsity of f (the number of non-zero Fourier coefficients for f, denoted by sparsity(f). Both the conjectures play a central role in the domains in which they are studied. A recent result of Lin and Zhang (2017) implies that to confirm the above two conjectures it suffices to upper bound alternation of f (denoted alt(f)) for all Boolean functions f by polynomial in s(f) and logarithm of sparsity(f), respectively. In this context, we show the following results: We show that there exists a family of Boolean functions for which alt(f) is at least exponential in s(f) and alt(f) is at least exponential in log sparsity(f). Enroute to the proof, we also show an exponential gap between alt(f) and the decision tree complexity of f, which might be of independent interest.As our main result, we show that, despite the above exponential gap between alt(f) and logsparsity(f), the Xor Log-Rank Conjecture is true for functions with the alternation upper bounded by poly(log n). It is easy to observe that the Sensitivity Conjecture is also true for this class of functions.The starting point for the above result is the observation (derived from Lin and Zhang (2017)) that for any Boolean function f, (Formula presented) where deg(f) and (Formula presented) are the degrees of f over R and F2. We give two further applications of this bound: (1) We show that Boolean functions with bounded alternation have high sparsity (Formula presented), thus partially answering a question of Kulkarni and Santha (2013). (2) We observe that the above relation improves the upper bound for influence to (Formula presented) improving Guo and Komargodski (2017).

In this paper, we study the Boolean function parameters sensitivity ((Formula Presented) ), block sensitivity ((Formula Presented) ), and alternation ((Formula Presented) ) under specially designed affine transforms and show several applications. For a function (Formula Presented), and (Formula Presented) for (Formula Presented) and (Formula Presented), the result of the transformation g is defined as (Formula Presented). As a warm up, we study alternation under linear shifts (when M is restricted to be the identity matrix) called the shift invariant alternation (the smallest alternation that can be achieved for the Boolean function f by shifts, denoted by (Formula Presented) ). By a result of Lin and Zhang [12], it follows that (Formula Presented). Thus, to settle the Sensitivity Conjecture ((Formula Presented) ), it suffices to argue that (Formula Presented). However, we exhibit an explicit family of Boolean functions for which (Formula Presented) is (Formula Presented). Going further, we use an affine transform A, such that the corresponding function g satisfies (Formula Presented), to prove that for (Formula Presented), the bounded error quantum communication complexity of F with prior entanglement, (Formula Presented) is (Formula Presented). Our proof builds on ideas from Sherstov [17] where we use specific properties of the above affine transformation. Using this, we show the following. (a)For a fixed prime p and an (Formula Presented), any Boolean function f that depends on all its inputs with (Formula Presented) must satisfy (Formula Presented). Here, (Formula Presented) denotes the degree of the multilinear polynomial over (Formula Presented) which agrees with f on Boolean inputs.(b)For Boolean function f such that there exists primes p and q with (Formula Presented) for (Formula Presented), the deterministic communication complexity - (Formula Presented) and (Formula Presented) are polynomially related. In particular, this holds when (Formula Presented). Thus, for this class of functions, this answers an open question (see [2]) about the relation between the two measures. Restricting back to the linear setting, we construct linear transformation A, such that the corresponding function g satisfies, (Formula Presented). Using this new relation, we exhibit Boolean functions f (other than the parity function) such that (Formula Presented) is (Formula Presented) where (Formula Presented) is the number of non-zero coefficients in the Fourier representation of f.