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

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is ... more >>>

The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language $L_{eq}=\{a^m b^m |m \in \mathbb{N}\}$ in ... more >>>

In this paper, we apply tools from algebraic geometry to prove new results concerning extractors for algebraic sets, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over $\mathbb{F}_2$ of substantially higher degree than the ... more >>>

A function $f:\Sigma^{*} \rightarrow \Sigma^{*}$ on strings is $AC^0$-pseudorandom if the pair $(x,\hat f(x))$ is $AC^0$-indistinguishable from a uniformly random pair $(y,z)$ when $x$ is chosen uniformly at random. Here $\hat f(x)$ is the string that is obtained from $f(x)$ by discarding some selected bits from $f(x)$.

It is shown ... more >>>