In briefA Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
SummaryThis paper studies position auctions in which advertisers are assigned positions and display order is set, while cascade user behavior means earlier clicks block later placements. The authors present a polynomial-time randomized mechanism that achieves a factor-6 welfare approximation and is truthful in expectation for arbitrary public click probabilities. The approach relies on a reach-weighted linear relaxation converted into feasible ordered allocations.
WhySimultaneously achieves constant-factor welfare and truthfulness for cascade position auctions via a novel decomposition and attenuation construction, a substantive theoretical advance.
In briefExtremal binary codes linked to the I-Ching hexagrams and their structure
SummaryThe paper studies binary codes compatible with the I-Ching's trigram structure, showing that a [6,3,3] code meets the doubled-trigram subspace in at most four codewords and that exactly two codes attain this bound, one being a shortened Hamming code. It defines diagonal-coherent codes and extremal ones, determining their number, minimum distances, hulls, and covering radius. The authors also propose three open problems.
In briefProof of the Langberg-Médard Conjecture on Network Coding Versus Fractional Routing
SummaryThis paper examines the capability gap between network coding and fractional routing in multiple unicast networks. The authors prove the Langberg-Médard conjecture: if coding lets every destination recover all sources' independent messages at a common rate, replacing each arc with an undirected edge of equal capacity permits fractional routing to deliver every message to its destination at that same rate. They also give a necessary and sufficient cut-capacity condition for simultaneous unit-rate fractional routing in undirected networks.
WhyResolves a long-open multi-unicast coding versus routing conjecture with complete proof and necessary-sufficient cut condition, a significant theoretical advance.
In briefFaster Log-Sum-Exp: Kernel Fusion and Integer Arithmetic for GPUs and CPUs
SummaryThis paper addresses the slow computation of the Log-Sum-Exp function, a common primitive in machine learning, on GPUs and CPUs. It proposes two drop-in kernels: FuseLSE, a single-pass fused GPU kernel using the Special Function Unit, and IntLSE, a CPU kernel using approximated integer arithmetic. Reported benchmarks show both kernels run about 10 to 11 times faster than PyTorch on small GPU workloads and about 6 times faster on larger ones, while IntLSE is about 3 to 6 times faster than FuseLSE on CPU.
In briefProof of the Langberg-Médard Multiple Unicast Conjecture
SummaryThis paper addresses the multiple unicast problem on directed networks with several senders and receivers. Under the condition that each sender-receiver pair is connected by enough arc-disjoint directed paths, the authors show that the underlying undirected network with unit capacities supports a feasible multiflow. This result proves the multiple unicast conjecture proposed by Langberg and Médard in 2009.
WhyProves the Langberg-Médard multiple unicast conjecture, resolving an open problem with a rigorous proof that matters for network coding and multiflow theory.
In briefDistributional statistics of nonequilibrium: a reference framework for random probability distributions under constraints
SummaryThe paper establishes a reference modeling framework for random probability distributions subject to constraints, generalizing Crooks' hyperensemble approach with Jaynesian priors of maximal uncertainty. It focuses on constraints on average energy and Shannon entropy, examining predictions such as mean and modal microstate distributions and the expected free energy of random distributions. The framework reduces to Boltzmann-Gibbs statistics when Shannon entropy is maximized, and is illustrated through comparisons with superstatistics, generation of random nonequilibrium steady states, and Bayesian inference.
Harrison Hartle, Aanjaneya Kumar, David H. Wolpert
In briefOS support that treats accelerators as first-class compute units in heterogeneous systems
SummaryThe paper argues that operating systems such as Linux treat hardware accelerators as peripheral devices, so software overheads reduce their benefits. The authors built MEERKAT, an FPGA-based framework, and study four sources of this overhead with techniques including virtual-memory-aware communication, a lightweight invocation interface, interrupt policy adaptation, and an accelerator-aware scheduler. Reported results include communication up to 260 times faster and 2 to 6 times better wall-clock performance than conventional schedulers.
WhyProposes accelerator-centric OS support with FPGA framework quantifying four O/S overhead sources; experiments show large communication and scheduling gains, impact mainly within heterogeneous systems
In briefSecrecy analysis and antenna placement for pinching-antenna systems against a mobile eavesdropper
SummaryThis paper studies physical-layer security in waveguide-based pinching antenna systems where a mobile eavesdropper is present. The authors analyze the ergodic secrecy rate under Gaussian and finite-alphabet signaling, assuming perfect legitimate-user location and only statistical eavesdropper information. Since the exact expression lacks a tractable closed form, they derive a closed-form upper bound via Jensen's inequality and use it to optimize antenna position. Numerical results show the bound is tight and that finite-alphabet signaling saturates at high SNR.
In briefJoint Design of Service Depth and Priority in Queues for AI Services
SummaryThis paper studies AI-assisted service systems where the server chooses both how deeply to process each job and what priority to give it. Deeper processing improves output quality but lengthens server occupancy and congestion. Using a single-server queue aimed at maximizing social welfare, the authors characterize the centralized optimum and show that, under private delay sensitivity, a price-based mechanism can leave a welfare gap relative to the centralized optimum.
In briefNemo: Faster caching and index pushdown for storage-separated OLTP databases
SummaryStorage-disaggregated databases separate compute from storage but suffer network round-trip and page-transfer bottlenecks. This paper presents Nemo, which pushes the index down to storage, caches only hot records at compute, uses a tree-structured record buffer for both caching and buffering, and caches negative search results. It also provides phantom protection that does not depend on the storage-side data layout. Experiments report up to 11.42x and 2.97x speedups over page-based B+Tree and 2-Tree on positive point queries.
In briefOptimal Voting Rules Beyond Utilitarian Welfare
SummaryThis paper studies how to judge voting rules by the social welfare of the alternatives they elect. It extends prior utilitarian results to the power mean family of welfare functions, which includes utilitarian, Nash, and egalitarian welfare. The authors show that a deterministic positional scoring rule is asymptotically optimal for expected social welfare and characterize it for a broad class of utility distributions. They also find that among randomized positional scoring rules, plurality uniquely maximizes expected welfare for all power means.
In briefLooseLeaf: Serverless GPUs for Computational Notebooks
SummaryComputational notebooks keep a GPU reserved for the whole session, even though it only computes while a cell runs. This paper presents LooseLeaf, a serverless GPU platform for interactive notebooks that derives each cell's minimal required variables and packages and prepares a GPU worker during user editing. This allows the GPU to be released after every cell. The authors report that analysis of 5,000 real notebooks shows these closures are small.
In briefTargeting Interventions to Reduce Volatility in Network Systems (Part I: Idiosyncratic Shocks)
SummaryThe paper studies how to design optimal interventions that minimize aggregate volatility in linear network equilibrium models, such as those arising in network games, production networks, and opinion dynamics. It identifies a general network centrality measure that determines how each node's shock variance amplifies system-wide volatility, reducing to Katz-Bonacich, cycle, and concentration centralities in special cases. Under a budget constraint, the authors solve analytically for the optimal shock attenuation, which has a water-filling structure that targets more nodes as the budget grows. A robust version against adversarially chosen shock variances is also solved and shows the same water-filling structure.
Luca Damonte, Leonardo Cianfanelli, Giacomo Como et al.
In briefFluctuations of relative entropy between random quantum states
SummaryThis paper derives the variances of relative entropy over Hilbert–Schmidt and Bures–Hall random state ensembles, measuring how it fluctuates around its average. Exact variance results are given for independent states drawn from the same ensemble and from two different ensembles. The results indicate that the average relative entropy is typical in the limiting regimes considered. The calculations use zonal polynomials to incorporate eigenvalue correlation functions of the ensembles.
In briefPolyhedral RIS with quantum-assisted facet selection for uniform coverage
SummaryThis paper studies a chamfered hexagonal polyhedral reconfigurable intelligent surface (RIS) designed to provide nearly uniform coverage to moving users under discrete phase control and facet mounting errors. The authors formulate each facet-selection subproblem of the max-min rate design as an exact QUBO problem and derive a closed-form bound on gain loss. In simulations, the polyhedral surface reduces dead zones in vertical planar panels from 77% to 0.3% and raises minimum rate by 34% relative to a STAR panel. Simulated annealing finds the optimum in 95% of cases, while the quantum approximation algorithm does not.
In briefLatency-Optimal Timestamp Object Implementations
SummaryTimestamp objects return strictly increasing integers and are used in distributed algorithms to order operations. This paper studies the maximum resilience and minimum latency of such implementations in asynchronous message-passing systems, with latency measured by worst-case message delay. It covers crash failures and Byzantine failures with and without digital signatures. The authors give lower bounds and algorithms establishing optimal resilience for each failure type and optimal latency in all cases but one, and introduce a new lower-bound technique called a cyclic chain argument.
WhyIntroduces a new cyclic chain lower-bound technique and settles optimal resilience and latency for timestamp objects under several failure models.
In briefLogarithmic Separation Between LZ77 and LZ-End, and Grammar Compression
SummaryThis paper proves a logarithmic separation between LZ77 and LZ-End. It also shows a logarithmic separation between LZ77 and grammar compression. These results establish that the compression efficiency of these methods differs by a logarithmic factor.
Philip Bille, Inge Li G{\o}rtz, Rikke Jessen et al.
In briefBeam search decoding for error-correcting codes using conditional diffusion
SummaryThis paper proposes a diffusion framework for neural decoding of error-correcting codes, treating decoding as a conditional process that predicts codeword bits given the channel observation. For masked diffusion, the authors introduce Maxwell beam search, which keeps multiple candidate trajectories, removes parity-infeasible ones, and ranks the rest by accumulated log-probabilities. Tested on BPSK over AWGN with Polar, LDPC, and BCH codes, the method reportedly outperforms a single-trajectory diffusion decoder and existing neural decoding results in all evaluated settings.
In briefAdjusting Hospital Capacities to Restore Stable Matching with Couples
SummaryThis paper studies how to adjust hospital capacities and find a stable matching at the same time in the Hospitals/Residents problem with couples, where each couple is either fully matched or not matched at all. The authors develop Exact and Cutoff integer programming formulations. They prove that for arbitrary strict preferences, changing each hospital capacity by at most two guarantees a stable matching, and that this bound is tight. Computational tests on 96,000 synthetic and reconstructed markets show that small capacity changes restore existence when no stable matching exists originally.
In briefAFRA: Age-threshold frame-based random access protocol for timely communication among multiple agents
SummaryThis paper proposes AFRA, a distributed medium access protocol that helps multi-agent systems sharing a wireless channel keep information fresh. When an agent's information age reaches a threshold, it starts a local frame with a mandatory transmission and makes one further random attempt if that fails. The authors prove that, under stated conditions on frame length and threshold, operation converges almost surely to collision-free periodic behavior, and they derive closed-form expressions for throughput, average AoI, and average peak AoI. Simulations indicate fast convergence at small thresholds and lower window-averaged AoI than the other age-aware schemes evaluated.
In briefPolarization on bounded Euclidean spaces and general compact groups: proves polarization for memoryless sources over circles and compact groups.
SummaryThe paper establishes polarization for memoryless sources taking values on the unit-perimeter circle or more general compact groups under Arıkan's polar transform. For sources with finite differential entropy, all but an O((log N)^(-1/12)) fraction of conditional differential entropies in successive cancellation order lie within any fixed positive distance of zero, where N is the block length. Examples indicate the true polarization rate is very slow.
Sharang M. Sriramu, Lampros Gavalakis, Ioannis Kontoyiannis et al.
