arXiv:2605.17508v1 Announce Type: new
Abstract: Split Federated Learning (SFL) enables privacy-preserving collaborative training by partitioning models between clients and a server. However, under non-IID data distributions, SFL often suffers from biased optimization and unstable convergence, while existing solutions largely adapt techniques from conventional federated learning. In this work, we observe that the split architecture of SFL inherently alters how client information is represented and coordinated, opening opportunities for bias compensation beyond parameter-level aggregation. Based on this insight, we propose BESplit, an architecture-aware framework that exploits the intrinsic structure of SFL to mitigate non-IID effects. First, to prevent biased local data from dominating global updates, we introduce Evidential Aggregation (EA) to perform fine-grained reweighting of client contributions based on evidential uncertainty. Second, to further reduce distributional skew, we develop Bias-Compensated Collaboration (BCC) to align split-layer representations by pairing complementary clients. Finally, Dual-Teacher Distillation (DTD) is incorporated to synchronize knowledge between decoupled client and server models, enabling independent local inference. Extensive experiments on five benchmark datasets demonstrate that BESplit consistently outperforms state-of-the-art methods in accuracy, convergence stability, and computational efficiency under diverse non-IID settings.
Science Journals
arXiv:2605.15407v2 Announce Type: replace
Abstract: We consider amortized Bayesian inference for nonlinear inverse problems in settings where only samples from the joint distribution of parameters and observations are available. Classical methods such as Markov chain Monte Carlo require solving a new inference problem for each observation, which can be computationally prohibitive when inference must be repeated many times. We propose a transport-based approach that learns an observation-dependent map pushing forward a reference measure to approximate the posterior distribution. The map is trained by minimizing an averaged energy-distance objective between the true posterior and the learned pushforward. This formulation is likelihood-free, requiring only joint samples, and avoids density evaluation, invertibility constraints, and Jacobian determinant computations. For function-space inverse problems with Gaussian priors, we parameterize the transport map as the identity plus a perturbation in the Cameron-Martin space of the prior, preserving absolute continuity with respect to the prior. In infinite-dimensional settings, the map is represented using neural operators. We illustrate the method on a finite-dimensional nonlinear inverse problem and two PDE-constrained inverse problems arising in porous medium flow and seismic inversion. The results show that the learned transport captures posterior structure, including multimodality and dominant modes, while enabling fast posterior sampling for new observations.
arXiv:2509.13045v4 Announce Type: replace-cross
Abstract: Boron-doped diamond crystals (BDD, C$_{1-x}$B$_{x}$) exhibit exceptional mechanical strength, electronic tunability, and resistance to radiation damage. This makes them promising materials for use in gamma-ray crystal-based light sources. To better understand and quantify the structural distortions introduced by doping, which are critical for maintaining channelling efficiency, we perform atomistic-level molecular dynamics simulations on periodic C$_{1-x}$B$_{x}$ systems of various sizes. These simulations allow the influence of boron concentration on the lattice constant and the (110) and (100) inter-planar distances to be evaluated over the concentration range from pure diamond (0%) to 5% boron at room temperature (300 K). Linear relationships between both lattice constant and inter-planar distance with increasing dopant concentration are observed, with a deviation from Vegard's Law. This deviation is larger than that reported by other theoretical and computational studies; however, this may be attributed to an enhanced crystal quality over these studies, a vital aspect when considering gamma-ray crystal light source design. The methodology presented here incorporates several refinements to closely reflect the conditions of microwave plasma chemical vapour deposition (MPCVD) crystal growth. Validation of the methodology is provided through a comprehensive statistical analysis of the structure of our generated crystals. These results enable reliable atomistic modelling of doped diamond crystals and support their use in the design and fabrication of periodically bent structures for next-generation gamma-ray light source technologies.
arXiv:2605.17655v1 Announce Type: new
Abstract: The European Commission recently introduced new regulation to harmonize transparency reporting of large online platforms under the Digital Services Act (DSA). Here, we present the first systematic evaluation of transparency reporting data quality after this normative change, for the eight largest social media platforms in the European Union. In detail, we run a set of large-scale quantitative analyses on key reporting dimensions, followed by a structured comparative assessment across platforms and reporting mechanisms. Among our findings is that: (i) the analyzed platforms had varying degrees of compliance and data quality, but all exhibited issues on data formatting, timeliness, consistency, and completeness; (ii) some platforms employed differing reporting procedures across mechanisms, which caused them to submit contrasting information; (iii) despite the harmonization, a number of issues still prevent interoperability between reporting mechanisms; and (iv) many of the previously identified issues with transparency reporting are still unresolved. We conclude by discussing implications for transparency auditing and proposing key targeted improvements to strengthen the reliability and interoperability of DSA transparency reporting.
arXiv:2411.15294v2 Announce Type: replace-cross
Abstract: For decades it is known that Quantum Computers might serve as a tool to solve a very specific kind of problems that have long thought to be incalculable. Some of those problems are of a combinatorial nature, with the quantum advantage arising from the exploding size of a huge decision tree. Although this is of high interest as well, there are more opportunities to make use of the quantum advantage among non-perfect information games with a limited amount of steps within the game. Even though it is not possible to answer the question for the winning move in a specific situation, people are rather interested in what choice gives the best outcome in the long run. This leads us to the search for the highest number of paths within the game's decision tree despite the lack of information and, thus, to a maximum of the payoff-function. We want to illustrate on how Quantum Computers can play a significant role in solving these kind of games, using an example of the most popular German card game Skat. Therefore we use quantum registers to encode the game's information properly and construct the corresponding quantum gates in order to model the game progress and obey the rules. Finally, we use a score operator to project the quantum state onto the winning subspace and therefore evaluate the winning probability for each alternative decision by the player to be made by using quantum algorithms, such as quantum counting of the winning paths to gain a possible advantage in computation speed over classical approaches. Thus, we get a reasonable recommendation of how to act at the table due to the payoff-function maximization. This approach is clearly not doable on a classical computer due to the huge tree-search problem and we discuss peculiarities of the problem that may lead to a quantum advantage when exceeding a certain problem size.
arXiv:2503.21405v2 Announce Type: replace-cross
Abstract: In this paper, we study the error bound between the Dirac--Fock ground-state energy and the Hartree--Fock ground-state energy, a quantity known as the relativistic effect in quantum mechanics. We confirm that the relativistic effect in the Dirac--Fock ground-state energy is of the order $\mathcal{O}(c^{-2})$ with $c$ being the speed of light. Furthermore, if the potential between electrons and nuclei is regular, we get the well-known leading order relativistic correction -- the Breit--Pauli term, which is the sum of the mass-velocity term, the Darwin term, and the spin-orbit term. As a consequence, we also show that the same relativistic effects and leading order relativistic correction also hold in a QED model introduced by Mittleman when the vacuum polarization -- a term of the order $\mathcal{O}(c^{-3})$ -- is neglected. To our knowledge, this is the first time in mathematics that the leading-order relativistic correction has been obtained from nonlinear Dirac ground-state energy problems.
arXiv:2605.17366v1 Announce Type: new
Abstract: Multimodal item embeddings are crucial for e-commerce item-to-item (I2I) retrieval, yet real-world product images often contain promotional overlays and background clutter that inject spurious visual cues and degrade retrieval robustness. This issue is particularly pronounced in MLRM-style pipelines, where a frozen vision encoder is connected to an LLM through a lightweight connector that must selectively aggregate visual tokens. We propose Text-Guided Q-Former (TGQ-Former), a text-guided visual representation learning framework that leverages structured metadata as semantic guidance for visual token extraction while preserving complementary visual evidence. Concretely, TGQ-Former employs a hybrid-query connector to disentangle metadata-anchored and exploratory visual streams, and introduces a lightweight reliability-aware dual-gated vector modulation module to adaptively calibrate their contributions under noisy inputs. Experiments on large-scale, real-world e-commerce datasets with full-pool retrieval show that TGQ-Former consistently outperforms strong connector baselines and end-to-end MLLMs. On average, it improves Hit Rate@100 (H@100) by 6.04%, demonstrating the effectiveness of text-guided visual encoding for robust multimodal retrieval.
arXiv:2605.17009v1 Announce Type: cross
Abstract: The reconfigurable intelligent surfaces detection and identification (RISs-ID) is a critical process that enables a base station (BS) to adaptively assign the appropriate RIS to a given user equipment (UE). This work proposes a novel modulation scheme to enhance the reliability of RIS-ID by reducing the miss detection and false-alarm probabilities. Specifically, we leverage the RIS's passive beamforming gain to enable over-the-air modulation of the RIS ID, combined with passive beam sweeping to extend detection coverage in angular space. The proposed modulation scheme is validated through computer simulations and prototype experiments, demonstrating its effectiveness in reducing miss-detection and false-alarm probabilities.
arXiv:2605.17107v1 Announce Type: cross
Abstract: We introduce a novel framework for uncertainty quantification of solution operators associated with stochastic partial differential equations (SPDEs). Although SPDEs play a central role in modeling complex physical systems under uncertainty, their practical use typically requires specifying the magnitude and structure of model uncertainties that are often unknown and difficult to infer from noisy measurements. To address this challenge, we develop a stochastic operator-learning framework that learns directly from noisy data and outputs both a mean solution field and a quantification of uncertainty. The proposed method, namely the Stochastic Operator Network (SON), is constructed by combining the structure of the Deep Operator Network (DeepONet) with Stochastic Neural Networks (SNNs) to model stochasticity and enable probabilistic prediction. The training procedure is carried out by minimizing a Hamiltonian-type loss and optimizing the resulting objective using the Stochastic Maximum Principle. Numerical experiments on benchmark SPDEs under multiple uncertainty sources demonstrate the accuracy and robustness of the proposed method in capturing solution structure and quantifying predictive uncertainty.
arXiv:2605.18334v1 Announce Type: new
Abstract: While 3D Gaussian Splatting (3DGS) has revolutionized real-time photorealistic view synthesis, its fundamental reliance on symmetric Gaussian distributions introduces visual artifacts that hinder accurate spatial data exploration. Specifically, symmetric kernels struggle to capture shape and color discontinuities , which cause blurriness and primitive redundancy that mislead human perception during visual analysis. To address these visualization barriers, we introduce 3D Skew Gaussian Splatting (3DSGS), a novel framework that significantly enhances the structural fidelity and compactness of explicit scene representations. Our key insight lies in extending the standard primitive to a general Skew Gaussian counterpart. This generalized primitive inherits the highly efficient rasterization properties of standard Gaussians while gaining intrinsic asymmetric modeling capabilities. We couple this with an enhanced opacity representation to better handle complex transparency, alongside a depth-aware densification strategy that intelligently manages primitive allocation. Furthermore, to make these advancements actionable for real-world visual analytics, we re-derive the CUDA rasterization pipeline to universally support both symmetric and skew Gaussians, integrating it into a decoupled, free-camera interactive visualization engine. Extensive experiments demonstrate that 3DSGS achieves superior rendering quality and structural compactness, particularly in regions with intricate details, while maintaining the real-time frame rates necessary for fluid interactive exploration. Supplementary derivations and visual results are available at \textbf{\textit{https://3d-skew-gs.github.io/}}.
arXiv:2601.13992v2 Announce Type: replace
Abstract: Chain-of-Thought (CoT) reasoning empowers Large Language Models (LLMs) with remarkable capabilities but typically requires prohibitive parameter scales. CoT distillation has emerged as a promising paradigm to transfer reasoning prowess into compact Student Models (SLMs), but existing approaches often rely on a solitary teacher, capping the student's potential since individual LLMs often exhibit distinct capability biases and may suffer from catastrophic forgetting. While leveraging diverse teachers seems appealing, effectively fusing their supervisions remains challenging: teacher-student incompatibility risks amplifying hallucinations, and passive supervision fails to ensure genuine logic internalization. To address this, we introduce COMPACT, a framework that adaptively fuses supervisions from different teachers by dynamically weighting teacher gradients based on the student's real-time compatibility evaluated by a multi-dimensional metric: (1) Graph-based Consensus to filter misleading rationales by identifying mainstream reasoning paths; (2) Mutual-Information-based Adaptability to detect "epiphany moments" for genuinely understanding the reasoning process rather than merely imitating; and (3) Loss-based Difficulty to assess student receptivity to the teacher's guidance and prevent negative transfer. Extensive experiments and latent space analysis demonstrate that COMPACT effectively integrates diverse reasoning capabilities without damaging the model's original knowledge structure, achieving state-of-the-art performance on various benchmarks while mitigating catastrophic forgetting.
arXiv:2605.17811v1 Announce Type: new
Abstract: Can a shared-weight recurrent Transformer develop distinct internal roles without being partitioned into separate modules? We study this in Asymmetric Input Recurrence (AIR), a minimal two-state reasoning architecture in which the same Transformer model is reused for both updates (per literature, L and H) and the only built-in difference in the update rule is that the encoded input is injected during L-updates but not H-updates. Across Sudoku-Extreme and Maze, decoded rollouts reveal a consistent split: $\zH$ behaves like a fully committed proposal state, whereas $\zL$ retains local uncertainty and shifting intermediate structure. Freeze experiments show that this split is, in practice, related to the model's state dynamics: in Sudoku, freezing $\zH$ reduces $\zL$'s content changes whereas freezing $\zL$ increases $\zH$'s, while in Maze, freezing either state increases content changes in the other state. Ablations show that to induce specialization, the shared model needs to be able to tell the two update types apart, either from input injection asymmetry or from a separate level token. Mechanistically, attention analysis shows that L-updates are consistently more local than H-updates in both Sudoku and Maze. Together, these results show that, in a two-state recurrent setting, a clear state-identity signal can induce stable, related functional roles inside a shared-parameter recurrent Transformer. Code is available at \href{https://github.com/juchengshen/air}{\textcolor{blue}{https://github.com/juchengshen/air}}.
arXiv:2605.17828v1 Announce Type: new
Abstract: The goal of this primer is to provide a relatively short exposition of the basics of multigrid methods, simplified by focusing on fundamental concepts in a variational setting. This is done by way of a quadratic energy minimization formulation of symmetric positive definite linear equations arising from the discretization of elliptic partial differential equations. This focus provides an alternate viewpoint to other expositions and, more importantly, it enables a simplification of the development while clarifying the principles that lead to effective algorithms. The development begins with multigrid as an iterative solver exemplified by the so-called V-cycle. It then introduces the full multigrid method as a direct solver in the sense that it is aimed directly at the source of the matrix equations. In this way, full multigrid attempts to achieve discretization-level accuracy at a cost comparable to that of a few matrix multiplies on the finest level.
arXiv:2605.17566v1 Announce Type: new
Abstract: With the rapid progress of multimodal foundation models and predictive pre-training, an important open question is how to equip 3D point clouds with a pre-training paradigm that is better aligned with next-token and next-embedding learning. Existing point-cloud self-supervised methods are largely built on masked reconstruction or explicit geometric generation, and thus remain tied to input recovery rather than predictive dependency modeling. In this paper, we introduce PointNTP, which reformulates point cloud pre-training as a fully causal, decoder-free latent Next-Token Prediction problem. Specifically, each point cloud is first partitioned into local patches and serialized into a structured 3D token sequence according to patch-center geometry. The resulting sequence is then modeled by a causal Transformer under prefix-only conditioning, and trained with a shift-based prediction objective stabilized by stop-gradient targets. This design enables the model to learn structural dependencies directly in latent space, without reconstruction decoders or explicit geometric recovery. Extensive experiments demonstrate that the proposed PointNTP is highly competitive across multiple downstream tasks: it achieves 93.8%(+0.5%), 92.6%(+0.3%), and 89.3%(+1.1%) on OBJ_BG, OBJ_ONLY, and PB_T50_RS of ScanObjectNN, respectively; obtains 85.0%(+0.1%) in Cls.mIoU on ShapeNetPart; and reaches 71.1% mAcc on S3DIS Area 5. Overall, decoder-free causal latent prediction provides a simple, scalable, and potentially modality-agnostic paradigm for point-cloud self-supervised learning, offering a new 3D perspective on foundation-style predictive learning for 3D data.
arXiv:2605.18273v1 Announce Type: new
Abstract: The hydroelastic response of free floating viscoelastic covers is measured using Faraday waves on the surface of a vertically oscillated fluid layer. We systematically vary the thickness $d$ of the covers to investigate its effect on the hydroelastic dispersion relation, the damping and the isotropy of the waves. Compared to bare fluids, the wave patterns are disordered. Various methods are explored to define and analyze the wavelengths, the isotropy, and shape of the waves. We find a significant difference between the measurements and the theoretical dispersion relation. Over all thicknesses $d$, this is explained by an increase in the in-plane membrane tension, which scales with $d^{3/2}$. Covering waves also has a large efect on their damping. Only for thin covers ($d = 20\: \mu{\rm m}$) the onset amplitude (and thus the damping) can be explained by dissipation in the bulk and in the boundary layer of the water beneath the cover. The same was found for bare water due to the presence of an immobile surface layer. Lastly, we find a large effect of the membrane on the ampitude of the waves, which we attribute to nonlinear wave interaction.
arXiv:2605.17582v1 Announce Type: new
Abstract: Many natural and engineered time series -- equity returns, climate anomalies, turbulent velocities, neural recordings, packet-level network traffic -- are approximately self-similar: their horizon-$T$ distribution is tied to the horizon-$1$ distribution by one scaling exponent $H$. Standard deep generative sequence models (transformers, dilated TCNs, the WaveNet family) ignore this. Their receptive fields are wide, but kernel parameters live independently at every dilation level, yielding a multi-scale architecture, not a scale-equivariant one. We make three contributions. First, we give a precise definition of discrete scale equivariance for 1D causal networks and prove that dyadic dilation commutes (up to boundary effects) with any dilated-convolution stack whose kernel weights are shared across levels. Tying the kernel shrinks the convolutional parameter budget by an $L$-fold factor (where $L$ is depth) and hard-wires self-similarity in as an inductive bias. Second, we wrap this Scale-Equivariant WaveNet (SE-WaveNet) backbone in three components that carry the same prior: a one-level Daubechies-4 wavelet input, a Hurst-FiLM block exposing the local scaling exponent, and a spectral-consistency training term targeting the $|f|^{-(2H+1)}$ power-law spectrum. The head is a conditional normalising flow, chosen to preserve equivariance. Third, on 30 years of S&P 500 daily log-returns, SE-WaveNet samples reproduce the empirical scaling-collapse diagnostic on the Allan-Variance top-25 universe (median $\mathcal{C}^\star = 0.020$), while a vanilla WaveNet at matched capacity does not ($\geq 0.06$). NLL, KS-calibration, and tail energy distance tie or beat the baseline, with $L\times$ fewer convolutional parameters.
arXiv:2605.17902v1 Announce Type: new
Abstract: Stochastic-process-based degradation modeling is a core approach for estimating the distribution of remaining useful life (RUL); however, the selection of an appropriate stochastic process has not been sufficiently addressed. Existing model selection methods mainly rely on the statistical fit of the observed health indicator (HI) trajectory, but this approach may select a model that is inconsistent with the underlying degradation mechanism when the observation window is short or the signal is highly noisy. To address this issue, this paper proposes Literature-Anchored Stochastic Trajectory Retrieval-Augmented Generation (LAST-RAG). The proposed method uses both the observed HI trajectory and domain-specific context, and hierarchically conditions the candidate degradation model space based on theoretical and mechanical evidence retrieved from a local evidence bank. In addition, Rule-based Confidence Reasoning with Uncertain State (RCRUS) is introduced to prevent candidate models from being prematurely eliminated when hierarchical decisions are uncertain. Simulation-based experiments demonstrate that the proposed method outperforms statistical, prognostic, and uncertainty-aware baselines in both Wiener/gamma family classification and detailed degradation model classification. Ultimately, this study reframes degradation model selection from a purely statistical goodness-of-fit problem into a knowledge-conditioned decision-making problem that integrates observed data with domain knowledge.
arXiv:2605.17850v1 Announce Type: cross
Abstract: iffusion-based generative models increasingly rely on inference-time guidance, adding a drift term or reweighting mixture of experts, to improve sample quality on task-specific objectives. However, most existing techniques require repeated score or gradient evaluations, introducing bias, high computational overhead, or both. We introduce \texttt{URGE}, Unbiased Resampling via Girsanov Estimation, a derivative-free inference-time scaling algorithm that performs path-wise importance reweighting via a Girsanov change of measure. Instead of computing gradient-based particle weights in previous work, \texttt{URGE} attaches a simple multiplicative weight to each simulated trajectory and periodically resamples. No score, no Hessian, and no PDE evaluation is required. We establish an equivalence between path-wise and particle-wise SMC: the Girsanov path weight admits a backward conditional expectation that recovers the previous particle-level weights, guaranteeing that both schemes produce the same unbiased terminal law. Empirically, \texttt{URGE} outperforms existing inference-time guidance baselines on synthetic tests and diffusion-model benchmarks, achieving better generation quality, while being significantly simpler to implement and fully gradient-free.
arXiv:2605.17914v1 Announce Type: new
Abstract: We propose a novel framework that provides constructive feedback to an LLM in the "guess-and-check" paradigm by formally verifying its own thinking process and detecting local reasoning errors. We apply this framework to the loop invariant synthesis problem. We prompt the model to produce a step-by-step natural language proof justifying its thinking process for the failed verification condition of its generated loop invariants. Then, we use an LLM to translate the reasoning steps into first-order logic implications, which can be checked automatically. An invalid implication pinpoints the exact logical flaw in the LLM's thinking process, which we then use to construct targeted feedback for refinement. We have implemented our approach in a tool called LORIS and evaluated it on a main benchmark suite of 460 C programs and an additional benchmark suite of 50 C programs each of which involves non-linear properties. On the main benchmark suite, LORIS solved 445 of the programs, and achieved an overall success rate of $93.1\%$. LORIS also demonstrates robustness on the challenging non-linear benchmark suite.
arXiv:2605.17925v1 Announce Type: new
Abstract: Optimization problems in real-world applications across the medical and engineering domains often involve potential risks when evaluating candidate solutions. Safe optimization aims to perform optimization while suppressing unsafe solution evaluations in such situations. For continuous search spaces, there exist safe optimization methods based on evolutionary computation. However, the algorithm development of safe optimization methods for binary search spaces has not been adequately addressed. In this study, we incorporate additional mechanisms for safe optimization into a binary optimization method, the adaptive stochastic natural gradient method (ASNG) with a family of Bernoulli distributions. For safety functions that must be kept non-negative during optimization, the proposed method, safe ASNG, estimates the Lipschitz constants with respect to the Hamming distance by constructing surrogate models of safety functions based on discrete Walsh functions. Then, safe ASNG computes a safe region that consists of safe solutions around the previously evaluated safe solutions. By projecting newly generated solutions to their nearest neighbors within the safe region, safe ASNG suppresses unsafe solution evaluations. Experimental results on benchmark problems on binary domains confirm that, while the comparative methods fail to suppress unsafe solution evaluations, safe ASNG achieves efficient optimization while effectively suppressing unsafe solution evaluations.
arXiv:2605.18319v1 Announce Type: new
Abstract: We develop a framework for analyzing parameter symmetries in deep ReLU networks and obtain a complete characterization of the generic parameter fibers for three-layer bottleneck architectures. Our approach provides explicit semi-algebraic descriptions of these fibers and yields a polynomial time algorithm for deciding functional equivalence of two parameters. The symmetries include discrete and continuous transformations arising from layer composition, and depend on whether deeper layers hide or preserve geometric structure from preceding layers. Finally, we show that some of these symmetries induce local conservation laws along gradient flow, while others do not.
arXiv:2506.15588v2 Announce Type: replace
Abstract: Differential privacy (DP) protects sensitive data during neural network training, but standard methods like DP-Adam suffer from high memory overhead due to per-sample gradient clipping, limiting scalability. We introduce DP-GRAPE (Gradient RAndom ProjEction), a DP training method that significantly reduces memory usage while maintaining utility on par with first-order DP approaches. DP-GRAPE is motivated by our finding that privatization flattens the gradient singular value spectrum, making SVD-based projections (as in GaLore (Zhao et al., 2024)) unnecessary. Consequently, DP-GRAPE employs three key components: (1) random Gaussian matrices replace SVD-based subspaces, (2) gradients are privatized after projection, and (3) projection is applied during backpropagation. These contributions eliminate the need for costly SVD computations, enable substantial memory savings, and lead to improved utility. Despite operating in lower-dimensional subspaces, our theoretical analysis shows that DP-GRAPE achieves a privacy-utility tradeoff comparable to DP-SGD. Our extensive empirical experiments show that DP-GRAPE can significantly reduce the memory footprint of DP training without sacrificing accuracy or training time. In particular, DP-GRAPE reduces memory usage by over 63% when pre-training Vision Transformers and over 70% when fine-tuning RoBERTa-Large as compared to DP-Adam, while achieving similar performance. We further demonstrate that DP-GRAPE scales to fine-tuning large models such as OPT with up to 6.7 billion parameters, a scale at which DP-Adam fails due to memory constraints. Our code is available at https://github.com/alexmul1114/DP_GRAPE.
arXiv:2512.02691v3 Announce Type: replace
Abstract: Consider a high-multiplicity Bin Packing instance $I$ with $d$ distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime ${{|I|}^2}^{O(d)}$ for this problem~[SODA'14], where $|I|$ denotes the encoding length of the instance $I$. Although Jansen and Klein~[SODA'17] later developed an algorithm that improves upon this runtime in a special case, it has remained a major open problem by Goemans and Rothvoss~[J.ACM'20] whether the doubly exponential dependency on $d$ is necessary.
We solve this open problem by showing that unless the ETH fails, there is no algorithm solving the high-multiplicity Bin Packing problem in time ${{|I|}^2}^{o(d)}$. To prove this, we introduce a novel reduction from 3-SAT. The core of our construction is efficiently encoding all information from a 3-SAT instance with $n$ variables into an ILP with $O(\log(n))$ variables and constraints.
This result confirms that the Goemans and Rothvoss algorithm is essentially best-possible for Bin Packing parameterized by the number $d$ of item sizes in the context of XP time algorithms.
arXiv:2602.06866v2 Announce Type: replace
Abstract: Reliable short-term demand forecasting is essential for managing shared micro-mobility services and ensuring responsive, user-centered operations. This study introduces T-STAR (Two-stage Spatial and Temporal Adaptive contextual Representation), a novel transformer-based probabilistic framework designed to forecast station-level bike-sharing demand at a 15-minute resolution. T-STAR addresses key challenges in high-resolution forecasting by disentangling consistent demand patterns from short-term fluctuations through a hierarchical two-stage structure. The first stage captures coarse-grained hourly demand patterns, while the second stage improves prediction accuracy by incorporating high-frequency, localized inputs, including recent fluctuations and real-time demand variations in connected metro services, to account for temporal shifts in short-term demand. Time series transformer models are employed in both stages to generate probabilistic predictions. Extensive experiments using Washington D.C.'s Capital Bikeshare data demonstrate that T-STAR outperforms existing methods in both deterministic and probabilistic accuracy. The model exhibits strong spatial and temporal robustness across stations and time periods. A zero-shot forecasting experiment further highlights T-STAR's ability to transfer to previously unseen service areas without retraining. These results underscore the framework's potential to deliver granular, reliable, and uncertainty-aware short-term demand forecasts, which enable seamless integration to support multimodal trip planning for travelers and enhance real-time operations in shared micro-mobility services.
arXiv:2602.20706v2 Announce Type: replace
Abstract: This paper introduces online algorithms with unreliable guidance (OAG), a model for ML-augmented online decision-making that cleanly separates the predictive and algorithmic components, thus offering a single, well-defined analysis framework that depends only on the problem at hand. Formulated through the lens of request-answer games, the OAG model brings multiple concepts (predictions from the answer space, guide, anytime competitiveness) which enable learning-augmented algorithms to be analyzed independently of predictor-specific choices - such as prediction semantics, error functions, or probing strategies - that would otherwise restrict the algorithm's generality and applicability. The clean framework of the OAG model allows to build the first generic compiler, the drop-or-trust-blindly (DTB) compiler, that turns almost any standard, prediction-free online algorithm into a learning-augmented one. Although simple, we show that the DTB compiler produces new learning-augmented algorithms with strong consistency-robustness guarantees for three classic online problems: we achieve new trade-offs for bipartite matching with adversarial arrival order, and obtain optimal solutions for caching and uniform metrical task systems.