Given samples from two distributions over an n -element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in n , specifically, O ( n 2/3 ε −8/3 log n ), independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than { ε 4/3 n −1/3 /32, εn −1/2 /4}) or large (more than ε ) in ℓ 1 distance. This result can be compared to the lower bound of Ω ( n 2/3 ε −2/3 ) for this problem given by Valiant [2008]. Our algorithm has applications to the problem of testing whether a given Markov process is rapidly mixing. We present sublinear algorithms for several variants of this problem as well.

The Coxeter lattices are a family of lattices containing many of the important lattices in low dimensions. This includesAn,E7,E8and their dualsAn*,E7*, andE8*. We consider the problem of finding a nearest point in a Coxeter lattice. We describe two new algorithms, one with worst case arithmetic complexityO(nlogn) and the other with worst case complexityO(n) wherenis the dimension of the lattice. We show that for the particular latticesAnandAn* the algorithms are equivalent to nearest point algorithms that already exist in the literature.

Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n/sup 2/3//spl epsiv//sup -4/ log n) independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than max(/spl epsiv//sup 2//32/sup 3//spl radic/n,/spl epsiv//4/spl radic/n=)) or large (more than /spl epsiv/) in L/sub 1/-distance. We also give an /spl Omega/(n/sup 2/3//spl epsiv//sup -2/3/) lower bound. Our algorithm has applications to the problem of checking whether a given Markov process is rapidly mixing. We develop sublinear algorithms for this problem as well.

In a previous article, we considered game trees as graphical models. Adopting an evaluation function that returned a probability distribution over values likely to be taken at a given position, we described how to build a model of uncertainty and use it for utility-directed growth of the search tree and for deciding on a move after search was completed. In some games, such as chess and Othello, the same position can occur more than once, collapsing the game tree to a directed acyclic graph (DAG). This induces correlations among the distributions at sibling nodes. This article discusses some issues that arise in extending our algorithms to a DAG. We give a simply described algorithm for correctly propagating distributions up a game DAG, taking account of dependencies induced by the DAG structure. This algorithm is exponential time in the worst case. We prove that it is #P complete to propagate distributions up a game DAG correctly. We suggest how our exact propagation algorithm can yield a fast but inexact heuristic.

We find a large number of "geometric separator theorems" such as: I: Given N disjoint isooriented squares in the plane, there exists a rectangle with /spl les/2N/3 squares inside, /spl les/2N/3 squares outside, and /spl les/(4+0(1))/spl radic/N partly in & out. II: There exists a rectangle that is crossed by the minimal spanning tree of N sites in the plane at /spl les/(4/spl middot/3/sup 1/4/+0(1))/spl radic/N points, having /spl les/2N/3 sites inside and outside. These theorems yield a large number of applications, such as subexponential algorithms for traveling salesman tour and rectilinear Steiner minimal tree in R/sup d/, new point location algorithms, and new upper and lower bound proofs for "planar separator theorems".

probability l/2 in a Monte Carlo sense2 in time The main result of t,his paper is an improvement of Arora's method to find (l+e) approximations for geometric NP-hard problems including the Euclidean Traveling Salesman Problem and t.he Euclidean Steiner Minimum Tree problems.For f&d dimension d and E, our algorithms run in O(NlogN) time.(s\/;i) O(d(+.&)d-')N + O(dN log N) and (sd)"(d)N + (sfi)"(d(~~)d-') log N (4 An interesting byproduct of our work is the definition and consbruction of banyans, a generalization of graph spxmers.A (1 + e)-banyan for a set of points A is a set of points A' and line segments S wit,h endpoints in A U A' such that a 1 + e optimal Steiner Minimum Tree for any subset of A is contained in S. We give a construction for banyans such that the total length of the line segments in S is within a constant factor of the size of t,he minimum spanning tree of A when e and d are fked.space, or in a Las Vegas sense3 in time 2(ad)"(d) N + O(dNlogN), or a deterministic algorithm with runt,ime 2(sd)"(d) N + (sd) o(d)Nlog N, in both of the latter cases consumingIn thii abbreviated paper, we only provide proofs of these results in two dimensions.The full paper on WDS's web page (http://wuu.neci.nj.nec.com/homepages/wds,click"NECItechnical reports") extends the techniques to higher dimensions, proves some new facts and clarifies some old facts about spanners, and also gives approsimation algorithms for minimum matching, edge cover, rectilinear Steiner minimum tree, and minimum a-matching.(s~)'(~)N + 2(8d)o'd' log N space.Our (1+1/s)-approsimation algorithms for NP-hard problems run more slowly than competing esact algorithms when so(l) > N or do(') > log N, otherwise they run more quicldy. New Ingredients

We present an algorithm for testing the inscribability of a trivalent polyhedron, or, equivalently, testing the circumscribability of a simplicial polyhedron. Our algorithm runs in linear time, using only low-precision integer arithmetic. The algorithm is based on a purely combinatorial characterization of inscribable trivalent polyhedra.

We consider the problem of determining which point sets in some given space realise a given distance multiset. Special cases include the “turnpike problem” where the points lie on a line, and the “beltway problem” where the points lie on a loop. Of interest is the algorithmic problem of determining such point sets for a given collection of distances and the combinatorial problem of finding bounds on the maximum number of different solutions. These problems find applications in many fields, including genetics and crystallography.

A table of binary constant weight codes of length n>