Replicability is a fundamental challenge in reinforcement learning (RL), as RL algorithms are empirically observed to be unstable and sensitive to variations in training conditions. To formally address this issue, we study \emph{list replicability} in the Probably Approximately Correct (PAC) RL framework, where an algorithm must return a near-optimal policy that lies in a \emph{small list} of policies across different runs, with high probability. The size of this list defines the \emph{list complexity}. We introduce both weak and strong forms of list replicability: the weak form ensures that the final learned policy belongs to a small list, while the strong form further requires that the entire sequence of executed policies remains constrained. These objectives are challenging, as existing RL algorithms exhibit exponential list complexity due to their instability. Our main theoretical contribution is a provably efficient tabular RL algorithm that guarantees list replicability by ensuring the list complexity remains polynomial in the number of states, actions, and the horizon length. We further extend our techniques to achieve strong list replicability, bounding the number of possib
This work explores the connection between differential privacy (DP) and online learning in the context of PAC list learning. In this setting, a $k$-list learner outputs a list of $k$ potential predictions for an instance $x$ and incurs a loss if the true label of $x$ is not included in the list. A basic result in the multiclass PAC framework with a finite number of labels states that private learnability is equivalent to online learnability [Alon, Livni, Malliaris, and Moran (2019); Bun, Livni, and Moran (2020); Jung, Kim, and Tewari (2020)]. Perhaps surprisingly, we show that this equivalence does not hold in the context of list learning. Specifically, we prove that, unlike in the multiclass setting, a finite $k$-Littlestone dimensio--a variant of the classical Littlestone dimension that characterizes online $k$-list learnability--is not a sufficient condition for DP $k$-list learnability. However, similar to the multiclass case, we prove that it remains a necessary condition. To demonstrate where the equivalence breaks down, we provide an example showing that the class of monotone functions with $k+1$ labels over $\mathbb{N}$ is online $k$-list learnable, but not DP $k$-list lear
Komjath studied the list chromatic number of infinite graphs and introduced the notion of restricted list chromatic number. For a graph $X=(V_X,E_X)$ and a cardinal $κ$, we say that $X$ is restricted list colorable for $κ$ if for every $L:V_X\to[κ]^κ$ there is a choice function $c$ of $L$ such that $c(v) eq c(w)$ whenever ${v,w}\in E_X$. In this paper, we discuss a variation, stationary list colorability for $κ$, obtained by replacing $[κ]^κ$ with the set of all stationary subsets of $κ$. We compare the stationary list colorability with other coloring properties. Among other things, we prove that the stationary list colorability is essentially different from other coloring properties including the restricted list colorability. We also prove the consistency result showing that for some $κ<λ$, restricted and stationary list colorability at $κ$ do not imply the corresponding properties at $λ$.
In a recent breakthrough [BGM23, GZ23, AGL23], it was shown that randomly punctured Reed-Solomon codes are list decodable with optimal list size with high probability, i.e., they attain the Singleton bound for list decoding [ST20, Rot22, GST22]. We extend this result to the family of polynomial ideal codes, a large class of error-correcting codes which includes several well-studied families of codes such as Reed-Solomon, folded Reed-Solomon, and multiplicity codes. More specifically, similarly to the Reed-Solomon setting, we show that randomly punctured polynomial ideal codes over an exponentially large alphabet exactly achieve the Singleton bound for list-decoding; while such codes over a polynomially large alphabet approximately achieve it. Combining our results with the efficient list-decoding algorithm for a large subclass of polynomial ideal codes of [BHKS21], implies as a corollary that a large subclass of polynomial ideal codes (over random evaluation points) is efficiently list decodable with optimal list size. To the best of our knowledge, this gives the first family of codes that can be efficiently list decoded with optimal list size (for all list sizes), as well as the f
Given a list assignment for a graph, list packing asks for the existence of multiple pairwise disjoint list colorings of the graph. Several papers have recently appeared that study the existence of such a packing of list colorings. Formally, a proper $L$-packing of size $k$ of a graph $G$ is a set of $k$ pairwise disjoint proper $L$-colorings of $G$ where $L$ is a list assignment of colors to the vertices of $G$. In this note, we initiate the study of counting such packings of list colorings of a graph. We define $P_\ell^\star(G,q,k)$ as the guaranteed number of proper $L$-packings of size $k$ of $G$ over all list assignments $L$ that assign $q$ colors to each vertex of $G$, and we let $P^\star(G,q,k)$ be its classical coloring counterpart. We let $P_\ell^\star(G,q)= P_\ell^\star(G,q,q)$ so that $P_\ell^\star(G,q)$ is the enumerative function for the previously studied list packing number $χ_\ell^\star(G)$. Note that the chromatic polynomial of $G$, $P(G,q)$, is $P^\star(G,q,1)$, and the list color function of $G$, $P_\ell(G,q)$, is $P_\ell^\star(G,q,1)$. Inspired by the well-known behavior of the list color function and the chromatic polynomial, we make progress towards the questi
Given a countable Turing ideal $\mathcal{I} \subseteq ω^ω$, we say that $x$ is a list (resp. weak list) of $\mathcal{I}$ if $\mathcal{I}=\{x^{[n]} : n \in ω\}$ (resp. if $\mathcal{I} \subseteq \{x^{[n]} :n \in ω\}$). We show that, for several natural ideals $\mathcal{I}$, $x$ computes a list of $\mathcal{I}$ if and only if it computes a function dominating all the functions in $\mathcal{I}$. On the other hand, we provide reals which are $\mathsf{HYP}$-strongly null engulfing (and hence $\mathsf{HYP}$-dominating, by results of Greenberg, Kuyper and Turetsky) but which cannot compute a weak list for $\mathsf{HYP}$, solving a problem left open in a recent paper by Greenberg and the second author. This result can be generalized to any countable ideal which is downward closed under $\leq_{\mathsf{HYP}}$. We also give a characterization of reals which compute a list of $\mathsf{HYP}$: $x$ computes a list of $\mathsf{HYP}$ if and only if $x$ is $\mathsf{HYP}$-dominating and $\mathcal{O}$ is $Σ^0_2(x)$.
We study the problem of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted a lot of attention. For list packing the setup is similar but we seek a full decomposition of the lists of colors into pairwise-disjoint proper list colorings. In particular, the existence of a list packing implies the existence of a list coloring. Recent works on list packing have focused on existence or extremal results of on the number of list packings, but here we turn to the algorithmic aspects of counting. In graphs of maximum degree $Δ$ and when the number of colors is at least $Ω(Δ^2)$, we give an FPRAS based on rapid mixing of a natural Markov chain (the Glauber dynamics) which we analyze with the path coupling technique. Some motivation for our work is the investigation of an atypical spin system, one where the number of spins for each vertex is much larger than the graph degree.
List-decoding and list-recovery are important generalizations of unique decoding that received considerable attention over the years. However, the optimal trade-off among list-decoding (resp. list-recovery) radius, list size, and the code rate are not fully understood in both problems. This paper takes a step towards this direction when the list size is a given constant and the alphabet size is large (as a function of the code length). We prove a new Singleton-type upper bound for list-decodable codes, which improves upon the previously known bound by roughly a factor of $1/L$, where $L$ is the list size. We also prove a Singleton-type upper bound for list-recoverable codes, which is to the best of our knowledge, the first such bound for list-recovery. We apply these results to obtain new lower bounds that are optimal up to a multiplicative constant on the list size for list-decodable and list-recoverable codes with rates approaching capacity. Moreover, we show that list-decodable \emph{nonlinear} codes can strictly outperform list-decodable linear codes. More precisely, we show that there is a gap for a wide range of parameters, which grows fast with the alphabet size, between the
We prove that Reed-Solomon (RS) codes with random evaluation points are list recoverable up to capacity with optimal output list size, for any input list size. Namely, given an input list size $\ell$, a designated rate $R$, and any $\varepsilon > 0$, we show that a random RS code is list recoverable from $1-R-\varepsilon$ fraction of errors with output list size $L = O(\ell/\varepsilon)$, for field size $q=\exp(\ell,1/\varepsilon) \cdot n^2$. In particular, this shows that random RS codes are list recoverable beyond the "list recovery Johnson bound". Such a result was not even known for arbitrary random linear codes. Our technique follows and extends the recent line of work on list decoding of random RS codes, specifically the works of Brakensiek, Gopi, and Makam (STOC 2023), and of Guo and Zhang (FOCS 2023).
The HWO Target Stars and Systems 2025 (TSS25) list is a community-developed catalog of potential stellar targets for the Habitable Worlds Observatory (HWO) in its survey to directly image Earth-sized planets in the habitable zone. The TSS25 list categorizes potential HWO targets into priority tiers based on their likelihood to be surveyed and the necessity of obtaining observations of their stellar properties prior to the launch of the mission. This target list builds upon previous efforts to identify direct imaging targets and incorporates the results of multiple yield calculations assessing the science return of current design concepts for HWO. The TSS25 list identifies a sample of target stars that have a high probability to be observed by HWO (Tiers 1 and 2), independent of assumptions about the mission's final architecture. These stars should be the focus of community precursor science efforts in order to mitigate risks and maximize the science output of HWO. This target list is publicly available and is a living catalog that will be continually updated leading up to the mission.
A family of error-correcting codes is list-decodable from error fraction $p$ if, for every code in the family, the number of codewords in any Hamming ball of fractional radius $p$ is less than some integer $L$ that is independent of the code length. It is said to be list-recoverable for input list size $\ell$ if for every sufficiently large subset of codewords (of size $L$ or more), there is a coordinate where the codewords take more than $\ell$ values. The parameter $L$ is said to be the "list size" in either case. The capacity, i.e., the largest possible rate for these notions as the list size $L \to \infty$, is known to be $1-h_q(p)$ for list-decoding, and $1-\log_q \ell$ for list-recovery, where $q$ is the alphabet size of the code family. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below, $ε> 0$ is the gap to capacity). (1) A random linear code of rate $1 - \log_q(\ell) - ε$ requires list size $L \ge \ell^{Ω(1/ε)}$ for list-recovery from input list size $\ell$. This is surprisingly in contrast to compl
There has been a recent interest in understanding and characterizing the sample complexity of list learning tasks, where the learning algorithm is allowed to make a short list of $k$ predictions, and we simply require one of the predictions to be correct. This includes recent works characterizing the PAC sample complexity of standard list classification and online list classification. Adding to this theme, in this work, we provide a complete characterization of list PAC regression. We propose two combinatorial dimensions, namely the $k$-OIG dimension and the $k$-fat-shattering dimension, and show that they characterize realizable and agnostic $k$-list regression respectively. These quantities generalize known dimensions for standard regression. Our work thus extends existing list learning characterizations from classification to regression.
A strong edge-coloring of a graph is a proper edge-coloring, in which the edges of every path of length 3 receive distinct colors; in other words, every pair of edges at distance at most 2 must be colored differently. The least number of colors needed for a strong edge-coloring of a graph is the strong chromatic index. We consider the list version of the coloring and prove that the list strong chromatic index of graphs with maximum degree 3 is at most 10. This bound is tight and improves the previous bound of 11 colors. We also consider the question whether the strong chromatic index and the list strong chromatic index always coincide. We answer it in negative by presenting an infinite family of graphs for which the two invariants differ. For the special case of the Petersen graph, we show that its list strong chromatic index equals 7, while its strong chromatic index is 5. Up to our best knowledge, this is the first known edge-coloring for which there are graphs with distinct values of the chromatic index and its list version. In relation to the above, we also initiate the study of the list version of the normal edge-coloring. A normal edge-coloring of a cubic graph is a proper ed
We extend the notion of list decoding to {\em ratio list decoding} which involves a list decoder whose list size is specified as a function of the number of messages $M_n$ and the block length $n$. We present necessary and sufficient conditions on $M_n$ for the existence of code sequences which enable reliable list decoding with respect to the desired list size $L(M_n,n)$. It is shown that the ratio-capacity, defined as the supremum of achievable normalized logarithms of the ratio $r(M_n,n)=M_n/L(M_n,n)$ is equal to the Shannon channel capacity $C$, for both stochastic and deterministic encoding. Allowing for random list size, we are able to deduce some properties of identification codes, where the decoder's output can be viewed as a list of messages corresponding to decision regions that include the channel output. We further address the regime of mismatched list decoding, in which the list constitutes of the codewords that accumulate the highest score values (jointly with the channel output) according to some given function. We study the case of deterministic encoding and mismatched ratio list decoding. We establish similar necessary and sufficient conditions for the existence of
A falling rule list is a probabilistic decision list for binary classification, consisting of a series of if-then rules with antecedents in the if clauses and probabilities of the desired outcome ("1") in the then clauses. Just as in a regular decision list, the order of rules in a falling rule list is important -- each example is classified by the first rule whose antecedent it satisfies. Unlike a regular decision list, a falling rule list requires the probabilities of the desired outcome ("1") to be monotonically decreasing down the list. We propose an optimization approach to learning falling rule lists and "softly" falling rule lists, along with Monte-Carlo search algorithms that use bounds on the optimal solution to prune the search space.
We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon codes can be made to run in $\tilde{O}(n)$ time. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every $ε>0$, and rate $r \in (0,1)$, there exist explicit families of these codes that have rate $r$ and can be list decoded from a $(1-r-ε)$ fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in $\tilde{O}(n)$, where $n$ is the block-length of the code. Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a $\tilde{O}(n)$ time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design $\tilde{O}(n)$ time algorithms for two natural algebraic problems: given a $(m+2
Equitable list arboricity, introduced by Zhang in 2016, generalizes the notion of equitable list coloring by requiring the subgraph induced by each color class to be acyclic (instead of edgeless) in addition to the usual upper bound on the size of each color class. Graph $G$ is equitably $k$-list arborable if an equitable, arborable list coloring of $G$ exists for every list assignment for $G$ that associates with each vertex in $G$ a list of $k$ available colors. Zhang conjectured that any graph $G$ is equitably $k$-list arborable for each $k$ satisfying $k \geq \lceil (1+Δ(G))/2 \rceil$. We verify this conjecture for powers of cycles by applying a new lemma which is a general tool for extending partial equitable, arborable list colorings. We also propose a stronger version of Zhang's Conjecture for certain connected graphs: any connected graph $G$ is equitably $k$-list arborable for each $k$ satisfying $k \geq \lceil Δ(G)/2 \rceil$ provided $G$ is neither a cycle nor a complete graph of odd order. We verify this stronger version of Zhang's Conjecture for powers of paths, 2-degenerate graphs, and certain other graphs. We also show that if $G$ is equitably $k$-list arborable it doe
We define two classes of functions, called regular (respectively, first-order) list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pairs of lists, etc. The definition is in the style of regular expressions: the functions are constructed by starting with some basic functions (e.g. projections from pairs, or head and tail operations on lists) and putting them together using four combinators (most importantly, composition of functions). Our main results are that first-order list functions are exactly the same as first-order transductions, under a suitable encoding of the inputs; and the regular list functions are exactly the same as MSO-transductions.
Let $H$ be an undirected graph. In the List $H$-Homomorphism Problem, given an undirected graph $G$ with a list constraint $L(v) \subseteq V(H)$ for each variable $v \in V(G)$, the objective is to find a list $H$-homomorphism $f:V(G) \to V(H)$, that is, $f(v) \in L(v)$ for every $v \in V(G)$ and $(f(u),f(v)) \in E(H)$ whenever $(u,v) \in E(G)$. We consider the following problem: given a map $f:V(G) \to V(H)$ as an oracle access, the objective is to decide with high probability whether $f$ is a list $H$-homomorphism or \textit{far} from any list $H$-homomorphisms. The efficiency of an algorithm is measured by the number of accesses to $f$. In this paper, we classify graphs $H$ with respect to the query complexity for testing list $H$-homomorphisms and show the following trichotomy holds: (i) List $H$-homomorphisms are testable with a constant number of queries if and only if $H$ is a reflexive complete graph or an irreflexive complete bipartite graph. (ii) List $H$-homomorphisms are testable with a sublinear number of queries if and only if $H$ is a bi-arc graph. (iii) Testing list $H$-homomorphisms requires a linear number of queries if $H$ is not a bi-arc graph.
In this paper uniquely list colorable graphs are studied. A graph G is called to be uniquely k-list colorable if it admits a k-list assignment from which G has a unique list coloring. The minimum k for which G is not uniquely k-list colorable is called the M-number of G. We show that every triangle-free uniquely vertex colorable graph with chromatic number k+1, is uniquely k-list colorable. A bound for the M-number of graphs is given, and using this bound it is shown that every planar graph has M-number at most 4. Also we introduce list criticality in graphs and characterize all 3-list critical graphs. It is conjectured that every $χ_\ell$-critical graph is $χ'$-critical and the equivalence of this conjecture to the well known list coloring conjecture is shown.