Large language models (LLMs) have been used to generate formal proofs of mathematical theorems in proofs assistants such as Lean. However, we often want to optimize a formal proof with respect to various criteria, depending on its downstream use. For example, we may want a proof to adhere to a certain style, be declaratively structured, or concise. Having suitably optimized proofs is also important for learning tasks, especially since human-written proofs may not optimal for that purpose. To this end, we study a new problem of automated proof optimization: rewriting a proof so that it is correct and optimizes for an arbitrary criterion, such as length or declarativity. As a first method for automated proof optimization, we present ImProver, a large-language-model agent that rewrites proofs to optimize arbitrary user-defined metrics in Lean. We find that naively applying LLMs to proof optimization falls short, and we incorporate various improvements into ImProver, such as the use of symbolic Lean context in a novel Chain-of-States technique, as well as error-correction and retrieval. We test ImProver on rewriting real-world undergraduate, competition, and research-level mathematics theorems, finding that ImProver is capable of rewriting proofs so that they are substantially shorter and more declarative in structure.

Abstract. We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges [Formula: see text] with arbitrary covering requirements [Formula: see text], the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge [Formula: see text] is considered covered by the first time when [Formula: see text] and many of its vertices appear in the ordering. We give a [Formula: see text] approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all [Formula: see text]) of Min Sum Set Cover (MSSC) studied by Feige, Lovász, and Tetali, and improving upon the previous best known bound of [Formula: see text] due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., [Formula: see text]) and [Formula: see text] for every edge [Formula: see text]. We give a [Formula: see text] approximation for MSVC and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best [Formula: see text] approximation of Barenholz, Feige, and Peleg. Finally, we revisit MSSC and consider the [Formula: see text] norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of [Formula: see text] for all [Formula: see text], giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For [Formula: see text], this gives yet another proof of the 4 approximation for MSSC.

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [1], convex geometry [2], fair allocations [3], combinatorics [4], spectral graph theory [5], network design, and random processes [6]. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_{1},\cdots,\ v_{n}\}\subset \mathbb{R}^{d}$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the matrix $\displaystyle \sum_{i\in S}v_{i}v_{i}^{\text{T}}$. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint $(|S|\leq k)$ or matroid constraint $(S$ is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a $r^{O(r)}$-approximation for any matroid of rank $r \leq d$. This improves previous results that give $e^{O(r^{2})}$-approximation algorithms relying on $e^{O(r)}$-approximate estimation algorithms [4], [7] –[9] for any r$\leq$d. All previous results use convex relaxations and their relationship to stable polynomials and strongly $\log$-concave polynomials or non-convex relaxations for the problem [10]. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the $\det(.)$ function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements {ke ∊ Z+ : e ∊ E}, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge e is considered covered by the first time when ke many of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all ke = 1) of min sum set cover (MSSC) studied by Feige, Lovász and Tetali [11], and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan [20]. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph (i.e., |e| = 2) and ke = 1, for every edge e ∊ E. We give a 16/9 ≃ 1.778 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg [6]. (The claimed 1.79 approximation result of Iwata, Tetali and Tripathi [21] for the MSVC turned out have an unfortunate, seemingly unfixable, mistake in it.) Finally, we revisit MSSC and consider the ℓp norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm simultaneously achieves approximation guarantees of (p + 1)1+1/p, for all p ≥ 1, giving another proof of the result of Golovin, Gupta, Kumar and Tangwongsan [13], and showing its tightness up to NP-hardness. For p = 1, this gives yet another proof of the 4 approximation for MSSC.

For d ≥ 2 and all q≥ q 0(d) we give an efficient algorithm to approximately sample from the q-state ferromagnetic Potts and random cluster models on the torus (ℤ / n ℤ ) d for any inverse temperature β≥ 0. This stands in contrast to Markov chain mixing time results: the Glauber dynamics mix slowly at and below the critical temperature, and the Swendsen–Wang dynamics mix slowly at the critical temperature. We also provide an efficient algorithm (an FPRAS) for approximating the partition functions of these models.

A new approach to understanding evolution [Val09], namely viewing it through the lens of computation, has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [CLPV14]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [WVA05], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability. On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game. Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.

Given a planar triangulation, a 3-orientation is an orientation of the internal edges so all internal vertices have out-degree three. Each 3-orientation gives rise to a unique edge coloring known as a Schnyder wood that has proven powerful for various computing and combinatorics applications. We consider natural Markov chains for sampling uniformly from the set of 3-orientations. First, we study a “triangle-reversing” chain on the space of 3-orientations of a fixed triangulation that reverses the orientation of the edges around a triangle in each move. We show that, when restricted to planar triangulations of maximum degree six, this Markov chain is rapidly mixing and we can approximately count 3-orientations. Next, we construct a triangulation with high degree on which this Markov chain mixes slowly. Finally, we consider an “edge-flipping” chain on the larger state space consisting of 3-orientations of all planar triangulations on a fixed number of vertices. We prove that this chain is always rapidly mixing.

Efficiently solving large-scale sparse linear systems is important for robot mapping and navigation. Recently, the subgraph-preconditioned conjugate gradient method has been proposed to combine the advantages of two reigning paradigms, direct and iterative methods, to improve the efficiency of the solver. Yet the question of how to pick a good subgraph is still an open problem. In this paper, we propose a new metric to measure the quality of a spanning tree preconditioner based on support theory. We use this metric to develop an algorithm to find good subgraph preconditioners and apply them to solve the SLAM problem. The results show that although the proposed algorithm is not fast enough, the new metric is effective and resulting subgraph preconditioners significantly improve the efficiency of the state-of-the-art solver.

Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this article, we focus on the problem of sampling random walks efficiently in a distributed network and its applications. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain random walk samples. All previous algorithms that compute a random walk sample of length ℓ as a subroutine always do so naively, that is, in O (ℓ) rounds. The main contribution of this article is a fast distributed algorithm for performing random walks. We present a sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length ℓ in Õ (√ℓ D ) rounds ( Õ hides polylog n factors where n is the number of nodes in the network) with high probability on an undirected network, where D is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive O (ℓ) bound. Furthermore, our algorithm is optimal within a poly-logarithmic factor as there exists a matching lower bound [Nanongkai et al. 2011]. We further extend our algorithms to efficiently perform k independent random walks in Õ (√ k ℓ D + k ) rounds. We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling. Our random-walk algorithms can be used to speed up distributed algorithms in applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algorithm for computing a random spanning tree (RST) in an arbitrary (undirected unweighted) network which runs in Õ (√ mD ) rounds with high probability ( m is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.

Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset S such that its expansion (a.k.a. conductance) is bounded as follows: [ φ(S) def= (w(S,bar{S}))/(min set(w(S), w(bar(S)))) ≤ √(2 λ2) ] where w is the total edge weight of a subset or a cut and λ2 is the second smallest eigenvalue of the normalized Laplacian of the graph. Here we prove the following natural generalization: for any integer k ∈ [n], there exist ck disjoint subsets S1, ..., Sck, such that [ maxi φ(Si) ≤ C √(λk log k) ] where λk is the kth smallest eigenvalue of the normalized Laplacian and c<1,C>0 are suitable absolute constants. Our proof is via a polynomial-time algorithm to find such subsets, consisting of a spectral projection and a randomized rounding. As a consequence, we get the same upper bound for the small set expansion problem, namely for any k, there is a subset S whose weight is at most a O(1/k) fraction of the total weight and φ(S) ≤ C √(λk log k). Both results are the best possible up to constant factors.

The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ|I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree Δ ≥ 3, is a well known computationally challenging problem. More concretely, let λc(TΔ) denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite Δ-regular tree; recent breakthrough results of Dror Weitz (2006) and Allan Sly (2010) have identified λc(TΔ) as a threshold where the hardness of estimating the above partition function undergoes a computational transition. We focus on the well-studied particular case of the square lattice Z2, and provide a new lower bound for the uniqueness threshold, in particular taking it well above λc(T4). Our technique refines and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing (and hence uniqueness) for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to Z2we prove that strong spatial mixing holds for all λ <; 2.3882, improving upon the work of Weitz that held for λ <; 27/16 = 1.6875. Our results imply a fully-polynomial deterministic approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core distribution.

Consider a wireless network of n nodes represented by a (undirected) graph G where an edge (i,j) models the fact that transmissions of i and j interfere with each other, i.e. simultaneous transmissions of i and j become unsuccessful. Hence it is required that at each time instance a set of non-interfering nodes (corresponding to an independent set in G) access the wireless medium. To utilize wireless resources efficiently, it is required to arbitrate the access of medium among interfering nodes properly. Moreover, to be of practical use, such a mechanism is required to be totally distributed as well as simple. As the main result of this paper, we provide such a medium access algorithm. It is randomized, totally distributed and simple: each node attempts to access medium at each time with probability that is a function of its local information. We establish efficiency of the algorithm by showing that the corresponding network Markov chain is positive recurrent as long as the demand imposed on the network can be supported by the wireless network (using any algorithm). In that sense, the proposed algorithm is optimal in terms of utilizing wireless resources. The algorithm is oblivious to the network graph structure, in contrast with the so-called polynomial back-off algorithm by Hastad-Leighton-Rogoff (STOC '87, SICOMP '96) that is established to be optimal for the complete graph and bipartite graphs (by Goldberg-MacKenzie (SODA '96, JCSS '99)).

We consider the performance of two classic approximation algorithms which work by scanning the input and greedily constructing a solution. We investigate whether running these algorithms on a random permutation of the input can increase their performance ratio. We obtain the following results: 1. Johnson's approximation algorithm for MAX-SAT is one of the first approximation algorithms to be rigorously analyzed. It has been shown that the performance ratio of this algorithm is 2/3. We show that when executed on a random permutation of the variables, the performance ratio of this algorithm is improved to 2/3 + c for some c > 0 This resolves an open problem of Chen, Friesen and Zhang [JCSS 1999]. (See also the paper by Poloczek and Schnitger in these proceedings for related results on this algorithm and its variants). 2. Motivated by the above improvement, we consider the performance of the greedy algorithm for MAX-CUT whose performance ratio is 1/2. Our hope was that running the greedy algorithm on a random permutation of the vertices would result in a 1/2 + c approximation algorithm. However, it turns out that in this case the performance of the algorithm remains 1/2. This resolves an open problem of Mathieu and Schudy [SODA 2008].

The classical hard core model from statistical physics, with activity [Formula: see text] and capacity [Formula: see text], on a graph [Formula: see text], concerns a probability measure on the set [Formula: see text] of independent sets of [Formula: see text], with the measure of each independent set [Formula: see text] being proportional to [Formula: see text]. Ramanan et al. [K. Ramanan, A. Sengupta, I. Ziedins and P. Mitra, Adv. Appl. Probab., 34 (2002), pp. 1–27] proposed a generalization of the hard core model as an idealized model of multicasting in communication networks. In this generalization, the multistate hard core model, the capacity [Formula: see text] is allowed to be a positive integer, and a configuration in the model is an assignment of states from [Formula: see text] to [Formula: see text] (the set of nodes of [Formula: see text]) subject to the constraint that the states of adjacent nodes may not sum to more than [Formula: see text]. The activity associated to state [Formula: see text] is [Formula: see text], so that the probability of a configuration [Formula: see text] is proportional to [Formula: see text]. In this work, we consider this generalization when [Formula: see text] is an infinite rooted [Formula: see text]-ary tree and prove rigorously some of the conjectures made by Ramanan et al. In particular, we show that the [Formula: see text] model exhibits a (first-order) phase transition at a larger value of [Formula: see text] than the [Formula: see text] model exhibits its (second-order) phase transition. In addition, for large [Formula: see text] we identify a short interval of values for [Formula: see text] above which the model exhibits phase coexistence and below which there is phase uniqueness. For odd [Formula: see text], this transition occurs in the region of [Formula: see text], while for even [Formula: see text], it occurs around [Formula: see text]. In the latter case, the transition is first-order.

Random instances of constraint satisfaction problems (CSPs) appear to be hard for all known algorithms when the number of constraints per variable lies in a certain interval. Contributing to the general understanding of the structure of the solution space of a CSP in the satisfiable regime, we formulate a set of technical conditions on a large family of random CSPs and prove bounds on three most interesting thresholds for the density of such an ensemble: namely, the satisfiability threshold, the threshold for clustering of the solution space, and the threshold for an appropriate reconstruction problem on the CSPs. The bounds become asymptoticlally tight as the number of degrees of freedom in each clause diverges. The families are general enough to include commonly studied problems such as random instances of Not-All-Equal SAT, [Formula: see text]-XOR formulae, hypergraph 2-coloring, and graph [Formula: see text]-coloring. An important new ingredient is a condition involving the Fourier expansion of clauses, which characterizes the class of problems with a similar threshold structure.

We focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample. We first present a fast sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length l in Õ(√l D) rounds (with high probability) on an undirected network, where D is the diameter of the network. This improves over the previous best algorithm that ran in Õ(l2/3D1/3) rounds (Das Sarma et al., PODC 2009). We further extend our algorithms to efficiently perform k independent random walks in Õ(√kl D + k) rounds. We then show that there is a fundamental difficulty in improving the dependence on l any further by proving a lower bound of Ω(√l/log l + D) under a general model of distributed random walk algorithms. Our random walk algorithms are useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algorithm for computing a random spanning tree (RST) in an arbitrary (undirected) network which runs in Õ(√mD) rounds (with high probability; here m is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.

We prove that the mixing time of the Glauber dynamics for random k-colorings of the complete tree with branching factor b undergoes a phase transition at k = b(1 + ob(1))/ln b. Our main result shows nearly sharp bounds on the mixing time of the dynamics on the complete tree with n vertices for k = Cb/ln b colors with constant C. For C ≥ 1 we prove the mixing time is . On the other side, for C < 1 the mixing time experiences a slowing down, in particular, we prove it is and . The critical point C = 1 is interesting since it coincides (at least up to first order) to the so-called reconstruction threshold which was recently established by Sly. The reconstruction threshold has been of considerable interest recently since it appears to have close connections to the efficiency of certain local algorithms, and this work was inspired by our attempt to understand these connections in this particular setting.

We establish the existence of free energy limits for several sparse random hypergraph models corresponding to certain combinatorial models on Erdos-Renyi (ER) graph G(N,c/N) and random r-regular graph G(N,r).

The spectral profile of a graph is a natural generalization of the classical notion of its Rayleigh quotient. Roughly speaking, given a graph G, for each 0< δ < 1, the spectral profile ΛG(δ) minimizes the Rayleigh quotient (from the variational characterization) of the spectral gap of the Laplacian matrix of G over vectors with support at most δ over a suitable probability measure. Formally, the spectral profile ΛG of a graph G is a function ΛG : [0,1/2] -> R defined as: ΛG(δ) def= minx∈ RVd(supp(x))≤ δ (∑gij (xi-xj)2)/(∑i di xi2) where gij is the weight of the edge (i,j) in the graph, di is the degree of vertex i, and d(\supp(x)) is the fraction of edges incident on vertices within the support of vector x. While the notion of the spectral profile has numerous applications in Markov chain, it is also is closely tied to its isoperimetric profile of a graph. Specifically, the spectral profile is a relaxation for the problem of approximating edge expansion of small sets in graphs. In this work, we obtain an efficient algorithm that yields a log(1/δ)-factor approximation for the value of ΛG(δ). By virtue of its connection to edge-expansion, we also obtain an algorithm for the problem of approximating edge expansion of small linear sized sets in a graph. This problem was recently shown to be intimately connected to the Unique Games Conjecture in [18]. Finally, we extend the techniques to obtain approximation algorithms with similar guarantees for restricted eigenvalue problems on diagonally dominant matrices.

Upper and lower bounds are obtained for the joint entropy of a collection of random variables in terms of an arbitrary collection of subset joint entropies. These inequalities generalize Shannon's chain rule for entropy as well as inequalities of Han, Fujishige, and Shearer. A duality between the upper and lower bounds for joint entropy is developed. All of these results are shown to be special cases of general, new results for submodular functions-thus, the inequalities presented constitute a richly structured class of Shannon-type inequalities. The new inequalities are applied to obtain new results in combinatorics, such as bounds on the number of independent sets in an arbitrary graph and the number of zero-error source-channel codes, as well as determinantal inequalities in matrix theory. A general inequality for relative entropies is also developed. Finally, revealing connections of the results to literature in economics, computer science, and physics are explored.

The discrete logarithm problem asks to solve for the exponent x, given the generator g of a cyclic group G and an element h∈ G such that gx=h. We give the first rigorous proof that Pollard's Kangaroo method finds the discrete logarithm in expected time (3+o(1))√{b-a} for the worst value of x∈[a,b], and (2+o(1))√b-a when x∈uar[a,b]. This matches the conjectured time complexity and, rare among the analysis of algorithms based on Markov chains, even the lead constants 2 and 3 are correct.

We analyze-a fairly standard idealization of Pollard's rho algorithm for finding the discrete logarithm in acyclic group G. It is found that, with high probability, a collision occurs in O(radic( |G|log|G|log log|G|)) steps, not far from the widely conjectured value of Theta(radic|G|). Tins improves upon a recent result of Miller-Venkalesan which showed an upper bound of O(radic|G|log3|G|). Our proof is based on analyzing an appropriate nonreversible, non-lazy random walk on a discrete cycle of (odd) length |G|, and showing that the mixing time of the corresponding walk is O(log|G|log log|G|).

New upper and lower bounds are given for joint entropy of a collection of random variables, in both discrete and continuous settings. These bounds generalize well-known information theoretic inequalities due to Han. A number of applications are suggested, including a new bound on the number of independent sets of a graph that is of interest in discrete mathematics, and a bound on the number of zero-error codes.

We construct a deterministic fully polynomial time approximationscheme (FPTAS) for computing the total number of matchings in abounded degree graph. Additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(O(√n log2n)),where n is the number of vertices.

This paper estimates threshold values of the message-passing iterative decoder for expander codes on discrete-input additive white Gaussian noise (AWGN) channels. We give a new upper bound on the rate of these codes and argue that expander codes are good codes at high rates on this channel.

Motivated by (the rate of information loss or) the rate at which the entropy of an ergodic Markov chain relative to its stationary distribution decays to zero, we study modified versions of the standard logarithmic Sobolev inequality in the discrete setting of finite Markov chains and graphs. These inequalities turn out to be weaker than the standard log-Sobolev inequality, but stronger than the Poincare' (spectral gap) inequality. We also derive a hypercontractivity formulation equivalent to our main modified log-Sobolev inequality which might be of independent interest. Finally we show that, in contrast with the spectral gap, for bounded degree expander graphs various log-Sobolev-type constants go to zero with the size of the graph.

We analyze and solve a game in which a player chooses which of several Markov chains to advance, with the object of minimizing the expected time (or cost) for one of the chains to reach a target state. The solution entails computing (in polynomial time) a function $\gamma$---a variety of "Gittins index"---on the states of the individual chains, the minimization of which produces an optimal strategy. It turns out that $\gamma$ is a useful cousin of the expected hitting time of a Markov chain but is defined, for example, even for random walks on infinite graphs. We derive the basic properties of $\gamma$ and consider its values in some natural situations.

Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z/sup d/. We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L/sup d-1/. In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point.

Naor and Yung (1989) show that a one-bit-compressing universal one-way hash function (UOWHF) can be constructed based on a one-way permutation. This construction can be iterated to build a UOWHF which compresses by /spl epsiv/n bits, at the cost of /spl epsiv/n invocations of the one-way permutation. The show that this construction is not far from optimal, in the following sense, there exists an oracle relative to which there exists a one-way permutation with inversion probability 2/sup -p(n)/ (for any p(n)/spl isin//spl omega/(log n)), but any construction of an /spl epsiv/n-bit-compressing UOWHF. Requires /spl Omega/(/spl radic/n/p(n)) invocations of the one-way permutation, on average. (For example, there exists in this relativized world a one-way permutation with inversion probability n/sup -/spl omega/(1)/, but no UOWHF that involves it fewer than /spl Omega/(/spl radic/n/log n) times.) Thus any proof that a more efficient UOWHF can be derived from a one-way permutation is necessarily non-relativizing; in particular, no provable construction of a more efficient UOWHF can exist based solely on a "black box" one-way permutation. This result can be viewed as a partial justification for the practice of building efficient UOWHFs from stronger primitives (such as collision intractable hash functions), rather than from weaker primitives such as one-way permutations.

Random walks are well known for playing a crucial role in the design of randomized off-line as well as on-line algorithms. In this work we prove some basic identities for ergodic Markov chains (e.g., an interesting characterization of reversibility in Markov chains is obtained in terms of first passage times). Besides providing new insight into random walks on weighted graphs, we show how these identities give us a way of designing competitive randomized on-line algorithms for certain well-known problems.

This paper first presents a Markov chain that exactly models an optical shared-memory packet switch. Without loss in model accuracy, this Markov chain state size is greatly reduced to form a reduced Markov chain (RMC). A simplified construction method is given to make the RMC tractable. Throughput and probability of packet loss derived using the RMC are also presented.

Given an n × n matrix A = [aij], a transversal of A is a set of elements, one from each row and one from each column. A transversal is a latin transversal if no two elements are the same. Erdös and Spencer showed that there always exists a latin transversal in any n × n matrix in which no element appears more than s times, for s⩽ (n — 1)/16. Here we show that, in fact, the elements of the matrix can be partitioned into n disjoint latin transversals, provided n is a power of 2 and no element appears more than εn times for some fixed ε>0. The assumption that n is a power of 2 can be weakened, but at the moment we are unable to prove the theorem for all values of n.

The multiparty communication complexity concerns the least number of bits that must be exchanged among a number of players to collaboratively compute a Boolean function $f ( x_1 , \ldots ,x_k )$, while each player knows at most t inputs for some fixed $t < k$. The relation of the multiparty communication complexity to various hypergraph properties is investigated. Many of these properties are satisfied by random hypergraphs and can be classified by the framework of quasi randomness. Namely, many disparate properties of hypergraphs are shown to be mutually equivalent, and, furthermore, various equivalence classes form a natural hierarchy. In this paper, it is proved that the multiparty communication complexity problems are equivalent to certain hypergraph properties and thereby establish the connections among a large number of combinatorial and computational aspects of hypergraphs or Boolean functions.

A token located at some vertex $v $ of a connected, undirected graph G on n vertices is said to be taking a “random walk” on G if, whenever it is instructed to move, it moves with equal probability to any of the neighbors of $v $. The authors consider the following problem: Suppose that two tokens are placed on G, and at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying to keep the tokens apart as long as possible. What is the expected time M before they meet? The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing. Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound. The authors use a novel potential function argument to show that in the worst case $M = ( \frac{4}{27} + o ( 1 ) )n^3 $.

We show that the token management protocol proposed by Israeli and Jalfon in PODC '90 self-stabilizes in polynomial time.The protocol makes use of accidental meetings in random walks to reduce a multiplicity of tokens to only one.In an abstract setting, our theorem reads as follows:Let two tokens be placed on vertices of a connected, undirected, n-vertex graph.Suppose that at each tick of a clock a "schedule demon" points to one of the tokens, which then takes a random step to a neighboring vertex.Then, regardless of the demon's strategy, the tokens will meet in expected time at most 8n3/27.Our proof technique makes novel use of a potential function on pairs of vertices, a "remoteness" ordering and a random walk identity, all of which may be of independent theoretical interest.