We develop a new and simple way to describe Karatsuba-like algorithms for multiplication of polynomials over$\mathbb {F}_2$. We restrict the search of small circuits to a class of circuits we callsymmetric bilinear. These are circuits in which AND gates only compute functions of the form$\sum _{i \in S} a_i \cdot \sum _{i \in S} b_i \quad \quad (S \subseteq \lbrace 0, \ldots, n-1\rbrace).$∑i∈Sai·∑i∈Sbi(S⊆{0,...,n-1}).These techniques yield improved recurrences for$M(kn)$M(kn), the number of gates used in a circuit that multiplies two$kn$kn-term polynomials, for$k = 4,5,6,$k=4,5,6,and 7. We built and verified the circuits for$n$n-term binary polynomial multiplication for values of$n$nof practical interest. Circuits for$n$nup to 100 are posted athttp://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/BinPolMult.tar.gz.

We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size. With a fairness condition on interactions, we define the concept of stable computation of a function or predicate, and give protocols that stably compute functions in a class including Boolean combinations of threshold-k, parity, majority, and simple arithmetic. We prove that all stably computable predicates are in NL. With uniform random sampling of pairs to interact, we define the model of conjugating automata and show that any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a protocol in a population of size n. We prove that all predicates computable with high probability in this model are in P ∩ RL. Several open problems and promising future directions are discussed.

We improve on the communication complexity of zero-knowledge proof systems.Let ~ be a 13001eancircuit of size n.Previous zero-knowledge proof systems for the satisfiability of % require the use of Q(kn) bit commitments in order to achieve a probability of undetected cheating below 2 'k.In the case k = n, the communication complexity of these protocols is therefore Q(nz) bit commitments.In this paper, we present a zero-knowledge proof system for achieving the same goal with only O(nl' 'X + k&l+ 'n ) bit commitments, where s. goes to zero as n goes to infinity.

The communication complexity of zero-knowledge proof systems is improved. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega (kn) bit commitments in order to achieve a probability of undetected cheating not greater than 2/sup -k/. In the case k=n, the communication complexity of these protocols is therefore Omega (n/sup 2/) bit commitments. A zero-knowledge proof is given for achieving the same goal with only O(n/sup m/+k square root n/sup m/) bit commitments, where m=1+ epsilon /sub n/ and epsilon /sub n/ goes to zero as n goes to infinity. In the case k=n, this is O(n square root n/sup m/). Moreover, only O(k) commitments need ever be opened, which is interesting if committing to a bit is significantly less expensive than opening a commitment.>

The authors present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is O(log log n+k+log 1/ epsilon ), where epsilon is the statistical difference between the distribution induced on any k-bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by J. Naor and M. Naor (1990). An advantage of the present constructions is their simplicity. Two of the constructions are based on bit sequences that are widely believed to possess randomness properties, and the results can be viewed as an explanation and establishment of these beliefs.>

A probabilistic polynomial-time algorithm for computing the square root of a numberx \in {\bf Z}/P{\bf Z}, whereP = 2^{S}Q + 1(Qodd,s > 0)is a prime number, is described. In contrast to the Adleman, Manders, and Miller algorithm, this algorithm gets faster as s grows. As with the Berlekamp-Rabin algorithm, the expected running time of the algorithm is independent ofx. However, the algorithm presented here is considerably faster for values ofsgreater than2.