Search

Go-or-grow approaches represent a specific class of mathematical models used to describe populations where individuals either migrate or reproduce, but not both simultaneously. These models have a wide range of applications in biology and medicine, chiefly among those the modeling of brain cancer spread. The analysis of go-or-grow models has inspired new mathematics, and it is the purpose of this review to highlight interesting and challenging mathematical properties of reaction--diffusion models of the go-or-grow type. We provide a detailed review of biological and medical applications before focusing on key results concerning solution existence and uniqueness, pattern formation, critical domain size problems, and traveling waves. We present new general results related to the critical domain size and traveling wave problems, and we connect these findings to the existing literature. Moreover, we demonstrate the high level of instability inherent in go-or-grow models. We argue that there is currently no accurate numerical solver for these models, and emphasize that special care must be taken when dealing with the "monster on a leash"., Comment: 40 pages, 5 figures

In this paper, we first propose a natural generalization of the well-known compare-and-swap object, one that replaces the equality comparison with an arbitrary comparator. We then present a simple wait-free universal construction using this object and prove its correctness., Comment: 12 pages

Oblivious RAM (ORAM) is a well-researched primitive to hide the memory access pattern of a RAM computation; it has a variety of applications in trusted computing, outsourced storage, and multiparty computation. In this paper, we study the so-called offline ORAM in which the sequence of memory access locations to be hidden is known in advance. Apart from their theoretical significance, offline ORAMs can be used to construct efficient oblivious algorithms. We obtain the first optimal offline ORAM with perfect security from oblivious priority queues via time-forward processing. For this, we present a simple construction of an oblivious priority queue with perfect security. Our construction achieves an asymptotically optimal (amortized) runtime of $\Theta(\log N)$ per operation for a capacity of $N$ elements and is of independent interest. Building on our construction, we additionally present efficient external-memory instantiations of our oblivious, perfectly-secure construction: For the cache-aware setting, we match the optimal I/O complexity of $\Theta(\frac{1}{B} \log \frac{N}{M})$ per operation (amortized), and for the cache-oblivious setting we achieve a near-optimal I/O complexity of $O(\frac{1}{B} \log \frac{N}{M} \log\log_M N)$ per operation (amortized)., Comment: 23 pages, full version of the paper to appear in ISAAC 2024

We study the problem of learning the clusters of a given graph in the self-directed learning setup. This learning setting is a variant of online learning, where rather than an adversary determining the sequence in which nodes are presented, the learner autonomously and adaptively selects them. While self-directed learning of Euclidean halfspaces, linear functions, and general abstract multi-class hypothesis classes was recently considered, no results previously existed specifically for self-directed node classification on graphs. In this paper, we address this problem developing efficient algorithms for it. More specifically, we focus on the case of (geodesically) convex clusters, i.e., for every two nodes sharing the same label, all nodes on every shortest path between them also share the same label. In particular, we devise a polynomial-time algorithm that makes only $3(h(G)+1)^4 \ln n$ mistakes on graphs with two convex clusters, where $n$ is the total number of nodes and $h(G)$ is the Hadwiger number, i.e., the size of the largest clique minor of the graph $G$. We also show that our algorithm is robust to the case that clusters are slightly non-convex, still achieving a mistake bound logarithmic in $n$. Finally, for the more standard case of homophilic clusters, where strongly connected nodes tend to belong the same class, we devise a simple and efficient algorithm.

Can a deep neural network be approximated by a small decision tree based on simple features? This question and its variants are behind the growing demand for machine learning models that are *interpretable* by humans. In this work we study such questions by introducing *interpretable approximations*, a notion that captures the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $\mathcal{H}$. In particular, we consider the approximation of a binary concept $c$ by decision trees based on a simple class $\mathcal{H}$ (e.g., of bounded VC dimension), and use the tree depth as a measure of complexity. Our primary contribution is the following remarkable trichotomy. For any given pair of $\mathcal{H}$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $\mathcal{H}$ with arbitrary accuracy; (ii) $c$ can be approximated by $\mathcal{H}$ with arbitrary accuracy, but there exists no universal rate that bounds the complexity of the approximations as a function of the accuracy; or (iii) there exists a constant $\kappa$ that depends only on $\mathcal{H}$ and $c$ such that, for *any* data distribution and *any* desired accuracy level, $c$ can be approximated by $\mathcal{H}$ with a complexity not exceeding $\kappa$. This taxonomy stands in stark contrast to the landscape of supervised classification, which offers a complex array of distribution-free and universally learnable scenarios. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-free) complexity. We extend our trichotomy to classes $\mathcal{H}$ of unbounded VC dimension and give characterizations of interpretability based on the algebra generated by $\mathcal{H}$., Comment: To appear at COLT 2024

Literature is the primary expression of scientific knowledge and an important source of research data. However, scientific knowledge expressed in narrative text documents is not inherently machine reusable. To facilitate knowledge reuse, e.g. for synthesis research, scientific knowledge must be extracted from articles and organized into databases post-publication. The high time costs and inaccuracies associated with completing these activities manually has driven the development of techniques that automate knowledge extraction. Tackling the problem with a different mindset, we propose a pre-publication approach, known as reborn, that ensures scientific knowledge is born reusable, i.e. produced in a machine-reusable format during knowledge production. We implement the approach using the Open Research Knowledge Graph infrastructure for FAIR scientific knowledge organization. We test the approach with three use cases, and discuss the role of publishers and editors in scaling the approach. Our results suggest that the proposed approach is superior compared to classical manual and semi-automated post-publication extraction techniques in terms of knowledge richness and accuracy as well as technological simplicity.

We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by monophonic halfspaces, partitions of the vertices that are convex in a certain abstract sense. Monophonic halfspaces, and related notions such as geodesic halfspaces,have recently attracted interest, and several connections have been drawn between their properties(e.g., their VC dimension) and the structure of the underlying graph $G$. We prove several novel results for learning monophonic halfspaces in the supervised, online, and active settings. Our main result is that a monophonic halfspace can be learned with near-optimal passive sample complexity in time polynomial in $n = |V(G)|$. This requires us to devise a polynomial-time algorithm for consistent hypothesis checking, based on several structural insights on monophonic halfspaces and on a reduction to $2$-satisfiability. We prove similar results for the online and active settings. We also show that the concept class can be enumerated with delay $\operatorname{poly}(n)$, and that empirical risk minimization can be performed in time $2^{\omega(G)}\operatorname{poly}(n)$ where $\omega(G)$ is the clique number of $G$. These results answer open questions from the literature (Gonz\'alez et al., 2020), and show a contrast with geodesic halfspaces, for which some of the said problems are NP-hard (Seiffarth et al., 2023)., Comment: To appear at COLT 2024

Quantum chemistry simulations offer a cost-effective way for computational design of BODIPY photosensitizers with potential use in photodynamic therapy (PDT). However, accurate predictions of photophysical properties, such as excitation energies, pose a challenge for the popular time-dependent density functional theory (TDDFT) and equation-of-motion coupled cluster with singles and doubles (EOM-CCSD) methods. By contrast, reliable descriptions can be achieved by multi-reference quantum chemistry methods, though unfortunately, their computational cost grows exponentially with the number of correlated electrons. Alternatively, quantum computing holds a great potential for exact simulation of photophysical properties in a computationally more efficient way. To this end, we introduce the state-specific $\Delta$UCCSD-VQE (unitary coupled cluster with singles and doubles variational quantum eigensolver) and $\Delta$ADAPT-VQE methods in which the electronically excited state is calculated via a non-Aufbau electronic configuration. The accuracy and capability of the developed methods are assessed against experimentally determined excitation energies for six BODIPY-derivatives. We show that the proposed methods predict accurate vertical excitation energies that are not only in good agreement with experimental reference data but also outperform popular quantum chemistry methods, such as TDDFT and EOM-CCSD. Spurred by its impressive performance and simplicity, we are confident that $\Delta$ADAPT will emerge as the method of choice for guiding the rational design of photosensitizers for PDT and photocatalysis in the era of near-term quantum computing.

Linearizable datastores are desirable because they provide users with the illusion that the datastore is run on a single machine that performs client operations one at a time. To reduce the performance cost of providing this illusion, many specialized algorithms for linearizable reads have been proposed which significantly improve read performance compared to write performance. The main difference between these specialized algorithms is their performance under different workloads. Unfortunately, since a datastore's workload is often unknown or changes over time and system designers must decide on a single read algorithm to implement ahead of time, a datastore's performance is often suboptimal as it cannot adapt to workload changes. In this paper, we lay the groundwork for addressing this problem by proposing Chameleon, an algorithm for linearizable reads that provides a principled approach for datastores to switch between existing read algorithms at runtime. The key observation that enables this generalization is that all existing algorithms are specific read-write quorum systems. Chameleon constructs a generic read-write quorum system, by using tokens that are included to complete write and read operations. This token quorum system enables Chameleon to mimic existing read algorithms and switch between them by transferring these tokens between processes., Comment: 7 pages, 4 figures

We study the classic problem of prediction with expert advice under bandit feedback. Our model assumes that one action, corresponding to the learner's abstention from play, has no reward or loss on every trial. We propose the CBA algorithm, which exploits this assumption to obtain reward bounds that can significantly improve those of the classical Exp4 algorithm. We can view our problem as the aggregation of confidence-rated predictors when the learner has the option of abstention from play. Importantly, we are the first to achieve bounds on the expected cumulative reward for general confidence-rated predictors. In the special case of specialists we achieve a novel reward bound, significantly improving previous bounds of SpecialistExp (treating abstention as another action). As an example application, we discuss learning unions of balls in a finite metric space. In this contextual setting, we devise an efficient implementation of CBA, reducing the runtime from quadratic to almost linear in the number of contexts. Preliminary experiments show that CBA improves over existing bandit algorithms.

We investigate novel random graph embeddings that can be computed in expected polynomial time and that are able to distinguish all non-isomorphic graphs in expectation. Previous graph embeddings have limited expressiveness and either cannot distinguish all graphs or cannot be computed efficiently for every graph. To be able to approximate arbitrary functions on graphs, we are interested in efficient alternatives that become arbitrarily expressive with increasing resources. Our approach is based on Lov\'asz' characterisation of graph isomorphism through an infinite dimensional vector of homomorphism counts. Our empirical evaluation shows competitive results on several benchmark graph learning tasks., Comment: accepted for publication at ICML 2023

In clinical practice, many diagnosis tasks rely on the identification of cells in histopathology images. While supervised machine learning techniques require labels, providing manual cell annotations is time-consuming due to the large number of cells. In this paper, we propose a self-supervised framework (VOLTA) for cell representation learning in histopathology images using a novel technique that accounts for the cell's mutual relationship with its environment for improved cell representations. We subjected our model to extensive experiments on the data collected from multiple institutions around the world comprising of over 700,000 cells, four cancer types, and cell types ranging from three to six categories for each dataset. The results show that our model outperforms the state-of-the-art models in cell representation learning. To showcase the potential power of our proposed framework, we applied VOLTA to ovarian and endometrial cancers with very small sample sizes (10-20 samples) and demonstrated that our cell representations can be utilized to identify the known histotypes of ovarian cancer and provide novel insights that link histopathology and molecular subtypes of endometrial cancer. Unlike supervised deep learning models that require large sample sizes for training, we provide a framework that can empower new discoveries without any annotation data in situations where sample sizes are limited.

Preservation of the chemical and structural integrity of samples that will be brought back from Mars is paramount to achieving the scientific objectives of MSR. Given our knowledge of the nature of the samples retrieved at Jezero by Perseverance, at least two options need to be tested for opening the sample tubes: (1) One or two radial cuts at the end of the tube to slide the sample out. (2) Two radial cuts at the ends of the tube and two longitudinal cuts to lift the upper half of the tube and access the sample. Strategy 1 will likely minimize contamination but incurs the risk of affecting the physical integrity of weakly consolidated samples. Strategy 2 will be optimal for preserving the physical integrity of the samples but increases the risk of contamination and mishandling of the sample as more manipulations and additional equipment will be needed. A flexible approach to opening the sample tubes is therefore required, and several options need to be available, depending on the nature of the rock samples returned. Both opening strategies 1 and 2 may need to be available when the samples are returned to handle different sample types (e.g., loosely bound sediments vs. indurated magmatic rocks). This question should be revisited after engineering tests are performed on analogue samples. The MSR sample tubes will have to be opened under stringent BSL4 conditions and this aspect needs to be integrated into the planning., Comment: 8 pages, 3 figures, 1 table, report NASA-ESA Mars Rock Team Report

Graph neural networks (GNNs) are the primary tool for processing graph-structured data. Unfortunately, the most commonly used GNNs, called Message Passing Neural Networks (MPNNs) suffer from several fundamental limitations. To overcome these limitations, recent works have adapted the idea of positional encodings to graph data. This paper draws inspiration from the recent success of Laplacian-based positional encoding and defines a novel family of positional encoding schemes for graphs. We accomplish this by generalizing the optimization problem that defines the Laplace embedding to more general dissimilarity functions rather than the 2-norm used in the original formulation. This family of positional encodings is then instantiated by considering p-norms. We discuss a method for calculating these positional encoding schemes, implement it in PyTorch and demonstrate how the resulting positional encoding captures different properties of the graph. Furthermore, we demonstrate that this novel family of positional encodings can improve the expressive power of MPNNs. Lastly, we present preliminary experimental results., Comment: Accepted at NeurIPS Workshop on Symmetry and Geometry in Neural Representations: Extended Abstract Track 2022