Properties of stable matchings in the popular random-matching-market model have been studied for over 50 years. In a random matching market, each agent has complete preferences drawn uniformly and independently at random. Wilson (1972), Knuth (1976) and Pittel (1989) proved that in balanced random matching markets, the proposers are matched to their ln nth choice on average. In this paper, we consider competitive markets with n jobs and n+k candidates, and partial lists where each agent only ranks their top d choices. Despite the long history of the problem, the following fundamental question remains unanswered for these generalized markets: what is the tight threshold on list length d that results in a perfect stable matching with high probability? In this paper, we answer this question exactly - we prove a sharp threshold d₀ = ln n ⋅ ln (n+k)/(k+1) on the existence of perfect stable matchings when k = o(n). That is, we show that if d < (1-ε) d₀, then no stable matching matches all jobs; moreover, if d > (1+ ε) d₀, then all jobs are matched in every stable matching with high probability. This bound improves and generalizes recent results by Kanoria, Min and Qian (2021). Furthermore, we extend the line of work studying the effect of imbalance on the expected rank of the proposers (termed the "stark effect of competition"). We establish the regime in unbalanced markets that forces this stark effect to take shape in markets with partial preferences.

In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance δ is a family C of graphs, on a common vertex set of size n, such that if we start with any graph in C, we would have to modify the neighborhoods of at least δ n vertices in order to obtain some other graph in C. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. Yohananov and Yaakobi were the first to construct codes in this metric. We extend their work by showing 1) Combinatorial results determining the optimal rate vs distance trade-off nonconstructively. 2) Graph code analogues of Reed-Solomon codes and code concatenation, leading to positive distance codes for all rates and positive rate codes for all distances. 3) Graph code analogues of dual-BCH codes, yielding large codes with distance δ = 1-o(1). This gives an explicit "graph code of Ramsey graphs". Several recent works, starting with the paper of Alon, Gujgiczer, Körner, Milojević, and Simonyi, have studied more general graph codes; where the symmetric difference between any two graphs in the code is required to have some desired property. Error-correcting graph codes are a particularly interesting instantiation of this concept.

We study the following combinatorial counting and sampling problems: can we sample from the Erdős-Rényi random graph$G(n,p)$conditioned on triangle-freeness? Can we approximate (either algorithmically or with a formula) the probability that$G(n,p)$is triangle-free? These are prototypical instances of forbidden substructure problems ubiquitous in combinatorics. The algorithmic questions are instances of approximate sampling and counting for a hypergraph hard-core model. Estimating the probability that$G(n,p)$has no triangles is a fundamental question in probabilistic combinatorics and one that has led to the development of many important tools in the field. Through the work of several authors, the asymnpotics of the logarithm of this probability are known if$p=o(n^{-1/2})$or if$p=\omega(n^{-1/2})$. The regime$p=\Theta(n^{-1/2})$is more mysterious, as this range witnesses a dramatic change in the the typical structural properties of$G(n,p)$conditioned on triangle-freeness. As we show, this change in structure has a profound impact on the performance of sampling algorithms. We give two different efficient sampling algorithms for this problem (and complementary approximate counting algorithms), one that is efficient when$p < c/\sqrt{n}$and one that is efficient when$p > C/\sqrt{n}$for constants$c, C > 0$. The latter algorithm involves a new approach for dealing with large defects in the setting of sampling from low-temperature spin models. Our algorithmic results can be used to give an asymptotic formula for the logarithm of the probability$G(n,p)$is triangle-free when$p < c/\sqrt{n}$. This algorithmic approach to large deviation problems in random graphs is very different than the known approaches in the suBCRitical regime$p=o(n^{-1/2})$(based on the Poisson paradigm) and in the supercritical regime$p=\omega(n^{-1/2})$(based on regularity lemmas or hypergraph containers); in fact, to the best of our knowledge, no asymptotic formula for the log probability in the regime$p=\Theta(n^{-1/2})$was even conjectured previously.

We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph - in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient counting algorithms typically apply to "high-temperature" problems on bounded-degree graphs, and our contribution is a notable exception as it applies to dense graphs in a low-temperature setting. Our methods give a counting-focused complement to the long line of work in combinatorial optimization showing that CSPs such as Max-Cut and Unique Games are easy on dense graphs via spectral arguments. Our contributions include a novel extension of the method of graph containers that differs considerably from other recent low-temperature algorithms. The additional key insights come from spectral graph theory and have previously been successful in approximation algorithms. As a result, we can overcome some limitations that seem inherent to the aforementioned class of algorithms. In particular, we exploit the fact that dense, regular graphs exhibit a kind of small-set expansion (i.e., bounded threshold rank), which, via subspace enumeration, lets us enumerate small cuts efficiently.

We give algorithms for approximating the partition function of the ferromagnetic Potts model on d-regular expanding graphs. We require much weaker expansion than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models, using extremal graph theory and applications of Karger’s algorithm to counting cuts that may be of independent interest. It is #BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of #BIS are rare. We believe that these methods can shed more light on other important problems such as sub-exponential algorithms for approximate counting problems.

By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. The first algorithm applies to d-regular, bipartite graphs satisfying a weak expansion condition: when d is constant, and the graph is a Ω(log2 d/d)-bipartite expander, we obtain an FPTAS for the number of independent sets. Previously such a result for d > 5 was known only for graphs satisfying the much stronger expansion conditions of random graphs. The second algorithm applies to all d-regular, bipartite graphs, runs in time exp , and outputs a (1 + o(1))-approximation to the number of independent sets.

We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound. In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound. It was previously known that there are Reed-Solomon codes that do not have this property. As an immediate corollary to our main theorem, we obtain better degree bounds on unbalanced expanders that come from Reed-Solomon codes.

Let $\mathcal{H}$ be a $t$-regular hypergraph on $n$ vertices and $m$ edges. Let $M$ be the $m \times n$ incidence matrix of $\mathcal{H}$ and let us denote $λ=\max_{v \perp \overline{1},\|v\| = 1}\|Mv\|$. We show that the discrepancy of $\mathcal{H}$ is $O(\sqrt{t} + λ)$. As a corollary, this gives us that for every $t$, the discrepancy of a random $t$-regular hypergraph with $n$ vertices and $m \geq n$ edges is almost surely $O(\sqrt{t})$ as $n$ grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.

A covering code is a subset C ⊆ {0, 1}nwith the property that any z E {0, 1}nis close to some c E C in Hamming distance. For every c, δ > 0, we show a construction of a family of codes with relative covering radius δ+ε and rate 1-H(δ) with block length at most exp(O((1/c) log(1/c))) for every c> 0. This improves upon a folklore construction which only guaranteed codes of block length exp(1/ε2). The main idea behind this proof is to find a distribution on codes with relatively small support such that most of these codes have good covering properties.

A rainbow q-coloring of a k-uniform hypergraph is a q-coloring of the vertex set such that every hyperedge contains all q colors. We prove that given a rainbow -colorable k-uniform hypergraph, it is NP-hard to find a normal 2-coloring. Previously, this was only known for rainbow -colorable hypergraphs (Guruswami and Lee, SODA 2015). We also study a generalization which we call rainbow (q, p)-coloring, defined as a coloring using q colors such that every hyperedge contains at least p colors. We prove that given a rainbow -colorable k uniform hypergraph, it is NP-hard to find a normal c-coloring for any c = o(k). The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J. Comb. Theory, Ser. B 1990) using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.

Andreev’s Problem is the following: Given an integer d and a subset of S subset F_q x F_q, is there a polynomial y = p(x) of degree at most d such that for every a in F_q, (a,p(a)) in S? We show an AC^0[oplus] lower bound for this problem. This problem appears to be similar to the list recovery problem for degree-d Reed-Solomon codes over F_q which states the following: Given subsets A_1,...,A_q of F_q, output all (if any) the Reed-Solomon codewords contained in A_1 x *s x A_q. In particular, we study this problem when the lists A_1, ..., A_q are randomly chosen, and are of a certain size. This may be of independent interest.

In this note, we prove a tight lower bound on the joint entropy of n unbiased Bernoulli random variables which are n/2-wise independent. For general k-wise independence, we give new lower bounds by adapting Navon and Samorodnitsky's Fourier proof of the `LP bound' on error correcting codes. This counts as partial progress on a problem asked by Gavinsky and Pudlak in [3].

Reed-Muller codes are some of the oldest and most widely studied error-correcting codes, of interest for both their algebraic structure as well as their many algorithmic properties. A recent beautiful result of Saptharishi, Shpilka and Volk [SSV17] showed that for binary Reed-Muller codes of length n and distance d = O(1), one can correct polylog(n) random errors in poly(n) time (which is well beyond the worst-case error tolerance of O(1)). In this paper, we consider the problem of syndrome decoding Reed-Muller codes from random errors. More specifically, given the polylog(n)-bit long syndrome vector of a codeword corrupted in polylog(n) random coordinates, we would like to compute the locations of the codeword corruptions. This problem turns out to be equivalent to a basic question about computing tensor decomposition of random low-rank tensors over finite fields. Our main result is that syndrome decoding of Reed-Muller codes (and the equivalent tensor decomposition problem) can be solved efficiently, i.e., in polylog(n) time. We give two algorithms for this problem: 1. The first algorithm is a finite field variant of a classical algorithm for tensor decomposition over real numbers due to Jennrich. This also gives an alternate proof for the main result of [SSV17]. 2. The second algorithm is obtained by implementing the steps of [SSV17]'s Berlekamp-Welch-style decoding algorithm in sublinear-time. The main new ingredient is an algorithm for solving certain kinds of systems of polynomial equations.