Forskningsradar

Science Journals

Peer-reviewade publikationer — 51240 artiklar

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
arXiv:2605.19702v1 Announce Type: new Abstract: Color refinement is an important technique that works very well in practice for the graph isomorphism problem. Tinhofer graphs are the class of graphs for which refinement together with individualization correctly tests graph isomorphism against every other graph, irrespective of the choices of vertices made during individualization. Motivated by the fact that Tinhofer graphs form a natural boundary for efficient graph isomorphism tests based on color refinement, in this paper, we introduce a hierarchy of graph classes within the class of Tinhofer graphs. We call a graph $G$ $k$-Tinhofer if, after $k$ rounds of individualization and refinement, the resulting colored graphs remain isomorphic for every graph $H \cong G$, irrespective of the choices of vertices made during individualization. Arvind et al. (2017) studied a hierarchy of graph classes motivated by color refinement - discrete, amenable, Tinhofer, and refinable graphs. We show that the $k$-Tinhofer hierarchy lies between the class of all graphs and Tinhofer graphs, with refinable graphs coinciding with the first level of the hierarchy. We obtain two characterizations of $k$-Tinhofer graphs: an algebraic characterization in terms of orbit partitions induced by pointwise stabilizers of automorphism groups, and a combinatorial characterization in terms of individualization-refinement trees and quotient graphs. For every fixed integer $k \ge 0$, there exist vertex-colored graphs that are $k$-Tinhofer but not $(k + 1)$-Tinhofer. For every fixed integer $k \ge 0$, the problem of deciding whether a given $k$-Tinhofer graph is ($k + 1$)-Tinhofer is $P$-hard under uniform $\mathsf{AC^0}$ many-one reductions. We show that testing isomorphism between an $(n - k)$-Tinhofer graph $G$ and an arbitrary graph $H$ is fixed-parameter tractable with respect to the parameter $k$.
KIO-planner: Attention-Guided Single-Stage Motion Planning with Dual Mapping for UAV Navigation
arXiv:2605.19703v1 Announce Type: new Abstract: Autonomous UAV flight in confined, wall-dense environments requires low-latency and reliable motion planning under strict safety constraints. Traditional optimization-based planners suffer from mapping latency and easily fall into local minima when navigating through dense structural obstacles. Meanwhile, existing end-to-end learning methods struggle to extract fine-grained geometric features from raw depth images and lack hard kinodynamic constraints, leading to unpredictable collisions near walls. To address these issues, we propose KIO-planner, an attention-guided single-stage trajectory planning framework. First, we integrate a Convolutional Block Attention Module (CBAM) into the perception backbone to adaptively focus on critical structural edges and traversable space. Second, we introduce a novel Dual Mapping mechanism--comprising physical bounds activation and a deterministic Geometric Safety Shield in the depth-pixel space--to enforce kinodynamic feasibility and collision-free flight without global map fusion. Extensive high-fidelity simulated experiments demonstrate that KIO-planner enables highly agile navigation at speeds up to 3.0 m/s. Compared to the state-of-the-art baseline, KIO-planner achieves lower inference latency (approximately 24 ms) and generates significantly smoother trajectories, reducing control cost by 28.4%. Most notably, our Dual Mapping substantially increases the worst-case safety margin, measured by minimum distance to obstacles, from 0.48 m to 0.76 m, ensuring fast, smooth, and safer navigation in highly constrained environments.
Observing rurality of a geographical area from road graph geometry -- a qualitative study
arXiv:2601.12006v2 Announce Type: replace Abstract: In this paper we analyze the Finnish road network as a graph in order to measure whether the "rurality" or "urbanity" of an area correlates with local geometrical properties of the graph. Our primary motivation is the observation that the road systems in rural areas look similar to hyperbolic graphs, while in large cities they resemble more the Cayley graph of $\mathbb{Z}^2$. We do not aim for a comprehensive analysis, but rather wish to demonstrate that this observation can be measured and analyzed through looking at various "hyperbolicity measures" of randomly sampled geodesic triangles in the road graph.
EnsemHalDet: Robust VLM Hallucination Detection via Ensemble of Internal State Detectors
arXiv:2604.02784v2 Announce Type: replace Abstract: Vision-Language Models (VLMs) excel at multimodal tasks, but they remain vulnerable to hallucinations that are factually incorrect or ungrounded in the input image. Recent work suggests that hallucination detection using internal representations is more efficient and accurate than approaches that rely solely on model outputs. However, existing internal-representation-based methods typically rely on a single representation or detector, limiting their ability to capture diverse hallucination signals. In this paper, we propose EnsemHalDet, an ensemble-based hallucination detection framework that leverages multiple internal representations of VLMs, including attention outputs and hidden states. EnsemHalDet trains independent detectors for each representation and combines them through ensemble learning. Experimental results across multiple VQA datasets and VLMs show that EnsemHalDet consistently outperforms prior methods and single-detector models in terms of AUC. These results demonstrate that ensembling diverse internal signals significantly improves robustness in multimodal hallucination detection.
RefiningGPT: Specialized language Models for Automated Refinery Unit-level Process Diagram Synthesis
arXiv:2605.19704v1 Announce Type: new Abstract: Applying LLMs to complex industrial processes remains challenging due to the semantic gap between natural language design intents and the rigorous physical logic of engineering. In the field of petroleum refining engineering, a critical bottleneck is the automated synthesis of Unit-level Process Diagrams (UPDs), which serve as the topological bridge connecting abstract requirements to concrete unit operations. In this paper, we propose RefineGPT, a domain-specialized agent for autonomous refinery design.RefineGPT adopts a hierarchical architecture in which a supervised fine-tuned small language model is responsible for selecting units that satisfy design requirements, while a large language model is used to connect these units to generate the final topology. To enable supervised training, we develop a pipeline that extracts latent process motifs from noisy, unstructured legacy topologies and synthesizes high-quality rationale-based Chain-of-Thought (CoT) training data. Empirical validation demonstrates that RefineGPT achieves substantial improvements in topological consistency and chemical engineering feasibility, establishing a high-fidelity pathway for AI-augmented industrial process synthesis.
Whispers of Wealth: Red-Teaming Google's Agent Payments Protocol via Prompt Injection
arXiv:2601.22569v2 Announce Type: replace Abstract: Large language model (LLM) based agents are increasingly used to automate financial transactions, yet their reliance on contextual reasoning exposes payment systems to prompt-driven manipulation. The Agent Payments Protocol (AP2) aims to secure agent-led purchases through cryptographically verifiable mandates, but its practical robustness remains underexplored. In this work, we perform an AI red-teaming evaluation of AP2 and identify vulnerabilities arising from indirect and direct prompt injection. We introduce two attack techniques, the Branded Whisper Attack and the Vault Whisper Attack which manipulate product ranking and extract sensitive user data. Using a functional AP2 based shopping agent built with Gemini-2.5-Flash and the Google ADK framework, we experimentally validate that simple adversarial prompts can reliably subvert agent behavior. Our findings reveal critical weaknesses in current agentic payment architectures and highlight the need for stronger isolation and defensive safeguards in LLM-mediated financial systems.
Motif-Video 2B: Technical Report
arXiv:2604.16503v2 Announce Type: replace Abstract: Training strong video generation models usually requires massive datasets, large parameter counts, and substantial compute. In this work, we ask whether strong text-to-video quality is possible at a much smaller budget: fewer than 10M clips and less than 100,000 H200 GPU hours. Our core claim is that part of the answer lies in how model capacity is organized, not only in how much of it is used. In video generation, prompt alignment, temporal consistency, and fine-detail recovery can interfere with one another when they are handled through the same pathway. Motif-Video 2B addresses this by separating these roles architecturally, rather than relying on scale alone. The model combines two key ideas. First, Shared Cross-Attention strengthens text control when video token sequences become long. Second, a three-part backbone separates early fusion, joint representation learning, and detail refinement. To make this design effective under a limited compute budget, we pair it with an efficient training recipe based on dynamic token routing and early-phase feature alignment to a frozen pretrained video encoder. Our analysis shows that later blocks develop clearer cross-frame attention structure than standard single-stream baselines. On VBench, Motif-Video~2B reaches 83.76\%, surpassing Wan2.1 14B while using 7$\times$ fewer parameters and substantially less training data. These results suggest that careful architectural specialization, combined with an efficiency-oriented training recipe, can narrow or exceed the quality gap typically associated with much larger video models.
What Makes Synthetic Data Effective in Image Segmentation
arXiv:2605.19289v1 Announce Type: new Abstract: Driven by rapid advances in large-scale generative models, synthetic data has emerged as a promising solution for visual understanding. While modern diffusion models achieve remarkable photorealistic image synthesis, their potential in complex visual segmentation tasks remains underexplored. In this work, we conduct a systematic analysis of synthetic images from state-of-the-art diffusion models to uncover the factors governing their utility. In particular, synthetic images characterized by dense scene composition and fine instance fidelity demonstrate distinctive benefits, yielding significantly more discriminative spatial representations. Building on these insights, we propose SENSE, a unified framework that leverages flexible and scalable synthetic data to substantially enhance segmentation performance. Notably, SENSE is model-agnostic, compatible with diverse architectures (e.g., DPT and Mask2Former), and scales effectively across models with varying parameter capacities. Extensive experiments on Cityscapes, COCO, and ADE20K validate the effectiveness and generalization capability of our approach. Code is available at https://github.com/zhang0jhon/SENSE.
Dynamic Model Merging Made Slim
arXiv:2605.18904v1 Announce Type: new Abstract: Model merging enables the reuse of fine-tuned models without joint training or access to original data. Dynamic merging further improves flexibility by selectively activating task-relevant parameters and efficiently composing experts across multiple tasks. However, existing dynamic methods either maintain a full shared model with tiny experts or allocate excessive capacity to experts, leading to suboptimal accuracy--efficiency trade-offs. To address this, we propose DiDi-Merging, a slim dynamic merging framework that leverages differentiable rank allocation to balance shared and expert parameters. By formulating parameter budgeting as differentiable rank optimization in low-rank modules and introducing a data-free refinement step to recover task fidelity, DiDi-Merging matches prior dynamic baselines at only 1.24x the parameters of a single fine-tuned model and surpasses them at 1.4x, substantially more compact than methods requiring > 2x storage. DiDi-Merging applies across vision, language, and multimodal tasks.
Two-Level Sketching Alternating Anderson acceleration for Complex Physics Applications
arXiv:2505.08587v2 Announce Type: replace Abstract: We present a novel two-level sketching extension of the Alternating Anderson-Picard (AAP) method for accelerating fixed-point iterations in challenging single- and multi-physics simulations governed by discretized partial differential equations. Our approach combines a static, physics-based projection that reduces the least-squares problem to the most informative field (e.g., via Schur-complement insight) with a dynamic, algebraic sketching stage driven by a backward stability analysis under Lipschitz continuity. We introduce inexpensive estimators for stability thresholds and cache-aware randomized selection strategies to balance computational cost against memory-access overhead. The resulting algorithm solves reduced least-squares systems in place, minimizes memory footprints, and seamlessly alternates between low-cost Picard updates and Anderson mixing. Implemented in Julia, our two-level sketching AAP achieves up to 50% time-to-solution reductions compared to standard Anderson acceleration-without degrading convergence rates-on benchmark problems including Stokes, p-Laplacian, Bidomain, and Navier-Stokes formulations at varying problem sizes. These results demonstrate the method's robustness, scalability, and potential for integration into high-performance scientific computing frameworks. Our implementation is available open-source in the AAP.jl library.
Executable Boundary Contracts for Sound Event Traces
arXiv:2605.19632v1 Announce Type: new Abstract: Sound event reports often compress timed boundary behavior into frame, segment, or event scores. This paper defines executable boundary contracts for finite sound event traces. The frame fragment is a bounded Boolean fragment embeddable in STL after grid projection. The event layer adds declared interval matching, duration clauses, fragmentation clauses, and obligation restricted vector scoring. The aim is measurement, not a new general temporal logic and not a challenge leaderboard. The artifact evaluates controlled Mini LibriSpeech seeded scenes, MAESTRO Real soundscapes, frozen pretrained timing probes, and an official DCASE 2024 Task 4 baseline track. Across these tracks, standard scores and contract coordinates disagree in interpretable ways. The strongest real corpus finding is that union activity can hide typed boundary failure, while external DCASE outputs provide a class indexed challenge level reference. Code, generated tables, manifests, and Lean checks for the finite frame core are supplied as ancillary material.
Using Longitudinal Strong Focusing Principle to Lower Particle Beam Energy Spread Locally in a Storage Ring
arXiv:2605.19583v1 Announce Type: new Abstract: In this paper, we propose to use longitudinal strong focusing principle to lower particle beam energy spread locally in a storage ring. An example application of the proposed scheme in reversible Echo SSMB for high-power EUV radiation generation is presented. We believe strong focusing in the longitudinal dimension has a wide application potential.
Adaptive Power Iteration Method for Differentially Private PCA
arXiv:2602.11454v3 Announce Type: replace Abstract: We study $\left(\epsilon,\delta\right)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix $A\in\mathbb{R}^{n\times d}$ where each row of $A$ is a data point in $\mathbb{R}^{d}$. Following Dwork-Talwar-Thakurta-Zhang (STOC 2014), we consider the privacy model where neighboring inputs differ by one single row. We give a novel algorithm that achieves beyond-worst-case guarantees for input matrices with low coherence, which is a structural property of matrices in many applications, including but not limited to i.i.d. data. Our algorithm contributes to the extensive literature on private power iteration methods, where we introduce a new filtering technique which adapts to this coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which achieves beyond-worst-case guarantees for the more restrictive privacy model where neighboring inputs differ in one single entry by at most 1.
Set Shaping Theory as a Complementary Payload-Shaping Layer for Steganography
arXiv:2605.19885v1 Announce Type: cross Abstract: This paper studies the use of Set Shaping Theory (SST) as a reversible payload-shaping layer for least significant bit (LSB) image steganography. The proposal is not intended to replace existing steganographic methods or to compete with them as a new embedding scheme. Instead, SST is positioned as a complementary preprocessing stage that makes an existing embedding method easier to apply with lower statistical disturbance. The SST transformation increases the message length by K symbols and is implemented with the approximate and fast transformation algorithm developed by Glen Tankersley. Although the embedded payload is lengthened from N to N+K bits, the selected representation can reduce D_KL(P||Q) and therefore make the subsequent steganographic insertion less detectable under histogram-based criteria. Across 1,800 controlled simulations on four synthetic cover-image models, SST reduced D_KL(P||Q) by an average of 25.16 percent relative to a fair N+K LSB baseline, with a 95 percent confidence interval of +/- 1.22 percent. For K=8, the average reduction reached 42.81 percent. Additional robustness simulations with keyed random embedding paths confirmed the effect across several distances: at K=8, SST reduced KL divergence by 42.44 percent, Jensen-Shannon divergence by 29.62 percent, total variation by 12.41 percent, and symmetric chi-square distance by 28.30 percent. An additional image-based matrix-embedding/STC-like simulation showed that SST also reduces the minimum weighted insertion cost: relative to the unshaped K=0 reference, K=8 reduced the cost by 6.93 percent.
Language Model Memory and Memory Models for Language
arXiv:2602.13466v2 Announce Type: replace Abstract: The ability of machine learning models to store input information in hidden layer vector embeddings, analogous to the concept of `memory', is widely employed but not well characterized. We find that language model embeddings typically contain relatively little input information regardless of data and compute scale during training. In contrast, embeddings from autoencoders trained for input regeneration are capable of nearly perfect memory formation. The substitution of memory embeddings for token sequences leads to substantial computational efficiencies, motivating the introduction of a parallelizable encoder-decoder memory model architecture. Upon causal training these models contain information-poor embeddings incapable of arbitrary information access, but by combining causal and information retention objective functions they learn to form and decode information-rich memories. Training can be further streamlined by freezing a high fidelity encoder followed by a curriculum training approach where decoders first learn to process memories and then learn to additionally predict next tokens. We introduce the perspective that next token prediction training alone is poorly suited for accurate memory formation as the objective itself is non-invertible, motivating the use of combined objective functions for models where the entire input is not exposed.
Trajectory Planning and Control near the Limits: an Open Experimental Benchmark on the RoboRacer Platform
arXiv:2605.19881v1 Announce Type: new Abstract: We present a modular framework to benchmark new and existing methods for trajectory planning and control in high-acceleration maneuvers that push autonomous driving to the limits. Our framework includes time-optimal raceline generation, online time-optimal velocity replanning, geometric path tracking controllers, and a new model-structured neural network (MS-NN) to learn the inverse dynamics for steering control. We deploy our framework on a 1:10-scale RoboRacer platform, using two circuits. Through several ablations with cautious and aggressive racelines, we study the performance of single modules and their combinations. We show that our MS-NN significantly improves tracking accuracy, decreases steering oscillations, and is physically interpretable. Moreover, online velocity replanning improves lap times by compensating for execution errors, and enables the vehicle to safely reach higher speeds and accelerations. To support future research, our code, datasets, videos and results are publicly available at https://roboracer-benchmark.github.io/planning_control_benchmark/.
The Compilability Thresholds of 2-CNF to OBDD
arXiv:2603.15463v2 Announce Type: replace Abstract: We prove the existence of two thresholds regarding the compilability of random 2-CNF formulas to OBDDs. The formulas are drawn from $\mathcal{F}_2(n,\delta n)$, the uniform distribution over all 2-CNFs with $\delta n$ clauses and $n$ variables, with $\delta \geq 0$ a constant. We show that, with high probability, the random 2-CNF admits OBDDs of size polynomial in $n$ if $0 \leq \delta < 1/2$ or if $\delta > 1$. On the other hand, for $1/2 < \delta < 1$, with high probability, the random $2$-CNF admits only OBDDs of size exponential in $n$. It is no coincidence that the two ``compilability thresholds'' are $\delta = 1/2$ and $\delta = 1$. Both are known thresholds for other CNF properties, namely, $\delta = 1$ is the satisfiability threshold for 2-CNF while $\delta = 1/2$ is the treewidth threshold, i.e., the point where the treewidth of the primal graph jumps from constant to linear in $n$ with high probability.
Stone Duality for Monads
arXiv:2603.25710v2 Announce Type: replace Abstract: We introduce a contravariant idempotent adjunction between (i) the category of ranked monads on $\mathsf{Set}$; and (ii) the category of internal categories and internal retrofunctors in the category of locales. The left adjoint takes a monad $T$-viewed as a notion of computation, following Moggi-to its localic behaviour category $\mathsf{LB}T$. This behaviour category is understood as "the universal transition system" for interacting with $T$: its "objects" are states and the "morphisms" are transitions. On the other hand, the right adjoint takes a localic category $\mathsf{LC}$-similarly understood as a transition system-to the monad $\Gamma\mathsf{LC}$ where $(\Gamma\mathsf{LC})A$ is the set of $A$-indexed families of local sections to the source map which jointly partition the locale of objects. The fixed points of this adjunction consist of (i) hyperaffine-unary monads, i.e., those monads where term $t$ admits a read-only operation $\bar{t}$ predicting the output of $t$; and (ii) ample localic categories, i.e., whose source maps are local homeomorphisms and whose locale of objects are strongly zero-dimensional. The hyperaffine-unary monads arise in earlier works by Johnstone and Garner as a syntactic characterization of those monads with Cartesian closed Eilenberg-Moore categories. This equivalence is the Stone duality for monads; so-called because it further restricts to the classical Stone duality by viewing a Boolean algebra $B$ as a monad of $B$-partitions and the corresponding Stone space as a localic category with only identity morphisms.
LLM Agents Make Collective Belief Dynamics Programmable: Challenges and Research Directions
arXiv:2605.19915v1 Announce Type: new Abstract: Classical models of opinion dynamics assume human participants with bounded rationality and limited coordination. The rise of LLM-based agents introduces a qualitative shift: agents can now participate in online discussions at scale, maintain consistent persuasion strategies, and coordinate systematically. This paper argues that LLM agents make collective belief dynamics programmable, enabling deliberate steering of population-level beliefs. We term this emerging problem programmable collective belief control. Through controlled multi-agent simulations, we provide proof-of-concept evidence that coordinated AI agents can induce measurable belief shifts that stabilize within a few interaction rounds. We identify four structural properties (indistinguishability, persistence, contextuality, and configurability) that make detection and defense fundamentally difficult. Based on these findings, we outline a research agenda spanning theoretical foundations for adversarial belief dynamics, operational methods for system-level detection and intervention, and simulation infrastructure for scalable experimentation. Our goal is not to present a complete solution, but to articulate why this problem demands urgent attention and to provide a conceptual foundation for future work.
Navigating the Emotion Tree: Hierarchical Hyperbolic RAG for Multimodal Emotion Recognition
arXiv:2605.18884v1 Announce Type: new Abstract: Multimodal emotion recognition aims to integrate text, audio, and video sources to understand human affective states. Although multimodal large language models excel at multimodal reasoning, they typically treat emotion categories as independent labels, ignoring the rich hierarchical taxonomy of human psychology. Moreover, lacking external contextual knowledge makes them highly susceptible to over-interpreting noisy cues, further complicating fine-grained emotion classification. To address these issues, we propose \textbf{HyperEmo-RAG}, a retrieval-augmented generation framework that leverages a structured emotional knowledge base. Our framework introduces two key innovations. 1) Hierarchical hyperbolic grounding. Recognizing the inherent hierarchical tree structure of emotion taxonomies, we jointly embed hierarchical emotion labels and multimodal samples into a continuous hyperbolic space (Poincar\'e ball) and design a hierarchical beam-search deliberation process that progressively retrieves samples from coarse to fine-grained levels. 2) Structured evidence injection. Based on the retrieved evidence, we construct an evidence graph and inject the structured knowledge as explicit cognitive context into the LLM through a Tree-Aware Attention mechanism and an EmotionGraphFormer, preserving the integrity of graph-structured information. Experiments on multiple datasets demonstrate that HyperEmo-RAG significantly outperforms existing methods.
Enhanced Temperature Sensitivity in Ensemble NV Centers through Improved Optically Detected Magnetic Resonance Spectral Modeling
arXiv:2605.18863v1 Announce Type: new Abstract: Nitrogen-vacancy (NV) center ensembles provide a powerful platform for high-precision temperature sensing, with ongoing efforts to further enhance their measurement performance. In ensemble NV optically detected magnetic resonance (ODMR) spectra, commonly used Lorentzian and Voigt fitting models fail to accurately describe the spectral shape near the resonance frequency, leading to degraded precision in resonance-frequency determination and, consequently, temperature estimation. In this work, we analytically establish a new fitting method, termed dip-peak fitting, for extracting the resonance frequency from ensemble cw-ODMR spectra. Starting from a physical model that describes ensemble cw-ODMR spectra as a convolution of single-NV responses with distributed zero-field splitting and strain, we show that the spectral feature near resonance can be accurately approximated by a single Lorentzian function with a background term. The proposed fitting model reproduces the cw-ODMR spectrum around resonance more faithfully than conventional approaches, enabling faster and more accurate resonance-frequency determination under weaker microwave excitation. Experiments using fluorescent nanodiamond ensembles confirm the robustness and applicability of this method for high-precision temperature sensing.
Revisiting recursive methods for Dyson and Keldysh in NEGF: Part I
arXiv:2605.19910v1 Announce Type: new Abstract: The simulation of quantum transport in nanodevices requires the solution of the Dyson and Keldysh equations, a task dominated by the inversion of massive, block-tridiagonal matrices. While the Recursive Green's Function (RGF) method has long been the standard $O(N)$ solver for quasi-1D systems, its formulation has typically been restricted to sequential execution and nearest-neighbor interactions. In this work, we carefully reformulate RGF through the lens of Domain Decomposition and Schur Complement theory. This allows us to extend the recursive formalism to block $n$-diagonal systems (handling higher-order stencils) and to derive a parallel algorithm, Domain-Decomposition based RGF (DDRGF), which stitches macroscopic domains via reduced interface systems. We explore data dependencies in DDRGF in detail, by means of block-sparse structures and tracing back to the desired output as a block tridiagonal approximation, giving a clear, reproducible and extensible formulation. We validate these algorithms using \texttt{LibNEGF.jl}, a Julia-based implementation, demonstrating that the structural insights of domain decomposition provide a robust pathway for high-performance quantum transport simulations on modern multi-core clusters. The theory presented here lays down the base for tackling the Keldysh problem, to be similarly handled in future stages of our work. Although the target here is the acceleration of kernels in the non-equilibrium Green's function method, the algorithms and the implementations presented can be immediately used in any application involving block $n$-diagonal systems.
Rule-Based Graph Programs Matching the Time Complexity of Imperative Algorithms
arXiv:2501.09144v5 Announce Type: replace Abstract: We report on recent advances in rule-based graph programming, which allow us to match the time complexity of some fundamental imperative graph algorithms. In general, achieving the time complexity of graph algorithms implemented in conventional languages using a rule-based graph-transformation language is challenging due to the cost of graph matching. Previous work demonstrated that with rooted rules, certain algorithms can be implemented in the graph programming language GP 2 such that their runtime matches the time complexity of imperative implementations. However, this required input graphs to have a bounded node degree and (for some algorithms) to be connected. In this paper, we overcome these limitations by enhancing the graph data structure generated by the GP 2 compiler and exploiting the new structure in programs. We present three case studies: the first program checks whether input graphs are connected, the second program checks whether input graphs are acyclic, and the third program solves the single-source shortest-paths problem for graphs with integer edge-weights. The first two programs run in linear time on (possibly disconnected) input graphs with arbitrary node degrees. The third program runs in time $O(nm)$ on arbitrary input graphs, matching the time complexity of imperative implementations of the Bellman-Ford algorithm. For each program, we formally prove its correctness and time complexity, and provide runtime experiments on various graph classes.
Can LLMs Produce Better Object-Oriented Designs than Human-Involved Development?
arXiv:2605.19901v1 Announce Type: new Abstract: Background: Large Language Models (LLMs) are increasingly used for code generation. However, their ability to generate multi-class projects that require object-oriented design (OOD) remains unclear, especially relative to projects developed with human involvement. Aims: The primary objective of this study is to compare OOD quality in projects from three authorship conditions: PreAI (human-involved projects produced before widespread LLM use), PostAI (human-involved projects produced after widespread LLM use), and PureAI (projects generated end-to-end by contemporary LLMs). Method: We conducted a comparative case study on a postgraduate Java assignment. Two offerings of the same assignment were selected as the PreAI and PostAI datasets. PureAI projects were generated using three contemporary LLMs. We analyzed OOD quality using project-level OOD metrics, code smell density, and domain modeling. Results: Relative to human-involved projects, PureAI projects show lower code smell density and generally appear simpler in terms of total size, complexity, and coupling. However, this is consistent with oversimplification, as it is associated with missing abstractions and weaker responsibility separation. PostAI is closer to PureAI than PreAI on many OOD measures and also shows tendencies toward oversimplification. Conclusions: Our findings indicate that appropriate human guidance on object-oriented decomposition and responsibility assignment remains important when LLMs are used for object-oriented design.
Fair-Aurora: Comparing Fairness Strategies for Reinforcement Learning-Based Congestion Control in Multi-Flow Environments
arXiv:2605.19909v1 Announce Type: new Abstract: Reinforcement learning (RL) has emerged as a promising paradigm for Internet congestion control, achieving higher link utilization than classical heuristics. However, RL-based controllers trained in single-flow environments are not guaranteed to share bandwidth equitably when deployed in multi-flow networks. This paper investigates the fairness properties of Aurora~\cite{jay2019aurora}, a state-of-the-art deep RL congestion controller, and evaluates three post-hoc fairness strategies that preserve Aurora's RL architecture: \emph{reward shaping} (Strategy~A), \emph{observation augmentation} (Strategy~B), and \emph{loss-sensitivity tuning} (Strategy~C). Using a custom shared-bottleneck simulator and Jain's fairness index as the primary metric, we find that modest reward shaping achieves the best fairness while preserving aggregate throughput. All strategies maintain the total bandwidth budget with fairness being achieved through redistribution, not reduction. Beyond the 2-flow homogeneous setting, an extended evaluation across mixed Aurora--CUBIC competition and dynamic flow entry/exit scenarios shows that Strategy~C's loss-sensitivity emerges as the most TCP-friendly mechanism, while Strategy~B is the most stable through dynamic flow-set changes.