Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Krishnamoorthy Dinesh:

TR21-115 | 6th August 2021
Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

On quantum versus classical query complexity

Revisions: 2

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the ... more >>>

TR21-093 | 1st July 2021
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan

Bounded Indistinguishability for Simple Sources

A pair of sources $\mathbf{X},\mathbf{Y}$ over $\{0,1\}^n$ are $k$-indistinguishable if their projections to any $k$ coordinates are identically distributed. Can some $\mathit{AC^0}$ function distinguish between two such sources when $k$ is big, say $k=n^{0.1}$? Braverman's theorem (Commun. ACM 2011) implies a negative answer when $\mathbf{X}$ is uniform, whereas Bogdanov et ... more >>>

TR18-153 | 22nd August 2018
Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

New Bounds for Energy Complexity of Boolean Functions

Revisions: 1

For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(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 ... more >>>

TR18-152 | 30th August 2018
Krishnamoorthy Dinesh, Jayalal Sarma

Sensitivity, Affine Transforms and Quantum Communication Complexity

Revisions: 1

In this paper, we study the Boolean function parameters sensitivity ($\mathbf{s}$), block sensitivity ($\mathbf{bs}$), and alternation ($\mathbf{alt}$) under specially designed affine transforms and show several applications. For a function $f:\mathbb{F}_2^n \to \{0,1\}$, and $A = Mx+b$ for $M \in \mathbb{F}_2^{n \times n}$ and $b \in \mathbb{F}_2^n$, the result of the ... more >>>

TR17-192 | 15th December 2017
Krishnamoorthy Dinesh, Jayalal Sarma

Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps

Revisions: 1

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n ... more >>>

TR16-076 | 27th April 2016
Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Revisions: 2

We study projective dimension, a graph parameter (denoted by $pd(G)$ for a graph $G$), introduced by (Pudlak, Rodl 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 (Pudlak, ... more >>>

ISSN 1433-8092 | Imprint