• Simple near-linear time algorithm for ( 1 + ε ) Δ -edge-coloring that may be of practical interest. • Two-stage edge-coloring procedure reminiscent of palette sparsification for vertex coloring. • New flagging procedure for truncation of Vizing chains. We present a simple ( 1 + ε ) Δ -edge-coloring algorithm for graphs of maximum degree Δ = Ω ( log n / ε ) with running time O ( m log 3 n /ε 3 ). Our algorithm improves upon that of [Duan, He, and Zhang; SODA19], which was the first near-linear time algorithm for this problem. While our results are weaker than the current state-of-the-art, our approach is significantly simpler, both in terms of analysis as well as implementation, and may be of practical interest.

Abstract. We present a randomized algorithm that, given a constant [Formula: see text], outputs a proper [Formula: see text]-edge-coloring of an [Formula: see text]-edge simple graph [Formula: see text] of maximum degree [Formula: see text] in [Formula: see text] time with high probability. This is the first linear-time algorithm for this problem covering the full range of possible values of [Formula: see text]. Indeed, even for edge-coloring with [Formula: see text] colors (i.e., meeting the “greedy” bound), no such linear-time algorithm has been previously known.

Abstract. We study the algorithmic task of finding large independent sets in sparse Erdős–Rényi random [Formula: see text]-uniform hypergraphs on [Formula: see text] vertices having average degree [Formula: see text]. Krivelevich and Sudakov showed that the maximum independent set has density [Formula: see text] in the double limit [Formula: see text] followed by [Formula: see text]. We show that the class of low-degree polynomial algorithms can find independent sets of density [Formula: see text] but no larger. This extends and generalizes earlier results of Gamarnik and Sudan, Limits of local algorithms over sparse random graphs, 2014, Rahman and Virág, Ann. Probab., 45 (2017), pp. 1543–1577, and Wein, Math. Statist. Learn., 4 (2022), pp. 221–251 on graphs, and answers a question of Bal and Bennett. We conjecture that this statistical–computational gap of a multiplicative of [Formula: see text] indeed holds for this problem. Additionally, we explore the universality of this gap by examining [Formula: see text]-partite hypergraphs. A hypergraph [Formula: see text] is [Formula: see text]-partite if there is a partition [Formula: see text] such that each edge contains exactly one vertex from each set [Formula: see text]. We consider the problem of finding large balanced independent sets (independent sets containing the same number of vertices in each partition) in random [Formula: see text]-uniform [Formula: see text]-partite hypergraphs with [Formula: see text] vertices from each partition and average degree [Formula: see text]. We prove that the maximum balanced independent set has density [Formula: see text] asymptotically, matching that of independent sets in ordinary hypergraphs. Furthermore, we prove an analogous computational threshold of [Formula: see text] for low-degree polynomial algorithms, answering a question of the first author. We prove more general statements regarding [Formula: see text] -balanced independent sets (where we specify the proportion of vertices of the independent set contained within each partition). Our results recover and generalize recent work of Perkins and the second author on bipartite graphs. Our results not only pin down the precise threshold for low-degree algorithms in two different settings, but also suggest that these gaps persist for larger uniformities as well as across many models. A somewhat surprising aspect of the gap for balanced independent sets is that the algorithm achieving the lower bound is a simple degree-1 polynomial.

Let ε ∈ ( 0 , 1 ) and n , Δ ∈ N be such that Δ = Ω ( max ⁡ { log ⁡ n ε , ( 1 ε log ⁡ 1 ε ) 2 } ) . Given an n -vertex m -edge simple graph G of maximum degree Δ, we present a randomized O ( m log 3 ⁡ Δ / ε 2 ) -time algorithm that computes a proper ( 1 + ε ) Δ -edge-coloring of G with high probability. This improves upon the best known results for a wide range of the parameters ε , n , and Δ. Our approach combines a flagging strategy from earlier work of the author with a shifting procedure employed by Duan, He, and Zhang for dynamic edge-coloring. The resulting algorithm is simple to implement and may be of practical interest.

In this paper, we consider algorithms for edge-coloring multigraphs G of bounded maximum degree, i.e., Δ (G) = O(1). Shannon's theorem states that any multigraph of maximum degree Δ can be properly edge- colored with ⌊3Δ/2⌋ colors. Our main results include algorithms for computing such colorings. We design deterministic and randomized sequential algorithms with running time O(n log n) and O(n), respectively. This is the first improvement since the O(n2) algorithm in Shannon's original paper, and our randomized algorithm is optimal up to constant factors. We also develop distributed algorithms in the LOCAL model of computation. Namely, we design deterministic and randomized LOCAL algorithms with running time Õ(log5 n) and O(log2 n), respectively. The deterministic sequential algorithm is a simplified extension of earlier work of Gabow et al. in edge-coloring simple graphs. The other algorithms apply the entropy compression method in a similar way to recent work by the author and Bernshteyn, where the authors design algorithms for Vizing's theorem for simple graphs. We also extend those results to Vizing's theorem for multigraphs.

We consider a symmetric mixture of linear regressions with random samples from the pairwise comparison design, which can be seen as a noisy version of a type of Euclidean distance geometry problem. We analyze the expectation-maximization (EM) algorithm locally around the ground truth and establish that the sequence converges linearly, providing an $\ell_\infty$-norm guarantee on the estimation error of the iterates. Furthermore, we show that the limit of the EM sequence achieves the sharp rate of estimation in the $\ell_2$-norm, matching the information-theoretically optimal constant. We also argue through simulation that convergence from a random initialization is much more delicate in this setting, and does not appear to occur in general. Our results show that the EM algorithm can exhibit several unique behaviors when the covariate distribution is suitably structured.

Summary form only given. Most of the task allocation models & algorithms in distributed computing system (DCS) require a priori knowledge of its execution time on the processing nodes. Since the task assignment is not known in advance, this time is quite difficult to estimate. We propose a cluster-based dynamic allocation scheme, in a distributed computing system, which eliminate this time requirement. Further, as opposed to a single task allocation, generally proposed in most of the models, we consider multiple tasks. A fuzzy function is used for both the module clustering and processor clustering. Dynamic invocation of clustering and assignment is considered. Experimental results show the efficacy of the proposed model.