In briefFair chore sharing with optional task removal to guarantee each participant a maximin share
SummaryThis paper studies how to fairly split heterogeneous chores among participants on web platforms while leaving as few tasks unassigned as possible. The goal is to guarantee each agent her maximin share (MMS) from the original instance. The authors prove that for any instance with at least four agents, at most n-3 chore disposals suffice, improving a prior bound and removing its dependence on the number of chores. For four agents, they show one disposal always suffices, a tight result.
In briefVS-Flash: Faster Vector Search Using Computational Flash Memory
SummaryThis paper addresses vector databases used in retrieval-augmented generation, which outgrow host DRAM and rely on SSD-based serving, causing contention and high tail latency. It proposes VS-Flash, which treats flash as a large memory-semantic space and dynamically chooses between a computational flash device for large-batch queries and the host CPU for small, latency-sensitive queries, with both sharing the same resident data. On three billion-scale datasets, the authors report average bulk-search throughput gains of 36.8X over vanilla Milvus (up to 57.4X) and up to 24.8X lower p99 latency for latency-sensitive requests under mixed workloads.
In briefProof that recovering optimal strategies in mean-payoff games is as hard as solving them from scratch
SummaryThis paper studies mean-payoff games, deterministic two-player zero-sum turn-based games on finite weighted directed graphs where players aim to optimize the limiting average of edge costs. It gives a simple reduction from solving these games to the strategy recovery problem, showing that recovering optimal strategies given the vertex values is essentially as hard as solving the game without knowing those values. The authors further show that finding one player's optimal strategy stays hard even when the other player's optimal strategy and all values are known.
In briefpanvram: GPU-resident random access to a human pangenome cohort
SummaryThis paper presents panvram, a method for repeatedly sampling short sequence windows from a human pangenome. Each assembly is stored as a reference-relative block archive, and these archives are pooled on a GPU. For 558 haplotype assemblies, the default q4k form occupies 16.642 GB of persistent pools including the decoded reference, versus 11.634 GB for a compact form. Throughput figures come from batch API measurements and are not pooled as repeated trials in one environment.
In briefOne-shot joint classifier rebuilding across layers for federated learning
SummaryThis paper addresses classifier bias caused by non-IID data in federated learning, noting that classifiers built from intermediate-layer representations can outperform those using the last layer. The authors propose FLARE, which, after training, has clients perform one forward pass to gather class-conditional statistics and lets the server build a cross-layer joint ridge classifier with an adaptive coupling coefficient. Experiments across 11 datasets and 8 architectures report an 11.35% accuracy gain as a plug-and-play post-processing step requiring only one extra communication round.
In briefOff-tree forwarding to speed Plumtree broadcasts from any source
SummaryPlumtree builds a spanning tree in a gossip overlay for broadcasting, but the tree is optimized for the first source, so broadcasts from other nodes can take long detours. This paper proposes probabilistic exuding, where nodes near the source also forward payloads over non-tree links with a set probability, without changing the shared tree. In simulations on a 1000-node random regular overlay with random sources, it reduced 95th-percentile delivery latency by about 40% compared with Plumtree.
In briefMoney-free scheduling via sampled pairwise externality compensation
SummaryThis paper studies how to allocate a shared resource without money when agents have private, stochastic demands, can queue, and may act strategically or adversarially. The authors introduce Sampled Pairwise Externality Compensator (SPEC), which replaces exact future-externality calculations with sampled estimates to stay computationally efficient. In a stochastic scheduling model, the mechanism guarantees each agent a near-optimal worst-case fraction of its ideal utility, and this fraction approaches 1 as the job expiration probability vanishes.
David X. Lin, Chido Onyeze, Giannis Fikioris et al.
In briefIneffective GPU Occupancy in Heterogeneous Clusters and a Readiness-Aware Scheduler
SummaryThis paper studies heterogeneous GPU clusters where allocated GPUs often stay occupied without ever becoming ready to compute, which the authors call ineffective occupancy. On an Alibaba GPU trace, 52.70% of execution records never became ready. The proposed Readiness-Aware Scheduling (RAS) uses nine admission-time attributes to predict readiness and reorders admissions, reaching an ROC-AUC of 0.8187 under machine-grouped five-fold validation. RAS reduces the ineffective-occupancy ratio from 43.64% to 27.15% and raises effective coverage of large requests from 46.11% to 63.18% without sacrificing utilization.
In briefThree-stream overlap for faster multi-GPU iterative solvers
SummaryThis paper presents a three-way overlap design for two iterative linear solvers, pipelined PCG and pipelined BiCGStab, running on multiple GPUs. It runs collective communication, irregular point-to-point communication, and compute kernels at the same time. Tests on MareNostrum 5 and Leonardo supercomputers show gains over a two-stream baseline that grow with GPU count, reaching about 1.23 to 1.33 times at 64 GPUs. Large-scale runs report up to 35% speedup for Pipe-PCG and 33% for Pipe-BiCGStab.
WhyExtends overlap to three streams, showing consistent speedups over two-stream baselines across up to 512 GPUs on real supercomputers.
Sinan Ekmek\c{c}iba\c{s}{\i}, James D. Trotter, Johannes Langguth et al.
In briefA Gaussian extremal inequality for information-constrained optimal transport, applied to rate-distortion-perception
SummaryThe paper studies how much mutual information is needed for two copies of a distribution to reach a target correlation. It proves a sharp Gaussian extremal inequality: under fixed mean and covariance, the Gaussian requires the greatest minimum information cost. The proof uses a midpoint gluing construction of Ornstein-Uhlenbeck half-bridges. Applied to rate-distortion-perception, it establishes Gaussian extremality for unlimited common randomness, and an analogous result for finite common randomness.
WhyProves a sharp Gaussian extremal inequality via midpoint gluing, extending rate-distortion-perception results with rigorous proofs and applications.
In briefMixed-precision GPU acceleration for confidence regions of spatial excursion sets
SummaryThis paper presents a GPU-accelerated framework for computing inner and outer confidence regions of spatial excursion sets, the areas where a field exceeds a threshold, under incomplete and noisy observations. It combines adaptive tile-based mixed-precision arithmetic with distributed task execution to speed up universal kriging, conditional Gaussian simulation, and confidence region calibration. With appropriate precision tolerances, empirical coverage stays close to the double-precision reference and the nominal 90% level, and ocean surface-salinity experiments agree closely with the double-precision results.
In briefEmulating double-precision matrix multiplication on Intel Arc GPUs using INT8 engines
SummaryThis paper presents the first implementation of Ozaki scheme II for Intel GPUs, written in SYCL on top of oneMKL and exposing the full dgemm/zgemm interface. The scheme turns a floating-point matrix product into a few exact INT8 products followed by Chinese-remainder reconstruction, with the number of products setting accuracy. On an Intel Arc Pro B60, emulated DGEMM reaches up to 21.1 TFLOP/s, 12 to 28 times native FP64 DGEMM on the same board.
WhyFirst port of Ozaki scheme II to Intel GPUs with Xe2-specific optimizations, showing large measured speedups over native FP64 with extensive comparisons.
In briefPlaneZip: Lossless Compression of Training Activations Sent Over PCIe
SummaryWhen GPU memory is limited during training, activations are either moved to host memory or dropped and recomputed. This paper presents PlaneZip, which compresses swapped tensors on the copy path and plans swapping around that compression. It selects the smallest of several encodings for each 128-byte block and predicts compression ratios to budget link time. Trace-driven simulations report reduced rematerialization overhead compared with planners that lack compression.
In briefConvergence of Denoising Diffusion Models Measured by Rényi Divergence, a Stronger Error Metric
SummaryThis paper analyzes how denoising diffusion probabilistic models (DDPMs) converge, using Rényi divergence, which is more sensitive than total variation, KL divergence, or Wasserstein distance to mismatches in low-probability regions. The authors show the total error splits into mixing, discretization, and score estimation errors. They also give an iteration complexity for reaching a target accuracy and extend the analysis to critically damped DDPMs.
Wenliang Liu, Santiago Mazuelas, Guanding Yu et al.
In briefTighter Approximation and Competition Bounds for Simple Auctions
SummaryThe paper studies simple auctions for one additive buyer whose values for several items are independent. For regular items, it proves that grand-bundle second-price revenue with two bidders lies between optimal revenue and twice bundling revenue, which is tight and answers an open question. For general independent items, it improves the approximation factor from 6 and 5.2 to 2.645, and raises the known lower bound from 2 to 2.11.
WhyTightens approximation and lower bounds for multi-item auctions, answering an open question with rigorous proofs.
In briefA mechanism for collective foraging: percolating recruitment cascades coupled to a maximum-entropy field
SummaryThis paper proposes a collective foraging model in which an agent that finds a resource recruits others through a linear-threshold cascade, and its movement rewires the communication network, producing a self-limiting cycle of aggregation and release. The authors report that recruitment to discoveries, marginal-value patch leaving, and Lévy search with local exploitation emerge together without tuning. Gains reach up to 7.6 times the harvest of solitary search when resources are sparse and clustered.
In briefHEL: A GPU-resident runtime layer for orchestrating heterogeneous workloads.
SummaryThis paper presents HEL, a GPU-resident runtime system built on stateful services that persist for the lifetime of a user application. Programmers express workloads as applications that spawn coroutine-like tasks, which the HEL runtime schedules and runs, supporting synchronous and asynchronous tasks, runtime dependencies, batched submission, and automatic retries. Evaluations using producer-consumer and host-RPC benchmarks and a PFPL compression case study show performance advantages for underutilized GPUs and scenarios where task latency can be hidden.
Agnieszka M. {\L}upi\'nska, Serban D. Porumbescu, John D. Owens
In briefSample complexity of weak-signal latent-variable models
SummaryThis paper studies parameter estimation in latent-variable models where a small signal-strength parameter controls how strongly observations depend on the unknown parameter. By expanding the likelihood ratio around a shared null distribution, the authors show that if the parameter first becomes globally identifiable at order r, estimation requires on the order of β^{-2r} samples. They give conditions under which maximum likelihood and method-of-moments estimators attain this rate, and apply the framework to additive-noise channels and exponential-family models.
In briefOptimal single-track Gray codes built from Gray-ordered necklaces
SummaryA single-track Gray code is a cyclic Gray code in which each column is a cyclic shift of the first. For prime length n, the longest possible period is 2^n−2, and whether this is achieved for every prime has been open since 1996. The authors show that a conjecture by Degni and Drisko (2007) on the reflected Gray code order of necklaces implies optimal codes for every prime. This implication is formalized in Lean 4, and computation gives optimal codes for all odd primes n≤47.
WhyLinks the Degni-Drisko conjecture to single-track Gray codes, addressing an open problem for primes; formalization and computation support it, impact is subfield-level.
