In briefExact Cap Response and Aperture Selection for Molecular Communication under Aligned Drift
SummaryThis paper studies spatial reception in molecular communication, where directed molecule transport requires balancing useful capture against intersymbol interference. It analyzes a fully absorbing spherical receiver that counts absorptions only within a prescribed cap, deriving exact impulse, cumulative, and eventual responses from the joint first-hitting law under aligned drift. The responses are checked with particle simulations and time-step comparisons. For a 0.15 s symbol duration, the signal-to-interference difference (SID)-maximizing aperture grows from 29.13° at zero drift to 61.86° at 40 μm/s drift.
In briefEntropy Inequalities and Limit Theorems in Boolean Probability
SummaryThis paper studies Boolean entropy and Fisher information, proving a fractional Stam inequality and an entropy power inequality for sums of Boolean independent random variables. It also establishes a Boolean analogue of Barron's entropy convergence result along the Boolean central limit theorem. Under finite fourth moment assumptions, the authors derive explicit asymptotic rates for entropy-related quantities, and the approach relies on the Nevanlinna representation of Cauchy transforms.
In briefFormalizing Rate-Distortion Theory in Lean to Align Information Theory with Formal Verification
SummaryThis paper presents the first Lean formalization of core components of rate-distortion theory, a key framework for lossy compression and machine-learning analysis. Formalized information theory has so far focused almost entirely on Shannon's lossless theorems. The authors discuss the alignment challenges of translating definitions such as distortion measures, typicality and achievability into a proof assistant. They provide a reusable library of definitions and lemmas faithful to textbook conventions.
In briefBinary Cyclic Gradient Coding for Exact Recovery and Compression Robustness
SummaryThe paper introduces binary cyclic gradient coding (BCGC), an exact gradient coding scheme for n workers and up to s stragglers, whose encoding matrix is binary and decoding needs only a single summation. It proves that a binary coded scheme with compression is equivalent to an uncoded compressed scheme on a coarser data partition, explaining its stability where MDS codes diverge. Experiments on four datasets confirm the theory.
Hassan Ou-azzou, Imad Kissami, and El Houcine Bergou
In briefUndirected network coding enables faster external-memory integer sorting
SummaryThe paper gives a finite counterexample showing that, in undirected networks, network coding and fractional routing can achieve different rate combinations, contrary to the multiple-unicast conjecture. Using the counterexample's linear structure, it proposes a deterministic external-memory integer sorting algorithm whose block-transfer count is asymptotically smaller than the classical comparison-sorting bound in some parameter ranges. The algorithm's correctness and I/O complexity bound are formally verified in Lean.
WhyA finite counterexample to the multiple-unicast conjecture yields a deterministic external-memory integer sort beating the comparison I/O bound, with Lean-verified proofs.
In briefNo-regret learning when attacker types are unknown and bounded in a Stackelberg security game
SummaryThe paper studies a defender who repeatedly allocates security resources in a Stackelberg security game without knowing the set of attacker types, only an upper bound K_max on their number. If the defender observes each attacker's type, it achieves regret Õ(nK_max√T). If it only sees the attacked target and types come from an infinite universe, every algorithm has regret at least T−2. If the defender is told every B rounds which types have appeared, sublinear regret Õ(nK_max^{4/3}T^{2/3}+K_max B) is recovered.
WhyFully characterizes no-regret learning with unknown attacker types: matching sqrt(T) rate under full observation, impossibility under partial observation, and proven unavoidable delay cost.
In briefTrimSO(2): A faster, lower-memory way to train equivariant atomic-potential models
SummaryThis paper presents TrimSO(2), an algorithm for training equivariant interatomic potential models based on SO(2) convolutions, which are used to simulate molecules and materials. It integrates the required representation transformations into the model's existing dataflow, avoiding large intermediate tensors. On A100 and H100 GPUs, it reports 2.07-2.94x training speedups and 1.53-3.16x lower peak training memory compared with PyTorch implementations.
In briefNonlinear codes with fixed distance built from moment configurations
SummaryThe paper studies the largest size of codes of length n and minimum Hamming distance d over a q-symbol alphabet. For fixed q≥2 and d≥4 it constructs nonlinear codes with redundancy at most (d-3)log_q n plus a lower-order term. For d=4 and d=5 the coefficient of log_q n matches the Hamming bound, and at d=4 the codes provably outperform all linear codes.
WhyNonlinear codes match the Hamming bound coefficient at d=4,5 and provably beat linear codes, with rigorous proofs; impact stays largely within coding theory.
In briefAccord: a composable Solana arbitration primitive that uses Schelling-point voting
SummaryThis paper presents Accord, an arbitration oracle on Solana that lets any Solana program create its own court and file disputes. A random jury drawn from a stake-weighted pool of specialized jurors reviews encrypted evidence and votes under commit-reveal, with jurors who match the final ruling earning fees and those who don't losing stake. The paper also compares the design with Kleros on EVM and discusses Solana-specific implementation details.
In briefOptimal competitive ratio for online stochastic matching with known arrivals
SummaryThis paper resolves the optimal competitive ratio for unweighted online stochastic matching when the arrival law is known. For Poisson arrivals it achieves 1-e/e^e (about 0.8206), matching a known upper bound, and for exactly n i.i.d. arrivals it achieves the same guarantee up to an additive O(n^{-1/2}) loss. The authors also show that under an unknown arrival law the optimal ratio is strictly lower.
WhyExact Poisson-exponential correspondence yields the optimal competitive ratio for known-arrival online stochastic matching, with rigorous proofs of significant subfield impact.
In briefThe Energy Cost of Input Tokens in Large Language Models
SummaryThis paper profiles the energy use of input tokens during the prefill phase of large language models, using high-resolution power measurements of Llama-3.1 and Qwen-2 on NVIDIA A100 GPUs. It finds that optimised memory management such as PagedAttention delays the scaling bottleneck of attention computation, yielding up to an 8.9x energy efficiency advantage at 112,000 tokens. The authors also compare the energy gap between input and output tokens across serving systems and propose context-scaling laws.
In briefJoint Identification, Transmission, and Sensing Over Channels With Feedback
SummaryThis paper studies a discrete memoryless channel whose state varies, with noiseless feedback, where the transmitter uses randomized encoding to send messages, perform identification, and estimate the channel state under an average distortion limit. The authors derive a single-letter characterization of the capacity-distortion region for this joint task. Transmission rate is given by mutual information and identification rate by output entropy, both constrained by the sensing requirement on input distributions.
Vida Gholamian, Marcel A. Mross, Roberto Ferrara et al.
In briefCapacity limits for optical interference channels under average power limits
SummaryThis paper studies multiuser wavelength-division multiplexed optical links, where Kerr nonlinearity and chromatic dispersion cause interference. It replaces earlier peak power constraints with average input power constraints, which are more practical. The authors derive closed-form single-user capacity bounds in the high-SNR regime and give a finite-SNR extremality result under stated assumptions. They build an achievable region via time sharing and report split-step Fourier simulations that support the conclusions at practical launch powers.
In briefDynamic 3-coloring of bipartite graphs with optimal locality
SummaryThis paper presents a dynamic graph algorithm that maintains a 3-coloring of bipartite graphs under edge insertions. Color changes are confined to a radius of O(log n) around the inserted edge, giving an upper bound on locality in the dynamic-LOCAL model. The bound is tight, since a result by Chang et al. (PODC 2024) shows a matching Ω(log n) lower bound in the stronger online-LOCAL model. The result thus closes the gap between dynamic and online locality for this problem.
Yann Bourreau, Filippo Casagrande, Tim G\"ottlicher et al.
In briefEfficient construction of subspace-design codes over a constant alphabet
SummarySubspace-design codes are a central framework in coding theory, and recent work gave the first explicit versions over constant-size alphabets. This paper presents an explicit construction of r-dimensional subspace-design codes over a constant alphabet whose size grows exponentially in r, which is smaller than the doubly exponential size in a recent result. The construction uses modified algebraic geometry codes and admits efficient encoding, scaling quadratically with block length and linearly with r. The authors also generalize multiplicity codes to algebraic geometry codes and prove they achieve optimal parameters.
WhyModified algebraic geometry codes give constant-alphabet subspace-design codes with exponentially smaller alphabet than prior doubly-exponential bound, with efficient quadratic encoding and proofs.
In briefProof that the Two-Level Poset Game is PSPACE-complete
SummaryPoset games are a class of combinatorial games that includes classics such as Nim and Chomp. Determining the outcome of poset games of height at most three was already known to be PSPACE-complete, but the complexity for height at most two remained open for over a decade. This paper resolves the question by a polynomial-time reduction from Avoid True on positive CNF formulas, showing the Two-Level Poset Game is PSPACE-complete.
WhyResolves a decade-old open question on height-two poset games by a polynomial reduction from Avoid True, proving PSPACE-completeness.
In briefHow Sparse Matrix Update Schedules Can Be Reused When Changed Rows Shift
SummaryThis paper studies when reusing a prepared tiled schedule pays off in incremental sparse matrix multiplication, where only a few input rows change per step. Across 21 SuiteSparse matrices and controlled change patterns, a direct column-wise incremental update was 2.1 to 8.2 times faster than the best of eight full-recomputation codes. The direct update also beat the tiled, schedule-caching executor in 779 of 837 workloads. The authors conclude that matrix structure and how the changed rows move determine whether reuse is worthwhile, rather than schedule sophistication.
Hunter Horne (HorneSci), Eric Spencer (Loyola University Chicago, HorneSci) et al.
In briefWhat You Earn from What You Learn: How the Value of Information Is Characterized and How Hard It Is to Compute
SummaryThis paper studies the value of information in extensive-form decision problems, defined as the largest multiplicative gain a decision maker can obtain from an information refinement across all payoff environments. It gives a unifying characterization linking this value to the maximum fractional chromatic number over a family of conflict graphs. The authors show that computing the value of perfect information is NP-complete, and computing the value of recall is S2P-complete.
WhyUnifies value-of-information characterization via fractional chromatic number and proves NP- and S2P-completeness results, a strong theoretical advance with mainly theory-community impact.
Ratip Emin Berker, Ioannis Anagnostides, Emanuel Tewolde et al.
In briefWeak private information retrieval for graph-based storage under ε-privacy
SummaryThis paper studies Graph-based Weak Private Information Retrieval (G-WPIR), where servers are graph vertices and each file is stored on the two servers its edge connects. The authors adapt an existing G-WPIR scheme for arbitrary graphs and analyze its performance under an ε-privacy metric. They establish a lower bound on expected download cost for arbitrary graphs and derive an explicit rate upper bound for complete graphs. The paper also shows achievable rate-privacy trade-offs for complete graphs and complete bipartite graphs.
In briefHigh-girth quantum LDPC codes built from circulant and affine permutation matrices
SummaryThe paper studies two explicit constructions of binary CSS quantum LDPC codes with check weight six. The first, based on a fixed circulant shift pattern, gives codes with parameters [[6N, 2N+2, 6]] and Tanner graph girth twelve for N=31 and all N≥37, with exact distance established via a weight-six logical operator. The second uses fixed matrix polynomials with circulant and affine permutation coefficients, yielding four realizations with Tanner girth eight and computationally certified distances.
Vahid Nourozi, Roxana Smarandache, and David G. M. Mitchell{\dag}
In briefParallel sparse output writing for tensor compilers
SummarySparse tensor compilers optimize tensor operations on complex sparse data structures, but little prior work has addressed parallel versions. This paper presents Birdseed, described as the first tensor compiler to support all loop orderings over any standard sparse format in parallel. It writes directly into list, bytemap, hash, and dense levels of fibertree formats. The authors report asymptotic memory and time improvements over prior work and empirical speedups on kernels such as histogram construction and SpMSpV.
In briefCapacity of Noisy Torn Paper and Noisy Shuffling Channels
SummaryThe paper studies channels that split a codeword into fragments and return them in scrambled order, with the noisy version also adding bit substitution errors to each fragment. The authors establish a capacity upper bound for the noisy torn paper channel that matches the achievable rate of Ravi, Vahid, and Shomorony, resolving their conjecture. They also determine the capacity of the noisy shuffling channel, where all fragments have equal length, answering an open question posed by Shomorony and Heckel.
WhyProves a capacity upper bound matching the known achievable rate, resolving a conjecture and open question in information theory.
In briefFair splitting of two item types using maximin share
SummaryThis paper studies how to fairly divide indivisible items among several agents with additive valuations or costs, using the maximin share (MMS) fairness criterion. Because MMS allocations are not always guaranteed to exist when there are more than two agents, the authors focus on special instance classes where exact allocations can be ensured. They show that when items are two types of chores, MMS allocations always exist and can be computed in polynomial time using a geometric approach inspired by job scheduling. The paper also discusses extensions to two types of goods and to mixed instances with one good type and one chore type.
WhyProves MMS allocations always exist for two chore types with polynomial-time computation, using a novel geometric technique inspired by scheduling.
In briefA discrete version of Fisher information explained
SummaryThis paper studies a discrete analogue of Fisher information. Using a discrete Laplacian operator, the authors build a discrete version of the score function and from it define the information measure. This gives a natural framework for proving several information-theoretic inequalities in the discrete setting.
In briefTracing knowledge lineage to remove data across mutually distilled federated models
SummaryThis paper studies federated unlearning when an edge server and nearby devices train language models of different sizes through mutual distillation. A removal request applied to one model is insufficient, because the removed data's influence has been copied into other students whose uploads can teach it back to the corrected teacher. The authors propose HERD, which builds a knowledge lineage graph from existing server transfers, weights edges by transfer type, and selects the cheapest set of holders to correct so the cumulative residual is bounded. On TOFU, HERD leaves 18% to 52% less cumulative residual than the strongest baseline at 6% to 12% of its correction cost.
In briefA distributed relay framework that delivers drone energy to areas without infrastructure
SummaryThis paper addresses limited drone flight time in infrastructure-less regions such as remote wilderness, mountains, and disaster areas. It proposes a Distributed Energy Relay Framework in which porter drones cooperatively deliver batteries through a relay-and-cache transportation mechanism. Stations bid their delivery capability to a mission coordinator, which selects a low-cost coalition that meets mission requirements. Analytical evaluation shows how battery and drone characteristics affect energy delivery and supports the framework's effectiveness for sustaining drone missions.
In briefOptimal Test for Distribution Support Size
SummaryThe paper presents an optimal tester that decides whether an unknown probability distribution is supported on n elements or is ε-far from such a distribution in total variation distance. Its sample complexity is Θ(n/(ε log n)), improving on the earlier O(n/(ε log n) · log(min{1/ε, n})) bound of Ferreira Pinto Jr. and Harms (STOC 2025). The authors also provide a fairly good lower bound on support size.
WhyRemoves a logarithmic factor from prior support-size testing bounds, giving a matching optimal sample complexity with rigorous theoretical proof.
In briefEquality Conditions for Han- and Shearer-Type Information Inequalities and Their Combinatorial Uses
SummaryMadiman and Tetali proved strong and weak fractional inequalities that generalize classical entropy subset inequalities such as Han's inequality and Shearer's lemma. This paper decomposes the gap in the strong fractional inequality and uses it to give necessary and sufficient conditions for equality in the strong form of Han's inequality. The weak fractional inequality is then applied to an extremal graph theory problem, recovering and extending results of Sason (2022) and Boucheron et al. (2013).
Gunank Jakhar, Gowtham R. Kurri, Suryajith Chillara et al.
In briefCLS-hardness of 2D min-max optimization with product constraints
SummaryThis paper studies how hard it is to compute approximate first-order Nash equilibria in min-max optimization with one-dimensional min and max players under product constraints. With black-box access to the objective, any algorithm needs Ω(1/√ε) queries to find an ε-first-order Nash point. In the white-box setting, the authors show CLS-hardness by reduction from End-of-Potential-Line, implying even this simplest case is at least as hard as CLS.
WhyExtends first-order Nash hardness to CLS-completeness and gives a query lower bound for low-dimensional min-max, a notable advance via reduction and lower-bound proofs.
Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis et al.
In briefSolomonoff induction for selected bits and online classification
SummaryThis paper studies the prediction error of Solomonoff induction, a general sequence prediction method, on bits fixed by a computable pattern. The authors show that for some patterns the sum of per-position errors is unbounded, but the sum of squared errors is exponentially bounded in the pattern's program length. For bits fixed by a computable classification function, the squared-error sum is polynomially bounded, indicating faster convergence.
In briefRIS- and user-relay-assisted cooperative rate-splitting multiple access for full-duplex communication
SummaryThis paper studies a cooperative rate-splitting multiple access (C-RSMA) framework that uses a reconfigurable intelligent surface (RIS) and user relaying to improve wireless transmission. The authors jointly optimize the base station's transmit beamformers and the RIS's reflective beamformer to maximize common and private rates under a transmit power constraint. Because the variables are coupled and strong residual self-interference is present, the problem is described as NP-hard, so a low-complexity alternating optimization method is proposed. Simulations reportedly show higher sum-rate than RIS-assisted SDMA, half-duplex RSMA, and SDMA without RIS.
In briefOrrery: Simulating GPU-direct MPI communication with SimGrid
SummaryThe paper presents Orrery, a layer built on SimGrid's SMPI that models GPU-aware MPI communication for simulating HPC applications. It intercepts GPU memory allocations, kernel launches, data transfers, and MPI operations, and models them according to target system specifications, so simulation runs without physical GPUs. The authors validate Orrery with CUDA-aware MPI microbenchmarks and a Jacobi solver on up to 32 nodes of the MUSICA supercomputer, reporting that it reproduces key GPU-aware MPI mechanisms.
Ahmad Moh'd Saleh A. Belbeisi, Amir Raoofy, Josef Weidendorfer et al.
In briefRevisiting Cauchy-Schwarz norm bounds for detecting silent data corruption in LLM inference
SummaryThis paper examines Cauchy-Schwarz Norm Bounds (CSNB) as a low-overhead way to detect silent data corruption caused by hardware faults during LLM inference, comparing it with Algorithm-Based Fault Tolerance (ABFT). On dense LLM linear layers, CSNB keeps 99% of ABFT's fault detection capability while cutting verification overhead by 87% and threshold determination overhead by 67%. For Mixture-of-Experts router gate computations, CSNB retains only 55% of ABFT's detection capability, so the authors suggest checksum-based verification remains preferable there.
Anton Altenbernd, Dylan Everingham, Philipp Wiesner et al.
In briefTremulant: Unpredictable Delays in Serverless Platforms Beyond the 99th Percentile
SummaryThis paper analyzes several million requests across seven Function-as-a-Service (FaaS) platforms and finds that the slowest warm starts can be hundreds of times slower than the median. A virtual machine used as a baseline was substantially more consistent. The effect is confirmed using four independent public datasets spanning 2020 to 2025. The authors note that warm starts make up a growing share of the most extreme latencies, so cold-start mitigation alone cannot remove them.
