Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique often leads to randomized algorithms with no clear path to derandomization because the analyses rely on a union bound over exponentially many events. In this work, we revisit this goal of derandomizing randomized sampling in graphs. We give several results related to bounded-independence edge subsampling, and in the process of doing so, generalize several of the results of Alon and Nussboim (FOCS 2008), who studied bounded-independence analogues of random graphs (which can be viewed as edge subsamples of the complete graph). Most notably, we show: 1) O(log(m))-wise independence suffices for preserving connectivity when sampling at rate 1/2 in a graph with minimum cut ≥ κ log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant κ). 2) O(log(m))-wise (1/poly(m))-almost independence suffices for ensuring cycle-freeness when sampling at rate 1/2 in a graph with minimum cycle length ≥ κ log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant κ). 3) If we relax to arbitrary distributions, we show there is an explicit distribution with marginals ≤ 1/2 generated using O(log(m)log log(m)) random bits such that in a graph with minimum cut ≥ κ log(m) (for a sufficiently large constant κ), a sample from the distribution has is still connected with probability 1- 1/poly(m). To demonstrate the utility of our results, we revisit the classic problem of using parallel algorithms to find graphic matroid bases, first studied in the work of Karp, Upfal, and Wigderson (FOCS 1985). In this regime, we show that the optimal algorithms of Khanna, Putterman, and Song (arxiv 2025) can be explicitly derandomized while maintaining near-optimality.

In this work11Find the full version here: https://arxiv.org/pdf/2411.16596., we present a generalization of the linear operator family of codes that captures many codes that achieve list decoding capacity. Linear operator (LO) codes were introduced by Bhandari, Harsha, Kumar, and Sudan [BHKS24] as a way to capture capacity-achieving codes. In their framework, a code is specified by a collection of linear operators that are applied to a message polynomial and then evaluated at a specified set of evaluation points. We generalize this idea in a way that can be applied to bivariate message polynomials, getting what we call bivariate linear operator (B-LO) codes. We show that bivariate linear operator codes capture even more capacity-achieving codes, including permuted product codes introduced by Berman, Shany, and Tamo [BST24]. These codes work with bivariate message polynomials, which is why our generalization is necessary to capture them as a part of the linear operator framework. Similarly to the initial paper on linear operator codes, we present sufficient conditions for a bivariate linear operator code to be list decodable. Using this characterization, we are able to derive the theorem characterizing list-decodability of LO codes as a specific case of our theorem for B-LO codes. We also apply this theorem to show that permuted product codes are list decodable up to capacity, thereby unifying this result with those of known list-decodable LO codes, including Folded ReedSolomon, Multiplicity, and Affine Folded Reed-Solomon codes.