Proof of the Langberg-Médard Conjecture on Network Coding Versus Fractional Routing
WhyResolves a long-open multi-unicast coding versus routing conjecture with complete proof and necessary-sufficient cut condition, a significant theoretical advance.
Best achievable error for locating closely spaced point sources
WhyProves matching Bayes risk bounds for closely spaced source localization across separation and noise regimes, distinguishing odd and even source counts; impact largely confined to signal processing.
Pareto-optimal Scheduling with Predictions: a paper on single-machine job scheduling that balances trust in predictions against worst-case performance.
WhyExactly characterizes the optimal consistency-robustness tradeoff for deterministic algorithms with matching bounds, substantially improving prior Θ(1/ε) robustness with complete proofs.
Fundamental limits of bistatic ISAC over vector channels, i.e., the best achievable trade-off between communication rate and sensing accuracy.
WhyGives an exact single-letter capacity-distortion characterization for bistatic ISAC over vector channels, proving Gaussian superposition coding optimal via a Fisher-information matrix inequality.
Proof of the Golomb–Welch conjecture for lattice tilings
WhyResolves the long-open Golomb-Welch conjecture with a complete proof, fully settling existence of lattice Lee tilings, a significant advance for the subfield.
Proof of the Langberg-Médard Multiple Unicast Conjecture
WhyProves the Langberg-Médard multiple unicast conjecture, resolving an open problem with a rigorous proof that matters for network coding and multiflow theory.
Stars are a rough AI assessment based on the title and abstract: each paper is scored for novelty, strength of evidence and breadth of impact, then mapped to 1–5 stars (about 2% get five stars and 10% get four). The site only marks four- and five-star papers as Notable, with a one-line reason; no mark does not mean a paper is weak. The full text is not read, so treat the stars as a reading aid, not a verdict on quality. "Code" means the abstract states that code, data or tools are released.
In briefAdapting hybrid LLM inference to each request for greater efficiency
SummaryThis paper presents Morph, a serving system that co-designs model architecture and runtime so hybrid language models can choose their layer layout per request. Each block pairs Attention and state space model layers, and a prefill-stage gate selects a layout that stays fixed during decoding. Experiments on six datasets report a better quality-efficiency trade-off than static hybrid baselines, with serving throughput improved by up to 3.87x and substantially lower inference latency.
In briefPrivacy-preserving over-the-air federated learning in cell-free massive MIMO with user-centric clustering
SummaryThis paper studies a cross-layer design for differentially private federated learning over cell-free massive MIMO networks, where user model updates are aggregated over the air. It shows that thermal noise in wireless reception can help mask private information, reducing or removing the need for artificial noise. The authors jointly optimize access point-user associations, transmit powers, and artificial noise variances to minimize aggregation variance under per-user privacy constraints. Simulations report up to 89% lower aggregation variance than baselines and 97% test accuracy on MNIST, with consistent gains on CIFAR-10.
In briefCapacity of private information retrieval from coded storage with colluding, robust and Byzantine servers
SummaryThis paper studies private information retrieval from MDS-coded databases that include T colluding servers, U robust servers, and B Byzantine servers. The authors characterize the capacity for linear, full support-rank schemes and show the same expression holds without those restrictions when K=1 or T=1. They also extend the construction to retrieving P out of M files, and report that for P≥M/2 with K=1 or T=1 the multi-file scheme achieves capacity.
In briefUniqueness of codes for 4-cell connected disjoint clusters in the spatial chromatic model
SummaryThis paper studies the coding of the spatial chromatic model (SCM), an entity-oriented spatial data model in which each cell has a chromatic code. Earlier work had shown uniqueness for 2-cell and 3-cell connected disjoint clusters. Building on that, the authors prove that the chromatic codes of 4-cell connected disjoint clusters are unique.
In briefTAO: Tool-Aware Joint Scheduling for LLM Agent Serving
SummaryThis paper presents TAO, a scheduling framework for serving LLM-based agents that alternate between GPU model inference and external tools running on CPUs. TAO's value function combines near-term tool readiness, node-specific cache credit with time-aware decay, and token footprint, and a dynamic program jointly selects and places waiting sessions under capacity limits. Across 12 reported model-workload-concurrency settings, TAO reduces latency by up to 26.8%, mean time to first token by up to 36.3%, and increases decode throughput by up to 29.5% relative to the best evaluated baseline for each metric.
In briefPipeLink: Contract-Guided Linking of GPU Kernel Components
SummaryThis paper presents PipeLink, a linker that combines separately compiled GPU kernel components using contracts stating what each component requires and provides. PipeLink checks these contracts, solves a joint placement of streaming multiprocessor resources, and generates the transfers between components. Across 51 configurations on Hopper and Blackwell GPUs, linked kernels run within 0.2% of the same sources compiled as one unit.
WhyProposes a contract-guided linker for GPU kernel components; validated across 51 configurations within 0.2% of monolithic builds, with practical composition speedups.
In briefNegative Results for Over-the-Air Split Learning Under Channel Aging
SummaryThis paper studies reciprocity-based over-the-air split learning, where channel aging rotates and attenuates the derivative signal sent back to the transmitter. Seven case studies combine numerical forecasts, mechanism checks, and competing predictions. Most predicted training accuracy gains are not supported, while some local physical relations, such as the inverse relation between amplitude and phase gradient, hold.
In briefDeep Holes and Aperture: Sign Laws for Lattice-Sampled Random Waves
SummaryThis paper studies whether the empirical lag correlation of a Gaussian random wave field, sampled on a lattice within a bounded aperture, keeps a positive real part throughout the Voronoi cell. It identifies deep holes as the minimizers that govern failure and gives explicit sign-class counts for square, hexagonal, simple cubic, and body-centered cubic lattices. The authors also derive asymptotic and non-asymptotic aperture laws and state when a failure floor appears under Rayleigh-faded specular paths.
In briefCounting the fixed points of binary belief propagation: generic degree, syzygies, and real solutions
SummaryThe paper studies how many fixed points belief propagation has on a binary pairwise model. Over complex parameters, it determines the generic degree of the algebraic family arising from finite loopless multigraphs, expressed as a graph state sum over edge sets without degree-one vertices. Two geometric realizations of this state sum are given, and at strong external fields the real fixed point count is analyzed as a lower bound. The degree, resolution, and real-count results are formalized in Lean 4.
In briefWireless localization using digital twins and probabilistic inverse learning
SummaryThis paper studies how site-specific digital twins can support wireless localization with simplified distributed infrastructure. It proposes PRISM, a probabilistic scheme using single-antenna access points, which learns a proposal distribution over user locations from channel impulse responses and reweights candidates using digital twin consistency. With 10 single-antenna access points, it reports a median error of about 0.7 m and remains effective without retraining when digital twin features are degraded.
Mahmoud Saad Abouamer, Henrik C. M. Frederiksen, Robin J. Williams et al.
In briefContention-aware scheduling to handle skewed sparse matrix multiplication (technical report)
SummaryThis report examines why sparse matrix-matrix multiplication (SpGEMM) slows down on skewed real-world workloads. It identifies two causes: imbalance across computation cost, output density, and data locality, and cache contention from dense substructures. The authors propose adaptive morsel scheduling (AMS), which combines contention-aware load balancing, a data-conscious SMT activator, and a per-morsel hybrid accumulator. Evaluations on matrix squaring, relational queries, and graph analytics report that AMS significantly outperforms existing methods on skewed workloads while staying comparable on non-skewed ones.
In briefPhysics-informed neural operator for channel estimation in fluid antenna systems
SummaryThis paper frames channel estimation for fluid antenna systems as a stochastic inverse field-reconstruction problem constrained by the projected Helmholtz model. It shows that finite-aperture reconstruction leads to a frequency-domain deconvolution problem and proposes a U-shaped Fourier neural operator trained with a physics-aware Sobolev loss. Simulations report higher accuracy than state-of-the-art benchmarks and much lower inference latency than iterative solvers at high spatial-frequency resolutions.
In briefHow the power delay profile threshold affects RMS delay spread estimates at 33 GHz
SummaryThis paper examines how estimates of RMS delay spread, a measure of signal time dispersion in radio channels, change with the relative power threshold applied to power delay profiles. The analysis uses wideband measurements at 33 GHz in a dynamic road environment with moving vehicles. Lowering the threshold from -20 dB to -50 dB raises the median from about 140 ns to 168 ns and the 90th percentile from 200 ns to 210 ns. Both statistics converge at lower thresholds, with -40 dB a practical convergence level.
Jaros{\l}aw Wojtu\'n, Bartosz Czaja, Tomasz Grasza et al.
In briefWhen Do Token Systems Stabilize? Compatibility Constraints and Community Structure
SummaryThis paper studies token systems that enable service exchange without money, where agents face compatibility constraints. It establishes a necessary and sufficient condition for stability and shows that a minimum-token rule, selecting the lowest-balance available provider, achieves the optimal stability region. The criterion is applied to random token systems generated by stochastic block models, identifying two obstructions to stability: insufficient service opportunities for a group of communities or for an individual agent.
In briefFinite Fields: root sets, Frobenius maps and algebraic structure (monograph)
SummaryThis monograph develops finite field theory through root sets, Frobenius orbits, trace duality and cyclic modules. It applies these tools to polynomial constructions and algebraic coding theory, covering cyclic and constacyclic codes, BCH and Goppa bounds, rank-metric and trace codes. It also treats character sums, Gauss and Jacobi sums, and proofs of Weil bounds, emphasizing explicit links between field, orbit and linear-dependence structure.
In briefCharacterizing Maximum Nash Welfare: Envy-Freeness and Proportionality
SummaryThis paper studies how to allocate indivisible goods using the maximum Nash welfare rule. This rule was already known to be the only welfarist rule satisfying envy-freeness up to one good. The authors show that this fairness requirement can be replaced by much weaker conditions for any fixed k: envy-freeness up to k goods, or proportionality up to k goods. The characterization also holds for preference profiles with identical goods.
Karen Frilya Celine, Warut Suksompong, Nicholas Teh
In briefExact weight spectrum of RM(m-7,m): a counterexample to the Carlet-Solé conjecture
SummaryThis paper studies the weight spectrum of the Reed-Muller code RM(m-7,m), which describes which weights occur among Boolean functions of degree at most m-7. Combining affine geometry and Fourier analysis, the authors exclude eight weights previously conjectured for RM(7,14). They extend these exclusions to all m≥14 and thereby provide a counterexample to the Carlet-Solé conjecture.
In briefA new MIMO design using movable antennas that keeps signal paths strong
SummaryThis paper examines how distance differences between users and a base station can cause multi-user MIMO channels to lose spatial degrees of freedom. It proposes generalized pinching antennas placed close to users, which make the channel Gram matrix nearly diagonal and well-conditioned. Performance is assessed using rank-deficiency and outage probabilities. The analytical and simulation results indicate that pinching antennas can preserve spatial degrees of freedom and support users at spatially separated locations.
In briefAgar: What-If Analysis for Microservice Applications
SummaryThis paper presents AGAR, a counterfactual performance analysis tool for microservice applications. Instead of predicting exact values for each component, it learns simple, interpretable bounds that contain all observed behaviors and are tight enough to support end-to-end conclusions, then composes them to answer SLO-feasibility questions. This framing turns autoscaling into the query of finding the smallest resource allocation that meets an SLO. Across three microservice applications, the derived autoscaler reduces CPU allocation by up to 36.8% compared with state-of-the-art horizontal autoscalers while satisfying application SLOs.
Saarth Deshpande, Neeraja J. Yadwadkar, Venkat Arun
In briefNoise Shapes the Surplus: Strategic Play Against No-Regret Learners
SummaryThis paper studies how an optimizer in zero-sum games can gain cumulative payoff above the minimax benchmark against no-regret learners, here Follow-the-Regularized-Leader algorithms, that act on noisy payoff scores with decaying learning rates. Passive play earns at most constant surplus, while a clairvoyant optimizer secures surplus scaling with the inverse learning rate when the mean response is profitable. Active alternating play can still extract surplus from the learner's movement when it is not, and at the canonical rate the noiseless Ω(√T) surplus is recovered under mean-zero, finite-variance perturbations.
WhyProposes new exploitation mechanisms against noisy FTRL learners, proving sqrt(T) surplus under decaying rates; strong theory, but scope is limited to zero-sum games.
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis
In briefOptimal and Impossible Strategyproof Facility Placement in Multiple Dimensions
SummaryThis paper studies facility location in multidimensional normed spaces, aiming to minimize social cost, the sum of agents' distances to their nearest facility. For a single facility in the Euclidean plane, it shows that the optimal approximation ratios of deterministic strategyproof mechanisms match those of the coordinate-wise median, without assuming anonymity. It also shows that the coordinate-wise median is not always optimal in non-Euclidean spaces, and proves impossibility results for two or more facilities.
In briefLearning-Augmented Coordination Mechanisms: Using Demand Predictions to Improve Equilibrium Efficiency in Congestion Games
SummaryThis paper studies how selfish behavior reduces efficiency in decentralized resource allocation. It proposes learning-augmented coordination mechanisms that use a possibly inaccurate demand prediction to modify resource costs, with a confidence parameter β that yields near-optimal performance when predictions are accurate while keeping a good worst-case equilibrium guarantee. The paper also gives robustness bounds and impossibility results, including limits on error tolerance in non-atomic games.
WhyIntroduces learning-augmented coordination mechanisms for congestion games, achieving near-optimal consistency and PoS guarantees with matching impossibility results.
George Christodoulou, Vasilis Christoforidis, Alkmini Sgouritsa et al.
In briefJustGoal: An AI Given Only a Goal Beats Expert-Written GPU Kernels
SummaryThe paper introduces JustGoal, a baseline in which a general-purpose AI agent receives only an optimization goal and constraints, without kernel-specific knowledge bases or predefined workflows. On NVIDIA B200 GPUs, it beats open-source libraries on 8 of 10 operators, with per-operator geometric mean speedups of 1.14x to 2.34x, and beats the fastest public specialized-agent kernel on 5 of 9 comparable operators. The authors conclude that specialized machinery should be justified by clear gains over a same-model, goal-only baseline and reevaluated when the foundation model changes.
In briefFundamental limits of bistatic ISAC over vector channels, i.e., the best achievable trade-off between communication rate and sensing accuracy.
SummaryThis paper studies the fundamental performance limits of bistatic integrated sensing and communication systems over vector channels. For parallel channels with a degradation structure, the authors establish matching achievability and converse results, giving a single-letter characterization of the capacity-distortion function. For vector Gaussian channels with additive Gaussian states, they prove that Gaussian superposition coding is optimal, yielding an exact characterization of the capacity-distortion-power function.
WhyGives an exact single-letter capacity-distortion characterization for bistatic ISAC over vector channels, proving Gaussian superposition coding optimal via a Fisher-information matrix inequality.
In briefThermodynamic Characterization of Message-Passing Decoders: Framework and Initial Study
SummaryThis paper studies the thermodynamic efficiency of message-passing decoders using the mismatch cost framework, which provides a computable lower bound on irrecoverable energy loss. Using the [7,4] Hamming code over a binary erasure channel, it shows how channel-induced initialization statistics and the step-wise evolution of the algorithmic state distribution determine the total mismatch cost. The results indicate that thermodynamic cost depends jointly on decoding dynamics, input statistics, and hardware characteristics, suggesting paths toward energy-efficient decoder design.
In briefINC-MoE: Overlapping In-Network Collectives with Expert Computation for Faster MoE Inference
SummaryThe paper presents INC-MoE, an expert-parallel mixture-of-experts layer that offloads token dispatch and output combining to the network switch and overlaps these collective operations with each other and with expert computation. In an emulated four-node deployment with a dedicated in-network computing switch, it was evaluated on OLMoE prefill with four-way expert parallelism. Relative to vLLM's default collective path, it reduces time to first token by up to 33% and raises throughput by up to 50% while matching outputs.
In briefHow learning algorithms pick equilibria and can lead to collusion
SummaryThis paper studies how the design of learning algorithms affects which equilibrium players settle on in infinite-horizon discounted Markov games. It shows that stochastically stable states correspond to approximate stationary Nash equilibria that maximize the minimum transformed discounted value across players. In repeated Cournot games, every stochastically stable state yields an approximate public perfect equilibrium with minimum discounted profit above the Cournot-Nash benchmark, so collusion is inevitable under these conditions and learning dynamics.
WhyCharacterizes equilibrium selection via stochastic stability and proves learning dynamics inevitably yield approximate collusion in repeated Cournot games, impacting algorithmic collusion research.
In briefComputational Hardness of Outplaying No-Regret Learners: Easy With Pure Play, Hard Even With Mixed Play
SummaryThe paper studies how hard it is to optimize a strategy against a known online learner in repeated finite-horizon games. For general-sum games with bounded payoffs, unless P=NP, no polynomial-time optimizer can come within a constant factor cT of the best pure-action sequence, even when mixed strategies are allowed. In zero-sum games, deterministic pure actions efficiently recover surplus guarantees previously obtained only through mixed play against FTRL learners.
WhyExtends known hardness to broader mean-based learners and shows pure strategies match mixed surplus guarantees in zero-sum games.
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis
In briefExplicit Reed-Solomon codes with optimal list and line decoding
SummaryThe paper constructs explicit Reed-Solomon codes over extension fields that can be list-decoded from a fraction 1-R-ε of errors with optimal list size O((1-R)/ε). A simpler strongly explicit evaluation-point construction achieves list size (1/ε)^O(1/ε). Both constructions admit deterministic list-decoding algorithms running in polynomial time.
WhyGives explicit Reed-Solomon codes with near-optimal constant list size via subspace designs, with rigorous proofs and new line-decoding reduction.
Omar Alrabiah, Rohan Goyal, and Venkatesan Guruswami
In briefMapping the Computability Limits of Hylland-Zeckhauser Market Models
SummaryThis paper studies how hard it is to compute equilibria in the Hylland-Zeckhauser one-sided matching mechanism. It shows that allowing three utility values over {0,a,1} already makes approximate equilibrium computation PPAD-hard, while two values were known to be tractable. For separable concave utilities, two shared marginal slopes admit a polynomial-time exact algorithm, whereas three slopes lead to PPAD-hardness.
WhyResolves an open question by proving three utility values already yield PPAD-hardness, with a rigorous tractability threshold characterization.
Ioannis Panageas, Avi Shein, Shayan Taherijam et al.
In briefWorld Model for Energy-Efficient Beamforming in Dynamic Metasurface Antennas
SummaryThis paper addresses jointly optimizing digital beamforming and dynamic metasurface antenna (DMA) element weights under time-varying channels to maximize time-averaged energy efficiency, subject to power, phase, and minimum rate constraints. The authors propose a world model framework that learns latent system dynamics from environment interactions and optimizes both variables through imagined trajectories, with feasibility-preserving action mappings and safety cost signals. Simulations show about a 20% improvement in time-averaged energy efficiency over a deep Q-network baseline, with higher sample efficiency and more reliable constraint satisfaction.
Abdolrasoul Sakhaei Gharagezlou, Mehdi Monemi, Matti Latva-aho et al.
In briefMaking the telemetry pipeline measurable: an edge IoT testbed and dataset for latency, provenance, and energy
SummaryThis paper presents a measurement-first edge IoT testbed and dataset that treat timeliness, provenance, and energy as core telemetry dimensions. The system uses a role-based event-driven architecture, Avro-encoded telemetry messages, and a Mosquitto MQTT broker plugin that records ingress and egress timestamps. The dataset is released as replayable raw Avro streams and analysis-ready Parquet tables. The paper demonstrates one deployment through latency, measurement-context, and energy summaries, but does not introduce a new attribution method or a controlled performance benchmark.
In briefA unified queueing model for comparing serverless autoscaling under bursty workloads
SummaryThis paper compares three serverless autoscaling strategies: scale-per-request, concurrency-level scaling, and metric-based scaling, under bursty workloads. The authors combine analytical queueing network models with queueing Petri nets built in Java Modeling Tools, using two-phase hyper-exponential arrivals. They evaluate throughput, mean response time, system population, and system power. The study finds that scale-per-request has the lowest delay at moderate load but is fragile near capacity, concurrency-level scaling is sensitive to configuration, and metric-based scaling gives the most stable QoS across the workload range.
In briefFormation of environmental agreements and payoff sharing among countries.
SummaryThe paper addresses how countries must bear costly emission reductions for climate change, yet each prefers others to act while benefiting from a cleaner environment. It notes that game theory suits designing international environmental agreements, and that prior work treats coalition formation noncooperatively while cooperative games are used to share climate costs. Both approaches are described as having advantages and drawbacks.
Michel Grabisch, Elena Parilina, Agnieszka Rusinowska et al.
In briefMovable-antenna anti-jamming: provably locally optimal design and a unified antenna-position optimization framework
SummaryThis paper studies how movable antennas (MAs) can improve anti-jamming in wireless receivers by jointly optimizing antenna positions and the receive beamformer to maximize output SINR. For a single jammer and single line-of-sight path, it proposes a damped projected-gradient descent (DPGD) algorithm whose complexity scales linearly with the number of antennas and proves it converges almost surely to a local minimizer. For general cases with multipath or multiple jammers, it proposes a soft-active projected-gradient (SAPG) algorithm, also linear in complexity, applicable to MVDR and ZF reception. Numerical results show gains in anti-jamming performance and computational efficiency.
In briefA short note on how numerical error bounds change with hardware resources
SummaryThis short technical note explains how to bound numerical errors relative to computational resources. It combines known complexity estimates for parallelizable algorithms with parallelization laws. The authors suggest the approach generalizes beyond their examples and can fairly compare algorithms, hardware, and software by giving each configuration the same resource or energy budget.
In briefA unified framework for product assortment optimization and matching under multinomial logit customer choice
SummaryThe paper develops a unified framework for assortment optimization and matching when customers choose according to the multinomial logit (MNL) model. It centers on a single-customer problem where the firm commits to eligible products before their availability is revealed. A simple threshold policy achieves a tight 1/2 guarantee against a benchmark and accommodates cardinality constraints. Applied to several problems, the framework yields 1/2 guarantees and a 1/4 guarantee for fully static two-sided assortment optimization.
WhyProposes a unified framework with tight 1/2 guarantees improving several applications' approximation factors, mainly theoretical in impact.
In briefConverse of symplectic interlacing via low-rank singular value perturbations
SummaryThe paper proves the converse of the symplectic interlacing theorem. Given a global symplectic spectrum and a local symplectic spectrum satisfying the 2k-step interlacing inequalities, it constructs a real symmetric positive definite matrix with these prescribed spectra, where the local spectrum belongs to a principal submatrix. The main tool reduces s-principal compression to a rank-k singular value perturbation. In the Gaussian quantum marginal problem, the symplectic interlacing inequalities are shown to be the complete spectral compatibility conditions for the global-versus-local-mode marginal problem.
WhyProves the converse of the symplectic interlacing theorem with a complete characterization via low-rank singular value perturbations, a notable theoretical advance.
Priyanka Grover, Hemant K. Mishra, Sarishti Singh et al.
In briefMinimality of binary codes built from Hamming weight layers and graph cut spaces
SummaryThis paper studies the minimality of binary linear codes, which matter for secret-sharing schemes. It examines three known constructions: codes from a single complete Hamming-weight layer, codes from unions of such layers, and graph cut-space codes. For single-layer codes it gives a complete classification, showing they are minimal exactly when t is even. For unions of layers it gives an if-and-only-if minimality criterion, and for graph cut-space codes it translates minimality into a graph-theoretic condition.
In briefFurther Study of p-Ary Self-Orthogonal Codes from Square Functions
SummaryThis paper studies a family of trace codes over finite fields of odd characteristic, defined by two quadratic trace conditions. By analyzing the associated quadratic forms and evaluating character sums, it determines the codes' parameters and complete weight distributions. It also builds punctured codes using the multiplicative orbit structure of the defining sets and establishes self-orthogonality criteria, covering divisibility and projectivity.
In briefWho Pays for Hidden Reasoning? Billing Model Cloud Tokens
SummaryThis paper studies how charging for hidden internal reasoning and candidate answers in token-priced language model services affects provider decisions and social welfare. It builds a three-party model of users, a model firm, and an execution cloud, examining who controls the computation budget. A LiveCodeBench study compares answer quality, latency, token use, and resource consumption across five model deployments. It finds metered pricing yields higher welfare when the extra inference creates net social value, while fixed pricing is preferable when its costs outweigh benefits.
In briefBROCADE: A broker-based contract design for multi-agency welfare maximization.
SummaryThis paper studies welfare maximization in a contract model with m principals who privately value a public project's success and n agents whose effort is unobservable. It introduces three tools: a broker that separates principal payments from agent payments, an extension of Myerson's Lemma for dominant-strategy incentive compatibility (DSIC), and a black-box reduction to budget-constrained single-principal contract design. The authors give approximation results for deterministic and randomized contracts under different benchmarks, including a universally DSIC and budget-balanced randomized contract with an O(log m) approximation ratio independent of n.
In briefSharp limits on graph codes avoiding complete bipartite differences
SummaryThe paper studies how large a fraction of all graphs on n vertices can be chosen so that no two chosen graphs differ by exactly a complete bipartite graph K_{s,t}. For every pair s,t the authors determine this maximum density. When both parts are odd it is 1/2; otherwise, with 2h the largest even part size, the density is Θ(n^{-h}). The upper bound uses the Frankl–Füredi forbidden-intersection theorem, and the lower bound uses BCH-based binary linear codes.
WhyDetermines the exact order Θ(n^{-h}) for all fixed s,t, improving Alon's O(1/n) bound via Frankl–Füredi upper bound and BCH-code lower bound.
In briefA revisit of entropy and related measures for symbolic sequences and how to estimate them
SummaryThis paper revisits entropy, entropy density, effective measure complexity, and informational distance for analysing sequential data, grounding them in information theory and ergodic theory. A central result, Ziv's theorem, shows that the normalised number of distinct words is asymptotically equivalent to entropy density, supporting estimation via Lempel-Ziv factorisation. The authors introduce estimation procedures for finite sequences and an open-source parallel software library. Three case studies illustrate use: functional brain connectivity from fMRI, coupled nonlinear oscillators, and ECG-based atrial fibrillation classification.
Efren Aragon-Perez, Ania Mesa-Rodriguez, Karel Garcia-Medina et al.
In briefNew additive non-RS MDS and ACD codes from twisted Reed-Solomon codes
SummaryThis paper studies single-twist additive generalized twisted Reed-Solomon (GTRS) codes over finite fields. It gives necessary and sufficient conditions for these codes to be MDS for arbitrary hook and twist parameters. Using Schur squares, the authors show such additive MDS codes are not monomially equivalent to additive Reed-Solomon codes. They also identify a class of additive GTRS codes whose duals are again additive GTRS codes, which yield ACD codes for sufficiently large prime powers with characteristic avoiding a finite set.
In briefA priority-aware scheduler that reduces cold starts and balances load for serverless functions
SummaryThis paper presents SPES-Ext, a rule-based, priority-aware scheduler for memory-constrained distributed worker nodes running serverless functions. It categorizes functions by their invocation patterns and combines predictive function provisioning, eviction optimization, and dynamic load balancing. According to the authors' experiments, it cuts 75th-percentile cold starts by 80%, reduces memory waste by 83.92%, and improves worker load variance by 52.49% over state-of-the-art solutions.
In briefWhether Follow the Regularized Leader fails to converge in constrained optimization
SummaryThe paper studies whether Follow the Regularized Leader (FTRL), a basic online learning algorithm, converges to first-order stationary points in constrained nonconvex optimization. The authors construct an infinitely smooth constrained problem where continuous-time FTRL's KKT gap stays bounded away from zero indefinitely. They also show that FTRL with Euclidean regularization converges when the objective function is analytic.
WhyConstructs an infinitely smooth problem where continuous-time FTRL keeps a large KKT gap, a surprising theoretical result with proofs.
Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris et al.
In briefCounting subcodes of linear codes with prescribed hull dimension, plus containment and limiting distributions
SummaryThe paper counts subcodes of a fixed parent linear code having prescribed dimension, hull dimension, and type over finite fields. It splits the parent code into an LCD complement and its hull, and uses projection to reduce the problem to the LCD complement, yielding explicit formulas. The authors also treat the dual containment problem and derive asymptotic distributions of hull dimensions as the relevant dimensions grow.
In briefFrontGI: Architecture-Aware Parallel GNN Inference on Chiplet Multicore Systems
SummaryGraph Neural Network inference on large graphs often scales poorly on modern multicore systems with over a hundred cores when using standard libraries. This paper presents FrontGI, a set of techniques that choose parallelization strategies based on graph structure and multicore cache hierarchies. Evaluated on a 128-core AMD EPYC system, FrontGI achieves up to 3.35x, 3.20x, 2.89x and 3.10x speedups over DGL for GCN, GraphSAGE, GIN and SGC, with larger gains over PyG.
In briefWhen and how to use NVIDIA Hopper's TMA for GPU memory loads, based on real kernel workloads.
SummaryThis paper studies when GPU kernels should use the Tensor Memory Accelerator (TMA) on NVIDIA Hopper rather than alternatives such as cp.async or direct global loads. The authors catalog the load choices made in FlashAttention-3 and use microbenchmarks on H100 to identify transfer-size crossovers and multicast scaling effects, yielding rules of thumb. They also compare TMA multicast with distributed shared memory and check, via a CUTLASS GEMM study on B200, that the dispatch rules hold qualitatively on server Blackwell (SM100).
Christin David Bose, Cesar Avalos, Junrui Pan et al.
