Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Uma Girish:

TR20-101 | 7th July 2020
Uma Girish, Ran Raz, Wei Zhan

Lower Bounds for XOR of Forrelations

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

TR20-087 | 8th June 2020
Uma Girish, Ran Raz, Wei Zhan

Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Revisions: 1

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

TR19-152 | 6th November 2019
Uma Girish, Ran Raz, Avishay Tal

Quantum versus Randomized Communication Complexity, with Efficient Players

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

ISSN 1433-8092 | Imprint