@article{15163, abstract = {For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-colouring such graphs.}, author = {Campbell, Rutger and Hörsch, Florian and Moore, Benjamin}, issn = {0012-365X}, journal = {Discrete Mathematics}, number = {6}, publisher = {Elsevier}, title = {{Decompositions into two linear forests of bounded lengths}}, doi = {10.1016/j.disc.2024.113962}, volume = {347}, year = {2024}, } @article{18937, abstract = {A detailed structural, magnetic as well as dielectric dynamics study is carried out to investigate the influence of Bi3+ on YCrO3. All the samples crystalize in orthorhombic structure with Pnma symmetry and the grains are mostly stretched with Bi. A coexisting tunable fraction of both antiferromagnetic (AFM) and weak ferromagnetic (WFM) phases is acquired by the system down to Low-T. An abnormal negative magnetization in zero field is correlated to the competition among AFM and WFM phases. Maximum magnetization decreases while the coercivity first increases and then decreases with Bi is correlated to the competing effect between the local deformation and Cr–O–Cr exchange interaction. The magnetodielectric coupling with improved permittivity might be associated with the 6s2 lone pair electron of Bi3+. Furthermore, ac-conductivity increases with a decrease in activation energy (0.27–0.11 eV), is explained in the framework of structural model and charge carrier hopping between Cr3+ and Cr4+ ions.}, author = {Ray, Sujata Kumari and Pati, Anupama and Sahoo, Payala and Sahoo, A.K. and Singh, Saurabh and Takeuchi, Tsunehiro and Dash, S.}, issn = {0921-4526}, journal = {Physica B: Condensed Matter}, publisher = {Elsevier}, title = {{Tunable magnetoelectronic properties in Bi3+ substituted YCrO3}}, doi = {10.1016/j.physb.2024.416018}, volume = {685}, year = {2024}, } @misc{17488, abstract = {Behavioural data for Pokusaeva, Satapathy et al. Relevant information can be found in the 'README.txt' file.}, author = {Satapathy, Roshan K and Jösch, Maximilian A and Symonova, Olga and Pokusaeva, Victoria}, keywords = {drosophila, behaviour, locomotion, gap junctions}, publisher = {Institute of Science and Technology Austria}, title = {{Bilateral interactions of optic-flow sensitive neurons coordinate course control in flies}}, doi = {10.15479/AT:ISTA:17488}, year = {2024}, } @inproceedings{18758, abstract = {MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least m/2+(n-1)/4. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., f(k)⋅ O(m). We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and w_MSF(G) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., f(k)⋅ O(m+n).}, author = {Lill, Jonas and Petrova, Kalina H and Weber, Simon}, booktitle = {19th International Symposium on Parameterized and Exact Computation}, isbn = {9783959773539}, issn = {1868-8969}, location = {Egham, United Kingdom}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound}}, doi = {10.4230/LIPIcs.IPEC.2024.2}, volume = {321}, year = {2024}, } @article{18583, abstract = {There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph has a 3-colouring such that for every vertex v, at most half of the out-neighbours of v have the same colour as . As another example, the internal partition conjecture, due to DeVos and to Ban and Linial, states that for every d, all but finitely many d-regular graphs have a partition into two non-empty parts such that for every vertex v, at least half of the neighbours of v lie in the same part as v. We prove several results in this spirit: in particular, two of our results are that the majority colouring conjecture holds for Erdős–Rényi random directed graphs (of any density), and that the internal partition conjecture holds if we permit a tiny number of ‘exceptional vertices’. Our proofs involve a variety of techniques, including several different methods to analyse random recolouring processes. One highlight is a personality-changing scheme: we ‘forget’ certain information based on the state of a Markov chain, giving us more independence to work with.}, author = {Anastos, Michael and Cooley, Oliver and Kang, Mihyun and Kwan, Matthew Alan}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {6}, publisher = {Wiley}, title = {{Partitioning problems via random processes}}, doi = {10.1112/jlms.70010}, volume = {110}, year = {2024}, } @article{17376, abstract = {The inertia bound and ratio bound (also known as the Cvetković bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number α(G) of a graph G in terms of spectral information about a weighted adjacency matrix of G. For both inequalities, given a graph G, one needs to make a judicious choice of weighted adjacency matrix to obtain as strong a bound as possible. While there is a well-established theory surrounding the ratio bound, the inertia bound is much more mysterious, and its limits are rather unclear. In fact, only recently did Sinkovic find the first example of a graph for which the inertia bound is not tight (for any weighted adjacency matrix), answering a longstanding question of Godsil. We show that the inertia bound can be extremely far from tight, and in fact can significantly underperform the ratio bound: for example, one of our results is that for infinitely many n, there is an n-vertex graph for which even the unweighted ratio bound can prove α(G)≤4n3/4, but the inertia bound is always at least n/4. In particular, these results address questions of Rooney, Sinkovic, and Wocjan--Elphick--Abiad.}, author = {Kwan, Matthew Alan and Wigderson, Yuval}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {10}, pages = {3196--3208}, publisher = {London Mathematical Society}, title = {{The inertia bound is far from tight}}, doi = {10.1112/blms.13127}, volume = {56}, year = {2024}, } @article{18655, abstract = {Let Qd be the d-dimensional binary hypercube. We say that P={v1,…,vk} is an increasing path of length k−1 in Qd, if for every i∈[k−1] the edge vivi+1 is obtained by switching some zero coordinate in vi to a one coordinate in vi+1. Form a random subgraph Qdp by retaining each edge in E(Qd) independently with probability p. We show that there is a phase transition with respect to the length of a longest increasing path around p=ed. Let α be a constant and let p=αd. When αe, whp there is a path of length d−2 in Qdp, and in fact, whether it is of length d−2,d−1, or d depends on whether the all-zero and all-one vertices percolate or not.}, author = {Anastos, Michael and Diskin, Sahar and Elboim, Dor and Krivelevich, Michael}, issn = {1083-589X}, journal = {Electronic Communications in Probability}, publisher = {Duke University Press}, title = {{Climbing up a random subgraph of the hypercube}}, doi = {10.1214/24-ECP639}, volume = {29}, year = {2024}, } @article{18951, abstract = {We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes [n] d . These consist of successively switching the dimers along alternating cycles of prescribed (small) lengths. We study the connectivity properties of the dimer configuration space equipped with these transitions. Answering a question of Freire, Klivans, Milet, and Saldanha, we show that in three dimensions any configuration admits an alternating cycle of length at most 6. We further establish that any configuration on [n] d features order n d−2 alternating cycles of length at most 4d−2. We also prove that the dynamics of dimer configurations on the unit hypercube of dimension d is ergodic when switching alternating cycles of length at most 4d−4. Finally, in the planar but non-bipartite case, we show that parallelogram-shaped boxes in the triangular lattice are ergodic for switching alternating cycles of lengths 4 and 6 only, thus improving a result of Kenyon and Rémila, which also uses 8-cycles. None of our proofs make reference to height functions.}, author = {Hartarsky, Ivailo and Lichev, Lyuben and Toninelli, Fabio Lucio}, issn = {2308-5835}, journal = {Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions}, publisher = {EMS Press}, title = {{Local dimer dynamics in higher dimensions}}, doi = {10.4171/aihpd/200}, year = {2024}, } @article{18559, abstract = {We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth.}, author = {Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab and Simkin, Michael}, issn = {1939-8980}, journal = {Annals of Mathematics}, number = {3}, pages = {1059--1156}, publisher = {Princeton University}, title = {{High-girth Steiner triple systems}}, doi = {10.4007/annals.2024.200.3.4}, volume = {200}, year = {2024}, } @article{18938, abstract = {The synthesis of proteins as encoded in the genome depends critically on translational fidelity. Nevertheless, errors inevitably occur, and those that result in reading frame shifts are particularly consequential because the resulting polypeptides are typically nonfunctional. Despite the generally maladaptive impact of such errors, the proper decoding of certain mRNAs, including many viral mRNAs, depends on a process known as programmed ribosomal frameshifting. The fact that these programmed events, commonly involving a shift to the –1 frame, occur at specific evolutionarily optimized “slippery” sites has facilitated mechanistic investigation. By contrast, less is known about the scope and nature of error (i.e., nonprogrammed) frameshifting. Here, we examine error frameshifting by monitoring spontaneous frameshift events that suppress the effects of single base pair deletions affecting two unrelated test proteins. To map the precise sites of frameshifting, we developed a targeted mass spectrometry–based method called “translational tiling proteomics” for interrogating the full set of possible –1 slippage events that could produce the observed frameshift suppression. Surprisingly, such events occur at many sites along the transcripts, involving up to one half of the available codons. Only a subset of these resembled canonical “slippery” sites, implicating alternative mechanisms potentially involving noncognate mispairing events. Additionally, the aggregate frequency of these events (ranging from 1 to 10% in our test cases) was higher than we might have anticipated. Our findings point to an unexpected degree of mechanistic diversity among ribosomal frameshifting events and suggest that frameshifted products may contribute more significantly to the proteome than generally assumed.}, author = {Springstein, Benjamin L and Paulo, Joao A. and Park, Hankum and Henry, Kemardo and Fleming, Eleanor and Feder, Zoë and Harper, J. Wade and Hochschild, Ann}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences of the United States of America}, number = {6}, publisher = {National Academy of Sciences}, title = {{Systematic analysis of nonprogrammed frameshift suppression in E.coli via translational tiling proteomics}}, doi = {10.1073/pnas.2317453121}, volume = {121}, year = {2024}, } @article{18073, abstract = {Conserved signaling cascades monitor protein-folding homeostasis to ensure proper cellular function. One of the evolutionary conserved key players is IRE1, which maintains endoplasmic reticulum (ER) homeostasis through the unfolded protein response (UPR). Upon accumulation of misfolded proteins in the ER, IRE1 forms clusters on the ER membrane to initiate UPR signaling. What regulates IRE1 cluster formation is not fully understood. Here, we show that the ER lumenal domain (LD) of human IRE1α forms biomolecular condensates in vitro. IRE1α LD condensates were stabilized both by binding to unfolded polypeptides as well as by tethering to model membranes, suggesting their role in assembling IRE1α into signaling-competent stable clusters. Molecular dynamics simulations indicated that weak multivalent interactions drive IRE1α LD clustering. Mutagenesis experiments identified disordered regions in IRE1α LD to control its clustering in vitro and in cells. Importantly, dysregulated clustering of IRE1α mutants led to defects in IRE1α signaling. Our results revealed that disordered regions in IRE1α LD control its clustering and suggest their role as a common strategy in regulating protein assembly on membranes.}, author = {Kettel, Paulina and Marosits, Laura and Spinetti, Elena and Rechberger, Michael and Giannini, Caterina and Radler, Philipp and Niedermoser, Isabell and Fischer, Irmgard and Versteeg, Gijs A. and Loose, Martin and Covino, Roberto and Karagöz, G. Elif}, issn = {1460-2075}, journal = {EMBO Journal}, number = {20}, pages = {4668--4698}, publisher = {Embo Press}, title = {{Disordered regions in the IRE1α ER lumenal domain mediate its stress-induced clustering}}, doi = {10.1038/s44318-024-00207-0}, volume = {43}, year = {2024}, } @article{14834, abstract = {Bacteria divide by binary fission. The protein machine responsible for this process is the divisome, a transient assembly of more than 30 proteins in and on the surface of the cytoplasmic membrane. Together, they constrict the cell envelope and remodel the peptidoglycan layer to eventually split the cell into two. For Escherichia coli, most molecular players involved in this process have probably been identified, but obtaining the quantitative information needed for a mechanistic understanding can often not be achieved from experiments in vivo alone. Since the discovery of the Z-ring more than 30 years ago, in vitro reconstitution experiments have been crucial to shed light on molecular processes normally hidden in the complex environment of the living cell. In this review, we summarize how rebuilding the divisome from purified components – or at least parts of it - have been instrumental to obtain the detailed mechanistic understanding of the bacterial cell division machinery that we have today.}, author = {Radler, Philipp and Loose, Martin}, issn = {0171-9335}, journal = {European Journal of Cell Biology}, keywords = {Cell Biology, General Medicine, Histology, Pathology and Forensic Medicine}, number = {1}, publisher = {Elsevier}, title = {{A dynamic duo: Understanding the roles of FtsZ and FtsA for Escherichia coli cell division through in vitro approaches}}, doi = {10.1016/j.ejcb.2023.151380}, volume = {103}, year = {2024}, } @inproceedings{18702, abstract = {In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. }, author = {Anastos, Michael and Auerbach, Benedikt and Baig, Mirza Ahad and Cueto Noval, Miguel and Kwan, Matthew Alan and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z}, booktitle = {22nd International Conference on Theory of Cryptography}, isbn = {9783031780103}, issn = {1611-3349}, location = {Milan, Italy}, pages = {413--443}, publisher = {Springer Nature}, title = {{The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging}}, doi = {10.1007/978-3-031-78011-0_14}, volume = {15364}, year = {2024}, } @article{17475, abstract = {As a discrete analogue of Kac’s celebrated question on ‘hearing the shape of a drum’ and towards a practical graph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by their spectrum (of their adjacency matrix). A striking conjecture in this area, due to van Dam and Haemers, is that ‘almost all graphs are determined by their spectrum’, meaning that the fraction of unlabelled n-vertex graphs which are determined by their spectrum converges to 1 as n → ∞. In this paper, we make a step towards this conjecture, showing that there are exponentially many n-vertex graphs which are determined by their spectrum. This improves on previous bounds (of shape e c √ n ). We also propose a number of further directions of research. }, author = {Koval, Illya and Kwan, Matthew Alan}, issn = {1464-3847}, journal = {Quarterly Journal of Mathematics}, number = {3}, pages = {869--899}, publisher = {Oxford University Press}, title = {{Exponentially many graphs are determined by their spectrum}}, doi = {10.1093/qmath/haae030}, volume = {75}, year = {2024}, } @article{15118, abstract = {Cell division in all domains of life requires the orchestration of many proteins, but in Archaea most of the machinery remains poorly characterized. Here we investigate the FtsZ-based cell division mechanism in Haloferax volcanii and find proteins containing photosynthetic reaction centre (PRC) barrel domains that play an essential role in archaeal cell division. We rename these proteins cell division protein B 1 (CdpB1) and CdpB2. Depletions and deletions in their respective genes cause severe cell division defects, generating drastically enlarged cells. Fluorescence microscopy of tagged FtsZ1, FtsZ2 and SepF in CdpB1 and CdpB2 mutant strains revealed an unusually disordered divisome that is not organized into a distinct ring-like structure. Biochemical analysis shows that SepF forms a tripartite complex with CdpB1/2 and crystal structures suggest that these two proteins might form filaments, possibly aligning SepF and the FtsZ2 ring during cell division. Overall our results indicate that PRC-domain proteins play essential roles in FtsZ-based cell division in Archaea.}, author = {Nußbaum, Phillip and Kureisaite-Ciziene, Danguole and Bellini, Dom and Van Der Does, Chris and Kojic, Marko and Taib, Najwa and Yeates, Anna and Tourte, Maxime and Gribaldo, Simonetta and Loose, Martin and Löwe, Jan and Albers, Sonja Verena}, issn = {2058-5276}, journal = {Nature Microbiology}, number = {3}, pages = {698--711}, publisher = {Springer Nature}, title = {{Proteins containing photosynthetic reaction centre domains modulate FtsZ-based archaeal cell division}}, doi = {10.1038/s41564-024-01600-5}, volume = {9}, year = {2024}, } @article{15330, abstract = {Clathrin-mediated endocytosis (CME) is vital for the regulation of plant growth and development by controlling plasma membrane protein composition and cargo uptake. CME relies on the precise recruitment of regulators for vesicle maturation and release. Homologues of components of mammalian vesicle scission are strong candidates to be part of the scission machinery in plants, but the precise roles of these proteins in this process are not fully understood. Here, we characterised the roles of Plant Dynamin-Related Proteins 2 (DRP2s) and SH3-domain containing protein 2 (SH3P2), the plant homologue to Dynamins’ recruiters, like Endophilin and Amphiphysin, in the CME by combining high-resolution imaging of endocytic events in vivo and characterisation of the purified proteins in vitro. Although DRP2s and SH3P2 arrive similarly late during CME and physically interact, genetic analysis of the sh3p123 triple-mutant and complementation assays with non-SH3P2-interacting DRP2 variants suggests that SH3P2 does not directly recruit DRP2s to the site of endocytosis. These observations imply that despite the presence of many well-conserved endocytic components, plants have acquired a distinct mechanism for CME.}, author = {Gnyliukh, Nataliia and Johnson, Alexander J and Nagel, MK and Monzer, Aline and Babic, David and Hlavata, Annamaria and Alotaibi, SS and Isono, E and Loose, Martin and Friml, Jiří}, issn = {1477-9137}, journal = {Journal of Cell Science}, number = {8}, publisher = {The Company of Biologists}, title = {{Role of dynamin-related proteins 2 and SH3P2 in clathrin-mediated endocytosis in Arabidopsis thaliana}}, doi = {10.1242/jcs.261720}, volume = {137}, year = {2024}, } @article{15172, abstract = {We propose a novel approach to concentration for non-independent random variables. The main idea is to “pretend” that the random variables are independent and pay a multiplicative price measuring how far they are from actually being independent. This price is encapsulated in the Hellinger integral between the joint and the product of the marginals, which is then upper bounded leveraging tensorisation properties. Our bounds represent a natural generalisation of concentration inequalities in the presence of dependence: we recover exactly the classical bounds (McDiarmid’s inequality) when the random variables are independent. Furthermore, in a “large deviations” regime, we obtain the same decay in the probability as for the independent case, even when the random variables display non-trivial dependencies. To show this, we consider a number of applications of interest. First, we provide a bound for Markov chains with finite state space. Then, we consider the Simple Symmetric Random Walk, which is a non-contracting Markov chain, and a non-Markovian setting in which the stochastic process depends on its entire past. To conclude, we propose an application to Markov Chain Monte Carlo methods, where our approach leads to an improved lower bound on the minimum burn-in period required to reach a certain accuracy. In all of these settings, we provide a regime of parameters in which our bound fares better than what the state of the art can provide.}, author = {Esposito, Amedeo Roberto and Mondelli, Marco}, issn = {1557-9654}, journal = {IEEE Transactions on Information Theory}, number = {6}, pages = {3823--3839}, publisher = {IEEE}, title = {{Concentration without independence via information measures}}, doi = {10.1109/TIT.2024.3367767}, volume = {70}, year = {2024}, } @inproceedings{17893, abstract = {Strong data processing inequalities (SDPI) are an important object of study in Information Theory and have been well studied for f -divergences. Universal upper and lower bounds have been provided along with several applications, connecting them to impossibility (converse) results, concentration of measure, hypercontractivity, and so on. In this paper, we study Renyi divergence and the corresponding SDPI constant whose behavior seems to deviate from that of ordinary <1>-divergences. In particular, one can find examples showing that the universal upper bound relating its SDPI constant to the one of Total Variation does not hold in general. In this work, we prove, however, that the universal lower bound involving the SDPI constant of the Chi-square divergence does indeed hold. Furthermore, we also provide a characterization of the distribution that achieves the supremum when is equal to 2 and consequently compute the SDPI constant for Renyi divergence of the general binary channel.}, author = {Jin, Lifu and Esposito, Amedeo Roberto and Gastpar, Michael}, booktitle = {Proceedings of the 2024 IEEE International Symposium on Information Theory}, isbn = {9798350382846}, issn = {2157-8095}, location = {Athens, Greece}, pages = {3178--3183}, publisher = {IEEE}, title = {{Properties of the strong data processing constant for Rényi divergence}}, doi = {10.1109/ISIT57864.2024.10619367}, year = {2024}, } @article{14665, abstract = {We derive lower bounds on the maximal rates for multiple packings in high-dimensional Euclidean spaces. For any N > 0 and L ∈ Z ≥2 , a multiple packing is a set C of points in R n such that any point in R n lies in the intersection of at most L - 1 balls of radius √ nN around points in C . This is a natural generalization of the sphere packing problem. We study the multiple packing problem for both bounded point sets whose points have norm at most √ nP for some constant P > 0, and unbounded point sets whose points are allowed to be anywhere in R n . Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied over finite fields. We derive the best known lower bounds on the optimal multiple packing density. This is accomplished by establishing an inequality which relates the list-decoding error exponent for additive white Gaussian noise channels, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We also derive novel bounds on the list-decoding error exponent for infinite constellations and closed-form expressions for the list-decoding error exponents for the power-constrained AWGN channel, which may be of independent interest beyond multiple packing.}, author = {Zhang, Yihan and Vatedka, Shashank}, issn = {1557-9654}, journal = {IEEE Transactions on Information Theory}, number = {2}, pages = {1008--1039}, publisher = {IEEE}, title = {{Multiple packing: Lower bounds via error exponents}}, doi = {10.1109/TIT.2023.3334032}, volume = {70}, year = {2024}, } @inproceedings{17895, abstract = {We propose a concatenated code construction for a class of discrete-alphabet oblivious arbitrarily varying channels (AVCs) with cost constraints. The code has time and space complexity polynomial in the blocklength n . It uses a Reed-Solomon outer code, logarithmic blocklength random inner codes, and stochastic encoding by permuting the codeword before transmission. When the channel satisfies a condition called strong DS-nonsymmetrizability (a modified version of nonsymmetrizability originally due to Dobrushin and Stambler), we show that the code achieves a rate that for a variety of oblivious AVCs (such as classically studied error/erasure channels) match the known capacities.}, author = {Dey, B. K. and Jaggi, S. and Langberg, M. and Sarwate, A. D. and Zhang, Yihan}, booktitle = {Proceedings of the 2024 IEEE International Symposium on Information Theory }, isbn = {9798350382846}, issn = {2157-8095}, location = {Athens, Greece}, pages = {1586--1591}, publisher = {IEEE}, title = {{Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs}}, doi = {10.1109/ISIT57864.2024.10619362}, year = {2024}, }