Jayalal Sarma

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.

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

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.