In briefComplete classification of Z_{p^s}-linear generalized Hadamard codes
SummaryThis paper studies Z_{p^s}-linear generalized Hadamard (GH) codes, which are Gray map images of Z_{p^s}-additive codes and are built by a recursive construction. The authors complete the classification of these codes for every prime p, using a derived code obtained by puncturing outside a coordinate block determined by the kernel. They give the number of nonequivalent codes of length p^t for t≥3, which completes the classification of Z_{2^s}-linear Hadamard codes. They also prove a conjecture on codes with t_1≥2 and t_s=0.
In briefFast, flexible spiking neural network simulation on distributed on-chip memory accelerators
SummaryThe paper proposes a group-based mapping and communication strategy for running spiking network simulations on commercial accelerators with large distributed on-chip SRAM, addressing spike-routing challenges. On Graphcore IPUs, a cortical microcircuit model runs 22.7 times faster than biological real-time, with negligible build times and a reusable compiled graph. The approach makes no model- or hardware-specific assumptions.
Catherine Mia Sch\"ofmann, Jan Finkbeiner, Jan Vogelsang et al.
In briefNo truly sublogarithmic-round distributed MIS algorithm in the LOCAL model
SummaryThe paper proves that randomized LOCAL algorithms running in o(log n / log log n) rounds find a maximal independent set only with subconstant probability on some inputs. This shows that the 40-year-old O(log n)-round Luby and Alon–Babai–Itai CONGEST algorithm is nearly optimal. The authors build a hard instance by replacing vertices of a treelike graph with cliques and edges with bipartite Erdős–Rényi graphs, and analyze arbitrary algorithms using a novel round elimination approach.
WhyUses a novel round elimination on non-treelike dense bipartite random graphs to nearly match Luby's algorithm, closing a long-standing gap.
In briefDeterministic distributed linearly separable computation using nested cyclic codes
SummaryThis paper studies distributed linearly separable computation, where a master uses N workers to recover K_c deterministic linear combinations of K messages despite up to S stragglers. The authors propose a framework based on nested cyclic codes that achieves computation load M = (K/N)(S+K_c). For sufficiently large K, they prove a matching lower bound, establishing asymptotic optimality. Using cyclic locally recoverable codes as base codes, the master can often recover the results by contacting fewer than N-S workers.
In briefStudies on antenna beam pattern models for faster beam placement in LEO satellite networks
SummaryThis paper compares four antenna gain models, including Bessel and Gaussian models and a 3GPP model, for beam placement in low Earth orbit satellite networks. Each model's half-power angle is used to build a user compatibility graph, and the placement problem is solved as a minimum clique cover problem using graph coloring. The results show that the antenna pattern affects both beam resource usage and link quality, supporting antenna-pattern-aware beam placement.
Ninh Thi-Thanh Tam, Nguyen Viet Anh, Nguyen Minh Quan et al.
In briefNon-additive symmetric rank-metric codes: larger codes than additive ones in symmetric matrix spaces over finite fields
SummaryThis paper studies non-additive rank-metric codes inside symmetric matrices over finite fields, focusing on symmetric 2-codes. For odd q, the authors use isotropic vectors of a quadratic form on a four-dimensional space and link the construction to partial ovoids of the elliptic quadric Q^-(5,q). Building on a Cossidente and Pavese construction, they obtain a non-additive symmetric 2-code in Sym_3(q) of size q^4+2q^3, with an explicit matrix description. They also present a block-based construction giving lower bounds for all odd n≥3 and prime powers q>2 that exceed the largest additive code size with the same parameters.
WhyConstructs non-additive symmetric codes via partial ovoids of an elliptic quadric, giving the first infinite family beating additive codes, with complete proofs.
In briefA Gauss-Newton method for recovering phase from coded diffraction patterns
SummaryThis paper studies a minimum-norm Gauss-Newton method for phase retrieval from random coded diffraction patterns with additive intensity noise. It establishes convergence guarantees with quadratic error recursions in both resampled and fixed-data settings. Numerical experiments on synthetic signals and a natural image show the method's efficiency compared with state-of-the-art algorithms.
In briefA Distributed View from a Single GPU: RankLens for Distributed Training
SummaryDebugging, tuning, and analyzing distributed training is costly because it usually requires repeated runs at full target scale. This paper presents RankLens, which runs one surviving rank on a single GPU, executing the original training program's real local computation. At communication points it replaces real multi-rank communication with recorded results and recorded or estimated timing. Evaluated on DeepSpeed and Megatron-LM with 8 to 64 GPU configurations, it reports 100% communication-structure match for training tensors, under 5% timing error, and a reduction of analysis resources from target-scale clusters to one GPU.
In briefTruthful two-facility location on candidate sites in metric spaces
SummaryThe paper studies placing two facilities at candidate locations in a metric space, where agents have private positions and approval preferences and incur distance-based costs. The goal is to approximately minimize social cost or max cost while keeping agents truthful. On the line, it shows a deterministic lower bound of 7 for social cost, matching prior work, and that randomization improves this. For general metric spaces, it gives tight deterministic ratios of 2n-1 for social cost and 5 for max cost, and shows randomization gives substantial improvements.
In briefLatency-aware uplink NOMA edge computing with pinching antennas for deadline-feasible resource allocation
SummaryThis paper studies how many users offloading tasks to mobile edge computing at once can meet strict deadlines, in an uplink NOMA system served by a pinching-antenna system. It jointly optimizes transmit powers, CPU frequencies, and antenna configuration under latency constraints. The authors derive a closed-form least-power feasibility test and a three-block alternating-optimization algorithm, and numerical results show deadline feasibility is sustained at higher user loads than the baselines.
Sepehr Abolhasani, Saba Asaad, S. Mohammad Razavizadeh et al.
In briefSpace-time parallel simulation of Rayleigh-Bénard convection using parallel spectral deferred correction to cut run times
SummaryThe paper studies direct numerical simulation of Rayleigh-Bénard convection, a model of turbulent flow that demands very fine spatial grids and small time steps. The authors test parallel spectral deferred correction (SDC), a high-order time-stepping method, on JUSUF (CPUs) and JUPITER (GPUs) using two codes. Results show parallel SDC provides concurrency along the time axis and allows larger maximum stable time steps. Together these reduce the wall-clock time needed to simulate one free-fall time.
In briefChordal Codes: Constructing Codes and Efficient Gaussian-Elimination Decoding
SummaryThe paper introduces chordal codes, linear codes whose parity-check matrices have chordal primal graphs. The authors prove that the decoding submatrix for any erasure pattern keeps a chordal primal graph. As a result, Gaussian elimination following a perfect elimination ordering, called chordal elimination, is cheaper than Gaussian elimination on random codes. The paper also gives an upper bound on the complexity of chordal elimination.
In briefRouting optimality for demand graphs with matching number at most two
SummaryThis paper proves that network coding and fractional routing achieve the same capacity region in undirected networks whose demand graph has matching number at most two, meaning no three demand edges have pairwise disjoint endpoints. The authors reduce the problem, using the metric-packing reduction of Liu et al., to a distance-weighted communication inequality on the fixed graph Γ_{3,3}. The proof combines conditional entropy inequalities, two graph contractions, and an information inequality for deterministic interaction.
In briefCovering radius of Reed–Muller code RM(1,9) is 242, settling a long-open problem
SummaryThis paper resolves a long-standing open question in cryptography and coding theory by proving that the covering radius of the Reed–Muller code RM(1,9) is 242. The authors exclude nonlinearity 244 by constructing a cubic Boolean function that achieves a sharp Walsh ℓ¹ bound. They exclude nonlinearity 243 by deriving an inequality on the Walsh transform.
WhyResolves the long-open covering radius of RM(1,9) by excluding nonlinearities 244 and 243 via sharp Walsh bounds and cubic classification, a significant advance for coding and cryptography theory.
In briefQuota-based aging for predicted-length scheduling in LLM serving
SummaryThis paper proposes Quota-Based Aging (QBA), a scheduling policy for LLM serving systems that combines predicted short-first admission with quota-bounded promotion of aged requests predicted to be long. The authors evaluate QBA in a serving-aware event-driven simulator against FCFS, predicted short-first, and aggressive aging. The results indicate that QBA substantially reduces long-request tail latency while retaining much of the mean-latency benefit of prediction-guided scheduling.
In briefLearned score-based turbo message passing for recovering channels from spatially compressed measurements
SummaryThis paper addresses uplink channel recovery for hybrid beamforming in massive MIMO base stations, where the full spatial channel must be reconstructed from highly compressed beam-domain observations. The authors propose L-STMP, which deeply unfolds the turbo message-passing loop into a few trainable layers with learnable score priors. They also add PMI-assisted beam selection as a low-overhead directional prior, and simulations show consistent gains over existing baselines.
In briefA matroid generalization of weighted popular matching with a characterization and algorithm
SummaryThis paper studies a problem that unifies two generalizations of popular matchings in a one-sided preference model. It introduces the weighted popular common independent set problem, which simultaneously generalizes weighted popular matchings and popular common independent sets. The main result is the first polynomial-time algorithm for this problem, built on a solution-independent characterization of such sets.
Yuni Iwamasa, Yusuke Kobayashi, Ryoga Mahara et al.
In briefSharpening McDiarmid's Inequality with Rényi Divergence
SummaryThis paper asks whether Rényi divergence can improve McDiarmid's inequality and its KL-divergence-based distribution-dependent refinement. It shows that Marton's transport inequality generally fails when KL divergence is replaced by Rényi divergence of order 0<α<1. For sums of independent bounded random variables, additivity of Rényi divergence still yields concentration bounds. For Bernoulli sums, these bounds strictly improve the KL-based bound over a range of deviation thresholds. The paper also gives a distribution-dependent refinement of Gilardoni's inequality with explicit constants.
Amedeo Roberto Esposito, Adrien Vandenbroucque, Michael Gastpar
In briefMinimal exact disjunctive basis for solvability profiles of two-robot tasks
SummaryThis paper characterizes which tasks are solvable by two mobile robots in the plane under variable disorientation, chirality, and rigid movement assumptions. The authors show that every upset of a thirteen-class quotient order is realizable and construct a minimum exact disjunctive basis of thirteen tasks. They also find six tasks whose solvability signatures distinguish all inclusions and incomparabilities among the classes, and prove six is minimal.
Tsukasa Ninomiya, Shota Naito, Naoki Kitamura et al.
In briefOptimal Ferrers diagram rank-metric codes built by puncturing-inclusion using semifield codes
SummaryThis paper studies Ferrers diagram rank-metric codes, which are used in multilevel constructions of constant dimension codes for random network coding. It constructs an optimal code for the diagram [3,3,3,5] with rank distance 3 for every prime power q, answering an open problem from 2016. The method builds a [3×4,4,3]_q MRD code and shows that its punctured Delsarte dual contains a [3×3,3,3]_q MRD code derived from semifield codes. The authors also give optimal codes for two infinite families of Ferrers diagrams.
WhyAnswers an open problem of Etzion et al. via puncturing-inclusion constructions and infinite families; strong novelty, but impact is confined to rank-metric coding theory.
In briefCapacity Over Compute: Running Large Clinical Language Models on Consumer CPUs Using System RAM
SummaryThis paper argues that running large clinical language models at the point of care is limited mainly by GPU memory rather than processing power. The authors tested a 27-billion-parameter 4-bit model, used as a stand-in for a medical model, on two consumer computers with CPU-only pipelines and synthetic FHIR prompts. The model fit entirely in system RAM while both GPUs ran out of memory, and federated fine-tuning would transmit only a 22.6 MB low-rank adapter. The work is a research artifact using synthetic data, not a medical device.
In briefCapacity and gap limits of a rank-based gain-sharing method for online matching
SummaryThis paper studies the randomized primal-dual framework for online bipartite matching, which splits each matching gain between endpoint dual variables by offline rank. It defines certifying capacity as the strongest uniform guarantee achievable within a function class, and the certifying gap as its shortfall from Ranking's actual competitiveness. The analysis covers graphs with online degree at most d and d-regular graphs, showing the framework is tight for degree-one and unrestricted cases but has a positive gap for degree two. Both quantities converge to 1-1/e as d grows, with the gap bounded by roughly 1/(2ed).
WhyDefines certifying capacity within the primal-dual framework, giving exact results and matching bounds for low-degree graphs, a clear theoretical contribution.
In briefImproved combinatorial auction mechanisms, with and without buyer samples
SummaryThis paper presents new mechanisms for combinatorial auctions that aim to maximize social welfare with m items and n XOS buyers, across prophet-with-samples, secretary, and offline models. In the prophet-with-samples setting, the authors give a universally truthful, polynomial-time (2+ε)-approximation using O(log log m) samples per distribution, a factor shown tight even for a single item. For the secretary and offline models, they obtain an O(log log m)-approximate universally truthful mechanism, improving on the prior O((log log m)^2) bound.
WhyImproves approximation and sample complexity for combinatorial auctions, resolving two open problems with tight bounds and theoretical proofs.
In briefCacheSmith: Serving RAG Accurately Under Latency Targets Using Adaptive KV Cache Reuse
SummaryCacheSmith is a KV cache reuse system for RAG prefill that aims to meet latency service-level objectives while preserving generation quality. It splits selective recomputation into WarmUp, Probe, and Patch phases, configured dynamically by an SLO-aware scheduler and a budget-aware planner. Across four benchmarks with varying arrival rates and burstiness, it improves quality-gated SLO attainment by up to 27.5% over four state-of-the-art baselines.
In briefCo-adaptive entropy modeling and rate-distortion-optimal bit allocation for perceptual audio coding
SummaryThis paper presents a perceptual audio coder whose entropy-coding model and bit allocation adapt jointly across blocks without sending model side information. Encoder and decoder build identical histograms from decoded blocks to update the same model state. Under a strict per-block rate, entropy-coding-aware bit allocation reduces perceptual distortion by 15–24% relative to a solver that ignores it, and co-adaptation removes a further 3–4%. A MUSHRA listening test at 80 kbps per channel confirms this ranking.
In briefUniform Pricing for Customers Who Buy the Cheapest Acceptable Item
SummaryThis paper studies unit-demand pricing when customers follow a min-buying rule, purchasing the lowest-priced item that gives non-negative utility. The authors show that uniform pricing is optimal for symmetric environments with i.i.d. or exchangeable affiliated valuations, but not in all symmetric cases, where the gap to optimal item pricing is logarithmic in the number of items. For asymmetric regular valuations, a uniform price guarantees about 69.86% of optimal item-pricing revenue, which is tight. The results suggest non-uniform pricing's value largely diminishes under this satisficing demand model.
Titing Cui, Michael Hamilton, Jourdain Lamperski et al.
In briefA stochastic growth model for online platforms: how matching markets scale through admission, assignment and pay decisions
SummaryThis paper studies how online platforms acting as market makers in two-sided matching markets grow, addressing the so-called chicken-and-egg problem. The authors model the platform as a Markov process with servers and customers arriving according to Poisson processes. They characterize optimal admission, assignment, and compensation policies, and show that seniority-based compensation can substitute for upfront subsidies.
In briefDynamic pricing algorithm for perishable goods that adjusts prices based on inventory and demand
SummaryThis paper studies how a seller with limited inventory should sequentially price a perishable product for customers with varying valuations. The author proposes Dynamic Run-Out Pricing (DROP), an interpretable algorithm that adjusts prices in real time using current inventory and expected future demand. For bounded or exponential valuation distributions, the expected revenue converges to the optimal revenue as market size grows. For heavy-tailed Pareto valuations, the paper introduces Tail-Aware DROP (TA-DROP), which raises prices to protect inventory and is shown to restore asymptotic optimality.
In briefShortest-time routing paths between all satellite node pairs in time-varying networks
SummaryThis paper presents an algorithm for computing all-pairs shortest-time paths in time-varying networks, targeting low earth orbit (LEO) satellite constellations whose topology changes over time. The network is modeled as a temporal graph, and the algorithm runs in O(M²n³) time. Its structure resembles two matrix multiplication steps, forward and backward, which makes it well suited to parallelization on SIMD architectures such as GPUs, enabling efficient network-wide message routing.
In briefComputer-assisted exact lower bound on Fisher information convexity along 2D heat flow
SummaryThe paper studies the sharp constant c in a differential inequality for Fisher information along the heat flow on R². The value c=1 is shown false in two dimensions, while a known theorem gives c=1/2. The authors construct an exact, machine-verifiable sum-of-squares certificate establishing c ≥ 231691/250000 ≈ 0.926764. Combined with a Fourier-based construction, they bound the sharp constant between 0.926764 and about 0.94177, leaving the exact value open.
In briefA Computer Scientist's Introduction to Contract Theory: Paying for Results to Motivate Effort
SummaryThis survey introduces contract design to computer scientists, explaining how outcome-based payments can motivate effort. It covers applications such as online labor markets, incentive-aware algorithmic classification, and AI agent ecosystems. The paper presents the classic principal-agent model, shows that optimal contracts can be computed via linear programming but may be opaque and brittle, and then turns to simpler linear contracts with approximation guarantees and robust optimality. It also extends the discussion to multi-agent combinatorial contracts and learning under partial information.
In briefMCCL: A collective communication library that re-plans schedules when network links degrade
SummaryIn large-scale distributed training, collective communication is a key bottleneck, and existing libraries compute fixed schedules assuming static topology and peak link capacity. MCCL passively measures GPU-to-GPU throughput, detects persistent degradation, re-synthesizes affected schedules with warm-started synthesizers, and hot-swaps them during training. The paper reports under 2% overhead, under 1.2% measurement error, and about 12 ms swap time on a hardware prototype, and up to 4.99x training-time reduction over static schedules under gray failures in simulated Llama and DeepSeek workloads.
Michele Ferrero, Gabriele Castellano, Paolo Medagliani et al.
In briefConstructing Regular Fat Linear Sets and Non-Representable q-Matroids
SummaryThis paper studies regular fat linear sets over finite fields, which have exactly r fat points of weight at least two and all other points of weight one. The authors derive divisibility constraints on point weights using the scalar stabilizer of the defining subspace, showing that a rank 2i regular fat linear set in PG(1,q^n) has at most two or exactly q+1 fat points. They also construct higher-dimensional examples whose fat points do not form an F_q-subgeometry. Applying the projective-line results, they present an infinite family of non-representable rank-two q-matroids arising from partial spreads.
WhySolves two open problems with divisibility constraints and new higher-dimensional regular fat linear sets, with rigorous proofs and non-representable q-matroid families.
Yufei Qiu, Valentino Smaldore, Zhenpeng Wang et al.
In briefFlashT2S: GPU-accelerated converters from tensors to neural spikes for neuromorphic LLM backends
SummaryThis paper addresses the slow conversion between tensor and spike data formats that bottlenecks neuromorphic large language models during training and inference. It presents FlashT2S, GPU-accelerated conversion operators built with architecture-aware, data-centric optimizations. The authors report an average speedup of 850.78x over native operators and 5-11x over torch.compile-generated kernels, with output standardized for heterogeneous neuromorphic hardware.
In briefA new iterative decoding method for short BCH codes using more dual codewords
SummaryThis paper studies a shift-sum decoding algorithm that uses dual codewords. Existing methods rely mainly on minimum-weight dual codewords, which are limited in number. The authors extend the counting mechanism to dual codewords with Hamming weights up to a set bound, and add a normalized counting rule to reduce overcounting from higher-weight classes. Hard-decision and soft-information-aided iterative error reduction decoders are developed on this basis. Numerical results show the method outperforms existing minimum-weight shift-sum baselines, especially for short codes.
In briefMODAIC: Coordinated Asynchrony for Decentralized Multimodal Learning
SummaryThis paper presents MODAIC, a wait-free system for decentralized multimodal learning across edge devices with varying compute and bandwidth. It lets each modality progress independently while keeping cross-modal feature exchange, and uses load-aware update fetching and consensus-aware peer selection to reduce stale or delayed updates. Evaluated on AVE and KU-HAR, it improves average and worst-agent accuracy, and reduces time-to-accuracy by up to 30% on a cloud testbed.
In briefOnline fair item allocation with no-worse upgrade recourse
SummaryThe paper studies online fair division of indivisible goods, where irrevocable assignments rule out any positive maximin share (MMS) guarantee. It allows reassignments provided no affected agent becomes worse off, under item-level or bundle-level upgrades. Under item-level upgrades the optimal MMS factor is about 1/ln n, while bundle-level upgrades yield exact MMS for two agents and more than half of MMS for any number of agents.
WhyIntroduces online fair division under upgrade recourse, proving a near-optimal 1/H_n factor and exact MMS for two agents with rigorous theory, offering notable influence within the subfield.
In briefBeyond the Boundary: Optimal Grid Dispersion via Spread, Reverse, and Collect
SummaryThis paper studies deterministic dispersion of k≤n mobile agents on an oriented square grid, where agents can only communicate when co-located. Prior work was optimal only when k is linear in n, leaving open whether the Ω(√k) time bound can be met for smaller k. The authors present the SRC algorithm, which disperses agents in O(√k) synchronous rounds using O(log k) bits per agent, matching both time and memory lower bounds. The method needs no knowledge of grid size and works on infinite grids.
WhyGives a deterministic local-communication algorithm matching the Omega(sqrt k) time and memory lower bounds, closing an open question with rigorous analysis.
Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak et al.
