We consider the problem of efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity, which we call the set reconciliation problem. We describe an approach to set reconciliation based on a polynomial encoding of sets. The resulting protocols exhibit tractable computational complexity and nearly optimal communication complexity when the sets being reconciled are sparse. Also, these protocols can be adapted to work over a broadcast channel, allowing many clients to reconcile with one host based on a single broadcast, even if each client is missing a different subset.

It is well known that we can efficiently test whether a polynomial is identically zero or not by examining the values of the polynomial at well-chosen points. Both deterministic and efficient probabilistic algorithms have been devised for this purpose. It is not so well recognized that algebraic functions can be similarly tested for zeroness. The need for zero testing black boxes representing algebraic functions has recently arisen in the area of self-testing/self-correcting programs. Given a black box Bα that represents an algebraic function α and a few additional parameters about α, we show how to test if α is equal to the zero function.

Functional decomposition—whether a functionf(x) can be written as a composition of functionsg(h(x)) in a non-trivial way—is an important primitive in symbolic computation systems. The problem of univariate polynomial decomposition was shown to have an efficient solution by Kozen and Landau (1989). Dickerson (1987) and Gathen (1990a) gave algorithms for certain multivariate cases. Zippel (1991) showed how to decompose rational functions. In this paper, we address the issue of decomposition of algebraic functions. We show that the problem is related to univariate resultants in algebraic function fields, and in fact can be reformulated as a problem ofresultant decomposition. We characterize all decompositions of a given algebraic function up to isomorphism, and give an exponential time algorithm for finding a non-trivial one if it exists. The algorithm involves genus calculations and constructing transcendental generators of fields of genus zero.

This paper presents a polynomial time algorithm for determining whether a given univariate rational function over an arbitrary field is the composition of two rational functions over that field, and finds them if so.

A fundamental technique used by many algorithms in computer algebrais interpolating polynomials from their values. This paper discusses two algorithms for solving this problem for sparse multivariate polynomials, an updated version of a probabilistic one and a new deterministic technique that uses some ideas due to Ben-Or and Tiwari (1988). In addition algorithms are presented for quickly finding points that are not zeroes of sparse multivariate polynomials—the zero avoidance problem.

A simplified version of the Merkle-Hellman public key cryptographic system is breakable. While their full-fledged system seems to be resistant to the cryptanalytic attack we propose, the result suggests some ways in which the security of their system can be enhanced.