Search

We study subsets of groups and monoids defined by language-theoretic means, generalizing the classical approach to the word problem. We expand on results by Herbst from 1991 to a more general setting, and for a class of languages $\mathbf{C}$ we define the classes of $\mathbf{C}^\forall$-flat and $\mathbf{C}^\exists$-flat groups. We prove several closure results for these classes of groups, prove a connection with the word problem, and characterize $\mathbf{C}^\forall$-flat groups for several classes of languages. In general, we prove that the class of $\mathbf{C}^\forall$-flat groups is a strict subclass of the class of groups with word problem in $\mathbf{C}$, including for the class $\mathrm{REC}$ of recursive languages, for which $\mathbf{C}^\forall$-flatness for a group resp. monoid is proved to be equivalent to the decidability of the subgroup membership problem resp. the submonoid membership problem. We provide a number of examples, including the Tarski monsters of Ol'shanskii, showing the difficulty of characterizing $\mathbf{C}^\exists$-flat groups. As an application of our general methods, we also prove in passing that if $\mathbf{C}$ is a full semi-$\mathrm{AFL}$, then the class of epi-$\mathbf{C}$ groups is closed under taking finite index subgroups. This answers a question recently posed by Al Kohli, Bleak & Elliot., Comment: 24 pages. Comments welcome!

We introduce separability properties corresponding to generalized versions of the conjugacy, twisted conjugacy, Brinkmann and Brinkmann's conjugacy problems and how they relate when finite and cyclic extensions of groups are taken. In particular, we prove that some (concrete) generalizations of twisted conjugacy separability of a group $G$ with respect to virtually inner automorphisms are equivalent to some (concrete) generalizations of the conjugacy problem in finite extensions of $G$. Similarly, (generalized) conjugacy separability in cyclic extensions of $G$ implies (generalized) twisted conjugacy and Brinkmann's conjugacy separability in $G$. Applications include results in free, virtually abelian, virtually polycyclic groups and a proof that virtually free times free groups are conjugacy separable., Comment: 22 pages, comments are very welcome!

The first International AI Safety Report comprehensively synthesizes the current evidence on the capabilities, risks, and safety of advanced AI systems. The report was mandated by the nations attending the AI Safety Summit in Bletchley, UK. Thirty nations, the UN, the OECD, and the EU each nominated a representative to the report's Expert Advisory Panel. A total of 100 AI experts contributed, representing diverse perspectives and disciplines. Led by the report's Chair, these independent experts collectively had full discretion over the report's content.

We prove that a subset of a virtually free group is rational if and only if the language of geodesic words representing its elements (in any generating set) is rational and that the language of geodesics representing conjugates of elements in a rational subset of a virtually free group is context-free. As a corollary, the doubly generalized conjugacy problem is decidable for rational subsets of finitely generated virtually free groups: there is an algorithm taking as input two rational subsets $K_1$ and $K_2$ of a virtually free group that decides whether there is one element of $K_1$ conjugate to an element of $K_2$. For free groups, we prove that the same problem is decidable with rational constraints on the set of conjugators., Comment: 16 pages, comments are welcome

Infectious diseases, transmitted directly or indirectly, are among the leading causes of epidemics and pandemics. Consequently, several open challenges exist in predicting epidemic outbreaks, detecting variants, tracing contacts, discovering new drugs, and fighting misinformation. Artificial Intelligence (AI) can provide tools to deal with these scenarios, demonstrating promising results in the fight against the COVID-19 pandemic. AI is becoming increasingly integrated into various aspects of society. However, ensuring that AI benefits are distributed equitably and that they are used responsibly is crucial. Multiple countries are creating regulations to address these concerns, but the borderless nature of AI requires global cooperation to define regulatory and guideline consensus. Considering this, The Global South AI for Pandemic & Epidemic Preparedness & Response Network (AI4PEP) has developed an initiative comprising 16 projects across 16 countries in the Global South, seeking to strengthen equitable and responsive public health systems that leverage Southern-led responsible AI solutions to improve prevention, preparedness, and response to emerging and re-emerging infectious disease outbreaks. This opinion introduces our branches in Latin American and Caribbean (LAC) countries and discusses AI governance in LAC in the light of biotechnology. Our network in LAC has high potential to help fight infectious diseases, particularly in low- and middle-income countries, generating opportunities for the widespread use of AI techniques to improve the health and well-being of their communities.

We introduce some generalized topological concepts to deal with union-closed families, and show that one can reduce the proof of Frankl conjecture to some families of so-called supratopological spaces. We prove some results on the structure of normalized families, presenting a new way of reducing such a family to a smaller one using dual families. Applying our reduction method, we prove a refinement of a conjecture originally proposed by Poonen. Finally, we show that Frankl Conjecture holds for the class of families obtained from successively applying the reduction process to a power set., Comment: 27 pages, 1 figure. comments are welcome!

Parametrized gate circuits are used in plentiful applications in the current NISQ era of quantum computing. These parametrized gates are chiefly implemented using analytically found pulse protocols, often yielding suboptimal gate times, and consequently, fidelities. Alternatively, gate optimization algorithms are designed to construct high fidelity pulses for individual, fixed points in continuous parameter space. Gates for intermediate parameters can subsequently be found by some form of interpolation between previously constructed pulses. Nevertheless, it is not guaranteed (as with analytic protocols) that the pulses found by the optimization algorithms belong to the same \textit{family} of solutions and thus show resemblance. Interpolation between two pulses of differing solution families often leads to high infidelities, as the pulse strays away from the minimum in the parameter/fidelity landscape. In this work, we introduce a \textit{spectral clustering} method to sort high-fidelity, optimized pulses in families, and interpolating solely between pulses of the same family. Accordingly, interpolations will always approach maximal fidelity. Furthermore, as more than one pulse family is constructed, the parameter space can be partitioned according to which family prevails fidelity-wise. This work provides a meticulous demonstration of our constitutive continuous gate family construction by applying it to a universal gate set for Rydberg and Cat qubits under noise., Comment: 11 pages, 8 figures

The adoption of Deep Learning algorithms in the medical imaging field is a prominent area of research, with high potential for advancing AI-based Computer-aided diagnosis (AI-CAD) solutions. However, current solutions face challenges due to a lack of interpretability features and high data demands, prompting recent efforts to address these issues. In this study, we propose the ProtoAL method, where we integrate an interpretable DL model into the Deep Active Learning (DAL) framework. This approach aims to address both challenges by focusing on the medical imaging context and utilizing an inherently interpretable model based on prototypes. We evaluated ProtoAL on the Messidor dataset, achieving an area under the precision-recall curve of 0.79 while utilizing only 76.54\% of the available labeled data. These capabilities can enhances the practical usability of a DL model in the medical field, providing a means of trust calibration in domain experts and a suitable solution for learning in the data scarcity context often found.

Continual Object Detection is essential for enabling intelligent agents to interact proactively with humans in real-world settings. While parameter-isolation strategies have been extensively explored in the context of continual learning for classification, they have yet to be fully harnessed for incremental object detection scenarios. Drawing inspiration from prior research that focused on mining individual neuron responses and integrating insights from recent developments in neural pruning, we proposed efficient ways to identify which layers are the most important for a network to maintain the performance of a detector across sequential updates. The presented findings highlight the substantial advantages of layer-level parameter isolation in facilitating incremental learning within object detection models, offering promising avenues for future research and application in real-world scenarios., Comment: In Proceedings of the 19th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications - Volume 2: VISAPP, ISBN 978-989-758-679-8, ISSN 2184-4321, pages 466-474

We prove that the Brinkmann Problems (BrP & BrCP) and the twisted-conjugacy Problem (TCP) are decidable for any endomorphism of a free-abelian times free (FATF) group Fn x Z^m. Furthermore, we prove the decidability of the two-sided Brinkmann conjugacy problem (2BrCP) for monomorphisms of FATF groups (and combine it with TCP) to derive the decidability of the conjugacy problem for ascending HNN extensions of FATF groups., Comment: 15 pages

Time series forecasting is a subject of significant scientific and industrial importance. Despite the widespread utilization of forecasting methods, there is a dearth of research aimed at comprehending the conditions under which these methods yield favorable or unfavorable performances. Empirical studies, although common, are challenged by the limited availability of time series datasets, restricting the extraction of reliable insights. To address this limitation, we present tsMorph, a tool for generating semi-synthetic time series through dataset morphing. tsMorph works by creating a sequence of datasets from two original datasets. The characteristics of the generated datasets progressively depart from those of one of the datasets and converge toward the attributes of the other dataset. This method provides a valuable alternative for obtaining substantial datasets. In this paper, we show the benefits of tsMorph by assessing the predictive performance of the Long Short-Term Memory Network and DeepAR forecasting algorithms. The time series used for the experiments comes from the NN5 Competition. The experimental results provide important insights. Notably, the performances of the two algorithms improve proportionally with the frequency of the time series. These experiments confirm that tsMorph can be an effective tool for better understanding the behavior of forecasting algorithms, delivering a pathway to overcoming the limitations posed by empirical studies and enabling more extensive and reliable experiments.

We prove that centralizers of elements in [f.g. free]-by-cyclic groups are computable. As a corollary we get that, given two conjugate elements in a [f.g. free]-by-cyclic group, the set of conjugators can be computed and that the conjugacy problem with context-free constraints is decidable. In the end, we pose several problems arising naturally from this work.

We show that both the Brinkmann Problem (BrP) and the Brinkmann Conjugacy Problem (BrCP) are decidable for endomorphisms of the free group Fn.

We prove that Brinkmann's problems are decidable for endomorphisms of $F_n\times F_m$: given $(x,y),(z,w)\in F_n\times F_m$ and $\Phi\in \text{End}(F_n\times F_m)$, it is decidable whether there is some $k\in \mathbb N$ such that $(x,y)\Phi^k=(z,w)$ (or $(x,y)\Phi^k\sim(z,w)$). We also prove decidability of a two-sided version of Brinkmann's conjugacy problem for injective endomorphisms which, from the work of Logan, yields a solution to the conjugacy problem in ascending HNN-extensions of $F_n\times F_m$. Finally, we study the dynamics of automorphisms of $F_n\times F_m$ at the infinity, proving that every point in a continuous extension of an automorphism to the completion is either periodic or wandering, implying that the dynamics is asymptotically periodic, as occurs in the free and free-abelian times free cases., Comment: 21 pages. Comments are welcome!

We study the dynamics of measurable pseudo-Anosov homeomorphisms of surfaces, a generalization of Thurston's pseudo-Anosov homeomorphisms. A measurable pseudo-Anosov map has a transverse pair of full measure turbulations consisting of streamlines which are dense immersed lines: these turbulations are equipped with measures which are expanded and contracted uniformly by the homeomorphism. The turbulations need not have a good product structure anywhere, but have some local structure imposed by the existence of tartans: bundles of unstable and stable streamline segments which intersect regularly, and on whose intersections the product of the measures on the turbulations agrees with the ambient measure. We prove that measurable pseudo-Anosov maps are transitive, have dense periodic points, sensitive dependence on initial conditions, and are ergodic with respect to the ambient measure. Measurable pseudo-Anosovs maps were introduced in [11], where we constructed a parameterized family of non-conjugate examples on the sphere., Comment: Author accepted manuscript

We exhibit a continuously varying family $F_\lambda$ of homeomorphisms of the sphere $S^2$, for which each $F_\lambda$ is a measurable pseudo-Anosov map. Measurable pseudo-Anosov maps are generalizations of Thurston's pseudo-Anosov maps, and also of generalized pseudo-Anosov maps. They have a transverse pair of invariant full measure turbulations, consisting of streamlines which are dense injectively immersed lines: these turbulations are equipped with measures which are expanded and contracted uniformly by the homeomorphism. The turbulations need not have a good product structure anywhere, but have some local structure imposed by the existence of tartans: bundles of unstable and stable streamline segments which intersect regularly, and on whose intersections the product of the measures on the turbulations agrees with the ambient measure. Each map $F_\lambda$ is semi-conjugate to the inverse limit of the core tent map with slope $\lambda$: it is topologically transitive, ergodic with respect to a background Oxtoby-Ulam measure, has dense periodic points, and has topological entropy $h(F_\lambda) = \log \lambda$ (so that no two $F_\lambda$ are topologically conjugate). For a full measure, dense $G_\delta$ set of parameters, $F_\lambda$ is a measurable pseudo-Anosov map but not a generalized pseudo-Anosov map, and its turbulations are nowhere locally regular., Comment: 52 pages, 5 figures

We prove that the stable image of an endomorphism of a virtually free group is computable. For an endomorphism $\varphi$, an element $x\in G$ and a subset $K\subseteq G$, we say that the relative $\varphi$-order of $g$ in $K$, $\varphi\text{-ord}_K(g)$, is the smallest nonnegative integer $k$ such that $g\varphi^k\in K$. We prove that the set of orders, which we call $\varphi$-spectrum, is computable in two extreme cases: when $K$ is a finite subset and when $K$ is a recognizable subset. The finite case is proved for virtually free groups and the recognizable case for finitely presented groups. The case of finitely generated virtually abelian groups and some variations of the problem are also discussed., Comment: 16 pages, comments are welcome

We prove that, although it is undecidable if a subgroup fixed by an automorphism intersects nontrivially an arbitrary subgroup of $F_n\times F_m$, there is an algorithm that, taking as input a monomorphism and an endomorphism of $F_n\times F_m$, decides whether their fixed subgroups intersect nontrivially. The general case of this problem, where two arbitrary endomorphisms are given as input remains unknown. We show that, when two endomorphisms of a certain type are given as input, this problem is equivalent to the Post Correspondence Problem for free groups., Comment: 11 pages, comments are welcome

We establish a connection between the generalized conjugacy problem for a $G$-by-$\mathbb{Z}$ group, $GCP(G \rtimes \mathbb{Z})$, and two algorithmic problems for $G$: the generalized Brinkmann's conjugacy problem, $GBrCP(G)$, and the generalized twisted conjugacy problem, $GTCP(G)$. We explore this connection for generalizations of different kinds: relative to finitely generated subgroups, to theirs cosets, or to recognizable, rational, context-free or algebraic subsets of the group. Using this result, we are able to prove that $GBrCP(G)$ is decidable (with respect to cosets) when $G$ is a virtually polycyclic group, which implies in particular that the generalized Brinkmann's equality problem, $GBrP(G)$, is decidable if $G$ is a finitely generated abelian group. Finally, we prove that if $G$ is a finitely generated virtually free group, then the simple versions of Brinkmann's equality problem and of the twisted conjugacy problem, $BrP(G)$ and $TCP(G)$, are decidable., Comment: 16 pages, comments are welcome!

Identifying and calibrating quantitative dynamical models for physical quantum systems is important for a variety of applications. Here we present a closed-loop Bayesian learning algorithm for estimating multiple unknown parameters in a dynamical model, using optimised experimental "probe" controls and measurement. The estimation algorithm is based on a Bayesian particle filter, and is designed to autonomously choose informationally-optimised probe experiments with which to compare to model predictions. We demonstrate the performance of the algorithm in both simulated calibration tasks and in an experimental single-qubit ion-trap system. Experimentally, we find that with 60x fewer samples, we exceed the precision of conventional calibration methods, delivering an approximately 93x improvement in efficiency (as quantified by the reduction of measurements required to achieve a target residual uncertainty and multiplied by the increase in accuracy). In simulated and experimental demonstrations, we see that successively longer pulses are selected as the posterior uncertainty iteratively decreases, leading to an exponential improvement in the accuracy of model parameters with the number of experimental queries., Comment: 18 pages, 8 figures

We apply the knowledge of urban settings established with the study of Land Use and Transport Interaction (LUTI) models to develop reward functions for an agent-based system capable of planning realistic artificial cities. The system aims to replicate in the micro scale the main components of real settlements, such as zoning and accessibility in a road network. Moreover, we propose a novel representation for the agent's environment that efficiently combines the road graph with a discrete model for the land. Our system starts from an empty map consisting only of the road network graph, and the agent incrementally expands it by building new sites while distinguishing land uses between residential, commercial, industrial, and recreational., Comment: 12 pages, 6 figures, XIX Encontro Nacional de Intelig\^encia Artificial e Computacional (ENIAC 2022)

We study the relation between the structure of algebraic and context-free subsets of a group G and that of a finite index subgroup H. Using these results, we prove that a kind of Fatou property, previously studied by Berstel and Sakarovitch in the context of rational subsets and by Herbst in the context of algebraic subsets, holds for context-free subsets if and only if the group is virtually free. We also exhibit a counterexample to a question of Herbst concerning this property for algebraic subsets., Comment: minor changes

Excitement about the promise of quantum computers is tempered by the reality that the hardware remains exceptionally fragile and error-prone, forming a bottleneck in the development of novel applications. In this manuscript, we describe and experimentally test a fully autonomous workflow designed to deterministically suppress errors in quantum algorithms from the gate level through to circuit execution and measurement. We introduce the key elements of this workflow, delivered as a software package called Fire Opal, and survey the underlying physical concepts: error-aware compilation, automated system-wide gate optimization, automated dynamical decoupling embedding for circuit-level error cancellation, and calibration-efficient measurement-error mitigation. We then present a comprehensive suite of performance benchmarks executed on IBM hardware, demonstrating up to > 1000X improvement over the best alternative expert-configured techniques available in the open literature. Benchmarking includes experiments using up to 16 qubit systems executing: Bernstein Vazirani, Quantum Fourier Transform, Grover's Search, QAOA, VQE, Syndrome extraction on a five-qubit Quantum Error Correction code, and Quantum Volume. Experiments reveal a strong contribution of Non-Markovian errors to baseline algorithmic performance; in all cases the deterministic error-suppression workflow delivers the highest performance and approaches incoherent error bounds without the need for any additional sampling or randomization overhead, while maintaining compatibility with all additional probabilistic error suppression techniques., Comment: 20 pages, 16 figures

A fundamental question on the use of ML models concerns the explanation of their predictions for increasing transparency in decision-making. Although several interpretability methods have emerged, some gaps regarding the reliability of their explanations have been identified. For instance, most methods are unstable (meaning that they give very different explanations with small changes in the data), and do not cope well with irrelevant features (that is, features not related to the label). This article introduces two new interpretability methods, namely VarImp and SupClus, that overcome these issues by using local regressions fits with a weighted distance that takes into account variable importance. Whereas VarImp generates explanations for each instance and can be applied to datasets with more complex relationships, SupClus interprets clusters of instances with similar explanations and can be applied to simpler datasets where clusters can be found. We compare our methods with state-of-the art approaches and show that it yields better explanations according to several metrics, particularly in high-dimensional problems with irrelevant features, as well as when the relationship between features and target is non-linear.

Extracting knowledge from unlabeled texts using machine learning algorithms can be complex. Document categorization and information retrieval are two applications that may benefit from unsupervised learning (e.g., text clustering and topic modeling), including exploratory data analysis. However, the unsupervised learning paradigm poses reproducibility issues. The initialization can lead to variability depending on the machine learning algorithm. Furthermore, the distortions can be misleading when regarding cluster geometry. Amongst the causes, the presence of outliers and anomalies can be a determining factor. Despite the relevance of initialization and outlier issues for text clustering and topic modeling, the authors did not find an in-depth analysis of them. This survey provides a systematic literature review (2011-2022) of these subareas and proposes a common terminology since similar procedures have different terms. The authors describe research opportunities, trends, and open issues. The appendices summarize the theoretical background of the text vectorization, the factorization, and the clustering algorithms that are directly or indirectly related to the reviewed works.

We explore the near-term intersection of quantum computing with the transport sector. To support near-term integration, we introduce a framework for assessing the suitability of transport optimization problems for obtaining potential performance enhancement using quantum algorithms. Given a suitable problem, we then present a workflow for obtaining valuable transport solutions using quantum computers, articulate the limitations on contemporary systems, and describe newly available performance-enhancing tools applicable to current commercial quantum computing systems. We make this integration process concrete by following the assessment framework and integration workflow for an exemplary vehicle routing optimization problem: the Capacitated Vehicle Routing Problem. We present novel advances to exponentially reduce the required computational resources, and experimentally demonstrate a prototype implementation exhibiting over 20X circuit performance enhancement on a real quantum device., Comment: Accepted as a scientific paper for the 28th ITS World Congress 2022 Los Angeles

Although deep neural networks are capable of achieving performance superior to humans on various tasks, they are notorious for requiring large amounts of data and computing resources, restricting their success to domains where such resources are available. Metalearning methods can address this problem by transferring knowledge from related tasks, thus reducing the amount of data and computing resources needed to learn new tasks. We organize the MetaDL competition series, which provide opportunities for research groups all over the world to create and experimentally assess new meta-(deep)learning solutions for real problems. In this paper, authored collaboratively between the competition organizers and the top-ranked participants, we describe the design of the competition, the datasets, the best experimental results, as well as the top-ranked methods in the NeurIPS 2021 challenge, which attracted 15 active teams who made it to the final phase (by outperforming the baseline), making over 100 code submissions during the feedback phase. The solutions of the top participants have been open-sourced. The lessons learned include that learning good representations is essential for effective transfer learning., Comment: version 2 is the correct version, including supplementary material at the end

Document understanding is a key business process in the data-driven economy since documents are central to knowledge discovery and business insights. Converting documents into a machine-processable format is a particular challenge here due to their huge variability in formats and complex structure. Accordingly, many algorithms and machine-learning methods emerged to solve particular tasks such as Optical Character Recognition (OCR), layout analysis, table-structure recovery, figure understanding, etc. We observe the adoption of such methods in document understanding solutions offered by all major cloud providers. Yet, publications outlining how such services are designed and optimized to scale in the cloud are scarce. In this paper, we focus on the case of document conversion to illustrate the particular challenges of scaling a complex data processing pipeline with a strong reliance on machine-learning methods on cloud infrastructure. Our key objective is to achieve high scalability and responsiveness for different workload profiles in a well-defined resource budget. We outline the requirements, design, and implementation choices of our document conversion service and reflect on the challenges we faced. Evidence for the scaling behavior and resource efficiency is provided for two alternative workload distribution strategies and deployment configurations. Our best-performing method achieves sustained throughput of over one million PDF pages per hour on 3072 CPU cores across 192 nodes., Comment: 11 pages, 7 figures, to be published in IEEE CLOUD 2022

The field of Continual Learning investigates the ability to learn consecutive tasks without losing performance on those previously learned. Its focus has been mainly on incremental classification tasks. We believe that research in continual object detection deserves even more attention due to its vast range of applications in robotics and autonomous vehicles. This scenario is more complex than conventional classification given the occurrence of instances of classes that are unknown at the time, but can appear in subsequent tasks as a new class to be learned, resulting in missing annotations and conflicts with the background label. In this review, we analyze the current strategies proposed to tackle the problem of class-incremental object detection. Our main contributions are: (1) a short and systematic review of the methods that propose solutions to traditional incremental object detection scenarios; (2) A comprehensive evaluation of the existing approaches using a new metric to quantify the stability and plasticity of each technique in a standard way; (3) an overview of the current trends within continual object detection and a discussion of possible future research directions.

We consider the subgroup of points of finite orbit through the action of an endomorphism of a virtually free group, with particular emphasis on the subgroup of eventually fixed points, EvFix($\varphi$): points whose orbit contains a fixed point. We provide an algorithm to compute the subgroup of fixed points of an endomorphism of a finitely generated virtually free group and prove that finite orbits have cardinality bounded by a computable constant, which allows us to solve several algorithmic problems: deciding if $\varphi$ is a finite order element of End($G$), if $\varphi$ is aperiodic, if EvFix($\varphi$) is finitely generated and, in the free group case, whether EvFix($\varphi$) is a normal subgroup of $F_n$ or not. We also present a bound for the rank of EvFix($\varphi$) in case it is finitely generated., Comment: 15 pages, comments are welcome

Quantum information processing holds great promise for pushing beyond the current frontiers in computing. Specifically, quantum computation promises to accelerate the solving of certain problems, and there are many opportunities for innovation based on applications in chemistry, engineering, and finance. To harness the full potential of quantum computing, however, we must not only place emphasis on manufacturing better qubits, advancing our algorithms, and developing quantum software. To scale devices to the fault tolerant regime, we must refine device-level quantum control. On May 17-18, 2021, the Chicago Quantum Exchange (CQE) partnered with IBM Quantum and Super.tech to host the Pulse-level Quantum Control Workshop. At the workshop, representatives from academia, national labs, and industry addressed the importance of fine-tuning quantum processing at the physical layer. The purpose of this report is to summarize the topics of this meeting for the quantum community at large.