Jayalal Sarma

19-06-2022, Bisoyi, Sagar, Dinesh, Krishnamoorthy, Jayalal Sarma

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.

01-02-2019, Dinesh, Krishnamoorthy, Koroth, Sajin, Sarma, Jayalal

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.

01-06-2019, Dinesh, Krishnamoorthy, Sarma, Jayalal

The well-known SENSITIVITY CONJECTURE regarding combinatorial complexity measures on Boolean functions states that for any Boolean function f:{0,1} n →{0,1}, 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, f:{0,1} n →{0,1} the communication complexity of a related function f ⊕ :{0,1} n ×{0,1} n →{0,1} (defined as f ⊕ (x,y)=f(x⊕y)) 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 by 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). En route 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 log⁡sparsity(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, deg(f)≤alt(f)deg 2 (f)deg m (f) where deg(f), deg 2 (f) and deg m (f) are the degrees of f over R, F 2 and Z m respectively. We give three further applications of this bound: (1) We show that for Boolean functions f of constant alternation have deg 2 (f)=Ω(log⁡n). (2) Moreover, these functions also have high sparsity (exp⁡(Ω(deg(f))), thus partially answering a question of Kulkarni and Santha (2013). (3) We observe that our relation upper bounding real degree also improves the upper bound for influence to deg 2 (f) 2 ⋅alt(f) improving Guo and Komargodski (2017).

01-01-2019, Dinesh, Krishnamoorthy, Sarma, Jayalal

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.

01-12-2016, Dinesh, Krishnamoorthy, Koroth, Sajin, Jayalal Sarma

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.

01-01-2018, Dinesh, Krishnamoorthy, Otiv, Samir, Sarma, Jayalal

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

01-01-2020, Bisoyi, Sagar, Dinesh, Krishnamoorthy, Sarma, Jayalal

This paper explores the power of catalytic computation when the catalytic space (c(n), the full memory for which the content needs to be restored to original content at the end of the 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 in each of them. Low-end regime: We define the classes and (nondeterministic variant of) where and. Exploring the connection between computational power of one counter machines (OC) and constant pure space catalytic Turing machines, we observe that and show that. We prove that Low-end non-constant regime: Let M be an oblivious catalytic Turing machine using s(n) pure space and c(n) catalytic space such that then L(M) is regular. This strengthens the classical theorem on to the case of catalytic Turing machines.High-end regime: 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 pure space and catalytic space. Hence, catalytic algorithms can lead to a non-trivial saving in the pure space required for computation when K is. Our techniques include interesting generalizations of crossing sequence arguments and implementations of incremental dynamic programs using catalytic algorithms. These may be of independent interest.

12-12-2020, Dinesh, Krishnamoorthy, Otiv, Samir, Sarma, Jayalal

For a Boolean function f:{0,1}n→{0,1} computed by a Boolean circuit C over a finite basis B, the energy complexity of C (denoted by ECB(C)) is the maximum over all inputs {0,1}n of the number gates of the circuit C (excluding the inputs) that output a one. Energy Complexity of a Boolean function over a finite basis B denoted by ECB(f)=defminC⁡ECB(C) where C is a Boolean circuit over B computing f. We study the case when B={∧2,∨2,¬}, 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 3n(1+ϵ(n)) for a small ϵ(n) (which we observe is improvable to 3n−1). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions. • For all Boolean functions f, EC(f)≤O(DT(f)3) where DT(f) is the optimal decision tree depth of f. • We define a parameter positive sensitivity (denoted by psens), a quantity that is smaller than sensitivity (Cook et al. 1986, [3]) and defined in a similar way, and show that for any Boolean circuit C computing a Boolean function f, EC(C)≥psens(f)/3. • For a monotone function f, we show that EC(f)=Ω(KW+(f)) where KW+(f) is the cost of monotone Karchmer-Wigderson game of f. • Restricting the above notion of energy complexity to Boolean formulas, we show EC(F)=Ω(L(F)−Depth(F)) where L(F) is the size and Depth(F) is the depth of a formula F.

24-10-2020, Dinesh, Krishnamoorthy, Sarma, Jayalal

In this paper, we study the Boolean function parameters sensitivity (s), block sensitivity (bs), and alternation (alt) under specially designed affine transforms and show several applications. For a function f:F2n→{−1,1}, and A=Mx+b for M∈F2n×n and b∈F2n, the result of the transformation g is defined as ∀x∈F2n,g(x)=f(Mx+b). 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 salt(f)). By a result of Lin and Zhang (2017) [7], it follows that bs(f)≤O(salt(f)2s(f)). Thus, to settle the Sensitivity Conjecture (∀f,bs(f)≤poly(s(f))), it suffices to argue that ∀f,salt(f)≤poly(s(f)). However, we exhibit an explicit family of Boolean functions for which salt(f) is 2Ω(s(f)). Going further, we use an affine transform A, such that the corresponding function g satisfies bs(f,0n)≤s(g). We apply this in the setting of quantum communication complexity to prove that for F(x,y)=deff(x∧y), the bounded error quantum communication complexity of F with prior entanglement, Q1/3⁎(F) is Ω(bs(f,0n)). Our proof builds on ideas from Sherstov (2010) [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 ϵ, 0<ϵ<1, any Boolean function f that depends on all its inputs with degp(f)≤(1−ϵ)log⁡n must satisfy [Formula presented]. Here, degp(f) denotes the degree of the multilinear polynomial over Fp which agrees with f on Boolean inputs. (b) For Boolean function f such that there exists primes p and q with degq(f)≥Ω(degp(f)δ) for δ>2, the deterministic communication complexity - D(F) and Q1/3⁎(F) are polynomially related. In particular, this holds when degp(f)=O(1). Thus, for this class of functions, this answers an open question (see Buhrman and de Wolf (2001) [15]) 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, alt(f)≤2s(g)+1. Using this new relation, we exhibit Boolean functions f (other than the parity function) such that s(f) is Ω(sparsity(f)) where sparsity(f) is the number of non-zero coefficients in the Fourier representation of f. This family of Boolean functions also rule out a potential approach to settle the XOR Log-Rank conjecture via the recently settled Sensitivity conjecture (Hao Huang (2019) [5]).

01-01-2018, Dinesh, Krishnamoorthy, Sarma, Jayalal

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