In briefEmulating FP64 matrix products with low-precision INT8, FP8 and FP4 operations
SummaryThe paper treats Ozaki scheme II and its FP8 and FP4 variants as one family that emulates FP64 matrix products using residues modulo coprime moduli. It frames choosing a scheme as a combinatorial problem that minimizes the number of low-precision GEMMs and derives lower bounds on that count. Implemented on three Blackwell GPUs, the INT8, FP8 and FP4 schemes run faster than native FP64, up to 83x on B300.
WhyUnifies Ozaki-style schemes as a combinatorial optimization with GEMM lower bounds, yielding first FP6 schemes and measured speedups up to 83x on Blackwell GPUs.
Pratyai Mazumder, Alexandru Calotoiu, Torsten Hoefler
In briefOptimal codes that correct up to t deletions in permutations
SummaryThis paper constructs systematic permutation codes that correct multiple deletions under two models: symbol-invariant deletions (SIDs) and permutation-invariant deletions (PIDs). For any fixed t≥1 and large n, the encoders insert redundancy symbols while preserving the order of the message symbols. The redundancy is (7t−1)log n+O_t(1) bits for PIDs and 4t log n+O_t(1) bits for SIDs. Encoding and decoding run in n^{O(t)} time.
In briefMEDEM: A Design Method for Multi-Engine Deep Learning Accelerators
SummaryThis paper proposes MEDEM, a systematic methodology for designing deep learning accelerators that combine multiple complementary engines. It co-designs candidate engines and selects the combination that minimizes aggregate execution cost under a resource budget. The authors report geometric-mean improvements of up to 4.84x in energy-delay product and 1.59x in throughput over state-of-the-art designs.
Fareed Qararyah, Mohammad Ali Maleki, Pedro Trancoso
In briefSharp lower bound on second-best welfare in bilateral and matching markets when values are private
SummaryThe paper determines the exact ratio of second-best to first-best social welfare when buyers' and sellers' values are private. The ratio is approximately 0.8882516903 for arbitrary priors and 0.9113893681 when buyers have monotone hazard rates. Both constants are already attained in bilateral trade and extend to matching markets. The authors give variational characterizations of the constants and reproducible interval certificates for numerical evaluation.
WhyGives sharp second-best to first-best welfare ratios for bilateral and matching markets, proven tight for arbitrary priors and MHR buyers.
In briefRotatable antennas for space-air-ground networks: opportunities and challenges
SummaryThis article examines how rotatable antenna (RA) technology, which adjusts beam direction mechanically or electronically while keeping antenna positions fixed, can support communication and sensing in space-air-ground integrated networks (SAGINs). It explains RA's role in wide-area coverage, dynamic directional transmission, and cooperative sensing, and discusses design challenges such as channel acquisition and cross-segment coordination. An RA array prototype and two simulation studies are presented to illustrate feasibility and potential performance gains.
In briefCodes that fix two deletions using only three extra symbols over large alphabets
SummaryThe paper builds systematic codes over polynomial-size alphabets that correct two deletions using three redundant symbols, with polynomial-time encoding and decoding. A cardinality bound by Liu and Xing shows three redundant symbols are necessary, so the construction is optimal in this respect. The authors also show existence of such codes over alphabets of size O(n^4) and give a polynomial-time construction for a single burst of two adjacent deletions.
Valery (Binyamin) Grishin, Aryeh Lev Zabokritskiy (Yohananov)
In briefMatroid packing games: how to fairly split shared value (core and nucleolus)
SummaryThis paper studies the matroid base packing problem using cooperative game theory and defines a matroid base packing game. It extends the network strength game of Baiou and Barahona (2020) from graphic matroids to general matroids. Using the exchange structure of matroids, the authors build a graph-theoretic framework for analyzing the game's core and nucleolus. The framework gives a compact condition for core nonemptiness and polynomial-time algorithms for testing it, finding a core allocation, and computing the nucleolus.
In briefDelay guarantees for SIC-decoded VLSF codes under hardcore spatial regulation
SummaryThis paper studies the decoding delay of variable-length stop-feedback (VLSF) codes with successive interference cancellation over multiple access channels. For deployments modeled by hardcore point processes, the SINR has a positive lower bound for all transmitters in the coverage region. Under a fixed total error probability constraint, these transmitters are decodable within an upper-bounded delay, which is well approximated by an inverse Gaussian distribution. Numerical results show that hardcore regulation provides uniform performance guarantees across links.
In briefSix families of binary codes from Ding's conjectures: proofs and counterexamples on code weights
SummaryDing proposed ten conjectures on binary linear codes built from Boolean functions, and four were already proved by Gölo\u{g}lu and Krasnayová. This paper studies the remaining six conjectures. It obtains common weight restrictions and infinite five-weight families for Conjectures 19 and 27, and shows that codes in Conjecture 30 have three, four, or five nonzero weights, with a four-weight example disproving the original claim. For Conjecture 34 it gives a general (2h+1)-weight bound and a six-weight counterexample, and Conjecture 37 is completely resolved.
In briefExponential Backoff: Meta-Stability and Implicit Admission Control
SummaryThis paper analyzes exponential backoff, an algorithm that lets several users share one communication channel in a distributed way, similar to networking standards like 802.11. The authors show the algorithm is meta-stable: over long time scales, the system oscillates between configurations where only a subset of sources effectively access the channel. This creates a form of implicit admission control. The paper provides theoretical tools and numerical experiments, which are fully reproducible, with code publicly available as a Python package.
In briefWindowed, Quantized Group ADMM for Distributed Optimization on Heterogeneous Edge Networks
SummaryThis paper proposes WQ-GADMM, a method that coordinates group-based updates of edge clients under limited activation capacity and communication resources. Clients are grouped by estimated computation time, a limited number of groups are activated per window, and the cloud updates the global model after every group has updated once, with quantized model exchanges in both directions. For smooth nonconvex objectives, the authors bound the average squared KKT residual, with a term decreasing in iterations and a quantization-dependent error term. Experiments on MNIST and CIFAR-10 show that 12-bit communication reduces communication volume and simulated wall-clock time while keeping test accuracy comparable to full precision.
In briefCobalt: Using Expert Co-activation to Speed Up Distributed MoE Training
SummaryThis paper presents Cobalt, a training framework for Mixture-of-Experts (MoE) language models. It observes that many pairs of experts are often activated together by the same tokens, and uses this to co-locate such experts on the same node, reducing cross-node traffic, while adjusting workloads within nodes at each step. A communication-aware task assignment method routes tokens to fewer remote nodes. On 32 B200 GPUs, the authors report speedups of 1.53 to 2.41 times (1.28 to 1.89 times on average) over existing frameworks and a 75.74% to 99.26% reduction in cross-node token traffic.
In briefJanus: Efficient agentic LLM serving with SSD-based sparse KV storage
SummaryThe paper presents Janus, a serving framework for agentic LLM sessions that store history key-value caches on SSDs and use sparse attention. It runs the model's own KV selection module on earlier intermediate values to predict needed data, moving SSD reads off the inference critical path. It also coalesces reads and packs scattered writes to improve SSD efficiency. Across three models and three agentic traces, Janus reduces time to first token by up to 1.57-3.69 times over existing works while keeping decode efficiency.
In briefReshaping Rollout Workloads for Asynchronous RL Post-Training on Heterogeneous Accelerators
SummaryThis paper addresses rollout scheduling for reinforcement learning post-training on heterogeneous hardware and presents CadenceRL. It reshapes the workload structurally, using pacing, concentration, and late-bound KV preparation, to balance aggregate decode throughput with per-trajectory completion time without manual routing configuration. The authors report up to 48% higher decode throughput and up to 64% lower P95 trajectory latency on heterogeneous rollout pools.
In briefCalibrating a checksum detector for bfloat16 matrix multiplication errors and its blind spots
SummaryThis paper studies algorithm-based fault tolerance, a checksum method that flags corrupted matrix multiplications, which earlier work had evaluated only at float32. For bfloat16 with contraction length 4096, the authors fit a Generalized Pareto distribution to about 8e7 clean residuals and estimate a threshold near 3.14e-6 for a 1e-6 per-multiplication false-positive rate. Under their output-level perturbation model, the detector caught 304 of 400 single exponent-bit flips and none of 600 low-mantissa flips. The paper does not estimate real hardware fault rates.
In briefEfficient Transmit Waveform Design for 1-Bit DAC MIMO-OFDM Radar-Communication Systems
SummaryThis paper studies transmit waveform design for MIMO-OFDM dual-functional radar-communication systems that use 1-bit digital-to-analog converters, a topic it describes as underexplored. The waveform is designed to maximize the trace of the target angular Fisher information matrix, subject to symbol-error constraints via constructive interference and a 1-bit time-domain alphabet. The resulting large-scale nonlinear integer problem is solved with an inexact ADMM algorithm that alternates between time- and frequency-domain updates. Simulations show promising radar-communication performance.
In briefHARS: An LDPC bit-flipping decoder that sets parameters from the initial syndrome and local reliability
SummaryThis paper presents HARS, a bit-flipping decoder for LDPC codes that combines local channel reliability with parameter selection based on the initial syndrome. The initial syndrome weight sets the base weight, reliability coefficient, threshold decay factor, and perturbation amplitude for each frame. On rate-one-half PEGReg and WiMAX codes, HARS reduces bit-error rate and mean iteration count compared with a calibrated SM-NGDBF baseline. An FPGA implementation on an XC7A200T is also reported.
In briefA study of the maximum number of DNA sequences distinguishable by single-label DNA labeling
SummaryDNA labeling distinguishes DNA sequences by recording where labels appear, and its labeling capacity is the growth rate of the number of distinguishable sequences as length goes to infinity. The authors model the labeling process as a deterministic channel and show its zero-error capacity equals the labeling capacity. For a single label this channel is a star graph, and they derive zero-error capacities for all star graphs, fully characterizing single-label cases. They also present a general method for constructing capacity-achieving codes.
In briefApproximate uniformity in finite convolution models: how closely a sum of two fixed-support distributions can mimic the uniform law
SummaryThis paper studies how well the sum of two independent distributions with fixed support can approximate the uniform law. It measures closeness using Manhattan distance, Euclidean distance, forward Kullback-Leibler divergence, and the line-metric Wasserstein-one distance. Explicit results are obtained for two models, including one conjecture. The authors also apply their reconstruction method to a recent conjecture about the coding capacity of an additive noise channel.
In briefNonlinear data pricing makes optimal revenue computable again
SummaryThis paper studies how a data seller should price multiple datasets for budget-constrained buyers, using pricing functions that map purchased quantity to total payment. Prior work showed that optimal linear pricing is computationally intractable. The authors show that allowing general monotone, lower-continuous pricing functions can raise revenue and makes the optimum computable in polynomial time. Optimal functions are piecewise linear and convex, with total kinks bounded by the number of buyers.
Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma et al.
In briefSurrogate-enhanced fractional programming for MIMO device-to-device interference management
SummaryThe paper addresses weighted sum-rate maximization in multi-stream MIMO device-to-device interference networks. It extends the scalar surrogate-enhanced fractional programming (SEFP) method to matrix ratios using Hermitian functional calculus, yielding a matrix SEFP framework. The authors show XMMSE is a special case of SEFP and propose SEFPLinQ for joint scheduling and beamforming, with numerical results reporting consistent gains.
In briefWhy Walker satellite routing tables are not periodic, and how to compare them with fiber
SummaryThe paper models the configurations of a Walker satellite constellation as a dynamical system given by a translation on a torus, and extends this analysis to routing through satellites and fixed ground relays. For any deterministic, time-invariant routing rule, the routing table is periodic when the ratio of angular speeds is rational and non-periodic but ergodic when it is irrational. Long-run averages can then be computed from an explicit invariant measure, which makes comparisons of round-trip times between the constellation and terrestrial fiber meaningful.
In briefParaAnya: A plug-and-play output cache that speeds up parallel diffusion sampling by reusing repeated computations.
SummaryDiffusion model sampling is inherently sequential and computationally expensive. Parallel-in-time solvers use sliding windows, which causes the same timesteps to be evaluated repeatedly. ParaAnya caches input-output pairs and reuses them at overlapping timesteps, dispatching only cache misses to GPU workers. On Stable Diffusion v1.5 with eight GPUs, it gives 1.30 to 2.43 times speedups over uncached samplers and reduces function evaluations by up to 70.1% while keeping CLIP scores comparable.
In briefA polynomial-time test for which graphs always admit strongly EFX orientations
SummaryThis paper studies fair division of discrete goods modeled as graphs, where vertices are agents and edges are goods. It gives a polynomial-time characterization of strongly EFX orientable graphs, which are graphs that admit an EFX orientation regardless of valuation. A connected graph qualifies if it is bipartite, or if its block decomposition has exactly one nonbipartite block containing a suitable degree-2 vertex whose removal leaves a bipartite graph. The authors state the proof was discovered by AI with human help in breaking the problem into subproblems.
WhyGives a complete polynomial-time characterization of strongly EFX orientable graphs, resolving an open question with a rigorous proof.
In briefOptimal rank-metric quantum codes and their exact recovery radii
SummaryThis paper studies rank-metric quantum codes for correlated faults that are dense physically but low-rank over a base field. It proves an asymmetric rank-metric Singleton bound for CSS codes, including degenerate ones, and characterizes equality via commuting maximum-rank-distance matrix codes. For Singleton-optimal pairs with positive logical dimension, the measured syndrome exactly determines the projected error modulo stabilizers at radii strictly below half the sector rank distance.
In briefSelecting Contributors for Regional Digital Twins with Coverage Guarantees While Vehicles Move
SummaryThis paper studies how regional digital twins coordinate which contributors may join over congested broadcast networks in mobile settings without fixed infrastructure. The authors propose a host-coordinated protocol that admits only contributors whose timely, non-redundant coverage gain exceeds a congestion price within a cycle deadline, using a 13-byte beacon digest for pre-transmission scoring. Standards-based simulation reports that the timely actionable coverage deficit drops from 5.6% to 1.4% at comparable load to ETSI redundancy mitigation.
In briefAlgorithm for Arctic product-mix auction equilibria
SummaryThis paper studies Arctic product-mix auctions, where budget-constrained bidders express preferences over multiple substitute goods. It gives the first strongly polynomial algorithm for finding competitive equilibria when the auctioneer has separable convex piecewise-linear costs. The method combines a strongly polynomial reduction to the costless Arctic auction with an existing strongly polynomial algorithm for that case.
WhyGives the first strongly polynomial algorithm for competitive equilibria with convex costs, plus reductions to Fisher and Arrow-Debreu markets, with rigorous theoretical support.
In briefIncentive-compatible online matching with random arrival order
SummaryThe paper studies random-order online bipartite matching where users care only about being matched, while the platform maximizes total reward. It proposes the first constant-competitive, arrival-time incentive-compatible edge-weighted algorithm on complete bipartite graphs. The competitive ratio depends on the imbalance factor between online and offline nodes. For binary rewards, the authors present algorithms with a strictly better ratio.
In briefLDPC Fractus Codes: Sparse Codes Built by Recursion
SummaryThe paper introduces Fractus matrices, sparse matrices built through a self-similar recursive process, and uses them to construct LDPC codes. The resulting Tanner graphs have girth six and guarantee a minimum Hamming distance of at least ℓ+1. The authors establish algebraic properties of these matrices, including sparsity, regularity, recursive decomposition, and a natural lattice structure.
In briefInfluence maximization in near-linear time: a faster method for choosing key seed nodes
SummaryThis paper studies influence maximization, which seeks k seed nodes in a graph with n nodes and m edges to maximize expected information spread under standard diffusion models. The prior Borgs et al. algorithm ran in Õ((n+m)k) time, and later work only reduced log factors or improved the dependence on ε. The authors present an algorithm achieving a 1−1/e−ε approximation in Õ(n+m) time, removing the multiplicative dependence on k from the running time.
WhyResolves an open problem by removing the k factor, achieving near-linear time with the 1-1/e-epsilon guarantee; substantial theoretical advance with broad subfield impact.
In briefVoronoi-Markov chain and spatial entropy for point pattern analysis
SummaryThis paper revisits entropy in a spatial setting to derive computable, interpretable metrics for point pattern analysis, such as in histopathology. It reviews stochastic point process assumptions like Poisson homogeneity and Simple Sequential Inhibition, along with Voronoi and Delaunay tiling results that can provide null distributions for hypothesis testing. The authors introduce a "dense basin entropy" based on the Ord distribution over Voronoi basins, which is sensitive to clustering, and a Markov chain approximating Brownian motion. Simulations and histopathology experiments show these metrics offer insights complementary to other spatial entropy measures.
James C. Mathews Jr., Francisco Couzo, Aleksandr Petrov et al.
In briefFundamental Limits of Dynamic Tracking and Communication via Stationary Policies
SummaryThis paper studies joint sensing and communication, where a multi-antenna transmitter communicates with a receiver while tracking a moving target. The sensing-communication trade-off is formulated as a rate-distortion problem, with a tractable outer bound on tracking error derived via the posterior Cramér–Rao bound. Under stated assumptions, stationary randomized Markov policies are shown to suffice, leading to a Gaussian covariance-control outer bound. Numerical experiments compare this outer frontier with an achievable frontier based on an extended Kalman filter.
Mohammadreza Bakhshizadeh Mohajer, Luca Barletta, Alex Dytso et al.
In briefDNN-Assisted Near-Optimal SCMA Codebooks for Rician Fading Uplink Channels
SummaryThis paper addresses Sparse Code Multiple Access (SCMA), a non-orthogonal multiplexing technique for next-generation networks, and proposes a deep neural network (DNN)-assisted method for designing near-optimal uplink codebooks. The DNN is trained unsupervised, using a loss function derived from codebook structural characteristics, so no labeled data is required. Rician-factor-dependent design criteria are derived, with AWGN and Rayleigh fading as limiting cases, along with upper and lower bounds on average mutual information. Numerical results show gains over representative benchmark schemes across a range of Rician factors and good error-rate performance in the error-floor region.
In briefA hyperbolic bound on how fast two files can be retrieved from DNA storage
SummaryThe paper studies how sharing coding redundancy between two files affects their expected retrieval times in DNA-based storage. It focuses on two files encoded by a systematic linear code over a finite field. The authors prove a conjecture that the sum of each file's dimension divided by its expected retrieval time is at most one, provided one file has dimension greater than one. The proof uses a geometric view of growing spans and a sharpened projection bound.
In briefCompetitive optimality of Bell-Cover randomization in testing by betting
SummaryThe paper extends the Bell-Cover randomization result to testing by betting for composite nulls and simple alternatives. It shows that the randomized numeraire e-variable UE* beats any other e-variable with probability at least one half. The authors prove this competitive optimality is equivalent to the numeraire inequality E_Q[E/E*] ≤ 1, and they discuss its costs in expected log wealth and power.
In briefSimple deterministic auctions for selling multiple items
SummaryThis paper studies a single buyer with multiple items whose values are independent but not necessarily identically distributed. It analyzes the approximation ratios of three simple deterministic auctions: selling items separately, selling them as one bundle, and choosing the better of the two. For two i.i.d. items, the authors derive an exact tight ratio, and for general cases they prove that optimal revenue is at most 3 times the maximum of the two simple auctions' revenues, improving earlier bounds.
WhyConstructs novel tight Lagrangian dual certificates resolving the iid two-item approximation ratio, and improves the multi-item revenue comparison constant from 6 to 3 with rigorous analysis.
In briefA truthful-in-expectation method for fairly splitting indivisible items, guaranteeing a constant share of each agent's maximin value
SummaryThe paper studies fairly allocating indivisible goods among n strategic agents with additive valuations. The authors give a randomized mechanism that is truthful in expectation and guarantees each agent at least 1/7 of her maximin share in every realized allocation. The mechanism is also ex-ante envy-free and runs in polynomial time. This confirms a conjecture that cardinal information allows a constant ex-post MMS guarantee.
WhyResolves a conjectured gap, giving a truthful-in-expectation mechanism with constant ex-post MMS guarantee and polynomial-time implementation.
In briefDynamic wakeup when collisions are costly: a randomized algorithm
SummaryThis paper studies the wakeup problem on a shared communication channel, where packets become active at arbitrary times and a transmission succeeds only when exactly one packet sends. The authors propose Lowball, a randomized algorithm that needs neither collision detection nor knowledge of the number of packets. They measure performance by both latency and a per-collision cost C, and show that for large C the expected latency and expected collision cost are O(C^{1/2+ε} ln C) and O(√C).[ ]
In briefA simple proof of the group-theoretic Zhang-Yeung inequality
SummaryThis paper addresses the Zhang-Yeung inequality, the first non-Shannon-type inequality valid for all entropic vectors. Earlier work showed a one-to-one link between linear entropy inequalities and multiplicative inequalities on subgroup cardinalities of finite groups, but a direct group-theoretic proof of Zhang-Yeung was missing. The authors give a direct proof of this group-theoretic version using elementary group-theoretic and counting arguments.
In briefMemory in the Sky: Drone Memories Combined to Answer Low-Altitude Questions
SummaryThis paper studies low-altitude question answering (LAQA), where memories gathered by several drones are combined at a ground server to answer questions about long-term observations. It proposes a generative adversarial exam (GAE) to measure memory quality and a memory-centric framework (MemCen) that jointly selects drones and allocates transmit power under communication limits. MemCen reports QA accuracy of 92.4% and 84.0% in CARLA Town04 and Town05, and 88.5% on the PMAS real-world benchmark.
In briefBinary k-center with a hard threshold, applied to delegated voting
SummaryThe paper studies covering binary strings of equal length, some possibly with missing entries, using a fixed number of center strings so that each input is within a given relative distance of its closest center. It is motivated by multi-issue approval voting, asking how representatives should be designed before an election so that as many voters as possible are willing to delegate. The authors give a complete picture of computational complexity across the number of centers and the agreement threshold when entries may be missing. For the case without missing entries, they extend the hardness results to any number of centers and large thresholds, leaving a narrow threshold range unresolved.
Jakub Dargaj, Aris Filos-Ratsikas, Paul W. Goldberg
In briefOnline resource allocation where budgets can be refilled
SummaryOnline resource allocation is a framework for sequential decisions under budget limits, usually assuming budgets can only decrease. This paper studies a more general setting where actions can either consume or replenish resources, motivated by inventory systems and energy markets. The authors propose a dual-based algorithm that recovers best-of-both-worlds guarantees in the standard case and improves them when the replenishment factor is positive. It achieves Õ(√T) regret in stochastic settings and Õ(√T) α-regret in adversarial settings, and strictly satisfies budget constraints.
Eleonora Fidelia Chiefari, Francesco Emanuele Stradi, Alberto Marchesi
