Search

We consider the problem of counting the copies of a length-$k$ pattern $\sigma$ in a sequence $f \colon [n] \to \mathbb{R}$, where a copy is a subset of indices $i_1 < \ldots < i_k \in [n]$ such that $f(i_j) < f(i_\ell)$ if and only if $\sigma(j) < \sigma(\ell)$. This problem is motivated by a range of connections and applications in ranking, nonparametric statistics, combinatorics, and fine-grained complexity, especially when $k$ is a small fixed constant. Recent advances have significantly improved our understanding of counting and detecting patterns. Guillemot and Marx [2014] demonstrated that the detection variant is solvable in $O(n)$ time for any fixed $k$. Their proof has laid the foundations for the discovery of the twin-width, a concept that has notably advanced parameterized complexity in recent years. Counting, in contrast, is harder: it has a conditional lower bound of $n^{\Omega(k / \log k)}$ [Berendsohn, Kozma, and Marx 2019] and is expected to be polynomially harder than detection as early as $k = 4$, given its equivalence to counting $4$-cycles in graphs [Dudek and Gawrychowski, 2020]. In this work, we design a deterministic near-linear time $(1+\varepsilon)$-approximation algorithm for counting $\sigma$-copies in $f$ for all $k \leq 5$. Combined with the conditional lower bound for $k=4$, this establishes the first known separation between approximate and exact algorithms for pattern counting. Interestingly, our algorithm leverages the Birg\'e decomposition -- a sublinear tool for monotone distributions widely used in distribution testing -- which, to our knowledge, has not been applied in a pattern counting context before.

Supervised machine learning often encounters concept drift, where the data distribution changes over time, degrading model performance. Existing drift detection methods focus on identifying these shifts but often overlook the challenge of acquiring labeled data for model retraining after a shift occurs. We present the Strategy for Drift Sampling (SUDS), a novel method that selects homogeneous samples for retraining using existing drift detection algorithms, thereby enhancing model adaptability to evolving data. SUDS seamlessly integrates with current drift detection techniques. We also introduce the Harmonized Annotated Data Accuracy Metric (HADAM), a metric that evaluates classifier performance in relation to the quantity of annotated data required to achieve the stated performance, thereby taking into account the difficulty of acquiring labeled data. Our contributions are twofold: SUDS combines drift detection with strategic sampling to improve the retraining process, and HADAM provides a metric that balances classifier performance with the amount of labeled data, ensuring efficient resource utilization. Empirical results demonstrate the efficacy of SUDS in optimizing labeled data use in dynamic environments, significantly improving the performance of machine learning applications in real-world scenarios. Our code is open source and available at https://github.com/cfellicious/SUDS/, Comment: 9 pages, 5 tables, 3 figures

We consider a pseudo-parabolic approximations to the Navier-Stokes equations and prove existence and uniqueness of smooth solutions. We also consider convergence of family of pseudo-parabolic approximations.

Understanding the dehydrogenation of transition metal oxide surfaces under electrochemical potential is critical to the control of important chemical processes such as the oxygen evolution reaction (OER). Using first principles computations, we model the thermodynamic dehydrogenation process on RuO$_2$(110) and compare the results to experimental cyclic voltammetry (CV) on single crystal. We use a cluster expansion model trained on *ab initio* energy data coupled with Monte Carlo (MC) sampling to derive the macroscopic electrochemical observables, i.e., experimental CV, from the energetics of different hydrogen coverage microstates on well-defined RuO$_2$(110). Our model reproduces the unique "two-peaks" cyclic voltammogram observed experimentally with current density peak positions and shapes in good qualitative agreement. We show that RuO$_2$(110) starts as a water-covered surface with hydrogen on bridge (BRG) and coordination-unsaturated sites (CUS) at low potential (less than 0.4 V vs. reversible hydrogen electrode, RHE). As the potential increases, the hydrogens on BRG desorb, becoming the main contributor to the first CV peak with smaller contributions from CUS. When all BRG hydrogens are desorbed (before 1.2 V vs. RHE), the remaining CUS hydrogens desorb abruptly in a very small potential window leading to the sharp second peak observed during CV. Our work shows that above 1.23 V, the OER proceeds on a fully dehydrogenated RuO$_2$(110) surface., Comment: 20 pages, 6 figures in Main Text, 3 figures in Supplementary Info

We present Flotta, a Federated Learning framework designed to train machine learning models on sensitive data distributed across a multi-party consortium conducting research in contexts requiring high levels of security, such as the biomedical field. Flotta is a Python package, inspired in several aspects by Apache Spark, which provides both flexibility and security and allows conducting research using solely machines internal to the consortium. In this paper, we describe the main components of the framework together with a practical use case to illustrate the framework's capabilities and highlight its security, flexibility and user-friendliness., Comment: Accepted for publication at FLTA 2024: The 2nd IEEE International Conference on Federated Learning Technologies and Applications

The SetCover problem has been extensively studied in many different models of computation, including parallel and distributed settings. From an approximation point of view, there are two standard guarantees: an $O(\log \Delta)$-approximation (where $\Delta$ is the maximum set size) and an $O(f)$-approximation (where $f$ is the maximum number of sets containing any given element). In this paper, we introduce a new, surprisingly simple, model-independent approach to solving SetCover in unweighted graphs. We obtain multiple improved algorithms in the MPC and CRCW PRAM models. First, in the MPC model with sublinear space per machine, our algorithms can compute an $O(f)$ approximation to SetCover in $\hat{O}(\sqrt{\log \Delta} + \log f)$ rounds, where we use the $\hat{O}(x)$ notation to suppress $\mathrm{poly} \log x$ and $\mathrm{poly} \log \log n$ terms, and a $O(\log \Delta)$ approximation in $O(\log^{3/2} n)$ rounds. Moreover, in the PRAM model, we give a $O(f)$ approximate algorithm using linear work and $O(\log n)$ depth. All these bounds improve the existing round complexity/depth bounds by a $\log^{\Omega(1)} n$ factor. Moreover, our approach leads to many other new algorithms, including improved algorithms for the HypergraphMatching problem in the MPC model, as well as simpler SetCover algorithms that match the existing bounds.

Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ such that for any pair of distinct vertices $s, t \in V$, the Min-$s$-$t$-Cut on $T$ is also a Min-$s$-$t$-Cut on $G$. Computing a Gomory-Hu tree is a well-studied problem in graph algorithms and has received considerable attention. In particular, a long line of work recently culminated in constructing a Gomory-Hu tree in almost linear time [Abboud, Li, Panigrahi and Saranurak, FOCS 2023]. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s, t \in V$ with high probability. Our error bound is essentially optimal, as [Dalirrooyfard, Mitrovi\'c and Nevmyvaka, NeurIPS 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $\Omega(n)$ additive error even with $(1, 0.1)$-DP and allowing for a multiplicative error term. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth and Ullman, TCC 2012] and $O(\sqrt{mn} \cdot \text{polylog}(n/\delta) / \varepsilon)$ for $(\varepsilon, \delta)$-DP [Liu, Upadhyay and Zou, SODA 2024], both of which are implied by differential private algorithms that preserve all cuts in the graph. An important technical ingredient of our main result is an $\varepsilon$-DP algorithm for computing minimum Isolating Cuts with $\tilde{O}(n / \varepsilon)$ additive error, which may be of independent interest.

As a new practical and economical solution to the aging problem of overhead line (OHL) assets, the technical policies of most power grid companies in the world experienced a gradual transition from scheduled preventive maintenance to a risk-based approach in asset management. Even though the accumulation of contamination is predictable within a certain degree, there are currently no effective ways to identify the risk of the insulator flashover in order to plan its replacement. This paper presents a novel machine learning (ML) based method for estimating the flashover probability of the cup-and-pin glass insulator string. The proposed method is based on the Extreme Gradient Boosting (XGBoost) supervised ML model, in which the leakage current (LC) features and applied voltage are used as the inputs. The established model can estimate the critical flashover voltage (U50%) for various designs of OHL insulators with different voltage levels. The proposed method is also able to accurately determine the condition of the insulator strings and instruct asset management engineers to take appropriate actions., Comment: 10 pages, 9 figures

Stanley and Grinberg introduced the symmetric function associated to digraphs, called the Redei-Berge symmetric function. In [8] is shown that this symmetric function arises from a suitable structure of combinatorial Hopf algebra on digraphs. In this paper, we introduce two new combinatorial Hopf algebras of posets and permutations and define corresponding Redei-Berge functions for them. By using both theories, of symmetric functions and of combinatorial Hopf algebras, we prove many properties of the Redei-Berge function. These include some forms of deletion-contraction property, which make it similar to the chromatic symmetric function. We also find some invariants of digraphs that are detected by the Redei-Berge function.

A comprehensive set of muon spin spectroscopy and neutron scattering measurements supported by ab-initio and model Hamiltonian simulations have been used to investigate the magnetic ground state of Na$_2$PrO$_3$. $\mu$SR reveals N\'eel antiferromagnetic order below $T_{\rm N}\! \sim\! 4.9$ K, with a small static magnetic moment $m_{\rm static}\!\leq \! 0.22$~$\mu_{\rm B}/{\rm Pr}$ collinearly aligned along the $c-$axis. Inelastic neutron measurements reveal the full spectrum of crystal field excitations and confirm that the Pr$^{4+}$ ground state wave function deviates significantly from the $\Gamma_7$ limit relevant to the Kitaev model. Single and two magnon excitations are observed in the ordered state below $T_N=4.6$ K and are well described by non-linear spin wave theory from the N\'eel state using a magnetic Hamiltonian with Heisenberg exchange $J=1$ meV and symmetric anisotropic exchange $\Gamma/J=0.1$, corresponding to an XY model. Intense two magnon excitations are accounted for by $g$-factor anisotropy $g_\mathrm{z}/g_\pm = 1.29$. A fluctuating moment $\delta m^2 = 0.57(22)$ $\mu_{\rm B}^2/{\rm Pr}$ extracted from the energy and momentum integrated inelastic neutron signal is reduced from expectations for a local $J=1/2$ moment with average $g$-factor $g_{\rm avg}\approx 1.1$. Together, the results demonstrate that the small moment in Na$_2$PrO$_3$ arises from crystal field and covalency effects and that the material does not exhibit significant quantum fluctuations..

The choice of embedding model is a crucial step in the design of Retrieval Augmented Generation (RAG) systems. Given the sheer volume of available options, identifying clusters of similar models streamlines this model selection process. Relying solely on benchmark performance scores only allows for a weak assessment of model similarity. Thus, in this study, we evaluate the similarity of embedding models within the context of RAG systems. Our assessment is two-fold: We use Centered Kernel Alignment to compare embeddings on a pair-wise level. Additionally, as it is especially pertinent to RAG systems, we evaluate the similarity of retrieval results between these models using Jaccard and rank similarity. We compare different families of embedding models, including proprietary ones, across five datasets from the popular Benchmark Information Retrieval (BEIR). Through our experiments we identify clusters of models corresponding to model families, but interestingly, also some inter-family clusters. Furthermore, our analysis of top-k retrieval similarity reveals high-variance at low k values. We also identify possible open-source alternatives to proprietary models, with Mistral exhibiting the highest similarity to OpenAI models.

The process of annotating data within the legal sector is filled with distinct challenges that differ from other fields, primarily due to the inherent complexities of legal language and documentation. The initial task usually involves selecting an appropriate raw dataset that captures the intricate aspects of legal texts. Following this, extracting text becomes a complicated task, as legal documents often have complex structures, footnotes, references, and unique terminology. The importance of data cleaning is magnified in this context, ensuring that redundant information is eliminated while maintaining crucial legal details and context. Creating comprehensive yet straightforward annotation guidelines is imperative, as these guidelines serve as the road map for maintaining uniformity and addressing the subtle nuances of legal terminology. Another critical aspect is the involvement of legal professionals in the annotation process. Their expertise is valuable in ensuring that the data not only remains contextually accurate but also adheres to prevailing legal standards and interpretations. This paper provides an expanded view of these challenges and aims to offer a foundational understanding and guidance for researchers and professionals engaged in legal data annotation projects. In addition, we provide links to our created and fine-tuned datasets and language models. These resources are outcomes of our discussed projects and solutions to challenges faced while working on them.

Rhetorical figures play a major role in our everyday communication as they make text more interesting, more memorable, or more persuasive. Therefore, it is important to computationally detect rhetorical figures to fully understand the meaning of a text. We provide a comprehensive overview of computational approaches to lesser-known rhetorical figures. We explore the linguistic and computational perspectives on rhetorical figures, emphasizing their significance for the domain of Natural Language Processing. We present different figures in detail, delving into datasets, definitions, rhetorical functions, and detection approaches. We identified challenges such as dataset scarcity, language limitations, and reliance on rule-based methods., Comment: Submitted to ACM Computing Surveys. 35 pages

This study investigates the metacognitive capabilities of Large Language Models relative to human metacognition in the context of the International Coaching Federation ICF mimicking exam, a situational judgment test related to coaching competencies. Using a mixed method approach, we assessed the metacognitive performance, including sensitivity, accuracy in probabilistic predictions, and bias, of human participants and five advanced LLMs (GPT-4, Claude-3-Opus 3, Mistral Large, Llama 3, and Gemini 1.5 Pro). The results indicate that LLMs outperformed humans across all metacognitive metrics, particularly in terms of reduced overconfidence, compared to humans. However, both LLMs and humans showed less adaptability in ambiguous scenarios, adhering closely to predefined decision frameworks. The study suggests that Generative AI can effectively engage in human-like metacognitive processing without conscious awareness. Implications of the study are discussed in relation to development of AI simulators that scaffold cognitive and metacognitive aspects of mastering coaching competencies. More broadly, implications of these results are discussed in relation to development of metacognitive modules that lead towards more autonomous and intuitive AI systems.

We introduce two classes of graphs - suns and dumbbells, both with few variations and explore their chromatic symmetric function and its $e$-positivity. We also give many connections of these two classes with other classes of connected graphs.

We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector $\pi \in \mathbb{R}^n$ for a graph under a sequence of edge insertions and deletions. Our main result is a complete characterization of the complexity of dynamic PageRank maintenance for both multiplicative and additive ($L_1$) approximations. First, we establish matching lower and upper bounds for maintaining additive approximate PageRank in both incremental and decremental settings. In particular, we demonstrate that in the worst-case $(1/\alpha)^{\Theta(\log \log n)}$ update time is necessary and sufficient for this problem, where $\alpha$ is the desired additive approximation. On the other hand, we demonstrate that the commonly employed ForwardPush approach performs substantially worse than this optimal runtime. Specifically, we show that ForwardPush requires $\Omega(n^{1-\delta})$ time per update on average, for any $\delta > 0$, even in the incremental setting. For multiplicative approximations, however, we demonstrate that the situation is significantly more challenging. Specifically, we prove that any algorithm that explicitly maintains a constant factor multiplicative approximation of the PageRank vector of a directed graph must have amortized update time $\Omega(n^{1-\delta})$, for any $\delta > 0$, even in the incremental setting, thereby resolving a 13-year old open question of Bahmani et al.~(VLDB 2010). This sharply contrasts with the undirected setting, where we show that $\rm{poly}\ \log n$ update time is feasible, even in the fully dynamic setting under oblivious adversary.

The creation of high-quality human-labeled image-caption datasets presents a significant bottleneck in the development of Visual-Language Models (VLMs). In this work, we investigate an approach that leverages the strengths of Large Language Models (LLMs) and image generation models to create synthetic image-text pairs for efficient and effective VLM training. Our method employs a pretrained text-to-image model to synthesize image embeddings from captions generated by an LLM. Despite the text-to-image model and VLM initially being trained on the same data, our approach leverages the image generator's ability to create novel compositions, resulting in synthetic image embeddings that expand beyond the limitations of the original dataset. Extensive experiments demonstrate that our VLM, finetuned on synthetic data achieves comparable performance to models trained solely on human-annotated data, while requiring significantly less data. Furthermore, we perform a set of analyses on captions which reveals that semantic diversity and balance are key aspects for better downstream performance. Finally, we show that synthesizing images in the image embedding space is 25\% faster than in the pixel space. We believe our work not only addresses a significant challenge in VLM training but also opens up promising avenues for the development of self-improving multi-modal models., Comment: 9 pages, 6 figures

In this report, we introduce the Gemini 1.5 family of models, representing the next generation of highly compute-efficient multimodal models capable of recalling and reasoning over fine-grained information from millions of tokens of context, including multiple long documents and hours of video and audio. The family includes two new models: (1) an updated Gemini 1.5 Pro, which exceeds the February version on the great majority of capabilities and benchmarks; (2) Gemini 1.5 Flash, a more lightweight variant designed for efficiency with minimal regression in quality. Gemini 1.5 models achieve near-perfect recall on long-context retrieval tasks across modalities, improve the state-of-the-art in long-document QA, long-video QA and long-context ASR, and match or surpass Gemini 1.0 Ultra's state-of-the-art performance across a broad set of benchmarks. Studying the limits of Gemini 1.5's long-context ability, we find continued improvement in next-token prediction and near-perfect retrieval (>99%) up to at least 10M tokens, a generational leap over existing models such as Claude 3.0 (200k) and GPT-4 Turbo (128k). Finally, we highlight real-world use cases, such as Gemini 1.5 collaborating with professionals on completing their tasks achieving 26 to 75% time savings across 10 different job categories, as well as surprising new capabilities of large language models at the frontier; when given a grammar manual for Kalamang, a language with fewer than 200 speakers worldwide, the model learns to translate English to Kalamang at a similar level to a person who learned from the same content.

Given a graph with positive and negative edge labels, the correlation clustering problem aims to cluster the nodes so to minimize the total number of between-cluster positive and within-cluster negative edges. This problem has many applications in data mining, particularly in unsupervised learning. Inspired by the prevalence of large graphs and constantly changing data in modern applications, we study correlation clustering in dynamic, parallel (MPC), and local computation (LCA) settings. We design an approach that improves state-of-the-art runtime complexities in all these settings. In particular, we provide the first fully dynamic algorithm that runs in an expected amortized constant time, without any dependence on the graph size. Moreover, our algorithm essentially matches the approximation guarantee of the celebrated Pivot algorithm.

The thesis focuses on developing a data-driven algorithm, based on machine learning, to solve the stochastic alternating current (AC) chance-constrained (CC) Optimal Power Flow (OPF) problem. Although the AC CC-OPF problem has been successful in academic circles, it is highly nonlinear and computationally demanding, which limits its practical impact. The proposed approach aims to address this limitation and demonstrate its empirical efficiency through applications to multiple IEEE test cases. To solve the non-convex and computationally challenging CC AC-OPF problem, the proposed approach relies on a machine learning Gaussian process regression (GPR) model. The full Gaussian process (GP) approach is capable of learning a simple yet non-convex data-driven approximation to the AC power flow equations that can incorporate uncertain inputs. The proposed approach uses various approximations for GP-uncertainty propagation. The full GP CC-OPF approach exhibits highly competitive and promising results, outperforming the state-of-the-art sample-based chance constraint approaches. To further improve the robustness and complexity/accuracy trade-off of the full GP CC-OPF, a fast data-driven setup is proposed. This setup relies on the sparse and hybrid Gaussian processes (GP) framework to model the power flow equations with input uncertainty., Comment: 112 pages, 29 figures

A supposedly nonmagnetic 5d$^1$ double perosvkite oxide is investigated by a combination of spectroscopic and theoretical methods, namely resonant inelastic X-ray scattering, X-ray absorption spectroscopy, magnetic circular dichroism, and multiplet ligand field calculations. We found that the large spin-orbit coupling admixes the 5d $t_{2g}$ and $e_g$ orbitals, covalency raises the 5d population well above the nominal value, and the local symmetry is lower than $O_h$. The obtained electronic interactions account for the finite magnetic moment of Os in this compound and, in general, of 5d$^1$ ions. Our results provide direct evidence of elusive Jahn-Teller distortions, hinting at a strong electron-lattice coupling.

Finding min $s$-$t$ cuts in graphs is a basic algorithmic tool with applications in image segmentation, community detection, reinforcement learning, and data clustering. In this problem, we are given two nodes as terminals, and the goal is to remove the smallest number of edges from the graph so that these two terminals are disconnected. We study the complexity of differential privacy for the min $s$-$t$ cut problem and show nearly tight lower and upper bounds where we achieve privacy at no cost for running time efficiency. We also develop a differentially private algorithm for the multiway $k$-cut problem, in which we are given $k$ nodes as terminals that we would like to disconnect. As a function of $k$, we obtain privacy guarantees that are exponentially more efficient than applying the advanced composition theorem to known algorithms for multiway $k$-cut. Finally, we empirically evaluate the approximation of our differentially private min $s$-$t$ cut algorithm and show that it almost matches the quality of the output of non-private ones.

Finding dense subgraphs is a fundamental algorithmic tool in data mining, community detection, and clustering. In this problem, one aims to find an induced subgraph whose edge-to-vertex ratio is maximized. We study the directed case of this question in the context of semi-streaming and massively parallel algorithms. In particular, we show that it is possible to find a $(2+\epsilon)$ approximation on randomized streams even in a single pass by using $O(n \cdot {\rm poly} \log n)$ memory on $n$-vertex graphs. Our result improves over prior works, which were designed for arbitrary-ordered streams: the algorithm by Bahmani et al. (VLDB 2012) which uses $O(\log n)$ passes, and the work by Esfandiari et al. (2015) which makes one pass but uses $O(n^{3/2})$ memory. Moreover, our techniques extend to the Massively Parallel Computation model yielding $O(1)$ rounds in the super-linear and $O(\sqrt{\log n})$ rounds in the nearly-linear memory regime. This constitutes a quadratic improvement over state-of-the-art bounds by Bahmani et al. (VLDB 2012 and WAW 2014), which require $O(\log n)$ rounds even in the super-linear memory regime. Finally, we empirically evaluate our single-pass semi-streaming algorithm on $6$ benchmarks and show that, even on non-randomly ordered streams, the quality of its output is essentially the same as that of Bahmani et al. (VLDB 2012) while it is $2$ times faster on large graphs.

This study investigates the $L^1_{\operatorname{loc}}$ compactness of velocity averages of sequences of solutions $\{u_n\}$ for a class of kinetic equations. The equations are examined within both deterministic and stochastic heterogeneous environments. The primary objective is to deduce velocity averaging results under conditions on $u_n$ and the drift ${\mathfrak f}={\mathfrak f}(t,{\boldsymbol x},{\boldsymbol \lambda})$ that are more lenient than those stipulated in previous studies. The main outcome permits the inclusion of highly irregular drift vectors ${\mathfrak f} \in L^q$ that adhere to a general non-degeneracy condition. Moreover, the sequence $\{u_n\}$ is uniformly bounded in $L^p$ -- for an exponent $p$ allowed to be strictly smaller than $2$ -- under the requirement $\frac{1}{p} + \frac{1}{q} < 1$. Resolving the matter of strong compactness in velocity averages, considering these assumptions, has remained an open problem for a long time. The cornerstone of our work's progress lies in the strategic employment of the broader concept of $H$-distributions, moving beyond the traditional reliance on $H$-measures. Notably, our study represents one of the first significant uses of $H$-distributions in this context.

Image inpainting involves filling in damaged or missing regions of an image by utilizing information from the surrounding areas. In this paper, we investigate a highly nonlinear partial differential equation inspired by the modified Cahn-Hilliard equation. Instead of using standard potentials that depend solely on pixel intensities, we consider morphological image enhancement filters that are based on a variant of the shock filter: : \begin{align*} \partial_t u &= \Delta \left(-\nu \arctan(\Delta u)|\nabla u| - \mu \Delta u \right)+ \lambda(u_0 - u). \end{align*} This is referred to as the Shock Filter Cahn-Hilliard Equation. This equation is nonlinear with respect to the second-order derivative, which poses significant mathematical challenges. To address these, we make use of a specific approximation argument, establishing the existence of a family of approximate solutions through the Leray-Schauder fixed point theorem and the Aubin-Lions lemma. In the limit, we obtain a solution strategy wherein we can prove the existence and uniqueness of solutions. Proving the latter involves the use of Young measures and Kruzhkov entropy type-admissibility conditions. Additionally, we use a numerical method based on the convexity splitting idea to approximate solutions of the nonlinear partial differential equation and achieve fast inpainting results. To demonstrate the effectiveness of our approach, we apply our method to standard binary images and compare it with variations of the Cahn-Hilliard equation commonly used in the field., Comment: 40 pages, 37 figures

A political party can be considered as a company whose value depends on the voters support i.e. on the percentage of population supporting the party. Dynamics of the support is thus as a stochastic process with a deterministic growth rate perturbed by a white noise modeled through the Wiener process. This is in an analogy with the option modeling where the stock price behaves similarly as the voters' support. While in the option theory we have the question of fair price of an option, the question that we ask here is what is a reasonable level of support that the coalition of a major party (safely above the election threshold) and a minor party (under or around the election threshold) should achieve in order the minor party to get one more representative. We shall elaborate some of the conclusions in the case of recent elections in Montenegro (June, 2023) which are particularly interesting due to lots of political subjects entering the race.

In this paper we shall introduced the class of $d-CS$ spaces and so we shall obtained topological approach to large Kasahara spaces. This class include complete symmetric spaces, complete quasi $b$-metric spaces and complete $b$-spaces, but not include $d^*$-complete topological spaces and $d$-complete topological spaces. Further will be presented fixed theorem for nonlinear extended-contraction defined on this spaces, which generalize earlier results obtaned by Browder, Matkowski, Jachymski, Matkowski and \'Swiatkowski, Aran{\dj}elovi\'{c} and Ke\v{c}ki\'{c} and Alshehri, Aran{\dj}elovi\'c and Shahzad. Also, we obtain the fixed point theorem for nonlinear extended-contraction defined on quasi-metric spaces which extended recent result's of Pasicki, obtained for pseudo-metric spaces.

We introduce a new method which resolves the problem of regularity and compactness of entropy solutions for nonlinear degenerate parabolic equations under non-degeneracy conditions on the sphere. In particular, we address a problem of regularity of entropy solutions to homogeneous (autonomous) degenerate parabolic PDEs and existence of weak solutions to heterogeneous degenerate parabolic PDEs (non-autonomous PDEs -- with flux and diffusion explicitly depending on the space and time variables). The method of proof is reduction of the equation to a specific kinetic formulation involving two transport equations, one of the second and one of the first order. In the heterogeneous situation, this enables us to use (variants of) the H-measures to get velocity averaging lemmas and then, consequently, existence of a weak solution. In the homogeneous case, the kinetic reformulation makes it possible to get necessary estimates of the solution on the Littlewood-Paley dyadic blocks of the dual space., Comment: 32 pages

Here we study the effect of electron doping the kagome superconductor CsV$_3$Sb$_5$. Single crystals and powders of CsV$_3$Sb$_{5-x}$Te$_x$ are synthesized and characterized via magnetic susceptibility, nuclear quadrupole resonance, and x-ray diffraction measurements, where we observe a slight suppression of the charge density wave transition temperature and superconducting temperature with the introduction of electron dopants. In contrast to hole-doping, both transitions survive relatively unperturbed up to the solubility limit of Te within the lattice. A comparison is presented between the electronic phase diagrams of electron- and hole-tuned CsV$_3$Sb$_5$., Comment: 11 pages, 4 figures

Polarons and spin-orbit (SO) coupling are distinct quantum effects that play a critical role in charge transport and spin-orbitronics. Polarons originate from strong electron-phonon interaction and are ubiquitous in polarizable materials featuring electron localization, in particular $\mathrm{3d}$ transition metal oxides (TMOs). On the other hand, the relativistic coupling between the spin and orbital angular momentum is notable in lattices with heavy atoms and develops in $\mathrm{5d}$ TMOs, where electrons are spatially delocalized. Here we combine ab initio calculations and magnetic measurements to show that these two seemingly mutually exclusive interactions are entangled in the electron-doped SO-coupled Mott insulator $\mathrm{Ba_2Na_{1-x}Ca_xOsO_6}$ ($0< x < 1$), unveiling the formation of spin-orbital bipolarons. Polaron charge trapping, favoured by the Jahn-Teller lattice activity, converts the Os $\mathrm{5d^1}$ spin-orbital $\mathrm{J_{eff}=3/2}$ levels, characteristic of the parent compound $\mathrm{Ba_2NaOsO_6}$ (BNOO), into a bipolaron $\mathrm{5d^2}$ $\mathrm{J_{eff}=2}$ manifold, leading to the coexistence of different J-effective states in a single-phase material. The gradual increase of bipolarons with increasing doping creates robust in-gap states that prevents the transition to a metal phase even at ultrahigh doping, thus preserving the Mott gap across the entire doping range from $\mathrm{d^1}$ BNOO to $\mathrm{d^2}$ $\mathrm{Ba_2CaOsO_6}$ (BCOO).

Deep learning techniques are required for the analysis of synoptic (multi-band and multi-epoch) light curves in massive data of quasars, as expected from the Vera C. Rubin Observatory Legacy Survey of Space and Time (LSST). In this follow-up study, we introduced an upgraded version of a conditional neural process (CNP) embedded in a multistep approach for analysis of large data of quasars in the LSST Active Galactic Nuclei Scientific Collaboration data challenge database. We present a case study of a stratified set of the u-band light curves for 283 quasars with very low variability $\sim 0.03$. In this sample, CNP average mean square error is found to be $\sim 5\% $($\sim 0.5$ mag). Interestingly, beside similar level of variability there are indications that individual light curves show flare like features. According to preliminary structure function analysis, these occurrences may be associated to microlensing events with larger time scales $5-10$ years., Comment: accepted for publication by the MDPI Universe Special Issue A Multimessenger View of Supermassive Black Holes and the Quasar Main Sequence, Eds. Ascension Del Olmo and Paola Marziani

Language Models (LMs) have shown state-of-the-art performance in Natural Language Processing (NLP) tasks. Downstream tasks such as Named Entity Recognition (NER) or Part-of-Speech (POS) tagging are known to suffer from data imbalance issues, particularly regarding the ratio of positive to negative examples and class disparities. This paper investigates an often-overlooked issue of encoder models, specifically the position bias of positive examples in token classification tasks. For completeness, we also include decoders in the evaluation. We evaluate the impact of position bias using different position embedding techniques, focusing on BERT with Absolute Position Embedding (APE), Relative Position Embedding (RPE), and Rotary Position Embedding (RoPE). Therefore, we conduct an in-depth evaluation of the impact of position bias on the performance of LMs when fine-tuned on token classification benchmarks. Our study includes CoNLL03 and OntoNote5.0 for NER, English Tree Bank UD\_en, and TweeBank for POS tagging. We propose an evaluation approach to investigate position bias in transformer models. We show that LMs can suffer from this bias with an average drop ranging from 3\% to 9\% in their performance. To mitigate this effect, we propose two methods: Random Position Shifting and Context Perturbation, that we apply on batches during the training process. The results show an improvement of $\approx$ 2\% in the performance of the model on CoNLL03, UD\_en, and TweeBank., Comment: Updated content of the preprint

This chapter aims to provide a clear and understandable picture of constructive semigroups with apartness in Bishop's style of constructive mathematics, BISH. Our theory is partly inspired by the classical case, but it is distinguished from it in two significant aspects: we use intuitionistic logic rather than classical throughout; our work is based on the notion of apartness (between elements of the set, and, later, between elements and its subsets). Following Heyting, at least initially, classical semigroup theory is seen as a guide that helps us to develop the constructive theory of semigroups with apartness. To have a structure, we need a set, a relation, and rules establishing how we will put them together. Working within classical or intuitionistic logic, in order to analyze algebraic structures, it is necessary to start with study on sets and ordered sets, relational systems, etc. A comparative analysis between presented classical and constructive results is also a part of this chapter. All proofs can be found in the Appendix., Comment: arXiv admin note: substantial text overlap with arXiv:2008.11008

Extracting information from academic PDF documents is crucial for numerous indexing, retrieval, and analysis use cases. Choosing the best tool to extract specific content elements is difficult because many, technically diverse tools are available, but recent performance benchmarks are rare. Moreover, such benchmarks typically cover only a few content elements like header metadata or bibliographic references and use smaller datasets from specific academic disciplines. We provide a large and diverse evaluation framework that supports more extraction tasks than most related datasets. Our framework builds upon DocBank, a multi-domain dataset of 1.5M annotated content elements extracted from 500K pages of research papers on arXiv. Using the new framework, we benchmark ten freely available tools in extracting document metadata, bibliographic references, tables, and other content elements from academic PDF documents. GROBID achieves the best metadata and reference extraction results, followed by CERMINE and Science Parse. For table extraction, Adobe Extract outperforms other tools, even though the performance is much lower than for other content elements. All tools struggle to extract lists, footers, and equations. We conclude that more research on improving and combining tools is necessary to achieve satisfactory extraction quality for most content elements. Evaluation datasets and frameworks like the one we present support this line of research. We make our data and code publicly available to contribute toward this goal., Comment: iConference 2023

The use of BERT, one of the most popular language models, has led to improvements in many Natural Language Processing (NLP) tasks. One such task is Named Entity Recognition (NER) i.e. automatic identification of named entities such as location, person, organization, etc. from a given text. It is also an important base step for many NLP tasks such as information extraction and argumentation mining. Even though there is much research done on NER using BERT and other popular language models, the same is not explored in detail when it comes to Legal NLP or Legal Tech. Legal NLP applies various NLP techniques such as sentence similarity or NER specifically on legal data. There are only a handful of models for NER tasks using BERT language models, however, none of these are aimed at legal documents in German. In this paper, we fine-tune a popular BERT language model trained on German data (German BERT) on a Legal Entity Recognition (LER) dataset. To make sure our model is not overfitting, we performed a stratified 10-fold cross-validation. The results we achieve by fine-tuning German BERT on the LER dataset outperform the BiLSTM-CRF+ model used by the authors of the same LER dataset. Finally, we make the model openly available via HuggingFace., Comment: Presented at ICAART 2023

Electrical power systems are increasing in size, complexity, as well as dynamics due to the growing integration of renewable energy resources, which have sporadic power generation. This necessitates the development of near real-time power system algorithms, demanding lower computational complexity regarding the power system size. Considering the growing trend in the collection of historical measurement data and recent advances in the rapidly developing deep learning field, the main goal of this paper is to provide a review of recent deep learning-based power system monitoring and optimization algorithms. Electrical utilities can benefit from this review by re-implementing or enhancing the algorithms traditionally used in energy management systems (EMS) and distribution management systems (DMS).

Recent work on neural algorithmic reasoning has investigated the reasoning capabilities of neural networks, effectively demonstrating they can learn to execute classical algorithms on unseen data coming from the train distribution. However, the performance of existing neural reasoners significantly degrades on out-of-distribution (OOD) test data, where inputs have larger sizes. In this work, we make an important observation: there are many different inputs for which an algorithm will perform certain intermediate computations identically. This insight allows us to develop data augmentation procedures that, given an algorithm's intermediate trajectory, produce inputs for which the target algorithm would have exactly the same next trajectory step. We ensure invariance in the next-step prediction across such inputs, by employing a self-supervised objective derived by our observation, formalised in a causal graph. We prove that the resulting method, which we call Hint-ReLIC, improves the OOD generalisation capabilities of the reasoner. We evaluate our method on the CLRS algorithmic reasoning benchmark, where we show up to 3$\times$ improvements on the OOD test data., Comment: ICML 2023, Camera Ready; 17 pages, 7 figures