In briefTight limits on online selection with downward-closed constraints
SummaryThis paper studies online selection problems under arbitrary downward-closed feasibility constraints, considering different arrival orders and distributional assumptions. It establishes bounds for the standard adversarial-order prophet problem, the Bayesian random-order prophet secretary problem (and by extension the standard secretary problem), and the free-order prophet problem. Combined with earlier complementary results, these bounds pin down the asymptotically tight competitive ratios for these variants.
WhyThe authors establish tight competitive-ratio bounds for downward-closed prophet and secretary problems across several arrival orders, separating random-order from free-order models.
In briefLocality and Interference in Radio Multicasting: Structure and Scheduling
SummaryThis paper studies multipoint-to-multipoint multicasting in synchronous radio networks where participant locations are unknown and messages can be freely aggregated. It gives completion-time bounds for several schedules, including ones based on distance-two coloring, geometric data in unit disk graphs, strong selectivity, and random transmission. For one-hop designated delivery, it proves that the optimal schedule length equals the chromatic number of a conflict graph and is at most 2b−1.
In briefExplicit codes correcting insertions, deletions, and substitutions via multicoloring
SummaryThe paper constructs explicit q-ary codes of length n that correct any combination of at most t insertions, deletions, and substitutions. Their redundancy is 2t·log_q n plus O(log log n) q-ary symbols, matching the leading term of Levenshtein's classical existential bound. The approach uses a prime-based multicoloring of the edit-confusion graph, and the construction supports deterministic encoding and decoding.
WhyThe authors use prime-based multicoloring of the edit-confusion graph to match Levenshtein's leading redundancy term 2t log_q n, with deterministic encoding and decoding time bounds.
In briefInformation spectrum methods for multiple-access channels, Part III: strong converse for the K-user Gaussian case
SummaryThis is Part III of a series on K-user multiple-access channels. Starting from two fundamental lemmas, the authors derive the capacity region of the general K-user MAC with cost constraints and show it contains the polymatroid capacity region of the K-user Gaussian MAC. Using an information spectrum calculation, they prove that rate tuples outside the capacity region yield error probabilities tending to one, establishing the strong converse. This strong converse was first established by Fong and Tan.
In briefCapacity limits for multi-user channels that stay fixed during each codeword
SummaryThis paper studies the ε-capacity regions of two-user mixed multiple-access channels with finite alphabets, where the channel law stays fixed across a codeword, as in a slowly fading link. The authors derive a single-letter inner bound and an outer bound called the outage region, and show that the two coincide for well-ordered mixed MACs. They also extend Ahlswede's strong converse to K users.
In briefAutonomous Mobile Robots on a Computing Field: a model where the floor itself computes
SummaryThe paper introduces CABOT, a model in which the discrete plane robots move on is an active cellular automaton rather than a passive stage. The robots are deliberately weak, seeing only nearby cell states and robot positions, so the number of floor states becomes the measure of required resources. The authors show that a handful of states enables line formation, gathering and exploration, and prove that gathering and line formation cannot be solved when the floor must stay silent.
WhyThe authors recast the grid floor as a cellular automaton, reporting solvability and impossibility results for line formation, gathering and exploration with few states.
In briefAn optimized Mirabbasi-Martin pulse shaping filter for higher-order modulation in Zak-OTFS
SummaryThis paper proposes a separable two-dimensional Mirabbasi-Martin (MM) filter for Zak-OTFS modulation, together with a coefficient optimization method that minimizes aggregate sidelobe energy while keeping a compact structure. The optimized filter has no sidelobes and the narrowest -40 dB delay-Doppler pulsewidth among the compared sinc, Gaussian, and GS pulses, which confines pilot energy and reduces pilot-data interference. Simulations show better uncoded and coded bit error rate for higher-order QAM than these alternative filters.
In briefRegime-Uncertain Data Transactions: A Game-Theoretic Framework for Self-Adapting Multi-ML-Agent Systems
SummaryThe paper studies how autonomous ML agents in large organizations exchange data across legal boundaries when the applicable rules are uncertain. It models each exchange as a game between two agents and an enforcer, where agents hold beliefs about which rules apply and bargain over legal bundles using a method called LCNB. In a synthetic simulator covering GDPR, DPDP, CCPA/CPRA and a stricter regime, a citizenship-based rule violated 21–37% of shared records in two of three stress cases, while LCNB violated under 1%. The authors note limits, including that under default settings LCNB shares mostly aggregates, which partly explains its low violation rate.
In briefSS-HSDP: Faster, More Flexible Sharded Training by Decoupling Runtime and Update Parameters
SummaryThis paper presents SS-HSDP, a training framework that separates runtime parameters from update parameters so that computation layouts and optimization units can be organized independently. Using shared data views and hierarchical sharding, it avoids redundant data movement and supports optimizers such as Muon, along with fully zero-copy execution. In experiments on video and language model training with MXFP8, it achieves higher Model FLOPs Utilization than FSDP2, veScale-FSDP, and Megatron-FSDP. At 128 GPUs, MFU improves by up to 21.7% over the fastest baseline, with comparable or lower peak memory.
In briefLinear-order improvement of the Gilbert-Varshamov bound for linear and quantum codes
SummaryThis paper concerns the Gilbert-Varshamov bound, a standard benchmark for the existence of error-correcting codes. For q-ary linear codes, the best previously known general improvement was of order Θ(√n). The authors use a new viewpoint that tolerates O(n) low-weight points and removes them together at the cost of one dimension, yielding a Θ(n) multiplicative improvement for linear codes of arbitrary rate. The method is also extended to quantum codes, giving a Θ(n) improvement of the quantum GV bound for a stated range of relative distances.
WhyThe authors achieve a Θ(n)-multiplicative GV improvement for linear codes by allowing O(n) low-weight points and eliminating them jointly, extended to quantum codes.
In briefFlexible metasurfaces that reshape the array to improve secure wireless transmission
SummaryThis paper studies secure wireless transmission from a multi-antenna transmitter to one receiver in the presence of a multi-antenna eavesdropper, using a flexible intelligent metasurface whose shape can be changed. The transmit covariance matrix and the surface shape are jointly optimized to maximize secrecy rate, using a block coordinate ascent algorithm. Numerical results show higher secrecy rate than a conventional rigid antenna array, with about 2.5 dB transmit-power saving at the same secrecy rate.
In briefStrategically Robust Multi-Agent Control: A New Equilibrium Between Game-Theoretic and Robust Control
SummaryThis paper introduces strategically robust multi-agent control, which fills the gap between game-theoretic control and robust control. In dynamic games, players seek protection against misspecified control policies of other players, leading to a new equilibrium concept called strategically robust dynamic equilibrium. The authors study this concept in canonical open- and closed-loop settings. Numerical experiments on vehicle platooning, inventory management, and network control show resilience to misspecification and cases where strategic robustness improves performance or social welfare.
In briefUniversal optimality on finite Lee tori: which equal-size point sets minimize pair energy on finite Lee tori for all potentials of a given class.
SummaryThe paper studies subsets of finite Lee tori that minimize pair energy among sets of the same size, for every discretely completely monotone potential. At half occupancy on a product of even cycles, the two checkerboard sets minimize both total and maximum individual energy, and they are the only minimizers for nonconstant classical completely monotone potentials, proving the checkerboard conjecture for this class. The paper also characterizes when universally optimal sets exist at the independence number and gives a characterization at density 1/5 in Z_5^n via weighted counts of pairs at distances one and two. The proofs use integer box occupancy bounds and Fourier certificates.
WhyThe authors prove the checkerboard conjecture and characterize universally optimal sets on finite Lee tori using integer box occupancy bounds and Fourier certificates, with impact mostly confined to c
In briefSnoopie: A Multi-GPU Communication Profiler and Visualizer
SummaryThis paper presents Snoopie, a profiling tool for multi-GPU systems that tracks peer-to-peer GPU data transfers and calls from GPU-centric communication libraries. It attributes data movement to source code lines and data objects, and offers visualizations from system-wide views down to specific instructions and addresses. Case studies show its use in monitoring data movement, finding performance bugs, and understanding transfers hidden beneath communication libraries. The tool is publicly available.
Mohammad Kefah Taha Issa, Muhammad Aditya Sasongko, Ilyas Turimbetov et al.
In briefDesigning Information in a Forest: Algorithmic Aspects
SummaryThis paper studies Bayesian persuasion where a sender reveals information to multiple receivers whose information hierarchy is a pre-specified directed forest. Using a binary state and binary actions, it extends a tractability result for symmetric sender utility from private persuasion to the forest setting and gives a polynomial-time algorithm for modular utility. For supermodular utility, the problem is shown to be NP-hard with no FPTAS unless P=NP, and an approximation algorithm whose ratio depends linearly on the forest depth is provided.
In briefSmoothed Analysis for Distributed Maximal Independent Set
SummaryThis paper studies smoothed analysis of the distributed Maximal Independent Set (MIS) problem, where each edge of an arbitrary base graph is independently toggled with probability p. When p is about β·ln n/n for a large constant β, a randomized LOCAL algorithm computes an MIS in O(√log n) rounds with high probability, beating the worst-case lower bound. Conversely, for p at most (1/2−δ)·ln n/n, some base graph forces every randomized LOCAL algorithm to need Ω(log n/log log n) rounds, so the smoothing required is optimal up to a constant factor.
WhyThe authors apply smoothed analysis to distributed MIS, reporting O(√log n)-round randomized LOCAL algorithms and a nearly tight matching lower bound.
Dipan Dey, Fabien Dufoulon, William K. Moses Jr. et al.
In briefParallel computing systems for choosing the optimal process equipment
SummaryThis monograph studies how to select equipment for multiproduct batch chemical plants, a large NP-hard optimization problem that minimizes total capital cost while keeping the plant operable. The authors develop a branch-and-bound algorithm and parallel versions for shared-memory, cluster, and GPU systems. They also propose a hybrid method combining Ant Colony Optimization and Simulated Annealing, implemented on GPUs. Experiments report that the parallel hybrid algorithm finds solutions within 0.01% of the branch-and-bound optimum in tens of seconds, compared with tens of hours.
In briefA constructive theory for closed-form rate-distortion functions (methods for deriving exact formulas of rate-distortion functions)
SummaryThis paper develops a posterior-based construction framework for rate-distortion functions, using conditional entropy as a common distortion coordinate. It proves entropy-level attainability for finite-alphabet discrete sources and for absolutely continuous sources with integrable log densities, via constructive rate-entropy coding. The authors derive exact expressions for several source models, including Gamma, zeta, and negative binomial sources under specified distortion measures and intervals.
In briefMegaOps: A Kernel Overlapping Framework Combining PyTorch-style Modularity with Megakernel Speed
SummaryThe paper presents MegaOps, a framework that keeps the one-GPU-kernel-per-operator design of PyTorch-style ML frameworks while removing barriers between dependent kernels. Instead of fusing operators into a single megakernel, it runs dependent kernels on separate CUDA streams and synchronizes them on individual tiles of the intermediate tensor. Evaluated on dense Llama3 and Qwen3 models across H100, A100, and L40 GPUs and multi-GPU servers, MegaOps matches hand-tuned ThunderKittens megakernel throughput. It reaches 1.09 to 1.10 times the best baseline's decode throughput and 0.98 to 1.10 times its prefill throughput.
WhyThe authors remove kernel barriers via tile-level dependencies without fusing kernels, reporting parity with ThunderKittens megakernels and 1.09-1.10x decode throughput on Llama3 and Qwen3.
In briefCore nonemptiness for 2/3-convex games: whether a relaxed class of cooperative games always has a stable payoff allocation
SummaryThe paper studies the core of 2/3-convex games, a generalization of convex games in which at least two of any three distinct coalitions satisfy the supermodular inequality. It shows that every such game has a marginal worth vector in the core, so the core is nonempty, and the proof is constructive, yielding a linear-time algorithm for a core allocation. The authors also examine how 2/3-convexity relates to permutational convexity and introduce a model based on the OSCE's consensus-minus-two procedure, showing it is 2/3-convex but not necessarily convex.
Keisuke Bando, Toshiyuki Hirai, Kenzo Imamura et al.
In briefFaster Serverless LLM Cold Starts Through Shared and Prewarmed Startup Work
SummaryThe paper observes that serverless LLM cold starts take about a minute, with only 5-11% spent loading weights and most time going to repeated compilation, memory profiling and runtime setup. It presents Cairn, which lets the first server publish weights and engine artifacts to a CXL memory pool shared across the cluster, so other servers read them in place, and completes model-independent setup ahead of time in warm containers. Using ServerlessLLM on vLLM v0.20 with six models from 1B to 14B and an emulated shared CXL pool, Cairn reports 4.1-5.2x faster cold starts on servers without their own checkpoint and a 64% reduction in median TTFT.
In briefConcatenated codes with one inner code achieving low-rate Gilbert-Varshamov distance
SummaryThe paper studies concatenated codes that use one binary inner code for all outer coordinates, with outer codes taken as random subcodes of scaled algebraic codes. It gives a general upper bound on the probability that the minimum distance fails, along with conditions for exponential decay. Using algebraic-geometric codes from the Garcia-Stichtenoth tower, it constructs random binary codes with rates approaching ε² whose distance matches the leading coefficient of the Gilbert-Varshamov bound at low rates, with polynomial-time encoding and unique decoding.
WhyThe authors combine one inner code with subcodes of Garcia-Stichtenoth algebraic-geometry codes, reporting a low-rate GV-matching distance bound with exponential failure probability.
In briefSpeeding up distributed variational quantum computing over wireless networks by designing incentives for quantum processors
SummaryThe paper addresses the low willingness of quantum processors to take part in distributed variational quantum computing (DVQC). It proposes a two-stage incentive framework: first, it jointly optimizes subcircuit parameters, noise measurements and transmit power to reduce processor energy cost; second, it selects a subset of processors to maximize aggregator-side system utility. Experiments on MNIST and CIFAR-10 show performance comparable to centralized quantum computing and better energy efficiency and system utility than baseline schemes.
In briefTwo-stage secret sharing: distributing shares when a secret is revealed in parts
SummaryThis paper gives an information-theoretic model of two-stage secret sharing, for secrets that become available in parts. Shares for the first part are distributed before the rest is known, and shares for new participants are distributed later without updating earlier shares. The authors define and characterize two-stage access structures, derive a universal lower bound on the first-stage information the dealer must retain, and give a construction that meets this bound. Advance sharing is presented as a special case, with its own characterization and construction.
In briefReaching Majority Consensus in h-Majority Opinion Dynamics via First-Repetition Rules (Paper)
SummaryThis paper studies h-Majority dynamics, in which n agents holding one of k opinions each round sample h agents and adopt the most frequent opinion among them. The authors show that for any h≥3, if the initial majority's bias is large enough, consensus on the initially most frequent opinion is reached with high probability within O((1+n/(h²M₀)) log n) rounds. The central tool is a comparison principle showing that, among symmetric rules, plurality maximizes the gap between the most frequent opinion and any competitor.
WhyThe authors use a comparison principle to reduce one round of h-Majority to DejaVu, obtaining an O((1+n/(h^2 M_0)) log n) consensus time bound under a bias condition.
Niccol\`o D'Archivio, George Giakkoupis, Fr\'ed\'eric Giroire et al.
In briefClosed-form Gaussian projections for embedded hypercube Beta-Gaussian mixtures
SummaryThis paper derives closed-form Gaussian information projections for Beta-Gaussian distributions whose tangential parts live on affine embedded hypercubes and whose normal parts are Gaussian. The optimal Gaussian is uniquely determined by moment matching, and its minimum Kullback-Leibler divergence depends only on the intrinsic Beta parameters. The construction is extended to mixtures over finite pure embedded cubical complexes, and joint convexity of the divergence yields an explicit upper bound on the approximation error.
In briefNVIDIA Vera CPU microarchitecture comparison with Grace, AMD Turin, and Intel Granite Rapids
SummaryThis paper compares NVIDIA's Vera data-center CPU, which includes its first custom core design Olympus, with AMD Turin and Intel Granite Rapids, using NVIDIA Grace as a baseline. The evaluation moves from microbenchmarks through NAS kernels and miniapps to single-socket performance of scientific codes. Vera achieves the best performance in most tested codes, which the authors attribute mainly to high memory bandwidth, effective Spatial Multithreading, and a low-latency memory subsystem. Its floating-point performance trails Intel and AMD in a few compute-bound workloads.
In briefSensor participation in distributed detection when a fixed Boolean fusion rule is required
SummaryThe paper studies distributed binary detection where the fusion node must apply a prescribed Boolean decision rule. Under conditionally independent Bernoulli observations, it derives a signed-influence path identity valid for any Boolean rule, which reduces to an exact Russo-Margulis representation for monotone rules. This yields rule-sensitive necessary conditions for a target Bayes error and an influence-weighted Kullback-Leibler feasibility bound. The authors also derive lower bounds on the number of sensors that must participate, and numerical and Monte Carlo results illustrate the bounds and the performance penalty of keeping a fixed fusion rule instead of optimal likelihood-ratio fusion.
In briefRouting vehicles to improve city sensing coverage while keeping detours near equilibrium
SummaryThis paper addresses vehicular crowdsensing, where traffic concentrates on few roads and much of a city's network goes unsensed. The authors propose a two-stage method: a non-cooperative game with diversity-weighted rewards sets each vehicle's equilibrium deviation, then the platform recommends feasible routes within a tolerance of that value that improve coverage. Experiments on London and Monaco road networks report the router reaching about 99% of the optimal coverage-penalty reduction on small instances.
In briefWorst-case online algorithm performance under input subsampling
SummaryThis paper examines whether classical competitive ratios still hold when both an online algorithm and the offline optimum are evaluated on the same subsampled input. It studies prophet inequalities and ski-rental, two canonical online problems. For any single sampling rate, the classical worst-case ratios remain unchanged, so the paper asks whether one adversarial input can stay worst-case at two different rates simultaneously. The results show that instances worst-case at one rate need not remain hard at two rates at once.
In briefOptimizing Finite-Alphabet Message Passing Decoding for Fully Node-Parallel 5G LDPC Decoders
SummaryThis paper proposes a new way to design lookup tables for the min-RCQ LDPC decoding algorithm, using Bayesian optimization over a subspace of the design space with frame error rate as the loss. The method needs no channel or modulation knowledge and works for irregular LDPC codes with puncturing and shortening. It produces iteration-agnostic tables usable in every iteration, suiting fully node-parallel decoder architectures. The authors report 38.6% better energy efficiency than a state-of-the-art normalized min-sum decoder with no loss in error correction performance.
Alexander von Bank, Oliver Griebel, Eike-Manuel Edelmann et al.
In briefEmpirical square-root law for degree discrepancy in binary m-sequences
SummaryThe paper studies primitive binary LFSR sequences of period 2^k−1 and the range of total-variation degree discrepancy over all starting offsets for windows of length r. Computed profiles for k≤28 suggest the maximum scales as Θ(√N) with N=2^k, and the authors conjecture this square-root law. The tabulated peaks are grid maxima and thus lower bounds on the exhaustive maximum.
In briefA parallel greedy method for finding maximal b-matchings in hypergraphs
SummaryThis paper presents a parallel batch-voting algorithm for computing maximal b-matchings in hypergraphs. For a fixed edge order it is deterministic and returns the same result as the sequential greedy algorithm. The authors analyze its expected work and depth under random priority orders, implement it in CUDA, and test it on real-world hypergraphs, where it runs up to 19.07 times faster than the existing greedy method when b = 5.
Saeed Bakhshan, Daniel Grosu, Henrik Reinst\"adtler et al.
In briefThe Golden Ratio: Fair Splitting of Goods with EF1 and Ordinal MMS
SummaryThis paper studies how to fairly divide goods among agents. For additive valuations, it proves that a complete allocation always exists that is both envy-free up to one good (EF1) and satisfies 1-out-of-⌊φn⌋ ordinal maximin share (MMS), where φ is the golden ratio. For bivalued valuations, where each agent has two non-negative values per good, it obtains a complete allocation that is both EFX and satisfies 1-out-of-⌈(7n-1)/6⌉ MMS.
WhyThe authors prove EF1 plus 1-out-of-floor(phi n) MMS for additive goods, improving prior bounds, and an EFX plus MMS result for bivalued valuations.
