Multiset Deletion Codes: Cyclic Syndrome Constructions, Bounds, and Exact Results
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Multiset Deletion Codes".
Jane: Here's the gist of the paper. Multiset deletion codes are studied in the space of length-n multisets over a qary alphabet to understand coding-theoretic frameworks fundamentally different from classical sequence-based deletion models The explicit cyclic Sidon-type construction provides a universal, elementary, deletionspecific method for creating multiset t-deletioncorrecting codes with logarithmic redundancy in t when q is fixed The Core Construction and its Properties The main contribution is an explicit cyclic Sidon-type construction for q-ary multiset t-deletioncorrecting codes defined by a single congruence modulo m = t(t + 1)q−2 + 1 This construction assigns weights 1, t + 1, (t + 1)2,..., (t + 1)q−2, 0 (mod t(t + 1)q−2 + 1) to the alphabet symbols and imposes a single congruence constraint It works for every pair (q, t), with no prime-power or characteristic assumptions The construction is linear in the sense of Kovaˇcevi´c and Tan
8: Syndrome Class Analysis and Optimality The paper proves an asymptotic balance theorem for the syndrome classes, showing that for every fixed residue a modulo m, Cq(a) = 1/m (n + q − 1) / (q − 1) + Oq,t(n 2−2+ceil((q−1)/2))−1 This implies that asymptotically, choosing any convenient residue is as good as searching for a largest syndrome class The single-deletion case shows that the natural sum-modulo construction is asymptotically optimal for every fixed alphabet size q Comparison with Alternative Constructions The cyclic construction is compared against related Sidon-type constructions, including Varshamov power-sum constructions and Bose–Chowla type finite-field constructions The comparison shows that finite-field Sidon constructions are stronger in the large-alphabet, fixed-radius regime, whereas the cyclic deletionspecific construction is universal and has logarithmic redundancy in t when q is fixed Extremal Regimes and Bounds The paper analyzes extremal deletion regimes where t is close to n, yielding exact results such as Sq(n, n − 1) = q For t = n − 2, it reduces the problem to an ordinary intersection problem for squarefree codewords and obtains Sq(n, n−2) = q when n ⩾ q + 1 The comparison of general upper bounds shows that the explicit Kovaˇcevi´c–Tan bound is strongest in the standard fixed-q, t, n → ∞ regime Finite-Length Optimality and Conjectures For the single-deletion case, exact values for q = 3 and q = 4 are obtained, including uniqueness results for optimal codes in relevant parameter ranges These exact results show that the natural sum-modulo construction is not always finite-length optimal; for q = 3 there are two exceptional blocklengths n = 2, 4 Conjectures are formulated for q = 5 and prime alphabets suggesting the sum-modulo construction is optimal for all sufficiently large blocklengths The paper concludes that the cyclic construction is a universal, elementary, deletionspecific method whose strongest regime is fixed alphabet size, particularly when t grows and finite-field Sidon constructions are less natural.
Tom: The main takeaway is that while natural one-syndrome constructions are asymptotically optimal for fixed q, they may fail to be exactly optimal at small blocklengths or under the wrong choice of additive group Pruning redundant reasoning tokens The explicit cyclic Sidon-type construction provides a universal, elementary, deletionspecific method for creating multiset t-deletioncorrecting codes with logarithmic redundancy in t when q is fixed The construction is linear in the sense of Kovaˇcevi´c and Tan
8: How the training signal is built The construction assigns weights 1, t + 1, (t + 1)2,..., (t + 1)q−2, 0 (mod t(t + 1)q−2 + 1) to the alphabet symbols and imposes a single congruence constraint This construction is linear in the sense of Kovaˇcevi´c and Tan
8: Where the gains come from The comparison shows that finite-field and power-sum constructions are stronger when the alphabet size is large and the deletion radius is fixed The cyclic construction has logarithmic dependence on t for fixed alphabet size and avoids finite-field parameter restrictions The explicit Kovaˇcevi´c–Tan bound is strongest in the standard fixedq, t, n → ∞ regime The construction is universal, elementary, deletionspecific, and particularly efficient when q is fixed and t grows Pruning redundant reasoning tokens The paper proves an asymptotic balance theorem for the syndrome classes, showing that for every fixed residue a modulo m, Cq(a) = 1/m (n + q − 1) / (q − 1) + Oq,t(n 2−2+ceil((q−1)/2))−1 This implies that asymptotically, choosing any convenient residue is as good as searching for a largest syndrome class How the training signal is built The construction assigns weights 1, t + 1, (t + 1)2,..., (t + 1)q−2, 0 (mod t(t + 1)q−2 + 1) to the alphabet symbols and imposes a single congruence constraint Where the gains come from The construction is linear in the sense of Kovaˇcevi´c and Tan
8: The comparison shows that finite-field and power-sum constructions are stronger when the alphabet size is large and the deletion radius is fixed The cyclic construction has logarithmic dependence on t for fixed alphabet size and avoids finite-field parameter restrictions How the training signal is built The construction assigns weights 1, t + 1, (t + 1)2,...
Title and authors: Tom: So we're looking at this paper now called "Multiset Deletion Codes: Cyclic Syndrome Constructions, Bounds, and Exact Results." It’s by Kreindel and Barouch Essayag. This work is about these multiset deletion codes over a qary alphabet.
Jane: That sounds really technical. What’s the main idea behind what they are actually studying here? Like, what problem are they trying to solve with these kinds of codes?
Lu: They're looking at coding-theoretic frameworks that aren't based on classical sequences, but rather on multisets where the order doesn't matter. This paper focuses specifically on deletion models in this multiset space.
Meng: So, instead of checking if a string has a specific error pattern, we’re talking about whether two collections of symbols have enough overlap after some symbols get deleted. How does that translate to practical things?
Tom: Well, the core contribution they make is an explicit cyclic Sidon-type construction. This method lets you build these multiset t-deletioncorrecting codes for any alphabet size q and any deletion radius t.
Jane: An explicit construction sounds promising, but what’s the catch? Is this universal, or does it only work under certain conditions?
Lu: The paper claims it's universal because the construction is defined by a single congruence modulo t times plus one times q minus two plus one. This works for every pair of q and t, with no prime-power assumptions needed.
Meng: If it’s universal, that’s good for theory, but how does that actually look when you try to run this on real data? Does the construction itself have any immediate overhead?
Tom: It has a redundancy bound of at most log q times that modulo value. And they say it admits linear-time online decoding for fixed q and t after some finite preprocessing steps. That’s a concrete number we can work with.
Jane: So, the next thing I need to know is how good these codes are compared to other methods out there. Are they better than the standard ways we usually build these types of codes?
Lu: They compare this cyclic construction against things like Varshamov power-sum constructions and Bose–Chowla type finite-field constructions. The comparison shows that those finite-field Sidon constructions are stronger when the alphabet size is large and the deletion radius is fixed.
Title and authors: Meng: So, for my perspective, if I have a very large alphabet but only need to correct a small number of deletions, I’d be looking at those finite-field methods then. What about this cyclic one?
Tom: The paper says the cyclic construction has logarithmic dependence on t for fixed alphabet size q. That’s the key advantage they highlight when q is fixed and t grows.
Jane: That makes sense, but I'm curious about how well we can actually choose which residue to use in this construction. Is it just any number that works?
Lu: The paper proves an asymptotic balance theorem for the syndrome classes. This means for every fixed residue you pick modulo m, the size of that class is roughly one over m times n plus q minus one over q minus one, with some error term depending on q and t.
Meng: So if I’m just trying to find a good code, I don’t actually need to spend time searching for the perfect residue; any convenient residue should give me the same asymptotic performance. That simplifies things a lot for deployment.
Tom: Exactly. And they also show that for the single-deletion case, the natural sum-modulo construction is asymptotically optimal for every fixed alphabet size q. That's a strong statement about its efficiency in this specific setting.
Jane: That's interesting because I was thinking about what happens when we look at smaller blocklengths, like when n is not really huge anymore. Does this asymptotic optimality hold up exactly?
Lu: The paper does analyze extremal deletion regimes where t is close to n, and they get exact results there. For example, they find that for the case where t equals n minus two, the problem reduces to an ordinary intersection problem for squarefree codewords and shows Sq(n, n minus two) equals q when n is greater than or equal to q plus one <ref:2601.05636#pg1>.
Meng: An exact result like that is much more useful than just an asymptotic bound when I’m designing a system with a specific capacity limit. What about the bounds they compare? Are there any better general upper bounds we should be worried about?
Title and authors: Tom: They compare their explicit Kovaˇcevi´c–Tan bound against other things like the sphere-packing and projection bounds. The paper says that the explicit Kovaˇcevi´c–Tan bound is strongest in the standard setting where q and t are fixed and n goes to infinity.
Jane: That tells us something about where this specific construction shines versus those more general upper bounds. It suggests we need to be careful when we switch between those different regimes.
Lu: And for the single-deletion case, they found exact values for q equal to three and q equal to four, including uniqueness results for optimal codes in relevant parameter ranges. This shows that the natural sum-modulo construction isn't always exactly optimal at small blocklengths; there are two exceptional blocklengths n equals two and n equals four when t equals one.
Meng: So even when it looks good asymptotically, we might have to check those small cases manually for exact optimality. That’s a practical consideration for scaling up.
Tom: And they actually formulate conjectures for q equal to five and prime alphabets, suggesting that the sum-modulo construction is optimal for all sufficiently large blocklengths in that scenario. That gives us a direction for future research on larger alphabets.
Jane: It sounds like the main point is that this cyclic construction is a really useful, elementary tool when the alphabet size q is fixed and we are dealing with growing deletion radii t. But we have to be mindful of where those exact results break down at small sizes or when moving to very large alphabets.
Lu: The paper concludes by summarizing that the cyclic construction is a universal, elementary method for multiset t-deletioncorrecting codes, but its strength is most apparent when q is fixed and t grows faster than the other options.
Meng: For me, what I'm taking away is that if you want a robust method that isn't overly dependent on choosing the right finite field structure, this cyclic approach offers a solid starting point for deletion-based coding problems.
Tom: Right. And it’s clear that while the natural sum-modulo construction is asymptotically optimal for fixed q, we can't just assume it’s perfect everywhere. It depends on the blocklength and whether you need exact optimality or just good asymptotic performance in this Multiset Deletion Codes: Cyclic Syndrome Constructions, Bounds, and Exact Results paper.
The paper's summary: Tom: So, to wrap up what we just heard: this paper is about building codes for multisets where you delete some items, and they found a specific cyclic way to do that that works for any alphabet size and any deletion radius t.
Jane: Right. The big takeaway from the summary is that this construction isn't just some theoretical exercise; it’s an explicit method you can use. It uses weights based on t and q modulo some number, which lets you impose a single constraint to get these deletion-correcting codes.
Lu: What they really show is that this method is linear in the sense of Kovaˇcevi´c and Tan, which means it's structurally sound. They prove it works for every pair of q and t, no prime power restrictions needed whatsoever.
Meng: So, for someone who actually has to ship a product, that universality is good because you don't have to worry about whether your alphabet size is a power of two or something else when picking the construction method.
Tom: Exactly. And they also looked at how good these codes are compared to other methods we usually see, like those finite-field constructions or the power-sum ones.
Jane: They found that while those finite-field methods are stronger when your alphabet size is really big and you only delete a fixed number of items, this cyclic construction keeps things in check and has logarithmic redundancy in t when the alphabet size q is fixed.
Lu: That’s the trade-off they highlight. The cyclic construction avoids those restrictions on the finite field parameters while still giving you that logarithmic dependence on the deletion radius t.
Meng: From my side, I’m interested in how this affects deployment cost. If it has logarithmic redundancy in t, that means as you need to correct more deletions, the overhead doesn't explode like a linear dependency would. That’s something we care about when we talk about scaling up on production systems.
Tom: Right, and they looked at the syndrome classes too. They proved an asymptotic balance theorem which means you don't have to worry about picking a bad residue in your modulo calculation; any residue is roughly as good asymptotically.
Jane: So you can just pick whatever number works for your setup and get the expected performance guarantee without needing some complex search algorithm beforehand. It makes the design much simpler in practice.
Lu: They also dug into the hard limits, looking at extremal regimes where t gets really close to n, and they found exact results there, like showing that if you delete two items, t is about n minus two, then you can get a code size equal to the alphabet size q.
Meng: Exact results are gold. Knowing exactly when the math hits its limit helps us set realistic capacity targets for our hardware constraints.
Tom: And they also looked at those specific small alphabets, like three and four, where they found exact answers but also pointed out two weird blocklengths where the natural construction isn't optimal at all.
Jane: So it’s not just asymptotic performance across the board; you have to be careful about those small cases and choose your structure based on what you need: perfect optimality or just a good asymptotic running time.
Lu: Ultimately, the paper concludes that this cyclic construction is a very solid, elementary tool, especially when q is fixed and t grows. It’s a universal starting point for deletion problems.
Tom: So if you're building something from scratch involving multiset deletions, this explicit cyclic method seems like a really reliable way to start the design process.
The paper's improvements: Tom: We've just covered how this cyclic construction works for building those multiset deletion codes, and now we look at what the authors suggest we do next to make this even better.
Jane: So, if you have a good method but want to push it further, what are the suggested improvements in the paper? Is there a way they think we can tweak this construction to handle more complex deletion patterns?
Lu: They suggest that while the current construction is great for fixed alphabet size q and growing radius t, there’s room to explore how this method interacts with other types of constraints.
Meng: What kind of constraints are we talking about? Because right now, what I see is a very clean structure modulo some number m. Is they suggesting we can relax that constraint or maybe combine it with something else?
Tom: They point out that the comparison against those other constructions—the finite-field ones—is really important for setting future research directions. They suggest we need to look closer at when the finite-field method actually starts winning over this cyclic one.
Jane: That makes sense because we saw earlier that the finite-field approach is stronger in scenarios where the alphabet size is large and you only delete a fixed number of items. So, they are basically saying, "Keep looking at those specific regimes where the other methods shine."
Lu: Exactly. And they also hint at extending this work beyond just t-deletion codes. They suggest that because it’s linear in the sense of Kovaˇcevi´c and Tan, there might be ways to apply this same structural idea to different types of coding problems.
Meng: If they can generalize the structure, that would be huge for me at a startup. Generalizing a construction means you’re not just solving one problem; you’re finding a template that can solve many things.
Tom: And they also touch on what happens when we consider the prime alphabet case. They suggest that for very large data sets, we should expect this sum-modulo construction to be optimal then. That gives us a target for designing codes when we're dealing with huge alphabets and need to be sure about optimality.
Jane: So, they are giving us two clear paths forward: one is looking at how it competes with other existing methods in specific parameter spaces, and the other is using this method as a foundation to build something more general for different coding challenges.
Lu: That's the direction they are pushing toward. It’s moving from "this works well here" to "this structure can be used everywhere."
Conclusion: Tom: So we've covered how this paper on "Multiset Deletion Codes: Cyclic Syndrome Constructions, Bounds, and Exact Results" gives us an explicit way to build these codes for any alphabet size q and deletion radius t.
Jane: Right, it’s basically a universal blueprint for creating deletion-correcting codes using a cyclic method that works for every combination of those two parameters.
Lu: The big picture is that this construction is robust because it avoids having to make assumptions about prime powers or anything else when you set up the math.
Meng: So, from an engineering standpoint, it means you can design a code structure without worrying about the underlying field properties of your alphabet. That simplifies the implementation side a lot.
Lalam: I'm confident in this paper's findings because it’s explicitly shown to be linear and works for every q and t pair, which is a very strong guarantee in coding theory.
Tom: And we saw that the asymptotic balance theorem means you don't have to stress about picking a bad residue during the setup; any choice is fine for large numbers.
Jane: That’s huge because it means you can focus on other parts of your system design instead of spending time optimizing a modulo calculation just to get a slight speed boost.
Lu: It’s also interesting how they linked this to other methods, showing that while finite-field constructions are better for large alphabets, the cyclic method has its own niche where the alphabet size is fixed and the deletion radius t grows.
Meng: That distinction is important for us because if we’re building something with a huge alphabet but small errors, we know to look at those other methods instead of relying on this construction.
Tom: And they also gave us concrete examples for specific small alphabets like three and four, showing where the natural sum-modulo approach hits its exact limits at certain blocklengths.
Jane: So it shows that asymptotic performance doesn't always translate into perfect results right when you are designing a system with specific capacity limits.
Lu: They also pointed toward future work, suggesting that for prime alphabets and large enough data sets, this construction is expected to be optimal in the long run.
Meng: That’s a good signal for us on how to budget our research time; we know where the strong results are and where we need to keep an eye on things like that conjecture.
Lalam: I'm sure this paper will be cited because it provides a concrete, elementary tool for deletion problems that is hard to find elsewhere.
Tom: So, the main thing is that this cyclic construction gives us a reliable starting point for multiset deletion codes when the alphabet size q is fixed and we need to handle growing deletion radii t.
Jane: It's a solid piece of work because it’s universal in its setup, even if it doesn't solve every single coding problem out there.
Department of Computer Science, Reichman University · Research Assistant, MIGAL – Galilee Research Institute/Tel-Hai University of Kiryat Shmona and the Galilee
cs.IT, math.IT
Submitted: 2026-01-09
Updated: 2026-11-10
Comments: 24 pages
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 82/100
The gist: Multiset deletion codes are studied in the space of length-n multisets over a qary alphabet to understand coding-theoretic frameworks fundamentally different from classical sequence-based deletion…
Key concepts
- Cyclic Sidon-type Construction
- This is a specific method of building multiset codes by assigning weights (1, t+1, (t+1)2, ..., 0) to alphabet symbols modulo a specific number m. This assignment creates constraints that ensure the resulting code has the desired deletion-correcting properties based on the cyclic nature of the constraints.
- Syndrome Class Analysis
- This analysis examines how well different residue classes (syndrome classes) perform in terms of code size. The paper proves an asymptotic balance theorem, showing that for any fixed residue, the size of that class is nearly equal to the average class size, meaning no single residue is significantly better than others asymptotically.
- Logarithmic Redundancy
- Redundancy refers to how much extra information (redundancy) is needed in a code compared to the raw data. The paper shows that this construction achieves logarithmic redundancy in t when the alphabet size q is held constant, which is a highly efficient way to handle deletions.
- Extremal Regimes
- This refers to analyzing specific, extreme scenarios for the deletion radius t, such as when t is very close to n. The paper finds exact results in these regimes, like showing that if t = n-2 and n is large enough relative to q, the code size is exactly q.
Terminology
Summary
Multiset deletion codes are studied in the space of length-n multisets over a qary alphabet to understand coding-theoretic frameworks fundamentally different from classical sequence-based deletion models The explicit cyclic Sidon-type construction provides a universal, elementary, deletionspecific method for creating multiset t-deletioncorrecting codes with logarithmic redundancy in t when q is fixed
The Core Construction and its Properties
The main contribution is an explicit cyclic Sidon-type construction for q-ary multiset t-deletioncorrecting codes defined by a single congruence modulo m = t(t + 1)q−2 + 1 This construction assigns weights 1, t + 1, (t + 1)2,..., (t + 1)q−2, 0 (mod t(t + 1)q−2 + 1) to the alphabet symbols and imposes a single congruence constraint It works for every pair (q, t), with no prime-power or characteristic assumptions The construction is linear in the sense of Kovaˇcevi´c and Tan [8]
Syndrome Class Analysis and Optimality
The paper proves an asymptotic balance theorem for the syndrome classes, showing that for every fixed residue a modulo m, Cq(a) = 1/m (n + q − 1) / (q − 1) + Oq,t(n 2−2+ceil((q−1)/2))−1 This implies that asymptotically, choosing any convenient residue is as good as searching for a largest syndrome class The single-deletion case shows that the natural sum-modulo construction is asymptotically optimal for every fixed alphabet size q
Comparison with Alternative Constructions
The cyclic construction is compared against related Sidon-type constructions, including Varshamov power-sum constructions and Bose–Chowla type finite-field constructions The comparison shows that finite-field Sidon constructions are stronger in the large-alphabet, fixed-radius regime, whereas the cyclic deletionspecific construction is universal and has logarithmic redundancy in t when q is fixed
Extremal Regimes and Bounds
The paper analyzes extremal deletion regimes where t is close to n, yielding exact results such as Sq(n, n − 1) = q For t = n − 2, it reduces the problem to an ordinary intersection problem for squarefree codewords and obtains Sq(n, n−2) = q when n ⩾ q + 1 The comparison of general upper bounds shows that the explicit Kovaˇcevi´c–Tan bound is strongest in the standard fixed-q, t, n → ∞ regime
Finite-Length Optimality and Conjectures
For the single-deletion case, exact values for q = 3 and q = 4 are obtained, including uniqueness results for optimal codes in relevant parameter ranges These exact results show that the natural sum-modulo construction is not always finite-length optimal; for q = 3 there are two exceptional blocklengths n = 2, 4 Conjectures are formulated for q = 5 and prime alphabets suggesting the sum-modulo construction is optimal for all sufficiently large blocklengths
Conclusion
The paper concludes that the cyclic construction is a universal, elementary, deletionspecific method whose strongest regime is fixed alphabet size, particularly when t grows and finite-field Sidon constructions are less natural. The main takeaway is that while natural one-syndrome constructions are asymptotically optimal for fixed q, they may fail to be exactly optimal at small blocklengths or under the wrong choice of additive group
Pruning redundant reasoning tokens
The explicit cyclic Sidon-type construction provides a universal, elementary, deletionspecific method for creating multiset t-deletioncorrecting codes with logarithmic redundancy in t when q is fixed The construction is linear in the sense of Kovaˇcevi´c and Tan [8]
How the training signal is built
The construction assigns weights 1, t + 1, (t + 1)2,..., (t + 1)q−2, 0 (mod t(t + 1)q−2 + 1) to the alphabet symbols and imposes a single congruence constraint This construction is linear in the sense of Kovaˇcevi´c and Tan [8]
Where the gains come from
The comparison shows that finite-field and power-sum constructions are stronger when the alphabet size is large and the deletion radius is fixed The cyclic construction has logarithmic dependence on t for fixed alphabet size and avoids finite-field parameter restrictions The explicit Kovaˇcevi´c–Tan bound is strongest in the standard fixedq, t, n → ∞ regime The construction is universal, elementary, deletionspecific, and particularly efficient when q is fixed and t grows
The paper proves an asymptotic balance theorem for the syndrome classes, showing that for every fixed residue a modulo m, Cq(a) = 1/m (n + q − 1) / (q − 1) + Oq,t(n 2−2+ceil((q−1)/2))−1 This implies that asymptotically, choosing any convenient residue is as good as searching for a largest syndrome class
The construction assigns weights 1, t + 1, (t + 1)2,..., (t + 1)q−2, 0 (mod t(t + 1)q−2 + 1) to the alphabet symbols and imposes a single congruence constraint
The construction is linear in the sense of Kovaˇcevi´c and Tan [8] The comparison shows that finite-field and power-sum constructions are stronger when the alphabet size is large and the deletion radius is fixed The cyclic construction has logarithmic dependence on t for fixed alphabet size and avoids finite-field parameter restrictions
The construction assigns weights 1, t + 1, (t + 1)2,...
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Universal Deletion-Specific Construction: The AI system can utilize Construction 1 to generate explicit cyclic Sidon-type codes for arbitrary alphabet sizes q and deletion radii t, providing a construction that is
universal, elementary, deletionspecific, and particularly efficient when q is fixed and t grows.
-
Asymptotic Balance Analysis: The system can leverage the proof of Proposition 6 to determine that
optimizing over the residue class is not necessary for the asymptotic redundancy guarantee,
allowing it to choose any convenient residue without affecting the leading number of codewords or redundancy logq m + o(1). -
Comparison with Related Constructions: The AI can compare Construction 1 against Varshamov power-sum constructions, Bose-Chowla type finite-field constructions, and Xiao-Zhou's construction to understand their respective strengths in different regimes (e.g., finite-field methods being stronger in the large alphabet, fixed radius regime).
-
Upper Bound Comparison: The system can compare general upper bounds like the Kovaˇcevi´c–Tan bound with elementary bounds like the sphere-packing and projection bounds to determine which is strongest for specific parameter regimes (e.g., projection bound being stronger in large-alphabet or high-deletion regimes).
-
Extremal Regime Analysis: The system can apply specialized results for extremal deletion regimes, such as proving
Sq(n, n − 2) = q when n ⩾ q + 1
and providing certificate bounds for t = n - 3 to bound the code size in those specific scenarios. -
Optimal Single-Deletion Benchmarking: For fixed alphabets like q=3 and q=4, the system can identify that
the sum-modulo construction is optimal except at the exceptional blocklengths n = 2, 4
for t=1, enabling it to select the best code type based on whether it requires finite-length optimality or asymptotic optimality. -
Prime Alphabet Conjectures: The system can utilize Conjecture 22 to predict that
for all sufficiently large n,
the sum-modulo construction is conjectured to be optimal for prime alphabets, guiding design choices for very large data sets where exact finite-length bounds are unknown.
Sources
- Polynomial Constructions and Deletion-Ball Geometry for Multiset Deletion Codes
- The size of bipartite graphs with girth eight
Related papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Electromagnetic Signal and Information Theory: A Continuous-Aperture Array Perspective
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound