Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Zachary Remscrim:

TR19-107 | 29th July 2019
Zachary Remscrim

The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups

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

TR16-020 | 8th February 2016
Zachary Remscrim

The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

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

TR13-088 | 16th June 2013
Zachary Remscrim, Michael Sipser

$AC^0$ Pseudorandomness of Natural Operations

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

ISSN 1433-8092 | Imprint