title: Estimation of Semiconductor Power Losses Through Automatic Thermal Modeling

abstract: The optimal design of power converters requires accurate knowledge of the dissipation elements of its system to achieve the desired performance and security requirements. Calorimetric methods have surpassed classical electrical methods for the estimation of semiconductor power losses but have mechanical limitations and resort to analytical electrothermal equivalent circuits for this task. These electrothermal models are highly dependent on the topology and technology used on the power converter leading to either simplifications that underestimate the thermal effects or intractable sets of differential equations. To overcome these issues, we propose a novel data-driven identification method to characterize the thermal dynamics of power converters allowing the designer to obtain semiconductor total power losses only by means of temperature measurements without the need of a calorimeter. Given a set of power vs.temperature profiles, our solution identifies the linear model that best fits the data. The solution is based on an optimization problem that allows not only accurate identification but also coding of the desired modeling requirements, such as dynamics' invertibility to allow the estimation of power losses from the temperature profiles. The proposed methodology can be applied to any power converter topology. Furthermore, by obtaining a linear model, standard control theory techniques can be exploited to analyze and control the thermal dynamics. Real experiments validate the generality and accuracy of the proposal.


title: Looking for Carroll particles in two time spacetime

abstract: We make an attempt to describe Carroll particles with a non-vanishing value of energy (i.e. the Carroll particles which always stay in rest) in the framework of two time physics, developed in the series of papers by I. Bars and his co-authors. In the spacetime with one additional time dimension and one additional space dimension one can localize the symmetry which exists between generalized coordinate and their conjugate momenta. Such a localization implies the introduction of the gauge fields, which in turn implies the appearance of some first-class constraints. Choosing different gauge-fixing conditions and solving the constraints one obtain different time parameters, Hamiltonians, and generally, physical systems in the standard one time spacetime. In this way such systems as non-relativistic particle, relativistic particles, hydrogen atoms and harmonic oscillators were described as dual systems in the framework of the two time physics. Here, we find a set of gauge fixing conditions which provides as with such a parametrization of the phase space variables in the two time world which gives the description of Carroll particle in the one time world. Besides, we construct the quantum theory of such a particle using an unexpected correspondence between our parametrization and that obtained by Bars for the hydrogen atom in 1999.


title: A Survey of Methods for Estimating Hurst Exponent of Time Sequence

abstract: The Hurst exponent is a significant indicator for characterizing the self-similarity and long-term memory properties of time sequences. It has wide applications in physics, technologies, engineering, mathematics, statistics, economics, psychology and so on. Currently, available methods for estimating the Hurst exponent of time sequences can be divided into different categories: time-domain methods and spectrum-domain methods based on the representation of time sequence, linear regression methods and Bayesian methods based on parameter estimation methods. Although various methods are discussed in literature, there are still some deficiencies: the descriptions of the estimation algorithms are just mathematics-oriented and the pseudo-codes are missing; the effectiveness and accuracy of the estimation algorithms are not clear; the classification of estimation methods is not considered and there is a lack of guidance for selecting the estimation methods. In this work, the emphasis is put on thirteen dominant methods for estimating the Hurst exponent. For the purpose of decreasing the difficulty of implementing the estimation methods with computer programs, the mathematical principles are discussed briefly and the pseudo-codes of algorithms are presented with necessary details. It is expected that the survey could help the researchers to select, implement and apply the estimation algorithms of interest in practical situations in an easy way.


title: Exploring the Emotional Landscape of Music: An Analysis of Valence Trends and Genre Variations in Spotify Music Data

abstract: This paper conducts an intricate analysis of musical emotions and trends using Spotify music data, encompassing audio features and valence scores extracted through the Spotipi API. Employing regression modeling, temporal analysis, mood transitions, and genre investigation, the study uncovers patterns within music-emotion relationships. Regression models linear, support vector, random forest, and ridge, are employed to predict valence scores. Temporal analysis reveals shifts in valence distribution over time, while mood transition exploration illuminates emotional dynamics within playlists. The research contributes to nuanced insights into music's emotional fabric, enhancing comprehension of the interplay between music and emotions through years.


title: Datasets and Benchmarks for Nanophotonic Structure and Parametric Design Simulations

abstract: Nanophotonic structures have versatile applications including solar cells, anti-reflective coatings, electromagnetic interference shielding, optical filters, and light emitting diodes. To design and understand these nanophotonic structures, electrodynamic simulations are essential. These simulations enable us to model electromagnetic fields over time and calculate optical properties. In this work, we introduce frameworks and benchmarks to evaluate nanophotonic structures in the context of parametric structure design problems. The benchmarks are instrumental in assessing the performance of optimization algorithms and identifying an optimal structure based on target optical properties. Moreover, we explore the impact of varying grid sizes in electrodynamic simulations, shedding light on how evaluation fidelity can be strategically leveraged in enhancing structure designs.


title: Object-centric architectures enable efficient causal representation learning

abstract: Causal representation learning has showed a variety of settings in which we can disentangle latent variables with identifiability guarantees (up to some reasonable equivalence class). Common to all of these approaches is the assumption that (1) the latent variables are represented as $d$-dimensional vectors, and (2) that the observations are the output of some injective generative function of these latent variables. While these assumptions appear benign, we show that when the observations are of multiple objects, the generative function is no longer injective and disentanglement fails in practice. We can address this failure by combining recent developments in object-centric learning and causal representation learning. By modifying the Slot Attention architecture arXiv:2006.15055, we develop an object-centric architecture that leverages weak supervision from sparse perturbations to disentangle each object's properties. This approach is more data-efficient in the sense that it requires significantly fewer perturbations than a comparable approach that encodes to a Euclidean space and we show that this approach successfully disentangles the properties of a set of objects in a series of simple image-based disentanglement experiments.


title: A Few-Shot Learning Focused Survey on Recent Named Entity Recognition and Relation Classification Methods

abstract: Named Entity Recognition (NER) and Relation Classification (RC) are important steps in extracting information from unstructured text and formatting it into a machine-readable format. We present a survey of recent deep learning models that address named entity recognition and relation classification, with focus on few-shot learning performance. Our survey is helpful for researchers in knowing the recent techniques in text mining and extracting structured information from raw text.


title: MILL: Mutual Verification with Large Language Models for Zero-Shot Query Expansion

abstract: Query expansion, pivotal in search engines, enhances the representation of user information needs with additional terms. While existing methods expand queries using retrieved or generated contextual documents, each approach has notable limitations. Retrieval-based methods often fail to accurately capture search intent, particularly with brief or ambiguous queries. Generation-based methods, utilizing large language models (LLMs), generally lack corpus-specific knowledge and entail high fine-tuning costs. To address these gaps, we propose a novel zero-shot query expansion framework utilizing LLMs for mutual verification. Specifically, we first design a query-query-document generation method, leveraging LLMs' zero-shot reasoning ability to produce diverse sub-queries and corresponding documents. Then, a mutual verification process synergizes generated and retrieved documents for optimal expansion. Our proposed method is fully zero-shot, and extensive experiments on three public benchmark datasets are conducted to demonstrate its effectiveness over existing methods. Our code is available online at https://github.com/Applied-Machine-Learning-Lab/MILL to ease reproduction.


title: A Unique Training Strategy to Enhance Language Models Capabilities for Health Mention Detection from Social Media Content

abstract: An ever-increasing amount of social media content requires advanced AI-based computer programs capable of extracting useful information. Specifically, the extraction of health-related content from social media is useful for the development of diverse types of applications including disease spread, mortality rate prediction, and finding the impact of diverse types of drugs on diverse types of diseases. Language models are competent in extracting the syntactic and semantics of text. However, they face a hard time extracting similar patterns from social media texts. The primary reason for this shortfall lies in the non-standardized writing style commonly employed by social media users. Following the need for an optimal language model competent in extracting useful patterns from social media text, the key goal of this paper is to train language models in such a way that they learn to derive generalized patterns. The key goal is achieved through the incorporation of random weighted perturbation and contrastive learning strategies. On top of a unique training strategy, a meta predictor is proposed that reaps the benefits of 5 different language models for discriminating posts of social media text into non-health and health-related classes. Comprehensive experimentation across 3 public benchmark datasets reveals that the proposed training strategy improves the performance of the language models up to 3.87%, in terms of F1-score, as compared to their performance with traditional training. Furthermore, the proposed meta predictor outperforms existing health mention classification predictors across all 3 benchmark datasets.


title: Stacking Group Structure of Fermionic Symmetry-Protected Topological Phases

abstract: In the past decade, there has been a systematic investigation of symmetry-protected topological (SPT) phases in interacting fermion systems. Specifically, by utilizing the concept of equivalence classes of finite-depth fermionic symmetric local unitary (FSLU) transformations and the fluctuating decorated symmetry domain wall picture, a large class of fixed-point wave functions have been constructed for fermionic SPT (FSPT) phases. Remarkably, this construction coincides with the Atiyah-Hirzebruch spectral sequence, enabling a complete classification of FSPT phases. However, unlike bosonic SPT phases, the stacking group structure in fermion systems proves to be much more intricate. The construction of fixed-point wave functions does not explicitly provide this information. In this paper, we employ FSLU transformations to investigate the stacking group structure of FSPT phases. Specifically, we demonstrate how to compute stacking FSPT data from the input FSPT data in each layer, considering both unitary and anti-unitary symmetry, up to 2+1 dimensions. As concrete examples, we explicitly compute the stacking group structure for crystalline FSPT phases in all 17 wallpaper groups and the mixture of wallpaper groups with onsite time-reversal symmetry using the fermionic crystalline equivalence principle. Importantly, our approach can be readily extended to higher dimensions, offering a versatile method for exploring the stacking group structure of FSPT phases.


title: Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression

abstract: We consider the problem of finding second-order stationary points of heterogeneous federated learning (FL). Previous works in FL mostly focus on first-order convergence guarantees, which do not rule out the scenario of unstable saddle points. Meanwhile, it is a key bottleneck of FL to achieve communication efficiency without compensating the learning accuracy, especially when local data are highly heterogeneous across different clients. Given this, we propose a novel algorithm Power-EF that only communicates compressed information via a novel error-feedback scheme. To our knowledge, Power-EF is the first distributed and compressed SGD algorithm that provably escapes saddle points in heterogeneous FL without any data homogeneity assumptions. In particular, Power-EF improves to second-order stationary points after visiting first-order (possibly saddle) points, using additional gradient queries and communication rounds only of almost the same order required by first-order convergence, and the convergence rate exhibits a linear speedup in terms of the number of workers. Our theory improves/recovers previous results, while extending to much more tolerant settings on the local data. Numerical experiments are provided to complement the theory.


title: TESTA: Temporal-Spatial Token Aggregation for Long-form Video-Language Understanding

abstract: Large-scale video-language pre-training has made remarkable strides in advancing video-language understanding tasks. However, the heavy computational burden of video encoding remains a formidable efficiency bottleneck, particularly for long-form videos. These videos contain massive visual tokens due to their inherent 3D properties and spatiotemporal redundancy, making it challenging to capture complex temporal and spatial relationships. To tackle this issue, we propose an efficient method called TEmporal-Spatial Token Aggregation (TESTA). TESTA condenses video semantics by adaptively aggregating similar frames, as well as similar patches within each frame. TESTA can reduce the number of visual tokens by 75% and thus accelerate video encoding. Building upon TESTA, we introduce a pre-trained video-language model equipped with a divided space-time token aggregation module in each video encoder block. We evaluate our model on five datasets for paragraph-to-video retrieval and long-form VideoQA tasks. Experimental results show that TESTA improves computing efficiency by 1.7 times, and achieves significant performance gains from its scalability in processing longer input frames, e.g., +13.7 R@1 on QuerYD and +6.5 R@1 on Condensed Movie.


title: Multimodal ChatGPT for Medical Applications: an Experimental Study of GPT-4V

abstract: In this paper, we critically evaluate the capabilities of the state-of-the-art multimodal large language model, i.e., GPT-4 with Vision (GPT-4V), on Visual Question Answering (VQA) task. Our experiments thoroughly assess GPT-4V's proficiency in answering questions paired with images using both pathology and radiology datasets from 11 modalities (e.g. Microscopy, Dermoscopy, X-ray, CT, etc.) and fifteen objects of interests (brain, liver, lung, etc.). Our datasets encompass a comprehensive range of medical inquiries, including sixteen distinct question types. Throughout our evaluations, we devised textual prompts for GPT-4V, directing it to synergize visual and textual information. The experiments with accuracy score conclude that the current version of GPT-4V is not recommended for real-world diagnostics due to its unreliable and suboptimal accuracy in responding to diagnostic medical questions. In addition, we delineate seven unique facets of GPT-4V's behavior in medical VQA, highlighting its constraints within this complex arena. The complete details of our evaluation cases are accessible at https://github.com/ZhilingYan/GPT4V-Medical-Report.


title: A multi-modal table tennis robot system

abstract: In recent years, robotic table tennis has become a popular research challenge for perception and robot control. Here, we present an improved table tennis robot system with high accuracy vision detection and fast robot reaction. Based on previous work, our system contains a KUKA robot arm with 6 DOF, with four frame-based cameras and two additional event-based cameras. We developed a novel calibration approach to calibrate this multimodal perception system. For table tennis, spin estimation is crucial. Therefore, we introduced a novel, and more accurate spin estimation approach. Finally, we show how combining the output of an event-based camera and a Spiking Neural Network (SNN) can be used for accurate ball detection.


title: Feature Aggregation in Joint Sound Classification and Localization Neural Networks

abstract: This study addresses the application of deep learning techniques in joint sound signal classification and localization networks. Current state-of-the-art sound source localization deep learning networks lack feature aggregation within their architecture. Feature aggregation enhances model performance by enabling the consolidation of information from different feature scales, thereby improving feature robustness and invariance. This is particularly important in SSL networks, which must differentiate direct and indirect acoustic signals. To address this gap, we adapt feature aggregation techniques from computer vision neural networks to signal detection neural networks. Additionally, we propose the Scale Encoding Network (SEN) for feature aggregation to encode features from various scales, compressing the network for more computationally efficient aggregation. To evaluate the efficacy of feature aggregation in SSL networks, we integrated the following computer vision feature aggregation sub-architectures into a SSL control architecture: Path Aggregation Network (PANet), Weighted Bi-directional Feature Pyramid Network (BiFPN), and SEN. These sub-architectures were evaluated using two metrics for signal classification and two metrics for direction-of-arrival regression. PANet and BiFPN are established aggregators in computer vision models, while the proposed SEN is a more compact aggregator. The results suggest that models incorporating feature aggregations outperformed the control model, the Sound Event Localization and Detection network (SELDnet), in both sound signal classification and localization. The feature aggregation techniques enhance the performance of sound detection neural networks, particularly in direction-of-arrival regression.


title: Apple Tasting: Combinatorial Dimensions and Minimax Rates

abstract: In online binary classification under \emph{apple tasting} feedback, the learner only observes the true label if it predicts ``1". First studied by \cite{helmbold2000apple}, we revisit this classical partial-feedback setting and study online learnability from a combinatorial perspective. We show that the Littlestone dimension continues to provide a tight quantitative characterization of apple tasting in the agnostic setting, closing an open question posed by \cite{helmbold2000apple}. In addition, we give a new combinatorial parameter, called the Effective width, that tightly quantifies the minimax expected mistakes in the realizable setting. As a corollary, we use the Effective width to establish a \emph{trichotomy} of the minimax expected number of mistakes in the realizable setting. In particular, we show that in the realizable setting, the expected number of mistakes of any learner, under apple tasting feedback, can be $\Theta(1), \Theta(\sqrt{T})$, or $\Theta(T)$. This is in contrast to the full-information realizable setting where only $\Theta(1)$ and $\Theta(T)$ are possible.


title: Evaluating LLP Methods: Challenges and Approaches

abstract: Learning from Label Proportions (LLP) is an established machine learning problem with numerous real-world applications. In this setting, data items are grouped into bags, and the goal is to learn individual item labels, knowing only the features of the data and the proportions of labels in each bag. Although LLP is a well-established problem, it has several unusual aspects that create challenges for benchmarking learning methods. Fundamental complications arise because of the existence of different LLP variants, i.e., dependence structures that can exist between items, labels, and bags. Accordingly, the first algorithmic challenge is the generation of variant-specific datasets capturing the diversity of dependence structures and bag characteristics. The second methodological challenge is model selection, i.e., hyperparameter tuning; due to the nature of LLP, model selection cannot easily use the standard machine learning paradigm. The final benchmarking challenge consists of properly evaluating LLP solution methods across various LLP variants. We note that there is very little consideration of these issues in prior work, and there are no general solutions for these challenges proposed to date. To address these challenges, we develop methods capable of generating LLP datasets meeting the requirements of different variants. We use these methods to generate a collection of datasets encompassing the spectrum of LLP problem characteristics, which can be used in future evaluation studies. Additionally, we develop guidelines for benchmarking LLP algorithms, including the model selection and evaluation steps. Finally, we illustrate the new methods and guidelines by performing an extensive benchmark of a set of well-known LLP algorithms. We show that choosing the best algorithm depends critically on the LLP variant and model selection method, demonstrating the need for our proposed approach.


title: Gauge-optimal approximate learning for small data classification problems

abstract: Small data learning problems are characterized by a significant discrepancy between the limited amount of response variable observations and the large feature space dimension. In this setting, the common learning tools struggle to identify the features important for the classification task from those that bear no relevant information, and cannot derive an appropriate learning rule which allows to discriminate between different classes. As a potential solution to this problem, here we exploit the idea of reducing and rotating the feature space in a lower-dimensional gauge and propose the Gauge-Optimal Approximate Learning (GOAL) algorithm, which provides an analytically tractable joint solution to the dimension reduction, feature segmentation and classification problems for small data learning problems. We prove that the optimal solution of the GOAL algorithm consists in piecewise-linear functions in the Euclidean space, and that it can be approximated through a monotonically convergent algorithm which presents -- under the assumption of a discrete segmentation of the feature space -- a closed-form solution for each optimization substep and an overall linear iteration cost scaling. The GOAL algorithm has been compared to other state-of-the-art machine learning (ML) tools on both synthetic data and challenging real-world applications from climate science and bioinformatics (i.e., prediction of the El Nino Southern Oscillation and inference of epigenetically-induced gene-activity networks from limited experimental data). The experimental results show that the proposed algorithm outperforms the reported best competitors for these problems both in learning performance and computational cost.


title: Expanding memory in recurrent spiking networks

abstract: Recurrent spiking neural networks (RSNNs) are notoriously difficult to train because of the vanishing gradient problem that is enhanced by the binary nature of the spikes. In this paper, we review the ability of the current state-of-the-art RSNNs to solve long-term memory tasks, and show that they have strong constraints both in performance, and for their implementation on hardware analog neuromorphic processors. We present a novel spiking neural network that circumvents these limitations. Our biologically inspired neural network uses synaptic delays, branching factor regularization and a novel surrogate derivative for the spiking function. The proposed network proves to be more successful in using the recurrent connections on memory tasks.


title: Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming

abstract: Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS). In this work, we develop new techniques to extend the applicability of sketching-based approaches to the sparse dictionary learning and the Euclidean $k$-means clustering problems. In particular, we initiate the study of the challenging setting where the dictionary/clustering assignment for each of the $n$ input points must be output, which has surprisingly received little attention in prior work. On the fast algorithms front, we obtain a new approach for designing PTAS's for the $k$-means clustering problem, which generalizes to the first PTAS for the sparse dictionary learning problem. On the streaming algorithms front, we obtain new upper bounds and lower bounds for dictionary learning and $k$-means clustering. In particular, given a design matrix $\mathbf A\in\mathbb R^{n\times d}$ in a turnstile stream, we show an $\tilde O(nr/\epsilon^2 + dk/\epsilon)$ space upper bound for $r$-sparse dictionary learning of size $k$, an $\tilde O(n/\epsilon^2 + dk/\epsilon)$ space upper bound for $k$-means clustering, as well as an $\tilde O(n)$ space upper bound for $k$-means clustering on random order row insertion streams with a natural "bounded sensitivity" assumption. On the lower bounds side, we obtain a general $\tilde\Omega(n/\epsilon + dk/\epsilon)$ lower bound for $k$-means clustering, as well as an $\tilde\Omega(n/\epsilon^2)$ lower bound for algorithms which can estimate the cost of a single fixed set of candidate centers.


title: Efficient Cluster Selection for Personalized Federated Learning: A Multi-Armed Bandit Approach

abstract: Federated learning (FL) offers a decentralized training approach for machine learning models, prioritizing data privacy. However, the inherent heterogeneity in FL networks, arising from variations in data distribution, size, and device capabilities, poses challenges in user federation. Recognizing this, Personalized Federated Learning (PFL) emphasizes tailoring learning processes to individual data profiles. In this paper, we address the complexity of clustering users in PFL, especially in dynamic networks, by introducing a dynamic Upper Confidence Bound (dUCB) algorithm inspired by the multi-armed bandit (MAB) approach. The dUCB algorithm ensures that new users can effectively find the best cluster for their data distribution by balancing exploration and exploitation. The performance of our algorithm is evaluated in various cases, showing its effectiveness in handling dynamic federated learning scenarios.


title: Myriad: Large Multimodal Model by Applying Vision Experts for Industrial Anomaly Detection

abstract: Existing industrial anomaly detection (IAD) methods predict anomaly scores for both anomaly detection and localization. However, they struggle to perform a multi-turn dialog and detailed descriptions for anomaly regions, e.g., color, shape, and categories of industrial anomalies. Recently, large multimodal (i.e., vision and language) models (LMMs) have shown eminent perception abilities on multiple vision tasks such as image captioning, visual understanding, visual reasoning, etc., making it a competitive potential choice for more comprehensible anomaly detection. However, the knowledge about anomaly detection is absent in existing general LMMs, while training a specific LMM for anomaly detection requires a tremendous amount of annotated data and massive computation resources. In this paper, we propose a novel large multi-modal model by applying vision experts for industrial anomaly detection (dubbed Myriad), which leads to definite anomaly detection and high-quality anomaly description. Specifically, we adopt MiniGPT-4 as the base LMM and design an Expert Perception module to embed the prior knowledge from vision experts as tokens which are intelligible to Large Language Models (LLMs). To compensate for the errors and confusions of vision experts, we introduce a domain adapter to bridge the visual representation gaps between generic and industrial images. Furthermore, we propose a Vision Expert Instructor, which enables the Q-Former to generate IAD domain vision-language tokens according to vision expert prior. Extensive experiments on MVTec-AD and VisA benchmarks demonstrate that our proposed method not only performs favorably against state-of-the-art methods under the 1-class and few-shot settings, but also provide definite anomaly prediction along with detailed descriptions in IAD domain.


title: One-loop thermal radiation exchange in gravitational wave power spectrum

abstract: The radiation-dominated universe is a key ingredient of the standard Big Bang cosmology. Radiation comprises numerous quantum elementary particles, and the macroscopic behavior of radiation is described by taking the quantum thermal average of its constituents. While the interactions between individual particles and gravitational waves are often neglected in this context, it raises the question of whether these elementary particles interact with gravitational waves in the framework of quantum field theory. To address this question, this paper aims at exploring the quantum mechanical aspects of gravitational waves in a universe dominated by a massless scalar field, whose averaged energy-momentum tensor plays the role of background radiation. We establish the equivalence between the classical Einstein equation and the mean-field approximation of the Heisenberg equation in a local thermal state. Beyond the mean-field approximation, we analyze the quantum corrections to gravitational waves, particularly focusing on the thermal radiation loop corrections. Interestingly, we find the 1-loop correction surpasses the tree-level spectrum of primordial gravitational waves, which is $O(\alpha^2)$ where $\alpha=H_{\rm inf.}/M_{\rm pl}$ is the ratio of the inflationary Hubble parameter to the Planck mass. Then, to see if this result persists even if we take into account all the higher order loop corrections, the loop expansion is reorganized in the series expansion in $\alpha$. We find all the loop diagrams that may give $O(\alpha^2)$ contributions. We leave explicit computations of these diagrams for future studies. Thus, although we cannot claim that the whole loop corrections exceed the tree-level spectrum at the moment, our findings highlight the significance of considering quantum effects when studying the interaction between radiation and gravitational waves in the cosmological context.


title: Hall magnetohydrodynamics in a relativistically strong mean magnetic field

abstract: This Letter presents a magnetohydrodynamic model that describes the small-amplitude fluctuations with wavelengths comparable to ion inertial length in the presence of a relativistically strong mean magnetic field. The set of derived equations is virtually identical to the non-relativistic Hall reduced magnetohydrodynamics (Schekochihin et al. 2019), differing only by a few constants that take into account the relativistic corrections. This means that all the properties of kinetic Alfv\'en turbulence and ion cyclotron turbulence inherent in the non-relativistic Hall regime persist unchanged even in a magnetically dominated regime.


title: Deffuant opinion dynamics with attraction and repulsion

abstract: In the Deffuant model, individuals are located on the vertices of a graph, and are characterized by their opinion, a number in $[-1, 1]$. The dynamics depends on two parameters: a confidence threshold $\theta < 2$ and a convergent parameter $\mu_- \leq 1/2$. Neighbors on the graph interact at rate one, which results in no changes if the neighbors disagree by more than $\theta$, and a compromise with the opinions moving toward each other by a factor $\mu_-$ if they disagree by less than $\theta$ (attraction). The main conjecture about the Deffuant model, which was proved for the process on the integers, states that, for all $\mu_- > 0$ and starting from the product measure in which the opinions are uniformly distributed in the interval $[-1, 1]$, there is a phase transition from discordance to consensus at the confidence threshold one. In this paper, we study a natural variant of the model in which neighbors who disagree by more than $\theta$ feel more strongly about their own opinion, which is modeled by assuming that the opinions move away from each other by a divergent parameter $\mu_+$ (repulsion). We prove, for the process on the integers, the absence of a phase transition even for arbitrarily small $\mu_+ > 0$, in the sense that, for every nontrivial choice of $\theta$, there is always discordance.


title: Investigating peer recognition across an introductory physics sequence: Do first impressions last?

abstract: Students' beliefs about the extent to which meaningful others, including their peers, recognize them as a strong science student are correlated with their persistence in science courses and careers. Yet, prior work has found a gender bias in peer recognition, in which student nominations of strong peers disproportionately favor men over women, in some instructional contexts. Researchers have hypothesized that such a gender bias diminishes over time, as determined by students' academic year: studies have found a gender bias in science courses aimed at first-year students, but not in science courses aimed at beyond first-year students. This hypothesis that patterns of peer recognition change over time, however, has yet to be tested with longitudinal data--previous studies only examine snapshots of different students in different science courses. In this study, we isolate the effect of time on peer recognition by analyzing student nominations of strong peers across a two-semester introductory physics course sequence, containing the same set of students and the same instructor in both semesters, at a mostly-women institution. Using a combination of social network analysis and qualitative methods, we find that while many students receive similar levels of peer recognition over time, the four most highly nominated students--the recognition celebrities--exhibit some change between semesters even in this highly controlled setting. Furthermore, we observe that these changes in the celebrities track closely with changes in student outspokenness and that being outspoken is likely more important for gaining recognition than earning a high grade in the class. These findings lend support to prior work's hypothesis that peer recognition changes over time, but also challenge the generalizability of previous results (i.e., that patterns of recognition are related to students' academic year).


title: Bespoke Solvers for Generative Flow Models

abstract: Diffusion or flow-based models are powerful generative paradigms that are notoriously hard to sample as samples are defined as solutions to high-dimensional Ordinary or Stochastic Differential Equations (ODEs/SDEs) which require a large Number of Function Evaluations (NFE) to approximate well. Existing methods to alleviate the costly sampling process include model distillation and designing dedicated ODE solvers. However, distillation is costly to train and sometimes can deteriorate quality, while dedicated solvers still require relatively large NFE to produce high quality samples. In this paper we introduce "Bespoke solvers", a novel framework for constructing custom ODE solvers tailored to the ODE of a given pre-trained flow model. Our approach optimizes an order consistent and parameter-efficient solver (e.g., with 80 learnable parameters), is trained for roughly 1% of the GPU time required for training the pre-trained model, and significantly improves approximation and generation quality compared to dedicated solvers. For example, a Bespoke solver for a CIFAR10 model produces samples with Fr\'echet Inception Distance (FID) of 2.73 with 10 NFE, and gets to 1% of the Ground Truth (GT) FID (2.59) for this model with only 20 NFE. On the more challenging ImageNet-64$\times$64, Bespoke samples at 2.2 FID with 10 NFE, and gets within 2% of GT FID (1.71) with 20 NFE.


title: The Refined Humbert Invariant for an Automorphism Group of a Genus 2 Curve

abstract: The purpose of this paper is to list the refined Humbert invariants for a given automorphism group of a curve $C/K$ of genus 2 over an algebraically closed field $K$ with characteristic $0$. This invariant is an algebraic generalization of the (usual) \textit{Humbert invariant}. It is a positive definite quadratic form associated to the curve $C$, and it encodes many geometric properties of the curve. The paper has a special interest in the cases where $Aut(C)\simeq D_4$ or $D_6$. In these cases, several applications of the main results are discussed, including the curves with elliptic subcovers of a given degree.


title: Near-Optimal Packet Scheduling in Multihop Networks with End-to-End Deadline Constraints

abstract: Scheduling packets with end-to-end deadline constraints in multihop networks is an important problem that has been notoriously difficult to tackle. Recently, there has been progress on this problem in the worst-case traffic setting, with the objective of maximizing the number of packets delivered within their deadlines. Specifically, the proposed algorithms were shown to achieve $\Omega(1/\log(L))$ fraction of the optimal objective value if the minimum link capacity in the network is $C_{\min}=\Omega(\log (L))$, where $L$ is the maximum length of a packet's route in the network (which is bounded by the packet's maximum deadline). However, such guarantees can be quite pessimistic due to the strict worst-case traffic assumption and may not accurately reflect real-world settings. In this work, we aim to address this limitation by exploring whether it is possible to design algorithms that achieve a constant fraction of the optimal value while relaxing the worst-case traffic assumption. We provide a positive answer by demonstrating that in stochastic traffic settings, such as i.i.d. packet arrivals, near-optimal, $(1-\epsilon)$-approximation algorithms can be designed if $C_{\min} = \Omega\big(\frac{\log (L/\epsilon) } {\epsilon^2}\big)$. To the best of our knowledge, this is the first result that shows this problem can be solved near-optimally under nontrivial assumptions on traffic and link capacity. We further present extended simulations using real network traces with non-stationary traffic, which demonstrate that our algorithms outperform worst-case-based algorithms in practical settings.


title: Koopman Spectral Linearization vs. Carleman Linearization: A Computational Comparison Study

abstract: Nonlinearity presents a significant challenge in problems involving dynamical systems, prompting the exploration of various linearization techniques, including the well-known Carleman Linearization. In this paper, we introduce the Koopman Spectral Linearization method tailored for nonlinear autonomous dynamical systems. This innovative linearization approach harnesses the Chebyshev differentiation matrix and the Koopman Operator to yield a lifted linear system. It holds the promise of serving as an alternative approach that can be employed in scenarios where Carleman linearization is traditionally applied. Numerical experiments demonstrate the effectiveness of this linearization approach for several commonly used nonlinear dynamical systems.


title: Digital Twin-Driven Network Architecture for Video Streaming

abstract: Digital twin (DT) is revolutionizing the emerging video streaming services through tailored network management. By integrating diverse advanced communication technologies, DTs are promised to construct a holistic virtualized network for better network management performance. To this end, we develop a DT-driven network architecture for video streaming (DTN4VS) to enable network virtualization and tailored network management. With the architecture, various types of DTs can characterize physical entities' status, separate the network management functions from the network controller, and empower the functions with emulated data and tailored strategies. To further enhance network management performance, three potential approaches are proposed, i.e., domain data exploitation, performance evaluation, and adaptive DT model update. We present a case study pertaining to DT-assisted network slicing for short video streaming, followed by some open research issues for DTN4VS.


title: Reward Finetuning for Faster and More Accurate Unsupervised Object Discovery

abstract: Recent advances in machine learning have shown that Reinforcement Learning from Human Feedback (RLHF) can improve machine learning models and align them with human preferences. Although very successful for Large Language Models (LLMs), these advancements have not had a comparable impact in research for autonomous vehicles -- where alignment with human expectations can be imperative. In this paper, we propose to adapt similar RL-based methods to unsupervised object discovery, i.e. learning to detect objects from LiDAR points without any training labels. Instead of labels, we use simple heuristics to mimic human feedback. More explicitly, we combine multiple heuristics into a simple reward function that positively correlates its score with bounding box accuracy, i.e., boxes containing objects are scored higher than those without. We start from the detector's own predictions to explore the space and reinforce boxes with high rewards through gradient updates. Empirically, we demonstrate that our approach is not only more accurate, but also orders of magnitudes faster to train compared to prior works on object discovery.


title: Deep Audio Analyzer: a Framework to Industrialize the Research on Audio Forensics

abstract: Deep Audio Analyzer is an open source speech framework that aims to simplify the research and the development process of neural speech processing pipelines, allowing users to conceive, compare and share results in a fast and reproducible way. This paper describes the core architecture designed to support several tasks of common interest in the audio forensics field, showing possibility of creating new tasks thus customizing the framework. By means of Deep Audio Analyzer, forensics examiners (i.e. from Law Enforcement Agencies) and researchers will be able to visualize audio features, easily evaluate performances on pretrained models, to create, export and share new audio analysis workflows by combining deep neural network models with few clicks. One of the advantages of this tool is to speed up research and practical experimentation, in the field of audio forensics analysis thus also improving experimental reproducibility by exporting and sharing pipelines. All features are developed in modules accessible by the user through a Graphic User Interface. Index Terms: Speech Processing, Deep Learning Audio, Deep Learning Audio Pipeline creation, Audio Forensics.


title: Valence band electronic structure of Nb2Pd1.2Se5 and Nb2Pd0.95S5 superconductors

abstract: We present a comparative study of our valence band photoemission results on Nb2Pd1.2Se5 and Nb2Pd0.95S5 superconductors which is supported by our DFT based electronic structure calculations. We observe that the VB spectra of both the compounds are qualitatively similar, except slight difference in the binding energy position of all features between the two compounds which could be the result of different electronegativity of Se and S atom. The calculated density of states reveal that the VB features are mainly composed of Pd Se S hybridized states. The nature of DOS originating from the distinctly coordinated Pd atoms is different. Further, the involvement of the various Pd 4d and Nb 4d states in crossing of Fermi level signifies the multiband character of these compounds. In addition, we find a temperature dependent pseudogap in Nb2Pd0.95S5 which is absent in Nb2Pd1.2Se5.


title: Backward Reachability Analysis of Perturbed Continuous-Time Linear Systems Using Set Propagation

abstract: Backward reachability analysis computes the set of states that reach a target set under the competing influence of control input and disturbances. Depending on their interplay, the backward reachable set either represents all states that can be steered into the target set or all states that cannot avoid entering it -- the corresponding solutions can be used for controller synthesis and safety verification, respectively. A popular technique for backward reachable set computation solves Hamilton-Jacobi-Isaacs equations, which scales exponentially with the state dimension due to gridding the state space. In this work, we instead use set propagation techniques to design backward reachability algorithms for linear time-invariant systems. Crucially, the proposed algorithms scale only polynomially with the state dimension. Our numerical examples demonstrate the tightness of the obtained backward reachable sets and show an overwhelming improvement of our proposed algorithms over state-of-the-art methods regarding scalability, as systems with well over a hundred states can now be analyzed.


title: Roles of Scaling and Instruction Tuning in Language Perception: Model vs. Human Attention

abstract: Recent large language models (LLMs) have revealed strong abilities to understand natural language. Since most of them share the same basic structure, i.e. the transformer block, possible contributors to their success in the training process are scaling and instruction tuning. However, how these factors affect the models' language perception is unclear. This work compares the self-attention of several existing LLMs (LLaMA, Alpaca and Vicuna) in different sizes (7B, 13B, 30B, 65B), together with eye saccade, an aspect of human reading attention, to assess the effect of scaling and instruction tuning on language perception. Results show that scaling enhances the human resemblance and improves the effective attention by reducing the trivial pattern reliance, while instruction tuning does not. However, instruction tuning significantly enhances the models' sensitivity to instructions. We also find that current LLMs are consistently closer to non-native than native speakers in attention, suggesting a sub-optimal language perception of all models. Our code and data used in the analysis is available on GitHub.


title: Extension of Hyperspace Selections

abstract: In 1951, Ernest Michael wrote a definitive seminal article on hyperspaces raising a general question that became known as the hyperspace selection problem. The present paper contains some aspects of this problem, along with several open questions. Most of these considerations and questions are related to the usual map extension problem, but now in the setting of hyperspaces and hyperspace selections.


title: Scalar mixing and entrainment in an axisymmetric jet subjected to external turbulence

abstract: The effect of zero-mean-flow external turbulence on the topology of the scalar turbulent/turbulent interface (TTI) has been recently studied in axisymmetric jets (Kohan & Gaskin, J. Fluid Mech., vol. 950, 2022, A32). The present study aims to understand the process of turbulent entrainment into a jet, as affected by background turbulence, using scalar statistics. Planar-laser-induced fluorescence was employed to capture the orthogonal cross sections of the jet at a fixed downstream station with varying background turbulence intensities and length scales. The conditional scalar profiles revealed that the thickness of the scalar TTI is greater than that of the traditional turbulent/non-turbulent interface (TNTI), and the interfacial thickness is an increasing function of the background turbulence intensity. Although nibbling remains the primary entrainment mechanism in the far field, increased occurrence of concentration 'holes' within the interfacial layer in the presence of ambient turbulence suggests a more significant role of large-scale engulfment in the turbulent/turbulent entrainment process. Enhanced contribution of the area of detached jet patches (i.e. 'islands') to that of the main jet is hypothesized to be evidence of intense detrainment events in the background turbulence. This can potentially explain the reduced net entrainment into the jet, which manifests as less negative values of scalar skewness within the jet core.


title: Transport-of-Intensity Model for Single-Mask X-ray Differential Phase Contrast Imaging

abstract: X-ray phase contrast imaging holds great promise for improving the visibility of light-element materials such as soft tissues and tumors. Single-mask differential phase contrastnimaging method stands out as a simple and effective approach to yield differential phase contrast. In this work, we introduce a novel model for a single-mask phase imaging system based on the transport-of-intensity equation. Our model provides an accessible understanding of signal and contrast formation in single-mask X-ray phase imaging, offering a clear perspective on the image formation process, for example, the origin of alternate bright and dark fringes in phase contrast intensity images. Aided by our model, we present an efficient retrieval method that yields differential phase contrast imagery in a single acquisition step. Our model gives insight into the contrast generation and its dependence on the system geometry and imaging parameters in both the initial intensity image as well as in retrieved images. The model validity as well as the proposed retrieval method is demonstrated via both experimental results on a system developed in-house as well as with Monte Carlo simulations. In conclusion, our work not only provides a model for an intuitive visualization of image formation but also offers a method to optimize differential phase imaging setups, holding tremendous promise for advancing medical diagnostics and other applications.

categories: eess.IV physics.ins-det physics.med-ph physics.optics q-bio.TO


title: Smooth Stable Foliations of Anosov Diffeomorphisms

abstract: In this paper, we focus on the rigidity of $C^{2+}$-smooth codimension-one stable foliations of Anosov diffeomorphisms. Specifically, we show that if the regularity of these foliations is slightly bigger than $2$, then they will have the same smoothness as the diffeomorphisms.


title: Pushdown Layers: Encoding Recursive Structure in Transformer Language Models

abstract: Recursion is a prominent feature of human language, and fundamentally challenging for self-attention due to the lack of an explicit recursive-state tracking mechanism. Consequently, Transformer language models poorly capture long-tail recursive structure and exhibit sample-inefficient syntactic generalization. This work introduces Pushdown Layers, a new self-attention layer that models recursive state via a stack tape that tracks estimated depths of every token in an incremental parse of the observed prefix. Transformer LMs with Pushdown Layers are syntactic language models that autoregressively and synchronously update this stack tape as they predict new tokens, in turn using the stack tape to softly modulate attention over tokens -- for instance, learning to "skip" over closed constituents. When trained on a corpus of strings annotated with silver constituency parses, Transformers equipped with Pushdown Layers achieve dramatically better and 3-5x more sample-efficient syntactic generalization, while maintaining similar perplexities. Pushdown Layers are a drop-in replacement for standard self-attention. We illustrate this by finetuning GPT2-medium with Pushdown Layers on an automatically parsed WikiText-103, leading to improvements on several GLUE text classification tasks.


title: gafro: Geometric Algebra for Robotics

abstract: Geometry is a fundamental part of robotics and there have been various frameworks of representation over the years. Recently, geometric algebra has gained attention for its property of unifying many of those previous ideas into one algebra. While there are already efficient open-source implementations of geometric algebra available, none of them is targeted at robotics applications. We want to address this shortcoming with our library gafro. This article presents an overview of the implementation details as well as a tutorial of gafro, an efficient c++ library targeting robotics applications using geometric algebra. The library focuses on using conformal geometric algebra. Hence, various geometric primitives are available for computation as well as rigid body transformations. The modeling of robotic systems is also an important aspect of the library. It implements various algorithms for calculating the kinematics and dynamics of such systems as well as objectives for optimisation problems. The software stack is completed by python bindings in pygafro and a ROS interface in gafro_ros.


title: Bridging the Gap: Towards an Expanded Toolkit for ML-Supported Decision-Making in the Public Sector

abstract: Machine Learning (ML) systems are becoming instrumental in the public sector, with applications spanning areas like criminal justice, social welfare, financial fraud detection, and public health. While these systems offer great potential benefits to institutional decision-making processes, such as improved efficiency and reliability, they still face the challenge of aligning nuanced policy objectives with the precise formalization requirements necessitated by ML models. In this paper, we aim to bridge the gap between ML model requirements and public sector decision-making by presenting a comprehensive overview of key technical challenges where disjunctions between policy goals and ML models commonly arise. We concentrate on pivotal points of the ML pipeline that connect the model to its operational environment, discussing the significance of representative training data and highlighting the importance of a model setup that facilitates effective decision-making. Additionally, we link these challenges with emerging methodological advancements, encompassing causal ML, domain adaptation, uncertainty quantification, and multi-objective optimization, illustrating the path forward for harmonizing ML and public sector objectives.


title: Quantum Geometry Induced Third Order Nonlinear Transport Responses

abstract: Nonlinear transport phenomena offer an exciting probe into the band geometry and symmetry properties of a system. While most studies on nonlinear transport have looked at second-order nonreciprocal responses in noncentrosymmetric systems, the reciprocal third-order effects dominant in centrosymmetric systems remain largely uncharted. Here, we uncover two significant contributions to third-order charge conductivity: one affecting longitudinal resistance and another impacting the Hall effect. We demonstrate that these previously unexplored contributions arise in time-reversal symmetry-broken systems from band geometric quantities such as the Berry curvature and the symplectic connection. We prescribe a detailed symmetry dictionary to facilitate the discovery of these fundamental transport coefficients. Additionally, we unify our quantum kinetic results with the semiclassical wave-packet formalism to unveil all contributions to third-order charge transport. We illustrate our results in antiferromagnetic monolayer SrMnBi$_2$. Our comprehensive study significantly advances the fundamental understanding of reciprocal nonlinear responses.


title: Extending the Cooperative Dual-Task Space in Conformal Geometric Algebra

abstract: In this work, we are presenting an extension of the cooperative dual-task space (CDTS) in conformal geometric algebra. The CDTS was first defined using dual quaternion algebra and is a well established framework for the simplified definition of tasks using two manipulators. By integrating conformal geometric algebra, we aim to further enhance the geometric expressiveness and thus simplify the modeling of various tasks. We show this formulation by first presenting the CDTS and then its extension that is based around a cooperative pointpair. This extension keeps all the benefits of the original formulation that is based on dual quaternions, but adds more tools for geometric modeling of the dual-arm tasks. We also present how this CGA-CDTS can be seamlessly integrated with an optimal control framework in geometric algebra that was derived in previous work. In the experiments, we demonstrate how to model different objectives and constraints using the CGA-CDTS. Using a setup of two Franka Emika robots we then show the effectiveness of our approach using model predictive control in real world experiments.


title: Performance Characterization of NVMe Flash Devices with Zoned Namespaces (ZNS)

abstract: The recent emergence of NVMe flash devices with Zoned Namespace support, ZNS SSDs, represents a significant new advancement in flash storage. ZNS SSDs introduce a new storage abstraction of append-only zones with a set of new I/O (i.e., append) and management (zone state machine transition) commands. With the new abstraction and commands, ZNS SSDs offer more control to the host software stack than a non-zoned SSD for flash management, which is known to be complex (because of garbage collection, scheduling, block allocation, parallelism management, overprovisioning). ZNS SSDs are, consequently, gaining adoption in a variety of applications (e.g., file systems, key-value stores, and databases), particularly latency-sensitive big-data applications. Despite this enthusiasm, there has yet to be a systematic characterization of ZNS SSD performance with its zoned storage model abstractions and I/O operations. This work addresses this crucial shortcoming. We report on the performance features of a commercially available ZNS SSD (13 key observations), explain how these features can be incorporated into publicly available state-of-the-art ZNS emulators, and recommend guidelines for ZNS SSD application developers. All artifacts (code and data sets) of this study are publicly available at https://github.com/stonet-research/NVMeBenchmarks.


title: On a class of algebro-geometric solutions to the Ernst equation

abstract: We discuss a class of solutions to the Ernst equation in terms of theta functions with characteristics. We show that it is necessary to take into account a phase factor, which arises from a shift by a lattice vector, and impose conditions on the characteristics of the theta functions in order for the presented function to solve the Ernst equation for all the considered parameters.


title: Circuit Width Estimation via Effect Typing and Linear Dependency (Long Version)

abstract: Circuit description languages are a class of quantum programming languages in which programs are classical and produce a description of a quantum computation, in the form of a quantum circuit. Since these programs can leverage all the expressive power of high-level classical languages, circuit description languages have been successfully used to describe complex and practical quantum algorithms, whose circuits, however, may involve many more qubits and gate applications than current quantum architectures can actually muster. In this paper, we present Proto-Quipper-R, a circuit description language endowed with a linear dependent type-and-effect system capable of deriving parametric upper bounds on the width of the circuits produced by a program. We prove both the standard type safety results and that the resulting resource analysis is correct with respect to a big-step operational semantics. We also show that our approach is expressive enough to verify realistic quantum algorithms.


title: Direct stellarator coil design using global optimization: application to a comprehensive exploration of quasi-axisymmetric devices

abstract: Many stellarator coil design problems are plagued by multiple minima, where the locally optimal coil sets can sometimes vary substantially in performance. As a result, solving a coil design problem a single time with a local optimization algorithm is usually insufficient and better optima likely do exist. To address this problem, we propose a global optimization algorithm for the design of stellarator coils and outline how to apply box constraints to the physical positions of the coils. The algorithm has a global exploration phase that searches for interesting regions of design space and is followed by three local optimization algorithms that search in these interesting regions (a ``global-to-local" approach). The first local algorithm (phase I), following the globalization phase, is based on near-axis expansions and finds stellarator coils that optimize for quasisymmetry in the neighborhood of a magnetic axis. The second local algorithm (phase II) takes these coil sets and optimizes them for nested flux surfaces and quasisymmetry on a toroidal volume. The final local algorithm (phase III) polishes these configurations for an accurate approximation of quasisymmetry. Using our global algorithm, we study the trade-off between coil length, aspect ratio, rotational transform, and quality of quasi-axisymmetry. The database of stellarators, which comprises approximately 200,000 coil sets, is available online and is called QUASR, for `QUAsi-symmetric Stellarator Repository'.


title: Rooted partitions and number-theoretic functions

abstract: Recently, Merca and Schmidt proved a number of identities relating partitions of an integer with two classic number-theoretic functions, namely the M\"obius function and Euler's totient function. Their demonstrations were mainly algebraic. We give bijective proofs of some of these results. Our main tools are the concept of a rooted partition and an operation which we call the direct sum of a partition and a rooted partition.


title: Web3 Meets AI Marketplace: Exploring Opportunities, Analyzing Challenges, and Suggesting Solutions

abstract: Web3 and AI have been among the most discussed fields over the recent years, with substantial hype surrounding each field's potential to transform the world as we know it. However, as the hype settles, it's evident that neither AI nor Web3 can address all challenges independently. Consequently, the intersection of AI and Web3 is gaining increased attention, emerging as a new field with the potential to address the limitations of each. In this article, we will focus on the integration of web3 and the AI marketplace, where AI services and products can be provided in a decentralized manner (DeAI). A comprehensive review is provided by summarizing the opportunities and challenges on this topic. Additionally, we offer analyses and solutions to address these challenges. We've developed a framework that lets users pay with any kind of cryptocurrency to get AI services. Additionally, they can also enjoy AI services for free on our platform by simply locking up their assets temporarily in the protocol. This unique approach is a first in the industry. Before this, offering free AI services in the web3 community wasn't possible. Our solution opens up exciting opportunities for the AI marketplace in the web3 space to grow and be widely adopted.


title: The allocation of FIFA World Cup slots based on the ranking of confederations

abstract: Qualifications for several world championships in sports are organised such that distinct sets of teams play in their own tournament for a predetermined number of slots. Inspired by a recent work studying the problem with the tools from the literature on fair allocation, this paper provides an alternative approach based on historical matches between these sets of teams. We focus on the FIFA World Cup due to the existence of an official rating system and its recent expansion to 48 teams, as well as to allow for a comparison with the already suggested allocations. Our proposal extends the methodology of the FIFA World Ranking to compare the strengths of five confederations. Various allocations are presented depending on the length of the sample, the set of teams considered, as well as the frequency of rating updates. The results show that more European and South American teams should play in the FIFA World Cup. The ranking of continents by the number of deserved slots is different from the ranking implied by FIFA policy. We recommend allocating at least some slots transparently, based on historical performances, similar to the access list of the UEFA Champions League.


title: Conditions for semi-boundedness and discreteness of the spectrum to Schr\"odinger operator and some nonlinear PDEs

abstract: For Schr\"odinger operator $H=-\Delta+ V({\mathbf x})\cdot$, acting in the space $L_2(\mathbb R^d)\,(d\ge 3)$, necessary and sufficient conditions for semi-boundedness and discreteness of its spectrum.are obtained without assumption that the potential $V({\mathbf x})$ is bounded below. By reduction of the problem to investigation of existence of regular solutions for Riccati PDE necessary conditions for discreteness of the spectrum of operator $H$ are obtained under assumption that it is bounded below. These results are similar to ones obtained by author in \cite{Zel} for the one-dimensional case. Furthermore, sufficient conditions for the semi-boundedness and discreteness of the spectrum of $H$ are obtained in terms of a non-increasing rearrangement, mathematical expectation and standard deviation from the latter for positive part $V_+({\mathbf x})$ of the potential $V({\mathbf x})$ on compact domains that go to infinity, under certain restrictions for its negative part $V_-({\mathbf x})$. Choosing in an optimal way the vector field associated with difference between the potential $V({\mathbf x})$ and its mathematical expectation on the balls that go to infinity, we obtain a condition for semi-boundedness and discreteness of the spectrum for $H$ in terms of solutions of Neumann problem for nonhomogeneous $d/(d-1)$-Laplace equation. This type of optimization refers to a divergence constrained transportation problem.


title: Atom: Low-bit Quantization for Efficient and Accurate LLM Serving

abstract: The growing demand for Large Language Models (LLMs) in applications such as content generation, intelligent chatbots, and sentiment analysis poses considerable challenges for LLM service providers. To efficiently use GPU resources and boost throughput, batching multiple requests has emerged as a popular paradigm; to further speed up batching, LLM quantization techniques reduce memory consumption and increase computing capacity. However, prevalent quantization schemes (e.g., 8-bit weight-activation quantization) cannot fully leverage the capabilities of modern GPUs, such as 4-bit integer operators, resulting in sub-optimal performance. To maximize LLMs' serving throughput, we introduce Atom, a low-bit quantization method that achieves high throughput improvements with negligible accuracy loss. Atom significantly boosts serving throughput by using low-bit operators and considerably reduces memory consumption via low-bit quantization. It attains high accuracy by applying a novel mixed-precision and fine-grained quantization process. We evaluate Atom on 4-bit weight-activation quantization in the serving context. Atom improves end-to-end throughput (token/s) by up to $7.7\times$ compared to the FP16 and by $2.5\times$ compared to INT8 quantization, while maintaining the same latency target.


title: Proving Linear Mode Connectivity of Neural Networks via Optimal Transport

abstract: The energy landscape of high-dimensional non-convex optimization problems is crucial to understanding the effectiveness of modern deep neural network architectures. Recent works have experimentally shown that two different solutions found after two runs of a stochastic training are often connected by very simple continuous paths (e.g., linear) modulo a permutation of the weights. In this paper, we provide a framework theoretically explaining this empirical observation. Based on convergence rates in Wasserstein distance of empirical measures, we show that, with high probability, two wide enough two-layer neural networks trained with stochastic gradient descent are linearly connected. Additionally, we express upper and lower bounds on the width of each layer of two deep neural networks with independent neuron weights to be linearly connected. Finally, we empirically demonstrate the validity of our approach by showing how the dimension of the support of the weight distribution of neurons, which dictates Wasserstein convergence rates is correlated with linear mode connectivity.


title: Using Variational Eigensolvers on Low-End Hardware to Find the Ground State Energy of Simple Molecules

abstract: Key properties of physical systems can be described by the eigenvalues of matrices that represent the system. Computational algorithms that determine the eigenvalues of these matrices exist, but they generally suffer from a loss of performance as the matrix grows in size. This process can be expanded to quantum computation to find the eigenvalues with better performance than the classical algorithms. One application of such an eigenvalue solver is to determine energy levels of a molecule given a matrix representation of its Hamiltonian using the variational principle. Using a variational quantum eigensolver, we determine the ground state energies of different molecules. We focus on the choice of optimization strategy for a Qiskit simulator on low-end hardware. The benefits of several different optimizers were weighed in terms of accuracy in comparison to an analytic classical solution as well as code efficiency.


title: Updated Standard for Secure Satellite Communications: Analysis of Satellites, Attack Vectors, Existing Standards, and Enterprise and Security Architectures

abstract: Satellites play a vital role in remote communication where traditional communication mediums struggle to provide benefits over associated costs and efficiency. In recent years, satellite communication has achieved utter interest in the industry due to the achievement of high data rates through the massive deployment of LEO satellites. Because of the complex diversity in types of satellites, communication methodologies, technological obstacles, environmental limitations, elements in the entire ecosystem, massive financial impact, geopolitical conflict and domination, easier access to satellite communications, and various other reasons, the threat vectors are rising in the threat landscape. To achieve resilience against those, only technological solutions are not enough. An effective approach will be through security standards. However, there is a considerable gap in the industry regarding a generic security standard framework for satellite communication and space data systems. A few countries and space agencies have their own standard framework and private policies. However, many of those are either private, serve the specific requirements of specific missions, or have not been updated for a long time. This project report will focus on identifying, categorizing, comparing, and assessing elements, threat landscape, enterprise security architectures, and available public standards of satellite communication and space data systems. After that, it will utilize the knowledge to propose an updated standard framework for secure satellite communications and space data systems.


title: PACuna: Automated Fine-Tuning of Language Models for Particle Accelerators

abstract: Navigating the landscape of particle accelerators has become increasingly challenging with recent surges in contributions. These intricate devices challenge comprehension, even within individual facilities. To address this, we introduce PACuna, a fine-tuned language model refined through publicly available accelerator resources like conferences, pre-prints, and books. We automated data collection and question generation to minimize expert involvement and make the data publicly available. PACuna demonstrates proficiency in addressing intricate accelerator questions, validated by experts. Our approach shows adapting language models to scientific domains by fine-tuning technical texts and auto-generated corpora capturing the latest developments can further produce pre-trained models to answer some intricate questions that commercially available assistants cannot and can serve as intelligent assistants for individual facilities.


title: Where have all the low-metallicity galaxies gone? Tracing evolution in the mass--metallicity plane since a redshift of 0.7

abstract: Even over relatively recent epochs, galaxies have evolved significantly in their location in the mass-metallicity plane, which must be telling us something about the latter stages of galaxy evolution. In this paper, we analyse data from the LEGA-C survey using semi-analytic spectral and photometric fitting to determine these galaxies' evolution up to their observed epoch at $z \sim 0.7$. We confirm that, at $z \sim 0.7$, many objects already lie on the present-day mass-metallicity relation, but with a significant tail of high-mass low-metallicity galaxies that is not seen in the nearby Universe. Similar modelling of the evolution of galaxies in the nearby MaNGA survey allows us to reconstruct their properties at $z \sim 0.7$. Once selection criteria similar to those of LEGA-C are applied, we reassuringly find that the MaNGA galaxies populate the mass-metallicity plane in the same way at $z \sim 0.7$. Matching the LEGA-C sample to their mass-metallicity "twins" in MaNGA at this redshift, we can explore the likely subsequent evolution of individual LEGA-C galaxies. Galaxies already on the present-day mass--metallicity relation form few more stars and their disks fade, so they become smaller and more bulge-like. By contrast, the high-mass low-metallicity galaxies grow their disks through late star formation, and evolve rapidly to higher metallicities due to a cut-off in their wind-driven mass loss. There are significant indications that this late cut-off is associated with the belated end of strong AGN activity in these objects.


title: Accelerated Bayesian Inference for Molecular Simulations using Local Gaussian Process Surrogate Models

abstract: While Bayesian inference is the gold standard for uncertainty quantification and propagation, its use within physical chemistry encounters formidable computational barriers. These bottlenecks are magnified for modeling data with many independent variables, such as X-ray/neutron scattering patterns and electromagnetic spectra. To address this challenge, we apply a Bayesian framework accelerated via local Gaussian process (LGP) surrogate models. We show that the time-complexity of LGPs scales linearly in the number of independent variables, in stark contrast to the computationally expensive cubic scaling of conventional Gaussian processes. To illustrate the method, we trained a LGP surrogate model on the experimental radial distribution function of liquid neon, and observed a remarkable 288,000-fold speed-up compared to molecular dynamics with insignificant loss in predictive accuracy. We conclude that LGPs are robust and efficient surrogate models, poised to expand the application of Bayesian inference in molecular simulations to a broad spectrum of ever-advancing experimental data.


title: Dynamic Task and Weight Prioritization Curriculum Learning for Multimodal Imagery

abstract: This paper explores post-disaster analytics using multimodal deep learning models trained with curriculum learning method. Studying post-disaster analytics is important as it plays a crucial role in mitigating the impact of disasters by providing timely and accurate insights into the extent of damage and the allocation of resources. We propose a curriculum learning strategy to enhance the performance of multimodal deep learning models. Curriculum learning emulates the progressive learning sequence in human education by training deep learning models on increasingly complex data. Our primary objective is to develop a curriculum-trained multimodal deep learning model, with a particular focus on visual question answering (VQA) capable of jointly processing image and text data, in conjunction with semantic segmentation for disaster analytics using the FloodNet\footnote{https://github.com/BinaLab/FloodNet-Challenge-EARTHVISION2021} dataset. To achieve this, U-Net model is used for semantic segmentation and image encoding. A custom built text classifier is used for visual question answering. Existing curriculum learning methods rely on manually defined difficulty functions. We introduce a novel curriculum learning approach termed Dynamic Task and Weight Prioritization (DATWEP), which leverages a gradient-based method to automatically decide task difficulty during curriculum learning training, thereby eliminating the need for explicit difficulty computation. The integration of DATWEP into our multimodal model shows improvement on VQA performance. Source code is available at https://github.com/fualsan/DATWEP.


title: Comparative Analysis of Plastid Genomes Using Pangenome Research ToolKit (PGR-TK)

abstract: Plastid genomes (plastomes) of angiosperms are of great interest among biologists. High-throughput sequencing is making many such genomes accessible, increasing the need for tools to perform rapid comparative analysis. This exploratory analysis investigates whether the Pangenome Research Tool Kit (PGR-TK) is suitable for analyzing plastomes. After determining the optimal parameters for this tool on plastomes, we use it to compare sequences from each of the genera - Magnolia, Solanum, Fragaria and Cotoneaster, as well as a combined set from 20 rosid genera. PGR-TK recognizes large-scale plastome structures, such as the inverted repeats, among combined sequences from distant rosid families. If the plastid genomes are rotated to the same starting point, it also correctly groups different species from the same genus together in a generated cladogram. The visual approach of PGR-TK provides insights into genome evolution without requiring gene annotations.


title: Magnomechanically controlled Goos-H\"{a}nchen shift in cavity QED

abstract: Phenomena involving interactions among magnons, phonons, and photons in cavity magnomechanical systems have attracted considerable attention recently, owing to their potential applications in the microwave frequency range. One such important effect is the response of a probe field to such tripartite interaction between photon-magnon-phonon. In this paper, we study Goos-H\"{a}nchen shift (GHS) of a reflected probe field in a cavity magnomechanical system. We consider a YIG sphere positioned within a microwave cavity. A microwave control field directly drives the magnon mode in YIG sphere, whereas the cavity is driven via a weak probe field. Our results show that the GHS can be coherently controlled through magnon-phonon coupling via the control field. For instance, GHS can be tuned from positive to negative by tuning the magnon-phonon coupling. Similarly, the effective cavity detuning is another important controlling parameter for GHS. Furthermore, we observe that the enhancement of GHS occurs when magnon-phonon coupling is weak at resonance, and when the magnon-photon coupling is approximately equal to the loss of microwave photons. Our findings may have potential significance in applications related to microwave switching and sensing.


title: Efficient IoT Inference via Context-Awareness

abstract: While existing strategies to execute deep learning-based classification on low-power platforms assume the models are trained on all classes of interest, this paper posits that adopting context-awareness i.e. narrowing down a classification task to the current deployment context consisting of only recent inference queries can substantially enhance performance in resource-constrained environments. We propose a new paradigm, CACTUS, for scalable and efficient context-aware classification where a micro-classifier recognizes a small set of classes relevant to the current context and, when context change happens (e.g., a new class comes into the scene), rapidly switches to another suitable micro-classifier. CACTUS features several innovations, including optimizing the training cost of context-aware classifiers, enabling on-the-fly context-aware switching between classifiers, and balancing context switching costs and performance gains via simple yet effective switching policies. We show that CACTUS achieves significant benefits in accuracy, latency, and compute budget across a range of datasets and IoT platforms.


title: Dynamic V2X Autonomous Perception from Road-to-Vehicle Vision

abstract: Vehicle-to-everything (V2X) perception is an innovative technology that enhances vehicle perception accuracy, thereby elevating the security and reliability of autonomous systems. However, existing V2X perception methods focus on static scenes from mainly vehicle-based vision, which is constrained by sensor capabilities and communication loads. To adapt V2X perception models to dynamic scenes, we propose to build V2X perception from road-to-vehicle vision and present Adaptive Road-to-Vehicle Perception (AR2VP) method. In AR2VP,we leverage roadside units to offer stable, wide-range sensing capabilities and serve as communication hubs. AR2VP is devised to tackle both intra-scene and inter-scene changes. For the former, we construct a dynamic perception representing module, which efficiently integrates vehicle perceptions, enabling vehicles to capture a more comprehensive range of dynamic factors within the scene.Moreover, we introduce a road-to-vehicle perception compensating module, aimed at preserving the maximized roadside unit perception information in the presence of intra-scene changes.For inter-scene changes, we implement an experience replay mechanism leveraging the roadside unit's storage capacity to retain a subset of historical scene data, maintaining model robustness in response to inter-scene shifts. We conduct perception experiment on 3D object detection and segmentation, and the results show that AR2VP excels in both performance-bandwidth trade-offs and adaptability within dynamic environments.


title: Sparse Fr\'echet Sufficient Dimension Reduction with Graphical Structure Among Predictors

abstract: Fr\'echet regression has received considerable attention to model metric-space valued responses that are complex and non-Euclidean data, such as probability distributions and vectors on the unit sphere. However, existing Fr\'echet regression literature focuses on the classical setting where the predictor dimension is fixed, and the sample size goes to infinity. This paper proposes sparse Fr\'echet sufficient dimension reduction with graphical structure among high-dimensional Euclidean predictors. In particular, we propose a convex optimization problem that leverages the graphical information among predictors and avoids inverting the high-dimensional covariance matrix. We also provide the Alternating Direction Method of Multipliers (ADMM) algorithm to solve the optimization problem. Theoretically, the proposed method achieves subspace estimation and variable selection consistency under suitable conditions. Extensive simulations and a real data analysis are carried out to illustrate the finite-sample performance of the proposed method.


title: Photon Bound States in Coupled Waveguides

abstract: Photon bound states have been identified as particular solutions to the scattering of two photons from a single emitter, but from these results the full nature of these states remains elusive. We study a novel, clear and unambiguous signature that these bound states are truly bound. To this end we consider a new configuration of close-by waveguides, each chirally coupled to two-level emitters. We show that in this system the photon bound states behave like rigid molecules, where photons do not tunnel individually but rather collectively, such that there is rarely a single photon in each waveguide. We further identify new classes of bound states in this system.


title: Quest for the golden ratio universality class

abstract: Using mode coupling theory the conditions for all allowed dynamical universality classes for the conserved modes in one-dimensional driven systems are presented in closed form as a function of the stationary currents and their derivatives. With a view on the search for the golden ratio universality class the existence of some families of microscopic models is ruled out a priori by using an Onsager-type macroscopic current symmetry. At equal mean densities of the conserved quantities the golden modes can only appear if the currents are antisymmetric under interchange of the conserved densities and if these densities are correlated, but not in the symmetric case where at equal densities one mode is always diffusive and the second may be either Kardar-Parisi-Zhang (KPZ), modified KPZ, 3/2-L\'evy, or also diffusive. We also show that the predictions of mode coupling theory for a noisy chain of harmonic oscillators are exact.

categories: cond-mat.stat-mech math-ph math.MP nlin.CG


title: Finding Optimal Training Parameters for Quantum Generative Adversarial Networks

abstract: Some of the most impressive achievements of contemporary Machine Learning systems comes from the GAN (Generative Adversarial Network) structure. DALLE-2 and GPT- 3, two of the most impressive and recognizable feats of ML in recent years, were both trained using adversarial techniques. The world of Quantum Computing is already well aware of the value of such techniques on near-term Quantum Hardware: QGANs provide a highly efficient method for loading classical data into a quantum state. We investigate the performance of these techniques in an attempt to determine some of the optimal training parameters in a Qiskit-style Parameterized Circuit QGAN framework.


title: The fractional Laplacian: a primer

abstract: In this note we give a glimpse of the fractional Laplacian. In particular, we bring several definitions of this non-local operator and series of proofs of its properties. It is structured in a way as to show that several of those properties are natural extensions of their local counterparts, with some key differences.


title: Out-of-distribution Object Detection through Bayesian Uncertainty Estimation

abstract: The superior performance of object detectors is often established under the condition that the test samples are in the same distribution as the training data. However, in many practical applications, out-of-distribution (OOD) instances are inevitable and usually lead to uncertainty in the results. In this paper, we propose a novel, intuitive, and scalable probabilistic object detection method for OOD detection. Unlike other uncertainty-modeling methods that either require huge computational costs to infer the weight distributions or rely on model training through synthetic outlier data, our method is able to distinguish between in-distribution (ID) data and OOD data via weight parameter sampling from proposed Gaussian distributions based on pre-trained networks. We demonstrate that our Bayesian object detector can achieve satisfactory OOD identification performance by reducing the FPR95 score by up to 8.19% and increasing the AUROC score by up to 13.94% when trained on BDD100k and VOC datasets as the ID datasets and evaluated on COCO2017 dataset as the OOD dataset.


title: On the Smith-Thom deficiency of Hilbert squares

abstract: We give an expression for the Smith-Thom deficiency of the Hilbert square $X^{[2]}$ of a smooth real algebraic variety $X$ in terms of the rank of a suitable Mayer-Vietoris mapping in several situations. As a consequence, we establish a necessary and sufficient condition for the maximality of $X^{[2]}$ in the case of projective complete intersections, and show that with a few exceptions no real nonsingular projective complete intersection of even dimension has maximal Hilbert square. We also provide new examples of smooth real algebraic varieties with maximal Hilbert square.


title: Simple strategy for simulation of large area of axially symmetric metasurfaces

abstract: Metalenses are composed of nanostructures for focusing light and have been widely explored in many exciting applications. However, their expanding dimensions pose simulation challenges. We propose a method to simulate metalenses in a timely manner using vectorial wave and ray tracing models. We sample the metalens' radial phase gradient and locally approximate it by a linear phase response. Each sampling point is modeled as a binary blazed grating, employing the chosen nanostructure, to build a transfer function set. The metalens transmission or reflection is then obtained by applying the corresponding transfer function to the incoming field on the regions surrounding each sampling point. Fourier optics is used to calculate the scattered fields under arbitrary illumination for the vectorial wave method and a Monte Carlo algorithm is used in the ray tracing formalism. We validated our method against finite difference time domain simulations at 632 nm and we were able to simulate metalenses larger than 3000lambda0 in diameter on a personal computer.


title: Private Variable-Length Coding with Non-zero Leakage

abstract: A private compression design problem is studied, where an encoder observes useful data $Y$, wishes to compress it using variable length code and communicates it through an unsecured channel. Since $Y$ is correlated with private data $X$, the encoder uses a private compression mechanism to design encoded message $\cal C$ and sends it over the channel. An adversary is assumed to have access to the output of the encoder, i.e., $\cal C$, and tries to estimate $X$. Furthermore, it is assumed that both encoder and decoder have access to a shared secret key $W$. In this work, we generalize the perfect privacy (secrecy) assumption and consider a non-zero leakage between the private data $X$ and encoded message $\cal C$. The design goal is to encode message $\cal C$ with minimum possible average length that satisfies non-perfect privacy constraints. We find upper and lower bounds on the average length of the encoded message using different privacy metrics and study them in special cases. For the achievability we use two-part construction coding and extended versions of Functional Representation Lemma. Lastly, in an example we show that the bounds can be asymptotically tight.


title: Three Dogmas, a Puzzle and its Solution

abstract: Modern Logics, as formulated notably by Frege, Russell and Tarski involved basic assumptions about Natural Languages in general and Indo-European Languages in particular, which are contested by Linguists. Based upon those assumptions, formal Languages were designed to overcome what Logicians claimed to be 'defects' of Natural Language. In this paper we show that those assumptions contradict basic principles of Arabic. More specifically: The Logicians ideas, that within Natural Language words refer to objects, 'ToBe'-constructions represent identity statements, Indefinite Descriptions must be replaced by existential quantifiers to form meaningful Sentences and Symbols can have no interpretation-independent meanings, are all falsified using undisputed principles of Arabic. The here presented falsification serves two purposes. First, it is used as a factual basis for the rejection of approaches adopting Semantic axioms of Mathematical Logics as Models for meaning of Arabic Syntax. Second, it shows a way to approach the important computational problem: Satisfiability (SAT). The described way is based upon the realization that parsing Arabic utilizes the existence of 'meaning-particles' within Syntax to efficiently recognize words, phrases and Sentences. Similar meaning-particles are shown to exist in 3CNF formulas, which, when properly handled within the machinery of 3SAT-Solvers, enable structural conditions to be imposed on formulas, sufficient alone to guarantee the efficient production of non-exponentially sized Free Binary Decision Diagrams (FBDDs). We show, why known exponential Lower Bounds on sizes of FBDDs do not contradict our results and reveal practical evidence, obtained for multiplication circuits, supporting our claims.


title: Good Tools are Half the Work: Tool Usage in Deep Learning Projects

abstract: The rising popularity of deep learning (DL) methods and techniques has invigorated interest in the topic of SE4DL (Software Engineering for Deep Learning), the application of software engineering (SE) practices on deep learning software. Despite the novel engineering challenges brought on by the data-driven and non-deterministic paradigm of DL software, little work has been invested into developing DL-targeted SE tools. On the other hand, tools tackling non-SE issues specific to DL are actively used and referred to under the umbrella term "MLOps (Machine Learning Operations) tools". Nevertheless, the available literature supports the utility of conventional SE tooling in DL software development. Building upon previous mining software repositories (MSR) research on tool usage in open-source software works, we identify conventional and MLOps tools adopted in popular applied DL projects that use Python as the main programming language. About 63\% of the GitHub repositories we examined contained at least one conventional SE tool. Software construction tools are the most widely adopted, while the opposite applies to management and maintenance tools. Relatively few MLOps tools were found to be use, with only 20 tools out of a sample of 74 used in at least one repository. The majority of them were open-source rather than proprietary. One of these tools, TensorBoard, was found to be adopted in about half of the repositories in our study. Consequently, the widespread use of conventional SE tooling demonstrates its relevance to DL software. Further research is recommended on the adoption of MLOps tooling, focusing on the relevance of particular tool types, the development of required tools, as well as ways to promote the use of already available tools.


title: Partial Orderings as Heuristic for Multi-Objective Model-Based Reasoning

abstract: Model-based reasoning is becoming increasingly common in software engineering. The process of building and analyzing models helps stakeholders to understand the ramifications of their software decisions. But complex models can confuse and overwhelm stakeholders when these models have too many candidate solutions. We argue here that a technique based on partial orderings lets humans find acceptable solutions via a binary chop needing $O(log(N))$ queries (or less). This paper checks the value of this approach via the iSNEAK partial ordering tool. Pre-experimentally, we were concerned that (a)~our automated methods might produce models that were unacceptable to humans; and that (b)~our human-in-the-loop methods might actual overlooking significant optimizations. Hence, we checked the acceptability of the solutions found by iSNEAK via a human-in-the-loop double-blind evaluation study of 20 Brazilian programmers. We also checked if iSNEAK misses significant optimizations (in a corpus of 16 SE models of size ranging up to 1000 attributes by comparing it against two rival technologies (the genetic algorithms preferred by the interactive search-based SE community; and the sequential model optimizers developed by the SE configuration community~\citep{flash_vivek}). iSNEAK 's solutions were found to be human acceptable (and those solutions took far less time to generate, with far fewer questions to any stakeholder). Significantly, our methods work well even for multi-objective models with competing goals (in this work we explore models with four to five goals). These results motivate more work on partial ordering for many-goal model-based problems.


title: Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations

abstract: Graph-based approaches to nearest neighbor search are popular and powerful tools for handling large datasets in practice, but they have limited theoretical guarantees. We study the worst-case performance of recent graph-based approximate nearest neighbor search algorithms, such as HNSW, NSG and DiskANN. For DiskANN, we show that its "slow preprocessing" version provably supports approximate nearest neighbor search query with constant approximation ratio and poly-logarithmic query time, on data sets with bounded "intrinsic" dimension. For the other data structure variants studied, including DiskANN with "fast preprocessing", HNSW and NSG, we present a family of instances on which the empirical query time required to achieve a "reasonable" accuracy is linear in instance size. For example, for DiskANN, we show that the query procedure can take at least $0.1 n$ steps on instances of size $n$ before it encounters any of the $5$ nearest neighbors of the query.