arXiv:2602.10392v3 Announce Type: replace
Abstract: When designing new materials, it is often necessary to tailor the material design to have some desired properties. As the set of material design parameters grows, the search space grows exponentially, making the actual synthesis and evaluation of all combinations of designs virtually impossible. Even using traditional computational methods, such as Finite Element Analysis (FEA), becomes too computationally heavy to search this design space. Recent methods use machine learning (ML) surrogate models to more efficiently determine optimal material designs; unfortunately, these methods often (i) are notoriously difficult to interpret and (ii) under perform when the training data comes from a non-uniform sampling of the entire design space. In this work, we suggest the use of tensor completion methods as an all-in-one approach for interpretability and predictions. We observe classical tensor methods are able to compete with traditional ML methods in predictions, with the added benefit of their interpretable tensor factors (which are given for free). In our experiments, we are able to rediscover physical phenomena via the tensor factors, indicating that our predictions are aligned with the physics of the problem. This also means these factors could be used by experimentalists to identify potentially novel patterns, given we are able to rediscover existing ones. We also study the effects of both types of surrogate models (traditional ML \& tensor-based) when we encounter training data from a non-uniform sampling of the design space. We observe some more specialized tensor methods that are able to give better generalization in these non-uniform sampling scenarios, due to the low-rank constraint. We find the best generalization comes from a tensor model, which is able to improve upon the baseline ML methods by up to 5\% on aggregate $R^2$, and halve the error in some out of distribution sections.
Science Journals
arXiv:2602.13241v3 Announce Type: replace
Abstract: Emergency call-takers form the first operational link in public safety response, handling over 240 million calls annually while facing a sustained training crisis: staffing shortages exceed 25\% in many centers, and preparing a single new hire can require up to 720 hours of one-on-one instruction that removes experienced personnel from active duty. Traditional training approaches struggle to scale under these constraints, limiting both coverage and feedback timeliness. In partnership with Metro Nashville Department of Emergency Communications (MNDEC), we designed, developed, and deployed a GenAI-powered call-taking training system under real-world constraints. Over six months, deployment scaled from initial pilot to 190 operational users across 1,120 training sessions, exposing systematic challenges around system delivery, rigor, resilience, and human factors that remain largely invisible in controlled or purely simulated evaluations. By analyzing deployment logs capturing 98,429 user interactions, organizational processes, and stakeholder engagement patterns, we distill four key lessons, each coupled with concrete design and governance practices. These lessons provide grounded guidance for researchers and practitioners seeking to deliver AI-driven training systems in safety-critical public sector environments where practical constraints fundamentally shape human-centric design.
arXiv:2603.08225v3 Announce Type: replace
Abstract: The recovery of types from stripped binaries is a key to exact decompilation, yet its practical realization suffers. For composite structures in particular, both layout and semantic fidelity are required to enable end-to-end reconstruction. Many existing approaches either synthesize layouts or infer names post-hoc, which weakens downstream usability. This is further aggravated by an excessive runtime overhead that is especially prohibitive in automated environments. We present XTRIDE, an improved n-gram-based approach that focuses on practicality: highly optimized throughput and actionable confidence scores allow for deployment in automated pipelines. When compared to the state of the art in struct recovery, our method achieves comparable performance while being between 70 and 2300 times faster. As our inference is grounded in real-world types, we achieve the highest ratio of fully-correct struct layouts. With an optimized training regimen, our model outperforms the current state of the art on the DIRT dataset by 5.09 percentage points, achieving 90.15% type inference accuracy overall. Furthermore, we show that n-gram-based type prediction generalizes to function signature recovery: conducting a case study on embedded firmware, we show that this efficient approach to function similarity can assist in typical reverse engineering tasks.
arXiv:2607.09092v1 Announce Type: new
Abstract: Knowledge graphs (KGs) are often automatically constructed from large-scale corpora, but they inevitably contain factual errors due to noisy sources and extraction failures, and verifying them reliably at industrial scale remains a critical challenge. To address this, we propose AgentKGV, the Agentic LLM-RAG framework for KG fact Verification, that integrates dynamic routing and iterative query rewriting, which handles surface-form mismatch in document-level retrieval. To make this framework more accurate and cost-efficient for industrial deployment, we further introduce a two-stage training strategy: turn-level distillation-based SFT that transfers reasoning ability from a large teacher model into a small model for stable query rewriting and reasoning, and trajectory-level GRPO that optimizes the search policy to reduce unnecessary retrieval at scale. On the long-tail-predicate split of the open-domain T-REx benchmark, our framework improves macro-F1 over single-turn RAG by 5.5 \%p, and two-stage training does it further by 9.4 \%p. GRPO also cuts the average number of search calls from 3.24 to 1.63 without lowering accuracy.
arXiv:2604.20140v2 Announce Type: replace
Abstract: Direct Preference Optimization (DPO) is an effective framework for aligning large language models with human preferences, but it struggles with complex reasoning tasks. DPO optimizes for the likelihood of generating preferred over dispreferred responses in their entirety and lacks the granularity to provide feedback on subsections of many-step solutions typical of reasoning tasks. Existing methods excel at either stable preference learning (e.g., DPO variants like KTO and RSO) or structured reasoning (e.g., ReMA's multi-agent RL framework, Tree of Thoughts), but fail to merge these complementary strengths. We propose HiPO (Hierarchical Preference Optimization), an extension of DPO that separates responses into reasoning segments (query clarification and context, reasoning steps, and answer) and computes loss as a weighted sum of the DPO loss for each segment. Our approach enables segment-specific training while maintaining DPO's computational efficiency and training stability. We demonstrate that for multiple 7B LLMs fine-tuned using HiPO and DPO on the Math Stack Exchange preference dataset, the models trained with HiPO outperform the others on a variety of common math benchmarks and achieve greater organization, logical flow, and consistency as measured by GPT-4.1.
arXiv:2504.03030v2 Announce Type: replace
Abstract: This paper investigates the semi-discrete optimal transport (OT) problem with entropic regularization. We characterize the solution using a governing, well-posed ordinary differential equation (ODE). This naturally yields an algorithm to solve the problem numerically, which we prove has desirable properties, notably including global strong convexity of a value function whose Hessian must be inverted in the numerical scheme. Extensive numerical experiments are conducted to validate our approach. We compare the solutions obtained using the ODE method with those derived from Newton's method. Our results demonstrate that the proposed algorithm is competitive for problems involving the squared Euclidean distance and exhibits superior performance when applied to various powers of the Euclidean distance. Finally, we note that the ODE approach yields an estimate on the rate of convergence of the solution as the regularization parameter vanishes, for a generic cost function.
arXiv:2607.09187v1 Announce Type: new
Abstract: Data-driven control methods, like Data-enabled Predictive Control (DeePC), are often formulated for linear systems, where the principle of superposition allows global system behavior to be inferred from locally collected data through Willems' fundamental lemma. This principle does not hold for nonlinear systems, whose dynamics may vary across operating regions. We propose a data-driven predictive control framework for nonlinear systems that incorporates data column preferences according to their proximity to the current operating point through a weighted norm regularization, thereby localizing the predictor without discarding any data. We show how the proposed weighting scheme induces operating point-dependent data prioritization and ensures a well-posed optimization problem. A numerical study on a nonlinear two-tank system demonstrates that the proposed method matches or outperforms hard data-selection schemes while retaining the full data matrix and its rank, thereby guaranteeing feasibility.
arXiv:2604.25397v2 Announce Type: replace
Abstract: We maintain a $(1+\varepsilon)$-spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in $[4,\Psi]$ for some fixed and known $\Psi$. The resulting $(1+\varepsilon)$-spanner has size $O(n \varepsilon^{-2} \log \Psi \log (\varepsilon^{-1}))$, where $n$ is the present number of disks.
We develop a novel use of persistent data structures to dynamically maintain our $(1+\varepsilon)$-spanner. Our approach requires $O(\varepsilon^{-2} n \log^4 n \log \Psi)$ space and has an $O( \left( \frac{\Psi}{\varepsilon} \right)^2 \log^4 n \log^2 \Psi \log^2 (\varepsilon^{-1}))$ expected amortised update time. For constant $\varepsilon$ and $\Psi$, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time. Furthermore, we observe that for any $\varepsilon < 1$, our spanner also serves as a connectivity data structure. With a slight adaptation of our techniques, this leads to better bounds for dynamically supporting connectivity queries in a disk intersection graph. In particular, we improve the space usage when compared to the dynamic data structure of (Baumann et al., DCG'24), replacing the linear dependency on $\Psi$ by a polylogarithmic dependency. Finally, we generalise our results to $d$-dimensional hypercubes.
arXiv:2604.26111v2 Announce Type: replace
Abstract: The paper focuses on the development of numerical methods for the compressible Euler equations. It is well-known that if the Mach number is small, the system becomes stiff and hence explicit schemes suffer from severe time-step restrictions, making them inefficient or even impractical. Our objective is to develop an asymptotic preserving (AP) scheme that remains uniformly accurate and stable across all Mach numbers. Instead of the conservative hyperbolic flux splitting approach, which is widely used to design AP schemes, we consider a primitive (nonconservative) formulation and introduce a nonconservative hyperbolic splitting. The resulting system is discretized using a semi-implicit approach: the stiff part is handled semi-implicitly using second-order central differences, while the nonstiff part is treated explicitly using a second-order path-conservative central-upwind discretization. A key feature of our method is that the pressure at each time level is computed by solving a well-posed Poisson-type elliptic equation, thereby enforcing the AP property. Simultaneously, we evolve the conservative form of the system using a semi-discrete central-upwind (CU) scheme. At the end of each stage of the time discretization, we perform a special post-processing that selects the appropriate numerical solution depending on the Mach number. This guarantees that in low-Mach-number regimes, the solution is obtained by the AP nonconservative scheme, while in higher-Mach-number regimes, a sharp and physically relevant solution is computed by the conservative CU scheme. Numerical experiments confirm that the proposed AP scheme achieves the expected second order of accuracy and that the time-step constraint is independent of the Mach number, making it a robust and efficient alternative to conventional explicit methods.
arXiv:2605.01456v2 Announce Type: replace
Abstract: Visualization in historical research is shifting from isolated attempts to systematic practices. However, data-driven evidence about how historians actually use visualization remains scarce. We present a corpus-driven, mixed-methods study that combines analysis of images from 4,142 research articles across history and digital humanities journals with a collaboratively developed visualization taxonomy and a semi-automatic labeling pipeline. We construct a corpus of 14,021 images, classify 4,831 visualization instances using a hierarchical, domain-informed taxonomy, and analyze patterns of visualization adoption across venues, history subfields, and time. To interpret these patterns, we conduct interviews with 11 historians and use HiFigAtlas system as a boundary object to support joint inspection of the corpus. We identify distinct roles for visualizations in historical research: primary-source, evidence-synthesis, communicative, confirmative, and exploratory. We further find that while historians pursue diverse goals with figures, persistent epistemological and practical barriers, such as uncertainty, provenance, justification burden, and publication constraints, impede the adoption of visualization. This work contributes a grounded account of visualization use in historical scholarship and points to opportunities to better support domain-specific needs.
arXiv:2605.17393v2 Announce Type: replace
Abstract: Coordination graphs are a central abstraction in cooperative multi-agent reinforcement learning (MARL), yet existing sparse-graph learners lack a theoretically grounded mechanism to decide which edges should exist and how much information each edge should carry. Current methods rely on heuristic criteria that offer no formal guarantee on the learned topology, and no principled way to allocate different communication capacities to structurally different agent relationships. To address this, we propose Heterogeneous Information-Bottleneck Coordination Graphs (HIBCG), which learns a group-aware sparse graph in which both edge existence and message capacity are theoretically justified. With the graph information bottleneck (GIB) serving as the underlying tool, HIBCG first constructs a group-aligned block-diagonal prior that provides a closed-form criterion for edge retention -- determining which edges should exist and at what density per group block -- and then controls per-agent feature bandwidth on the resulting topology, compressing messages to retain only task-relevant content. We prove that the group-aligned prior strictly tightens the variational bound on topology learning, that the objective decomposes per group block, enabling differential edge control, and that capacity allocation follows a water-filling principle.
arXiv:2607.09264v1 Announce Type: new
Abstract: This paper examines "societal relevance," a concept introduced by Haider and Sundin to address the limitations of traditional relevance models in web search. While topical and user relevance are foundational to information science, they are insufficient for managing harmful content such as misinformation or discrimination found on the uncontrolled web. This study investigates three analytical questions: the definition of societal relevance, its practical application in search systems, and its distinction from information quality measures. By analyzing various combinations of system, user, and societal relevance, the paper explores how search outputs can be optimized for the "greater good". Although the concept remains theoretically underdeveloped, it provides a vital framework for developing value-driven search engines that prioritize ethical outcomes and societal interests over mere keyword matching.
arXiv:2606.00732v4 Announce Type: replace
Abstract: Learning long-range non-stationary temporal patterns remains a core challenge for modern sequence models, particularly in strict streaming settings. In these settings, data arrive sequentially and must be processed in a single pass without simultaneously revisiting past observations. Standard architectures, including recurrent neural networks and transformers, are constrained by either truncated backpropagation through time horizon or explicit input window length for long range credit assignment. To address these limitations, we propose SHARP (Sleep-based Hierarchical Accelerated Replay), a framework that decomposes temporal learning into two complementary components: a memory module that accumulates a structured history of past inputs, and a pattern-recognition module that operates over this memory. This separation enables resource- and compute-efficient adaptation to non-stationary dynamics by eliminating the need for backpropagation through time across many steps for long-range credit assignment. Inspired by the accelerated replay observed in rodents during slow-wave sleep, SHARP incorporates offline (sleep) phases in which temporally structured memory traces are replayed in an accelerated form and integrated into higher-level memory representations, improving long-range context retention. Through controlled simulations and ablation studies, we characterize the key properties of the proposed framework. In benchmark datasets such as text8 and PG-19, we demonstrate that SHARP improves over recurrent baselines by retaining next-token predictive performance on previously seen data while continuing to learn from the current stream and generalizing to future unseen data. These gains are enabled by its hierarchical structure, which yields an exponentially increasing effective temporal context with only linear-time computational cost.
arXiv:2606.03979v2 Announce Type: replace
Abstract: The past few decades have witnessed significant advances in the design of machine learning algorithms, from early studies on task-specific shallow models to more general deep Large Language Models (LLMs). Despite showing promising results in tasks that require instant prediction or in-context learning, existing models lack the ability to continually learn and effectively transfer their temporal in-context knowledge to their long-term parameters. Inspired by human learning process, we introduce a ''Sleep'' paradigm that allows the models to continually learn, distill their short-term fragile memories into stable long-term knowledge with replay, and recursively improve themselves with ''Dreaming'' process. In more detail, sleep consists of two stages: (1) Memory Consolidation: an upward distillation process, called Knowledge Seeding, where the memories of a smaller-self are distilled into a larger network to provide more capacity while preserving the knowledge. As a proof of concept, we present a new Generalized Distillation process for {Knowledge Seeding} (i.e., the combination of on-policy distillation with Reinforcement Learning (RL)-based imitation learning); (2) Dreaming: a self-improvement phase, where the model uses RL to generate a curriculum of synthetic data to rehearse new knowledge and refine existing capabilities without human supervision. Our experiments on long-horizon, continual learning, knowledge incorporation, and few-shot generalization tasks support the importance of the sleep stage.
arXiv:2606.18157v3 Announce Type: replace
Abstract: The prize-collecting stroll is the path version of the prize-collecting TSP. Given a complete metric graph, two distinct prescribed terminal vertices $s, t$, and nonnegative penalties on vertices, the prize-collecting stroll asks for an $s$-$t$ tour minimizing its length plus the total penalty of vertices that are not visited by it. We study a common generalization of the prize-collecting stroll and several related prize-collecting routing problems, which we call the prize-collecting-$\Phi$-TSP. In this model, $\Phi$ specifies a set of prescribed vertices together with their parity and connectivity requirements. We show that, if a $\rho$-approximation algorithm for the prize-collecting TSP is available, then, for every fixed $\varepsilon>0$, there is a polynomial-time $(\rho+\varepsilon)$-approximation algorithm for the prize-collecting-$\Phi$-TSP when the number of prescribed vertices is bounded by a fixed constant. Consequently, the prize-collecting stroll can be approximated as well as the prize-collecting TSP up to an arbitrarily small additive loss in the approximation ratio. This yields a better-than-$1.6$-approximation algorithm for the prize-collecting stroll, improving the previous best-known approximation guarantee of $1.6662$.
arXiv:2606.18613v3 Announce Type: replace
Abstract: The most plausible near-term role of medical LLMs is to assist rather than replace physicians, yet current evaluations often test isolated capabilities: clinical knowledge, EHR system interaction, or patient communication. Physician assistance instead requires coordinating these capabilities within the same interaction, where physicians issue underspecified requests, patients describe symptoms ambiguously, and EHR systems demand precise tool use. We introduce PhysAssistBench, a benchmark for interactive doctor-patient-EHR assistance. Built from real MIMIC-IV cases, PhysAssistBench uses a scalable pipeline to construct agentic patients: interactive, record-grounded agents that turn static EHR records into multi-turn clinical scenarios while preserving clinical factuality. PhysAssistBench provides a curated bilingual evaluation set of 1,296 manually reviewed and physician-validated turns. Experiments with leading LLMs show that current models remain unreliable in this setting, which exposes a key bottleneck for clinical LLMs: reliable assistance requires coordination across knowledge, communication, and systems, not isolated gains in any of them.
arXiv:2606.18977v2 Announce Type: replace
Abstract: Proving termination or non-termination of lasso programs is a challenging problem in program verification. To unify state-of-the-art approaches under a common execution framework, we present PaSTTeL, a modular and generic parallel portfolio framework for termination and non-termination analysis of lasso programs. PaSTTeL is designed to: (1) facilitate the integration of new analysis algorithms into the portfolio, (2) execute registered strategies concurrently, and (3) act as a self-contained library component that can be seamlessly embedded into any external project requiring (non-)termination analysis. Initial experiments demonstrate that an instantiation of PaSTTeL performs competitively against state-of-the-art tools.
arXiv:2607.02360v4 Announce Type: replace
Abstract: Monocular spacecraft 6D pose estimation remains difficult under weak texture, thin structures, illumination variation, and occlusion. This article presents GAP-GDRNet, a geometry-aware RGB framework built on GDR-Net for a single-target synthetic spacecraft benchmark. The method strengthens the geometry-guided regression pipeline at two points. First, AFR is placed before dense geometric prediction to combine global structural attention with local weak-texture enhancement. Second, PGSA is inserted into Patch-PnP to relate downsampled geometric regions before final pose regression. Dense supervision is obtained from a Blender-based rendering and annotation process that provides masks, model-coordinate maps, camera intrinsics, and 6D pose labels. On the self-built spacecraft dataset, GAP-GDRNet achieves a rotation error of 1.96{\deg}, a translation error of 0.0165 m,and 95.16% ADD@0.02 m, outperforming the reproduced GDR-Net baseline by 3.88 percentage points while running at 35.97 FPS. Tests on T-LESS and LM-O further show consistent gains over the reproduced baseline on textureless and occluded non-spacecraft objects.
arXiv:2607.03615v2 Announce Type: replace
Abstract: Recent work has suggested that adding irrelevant documents to the input of retrieval-augmented generation (RAG) systems can improve question-answering performance, a phenomenon referred to as the Power of Noise. This motivated investigations into the role of noise in information retrieval. In this paper, we reproduce the main findings of Cuconasu et al. and evaluate the robustness of the effect under extended experimental settings. We first confirm that the phenomenon holds under the original setup, which uses earlier-generation LLMs, restrictive prompting and constrained decoding settings. We subsequently introduce a series of extensions to investigate the underlying causes of the noise effect, examining the authors' original design choices including the use of different models, instruction prompting, and relaxed output length constraints. Across these ablations, the Power-of-Noise pattern proves highly sensitive to inference configuration: it can appear, weaken, or disappear under small changes to prompt formulation and decoding limits. Combined with our error analysis, which shows substantial contributions from truncation and malformed generations, this variance indicates that the original effect cannot be robustly confirmed as a general benefit of noisy retrieval under these experimental conditions. More broadly, our work highlights the importance of carefully scrutinizing inference design in retrieval-augmented generation systems. Our code is available at https://github.com/ina0105/The-Power-of-Noise-Reproduction.
arXiv:2607.04683v2 Announce Type: replace
Abstract: Vision-language models (VLMs) perform well on visual question answering with high-quality images but struggle when questions require knowledge beyond what is clearly and directly visible. In such settings, uncertainty quantification should not only indicate whether the model is likely to fail but also diagnose why it is uncertain, across dimensions such as perception, entity recognition, and knowledge retrieval. While prior work has focused on individual failure modes in isolation or treated incorrect answers as monolithic failures, we propose a unified framework for disentangling these failure modes and investigate whether pre-generation signals can predict these failure sources. Across a range of datasets and model families, we find a consistent pattern in VLM errors: some failures arise from visual or recognition bottlenecks, while others persist after the relevant entity is identified. Our main finding is that these failure sources can be predicted before decoding: recognition-related failures are best captured by visual-token representations, while failures that remain after recognition are better captured by prompt-conditioned hidden states. This pre-generation signal enables efficient failure-source prediction before the model produces an answer, allowing uncertain cases to be routed to targeted interventions such as image repair, entity recognition support, or external retrieval.
arXiv:2607.05734v2 Announce Type: replace
Abstract: Chain-of-thought (CoT) distillation in the recommendation domain is a necessary precursor to RL training, but raw teacher traces are ill-suited to this task. Large teachers approach the recommendation task with unusually high reasoning uncertainty, repeatedly rechecking their answers without revising them; supervised fine-tuning on such traces produces verbose students that never revise their initial guess. Furthermore, due to the novelty of the recommendation domain, the teacher's reasoning traces are highly out-of-distribution for the small student LLM.
We propose Student-Aware CoT Optimization for Recommendation Distillation (SCOReD), a CoT optimization framework tailored to recommendation that first parses each teacher trace into typed segments and uses the student LLM's attention to score the importance of each segment. Then SCOReD dynamically selects a per-segment edit (KEEP / REWRITE / FUSE / PRUNE) based on the output length and comparative log probability lift of the answer given the edit as per the student. Therefore, SCOReD prunes redundant sections of the reasoning trace while preserving information-dense sections and adapts raw teacher traces to the student's output distribution. Training on SCOReD-optimized CoTs provides a cleaner learning signal to the student model and improves over baseline SFT by 1.56% NDCG and 1.9% Recall@5, while reducing reasoning length by 27.3%.
arXiv:2607.06993v2 Announce Type: replace
Abstract: Customer behavior modeling underpins recommendation, marketing, and decision support, yet existing approaches either optimize predictive accuracy without explaining decisions or simulate users without grounding them in real behavioral data. We present the Large Behavioral Model (LBM) that learns customer decision making directly from large-scale retail transactions through a unified Person-Environment formulation. Customer state is represented by a behavioral profile derived from historical purchases, while product context is incorporated through retrieval-augmented generation. The model is trained using continued pre-training on verbalized behavioral data, supervised fine-tuning for decision generation, and reinforcement learning with verifiable rewards for evidence-based calibration. We evaluate the proposed framework on purchase prediction, hard-negative discrimination, basket completion, promotion response, and cross-domain voucher redemption. The model consistently outperforms frontier general-purpose language models on in-domain retail tasks while demonstrating strong zero-shot and fine-tuned transfer across retailers and decision domains. Ablation studies show that continued pre-training is the primary driver of behavioral generalization, retrieval is most effective when applied during both training and inference, and reinforcement learning improves reliance on explicit behavioral evidence over generic language-model priors. These results demonstrate that behavioral knowledge encoded in transaction histories can be effectively learned by language models, providing a scalable foundation for customer digital twins and behavior simulation.
arXiv:2607.09649v1 Announce Type: new
Abstract: Concept-based explainable artificial intelligence (AI) can make model reasoning more human-understandable, but concept-level outputs are not automatically trustworthy. We introduce ConceptSMILE, a model-agnostic perturbation-based auditing framework for evaluating the reliability of concept-based explanations. Rather than replacing SMILE, ConceptSMILE extends its perturbation-based logic from feature- or region-level attribution to the auditing of human-understandable concept explanations. The framework perturbs input regions, measures concept-response shifts, applies locality weighting, and fits an XGBoost surrogate to approximate local concept behaviour. Reliability is assessed through attribution accuracy, surrogate fidelity, faithfulness, stability, and consistency. We evaluate ConceptSMILE on retinal fundus images by comparing MedSAM-derived visual concepts with VLM-based semantic concepts. Results show that reliability varies across concepts and pathways: MedSAM achieves stronger spatial attribution and the highest surrogate fidelity ($R^2 = 0.8503$, $R_w^2 = 0.8465$), while the VLM pathway shows stronger vessel faithfulness and stronger stability under selected artefact conditions. ConceptSMILE provides an independent audit layer for evaluating the trustworthiness of concept-based XAI.
arXiv:2501.12293v4 Announce Type: replace
Abstract: In this paper, we present improved decoding algorithms for expander-based Tanner codes.
We begin by developing a randomized linear-time decoding algorithm that, under the condition that $ \delta d_0 > 2 $, corrects up to $ \alpha n $ errors for a Tanner code $ T(G, C_0) $, where $ G $ is a $ (c, d, \alpha, \delta) $-bipartite expander with $n$ left vertices, and $ C_0 \subseteq \mathbb{F}_2^d $ is a linear inner code with minimum distance $ d_0 $. This result improves upon the previous work of Shen, Shangguan, Ouyang and Cheng (IEEE TIT 2025), which required $ \delta d_0 > 3 $.
We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al.\ by achieving a decoding radius of $ \alpha n $, compared with the previous radius of $ \frac{2\alpha}{d_0(1 + 0.5c\delta) }n$.
Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code $T(G,C_0)$ is approximately $f_\delta^{-1} \left( \frac{1}{d_0} \right) \alpha n $, where $ f_\delta(\cdot) $ is the Size-Expansion Function.
As another application, we improve the decoding radius of our decoding algorithms from $\alpha n$ to approximately $f_\delta^{-1}\left(\frac{2}{d_0}\right)\alpha n$.
Finally, we extend Viderman's find-erasures-and-decode framework (ACM TOCT 2013) to general linear inner codes, obtaining a deterministic linear-time decoder for $\delta d_{0}>1.8$ when $d_0=3$, thus pushing below the $\delta d_0 > 2$ threshold of our general result.
arXiv:2502.08272v5 Announce Type: replace
Abstract: We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs). Denote $n$ and $w$ as the length and the width of a ROBP. We have the following results.
For standard ROBPs, we give an explicit $\varepsilon$-WPRG with seed length
$$O\left(\frac{\log n\log (nw)}{\max\left\{1,\log\log w-\log\log n\right\}}+\log w \left(\log\log\log w-\log\log\max\left\{2,\frac{\log w}{\log \frac{n}{\varepsilon}}\right\}\right)+\log\frac{1}{\varepsilon}\right).$$
For permutation ROBPs with unbounded widths and single accept nodes, we give an explicit $\varepsilon$-WPRG with seed length
$$O\left( \log n\left( \log\log n + \sqrt{\log(1/\varepsilon)} \right)+\log(1/\varepsilon)\right). $$
We also give a new Nisan-Zuckerman style derandomization for regular ROBPs with width $w$, length $n = 2^{O(\sqrt{\log w})}$, and multiple accept nodes. We attain optimal space complexity $O(\log w)$ for arbitrary approximation error $\varepsilon = 1/\text{poly} (w)$.
All our results are based on iterative weighted pseudorandom reductions, which can iteratively reduce fooling long ROBPs to fooling short ones.