We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an $s$-bit advice for a randomly chosen function $f\colon [n] \mapsto [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$ (i.e., to find $x$ such that $f(x)=y$). ... more >>>

A foundational result in the theory of quantum computation known as the ``principle of safe storage'' shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that ... more >>>

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