Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window

We study the structure of a uniformly randomly chosen partial order of width 2 on n elements. We show that under the appropriate scaling, the number of incomparable elements converges to the height of a one dimensional Brownian excursion at a uniformly chosen random time in the interval [0, 1], which follows the Rayleigh distribution.     

On the noise sensitivity of monotone functions

It is known that for all monotone functions f : {0, 1}ⁿ → {0, 1}, if x ∈ {0, 1}ⁿ is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with probability ? = n^?α, then P[f(x) ≠ f(y)] < cn^?α+1/2, for some c > 0. Previously, the best construction of monotone functions satisfying P[f_n(x) ≠ f_n(y)] ≥ δ, where 0 < δ < 1/2, required ? ≥ c(δ)n^?α, where α = 1 ? ln 2/ln 3 = 0.36907 …, and c(δ) > 0. We improve this result by achieving for every 0 < δ < 1/2, P[f_n(x) ≠ f_n(y)] ≥ δ, with:

• ? = c(δ)n^?α for any α < 1/2, using the recursive majority function with arity k = k(α);
• ? = c(δ)n^?1/2log^tn for t = log₂ = .3257 …, using an explicit recursive majority function with increasing arities; and
• ? = c(δ)n^?1/2, nonconstructively, following a probabilistic CNF construction due to Talagrand.

We also study the problem of achieving the best dependence on δ in the case that the noise rate ? is at least a small constant; the results we obtain are tight to within logarithmic factors. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 333–350, 2003     

New Coins From Old: Computing With Unknown Bias

Suppose that we are given a function f : (0, 1)→(0,1) and, for some unknown p∈(0, 1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of “heads”). For which functions f is it possible to simulate an f(p)-coin? This question was raised by S. Asmussen and J. Propp. A simple simulation scheme for the constant function f(p)≡1/2 was described by von Neumann (1951); this scheme can be easily implemented using a finite automaton. We prove that in general, an f(p)-coin can be simulated by a finite automaton for all p ∈ (0, 1), if and only if f is a rational function over ℚ. We also show that if an f(p)-coin can be simulated by a pushdown automaton, then f is an algebraic function over ℚ; however, pushdown automata can simulate f(p)-coins for certain nonrational functions such as . These results complement the work of Keane and O’Brien (1994), who determined the functions f for which an f(p)-coin can be simulated when there are no computational restrictions on the simulation scheme. * Supported by a Miller Fellowship. † Supported in part by NSF Grant DMS-0104073 and by a Miller Professorship. ‡ This work is supported under a National Science Foundation Graduate Research Fellowship.     

Quickest online selection of an increasing subsequence of specified size

Given a sequence of independent random variables with a common continuous distribution, we consider the online decision problem where one seeks to minimize the expected value of the time that is needed to complete the selection of a monotone increasing subsequence of a prespecified length n. This problem is dual to some online decision problems that have been considered earlier, and this dual problem has some notable advantages. In particular, the recursions and equations of optimality lead with relative ease to asymptotic formulas for mean and variance of the minimal selection time. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 235–252, 2016     

Standard simplices and pluralities are not the most noise stable

The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discrete noise stability respectively. These two conjectures are natural generalizations of the Gaussian noise stability result by Borell (1985) and the Majority is Stablest Theorem (2004). Here we show that the standard simplex is not the most stable partition in Gaussian space and that Plurality is not the most stable low influence partition in discrete space for every number of parts k ≥ 3, for every value ρ ≠ 0 of the noise and for every prescribed measure for the different parts as long as they are not all equal to 1/k. Our results do not contradict the original statements of the Plurality is Stablest and Standard Simplex Conjectures in their original statements concerning partitions to sets of equal measure. However, they indicate that if these conjectures are true, their veracity and their proofs will crucially rely on assuming that the sets are of equal measures, in stark contrast to Borell’s result, the Majority is Stablest Theorem and many other results in isoperimetric theory. Given our results it is natural to ask for (conjectured) partitions achieving the optimum noise stability.     

Noise correlation bounds for uniform low degree functions

We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by δ are called δ-uniform. The search for such bounds is motivated by their potential applicability to hardness of approximation, derandomization, and additive combinatorics. In our main result we show that $\operatorname{\mathbb {E}}[f_{1}(X_{1}^{1},\ldots,X_{1}^{n}) \ldots f_{k}(X_{k}^{1},\ldots,X_{k}^{n})]$ is close to 0 under the following assumptions:

the vectors $\{ (X_{1}^{j},\ldots,X_{k}^{j}) : 1 \leq j \leq n\}$ are independent identically distributed, and for each j the vector $(X_{1}^{j},\ldots,X_{k}^{j})$ has a pairwise independent distribution;

the functions f _i are uniform;

the functions f _i are of low degree.

We compare our result with recent results by the second author for low influence functions and to recent results in additive combinatorics using the Gowers norm. Our proofs extend some techniques from the theory of hypercontractivity to a multilinear setup.     

Seeded graph matching via large neighborhood statistics

We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge‐correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. We show that it is possible to achieve the information‐theoretic limit of graph sparsity in time polynomial in the number of vertices n. Moreover, we show the number of seeds needed for perfect recovery in polynomial‐time can be as low as in the sparse graph regime (with the average degree smaller than ) and in the dense graph regime, for a small positive constant . Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.     

Spin-exchange dynamical structure factor of the S=1/2 Heisenberg chain

We determine the spin-exchange dynamical structure factor of the Heisenberg spin chain, as is measured by indirect resonant inelastic x-ray scattering (RIXS). We find that two-spin RIXS excitations nearly entirely fractionalize into two-spinon states. These share the same continuum lower bound as single-spin neutron scattering excitations, even if the relevant final states belong to orthogonal symmetry sectors. The RIXS spectral weight is mainly carried by higher-energy excitations, and is beyond the reach of the low-energy effective theories of Luttinger liquid type.     

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s‐Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 ‐ o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n^{1+Ω(1/log log n)}. Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over {±}^Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < ∞ and the Ising model defined on G (n, d/n), there exists a β_d > 0, such that for all β < β_d with probability going to 1 as n →∞, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd?s‐Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub‐graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and β < β_d, where d tanh(β_d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009