Search

Quantum PCP conjecture is one of the most influential open problems in quantum complexity theory, which states that approximating the ground state energy for a sparse local Hamiltonian upto a constant is QMA-complete. However, even though the problem remains unsolved, weaker versions of it-such as the NLTS [FH13, ABN22] and NLSS [GG22] conjectures-have surfaced in the hope of providing evidence for QPCP. While the NLTS hamiltonians were first constructed in[ABN22], NLSS conjecture still remains unsolved. Weaker versions of the NLSS conjecture were addressed in [CCNN23, CCNN24], demonstrating that Clifford and almost-Clifford states-a subclass of sampleable states-have a lower energy bound on Hamiltonians prepared by conjugating the NLTS Hamiltonians from [ABN22]. In similar spirit, we construct a class of fermionic Hamilltonians for which energy of Gaussian states, a subclass of sampleable fermionic states, is bounded below by a constant. We adapt the technique used in [CCNN23] to our context., Comment: This work is an extension over Fermionic NLTS Hamiltonians

In this paper, we investigate the general properties and structure of $C^*$-extreme points within the $C^*$-convex set $\mathrm{UCP}(\mathcal{A},B(\mathcal{H}))$ of all unital completely positive (UCP) maps from a unital real $C^*$-algebra $\mathcal{A}$ to the algebra $B(\mathcal{H})$ of all bounded real linear maps on a real Hilbert space $\mathcal{H}$. We analyze the differences in the structure of $C^*$-extreme points between the real and complex $C^*$-algebra cases. In particular, we show that the necessary and sufficient conditions for a UCP map between matrix algebras to be a $C^*$-extreme point are identical in both the real and complex matrix algebra cases. We also observe significant differences in the structure of $C^*$-extreme points when $\mathcal{A}$ is a commutative real $C^*$-algebra compared to when $\mathcal{A}$ is a commutative complex $C^*$-algebra. We provide a complete classification of the $C^*$-extreme points of $\mathrm{UCP}(\mathcal{A},B(\mathcal{H}))$, where $\mathcal{A}$ is a unital commutative real $C^*$-algebra and $\mathcal{H}$ is a finite-dimensional real Hilbert space. As an application, we classify all $C^*$-extreme points in the $C^*$-convex set of all contractive skew-symmetric real matrices in $M_n(\mathbb{R})$.

The high-dimensional basis of orbital angular momentum (OAM) has several added and unique advantages for photonics quantum technologies compared to the polarization basis, which is only two-dimensional. However, one of the major roadblocks in implementing OAM-based applications with their full potentials is the absence of an ideal OAM-mode detector. Despite the plethora of efforts in the last three decades, currently, there is no OAM detector that can detect a broad OAM-mode spectrum, has uniform detection-efficiency over all the modes, measures the true spectrum, and works for an arbitrary quantum state without the need for any prior information. In this article, we experimentally demonstrate just such an OAM detector. We report detection of pure and mixed OAM states with fidelities more than 98% and with measurement times of only a few minutes for dimensionalities up to 100. We expect our work to substantially boost the OAM-based photonics quantum technology efforts., Comment: 40 pages (Main text 26 pages, Supplementary Material 14 pages), 13 figures

Remote magnetic sensing can be used to monitor the position of objects in real-time, enabling ground transport monitoring, underground infrastructure mapping and hazardous detection. However, magnetic signals are typically weak and complex, requiring sophisticated physical models to analyze them and a detailed knowledge of the system under study, factors that are frequently unavailable. In this work, we provide a solution to these limitations by demonstrating a Machine Learning (ML) method that can be trained exclusively on experimental data, without the need of any physical model, to predict the position of a magnetic target in real-time. The target can be any object with a magnetic signal above the floor noise, and in this case we use a quantum diamond magnetometer to track variations of few hundreds of nanoteslas produced by an elevator moving along a single axis. The one-dimensional movement is a simple yet challenging scenario, resembling realistic environments such as high buildings, tunnels or train circuits, and is the first step towards building broader applications. Our ML algorithm can be trained in approximately 40 min, achieving over 80% accuracy in predicting the target's position at a rate of 10 Hz, for a positional error tolerance of 30 cm, which is a precise distance compared to the 4-meter spacing between parking levels. Our results open up the possibility to apply this ML method more generally for real-time monitoring of magnetic objects, which will broaden the scope of magnetic detection applications., Comment: Keywords: Machine Learning, Supervised training, Object monitoring, Quantum diamond magnetometry, NV centers. Content: Main text (34 pages) including 6 figures; Supplementary Information (44 pages) including 22 figures

Tungsten monophosphide (WP) has been reported to superconduct below 0.8 K, and theoretical work has predicted an unconventional Cooper pairing mechanism. Here we present data for WP single crystals grown by means of chemical vapor transport (CVT) of WO3, P, and I2. In comparison to synthesis using WP powder as a starting material, this technique results in samples with substantially decreased low-temperature scattering and favors a more three dimensional morphology. We also find that the resistive superconducting transitions in these samples begin above 1 K. Variation in Tc is often found in strongly correlated superconductors, and its presence in WP could be the result of influence from a competing order and/or a non s-wave gap., Comment: 8 pages, 5 figures

However, real-world data often exhibit complex local structures that can be challenging for single-model approaches with a smooth global manifold in the embedding space to unravel. In this work, we conjecture that in the latent space of these large language models, the embeddings live in a local manifold structure with different dimensions depending on the perplexities and domains of the input data, commonly referred to as a Stratified Manifold structure, which in combination form a structured space known as a Stratified Space. To investigate the validity of this structural claim, we propose an analysis framework based on a Mixture-of-Experts (MoE) model where each expert is implemented with a simple dictionary learning algorithm at varying sparsity levels. By incorporating an attention-based soft-gating network, we verify that our model learns specialized sub-manifolds for an ensemble of input data sources, reflecting the semantic stratification in LLM embedding space. We further analyze the intrinsic dimensions of these stratified sub-manifolds and present extensive statistics on expert assignments, gating entropy, and inter-expert distances. Our experimental results demonstrate that our method not only validates the claim of a stratified manifold structure in the LLM embedding space, but also provides interpretable clusters that align with the intrinsic semantic variations of the input data.

Imposing an effective structural assumption on neural network weight matrices has been the major paradigm for designing Parameter-Efficient Fine-Tuning (PEFT) systems for adapting modern large pre-trained models to various downstream tasks. However, low rank based adaptation has become increasingly challenging due to the sheer scale of modern large language models. In this paper, we propose an effective kernelization to further reduce the number of parameters required for adaptation tasks. Specifically, from the classical idea in numerical analysis regarding matrix Low-Separation-Rank (LSR) representations, we develop a kernel using this representation for the low rank adapter matrices of the linear layers from large networks, named the Low Separation Rank Adaptation (LSR-Adapt) kernel. With the ultra-efficient kernel representation of the low rank adapter matrices, we manage to achieve state-of-the-art performance with even higher accuracy with almost half the number of parameters as compared to conventional low rank based methods. This structural assumption also opens the door to further GPU-side optimizations due to the highly parallelizable nature of Kronecker computations.

Nearest neighbor search is a fundamental data structure problem with many applications in machine learning, computer vision, recommendation systems and other fields. Although the main objective of the data structure is to quickly report data points that are closest to a given query, it has long been noted (Carbonell and Goldstein, 1998) that without additional constraints the reported answers can be redundant and/or duplicative. This issue is typically addressed in two stages: in the first stage, the algorithm retrieves a (large) number $r$ of points closest to the query, while in the second stage, the $r$ points are post-processed and a small subset is selected to maximize the desired diversity objective. Although popular, this method suffers from a fundamental efficiency bottleneck, as the set of points retrieved in the first stage often needs to be much larger than the final output. In this paper we present provably efficient algorithms for approximate nearest neighbor search with diversity constraints that bypass this two stage process. Our algorithms are based on popular graph-based methods, which allows us to "piggy-back" on the existing efficient implementations. These are the first graph-based algorithms for nearest neighbor search with diversity constraints. For data sets with low intrinsic dimension, our data structures report a diverse set of $k$ points approximately closest to the query, in time that only depends on $k$ and $\log \Delta$, where $\Delta$ is the ratio of the diameter to the closest pair distance in the data set. This bound is qualitatively similar to the best known bounds for standard (non-diverse) graph-based algorithms. Our experiments show that the search time of our algorithms is substantially lower than that using the standard two-stage approach.

This paper proposes a new compression paradigm -- Guaranteed Conditional Diffusion with Tensor Correction (GCDTC) -- for lossy scientific data compression. The framework is based on recent conditional diffusion (CD) generative models, and it consists of a conditional diffusion model, tensor correction, and error guarantee. Our diffusion model is a mixture of 3D conditioning and 2D denoising U-Net. The approach leverages a 3D block-based compressing module to address spatiotemporal correlations in structured scientific data. Then, the reverse diffusion process for 2D spatial data is conditioned on the ``slices'' of content latent variables produced by the compressing module. After training, the denoising decoder reconstructs the data with zero noise and content latent variables, and thus it is entirely deterministic. The reconstructed outputs of the CD model are further post-processed by our tensor correction and error guarantee steps to control and ensure a maximum error distortion, which is an inevitable requirement in lossy scientific data compression. Our experiments involving two datasets generated by climate and chemical combustion simulations show that our framework outperforms standard convolutional autoencoders and yields competitive compression quality with an existing scientific data compression algorithm.

Estimating treatment effects in time series data presents a significant challenge, especially when the control group is always unobservable. For example, in analyzing the effects of Christmas on retail sales, we lack direct observation of what would have occurred in late December without the Christmas impact. To address this, we try to recover the control group in the event period while accounting for confounders and temporal dependencies. Experimental results on the M5 Walmart retail sales data demonstrate robust estimation of the potential outcome of the control group as well as accurate predicted holiday effect. Furthermore, we provided theoretical guarantees for the estimated treatment effect, proving its consistency and asymptotic normality. The proposed methodology is applicable not only to this always-missing control scenario but also in other conventional time series causal inference settings.

Isometric tensor networks in two dimensions enable efficient and accurate study of quantum many-body states, yet the effect of the isometric restriction on the represented quantum states is not fully understood. We address this question in two main contributions. First, we introduce an improved variant of isometric network states (isoTNS) in two dimensions, where the isometric arrows on the columns of the network alternate between pointing upward and downward, hence the name alternating isometric tensor network states. Second, we introduce a numerical tool -- isometric Gaussian fermionic TNS (isoGfTNS) -- that incorporates isometric constraints into the framework of Gaussian fermionic tensor network states. We demonstrate in numerous ways that alternating isoTNS represent many-body ground states of two-dimensional quantum systems significantly better than the original isoTNS. First, we show that the entanglement in an isoTNS is mediated along the isometric arrows and that alternating isoTNS mediate entanglement more efficiently than conventional isoTNS. Second, alternating isoTNS correspond to a deeper, thus more representative, sequential circuit construction of depth $\mathcal{O}(L_x \cdot L_y)$ compared to the original isoTNS of depth $\mathcal{O}(L_x + L_y)$. Third, using the Gaussian framework and gradient-based energy minimization, we provide numerical evidences of better bond-dimension scaling and variational energy of alternating isoGfTNS for ground states of various free fermionic models, including the Fermi surface, the band insulator, and the $p_x + ip_y$ mean-field superconductor. Finally, we find improved performance of alternating isoTNS as compared to the original isoTNS for the ground state energy of the (interacting) transverse field Ising model.

Autonomous agents are often required to plan under multiple objectives whose preference ordering varies based on context. The agent may encounter multiple contexts during its course of operation, each imposing a distinct lexicographic ordering over the objectives, with potentially different reward functions associated with each context. Existing approaches to multi-objective planning typically consider a single preference ordering over the objectives, across the state space, and do not support planning under multiple objective orderings within an environment. We present Contextual Lexicographic Markov Decision Process (CLMDP), a framework that enables planning under varying lexicographic objective orderings, depending on the context. In a CLMDP, both the objective ordering at a state and the associated reward functions are determined by the context. We employ a Bayesian approach to infer a state-context mapping from expert trajectories. Our algorithm to solve a CLMDP first computes a policy for each objective ordering and then combines them into a single context-aware policy that is valid and cycle-free. The effectiveness of the proposed approach is evaluated in simulation and using a mobile robot., Comment: 9 pages, 5 figures, 2 tables, To appear in Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) 2025

In this article, we have proposed Rankine-Hugoniot (RH) boundary conditions at the normal shock front, which is passing through the condensed material. These RH conditions are quite general, and their convenient forms for the particle velocity, mass density, pressure, and temperature have been presented in terms of the upstream Mach number and the material parameters for the weak and the strong shocks, respectively. Finally, the effects on the mechanical quantities of the shock-compressed materials, e.g., titanium Ti6Al4V, stainless steel 304, aluminum 6061-T6, etc., have been discussed., Comment: 10 pages, 3 figures and 2 tables

HCI is future-oriented by nature: it explores new human--technology interactions and applies the findings to promote and shape vital visions of society. Still, the visions of futures in HCI publications seem largely implicit, techno-deterministic, narrow, and lacking in roadmaps and attention to uncertainties. A literature review centered on this problem examined futuring and its forms in the ACM Digital Library's most frequently cited HCI publications. This analysis entailed developing the four-category framework SPIN, informed by futures studies literature. The results confirm that, while technology indeed drives futuring in HCI, a growing body of HCI research is coming to challenge techno-centric visions. Emerging foci of HCI futuring demonstrate active exploration of uncertainty, a focus on human experience, and contestation of dominant narratives. The paper concludes with insight illuminating factors behind techno-centrism's continued dominance of HCI discourse, as grounding for five opportunities for the field to expand its contribution to futures and anticipation research., Comment: CHI Conference on Human Factors in Computing Systems (CHI '25), April 26-May 1, 2025, Yokohama, Japan

Non-native speakers with limited vocabulary often struggle to name specific objects despite being able to visualize them, e.g., people outside Australia searching for numbats. Further, users may want to search for such elusive objects with difficult-to-sketch interactions, e.g., numbat digging in the ground. In such common but complex situations, users desire a search interface that accepts composite multimodal queries comprising hand-drawn sketches of difficult-to-name but easy-to-draw objects and text describing difficult-to-sketch but easy-to-verbalize object attributes or interaction with the scene. This novel problem statement distinctly differs from the previously well-researched TBIR (text-based image retrieval) and SBIR (sketch-based image retrieval) problems. To study this under-explored task, we curate a dataset, CSTBIR (Composite Sketch+Text Based Image Retrieval), consisting of approx. 2M queries and 108K natural scene images. Further, as a solution to this problem, we propose a pretrained multimodal transformer-based baseline, STNET (Sketch+Text Network), that uses a hand-drawn sketch to localize relevant objects in the natural scene image, and encodes the text and image to perform image retrieval. In addition to contrastive learning, we propose multiple training objectives that improve the performance of our model. Extensive experiments show that our proposed method outperforms several state-of-the-art retrieval methods for text-only, sketch-only, and composite query modalities. We make the dataset and code available at our project website., Comment: Accepted at AAAI 2024, 9 pages. Project Website: https://vl2g.github.io/projects/cstbir

Recently, Freedman et al. (2024) report agreement of distances derived from the Tip of the Red Giant Branch (TRGB) and the J-Region Asymptotic Giant Branch (JAGB) at the 1$\%$ level for both nearby galaxies with ground-based imaging (0.5-4 Mpc) as well distant galaxies with JWST imaging (7-23 Mpc). Here we compare the same ground-based JAGB distances to uniformly reduced space-based optical TRGB distances from the Hubble Space Telescope (HST). We uncover a significant offset between these two distance scales of $\Delta\mu$ = 0.17 $\pm$ 0.04 (stat) $\pm$ 0.06 (sys) mag (9$\%$ in distance), with the HST TRGB distances being further. Inspections of the HST color-magnitude diagrams make a compelling case that the issue lies in the underlying JAGB distances. The source of the disagreement may lie with the lower resolution or photometric calibration of the ground-based near-infrared data, a contrast to the general agreement found between JWST JAGB and other space-based, second-rung distance indicators (Cepheids, Miras, TRGB) presented within Riess et al. (2024). High-resolution, near-infrared observations from an ongoing HST program will enable the simultaneous measurement of Cepheid, JAGB, and TRGB distances in four of these nearby galaxies and allow us to investigate whether the discrepancy noted here is due to ground-based observational systematics, or something intrinsic to the JAGB method relevant for this particular sample. A resolution of this discrepancy is required if the JAGB is to be used to determine a highly precise local value of the Hubble constant., Comment: Primary result shown in Figure 1. To be submitted to the AAS Journals within two weeks from arXiv posting. Comments welcome and appreciated

The materials science community seeks to support the FAIR principles for computational simulation research. The MatCore Project was recently launched to address this need, with the goal of developing an overall metadata framework and accompanying guidelines. This paper reports on the MatCore goals and overall progress. Historical background context is provided, including a review of the principles underlying successful core metadata standards. The paper also presents selected MatCore examples and discusses future plans., Comment: 11 pages, 5 figures, Conference Paper

Cloud systems are the backbone of today's computing industry. Yet, these systems remain complicated to design, build, operate, and improve. All these tasks require significant manual effort by both developers and operators of these systems. To reduce this manual burden, in this paper we set forth a vision for achieving holistic automation, intent-based system design and operation. We propose intent as a new abstraction within the context of system design and operation. Intent encodes the functional and operational requirements of the system at a high-level, which can be used to automate design, implementation, operation, and evolution of systems. We detail our vision of intent-based system design, highlight its four key components, and provide a roadmap for the community to enable autonomous systems.

For sink-free orientations in graphs of minimum degree at least $3$, we show that there is a deterministic approximate counting algorithm that runs in time $O((n^{73}/\varepsilon^{72})\log(n/\varepsilon))$, a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time $O((n/\varepsilon)^2\log(n/\varepsilon))$, where $n$ denotes the number of vertices of the input graph and $0<\varepsilon<1$ is the desired accuracy. All three algorithms are based on a local implementation of the sink popping method (Cohn, Pemantle, and Propp, 2002) under the partial rejection sampling framework (Guo, Jerrum, and Liu, 2019)., Comment: 15 pages, 1 figure. v2: updated discussion

The advances in digital tools have led to the rampant spread of misinformation. While fact-checking aims to combat this, manual fact-checking is cumbersome and not scalable. It is essential for automated fact-checking to be efficient for aiding in combating misinformation in real-time and at the source. Fact-checking pipelines primarily comprise a knowledge retrieval component which extracts relevant knowledge to fact-check a claim from large knowledge sources like Wikipedia and a verification component. The existing works primarily focus on the fact-verification part rather than evidence retrieval from large data collections, which often face scalability issues for practical applications such as live fact-checking. In this study, we address this gap by exploring various methods for indexing a succinct set of factual statements from large collections like Wikipedia to enhance the retrieval phase of the fact-checking pipeline. We also explore the impact of vector quantization to further improve the efficiency of pipelines that employ dense retrieval approaches for first-stage retrieval. We study the efficiency and effectiveness of the approaches on fact-checking datasets such as HoVer and WiCE, leveraging Wikipedia as the knowledge source. We also evaluate the real-world utility of the efficient retrieval approaches by fact-checking 2024 presidential debate and also open source the collection of claims with corresponding labels identified in the debate. Through a combination of indexed facts together with Dense retrieval and Index compression, we achieve up to a 10.0x speedup on CPUs and more than a 20.0x speedup on GPUs compared to the classical fact-checking pipelines over large collections., Comment: Accepted to ECIR 2025, 15 pages

Post-training quantization (PTQ) is a promising approach to reducing the storage and computational requirements of large language models (LLMs) without additional training cost. Recent PTQ studies have primarily focused on quantizing only weights to sub-8-bits while maintaining activations at 8-bits or higher. Accurate sub-8-bit quantization for both weights and activations without relying on quantization-aware training remains a significant challenge. We propose a novel quantization method called block clustered quantization (BCQ) wherein each operand tensor is decomposed into blocks (a block is a group of contiguous scalars), blocks are clustered based on their statistics, and a dedicated optimal quantization codebook is designed for each cluster. As a specific embodiment of this approach, we propose a PTQ algorithm called Locally-Optimal BCQ (LO-BCQ) that iterates between the steps of block clustering and codebook design to greedily minimize the quantization mean squared error. When weight and activation scalars are encoded to W4A4 format (with 0.5-bits of overhead for storing scaling factors and codebook selectors), we advance the current state-of-the-art by demonstrating <1% loss in inference accuracy across several LLMs and downstream tasks.

The J-region Asymptotic Giant Branch (JAGB) is an overdensity of stars in the near-infrared, attributed to carbon-rich asymptotic giant branch stars, and recently used as a standard candle for measuring extragalactic distances and the Hubble constant. Using JWST in Cycle 2, we extend JAGB measurements to 6 hosts of 9 Type Ia supernovae (SNe Ia) (NGC 2525, NGC 3147, NGC 3370, NGC 3447, NGC 5468, and NGC 5861), with two at $D \sim 40$ Mpc, all calibrated by the maser host NGC 4258. We investigate the effects of incompleteness and find that we are unable to recover a robust JAGB measurement in one of the two most distant hosts at $R \sim 40$ Mpc, NGC 3147. We compile all JWST JAGB observations in SNe Ia hosts, 15 galaxies hosting 18 SNe Ia, from the SH0ES and CCHP programs and employ all literature measures (mode, mean, median, model). We find no significant mean difference between these distances and those from HST Cepheids, $-0.03\pm0.02$ (stat) $\pm$ 0.05 (sys) mag. We find a difference of 0.11 $\pm$ 0.02 mag between JAGB mode measurements in the CCHP analyses of two fields in NGC 4258, a feature also seen in two SH0ES fields (see field-to-field variations in Li et al. 2024a), indicating significant field-to-field variation of JAGB measurements in NGC 4258 which produce a large absolute calibration uncertainty. Variations are also seen in the shape of the JAGB LF across galaxies so that different measures produce different values of the Hubble constant. We look for but do not (yet) find a standardizing relation between JAGB LF skew or color dependence and the apparent variation. Using the middle result of all JAGB measures to calibrate SNe Ia yields a Hubble constant of $H_0$ = 73.3 $\pm$ 1.4 (stat) $\pm$ 2.0 (sys) km/s/Mpc with the systematic dominated by apparent differences across NGC 4258 calibrating fields or their measures., Comment: 29 pages, 18 figures, 7 tables, submitted to ApJ

This work employs the quantum extremal surface framework to compute the Page curve for black holes corrected by non-extensive entropy. The entropy of Hawking radiation increases linearly with time, leading to the persistence of the information paradox for non-extensive entropy-corrected black holes. At late time, we extremize the generalized entropy functional; incorporating contributions from both matter and the quantum extremal island, we establish that the entanglement entropy of Hawking radiation saturates to the non-extensive extension of the Bekenstein-Hawking entropy. Finally, we study the dependence of non-extensive parameters on the Page time.

In this article, we present a description of the behaviour of shock-compressed solid materials following the Geometrical Shock Dynamics (GSD) theory. GSD has been successfully applied to various gas dynamics problems, and here we have employed it to investigate the propagation of cylindrically and spherically symmetric converging shock waves in solid materials. The analytical solution of shock dynamics equations has been obtained in strong-shock limit, assuming the solid material to be homogeneous and isotropic and obeying the Mie-Gruneisen equation of state. The non-dimensional expressions are obtained for the velocity of shock, the pressure, the mass density, the particle velocity, the temperature, the speed of sound, the adiabatic bulk modulus, and the change-in-entropy behind the strong converging shock front. The influences as a result of changes in (i) the propagation distance r from the axis or centre (r=0) of convergence, (ii) the Gruneisen parameter, and (iii) the material parameter are explored on the shock velocity and the domain behind the converging shock front. The results show that as the shock focuses at the axis or origin, the shock velocity, the pressure, the temperature, and the change-in-entropy increase in the shock-compressed titanium Ti6Al4V, stainless steel 304, aluminum 6061-T6, etc., Comment: 14pages, 2figures

We derive asymptotically precise expressions for test and train errors of denoising score matching (DSM) in generative diffusion models. The score function is parameterized by random features neural networks, with the target distribution being $d$-dimensional standard Gaussian. We operate in a regime where the dimension $d$, number of data samples $n$, and number of features $p$ tend to infinity while keeping the ratios $\psi_n=\frac{n}{d}$ and $\psi_p=\frac{p}{d}$ fixed. By characterizing the test and train errors, we identify regimes of generalization and memorization in diffusion models. Furthermore, our work sheds light on the conditions enhancing either generalization or memorization. Consistent with prior empirical observations, our findings indicate that the model complexity ($p$) and the number of noise samples per data sample ($m$) used during DSM significantly influence generalization and memorization behaviors., Comment: 8 pages

We present a class of diffusion-based algorithms to draw samples from high-dimensional probability distributions given their unnormalized densities. Ideally, our methods can transport samples from a Gaussian distribution to a specified target distribution in finite time. Our approach relies on the stochastic interpolants framework to define a time-indexed collection of probability densities that bridge a Gaussian distribution to the target distribution. Subsequently, we derive a diffusion process that obeys the aforementioned probability density at each time instant. Obtaining such a diffusion process involves solving certain Hamilton-Jacobi-Bellman PDEs. We solve these PDEs using the theory of forward-backward stochastic differential equations (FBSDE) together with machine learning-based methods. Through numerical experiments, we demonstrate that our algorithm can effectively draw samples from distributions that conventional methods struggle to handle., Comment: 8 pages

We analyze the time reversed dynamics of generative diffusion models. If the exact empirical score function is used in a regime of large dimension and exponentially large number of samples, these models are known to undergo transitions between distinct dynamical regimes. We extend this analysis and compute the transitions for an analytically tractable manifold model where the statistical model for the data is a mixture of lower dimensional Gaussians embedded in higher dimensional space. We compute the so-called speciation and collapse transition times, as a function of the ratio of manifold-to-ambient space dimensions, and other characteristics of the data model. An important tool used in our analysis is the exact formula for the mutual information (or free energy) of Generalized Linear Models.

The success of deep reinforcement learning (DRL) relies on the availability and quality of training data, often requiring extensive interactions with specific environments. In many real-world scenarios, where data collection is costly and risky, offline reinforcement learning (RL) offers a solution by utilizing data collected by domain experts and searching for a batch-constrained optimal policy. This approach is further augmented by incorporating external data sources, expanding the range and diversity of data collection possibilities. However, existing offline RL methods often struggle with challenges posed by non-matching data from these external sources. In this work, we specifically address the problem of source-target domain mismatch in scenarios involving mixed datasets, characterized by a predominance of source data generated from random or suboptimal policies and a limited amount of target data generated from higher-quality policies. To tackle this problem, we introduce Transition Scoring (TS), a novel method that assigns scores to transitions based on their similarity to the target domain, and propose Curriculum Learning-Based Trajectory Valuation (CLTV), which effectively leverages these transition scores to identify and prioritize high-quality trajectories through a curriculum learning approach. Our extensive experiments across various offline RL methods and MuJoCo environments, complemented by rigorous theoretical analysis, demonstrate that CLTV enhances the overall performance and transferability of policies learned by offline RL algorithms., Comment: Accepted at AAMAS 2025

Computer programming textbooks and software documentations often contain flowcharts to illustrate the flow of an algorithm or procedure. Modern OCR engines often tag these flowcharts as graphics and ignore them in further processing. In this paper, we work towards making flowchart images machine-interpretable by converting them to executable Python codes. To this end, inspired by the recent success in natural language to code generation literature, we present a novel transformer-based framework, namely FloCo-T5. Our model is well-suited for this task,as it can effectively learn semantics, structure, and patterns of programming languages, which it leverages to generate syntactically correct code. We also used a task-specific pre-training objective to pre-train FloCo-T5 using a large number of logic-preserving augmented code samples. Further, to perform a rigorous study of this problem, we introduce theFloCo dataset that contains 11,884 flowchart images and their corresponding Python codes. Our experiments show promising results, and FloCo-T5 clearly outperforms related competitive baselines on code generation metrics. We make our dataset and implementation publicly available., Comment: Published at: ICDAR 2023, Project Page: https://vl2g.github.io/projects/floco/

We examine two-player games over finite weighted graphs with quantitative (mean-payoff or energy) objective, where one of the players additionally needs to satisfy a fairness objective. The specific fairness we consider is called 'strong transition fairness', given by a subset of edges of one of the players, which asks the player to take fair edges infinitely often if their source nodes are visited infinitely often. We show that when fairness is imposed on player 1, these games fall within the class of previously studied omega-regular mean-payoff and energy games. On the other hand, when the fairness is on player 2, to the best of our knowledge, these games have not been previously studied. We provide gadget-based algorithms for fair mean-payoff games where fairness is imposed on either player, and for fair energy games where the fairness is imposed on player 1. For all variants of fair mean-payoff and fair energy (under unknown initial credit) games, we give pseudo-polynomial algorithms to compute the winning regions of both players. Additionally, we analyze the strategy complexities required for these games. Our work is the first to extend the study of strong transition fairness, as well as gadget-based approaches, to the quantitative setting. We thereby demonstrate that the simplicity of strong transition fairness, as well as the applicability of gadget-based techniques, can be leveraged beyond the omega-regular domain., Comment: This is an extended version of the same-titled paper accepted to FoSSaCS 2025

Given a graph $G$ and a set $S \subseteq V(G)$, we say that $S$ is $\Delta$-convex if the neighborhood of every vertex not in $S$ is an independent set. A collection ${\cal V} = (V_1, V_2, \ldots , V_p)$ of convex sets of $G$ is a convex $p$-cover if $V(G) = \underset{1 \leq i \leq p}{\bigcup} V_i$ and $V_i \nsubseteq {\underset{1 \leq j \leq p, j\ne i}{\bigcup}} V_j$ for $i \in \{1, \ldots, p\}$. If the convex sets of ${\cal V}$ are pairwise disjoint, ${\cal V}$ is a convex $p$-partition of $V(G)$. The convex cover number $\phi_c(G)$ (the convex partition number $\Theta_c(G)$) of a graph $G$ is the least integer $p \geq 2$ for which $G$ has a convex $p$-cover (convex $p$-partition). In this work, we prove that the {\sc Convex p-cover} and {\sc Convex p-Partition} problems are \NP-complete for any fixed $p \ge 4$ in $\Delta$-convexity. Furthermore, for the three standard graph products, namely, the Cartesian, strong and lexicographic products, we determine these parameters for some cases and present bounds for others.

Ancestral inference for branching processes in random environments involves determining the ancestor distribution parameters using the population sizes of descendant generations. In this paper, we introduce a new methodology for ancestral inference utilizing the generalized method of moments. We demonstrate that the estimator's behavior is critically influenced by the coefficient of variation of the environment sequence. Furthermore, despite the process's evolution being heavily dependent on the offspring means of various generations, we show that the joint limiting distribution of the ancestor and offspring estimators of the mean, under appropriate centering and scaling, decouple and converge to independent Gaussian random variables when the ratio of the number of generations to the logarithm of the number of replicates converges to zero. Additionally, we provide estimators for the limiting variance and illustrate our findings through numerical experiments and data from Polymerase Chain Reaction experiments and COVID-19 data.

The cosmic microwave background (CMB) experiments have reached an era of unprecedented precision and complexity. Aiming to detect the primordial B-mode polarization signal, these experiments will soon be equipped with $10^{4}$ to $10^{5}$ detectors. Consequently, future CMB missions will face the substantial challenge of efficiently processing vast amounts of raw data to produce the initial scientific outputs - the sky maps - within a reasonable time frame and with available computational resources. To address this, we introduce \texttt{BrahMap}, a new map-making framework that will be scalable across both CPU and GPU platforms. Implemented in C++ with a user-friendly Python interface for handling sparse linear systems, \texttt{BrahMap} employs advanced numerical analysis and high-performance computing techniques to maximize the use of super-computing infrastructure. This work features an overview of the \texttt{BrahMap}'s capabilities and preliminary performance scaling results, with application to a generic CMB polarization experiment., Comment: Submitted to 33rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP 2025)

Let $G = (V, E)$ be a simple undirected graph. A set $C \subseteq V(G)$ is weakly convex of graph $G$ if for every two vertices $u,v\in G$, there exists a $u-v$ geodesic whose vertices are in $C$. A set $C \subseteq V$ is an outer-weakly convex dominating set if it is dominating set and every vertex not in $C$ is adjacent to some vertex in $C$ and a set $V(G)\setminus C$ is weakly convex. The outer-weakly convex domination number of graph $G$, denoted by $\widetilde{ \gamma}_{wcon}(G)$, is the minimum cardinality of an outer-weakly convex dominating vertex set of graph $G$. In this paper, we determined the outer-weakly convex domination number of two graphs under the cartesian, strong and lexicographic products, and discuss some important combinatorial findings.

Dynamic Graph Neural Networks (DGNNs) have gained widespread attention due to their applicability in diverse domains such as traffic network prediction, epidemiological forecasting, and social network analysis. In this paper, we present ReInc, a system designed to enable efficient and scalable training of DGNNs on large-scale graphs. ReInc introduces key innovations that capitalize on the unique combination of Graph Neural Networks (GNNs) and Recurrent Neural Networks (RNNs) inherent in DGNNs. By reusing intermediate results and incrementally computing aggregations across consecutive graph snapshots, ReInc significantly enhances computational efficiency. To support these optimizations, ReInc incorporates a novel two-level caching mechanism with a specialized caching policy aligned to the DGNN execution workflow. Additionally, ReInc addresses the challenges of managing structural and temporal dependencies in dynamic graphs through a new distributed training strategy. This approach eliminates communication overheads associated with accessing remote features and redistributing intermediate results. Experimental results demonstrate that ReInc achieves up to an order of magnitude speedup compared to state-of-the-art frameworks, tested across various dynamic GNN architectures and real-world graph datasets.

Writing comprehensive and accurate descriptions of technical drawings in patent documents is crucial to effective knowledge sharing and enabling the replication and protection of intellectual property. However, automation of this task has been largely overlooked by the research community. To this end, we introduce PatentDesc-355K, a novel large-scale dataset containing ~355K patent figures along with their brief and detailed textual descriptions extracted from more than 60K US patent documents. In addition, we propose PatentLMM - a novel multimodal large language model specifically tailored to generate high-quality descriptions of patent figures. Our proposed PatentLMM comprises two key components: (i) PatentMME, a specialized multimodal vision encoder that captures the unique structural elements of patent figures, and (ii) PatentLLaMA, a domain-adapted version of LLaMA fine-tuned on a large collection of patents. Extensive experiments demonstrate that training a vision encoder specifically designed for patent figures significantly boosts the performance, generating coherent descriptions compared to fine-tuning similar-sized off-the-shelf multimodal models. PatentDesc-355K and PatentLMM pave the way for automating the understanding of patent figures, enabling efficient knowledge sharing and faster drafting of patent documents. We make the code and data publicly available., Comment: Accepted at AAAI 2025 (Main Track). Project page: https://vl2g.github.io/projects/PatentLMM/

Given a graph $G$, a set is $\Delta$-convex if there is no vertex $u\in V(G)\setminus S$ forming a triangle with two vertices of $S$. The $\Delta$-convex hull of $S$ is the minimum $\Delta$-convex set containing $S$. This article is an attempt to discuss the Carath\'eodory number and exchange number on various graph families and standard graph products namely Cartesian, strong and, lexicographic products of graphs.

Objective functions based on Hellinger distance yield robust and efficient estimators of model parameters. Motivated by privacy and regulatory requirements encountered in contemporary applications, we derive in this paper \emph{private minimum Hellinger distance estimators}. The estimators satisfy a new privacy constraint, namely, Hellinger differential privacy, while retaining the robustness and efficiency properties. We demonstrate that Hellinger differential privacy shares several features of standard differential privacy while allowing for sharper inference. Additionally, for computational purposes, we also develop Hellinger differentially private gradient descent and Newton-Raphson algorithms. We illustrate the behavior of our estimators in finite samples using numerical experiments and verify that they retain robustness properties under gross-error contamination.

Brown dwarfs lack nuclear fusion and cool with time; the coldest known have an effective temperature below 500 K, and are known as Y dwarfs. We present a James Webb Space Telescope (JWST) photometric dataset of Y dwarfs: twenty-three were imaged in wide-field mode, 20 using NIRCam with the F150W and F480M filters, and 3 using NIRISS with the F480M filter. We present an F480M vs. F150W $-$ F480M color-magnitude diagram for our sample, and other brown dwarfs with F150W and F480M colors synthesized from JWST spectra by Beiler et al. (2024). For one target, WISEA J083011.95$+$283716.0, its detection in the near-infrared confirms it as one of the reddest Y dwarfs known, with F150W $-$ F480M $= 9.62$ mag. We provide its updated parallax and proper motion. One of the Beiler et al. Y dwarfs, CWISEP J104756.81+545741.6, is unusually blue, consistent with strong CO absorption seen in its spectrum which the F480M filter is particularly sensitive to. The strong CO and the kinematics of the object suggest it may be very low-mass and young. We update the resolved photometry for the close binary system WISE J033605.05$-$014350.4 AB, and find that the secondary is almost as cold as WISE 085510.83$-$071442.5, with $T_{\rm eff} \lesssim 300$ K, however the F150W $-$ F480M color is significantly bluer, possibly suggesting the presence of water clouds. Astrometry is measured at the JWST epoch for the sample which is consistent with parallax and proper motion values reported by Kirkpatrick et al. (2021) and Marocco et al. (in prep)., Comment: Accepted by AJ Jan 23 2025

Social behaviour models are increasingly integrated into climate change studies, and the significance of climate tipping points for `runaway' climate change is well recognised. However, there has been insufficient focus on tipping points in social-climate dynamics. We developed a coupled social-climate model consisting of an Earth system model and a social behaviour model, both with tipping elements. The social model explores opinion formation by analysing social learning rates, the net cost of mitigation, and the strength of social norms. Our results indicate that the net cost of mitigation and social norms have minimal impact on tipping points when social norms are weak. As social norms strengthen, the climate tipping point can trigger a tipping element in the social model. However, faster social learning can delay or prevent the climate tipping point: sufficiently fast social learning means growing climate change mitigation can outpace the oncoming climate tipping point, despite social-climate feedback. By comparing high- and low-risk scenarios, we demonstrated high-risk scenarios increase the likelihood of tipping points. We also illustrate the role of a critical temperature anomaly in triggering tipping points. In conclusion, understanding social behaviour dynamics is vital for predicting climate tipping points and mitigating their impacts.

Deploying complex machine learning models on resource-constrained devices is challenging due to limited computational power, memory, and model retrainability. To address these limitations, a hybrid system can be established by augmenting the local model with a server-side model, where samples are selectively deferred by a rejector and then sent to the server for processing. The hybrid system enables efficient use of computational resources while minimizing the overhead associated with server usage. The recently proposed Learning to Help (L2H) model trains a server model given a fixed local (client) model, differing from the Learning to Defer (L2D) framework, which trains the client for a fixed (expert) server. In both L2D and L2H, the training includes learning a rejector at the client to determine when to query the server. In this work, we extend the L2H model from binary to multi-class classification problems and demonstrate its applicability in a number of different scenarios of practical interest in which access to the server may be limited by cost, availability, or policy. We derive a stage-switching surrogate loss function that is differentiable, convex, and consistent with the Bayes rule corresponding to the 0-1 loss for the L2H model. Experiments show that our proposed methods offer an efficient and practical solution for multi-class classification in resource-constrained environments., Comment: 30 pages, 7 figures, conference, ICLR 2025

Drones are increasingly used in forestry to capture high-resolution remote sensing data. While operations above the forest canopy are already highly automated, flying inside forests remains challenging, primarily relying on manual piloting. Inside dense forests, reliance on the Global Navigation Satellite System (GNSS) for localization is not feasible. Additionally, the drone must autonomously adjust its flight path to avoid collisions. Recently, advancements in robotics have enabled autonomous drone flights in GNSS-denied obstacle-rich areas. In this article, a step towards autonomous forest data collection is taken by building a prototype of a robotic under-canopy drone utilizing state-of-the-art open-source methods and validating its performance for data collection inside forests. The autonomous flight capability was evaluated through multiple test flights in two boreal forest test sites. The tree parameter estimation capability was studied by conducting diameter at breast height (DBH) estimation using onboard stereo camera data and photogrammetric methods. The prototype conducted flights in selected challenging forest environments, and the experiments showed excellent performance in forest reconstruction with a miniaturized stereoscopic photogrammetric system. The stem detection algorithm managed to identify 79.31 % of the stems. The DBH estimation had a root mean square error (RMSE) of 3.33 cm (12.79 %) and a bias of 1.01 cm (3.87 %) across all trees. For trees with a DBH less than 30 cm, the RMSE was 1.16 cm (5.74 %), and the bias was 0.13 cm (0.64 %). When considering the overall performance in terms of DBH accuracy, autonomy, and forest complexity, the proposed approach was superior compared to methods proposed in the scientific literature. Results provided valuable insights into autonomous forest reconstruction using drones, and several further development topics were proposed., Comment: 35 pages, 13 Figures

Context. The UVJ color-color diagram is a widely used diagnostic to separate star-forming and quiescent galaxies. Observational data from photometric surveys reveal a strong stellar mass trend, with higher-mass star-forming galaxies being systematically more dust-reddened. Aims. We analyze the UVJ diagram in the TNG100 cosmological simulation at cosmic noon ($z\approx2$). Specifically, we focus on the trend between UVJ colors and mass which has not been reproduced in any cosmological simulation thus far. Methods. We applied the SKIRT dust radiative transfer code to the TNG100 simulation to generate rest-frame UVJ fluxes. These UVJ colors were then compared to observational data from several well-studied extragalactic fields from the CANDELS/3D-HST programs, augmented by recent JWST/NIRCam photometry. Results. Quiescent and low-mass ($M_\star\lesssim10^{10.5}\,\mathrm{M}_\odot$) galaxies at cosmic noon do not require significant levels of dust reddening, as opposed to massive ($M_\star\gtrsim10^{11}\,\mathrm{M}_\odot$) star-forming galaxies. An extensive range of possible dust models fall short of the required dust reddening in V-J color for massive star-forming galaxies, with the simulated galaxies being too blue by $\approx0.9\,\mathrm{mag}$. Conclusions. We find that only variations in the star-to-dust geometries of the simulated galaxies can yield V-J colors that are red enough to match the observations. A toy model with isolated dust screens around younger stellar populations (with ages below $\sim1\,\mathrm{Gyr}$) can reproduce the observational data, while all conventional dust radiative transfer models (where the dust distribution follows the metals in the interstellar medium) fail to achieve the required V-J colors., Comment: Main text 17 pages, 12 figures. Accepted to A&A. Our analysis is publicly available at https://github.com/andreagebek/TNG100_UVJ

In information-theoretic private information retrieval (PIR), a client wants to retrieve one desired file out of $M$ files, stored across $N$ servers, while keeping the index of the desired file private from each $T$-sized subset of servers. A PIR protocol must ideally maximize the rate, which is the ratio of the file size to the total quantum of the download from the servers, while ensuring such privacy. In Weak-PIR (WPIR), the criterion of perfect information-theoretic privacy is relaxed. This enables higher rates to be achieved, while some information about the desired file index leaks to the servers. This leakage is captured by various known privacy metrics. By leveraging the well-established capacity-achieving schemes of Sun and Jafar under non-colluding ($T=1$) and colluding ($1

Specializing low-level systems to specifics of the workload they serve and platform they are running on often significantly improves performance. However, specializing systems is difficult because of three compounding challenges: i) specialization for optimal performance requires in-depth compile-time changes; ii) the right combination of specialization choices for optimal performance is hard to predict a priori; and iii) workloads and platform details often change online. In practice, benefits of specialization are thus not attainable for many low-level systems. To address this, we advocate for a radically different approach for performance-critical low-level systems: designing and implementing systems with and for runtime code specialization. We leverage just-in-time compilation to change systems code based on developer-specified specialization points as the system runs. The JIT runtime automatically tries out specialization choices and measures their impact on system performance, e.g. request latency or throughput, to guide the search. With Iridescent, our early prototype, we demonstrate that online specialization (i) is feasible even for low-level systems code, such as network stacks, (ii) improves system performance without the need for complex cost models, (iii) incurs low developer effort, especially compared to manual exploration. We conclude with future opportunities online system code specialization enables.

Large Language Models (LLMs) have shown strong promise as rerankers, especially in ``listwise'' settings where an LLM is prompted to rerank several search results at once. However, this ``cascading'' retrieve-and-rerank approach is limited by the bounded recall problem: relevant documents not retrieved initially are permanently excluded from the final ranking. Adaptive retrieval techniques address this problem, but do not work with listwise rerankers because they assume a document's score is computed independently from other documents. In this paper, we propose an adaptation of an existing adaptive retrieval method that supports the listwise setting and helps guide the retrieval process itself (thereby overcoming the bounded recall problem for LLM rerankers). Specifically, our proposed algorithm merges results both from the initial ranking and feedback documents provided by the most relevant documents seen up to that point. Through extensive experiments across diverse LLM rerankers, first stage retrievers, and feedback sources, we demonstrate that our method can improve nDCG@10 by up to 13.23% and recall by 28.02%--all while keeping the total number of LLM inferences constant and overheads due to the adaptive process minimal. The work opens the door to leveraging LLM-based search in settings where the initial pool of results is limited, e.g., by legacy systems, or by the cost of deploying a semantic first-stage., Comment: 16 pages, 2 figures, 3 tables

The safety and security of robotic systems are paramount when navigating around a hostile target. This paper addresses the problem of circumnavigating an unknown target by a unicycle robot while ensuring it maintains a desired safe distance and remains within the sensing region around the target throughout its motion. The proposed control design methodology is based on the construction of a joint Lyapunov function that incorporates: (i) a quadratic potential function characterizing the desired target-circumnavigation objective, and (ii) a barrier Lyapunov function-based potential term to enforce safety and sensing constraints on the robot's motion. A notable feature of the proposed control design is its reliance exclusively on local range measurements between the robot and the target, realized using a dynamic output feedback controller that treats the range as the only observable output for feedback. Using the Lyapunov stability theory, we show that the desired equilibrium of the closed-loop system is asymptotically stable, and the prescribed safety and security constraints are met under the proposed controllers. We also obtain restrictive bounds on the post-design signals and provide both simulation and experimental results to validate the theoretical contributions.

Graph Neural Networks (GNNs) have been widely adopted for their ability to compute expressive node representations in graph datasets. However, serving GNNs on large graphs is challenging due to the high communication, computation, and memory overheads of constructing and executing computation graphs, which represent information flow across large neighborhoods. Existing approximation techniques in training can mitigate the overheads but, in serving, still lead to high latency and/or accuracy loss. To this end, we propose OMEGA, a system that enables low-latency GNN serving for large graphs with minimal accuracy loss through two key ideas. First, OMEGA employs selective recomputation of precomputed embeddings, which allows for reusing precomputed computation subgraphs while selectively recomputing a small fraction to minimize accuracy loss. Second, we develop computation graph parallelism, which reduces communication overhead by parallelizing the creation and execution of computation graphs across machines. Our evaluation with large graph datasets and GNN models shows that OMEGA significantly outperforms state-of-the-art techniques.