For a tree Markov random field, nonreconstruction is said to hold if as the depth of the tree goes to infinity, the information that a typical configuration at the leaves gives about the value at the root goes to zero. The distribution of the measure at the root conditioned on a typical boundary can be computed using a distributional recurrence. However, the exact computation is not feasible because the support of the distribution grows exponentially with the depth. In this work, we introduce a notion of a survey of a distribution over probability vectors which is a succinct representation of the true distribution. We show that a survey of the distribution of the measure at the root can be constructed by an efficient recursive algorithm. The key properties of surveys are as follows: the size does not grow with the depth, they can be constructed recursively, and they still provide a good bound for the distance between the true conditional distribution and the unconditional distribution at the root. This approach applies to a large class of Markov random field models including randomly generated ones. As an application, we show bounds on the reconstruction threshold for the Potts model on small-degree trees.

Consider [Formula: see text]-colorings of the complete tree of depth [Formula: see text] and branching factor [Formula: see text]. If we fix the coloring of the leaves, for what range of [Formula: see text] is the root uniformly distributed over all [Formula: see text] colors (in the limit [Formula: see text])? This corresponds to the threshold for uniqueness of the infinite-volume Gibbs measure. It is straightforward to show the existence of colorings of the leaves which “freeze” the entire tree when [Formula: see text]. For [Formula: see text], Jonasson proved the root is “unbiased” for any fixed coloring of the leaves, and thus the Gibbs measure is unique. What happens for a typical coloring of the leaves? When the leaves have a nonvanishing influence on the root in expectation, over random colorings of the leaves, reconstruction is said to hold. Nonreconstruction is equivalent to extremality of the free-boundary Gibbs measure. When [Formula: see text], it is straightforward to show that reconstruction is possible (and hence the measure is not extremal). We prove that for [Formula: see text] and [Formula: see text], nonreconstruction holds; i.e., the Gibbs measure is extremal. We prove a strong form of extremality: With high probability over the colorings of the leaves the influence at the root decays exponentially fast with the depth of the tree. Closely related results were also proven recently by Sly. The above strong form of extremality implies that a local Markov chain that updates constant sized blocks has inverse linear entropy constant and hence [Formula: see text] mixing time where [Formula: see text] is the number of vertices of the tree. Extremality on trees and random graphs has received considerable attention recently since it may have connections to the efficiency of local algorithms.

We study the sparsity of real polynomials that sign represent parity on n variables, each of which takes values from some finite subset A of integers. While the degree of such polynomials has been well studied by M. Minsky and S. Papert (1968) and J. Aspnes (1994), relatively little is known about their sparsity. We study this problem using Descartes rule of signs, a classical result in algebra, relating the sparsity of a polynomial to its number of real roots. We show that sign representing parity over {0,1,..., m - 1}/sup n/ with the degree in each variable at most m - 1 requires sparsity at least m/sup n/. We show a bound of (m - l)/sup n/ for weak representations. We show that a tradeoff exists between sparsity and degree, by constructing a sign representation that has higher degree but lower sparsity. In some cases, the difference in sparsities is exponential. We show a lower bound of n(m - 2) + 1 on the sparsity of polynomials of any degree representing parity over {0, 1, ..., m -1 }/sup n/. We prove exact bounds on the sparsity of such polynomials for any two element subset A. We show that for depth-two and-or-not circuits with a threshold gate at the top, the minimum circuit size for a function f equals the minimum sparsity of a polynomial sign representing f over a certain basis. We use this to give a simple proof that such circuits need size (3/2)/sup n/ to compute parity, which improves on previous bounds by M. Goldmann (1997). We also show a tight lower bound of 2/sup n/ for the inner product function over {0,1}/sup n/ /spl times/ {0,1}/sup n/. The main technical tool used is Descartes rule of signs. Our bounds hold for various bases where Descartes sign rule is valid.

We study the problem of representing symmetric Boolean functions as symmetric polynomials over /spl Zopf//sub m/. We show an equivalence between such representations and simultaneous communication protocols. Computing a function f on 0 - 1 inputs with a polynomial of degree d modulo pq is equivalent to a two player simultaneous protocol for computing f where one player is given the first [log/sub p/d] digits of the weight in base q. This reduces the problem of proving bounds on the degree of symmetric polynomials to proving bounds on simultaneous communication protocols. We use this equivalence to show lower bounds of /spl Omega/(n) on symmetric polynomials weakly representing classes of Mod/sub r/ and Threshold functions. We show there exist symmetric polynomials over /spl Zopf//sub m/ of degree o(n) strongly representing Threshold c for c constant, using the fact that the number of solutions of certain exponential Diophantine equations are finite. Conversely, the fact that the degree is o(n) implies that some classes of Diophantine equations can have only finitely many solutions. Our results give simplifications of many previously known results and show that polynomial representations are intimately related to certain questions in number theory.