In briefExact sampling cost under Campbell coding, with a new Rényi-based lower bound
SummaryThis paper studies how many bits are needed for exact sampling when the cost is measured by Campbell's exponential coding criterion. The sender and receiver share i.i.d. samples from Q, and the sender sends an index so the chosen sample exactly follows P. The authors introduce a Rényi channel simulation divergence R_α(P‖Q), show it lower-bounds the Campbell cost of any exact sampler, and achieve it up to an additive constant using a new layered sampling scheme. For i.i.d. product distributions under suitable conditions, the gap beyond the leading Rényi-divergence term is (1/2)log n + O(1).]
In briefUsing Bistatic Delay and Doppler to Locate 3D Targets in Distributed Wi-Fi Sensing
SummaryThis paper studies how bistatic delay information improves the observability and localization of 3D moving targets in distributed Wi-Fi sensing. It compares Doppler-only sensing with combined delay-Doppler sensing and derives the associated Fisher information matrices. The analysis indicates that Doppler-only localization generically needs six receivers, while delay-Doppler localization can become locally identifiable with three receivers under non-degenerate geometry. Simulations with Wi-Fi-like bandwidths support these findings.
Kyungmin Hong, Moein Ahmadi, Thomas Stifter et al.
In briefBinary codes that fix multiple edits, using polynomial hashing and entropy recycling
SummaryThis paper presents new explicit binary codes of length n that can correct t edits, including deletions, insertions, and substitutions, which is relevant to DNA-based storage and racetrack memories. The authors first build a systematic code with a polynomial hash, using (4t+2)log n + O_t(log log n) bits of redundancy. They then introduce entropy recycling, which uses the indices of good hashes to carry information, reducing the redundancy to (2t+1)log n + O_t(log log n) bits. The paper also provides deterministic polynomial-time encoding and decoding algorithms.
WhyIntroduces polynomial hashing and entropy recycling, reducing redundancy for correcting t edits to (2t+1)log n with rigorous proofs; notable advance for coding theory.
In briefNearly lossless transfer of approximation ratios for cuttable distributed graph problems
SummaryThe paper studies constant-round LOCAL approximation for additive local vertex-subset minimization problems. It presents two deterministic, computable transfer methods that improve the approximation ratio from a source algorithm to alpha+1+eta and alpha+eta, under stronger local niceness assumptions on the target graph class. The results include concrete ratios for 2-domination on bounded Euler genus graphs and for minimum dominating set on planar graphs with an attached clique.
WhyImproves the transfer ratio to alpha plus eta, with planar 2-domination dropping from 19 to 6 plus eta via proofs.
In briefRate-distortion theory for Gaussian mixtures using posterior label sampling
SummaryThis paper studies the mean-squared error rate-distortion function of finite Gaussian mixture models, for which no closed-form solution or optimal test channel is known. The authors sandwich it between bounds and show the upper bound is achieved by a proposed Gibbs-relabelling method. They also propose a stochastic scalar quantization scheme for low rates and analyze the rate gap and distortion floor from finite codebooks.
In briefVariation of Hull Dimensions in Symplectic Linear Codes
SummaryThis paper studies how the hull dimension of symplectic linear codes varies under equivalence transformations that preserve symplectic distance. The authors introduce an even-valued invariant Δ(C) and prove that the minimum symplectic hull dimension among equivalent codes is k−Δ(C), which determines when a code is equivalent to a symplectic LCD code. They also determine all attainable hull dimensions for self-orthogonal codes and give graph-based constructions of symplectic self-dual MDS, optimal, and best-known codes.
In briefExtending Proportionality Axioms to General Additive Utilities
SummaryThis paper studies participatory budgeting, where a subset of candidates is chosen under a budget constraint and voters assign numerical utilities to candidates. It focuses on proportionality, the fairness notion that each group of voters should influence the outcome roughly in proportion to its size. The authors generalise the existing approval-based plus axioms, EJR+ and Core+, to general additive utilities. Their approach uses a payment-based view in which candidate costs are shared among supporters to balance voters' total payments.
In briefSiteEvo: An LLM Agent That Autonomously Designs Site-Tailored Massive MIMO Detectors
SummaryThis paper presents SiteEvo, a framework in which a large language model agent writes complete, executable massive MIMO detector programs tailored to a specific deployment site, rather than only tuning predefined algorithms. The generated detectors have their parameters optimized by a communication-system backend and are structurally simplified to cut computation while preserving bit error rate. The final detector is frozen for deployment without online LLM inference. Simulations across three sites show bit error rate reductions of 2.6 to 6.0 times over the best competing detector at 6 dB, and computational cost reductions of 16.7 to 34.1%.
In briefLasso Games: Games That End When the First Loop Forms
SummaryThis paper studies games on finite graphs with labelled or weighted edges, where play stops once the first loop forms, producing a lasso-shaped path. It compares two ways to decide the winner: the loop semantics, which only considers the loop, and the lasso semantics, which considers the whole play. The authors show that the choice of semantics strongly affects game complexity and memory needs, for example making mean-payoff games PSPACE-complete while lasso parity games stay polynomial-time solvable.
In briefRandomized Fair Chore Allocation with Agents Arriving Online
SummaryThis paper studies fairly allocating indivisible chores among agents who arrive one at a time, requiring immediate and irrevocable assignments. Fairness is measured by the ex-post maximin share (MMS) approximation ratio. For binary additive costs, the authors present a randomized algorithm with expected ratio 3/2+o(1) and show that no randomized online algorithm can do better than 3/2−o(1). A variant guarantees a ratio of 2 with high probability, which is stated to be optimal.
In briefPolynomial-time algorithms guaranteeing share-based and envy-based fairness together
SummaryThis paper studies allocating indivisible goods so that share-based fairness (AnyPrice share, APS) and envy-based fairness (EFL, MXS) hold simultaneously. It presents algorithms running in polynomial time, pseudopolynomial time, and for a fixed number of agents, achieving combinations such as exact EFL with (1-ε)-MXS and 2n/(3n-1)-APS. The authors also show that computing a numerical threshold between MXS and RMMS is weakly NP-hard.
WhyGives polynomial and pseudopolynomial algorithms achieving combined share and envy guarantees, plus a weak NP-hardness result; rigorous proofs, impact mostly within fair division.
In briefDecoding method for protecting one message more strongly than others, without knowing the channel
SummaryThe paper studies how to give one special message stronger error protection than ordinary messages over noisy channels. The authors build codes whose decoder does not need to know the channel's transition law. They show an achievable error exponent for the special message that beats the equal-protection random-coding baseline and stays positive near channel capacity.
Seyed AmirPouya Moeini, Albert Guill\'en i F\`abregas
In briefA tighter limit on undetected error exponents for erasure decoding at positive rates
SummaryThis paper studies the undetected-error exponent of discrete memoryless channels under erasure decoding. Assuming the undetected-error and erasure probabilities vanish, it derives an upper bound on this exponent at positive rates. The proof uses a genie-aided argument from Somekh-Baruch, in which an auxiliary output gives the decoder a list of codewords. The bound recovers Telatar's tight rate-zero converse and is at least as tight as the straight-line bound, with a numerical example showing a strict improvement.
Seyed AmirPouya Moeini, Marco Dalai, Albert Guill\'en i F\`abregas
In briefDecoding Reed-Solomon codes against insertion-deletion errors up to the half-Singleton bound
SummaryThis paper studies decoding optimal Reed-Solomon codes of dimension two when insertion and deletion errors occur, with errors up to the half-Singleton bound. It presents a general decoding algorithm with lower time complexity than brute-force decoding, which corrects errors beyond the reach of existing methods. For insertion-only and deletion-only error patterns, the authors give two specialized algorithms that are faster than the general one.
In briefProof that computing Wyner's common information and common entropy is NP-hard
SummaryThis paper studies two information measures for a pair of random variables with finite ranges: Wyner's common information J(p) and the common entropy G(p). Both are defined as infima over auxiliary variables that make X and Y conditionally independent. The authors prove that computing either quantity is NP-hard, and that deciding whether J(p) is strictly below a given integer is NP-complete on certain tables. The hardness also holds for approximation within a suitable inverse-polynomial additive error.
WhyProves NP-hardness of two classical information measures via exact criteria and reductions, resolving a longstanding question with significant theoretical impact.
In briefConstant-loss round-preserving direct-sum theorems for information complexity
SummaryThe paper studies how the information needed to solve many independent communication problem instances relates to the information needed for one instance. It proves a round-preserving Gap-Majority lemma whose additive information loss is constant, independent of the number of instances and rounds, improving on a previously known logarithmic loss. It also establishes a variance direct-sum theorem for additive square-integrable observables over product distributions, and derives same-round mean-square estimation bounds for arbitrary terminal outputs.
WhyReduces round-preserving information loss from logarithmic to constant for Gap-Majority composition and gives a variance direct-sum theorem with complete proofs; impact remains confined to information
In briefSimulator for predicting LLM inference cluster performance with hierarchical KV caching
SummaryThis paper presents a compositional discrete-event simulator for predicting how hardware and serving policies interact with hierarchical key-value caching in LLM inference clusters. It separates local service costs from shared resource and KV availability, reusing compute and transfer models calibrated on 1P-1D deployments across compatible workers. Validation against SGLang shows mean end-to-end latency errors of 1.34% for question answering and 6.36% for coding sessions, and CPU simulation reduces replay turnaround by 15.33 times on average.
In briefNew storage-efficient codes for repairing damaged data in distributed systems
SummaryThis paper proposes a new family of (n, k) Minimum Storage Regenerating (MSR) codes for distributed storage systems. The parity-check matrix is built as a block Vandermonde matrix of diagonal and generalized permutation matrices, giving a sub-packetization level of (d-k+1) raised to ceil(n/2), for any repair degree between k+1 and n-1. The construction relaxes the strict commutativity condition required in earlier Ye-Barg codes, and a new proof establishes the MDS property.
In briefBounds on converting nonlinear codes in the merge regime, using entropy/length profiles
SummaryThis paper proposes an information-theoretic framework for converting nonlinear codes in the merge regime. Using the entropy/length profile (ELP), it derives upper bounds on unchanged symbols and lower bounds on read symbols for arbitrary (n,M)_q codes, without assuming linearity. For linear codes these bounds reduce to generalized Hamming weight bounds. Constructions based on Hamming codes and quasigroups are presented, the latter showing the bounds remain tight for nonlinear codes.
In briefDirectivity Estimates and Tolerance Tradeoffs Under Random Perturbations: A study of the feasibility of high-directivity sources using generalized sensitivity metrics.
SummaryThe paper proposes generalized sensitivity metrics to assess how practical high-directivity sources are when subject to random errors. The approach applies to continuous sources, ideal uncoupled arrays, and heterogeneous arrays with mutual coupling. It gives the ensemble average of realized directivity under the chosen error model, serving as a fast predictor of directivity loss from source perturbations. The directivity and tolerance measures are used to formulate optimization problems that show their tradeoff, and examples check the predictions' accuracy.
In briefSparse near-field beamforming: a mechanism that reduces effective degrees of freedom
SummarySparse near-field arrays combine several widely separated sub-arrays coherently, supporting distributed MIMO, satellite formations, and integrated sensing and communication. The paper argues that interference suppression over a protected region depends on coherence within one sub-array rather than on the whole formation's span, so the region covariance's effective rank can drop from MN to M. It gives a nonasymptotic sufficient condition and validates the theory with an eight-satellite LEO study, including realized worst-case signal-to-interference ratio.
Changhao He, Xiaojuan Zhang, Francois Chin Po Shin
In briefRecall-bounded staleness analysis for filtered multi-tenant ANN graph indexes under concurrent updates
SummaryThe paper presents a graph-based vector index combining streaming updates, filtered search, and multi-tenancy, with a theoretical decomposition of per-tenant recall loss into update staleness and filtered navigability. In the reported experiments, increasing merge size 20x with a fixed insert horizon lowered terminal recall@10 monotonically from 99.44% to 99.01%. The authors add a filter- and tenant-aware cache and a scheduler with per-tenant staleness ceilings, which on a FreshDiskANN substrate eliminated tight-tier SLA violations under the evaluated churn workload.
In briefWeighted Beeping Networks: Adding Signal Strength to Beep-Based Wireless Models
SummaryBeeping networks model wireless communication with binary interference, which ignores varied signal strengths. This paper introduces weighted beeping networks, where edge weights model signal strength and a beep is received only when accumulated neighbor signals exceed a threshold. It studies local broadcast, guaranteeing delivery only along edges heavier than a threshold, and presents an algorithm whose round complexity is nearly optimal. The authors also show that algorithms for classic beeping networks can be emulated on weighted networks with logarithmic overhead.
WhyExtends beeping networks with weighted edges, giving a near-optimal local broadcast algorithm and a logarithmic-overhead emulation result with proofs.
In briefAlmost every Boolean function has its threshold degree near the middle
SummaryThe paper studies the polynomial threshold degree of Boolean functions, the lowest degree of a real polynomial whose sign represents the function. It proves that for a uniformly random Boolean function on n variables, the threshold degree is either floor(n/2) or ceil(n/2) except with exponentially small probability. This confirms a 1991 conjecture of Aspnes, Beigel, Furst and Rudich, and addresses related conjectures of Wang and Williams.
WhyProves almost all Boolean functions concentrate threshold degree at central integers, resolving two 1991 conjectures with a complete probabilistic proof.
In briefSelfish Learners Reach Cooperation When Learning Rates Vary
SummaryThe paper studies selfish gradient-ascent learners playing the iterated prisoner's dilemma, adjusting reactive strategies defined by reciprocity and forgiveness. Populations with uniform learning rates converge to always-defect (ALLD), while populations with variable learning rates approach generous tit-for-tat (GTFT), yielding nearly optimal collective payoffs. The authors prove sufficient conditions for convergence to ALLD or tit-for-tat and show that learning-rate variability lets cooperation recover from perturbations.
WhyApplies gradient-ascent learning to reactive strategies, showing learning-rate heterogeneity sustains cooperation, with proofs of convergence conditions.
In briefFair division of indivisible items via subsidies to achieve best-of-both-worlds guarantees
SummaryThe paper studies how fair division with subsidies relates to best-of-both-worlds fairness for indivisible items. It proves that if every instance in a valuation class admits a fair allocation that can be made envy-free with subsidies, then an ex-ante envy-free lottery over such allocations exists. The result yields alternative proofs for additive goods, chores, and mixtures, and the converse holds for two agents but fails for three or more.
WhyProves a general reduction linking BoBW existence to subsidized envy-freeability, with a counterexample and three-agent results; strong theory, narrow practical reach.
