Let G be a finite abelian group and A be a subset of $G \times G$ which is corner-free, meaning that there are no $x, y \in G$ and $d \in G \backslash\{0\}$ such that $(x, y),(x+d, y),(x, y+d) \in A$. We prove that \begin{equation*}|A| \leq|G|^{2} \cdot \exp \left(-(\log |G|)^{\Omega{1}}\right)\end{equation*}As a consequence, we obtain polynomial (in the input length) lower bounds on the non-deterministic communication complexity of Exactly-N in the 3-player Number-on-Forehead model. We also obtain the first “reasonable” lower bounds on the coloring version of the 3 -dimensional corners problem, as well as on the non-deterministic communication complexity of Exactly-N in the 4-player Number-on-Forehead model. This is an extended abstract. The full version of the paper can be found at https://arxiv.org/abs/2504.07006.

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 study discrepancy minimization for vectors in ℝn under various settings. The main result is the analysis of a new simple random process in high dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for online vector balancing against oblivious adversaries, resolving several questions posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as a linear time algorithm for logarithmic bounds for the Komlós conjecture.

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.

A numerical semigroup $S$ is called cyclotomic if its corresponding numerical semigroup polynomial, $P_S(x)=(1-x)\sum_{s\in S}x^s$, is expressible as a product of cyclotomic polynomials. Ciolan, García-Sánchez, and Moree [ SIAM J. Discrete Math., 30 (2016), pp. 650--668] conjectured that, for every embedding dimension at least 4, there exists a numerical semigroup which is symmetric but not cyclotomic. We prove this conjecture by giving an infinite class of numerical semigroup families $S_{n, t}$, which, for every fixed $t$, are symmetric but not cyclotomic when $n\ge \max\big(8(t+1)^3,40(t+2)\big)$. We also verify through a finite case check that the numerical semigroup families $S_{n, 0}$ and $S_{n, 1}$ yield noncyclotomic numerical semigroups for every embedding dimension at least 4.