Search

An abstract topological graph (AT-graph) is a pair $A=(G,\mathcal{X})$, where $G=(V,E)$ is a graph and $\mathcal{X} \subseteq {E \choose 2}$ is a set of pairs of edges of $G$. A realization of $A$ is a drawing $\Gamma_A$ of $G$ in the plane such that any two edges $e_1,e_2$ of $G$ cross in $\Gamma_A$ if and only if $(e_1,e_2) \in \mathcal{X}$; $\Gamma_A$ is simple if any two edges intersect at most once (either at a common endpoint or at a proper crossing). The AT-graph Realizability (ATR) problem asks whether an input AT-graph admits a realization. The version of this problem that requires a simple realization is called Simple AT-graph Realizability (SATR). It is a classical result that both ATR and SATR are NP-complete. In this paper, we study the SATR problem from a new structural perspective. More precisely, we consider the size $\mathrm{\lambda}(A)$ of the largest connected component of the crossing graph of any realization of $A$, i.e., the graph ${\cal C}(A) = (E, \mathcal{X})$. This parameter represents a natural way to measure the level of interplay among edge crossings. First, we prove that SATR is NP-complete when $\mathrm{\lambda}(A) \geq 6$. On the positive side, we give an optimal linear-time algorithm that solves SATR when $\mathrm{\lambda}(A) \leq 3$ and returns a simple realization if one exists. Our algorithm is based on several ingredients, in particular the reduction to a new embedding problem subject to constraints that require certain pairs of edges to alternate (in the rotation system), and a sequence of transformations that exploit the interplay between alternation constraints and the SPQR-tree and PQ-tree data structures to eventually arrive at a simpler embedding problem that can be solved with standard techniques., Comment: Short version with less content accepted to ISAAC 2024

MICADO is a first light instrument for the Extremely Large Telescope (ELT), set to start operating later this decade. It will provide diffraction limited imaging, astrometry, high contrast imaging, and long slit spectroscopy at near-infrared wavelengths. During the initial phase operations, adaptive optics (AO) correction will be provided by its own natural guide star wavefront sensor. In its final configuration, that AO system will be retained and complemented by the laser guide star multi-conjugate adaptive optics module MORFEO (formerly known as MAORY). Among many other things, MICADO will study exoplanets, distant galaxies and stars, and investigate black holes, such as Sagittarius A* at the centre of the Milky Way. After their final design phase, most components of MICADO have moved on to the manufacturing and assembly phase. Here we summarize the final design of the instrument and provide an overview about its current manufacturing status and the timeline. Some lessons learned from the final design review process will be presented in order to help future instrumentation projects to cope with the challenges arising from the substantial differences between projects for 8-10m class telescopes (e.g. ESO-VLT) and the next generation Extremely Large Telescopes (e.g. ESO-ELT). Finally, the expected performance will be discussed in the context of the current landscape of astronomical observatories and instruments. For instance, MICADO will have similar sensitivity as the James Webb Space Telescope (JWST), but with six times the spatial resolution., Comment: Proceedings of the SPIE, Volume 13096, id. 1309611 11 pp. (2024)

Adversarial patches in computer vision can be used, to fool deep neural networks and manipulate their decision-making process. One of the most prominent examples of adversarial patches are evasion attacks for object detectors. By covering parts of objects of interest, these patches suppress the detections and thus make the target object 'invisible' to the object detector. Since these patches are usually optimized on a specific network with a specific train dataset, the transferability across multiple networks and datasets is not given. This paper addresses these issues and investigates the transferability across numerous object detector architectures. Our extensive evaluation across various models on two distinct datasets indicates that patches optimized with larger models provide better network transferability than patches that are optimized with smaller models., Comment: 7 pages, 6 figures, 1 table

AI Infrastructure plays a key role in the speed and cost-competitiveness of developing and deploying advanced AI models. The current demand for powerful AI infrastructure for model training is driven by the emergence of generative AI and foundational models, where on occasion thousands of GPUs must cooperate on a single training job for the model to be trained in a reasonable time. Delivering efficient and high-performing AI training requires an end-to-end solution that combines hardware, software and holistic telemetry to cater for multiple types of AI workloads. In this report, we describe IBM's hybrid cloud infrastructure that powers our generative AI model development. This infrastructure includes (1) Vela: an AI-optimized supercomputing capability directly integrated into the IBM Cloud, delivering scalable, dynamic, multi-tenant and geographically distributed infrastructure for large-scale model training and other AI workflow steps and (2) Blue Vela: a large-scale, purpose-built, on-premises hosting environment that is optimized to support our largest and most ambitious AI model training tasks. Vela provides IBM with the dual benefit of high performance for internal use along with the flexibility to adapt to an evolving commercial landscape. Blue Vela provides us with the benefits of rapid development of our largest and most ambitious models, as well as future-proofing against the evolving model landscape in the industry. Taken together, they provide IBM with the ability to rapidly innovate in the development of both AI models and commercial offerings., Comment: Corresponding Authors: Talia Gershon, Seetharami Seelam,Brian Belgodere, Milton Bonilla

In this paper, we prove the convergence and uniqueness of a general discrete-time nonlinear Markov chain with specific conditions. The results have important applications in discrete differential geometry. First, on a general finite weighted graph, we prove the discrete-time Ollivier Ricci curvature flow $d_{n+1}\coloneqq(1-\alpha\kappa_{d_{n}})d_{n}$ converges to a constant curvature metric. Then the author in \cite[Theorem 5.1]{M23} proved a Laplacian separation principle on a locally finite graph with non-negative Ollivier curvature. Here we prove the Laplacian separation flow converges to the constant Laplacian solution and generalize the result to nonlinear $p$-Laplace operators. Moreover, our results can also be applied to study the long-time behavior in the nonlinear Dirichlet forms theory and nonlinear Perron--Frobenius theory. At last, we define the Ollivier Ricci curvature of nonlinear Markov chain which is consistent with the classical Ollivier Ricci curvature, sectional curvature \cite{CMS24}, coarse Ricci curvature on hypergraphs \cite{IKTU21} and the modified Ollivier Ricci curvature for $p$-Laplace. And we prove the convergence results for the nonlinear Markov chain with nonnegative Ollivier Ricci curvature., Comment: 25 pages, 1 figure

In this paper, we introduce Cheeger type constants via isocapacitary constants introduced by Maz'ya to estimate first Dirichlet, Neumann and Steklov eigenvalues on a finite subgraph of a graph. Moreover, we estimate the bottom of the spectrum of the Laplace operator and the Dirichlet-to-Neumann operator for an infinite subgraph. Estimates for higher-order Steklov eigenvalues on a finite or infinite subgraph are also proved., Comment: We corrected some typos

Fuzzing has proven to be a highly effective approach to uncover software bugs over the past decade. After AFL popularized the groundbreaking concept of lightweight coverage feedback, the field of fuzzing has seen a vast amount of scientific work proposing new techniques, improving methodological aspects of existing strategies, or porting existing methods to new domains. All such work must demonstrate its merit by showing its applicability to a problem, measuring its performance, and often showing its superiority over existing works in a thorough, empirical evaluation. Yet, fuzzing is highly sensitive to its target, environment, and circumstances, e.g., randomness in the testing process. After all, relying on randomness is one of the core principles of fuzzing, governing many aspects of a fuzzer's behavior. Combined with the often highly difficult to control environment, the reproducibility of experiments is a crucial concern and requires a prudent evaluation setup. To address these threats to validity, several works, most notably Evaluating Fuzz Testing by Klees et al., have outlined how a carefully designed evaluation setup should be implemented, but it remains unknown to what extent their recommendations have been adopted in practice. In this work, we systematically analyze the evaluation of 150 fuzzing papers published at the top venues between 2018 and 2023. We study how existing guidelines are implemented and observe potential shortcomings and pitfalls. We find a surprising disregard of the existing guidelines regarding statistical tests and systematic errors in fuzzing evaluations. For example, when investigating reported bugs, ...

We study geodesics in Friedmann-Lema{\^\i}tre-Robertson-Walker (FLRW) cosmological models and give the full set of solutions. For azimuthal geodesics, in a closed universe, we give the angular distance travelled by a test particle moving along such a geodesic during one cycle of expansion and re-collapse of the universe. We extend previous results regarding the path followed by light rays to the two-fluid case, also including a cosmological constant, as well as to massive test particles. Our work contains various new results and explicit formulae, often using special functions which naturally appear in this setting., Comment: 24 pages, 3 figures; v2 matches version published in Phys. Rev. D

In this note, we provide Steinerberger curvature formulas for block graphs, discuss curvature relations between two graphs and the graph obtained by connecting them via a bridge, and show that self-centered Bonnet-Myers sharp graphs are precisely those which are antipodal. We also discuss similarities and differences between Steinerberger and Ollivier Ricci curvature results.

In this paper we consider global $\theta$-curvatures of finite Markov chains with associated means $\theta$ in the spirit of the entropic curvature (based on the logarithmic mean) by Erbar-Maas and Mielke. As in the case of Bakry-\'Emery curvature, we also allow for a finite dimension parameter by making use of an adapted $\Gamma$ calculus for $\theta$-curvatures. We prove explicit positive lower curvature bounds (both finite- and infinite-dimensional) for finite abelian Cayley graphs. In the case of cycles, we provide also an upper curvature bound which shows that our lower bounds are asymptotically sharp (up to a logarithmic factor). Moreover, we prove new universal lower curvature bounds for finite Markov chains as well as curvature perturbation results (allowing, in particular, to compare entropic and Bakry-\'Emery curvatures). Finally, we present examples where entropic curvature differs significantly from other curvature notions like Bakry-\'Emery curvature or Ollivier Ricci and sectional curvatures.

This paper deals with the numerical computation of null controls for the linear heat equation. The goal is to compute approximations of controls that drive the solution from a prescribed initial state to zero at a given positive time. In [Fernandez-Cara \& M\"unch, Strong convergence approximations of null controls for the 1D heat equation, 2013], a so-called primal method is described leading to a strongly convergent approximation of distributed control: the controls minimize quadratic weighted functionals involving both the control and the state and are obtained by solving the corresponding optimality conditions. In this work, we adapt the method to approximate the control of minimal square integrable-weighted norm. The optimality conditions of the problem are reformulated as a mixed formulation involving both the state and its adjoint. We prove the well-posedness of the mixed formulation (in particular the inf-sup condition) then discuss several numerical experiments. The approach covers both the boundary and the inner situation and is valid in any dimension., Comment: 37 pages

The characterization of complex networks with tools originating in geometry, for instance through the statistics of so-called Ricci curvatures, is a well established tool of network science. There exist various types of such Ricci curvatures, capturing different aspects of network geometry. In the present work, we investigate Bakry-\'Emery-Ricci curvature, a notion of discrete Ricci curvature that has been studied much in geometry, but so far has not been applied to networks. We explore on standard classes of artificial networks as well as on selected empirical ones to what the statistics of that curvature are similar to or different from that of other curvatures, how it is correlated to other important network measures, and what it tells us about the underlying network. We observe that most vertices typically have negative curvature. Random and small-world networks exhibit a narrow curvature distribution whereas other classes and most of the real-world networks possess a wide curvature distribution. When we compare Bakry-\'Emery-Ricci curvature with two other discrete notions of Ricci-curvature, Forman-Ricci and Ollivier-Ricci curvature for both model and real-world networks, we observe a high positive correlation between Bakry-\'Emery-Ricci and both Forman-Ricci and Ollivier-Ricci curvature, and in particular with the augmented version of Forman-Ricci curvature. Bakry-\'Emery-Ricci curvature also exhibits a high negative correlation with the vertex centrality measure and degree for most of the model and real-world networks. However, it does not correlate with the clustering coefficient. Also, we investigate the importance of vertices with highly negative curvature values to maintain communication in the network. The computational time for Bakry-\'Emery-Ricci curvature is shorter than that required for Ollivier-Ricci curvature but higher than for Augmented Forman-Ricci curvature., Comment: 34 pages, 9 main figures, 12 supplementary tables, 1 supplementary figure

The aim of this work is to present some strategies to solve numerically controllability problems for the two-dimensional heat equation, the Stokes equations and the Navier-Stokes equations with Dirichlet boundary conditions. The main idea is to adapt the Fursikov-Imanuvilov formulation, see~[A.V. Fursikov, O.Yu. Imanuvilov: {\it Controllability of Evolutions Equations,} Lectures Notes Series, Vol.~34, Seoul National University, 1996]; this approach has been followed recently for the one-dimensional heat equation by the first two authors. More precisely, we minimize over the class of admissible null controls a functional that involves weighted integrals of the state and the control, with weights that blow up near the final time. The associated optimality conditions can be viewed as a differential system in the three variables $x_1$, $x_2$ and $t$ that is second--order in time and fourth--order in space, completed with appropriate boundary conditions. We present several mixed formulations of the problems and, then, associated mixed finite element Lagrangian approximations that are relatively easy to handle. Finally, we exhibit some numerical experiments., Comment: 35 pages

We study Markov chains with non-negative sectional curvature on finite metric spaces. Neither reversibility, nor the restriction to a particular combinatorial distance are imposed. In this level of generality, we prove that a 1-step contraction in the Wasserstein distance implies a 1-step contraction in relative entropy, by the same amount. Our result substantially strengthens a recent breakthrough of the second author, and has the advantage of being applicable to arbitrary scales. This leads to a time-varying refinement of the standard Modified Log-Sobolev Inequality (MLSI), which allows us to leverage the well-acknowledged fact that curvature improves at large scales. We illustrate this principle with several applications, including birth and death chains, colored exclusion processes, permutation walks, Gibbs samplers for high-temperature spin systems, and attractive zero-range dynamics. In particular, we prove a MLSI with constant equal to the minimal rate increment for the mean-field zero-range process, thereby answering a long-standing question., Comment: We added a section on Glauber dynamics for high-dimensional measures with weak dependencies, including high-temperature spin systems

Based on earlier work by Carlen-Maas and the second- and third-named author, we introduce the notion of intertwining curvature lower bounds for graphs and quantum Markov semigroups. This curvature notion is stronger than both Bakry-\'Emery and entropic Ricci curvature, while also computationally simpler than the latter. We verify intertwining curvature bounds in a number of examples, including finite weighted graphs and graphs with Laplacians admitting nice mapping representations, as well as generalized dephasing semigroups and quantum Markov semigroups whose generators are formed by commuting jump operators. By improving on the best-known bounds for entropic curvature of depolarizing semigroups, we demonstrate that there can be a gap between the optimal intertwining and entropic curvature bound. In the case of qubits, this improved entropic curvature bound implies the modified logarithmic Sobolev inequality with optimal constant.

Next-generation data networks need to support Tb/s rates. In-phase and quadrature (IQ) modulation combine phase and intensity information to increase the density of encoded data, reduce overall power consumption by minimising the number of channels, and increase noise tolerance. To reduce errors when decoding the received signal, intersymbol interference must be minimised. This is achieved with pure phase modulation, where the phase of the optical signal is controlled without changing its intensity. Phase modulators are characterised by the voltage required to achieve a $\pi$ phase shift V$_{\pi}$, the device length L, and their product V$_{\pi}$L. To reduce power consumption, IQ modulators are needed with$<$1V drive voltages and compact (sub-cm) dimensions, which translate in V$_\pi$L$<$1Vcm. Si and LiNbO$_3$ (LN) IQ modulators do not currently meet these requirements, because V$_{\pi}$L$>$1Vcm. Here, we report a double single-layer graphene (SLG) Mach-Zehnder modulator (MZM) with pure phase modulation in the transparent regime, where optical losses are minimised and remain constant with increasing voltage. Our device has $V_{\pi}L\sim$0.3Vcm, matching state-of-the-art SLG-based MZMs and plasmonic LN MZMs, but with pure phase modulation and low insertion loss ($\sim$5dB), essential for IQ modulation. Our $V_\pi L$ is$\sim$5 times lower than the lowest thin-film LN MZMs, and$\sim$3 times lower than the lowest Si MZMs. This enables devices with complementary metal-oxide semiconductor compatible V$_\pi$L ($<$1Vcm) and smaller footprint than LN or Si MZMs, improving circuit density and reducing power consumption by one order of magnitude.

Quadratic Unconstrained Binary Optimization (QUBO) problems are NP-hard problems and many real-world problems can be formulated as QUBO. Currently there are no algorithms known that can solve arbitrary instances of NP-hard problems efficiently. Therefore special-purpose hardware such as Digital Annealer, other Ising machines, as well as quantum annealers might lead to benefits in solving such problems. We study a particularly hard class of problems which can be formulated as QUBOs, namely Boolean satisfiability (SAT) problems, and specifically 3-SAT. One intriguing aspect about 3-SAT problems is that there are different transformations from 3-SAT to QUBO. We study the transformations' influence on the problem solution, using Digital Annealer as a special-purpose solver. Besides well-known transformations we investigate a novel in this context not yet discussed transformation, using less auxiliary variables and leading to very good performance. Using exact diagonalization, we explain the differences in performance originating from the different transformations. We envision that this knowledge allows for specifically engineering transformations that improve a solvers capacity to find high quality solutions. Furthermore, we show that the Digital Annealer outperforms a quantum annealer in solving hard 3-SAT instances., Comment: 10 pages, 4 figures

In this paper, we propose a generalization of Bakry-\'Emery's calculus which allows us to formulate both Bakry-\'Emery and entropic curvature simultaneously. This formulation represents both curvatures as an integral of the Bochner formula against some measure. This leads to a natural optimality criterion of measures, which we investigate in the Bakry-\'Emery setting. Moreover, our approach leads also to a dimension parameter in the framework of entropic curvature. We also present gradient estimate applications, that is, diameter estimates for Markov chains with strictly positive entropic curvature and a spectral gap estimate. The latter implies non-existence of non-negatively curved expanders.

With the advent of interconnected and sensor-equipped edge devices, Federated Learning (FL) has gained significant attention, enabling decentralized learning while maintaining data privacy. However, FL faces two challenges in real-world tasks: expensive data labeling and domain shift between source and target samples. In this paper, we introduce a privacy-preserving, resource-efficient FL concept for client adaptation in hardware-constrained environments. Our approach includes server model pre-training on source data and subsequent fine-tuning on target data via low-end clients. The local client adaptation process is streamlined by probabilistic mixing of instance-level feature statistics approximated from source and target domain data. The adapted parameters are transferred back to the central server and globally aggregated. Preliminary results indicate that our method reduces computational and transmission costs while maintaining competitive performance on downstream tasks., Comment: Accepted at the Adapting to Change: Reliable Multimodal Learning Across Domains Workshop @ ECML PKKD 2023

The astronomical community is grappling with the increasing volume and complexity of data produced by modern telescopes, due to difficulties in reducing, accessing, analyzing, and combining archives of data. To address this challenge, we propose the establishment of a coordinating body, an "entity," with the specific mission of enhancing the interoperability, archiving, distribution, and production of both astronomical data and software. This report is the culmination of a workshop held in February 2023 on the Future of Astronomical Data Infrastructure. Attended by 70 scientists and software professionals from ground-based and space-based missions and archives spanning the entire spectrum of astronomical research, the group deliberated on the prevailing state of software and data infrastructure in astronomy, identified pressing issues, and explored potential solutions. In this report, we describe the ecosystem of astronomical data, its existing flaws, and the many gaps, duplication, inconsistencies, barriers to access, drags on productivity, missed opportunities, and risks to the long-term integrity of essential data sets. We also highlight the successes and failures in a set of deep dives into several different illustrative components of the ecosystem, included as an appendix., Comment: 59 pages; please send comments and/or questions to foadi@googlegroups.com

In this article we study two discrete curvature notions, Bakry-\'Emery curvature and Ollivier Ricci curvature, on Cayley graphs. We introduce Right Angled Artin-Coxeter Hybrids (RAACHs) generalizing Right Angled Artin and Coxeter groups (RAAGs and RACGs) and derive the curvatures of Cayley graphs of certain RAACHs. Moreover, we show for general finitely presented groups $\Gamma = \langle S \, \mid\, R \rangle$ that addition of relators does not lead to a decrease the weighted curvatures of their Cayley graphs with adapted weighting schemes.

We study heat kernel convergence of induced subgraphs with Neumann boundary conditions. We first establish convergence of the resulting semigroups to the Neumann semigroup in $\ell^2$. While convergence to the Neumann semigroup always holds, convergence to the Dirichlet semigroup in $\ell^2$ turns out to be equivalent to the coincidence of the Dirichlet and Neumann semigroups while convergence in $\ell^1$ is equivalent to stochastic completeness. We then investigate the Feller property for the Neumann semigroup via generalized solutions and give applications to graphs satisfying a condition on the edges as well as birth-death chains.

We introduce a Laplacian separation principle for the the eikonal equation on Markov chains. As application, we prove an isoperimetric concentration inequality for Markov chains with non-negative Ollivier curvature. That is, every single point from the concentration profile yields an estimate for every point of the isoperimetric estimate. Applying to exponential and Gaussian concentration, we obtain affirmative answers to two open quesions by Erbar and Fathi. Moreover, we prove that the modified log-Sobolev constant is at least the minimal Ollivier Ricci curvature, assuming non-negative Ollivier sectional curvature, i.e., the Ollivier Ricci curvature when replacing the $\ell_1$ by the $\ell_\infty$ Wasserstein distance. This settles a recent open Problem by Pedrotti. We give a simple example showing that non-negative Ollivier sectional curvature is necessary to obtain a modified log-Sobolev inequality via positive Ollivier Ricci bound. This provides a counterexample to a conjecture by Peres and Tetali.

We address the exact boundary controllability of the semilinear wave equation $\partial_{tt}y-\Delta y + f(y)=0$ posed over a bounded domain $\Omega$ of $\mathbb{R}^d$. Assuming that $f$ is continuous and satisfies the condition $\limsup_{\vert r\vert\to \infty} \vert f(r)\vert /(\vert r\vert \ln^p\vert r\vert)\leq \beta$ for some $\beta$ small enough and some $p\in [0,3/2)$, we apply the Schauder fixed point theorem to prove the uniform controllability for initial data in $L^2(\Omega)\times H^{-1}(\Omega)$. Then, assuming that $f$ is in $\mathcal{C}^1(\mathbb{R})$ and satisfies the condition $\limsup_{\vert r\vert\to \infty} \vert f^\prime(r)\vert/\ln^p\vert r\vert\leq \beta$, we apply the Banach fixed point theorem and exhibit a strongly convergent sequence to a state-control pair for the semilinear equation.

Inspired by asymptotically flat manifolds, we introduce the concept of asymptotically flat graphs and define the discrete ADM mass on them. We formulate the discrete positive mass conjecture based on the scalar curvature in the sense of Ollivier curvature, and prove the positive mass theorem for asymptotically flat graphs that are combinatorially isomorphic to grid graphs. As a corollary, the discrete torus does not admit positive scalar curvature. We prove a weaker version of the positive mass conjecture: an asymptotically flat graph with non-negative Ricci curvature is isomorphic to the standard grid graph. Hence the combinatorial structure of an asymptotically flat graph is determined by the curvature condition, which is a discrete analog of the rigidity part for the positive mass theorem. The key tool for the proof is the discrete harmonic function of linear growth associated with the salami structure.

We study phase equilibria in a minimal model of charge-regulated polymer solutions. Our model consists of a single polymer species whose charge state arises from protonation-deprotonation processes in the presence of a dissolved acid, whose anions serve as screening counterions. We explicitly account for variability in the polymers' charge states. Homogeneous equilibria in this model system are characterised by the total concentration of polymers, the concentration of counter-ions and the charge distributions of polymers which can be computed with the help of analytical approximations. We use these analytical results to characterise how parameter values and solution acidity influence equilibrium charge distributions and identify for which regimes uni-modal and multi-modal charge distributions arise. We then study the interplay between charge regulation, solution acidity and phase separation. We find that charge regulation has a significant impact on polymer solubility and allows for non-linear responses to the solution acidity: re-entrant phase behaviour is possible in response to increasing solution acidity. Moreover, we show that phase separation can yield to the coexistence of local environments characterised by different charge distributions and mixture compositions.

Adversarial patches are still a simple yet powerful white box attack that can be used to fool object detectors by suppressing possible detections. The patches of these so-called evasion attacks are computational expensive to produce and require full access to the attacked detector. This paper addresses the problem of computational expensiveness by analyzing 375 generated patches, calculating the principal components of these and show, that linear combinations of the resulting "eigenpatches" can be used to fool object detections successfully.