Search

Linear temporal logic (LTL) and, more generally, $\omega$-regular objectives are alternatives to the traditional discount sum and average reward objectives in reinforcement learning (RL), offering the advantage of greater comprehensibility and hence explainability. In this work, we study the relationship between these objectives. Our main result is that each RL problem for $\omega$-regular objectives can be reduced to a limit-average reward problem in an optimality-preserving fashion, via (finite-memory) reward machines. Furthermore, we demonstrate the efficacy of this approach by showing that optimal policies for limit-average problems can be found asymptotically by solving a sequence of discount-sum problems approximately. Consequently, we resolve an open problem: optimal policies for LTL and $\omega$-regular objectives can be learned asymptotically.

It is well-known that the proximity effect at superconductor/ferromagnet (S/F) interfaces produces damped oscillatory behavior of the Cooper pair wave function within the ferromagnetic regions, which is analogous to the inhomogeneous Fulde-Ferrell-Larkin-Ovchinnikov (FFLO) superconductivity. It is often called mesoscopic FFLO state and gives rise to $0-\pi$-transitions in S/F/S Josephson junctions. This paper offers an analysis of the proximity effect at interfaces between superconductors and magnetic van der Waals (vdW) bilayers. The specific feature of the proximity effect in the vdW bilayer systems is the presence of non-local Cooper pairs. We predict that the mesoscopic FFLO state formed by such pairs is sensitive to the difference between on-site energies of the monolayers composing the bilayer and, thus, can be controlled by applying a gating potential to one of the monolayers. This opens the possibility of implementing gate-controlled $0-\pi$ transitions in Josephson junctions through the magnetic vdW bilayer weak links.

The free monoid with two generators acts on classes (=properties) of morphisms of a category by taking the left or right orthogonal complement with respect to the lifting property, and we define the Quillen negation monoid of the category to be its largest quotient which acts faithfully. We consider the category of topological spaces and show that a number of natural properties of continuous maps are obtained by applying this action to a single example. Namely, for the category of topological spaces we show finiteness of the orbit of the simplest class of morphisms { \emptyset \to {*} }, and we calculate its Schreier graph. The orbit consists of 21 classes of morphisms, and most of these classes are explicitly defined by standard terminology from a typical first year course of topology: a map having a section or dense image; quotient and induced topology; surjective, injective; (maps representing) subsets, closed subsets; disjoint union, disjoint union with a discrete space; each fibre satisfying separation axiom T0 or T1 . Also, the notions of being connected, having a generic point, and being a complete lattice, can be defined in terms of the classes in the orbit. In particular, calculating parts of this orbit can be used in an introductory course as exercises connecting basic definitions in topology and category theory.

Perovskites with the generic composition ABO$_3$ exhibit an enormous variety of quantum states such as magnetism, orbital order, ferroelectricity and superconductivity. Their flexible and comparatively simple structure allows for facile chemical substitution and cube-on-cube combination of different compounds in atomically sharp epitaxial heterostructures. However, already in the bulk, the diverse physical properties of perovskites and their anisotropy are determined by small deviations from the ideal perovskite structure, which are difficult to control. Here we show that directional imprinting of atomic displacements in the antiferromagnetic Mott insulator YVO$_3$ is achieved by depositing epitaxial films on different facets of an isostructural substrate. These facets were chosen such that other control parameters, including strain and polarity mismatch with the overlayer, remain unchanged. We use polarized Raman scattering and spectral ellipsometry to detect signatures of staggered orbital and magnetic order, and demonstrate distinct spin-orbital ordering patterns on different facets. These observations can be attributed to the influence of specific octahedral rotation and cation displacement patterns, which are imprinted by the substrate facet, on the covalency of the bonds and the superexchange interactions in YVO$_3$. Well beyond established strain-engineering strategies, our results show that substrate-induced templating of lattice distortion patterns constitutes a powerful pathway for materials design., Comment: 7 pages, 4 figures, Supplemental Material

The orthogonality dimension of a graph over $\mathbb{R}$ is the smallest integer $d$ for which one can assign to every vertex a nonzero vector in $\mathbb{R}^d$ such that every two adjacent vertices receive orthogonal vectors. For an integer $d$, the $d$-Ortho-Dim$_\mathbb{R}$ problem asks to decide whether the orthogonality dimension of a given graph over $\mathbb{R}$ is at most $d$. We prove that for every integer $d \geq 3$, the $d$-Ortho-Dim$_\mathbb{R}$ problem parameterized by the vertex cover number $k$ admits a kernel with $O(k^{d-1})$ vertices and bit-size $O(k^{d-1} \cdot \log k)$. We complement this result by a nearly matching lower bound, showing that for any $\varepsilon > 0$, the problem admits no kernel of bit-size $O(k^{d-1-\varepsilon})$ unless $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. We further study the kernelizability of orthogonality dimension problems in additional settings, including over general fields and under various structural parameterizations., Comment: 29 pages

Complex oxides are well known to develop oxygen ordering patterns with well defined periodicities, but their interplay with electronic correlations remains largely unexplored. Here, we report resonant and non-resonant x-ray diffraction data indicating a four-unit-cell periodic superstructure related to oxygen vacancy ordering in La$_{2-x}$Ca$_{x}$CuO$_{4}$ films with doping levels from the underdoped ($x = 0.15$) to the extremely overdoped ($x = 0.50$) regime. Whereas the lattice superstructure is temperature independent up to 300 K, a strongly temperature dependent electronic charge density wave (CDW) is observed in the underdoped and slightly overdoped regimes ($x\leq0.20$). The periodicity, in-plane and out-of-plane correlation lengths of the CDW are locked in by the lattice superstructure. Our results highlight the necessity to consider lattice and electronic energetics on equal footing in the high-temperature oxygen-disordered phase to explain oxygen ordering phenomena in complex oxides., Comment: 4 figures, supplement included

We evaluate the robustness of several large language models on multiple datasets. Robustness here refers to the relative insensitivity of the model's answers to meaning-preserving variants of their input. Benchmark datasets are constructed by introducing naturally-occurring, non-malicious perturbations, or by generating semantically equivalent paraphrases of input questions or statements. We further propose a novel metric for assessing a model robustness, and demonstrate its benefits in the non-adversarial scenario by empirical evaluation of several models on the created datasets., Comment: Published in the 2024 Conference on Empirical Methods in Natural Language Processing (EMNLP) findings

Sapphire is a technologically highly relevant material, but it poses many challenges to performing epitaxial thin-film deposition. We have identified and applied the conditions for adsorption-controlled homoepitaxial growth of c-plane sapphire. The films thus grown are atomically smooth, have a controlled termination, and are of outstanding crystallinity. Their chemical purity exceeds that of the substrates. The films exhibit exceptional optical properties such as a single-crystal-like bandgap and a low density of F+ centers.

We present a novel approach to automating the identification of risk factors for diseases from medical literature, leveraging pre-trained models in the bio-medical domain, while tuning them for the specific task. Faced with the challenges of the diverse and unstructured nature of medical articles, our study introduces a multi-step system to first identify relevant articles, then classify them based on the presence of risk factor discussions and, finally, extract specific risk factor information for a disease through a question-answering model. Our contributions include the development of a comprehensive pipeline for the automated extraction of risk factors and the compilation of several datasets, which can serve as valuable resources for further research in this area. These datasets encompass a wide range of diseases, as well as their associated risk factors, meticulously identified and validated through a fine-grained evaluation scheme. We conducted both automatic and thorough manual evaluation, demonstrating encouraging results. We also highlight the importance of improving models and expanding dataset comprehensiveness to keep pace with the rapidly evolving field of medical research., Comment: BioNLP@ACL2024, 12 pages

The Uniform Information Density (UID) hypothesis posits that speakers optimize the communicative properties of their utterances by avoiding spikes in information, thereby maintaining a relatively uniform information profile over time. This paper investigates the impact of UID principles on syntactic reduction, specifically focusing on the optional omission of the connector "that" in English subordinate clauses. Building upon previous research, we extend our investigation to a larger corpus of written English, utilize contemporary large language models (LLMs) and extend the information-uniformity principles by the notion of entropy, to estimate the UID manifestations in the usecase of syntactic reduction choices., Comment: ACL2024 (main conference), 8 pages

We present the Knesset Corpus, a corpus of Hebrew parliamentary proceedings containing over 30 million sentences (over 384 million tokens) from all the (plenary and committee) protocols held in the Israeli parliament between 1998 and 2022. Sentences are annotated with morpho-syntactic information and are associated with detailed meta-information reflecting demographic and political properties of the speakers, based on a large database of parliament members and factions that we compiled. We discuss the structure and composition of the corpus and the various processing steps we applied to it. To demonstrate the utility of this novel dataset we present two use cases. We show that the corpus can be used to examine historical developments in the style of political discussions by showing a reduction in lexical richness in the proceedings over time. We also investigate some differences between the styles of men and women speakers. These use cases exemplify the potential of the corpus to shed light on important trends in the Israeli society, supporting research in linguistics, political science, communication, law, etc., Comment: 28 pages, 7 figures

The Church Problem asks for the construction of a procedure which, given a logical specification A(I,O) between input omega-strings I and output omega-strings O, determines whether there exists an operator F that implements the specification in the sense that A(I, F(I)) holds for all inputs I. Buchi and Landweber provided a procedure to solve the Church problem for MSO specifications and operators computable by finite-state automata. We investigate a generalization of the Church synthesis problem to the continuous time of the non-negative reals. We show that in the continuous time there are phenomena which are very different from the canonical discrete time domain of the natural numbers.

Variational quantum algorithms have become the de facto model for current quantum computations. A prominent example of such algorithms -- the quantum approximate optimization algorithm (QAOA) -- was originally designed for combinatorial optimization tasks, but has been shown to be successful for a variety of other problems. However, for most of these problems the optimal circuit depth remains unknown. One such problem is unstructured search which consists on finding a particular bit string, or equivalently, preparing a state of high overlap with a target state. To bound the optimal QAOA depth for such problem we build on its known solution in a continuous time quantum walk (CTQW). We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity (circuit depth) needed to prepare a state of almost perfect overlap with the target state. The obtained complexity exceeds the Grover's algorithm complexity $O\left(N^\frac{1}{2}\right)$, but remains smaller than $O \left(N^{\frac{1}{2}+c}\right)$ for any $c>0$, which shows quantum advantage of QAOA over classical solutions. We verify our analytical predictions by numerical simulations of up to 68 qubits, which demonstrate that our result overestimates the number of QAOA layers resulting from a trotterized CTQW by at most a polynomial factor., Comment: 10 pages, 3 figures, published version

Among the most insidious attacks on Reinforcement Learning (RL) solutions are training-time attacks (TTAs) that create loopholes and backdoors in the learned behaviour. Not limited to a simple disruption, constructive TTAs (C-TTAs) are now available, where the attacker forces a specific, target behaviour upon a training RL agent (victim). However, even state-of-the-art C-TTAs focus on target behaviours that could be naturally adopted by the victim if not for a particular feature of the environment dynamics, which C-TTAs exploit. In this work, we show that a C-TTA is possible even when the target behaviour is un-adoptable due to both environment dynamics as well as non-optimality with respect to the victim objective(s). To find efficient attacks in this context, we develop a specialised flavour of the DDPG algorithm, which we term gammaDDPG, that learns this stronger version of C-TTA. gammaDDPG dynamically alters the attack policy planning horizon based on the victim's current behaviour. This improves effort distribution throughout the attack timeline and reduces the effect of uncertainty the attacker has about the victim. To demonstrate the features of our method and better relate the results to prior research, we borrow a 3D grid domain from a state-of-the-art C-TTA for our experiments. Code is available at "bit.ly/github-rb-gDDPG"., Comment: 19 pages, 7 figures

With an aging population, numerous assistive and monitoring technologies are under development to enable older adults to age in place. To facilitate aging in place predicting risk factors such as falls, and hospitalization and providing early interventions are important. Much of the work on ambient monitoring for risk prediction has centered on gait speed analysis, utilizing privacy-preserving sensors like radar. Despite compelling evidence that monitoring step length, in addition to gait speed, is crucial for predicting risk, radar-based methods have not explored step length measurement in the home. Furthermore, laboratory experiments on step length measurement using radars are limited to proof of concept studies with few healthy subjects. To address this gap, a radar-based step length measurement system for the home is proposed based on detection and tracking using radar point cloud, followed by Doppler speed profiling of the torso to obtain step lengths in the home. The proposed method was evaluated in a clinical environment, involving 35 frail older adults, to establish its validity. Additionally, the method was assessed in people's homes, with 21 frail older adults who had participated in the clinical assessment. The proposed radar-based step length measurement method was compared to the gold standard Zeno Walkway Gait Analysis System, revealing a 4.5cm/8.3% error in a clinical setting. Furthermore, it exhibited excellent reliability (ICC(2,k)=0.91, 95% CI 0.82 to 0.96) in uncontrolled home settings. The method also proved accurate in uncontrolled home settings, as indicated by a strong agreement (ICC(3,k)=0.81 (95% CI 0.53 to 0.92)) between home measurements and in-clinic assessments.

This paper presents the real-world smart-meter dataset and offers an analysis of solutions derived from the Energy Prediction Technical Challenges, focusing primarily on two key competitions: the IEEE Computational Intelligence Society (IEEE-CIS) Technical Challenge on Energy Prediction from Smart Meter data in 2020 (named EP) and its follow-up challenge at the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE) in 2021 (named as XEP). These competitions focus on accurate energy consumption forecasting and the importance of interpretability in understanding the underlying factors. The challenge aims to predict monthly and yearly estimated consumption for households, addressing the accurate billing problem with limited historical smart meter data. The dataset comprises 3,248 smart meters, with varying data availability ranging from a minimum of one month to a year. This paper delves into the challenges, solutions and analysing issues related to the provided real-world smart meter data, developing accurate predictions at the household level, and introducing evaluation criteria for assessing interpretability. Additionally, this paper discusses aspects beyond the competitions: opportunities for energy disaggregation and pattern detection applications at the household level, significance of communicating energy-driven factors for optimised billing, and emphasising the importance of responsible AI and data privacy considerations. These aspects provide insights into the broader implications and potential advancements in energy consumption prediction. Overall, these competitions provide a dataset for residential energy research and serve as a catalyst for exploring accurate forecasting, enhancing interpretability, and driving progress towards the discussion of various aspects such as energy disaggregation, demand response programs or behavioural interventions.

Semantic consistency of a language model is broadly defined as the model's ability to produce semantically-equivalent outputs, given semantically-equivalent inputs. We address the task of assessing question-answering (QA) semantic consistency of contemporary large language models (LLMs) by manually creating a benchmark dataset with high-quality paraphrases for factual questions, and release the dataset to the community. We further combine the semantic consistency metric with additional measurements suggested in prior work as correlating with LLM QA accuracy, for building and evaluating a framework for factual QA reference-less performance prediction -- predicting the likelihood of a language model to accurately answer a question. Evaluating the framework on five contemporary LLMs, we demonstrate encouraging, significantly outperforming baselines, results., Comment: EMNLP2023 GEM workshop, 17 pages

Shock wave reflection from a rigid wall has been thoroughly studied in the Newtonian limit, simplifying the problem by analyzing it in a steady-state frame, $S'$, where the point $P$ of the shock's intersection with the wall is at rest. However, a "super-luminal" regime emerges when the velocity of point $P$ ($v_p$) exceeds the speed of light ($v_p>c$), where no steady-state frame $S'$ exists. It occurs predominantly in the relativistic regime, relevant in astrophysics, where it encompasses nearly all of the shock incidence angles. To study this regime, we introduce a new approach. We formulate integral conservation laws in the lab frame $S$ (where the unshocked fluid is at rest) for regular reflection (RR), using two methods: a. fixed volume analysis and b. fixed fluid analysis. We show the equivalence between the two methods, and also to the steady-state oblique shock jump conditions in frame $S'$ in the sub-luminal regime ($v_p

Shocks are ubiquitous in astrophysical sources, many of which involve relativistic bulk motions, leading to the formation of relativistic shocks. Such relativistic shocks have so far been studied mainly in one dimension, for simplicity, but the complex nature of the relevant astrophysical flows often requires higher dimensional studies. Here we study the two-dimensional problem of the reflection of a planer shock off of a wall for a general incidence angle and a cold unshocked medium. We use primarily relativistic hydrodynamic numerical simulations, and elaborately compare the results to an analytic treatment. The simulations are performed both in the rest frame S of the unshocked fluid, where the dimensionless proper speed of the singly shocked fluid is $u_1=\Gamma_1\beta_1$ and the shock incidence angle is $\alpha_1$, and in the rest frame S$^\prime$ of the point P of intersection of the incident shock and the wall for regular reflection (RR). Good agreement is obtained between the simulations in these two frames and with the analytic solution. The establishment of a steady flow in frame S$^\prime$ is explored, along with the transition between the strong and weak shock RR solutions. The transition line between RR and Mach reflection (MR) is studied numerically in the $u_1$-$\alpha_1$ plane and found to coincide with the analytic detachment/sonic line. The flow properties along the sonic line are investigated in detail focusing on how they vary between the Newtonian and relativistic limits., Comment: Submitted to MNRAS

Variational quantum algorithms have emerged as a cornerstone of contemporary quantum algorithms research. Practical implementations of these algorithms, despite offering certain levels of robustness against systematic errors, show a decline in performance due to the presence of stochastic errors and limited coherence time. In this work, we develop a recipe for mitigating quantum gate errors for variational algorithms using zero-noise extrapolation. We introduce an experimentally amenable method to control error strength in the circuit. We utilize the fact that gate errors in a physical quantum device are distributed inhomogeneously over different qubits and qubit pairs. As a result, one can achieve different circuit error sums based on the manner in which abstract qubits in the circuit are mapped to a physical device. We find that the estimated energy in the variational approach is approximately linear with respect to the circuit error sum (CES). Consequently, a linear fit through the energy-CES data, when extrapolated to zero CES, can approximate the energy estimated by a noiseless variational algorithm. We demonstrate this numerically and investigate the applicability range of the technique.

This work addresses the challenge of patrolling regular grid graphs of any dimension using a single mobile agent with minimal memory and limited sensing range. We show that it is impossible to patrol some grid graphs with $0$ bits of memory, regardless of sensing range, and give an exact characterization of those grid graphs that can be patrolled with $0$ bits of memory and sensing range $V$. On the other hand, we show that an algorithm exists using $1$ bit of memory and $V=1$ that patrols any $d$-dimensional grid graph. This result is surprising given that the agent must be able to move in $2d$ distinct directions to patrol, while $1$ bit of memory allows specifying only two directions per sensory input. Our $1$-bit patrolling algorithm handles this by carefully exploiting a small state-space to access all the needed directions while avoiding getting stuck. Overall, our results give concrete evidence that extremely little memory is needed for patrolling highly regular environments like grid graphs compared to arbitrary graphs. The techniques we use, such as partitioning the environment into sensing regions and exploiting distinct coordinates resulting from higher-dimensionality, may be applicable to analyzing the space complexity of patrolling in other types of regular environments as well.

Data drift is the change in model input data that is one of the key factors leading to machine learning models performance degradation over time. Monitoring drift helps detecting these issues and preventing their harmful consequences. Meaningful drift interpretation is a fundamental step towards effective re-training of the model. In this study we propose an end-to-end framework for reliable model-agnostic change-point detection and interpretation in large task-oriented dialog systems, proven effective in multiple customer deployments. We evaluate our approach and demonstrate its benefits with a novel variant of intent classification training dataset, simulating customer requests to a dialog system. We make the data publicly available., Comment: ACL2023 industry track (9 pages)

This paper considers the phenomenon where a single probe to a target generates multiple, sometimes numerous, packets in response -- which we term "blowback". Understanding blowback is important because attackers can leverage it to launch amplified denial of service attacks by redirecting blowback towards a victim. Blowback also has serious implications for Internet researchers since their experimental setups must cope with bursts of blowback traffic. We find that tens of thousands, and in some protocols, hundreds of thousands, of hosts generate blowback, with orders of magnitude amplification on average. In fact, some prolific blowback generators produce millions of response packets in the aftermath of a single probe. We also find that blowback generators are fairly stable over periods of weeks, so once identified, many of these hosts can be exploited by attackers for a long time.

We apply the theory of operadic Koszul duality to provide a cofibrant resolution of the colored operad whose algebras are prefactorization algebras on a fixed space M. his allows us to describe a notion of prefactorization algebra up to homotopy as well as morphisms up to homotopy between such objects. We make explicit these notions for several special M, such as certain finite topological spaces, or the real line., Comment: To appear in Res. Math. Sci

This paper investigates policy resilience to training-environment poisoning attacks on reinforcement learning (RL) policies, with the goal of recovering the deployment performance of a poisoned RL policy. Due to the fact that the policy resilience is an add-on concern to RL algorithms, it should be resource-efficient, time-conserving, and widely applicable without compromising the performance of RL algorithms. This paper proposes such a policy-resilience mechanism based on an idea of knowledge sharing. We summarize the policy resilience as three stages: preparation, diagnosis, recovery. Specifically, we design the mechanism as a federated architecture coupled with a meta-learning manner, pursuing an efficient extraction and sharing of the environment knowledge. With the shared knowledge, a poisoned agent can quickly identify the deployment condition and accordingly recover its policy performance. We empirically evaluate the resilience mechanism for both model-based and model-free RL algorithms, showing its effectiveness and efficiency in restoring the deployment performance of a poisoned policy.

We study deterministic online embeddings of metrics spaces into normed spaces and into trees against an adaptive adversary. Main results include a polynomial lower bound on the (multiplicative) distortion of embedding into Euclidean spaces, a tight exponential upper bound on embedding into the line, and a $(1+\epsilon)$-distortion embedding in $\ell_\infty$ of a suitably high dimension., Comment: 15 pages, no figures