All reports by Author Krishnamoorthy Dinesh:

__
TR23-108
| 21st July 2023
__

Andrej Bogdanov, Tsun-Ming Cheung, Krishnamoorthy Dinesh, John C.S. Lui#### Classical simulation of one-query quantum distinguishers

__
TR21-115
| 6th August 2021
__

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming#### On quantum versus classical query complexity

Revisions: 2

__
TR21-093
| 1st July 2021
__

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan#### Bounded Indistinguishability for Simple Sources

Revisions: 1

__
TR18-153
| 22nd August 2018
__

Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma#### New Bounds for Energy Complexity of Boolean Functions

Revisions: 1

__
TR18-152
| 30th August 2018
__

Krishnamoorthy Dinesh, Jayalal Sarma#### Sensitivity, Affine Transforms and Quantum Communication Complexity

Revisions: 1

__
TR17-192
| 15th December 2017
__

Krishnamoorthy Dinesh, Jayalal Sarma#### Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps

Revisions: 1

__
TR16-076
| 27th April 2016
__

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma#### Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Revisions: 2

Andrej Bogdanov, Tsun-Ming Cheung, Krishnamoorthy Dinesh, John C.S. Lui

We study the relative advantage of classical and quantum distinguishers of bounded query complexity over $n$-bit strings, focusing on the case of a single quantum query. A construction of Aaronson and Ambainis (STOC 2015) yields a pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm, but $O(\epsilon k/\sqrt{n})$-indistinguishable ... more >>>

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

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

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan

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

Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

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

Krishnamoorthy Dinesh, Jayalal Sarma

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

Krishnamoorthy Dinesh, Jayalal Sarma

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

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

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