In briefNear-MMS fair allocations when few extra agents are present
SummaryThe paper studies fair allocation of indivisible goods, asking whether a subset of n agents among more agents can each receive at least a fixed fraction of their n-maximin share (MMS). The authors show that when agent redundancy is positive, this fraction approaches 1 as n grows. This also holds without redundancy when the number of goods is at most (2−c)n. Adapting their techniques, they improve a result of Ezra and Garbuz, showing that without redundancy, n−O(log²n) agents can always receive their full MMS.
WhyThe authors show that with agent redundancy the MMS fraction tends to 1 as n grows, yielding a corollary for m≤(2-c)n and improving Ezra and Garbuz's result.
In briefPlotkin-optimal pure quantum LRCs with large minimum distances from NMDS codes
SummaryThis paper presents a general framework for building optimal pure quantum locally recoverable codes (qLRCs) that reach a Plotkin-like bound, using Hermitian dual-containing near maximum-distance separable (NMDS) codes. It focuses on extended subcodes of generalized Reed-Solomon (ESGRS) codes, determining their localities by analyzing subset sum problems over finite fields. Using the algebraic structure of these codes, the authors construct four families of such qLRCs with large lengths and more flexible minimum distances than existing constructions.
SummaryThis paper studies the distortion framework in social choice theory, which measures the efficiency of randomized selection of an alternative based on agents' preferences. The authors present a linear-programming algorithm that computes the optimal randomized decision for a given instance, which is simpler and faster than prior methods. They also give a non-convex quadratic programming algorithm to compute the exact distortion of any randomized positional scoring rule.
Soroush Ebadian, Aris Filos-Ratsikas, Mohamad Latifian et al.
In briefFast Equilibrium Computation for the Colonel Blotto Game
SummaryThe paper studies Colonel Blotto, a resource-allocation game where two players split budgets across battlefields and the higher allocation wins each battlefield's value. It gives a fully polynomial-time approximation scheme that computes an epsilon-Nash equilibrium in time polynomial in the input length and 1/epsilon. For sufficiently balanced budgets and battlefield values, it also computes exact equilibria in linear time.
WhyThe authors report a fully polynomial-time approximation scheme for equilibria in Colonel Blotto games, plus linear-time exact equilibria for balanced cases.
In briefParallel Python implementation of sparse nonlinear dynamics identification (SINDy) using Numba, OpenMP, threads and multiprocessing, tested on Lorenz and Rössler systems
SummaryThis paper presents an open-source Python implementation of SINDy, a method that recovers interpretable governing equations from time-series data by sparse regression. The same loop-based kernels are compiled with Numba and run on a shared-memory multicore node through four interchangeable back ends: Numba prange, OpenMP via PyOMP, Python threads, and multiprocessing with shared memory. On the Lorenz and Rössler systems, all back ends recover the exact sparsity pattern, reach 14.8 to 20.3 speed-up on 24 cores, and cut total time to solution by up to 117 times relative to PySINDy.
In briefWhat Limits Serving Speed in Looped Language Models: Measurements and Optimizations Ranked by Exactness
SummaryThe paper measures how fast two looped language models, Ouro and Huginn-0125, can be served in an open-source inference engine. Because these models reuse the same block of layers many times per token, per-layer overhead is paid on every loop. The authors rank their optimizations from bitwise-identical changes to those requiring an accuracy check, and report throughput gains alongside effects on GSM8K accuracy.
In briefTight Bound for Randomized Truthful Scheduling
SummaryThe paper studies randomized truthful mechanisms for minimizing makespan on unrelated machines. It proves a lower bound of (m+1)/2 on the approximation ratio for truthful-in-expectation mechanisms, determining the optimal ratio as m/2 plus a constant. It also raises the leading constant of the lower bound for universally truthful mechanisms from 3/2−√2 to 1/2, which together with a known upper bound settles that ratio up to lower-order terms.
WhyThe authors prove a (m+1)/2 lower bound for randomized truthful makespan scheduling, improving the leading constant from about 0.0858 to 1/2.
In briefTight limits for fair-in-expectation job scheduling on machines
SummaryThe paper studies randomized mechanisms that schedule indivisible jobs on n unrelated machines, where each selfish machine owner privately knows its job processing times. The mechanisms are truthful in expectation and aim to minimize the expected makespan. For n of at least 7, the authors prove the optimal approximation ratio is (n+1)/2, and they give a matching mechanism. For two machines the optimal ratio is about 1.505995705434, and for three machines it is 2.
WhyThe authors report a matching lower and upper bound of (n+1)/2 for n≥7 and exact constants for two and three machines, for truthful-in-expectation scheduling.
In briefA study of numerical bugs in GPU programs and automated detection
SummaryThis paper analyzes 397 real-world numerical bug samples from GitHub in GPU programs, identifying their root causes, symptoms, triggering input patterns, test oracles, and fixing strategies. The authors also present GPU-NBDetect, a preliminary tool that detects numerical bugs across six bug categories. It found 226 bugs in 186 mathematical functions across four libraries, and developers confirmed 60 of them.
Ravishka Rathnasuriya, Nidhi Majoju, Zihe Song et al.
In briefComputer-aided design and checking of cheat-proof facility placement on distance networks
SummaryThis paper studies how to automatically design randomized facility location mechanisms on continuous metric graphs that are strategyproof, with the goal of minimizing total distance. The authors develop methods for computing upper and lower bounds on the best approximation ratio achievable by such mechanisms, and introduce finite representations called piecewise-linear attributions. Certified upper and lower bounds are computed on several metric graphs.
In briefAnalysis of Serverless Workloads Across Function-as-a-Service Platforms
SummaryThis paper compares eight publicly available Function-as-a-Service workload traces from major cloud providers and a scientific computing platform. It characterizes invocation patterns, latency, cold start behavior, and resource utilization. The authors report that execution times have shortened, shifting bottlenecks toward platform scheduling and dependency management, and that concurrent long-lived containers are increasingly used. They also find resource over-provisioning and highly skewed user request volumes.
Saman Akbari, Yassine Lazreg, Mohammadreza Malekabbasi et al.
In briefConstant-factor fair-share guarantees for subadditive valuations
SummaryThe paper studies maximin share (MMS), a fairness measure for dividing indivisible goods among n agents. For general subadditive valuations, it improves the known guarantee from Ω(1/log log n) to Ω(1/log* n). It also introduces q-partitioning valuations, an intermediate class between subadditive and XOS, and proves constant guarantees when q/n has a positive lower bound. For XOS valuations, the universal guarantee rises from about 0.2353 to 0.3125.
WhyThe authors improve the general subadditive MMS guarantee exponentially to Ω(1/log* n) and report constant guarantees for intermediate q-partitioning valuation classes.
In briefRank-metric intersecting codes: extending intersecting codes to the matrix rank metric
SummaryIntersecting codes are codes in which any two nonzero codewords share a common nonzero coordinate. This paper extends the notion to the matrix rank-metric setting, defining the support of a matrix as its row space. Using the slice space of the generator tensor, the authors give a geometric characterization equivalent to the intersecting property, which yields parameter bounds, one of them sharp, along with first constructions. For codes closed under multiplication, i.e. matrix algebras, the intersecting property can be read from the Jacobson radical and the socle, enabling flexible construction of many such codes.
In briefShort proof and generalization of the rainbow cycle theorem, with improved bounds for binary even-query LCCs
SummaryThe paper studies rainbow cycles, which are cycles in which no color appears more than once. It gives a short proof of an earlier result showing that a properly edge-colored graph with sufficiently large average degree always contains a rainbow cycle, and extends this to weighted graphs with list-colored edges. Using this generalization, the authors prove an upper bound on the dimension of binary linear even-query locally correctable codes, closing the gap with the best known lower bounds for odd-query codes.
