Source author record

Krishnamoorthy Dinesh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity

Catalog footprint

Research overview

3works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

New Bounds for Energy Complexity of Boolean Functions

$\newcommand{\EC}{\mathsf{EC}}\newcommand{\KW}{\mathsf{KW}}\newcommand{\DT}{\mathsf{DT}}\newcommand{\psens}{\mathsf{psens}} \newcommand{\calB}{\cal B}$ For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\mathcal{B}$ , the energy complexity of $C$ (denoted by $\EC_{\calB}(C)$) is the maximum over all inputs $\{0,1\}^n$ 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 $\calB$ denoted by $\EC_\calB(f):= \min_C \EC_{\calB}(C)$ where $C$ is a circuit over $\calB$ computing $f$ . We study the case when $\calB = \{\land_2, \lor_2, \lnot\}$, 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) \le O(\DT(f)^3)$ where $\DT(f)$ is the optimal decision tree depth of $f$ . * We define a parameter \textit{positive sensitivity} (denoted by $\psens$), 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$ , $ \EC(C) \ge \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) = Ω\left (\sqrt{L(F)}-depth(F)\right )$ where $L(F)$ is the size and $depth(F)$ is the depth of a formula $F$ .

preprint2020arXiv

Sensitivity, Affine Transforms and Quantum Communication Complexity

$\newcommand{\F}{\mathbb{F}}$ We study the Boolean function parameters sensitivity ( $s$ ), block sensitivity ( $bs$ ), and alternation ( $alt$ ) under specially designed affine transforms. For a function $f:\F_2^n\to \{0,1\}$, and $A=Mx+b$ for $M \in \F_2^{n\times n}$ and $b\in \F_2^n$, the result of the transformation $g$ is defined as $\forall x\in\F_2^n, g(x)=f(Mx+b)$. We study alternation under linear shifts ( $M$ is the identity matrix) called the shift invariant alternation (denoted by $salt(f)$ ). We exhibit an explicit family of functions for which $salt(f)$ is $2^{Ω(s(f))}$ . We show an affine transform $A$ , such that the corresponding function $g$ satisfies $bs(f,0^n) \le s(g)$ , using which we proving that for $F(x,y)=f(x\land y)$ , the bounded error quantum communication complexity of $F$ with prior entanglement, $Q^*_{1/3}(F)=Ω(\sqrt{bs(f,0^n)})$ . Our proof builds on ideas from Sherstov (2010) where we use specific properties of the above affine transformation. We show, * For a prime $p$ and $0<ε<1$ , any $f$ with $deg_p(f)\le(1-ε)\log n$ must satisfy $Q^*_{1/3}(F) = Ω(\frac{n^{ε/2}}{\log n})$ . Here, $deg_p(f)$ denotes the degree of the multilinear polynomial of $f$ over $\F_p$. * For any $f$ such that there exists primes $p$ and $q$ with $deg_q(f) \ge Ω(deg_p(f)^δ)$ for $δ> 2$ , the deterministic communication complexity - $D(F)$ and $Q^*_{1/3}(F)$ are polynomially related. In particular, this holds when $deg_p(f) = O(1)$ . Thus, for this class of functions, this answers an open question (see Buhrman and deWolf (2001)) about the relation between the two measures. We construct linear transformation $A$ , such that $g$ satisfies, $alt(f) \le 2s(g)+1$ . Using this, we exhibit a family of Boolean functions that rule out a potential approach to settle the XOR Log-Rank conjecture via a proof of Sensitivity conjecture [Hao Huang (2019)].

preprint2017arXiv

Characterization and Lower Bounds for Branching Program Size using Projective Dimension

We study projective dimension, a graph parameter (denoted by pd $(G)$ for a graph $G$ ), introduced by (Pudlák, Rödl 1992), who showed that proving lower bounds for pd $(G_f)$ for bipartite graphs $G_f$ associated with a Boolean function $f$ imply size lower bounds for branching programs computing $f$ . Despite several attempts (Pudlák, Rödl 1992 ; Babai, Rónyai, Ganapathy 2000), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We show that there exist a Boolean function $f$ (on $n$ bits) for which the gap between the projective dimension and size of the optimal branching program computing $f$ (denoted by bpsize $(f)$ ), is $2^{Ω(n)}$ . Motivated by the argument in (Pudlák, Rödl 1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by upd $(G)$ ) and bitwise decomposable projective dimension (denoted by bitpdim $(G)$ ). As our main result, we show that there is an explicit family of graphs on $N = 2^n$ vertices such that the projective dimension is $O(\sqrt{n})$ , the projective dimension with intersection dimension $1$ is $Ω(n)$ and the bitwise decomposable projective dimension is $Ω(\frac{n^{1.5}}{\log n})$ . We also show that there exist a Boolean function $f$ (on $n$ bits) for which the gap between upd $(G_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$ , $\textrm{bitpdim}(G_f)/6 \le \textrm{bpsize}(f) \le (\textrm{bitpdim}(G_f))^c$ . We also study two other variants of projective dimension and show that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.