More Like this

1. Bounds on the List Size of Successive Cancellation List Decoding

   https://doi.org/10.1109/SPCOM50965.2020.9179593  

   Coskun, Mustafa Cemil; Pfister, Henry D. (July 2020, 2020 International Conference on Signal Processing and Communications (SPCOM))

   Successive cancellation list decoding of polar codes provides very good performance for short to moderate block lengths. However, the list size required to approach the performance of maximum-likelihood decoding is still not well understood theoretically. This work identifies information-theoretic quantities that are closely related to this required list size. It also provides a natural approximation for these quantities that can be computed efficiently even for very long codes. Simulation results are provided for the binary erasure channel as well as the binary-input additive white Gaussian noise channel. 

   more » « less
2. List Ramsey numbers

   https://doi.org/10.1002/jgt.22610  

   Alon, Noga; Bucić, Matija; Kalvari, Tom; Kuperwasser, Eden; Szabó, Tibor (January 2021, Journal of Graph Theory)

   null (Ed.)
3. Layered List Labeling

   https://doi.org/10.1145/3651602  

   Bender, Michael A.; Conway, Alex; Farach-Colton, Martin; Komlos, Hanna; Kuszmaul, William (June 2024, PODS)
4. Sampling List Packings

   https://doi.org/10.4230/LIPIcs.ITCS.2025.24  

   Camrud, Evan; Davies, Ewan; Karduna, Alex; Lee, Holden (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We initiate the study of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted substantial 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. The existence of a list packing implies the existence of a list coloring, but the converse is false. 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 and sampling. In graphs of maximum degree Δ and when the number of colors is at least Ω(Δ²), we give a fully polynomial-time randomized approximation scheme (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. 

   more » « less
5. Five-list-coloring graphs on surfaces III. One list of size one and one list of size two

   https://doi.org/10.1016/j.jctb.2017.06.004  

   Postle, Luke; Thomas, Robin (January 2018, Journal of Combinatorial Theory, Series B)