All reports by Author Uma Girish:

__
TR21-046
| 22nd March 2021
__

Uma Girish, Avishay Tal, Kewen Wu#### Fourier Growth of Parity Decision Trees

__
TR20-101
| 7th July 2020
__

Uma Girish, Ran Raz, Wei Zhan#### Lower Bounds for XOR of Forrelations

__
TR20-087
| 8th June 2020
__

Uma Girish, Ran Raz, Wei Zhan#### Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Revisions: 2

__
TR19-152
| 6th November 2019
__

Uma Girish, Ran Raz, Avishay Tal#### Quantum versus Randomized Communication Complexity, with Efficient Players

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$.

Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound ...
more >>>

Uma Girish, Ran Raz, Wei Zhan

The Forrelation problem, first introduced by Aaronson [AA10] and Aaronson and Ambainis [AA15], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [AA15]; the first separation between ... more >>>

Uma Girish, Ran Raz, Wei Zhan

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq poly(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive ... more >>>

Uma Girish, Ran Raz, Avishay Tal

We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean ... more >>>