Abstract (i) First we show that all the known algorithms for polynomial division can be
represented as algorithms for triangular Toeplitz matrix inversion. In spite of the apparent …

We define the notion of a catalytic-space computation. This is a computation that has a small
amount of clean space available and is equipped with additional auxiliary space, with the …

This paper is a report on algorithms to solve problems in number theory. I believe the most
interesting such problems to be those from elementary number theory whose complexity is …

In a non-interactive zero-knowledge (NIZK) proof, a prover can non-interactively convince a
verifier of a statement without revealing any additional information. Thus far, numerous …

On the Power of Small-Depth Computation Page 1 On the Power of Small-Depth Computation Full
text available at: http://dx.doi.org/10.1561/0400000033 Page 2 On the Power of Small-Depth …

A miniature gas chromatography (GC) system has been designed and fabricated using
silicon micromachining and integrated circuit (IC) processing techniques. The silicon …

Strategic games may exhibit symmetries in a variety of ways. A characteristic feature,
enabling the compact representation of games even when the number of players is …

In this talk we will consider various classes defined by small depth polynomial size circuits
which contain threshold gates and parity gates. We will describe various inclusions between …

In this paper we present new constructions of multi-party homomorphic secret sharing (HSS)
based on a new primitive that we call homomorphic encryption with decryption to shares …

P-printable sets, defined in [HY-84], arise naturally in the study of P-uniform circuit
complexity, generalized Kolmogorov complexity, and data compression, as well as in many …