Pekka Orponen

We introduce a model for analog computation with discrete

time in the presence of analog noise

that is flexible enough to cover the most important concrete

cases, such as noisy analog neural nets and networks of spiking neurons.

This model subsumes the classical ...
more >>>

Eduardo D. Sontag

We consider recurrent analog neural nets where the output of each

gate is subject to Gaussian noise, or any other common noise

distribution that is nonzero on a large set.

We show that many regular languages cannot be recognized by

networks of this type, and

more >>>

Eldar Fischer, Frederic Magniez, Michel de Rougemont

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.

We present a simple proof to show that parity cannot be computed by such circuits.

Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ...
more >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity $\Theta(1)$, $\tilde{\Theta}(\sqrt n)$, or $\Theta(n)$. The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we ... more >>>