CS Paper Radar

Binary Huffman Coding with Unequal Letter Costs Is NP-Complete

L. Sunil Chandran, Rishikesh Gajjala

cs.DS cs.CCcs.CGcs.IT ·submitted 2026-11-03 07:36 UTC · v1

Abstract

Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.

Comment
51 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Massively Parallel Algorithms for Huffman Coding

cs.DS ·2026-10-06 ·Masoud Seddighin, Saeed Seddighin
similarity 0.66
Abstract

Huffman coding is one of the oldest and most fundamental problems in computer science. Given a string of length $\TextLength$ over a general alphabet, the goal is to assign a binary codeword to each character so that no codeword is a prefix of another and the total encoded length of the string is minimized. Huffman coding is widely used in practical compression systems, including file compression. As modern datasets continue to grow, it is natural to study whether a Huffman code can be constructed efficiently in the massively parallel computation (\MPC) model. The celebrated Huffman coding algorithm admits two straightforward \MPC implementations: for any constant $ε\in(0,1)$, one uses $O(\TextLength^ε)$ memory per machine but requires $Θ(\log \TextLength)$ rounds, while the other runs in $O(1)$ rounds but requires $Θ(\sqrt{\TextLength})$ memory per machine. We give the first nontrivial \MPC algorithm for Huffman coding that bypasses both limitations. For every constant $ε>0$, our algorithm uses $O_ε(\log\log \TextLength)$ rounds and $\softO(\TextLength^ε)$ memory per machine, while its total memory and total computation are $\softO(\TextLength)$. {\color{black}Although our framework is tailored to the \MPC model, we show that it has applications in the \PRAM setting as well. Specifically, we show that the same algorithm can be implemented in the \PRAM model with total work close to linear. In particular, whenever the text length is at most $2^{O\left(\left(\frac{\log \AlphabetSize}{\log\log \AlphabetSize}\right)^2\right)}$ (slightly superpolynomial), where $\AlphabetSize$ is the alphabet size, our parallel running time is asymptotically better than that of all previously known \PRAM algorithms and is essentially optimal.}

0.26

How Hard Is Tokenisation? Algorithms and Complexity Beyond NP-Hardness

cs.DS ·2026-11-09 ·Andrei Robert Ion, Rares Mateiu, Adrian Miclaus, Alexandru Popa
theoryhot direction similarity 0.64
Abstract

Given a collection of strings and a vocabulary budget, how well can we minimize its total token count, and how does the answer change with the tokenisation model? For binary direct tokenisation, previous work proved APX-hardness but left constant-factor approximability unresolved \citep{kastreva2026}. We rule out every polynomial-time $M^{1-\varepsilon}$ approximation, for fixed $\varepsilon>0$, unless $\mathrm{P}=\mathrm{NP}$, even on distinct equal-length strings with $K=m-1$. Here $M$ is the total input length and $m$ is the number of input strings. We complement this lower bound with a deterministic polynomial-time $O(M/\log M)$ approximation algorithm and stronger bounds for selected vocabulary budgets. For the different objective of maximizing compression savings, GreedTok was shown to attain a constant fraction of the optimum on unrestricted alphabets \citep{baliga2026}; we establish a deterministic EPTAS for direct savings on every fixed alphabet and analyze greedy selection by true marginal gains. For exact optimization, we give a binary direct algorithm running in $2^{O(n\log\log n/\log n)}\poly(I)$ time, where $n$ is the total length of the distinct input strings and $I$ is the input encoding length. Finally, we resolve two unary merge-model hardness questions left by the bounded-alphabet study \citep{kastreva2026}: standard unary bottom-up tokenisation is APX-hard, and unary optimal pair encoding is strongly NP-complete, strengthening the previously known weak hardness.

0.23

Tokenization: Hardness and Bicriteria Approximation Algorithms

cs.DS cs.AIcs.CC ·2026-11-11 ·Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran
theory similarity 0.62
Abstract

We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(γ,γ)$-bicriteria algorithm, with $γ= \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $γK$ with number of tokens at most $γ{\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.

0.18

On Optimal Encodings and Systematicity in Function-Correcting Codes

cs.IT ·2026-10-06 ·Charul Rajput, Kanchana Lokshmii Jagatti, B. Sundar Rajan
theory similarity 0.61
Abstract

Function-correcting codes (FCCs) protect the value of a function $f$ of the message against $t$ errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of $2t$ on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs $2t$. For a linear function $f$ and a fixed linear code $C$, let $d_f$ denote the minimum distance between codewords of messages with different function values. Different generator matrices of $C$ assign different codewords to the messages and can give different values of $d_f$. We study which generator matrix of $C$ gives the largest $d_f$. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of $C$. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of $C$ alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic $(f,t)$-FCC of length $n$ exists if and only if a condition depending on $f$ only through the size of its smaller preimage holds. For $t=1$, redundancy $1$ is sufficient for every nonconstant two-valued function on $\mathbb{F}_2^k$ with $k\ge 10$. For general $t$, redundancy $1$ suffices for all two-valued functions once $k$ is large enough, and for each $s<2t$ we give an upper bound on the threshold in $k$ beyond which redundancy $s$ suffices.

0.15

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.61
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Improving the Bounds on Approximating Weighted Maximin Share for Chores

cs.GT cs.AI ·2026-10-11 ·Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
similarity 0.60
Abstract

We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be $α$-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most $α$ times her weighted maximin share. We establish that every instance admits a $4.124234528$-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a $4.12424$-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to $e$. Together, our results substantially narrow the previously best-known gap of $[2,12]$ established by Li et al.~\cite{LWX26} to $[e,4.12424]$.

0.15

Even Faster Algorithms for Bounded Integer Programming

cs.DS ·2026-11-18 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.60
Abstract

We study integer programs $\min\{\mathbf{c}^{T}\mathbf{x}: A\mathbf{x}=\mathbf{b},\mathbf{l}\le\mathbf{x}\le\mathbf{u},\mathbf{x}\in\mathbb{Z}^n\}$ with a fixed number $d$ of equality constraints and constraint coefficients of absolute value at most $N$. Chen, Mao, and Zhang recently solved such programs in almost $N^{2d}$ time. We show that any polynomial saving for $(\min,+)$-convolution carries over to this problem. If witnessed $(\min,+)$-convolution of arrays of length $m$ can be computed in $\tilde{O}(m^ρ)$ time with error probability $p$, then for every $\varepsilon>0$ bounded integer programming can be solved in $\tilde{O}\bigl(n+N^{(\max\{ρ,3/2\}+\varepsilon)d}\bigr)$ time with the same error probability $p$, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for $(\min,+)$-convolution, this gives a deterministic algorithm running in $\tilde{O}(n+N^{1.99986\,d})$ time and a randomized algorithm running in $\tilde{O}(n+N^{1.9602\,d})$ time, up to the same factors.

0.09

Bounded Weighted Edit Distance with Metric Costs

cs.DS ·2026-11-10 ·Jihan Wang
similarity 0.60
Abstract

We give a deterministic $O(n+k^2)$-time algorithm for bounded weighted edit distance when the input costs form an integer metric on the alphabet extended by a gap symbol. Here $n$ is the total input length and $k$ is the given threshold on the distance. If the distance is at most $k$, the algorithm returns it with an optimal alignment. Otherwise, it reports that the distance exceeds $k$. The running time matches the classical unit-cost bound and is independent of the alphabet size and of the largest cost. The algorithm keeps only the farthest-reaching prefix alignment for each cost and each difference between the total gap costs of the aligned prefixes. For real metrics whose nonzero costs are at least one, scaling and upward rounding give a $(1+\varepsilon)$-approximation for the bounded problem in $\widetilde{O}(n+(k/\varepsilon)^2)$ time. If insertions and deletions have integer costs, the running time improves to $\widetilde{O}(n+k^2/\varepsilon)$.

0.20