Abstract. We give an online algorithm that with high probability computes a [Formula: see text] edge coloring on a graph [Formula: see text] with maximum degree [Formula: see text] under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar-Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrence based approach for arguing correlation decay.

We derive an explicit distribution for the threshold sequence of the symmetric binary perceptron with Gaussian disorder, proving that the critical window is of constant width.

A celebrated theorem of Spencer states that for every set system S1,…, Sm ⊆ [n], there is a coloring of the ground set with {±1} with discrepancy . We provide an algorithm to find such a coloring in near input-sparsity time Õ(n + Σi=1m|Si|)

Let$X$be a random vector valued in$\mathbb {R}^{m}$such that$\|X\|_{2} \le 1$almost surely. For every$k\ge 3$, we show that there exists a sigma algebra$\mathcal {F}$generated by a partition of$\mathbb {R}^{m}$into$k$sets such that$\|\mathrm {Cov}(X) - \mathrm {Cov}(\mathbb {E}[X\mid \mathcal {F}]) \|_{\mathrm {F}} \lesssim \frac {1}{\sqrt {\log {k}}}$. This is optimal up to the implicit constant and improves on a previous bound due to Boedihardjo, Strohmer, and Vershynin. Our proof provides an efficient algorithm for constructing$\mathcal {F}$and leads to improved accuracy guarantees for$k$-anonymous or differentially private synthetic data. We also establish a connection between the above problem of minimizing the covariance loss and the pinning lemma from statistical physics, providing an alternate (and much simpler) algorithmic proof in the important case when$X \in \{\pm 1\}^{m}/\sqrt {m}$almost surely.

In this note, we design a discrete random walk on the real line which takes steps 0,±1 (and one with steps in {±1,2}) where at least 96% of the signs are ±1 in expectation, and which has 𝒩(0,1) as a stationary distribution. As an immediate corollary, we obtain an online version of Banaszczyk’s discrepancy result for partial colorings and ±1,2 signings. Additionally, we recover linear time algorithms for logarithmic bounds for the Komlós conjecture in an oblivious online setting.

We give an FPTAS for computing the number of matchings of size k in a graph G of maximum degree Δ on n vertices, for all k ≤ (1−δ)m*(G), where δ>0 is fixed and m*(G) is the matching number of G, and an FPTAS for the number of independent sets of size k ≤ (1−δ) αc(Δ) n, where αc(Δ) is the NP-hardness threshold for this problem. We also provide quasi-linear time randomized algorithms to approximately sample from the uniform distribution on matchings of size k ≤ (1−δ)m*(G) and independent sets of size k ≤ (1−δ)αc(Δ)n.

We give an online algorithm that with high probability computes a (e/e−1 + o(1))Δ edge coloring on a graph G with maximum degree Δ = ω(logn) under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar-Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrences based approach for arguing correlation decay.

We present a randomized algorithm which takes as input an undirected graph G on n vertices with maximum degree Δ, and a number of colors k ≥ (8/3 + oΔ(1))Δ, and returns – in expected time Õ(nΔ2logk) – a proper k-coloring of G distributed perfectly uniformly on the set of all proper k-colorings of G. Notably, our sampler breaks the barrier at k = 3Δ encountered in recent work of Bhandari and Chakraborty [STOC 2020]. We also discuss how our methods may be modified to relax the restriction on k to k ≥ (8/3 − є0)Δ for an absolute constant є0 > 0.