0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight

• URL: http://arxiv.org/abs/2607.18452v1
• Date: Mon, 20 Jul 2026 19:02:48 GMT
• Title: 0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
• Abstract summary: Two binary words of equal length are 0-cyclically equalizable if and only if they have equal Hamming weight.<n>We encode a pair of binary words as a single word over the four-letter alphabet A, B, X, O.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The random cut is one of the most fundamental shuffles in card-based cryptography: it rotates a sequence of face-down cards by a secret amount. Under this shuffle, two sequences of cards are indistinguishable if and only if they are cyclic shifts of each other. This motivates the question of whether, given two sequences of cards, inserting cards at matching positions can make them indistinguishable. A previous study shows that such an insertion is always possible when any cards may be inserted, as long as the two words are permutations of each other. This paper considers a stronger restriction: if the cards are binary, carrying only 0 or 1, can we insert only 0s to make the sequences indistinguishable? We call two words 0-cyclically equalizable if one can insert 0s into both sequences at matching positions so that the resulting words are cyclic shifts of each other. Our main result is that two binary words of equal length are 0-cyclically equalizable if and only if they have equal Hamming weight, that is, the same number of 1-bits. Since equal Hamming weight is clearly necessary, the content of the paper is to show that it is also sufficient. Our proof is constructive: we encode a pair of binary words as a single word over the four-letter alphabet {A, B, X, O}, reduce equalizability to a simpler condition in this encoding, and build the required insertion explicitly.

Related papers

• Explicit Boundary Markers for Subword Vocabularies [12.858857146500414]
  Subword tokenizers represent many common words twice in space-using writing systems.<n>We introduce an alternative to standard whitespace conventions using an explicit word boundary marker.
  arXiv  Detail & Related papers  (2026-08-09T18:16:51Z)
• Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings [0.0]
  Flashback is a reversible string decomposition that repeatedly peels the maximal leading and trailing character runs from a sentinel-wrapped input.<n>Our central result is a run-pairing theorem: Flashback is equivalent to pairing the first run of the string with the last, the second with the second-to-last, and so on.<n>This gives an exact token count of 1+[r/2] for a string with r maximal runs, and matches a lower bound that holds for any admissible bilateral run-peeling scheme.
  arXiv  Detail & Related papers  (2026-04-29T00:30:33Z)
• Cyclic Equalizability Characterized by Parikh Vectors [0.0]
  Cyclic equalizability is a notion introduced by Shinagawa and Nuida in 2025.<n>We prove that two words are cyclically equalizable if and only if they have the same Parikh vector.
  arXiv  Detail & Related papers  (2026-04-21T14:22:19Z)
• Modeling Overlapped Speech with Shuffles [57.278869801844316]
  We propose to model parallel streams of data, such as overlapped speech, using shuffles.<n>We show how the shuffle product and partial order finite-state automata (FSAs) can be used for alignment and speaker-attributed transcription of overlapped speech.
  arXiv  Detail & Related papers  (2026-03-18T14:28:58Z)
• Succinct QUBO formulations for permutation problems by sorting networks [0.1590850178837849]
  We introduce a QUBO formulation for permutations using compare-exchange networks, with only $O(n log2 n)$ binary variables.<n>A central feature of our approach is each permutation corresponds to a unique variable assignment, enabling unbiased sampling.<n>We expect this method to be practically useful in areas where unbiased sampling of constrained permutations is important.
  arXiv  Detail & Related papers  (2026-03-08T10:37:52Z)
• Cyclic Equalizability of Words and Its Application to Card-Based Cryptography [0.36832029288386137]
  We show that two binary words of equal length and equal Hamming weight are cyclically equalizable.<n>As applications of cyclic equalizability to card-based cryptography, we describe its applications to the information erasure problem and to single-cut full-open protocols.
  arXiv  Detail & Related papers  (2025-07-07T12:03:36Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Lexinvariant Language Models [84.2829117441298]
  Token embeddings, a mapping from discrete lexical symbols to continuous vectors, are at the heart of any language model (LM) We study textitlexinvariantlanguage models that are invariant to lexical symbols and therefore do not need fixed token embeddings in practice. We show that a lexinvariant LM can attain perplexity comparable to that of a standard language model, given a sufficiently long context.
  arXiv  Detail & Related papers  (2023-05-24T19:10:46Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string.
  arXiv  Detail & Related papers  (2023-05-24T11:47:35Z)
• Compressing 1D Time-Channel Separable Convolutions using Sparse Random Ternary Matrices [65.4388266814055]
  We replace 1x1-convolutions in 1D time-channel separable convolutions with constant, sparse random ternary matrices with weights in $-1,0,+1$. For command recognition on Google Speech Commands v1, we improve the state-of-the-art accuracy from $97.21%$ to $97.41%$ at the same network size. For speech recognition on Librispeech, we half the number of weights to be trained while only sacrificing about $1%$ of the floating-point baseline's word error rate.
  arXiv  Detail & Related papers  (2021-03-31T15:09:20Z)
• Fast Interleaved Bidirectional Sequence Generation [90.58793284654692]
  We introduce a decoder that generates target words from the left-to-right and right-to-left directions simultaneously. We show that we can easily convert a standard architecture for unidirectional decoding into a bidirectional decoder. Our interleaved bidirectional decoder (IBDecoder) retains the model simplicity and training efficiency of the standard Transformer.
  arXiv  Detail & Related papers  (2020-10-27T17:38:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.