title: 1/f noise spectroscopy and noise tailoring of nanoelectronic devices

abstract: In this paper, we review the 1/f-type noise properties of nanoelectronic devices focusing on three demonstrative platforms: resistive switching memories, graphene nanogaps and single-molecule nanowires. The functionality of such ultrasmall devices is confined to an extremely small volume, where bulk considerations on the noise loose their validity: the relative contribution of a fluctuator heavily depends on its distance from the device bottleneck, and the noise characteristics are sensitive to the nanometer-scale device geometry and the details of the mostly non-classical transport mechanism. All these are reflected by a highly system-specific dependence of the noise properties on the active device volume (and the related device resitance), the frequency, or the applied voltage. Accordingly, 1/f-type noise measurements serve as a rich fingerprint of the relevant transport and noise-generating mechanisms in the studied nanoelectronic systems. Finally, we demonstrate that not only the fundamental understanding and the targeted noise suppression is fueled by the 1/f-type noise analysis, but novel probabilistic computing hardware platforms heavily seek well tailorable nanoelectric noise sources.


title: Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs

abstract: We address the issue of safety in reinforcement learning. We pose the problem in an episodic framework of a constrained Markov decision process. Existing results have shown that it is possible to achieve a reward regret of $\tilde{\mathcal{O}}(\sqrt{K})$ while allowing an $\tilde{\mathcal{O}}(\sqrt{K})$ constraint violation in $K$ episodes. A critical question that arises is whether it is possible to keep the constraint violation even smaller. We show that when a strictly safe policy is known, then one can confine the system to zero constraint violation with arbitrarily high probability while keeping the reward regret of order $\tilde{\mathcal{O}}(\sqrt{K})$. The algorithm which does so employs the principle of optimistic pessimism in the face of uncertainty to achieve safe exploration. When no strictly safe policy is known, though one is known to exist, then it is possible to restrict the system to bounded constraint violation with arbitrarily high probability. This is shown to be realized by a primal-dual algorithm with an optimistic primal estimate and a pessimistic dual update.


title: Massively Parallel and Dynamic Algorithms for Minimum Size Clustering

abstract: In this paper, we study the $r$-gather problem, a natural formulation of minimum-size clustering in metric spaces. The goal of $r$-gather is to partition $n$ points into clusters such that each cluster has size at least $r$, and the maximum radius of the clusters is minimized. This additional constraint completely changes the algorithmic nature of the problem, and many clustering techniques fail. Also previous dynamic and parallel algorithms do not achieve desirable complexity. We propose algorithms both in the Massively Parallel Computation (MPC) model and in the dynamic setting. Our MPC algorithm handles input points from the Euclidean space $\mathbb{R}^d$. It computes an $O(1)$-approximate solution of $r$-gather in $O(\log^{\varepsilon} n)$ rounds using total space $O(n^{1+\gamma}\cdot d)$ for arbitrarily small constants $\varepsilon,\gamma > 0$. In addition our algorithm is fully scalable, i.e., there is no lower bound on the memory per machine. Our dynamic algorithm maintains an $O(1)$-approximate $r$-gather solution under insertions/deletions of points in a metric space with doubling dimension $d$. The update time is $r \cdot 2^{O(d)}\cdot \log^{O(1)}\Delta$ and the query time is $2^{O(d)}\cdot \log^{O(1)}\Delta$, where $\Delta$ is the ratio between the largest and the smallest distance.


title: Ensemble Markov chain Monte Carlo with teleporting walkers

abstract: We introduce an ensemble Markov chain Monte Carlo approach to sampling from a probability density with known likelihood. This method upgrades an underlying Markov chain by allowing an ensemble of such chains to interact via a process in which one chain's state is cloned as another's is deleted. This effective teleportation of states can overcome issues of metastability in the underlying chain, as the scheme enjoys rapid mixing once the modes of the target density have been populated. We derive a mean-field limit for the evolution of the ensemble. We analyze the global and local convergence of this mean-field limit, showing asymptotic convergence independent of the spectral gap of the underlying Markov chain, and moreover we interpret the limiting evolution as a gradient flow. We explain how interaction can be applied selectively to a subset of state variables in order to maintain advantage on very high-dimensional problems. Finally we present the application of our methodology to Bayesian hyperparameter estimation for Gaussian process regression.


title: Towards real time assessment of earthfill dams via Model Order Reduction

abstract: The use of Internet of Things (IoT) technologies is becoming a preferred solution for the assessment of tailings dams' safety. Real-time sensor monitoring proves to be a key tool for reducing the risk related to these ever-evolving earth-fill structures, that exhibit a high rate of sudden and hazardous failures. In order to optimally exploit real-time embankment monitoring, one major hindrance has to be overcome: the creation of a supporting numerical model for stability analysis, with rapid-enough response to perform data assimilation in real time. A model should be built, such that its response can be obtained faster than the physical evolution of the analyzed phenomenon. In this work, Reduced Order Modelling (ROM) is used to boost computational efficiency in solving the coupled hydro-mechanical system of equations governing the problem. The Reduced Basis method is applied to the coupled hydro-mechanical equations that govern the groundwater flow, that are made non-linear as a result of considering an unsaturated soil. The resulting model's performance is assessed by solving a 2D and a 3D problem relevant to tailings dams' safety. The ROM technique achieves a speedup of 3 to 15 times with respect to the full-order model (FOM) while maintaining high levels of accuracy.


title: Egalitarian Resource Sharing Over Multiple Rounds

abstract: It is often beneficial for agents to pool their resources in order to better accommodate fluctuations in individual demand. Many multi-round resource allocation mechanisms operate in an online manner: in each round, the agents specify their demands for that round, and the mechanism determines a corresponding allocation. In this paper, we focus instead on the offline setting in which the agents specify their demand for each round at the outset. We formulate a specific resource allocation problem in this setting, and design and analyze an associated mechanism based on the solution concept of lexicographic maximin fairness. We present an efficient implementation of our mechanism, and prove that it is envy-free, non-wasteful, resource monotonic, population monotonic, and group strategyproof. We also prove that our mechanism guarantees each agent at least half of the utility that they can obtain by not sharing their resources. We complement these positive results by proving that no maximin fair mechanism can improve on the aforementioned factor of one-half.


title: RegionViT: Regional-to-Local Attention for Vision Transformers

abstract: Vision transformer (ViT) has recently shown its strong capability in achieving comparable results to convolutional neural networks (CNNs) on image classification. However, vanilla ViT simply inherits the same architecture from the natural language processing directly, which is often not optimized for vision applications. Motivated by this, in this paper, we propose a new architecture that adopts the pyramid structure and employ a novel regional-to-local attention rather than global self-attention in vision transformers. More specifically, our model first generates regional tokens and local tokens from an image with different patch sizes, where each regional token is associated with a set of local tokens based on the spatial location. The regional-to-local attention includes two steps: first, the regional self-attention extract global information among all regional tokens and then the local self-attention exchanges the information among one regional token and the associated local tokens via self-attention. Therefore, even though local self-attention confines the scope in a local region but it can still receive global information. Extensive experiments on four vision tasks, including image classification, object and keypoint detection, semantics segmentation and action recognition, show that our approach outperforms or is on par with state-of-the-art ViT variants including many concurrent works. Our source codes and models are available at https://github.com/ibm/regionvit.


title: Account of the baryonic feedback effect in gamma-ray measurements of intergalactic magnetic fields

abstract: Intergalactic magnetic fields in the voids of the large-scale structure can be probed via measurements of secondary gamma-ray emission from gamma-ray interactions with extragalactic background light. Lower bounds on the magnetic field in the voids were derived from the non-detection of this emission. It is not clear a priori what kind of magnetic field is responsible for the suppression of the secondary gamma-ray flux: a cosmological magnetic field that might be filling the voids or the field spread by galactic winds driven by star formation and active galactic nuclei. We used IllustrisTNG cosmological simulations to study the effect of magnetized galactic wind bubbles on the secondary gamma-ray flux. We show that within the IllustrisTNG model of baryonic feedback, the galactic wind bubbles typically provide energy-independent secondary flux suppression at the level of about 10%. The observed flux suppression effect has to be due to the cosmological magnetic field in the voids. This might not be the case for a special case when the primary gamma-ray source has a hard intrinsic gamma-ray spectrum that peaks in the energy range above 50 TeV. In this case, the observational data may be strongly affected by the magnetized bubble that is blown by the source host galaxy.


title: Conservation laws in coupled cluster dynamics at finite-temperature

abstract: We extend the finite-temperature Keldysh non-equilibrium coupled cluster theory (Keldysh-CC) [{\it J. Chem. Theory Comput.} \textbf{2019}, 15, 6137-6253] to include a time-dependent orbital basis. When chosen to minimize the action, such a basis restores local and global conservation laws (Ehrenfest's theorem) for all one-particle properties, while remaining energy conserving for time-independent Hamiltonians. We present the time-dependent orbital-optimized coupled cluster doubles method (Keldysh-OCCD) in analogy with the formalism for zero-temperature dynamics, extended to finite temperatures through the time-dependent action on the Keldysh contour. To demonstrate the conservation property and understand the numerical performance of the method, we apply it to several problems of non-equilibrium finite-temperature dynamics: a 1D Hubbard model with a time-dependent Peierls phase, laser driving of molecular H$_2$, driven dynamics in warm-dense silicon, and transport in the single impurity Anderson model.


title: The R-U-A-Robot Dataset: Helping Avoid Chatbot Deception by Detecting User Questions About Human or Non-Human Identity

abstract: Humans are increasingly interacting with machines through language, sometimes in contexts where the user may not know they are talking to a machine (like over the phone or a text chatbot). We aim to understand how system designers and researchers might allow their systems to confirm its non-human identity. We collect over 2,500 phrasings related to the intent of ``Are you a robot?". This is paired with over 2,500 adversarially selected utterances where only confirming the system is non-human would be insufficient or disfluent. We compare classifiers to recognize the intent and discuss the precision/recall and model complexity tradeoffs. Such classifiers could be integrated into dialog systems to avoid undesired deception. We then explore how both a generative research model (Blender) as well as two deployed systems (Amazon Alexa, Google Assistant) handle this intent, finding that systems often fail to confirm their non-human identity. Finally, we try to understand what a good response to the intent would be, and conduct a user study to compare the important aspects when responding to this intent.


title: Generic E-Variables for Exact Sequential k-Sample Tests that allow for Optional Stopping

abstract: We develop E-variables for testing whether two or more data streams come from the same source or not, and more generally, whether the difference between the sources is larger than some minimal effect size. These E-variables lead to exact, nonasymptotic tests that remain safe, i.e. keep their type-I error guarantees, under flexible sampling scenarios such as optional stopping and continuation. In special cases our E-variables also have an optimal 'growth' property under the alternative. While the construction is generic, we illustrate it through the special case of k x 2 contingency tables, where we also allow for the incorporation of different restrictions on a composite alternative. Comparison to p-value analysis in simulations and a real-world example show that E-variables, through their flexibility, often allow for early stopping of data collection, thereby retaining similar power as classical methods, while also retaining the option of extending or combining data afterwards.


title: Efficient Classification of Very Large Images with Tiny Objects

abstract: An increasing number of applications in computer vision, specially, in medical imaging and remote sensing, become challenging when the goal is to classify very large images with tiny informative objects. Specifically, these classification tasks face two key challenges: $i$) the size of the input image is usually in the order of mega- or giga-pixels, however, existing deep architectures do not easily operate on such big images due to memory constraints, consequently, we seek a memory-efficient method to process these images; and $ii$) only a very small fraction of the input images are informative of the label of interest, resulting in low region of interest (ROI) to image ratio. However, most of the current convolutional neural networks (CNNs) are designed for image classification datasets that have relatively large ROIs and small image sizes (sub-megapixel). Existing approaches have addressed these two challenges in isolation. We present an end-to-end CNN model termed Zoom-In network that leverages hierarchical attention sampling for classification of large images with tiny objects using a single GPU. We evaluate our method on four large-image histopathology, road-scene and satellite imaging datasets, and one gigapixel pathology dataset. Experimental results show that our model achieves higher accuracy than existing methods while requiring less memory resources.


title: Meta-Learning with Fewer Tasks through Task Interpolation

abstract: Meta-learning enables algorithms to quickly learn a newly encountered task with just a few labeled examples by transferring previously learned knowledge. However, the bottleneck of current meta-learning algorithms is the requirement of a large number of meta-training tasks, which may not be accessible in real-world scenarios. To address the challenge that available tasks may not densely sample the space of tasks, we propose to augment the task set through interpolation. By meta-learning with task interpolation (MLTI), our approach effectively generates additional tasks by randomly sampling a pair of tasks and interpolating the corresponding features and labels. Under both gradient-based and metric-based meta-learning settings, our theoretical analysis shows MLTI corresponds to a data-adaptive meta-regularization and further improves the generalization. Empirically, in our experiments on eight datasets from diverse domains including image recognition, pose prediction, molecule property prediction, and medical image classification, we find that the proposed general MLTI framework is compatible with representative meta-learning algorithms and consistently outperforms other state-of-the-art strategies.


title: A Diversity-Aware Memetic Algorithm for the Linear Ordering Problem: Improving Best-Known Solutions for Standard Benchmarks

abstract: The Linear Ordering Problem (LOP) is a very popular NP-hard combinatorial optimization problem with many practical applications that may require the use of large instances. The Linear Ordering Library (LOLIB) gathers a set of standard benchmarks widely used in the validation of solvers for the LOP. Among them, the xLOLIB2 collects some of the largest and most challenging instances in current literature. In this work, we present new best-known solutions for each of the 200 complex instances that comprises xLOLIB2. Moreover, the proposal devised in this research is able to achieve all current best-known solutions in the rest of instances of LOLIB and improve them in other 93 cases out of 485, meaning that important advances in terms of quality and robustness are attained. This important advance in the field of the LOP has been possible thanks to the development of a novel Memetic Algorithm (MA) that was designed by taking into account some of the weaknesses of state-of-the-art LOP solvers. One of the keys to success is that the novel proposal allows for a gradual shift from exploration to exploitation, which is done by taking into account the stopping criterion and elapsed period of execution to alter the internal decisions taken by the optimizer. The novel diversity-aware proposal is called the Memetic Algorithm with Explicit Diversity Management (MA-EDM) and extensive comparisons against state-of-the-art techniques provide insights into the reasons for the superiority of MA-EDM.


title: Enterprise-Scale Search: Accelerating Inference for Sparse Extreme Multi-Label Ranking Trees

abstract: Tree-based models underpin many modern semantic search engines and recommender systems due to their sub-linear inference times. In industrial applications, these models operate at extreme scales, where every bit of performance is critical. Memory constraints at extreme scales also require that models be sparse, hence tree-based models are often back-ended by sparse matrix algebra routines. However, there are currently no sparse matrix techniques specifically designed for the sparsity structure one encounters in tree-based models for extreme multi-label ranking/classification (XMR/XMC) problems. To address this issue, we present the masked sparse chunk multiplication (MSCM) technique, a sparse matrix technique specifically tailored to XMR trees. MSCM is easy to implement, embarrassingly parallelizable, and offers a significant performance boost to any existing tree inference pipeline at no cost. We perform a comprehensive study of MSCM applied to several different sparse inference schemes and benchmark our methods on a general purpose extreme multi-label ranking framework. We observe that MSCM gives consistently dramatic speedups across both the online and batch inference settings, single- and multi-threaded settings, and on many different tree models and datasets. To demonstrate its utility in industrial applications, we apply MSCM to an enterprise-scale semantic product search problem with 100 million products and achieve sub-millisecond latency of 0.88 ms per query on a single thread -- an 8x reduction in latency over vanilla inference techniques. The MSCM technique requires absolutely no sacrifices to model accuracy as it gives exactly the same results as standard sparse matrix techniques. Therefore, we believe that MSCM will enable users of XMR trees to save a substantial amount of compute resources in their inference pipelines at very little cost.


title: Non-symmorphic symmetry and field-driven odd-parity pairing in CeRh$_2$As$_2$

abstract: Recently, evidence has emerged for a field-induced even- to odd-parity superconducting phase transition in CeRh$_2$As$_2$ [S. Khim et al., Science 373 1012 (2021)]. Here we argue that the P4/nmm non-symmorphic crystal structure of CeRh$_2$As$_2$ plays a key role in enabling this transition by ensuring large spin-orbit interactions near the Brillouin zone boundaries, which naturally leads to the required near-degeneracy of the even- and odd-parity channels. We further comment on the relevance of our theory to FeSe, which crystallizes in the same structure.


title: Contact Tracing Information Improves the Performance of Group Testing Algorithms

abstract: Group testing can help maintain a widespread testing program using fewer resources amid a pandemic. In group testing, we are given $n$ samples, one per individual. These samples are arranged into $m < n$ pooled samples, where each pool is obtained by mixing a subset of the $n$ individual samples. Infected individuals are then identified using a group testing algorithm. In this paper, we use side information (SI) collected from contact tracing (CT) within nonadaptive/single-stage group testing algorithms. We generate CT SI data by incorporating characteristics of disease spread between individuals. These data are fed into two signal and measurement models for group testing, and numerical results show that our algorithms provide improved sensitivity and specificity. We also show how to incorporate CT SI into the design of the pooling matrix. That said, our numerical results suggest that the utilization of SI in the pooling matrix design based on the minimization of a weighted coherence measure does not yield significant performance gains beyond the incorporation of SI in the group testing algorithm.


title: A Discrete Variational Derivation of Accelerated Methods in Optimization

abstract: Many of the new developments in machine learning are connected with gradient-based optimization methods. Recently, these methods have been studied using a variational perspective. This has opened up the possibility of introducing variational and symplectic methods using geometric integration. In particular, in this paper, we introduce variational integrators which allow us to derive different methods for optimization. Using both, Hamilton's and Lagrange-d'Alembert's principle, we derive two families of respective optimization methods in one-to-one correspondence that generalize Polyak's heavy ball and the well known Nesterov accelerated gradient method, the second of which mimics the behavior of the first reducing the oscillations of classical momentum methods. However, since the systems considered are explicitly time-dependent, the preservation of symplecticity of autonomous systems occurs here solely on the fibers. Several experiments exemplify the result.


title: Hidden Markov Modeling for Maximum Likelihood Neuron Reconstruction

abstract: Recent advances in brain clearing and imaging have made it possible to image entire mammalian brains at sub-micron resolution. These images offer the potential to assemble brain-wide atlases of neuron morphology, but manual neuron reconstruction remains a bottleneck. Several automatic reconstruction algorithms exist, but most focus on single neuron images. In this paper, we present a probabilistic reconstruction method, ViterBrain, which combines a hidden Markov state process that encodes neuron geometry with a random field appearance model of neuron fluorescence. Our method utilizes dynamic programming to compute the global maximizers of what we call the "most probable" neuron path. Our most probable estimation method models the task of reconstructing neuronal processes in the presence of other neurons, and thus is applicable in images with several neurons. Our method operates on image segmentations in order to leverage cutting edge computer vision technology. We applied our algorithm to imperfect image segmentations where false negatives severed neuronal processes, and showed that it can follow axons in the presence of noise or nearby neurons. Additionally, it creates a framework where users can intervene to, for example, fit start and endpoints. The code used in this work is available in our open-source Python package brainlit.


title: Subgroup Fairness in Two-Sided Markets

abstract: It is well known that two-sided markets are unfair in a number of ways. For instance, female workers at Uber earn less than their male colleagues per mile driven. Similar observations have been made for other minority subgroups in other two-sided markets. Here, we suggest a novel market-clearing mechanism for two-sided markets, which promotes equalisation of the pay per hour worked across multiple subgroups, as well as within each subgroup. In the process, we introduce a novel notion of subgroup fairness (which we call Inter-fairness), which can be combined with other notions of fairness within each subgroup (called Intra-fairness), and the utility for the customers (Customer-Care) in the objective of the market-clearing problem. While the novel non-linear terms in the objective complicate market clearing by making the problem non-convex, we show that a certain non-convex augmented Lagrangian relaxation can be approximated to any precision in time polynomial in the number of market participants using semi-definite programming. This makes it possible to implement the market-clearing mechanism efficiently. On the example of driver-ride assignment in an Uber-like system, we demonstrate the efficacy and scalability of the approach, and trade-offs between Inter- and Intra-fairness.


title: Dissipative search of an unstructured database

abstract: The search of an unstructured database amounts to finding one element having a certain property out of $N$ elements. The classical search with an oracle checking one element at a time requires on average $N/2$ steps. The Grover algorithm for the quantum search, and its unitary Hamiltonian evolution analogue, accomplish the search asymptotically optimally in $\mathcal{O} (\sqrt{N})$ time steps. We reformulate the search problem as a dissipative Markov process acting on an $N$-level system weakly coupled to a thermal bath. Assuming that the energy levels of the system represent the database elements, we show that, with a proper choice of the spectrum and physically admissible, long-range transition rates between the energy levels, the system relaxes to the ground state, corresponding to the sought element, in time $\mathcal{O} (\ln N)$.


title: Analogues of theorems of Chernoff and Ingham on the Heisenberg group

abstract: We prove an analogue of Chernoff's theorem for the Laplacian $ \Delta_{\mathbb{H}} $ on the Heisenberg group $ \mathbb{H}^n.$ As an application, we prove Ingham type theorems for the group Fourier transform on $ \mathbb{H}^n $ and also for the spectral projections associated to the sublaplacian.


title: Understanding and Improving Fairness-Accuracy Trade-offs in Multi-Task Learning

abstract: As multi-task models gain popularity in a wider range of machine learning applications, it is becoming increasingly important for practitioners to understand the fairness implications associated with those models. Most existing fairness literature focuses on learning a single task more fairly, while how ML fairness interacts with multiple tasks in the joint learning setting is largely under-explored. In this paper, we are concerned with how group fairness (e.g., equal opportunity, equalized odds) as an ML fairness concept plays out in the multi-task scenario. In multi-task learning, several tasks are learned jointly to exploit task correlations for a more efficient inductive transfer. This presents a multi-dimensional Pareto frontier on (1) the trade-off between group fairness and accuracy with respect to each task, as well as (2) the trade-offs across multiple tasks. We aim to provide a deeper understanding on how group fairness interacts with accuracy in multi-task learning, and we show that traditional approaches that mainly focus on optimizing the Pareto frontier of multi-task accuracy might not perform well on fairness goals. We propose a new set of metrics to better capture the multi-dimensional Pareto frontier of fairness-accuracy trade-offs uniquely presented in a multi-task learning setting. We further propose a Multi-Task-Aware Fairness (MTA-F) approach to improve fairness in multi-task learning. Experiments on several real-world datasets demonstrate the effectiveness of our proposed approach.


title: Higher Theories and Monads

abstract: We extend Bourke and Garner's idempotent adjunction between monads and pretheories to the framework of $\infty$-categories and we use this to prove many classical results about monads in the $\infty$-categorical framework. Amongst other things, we show that the category of algebras for an accessible monads on a locally presentable $\infty$-category $\mathcal{E}$ is again locally presentable, and that a diagram of accessible monads on a locally presentable $\infty$-category admits a colimit. Our results also provide a new and simpler way to construct and describe monads in terms of theories.


title: Location and audience selection for maximizing social influence

abstract: Viral marketing campaigns target primarily those individuals who are central in social networks and hence have social influence. Marketing events, however, may attract diverse audience. Despite the importance of event marketing, the influence of heterogeneous target groups is not well understood yet. In this paper, we define the Spreading Potential (SP) problem in which different sets of agents need to evaluated and compared based on their social influence. A typical application of SP is choosing locations for a series of marketing events. The SP problem is different from the well-known Influence Maximization (IM) problem in two aspects. Firstly, it deals with sets rather than nodes. Secondly, the sets are diverse, composed by a mixture of influential and ordinary agents. Thus, SP needs to assess the contribution of ordinary agents too, while IM only aims to find top spreaders. We provide a systemic test for ranking influence measures in the SP problem based on node sampling and on a novel statistical method, the Sum of Ranking Differences. Using a Linear Threshold diffusion model on an online social network, we evaluate seven network measures of social influence. We demonstrate that the statistical assessment of these influence measures is remarkably different in the SP problem, when low-ranked individuals are present, from the IM problem, when we focus on the algorithm's top choices exclusively.


title: On the Design of Strategic Task Recommendations for Sustainable Crowdsourcing-Based Content Moderation

abstract: Crowdsourcing-based content moderation is a platform that hosts content moderation tasks for crowd workers to review user submissions (e.g. text, images and videos) and make decisions regarding the admissibility of the posted content, along with a gamut of other tasks such as image labeling and speech-to-text conversion. In an attempt to reduce cognitive overload at the workers and improve system efficiency, these platforms offer personalized task recommendations according to the worker's preferences. However, the current state-of-the-art recommendation systems disregard the effects on worker's mental health, especially when they are repeatedly exposed to content moderation tasks with extreme content (e.g. violent images, hate-speech). In this paper, we propose a novel, strategic recommendation system for the crowdsourcing platform that recommends jobs based on worker's mental status. Specifically, this paper models interaction between the crowdsourcing platform's recommendation system (leader) and the worker (follower) as a Bayesian Stackelberg game where the type of the follower corresponds to the worker's cognitive atrophy rate and task preferences. We discuss how rewards and costs should be designed to steer the game towards desired outcomes in terms of maximizing the platform's productivity, while simultaneously improving the working conditions of crowd workers.


title: Domain Range Semigroups and Finite Representations

abstract: Relational semigroups with domain and range are a useful tool for modelling nondeterministic programs. We prove that the representation class of domain-range semigroups with demonic composition is not finitely axiomatisable. We extend the result for ordered domain algebras and show that any relation algebra reduct signature containing domain, range, converse, and composition, but no negation, meet, nor join has the finite representation property. That is any finite representable structure of such a signature is representable over a finite base. We survey the results in the area of the finite representation property.


title: A crossover from Kondo semiconductor to metallic antiferromagnet with $5d$-electron doping in CeFe$_2$Al$_{10}$

abstract: We report a systematic study of the $5d$-electron-doped system Ce(Fe$_{1-x}$Ir$_x$)$_2$Al$_{10}$ ($0 \leq x \leq 0.15$). With increasing $x$, the orthorhombic $b$~axis decreases slightly while accompanying changes in $a$ and $c$ leave the unit cell volume almost unchanged. Inelastic neutron scattering, along with thermal and transport measurements, reveal that for the Kondo semiconductor CeFe$_2$Al$_{10}$, the low-temperature energy gap which is proposed to be a consequence of strong $c \mhyphen f$ hybridization, is suppressed by a small amount of Ir substitution for Fe, and that the system adopts a metallic ground state with an increase in the density of states at the Fermi level. The charge or transport gap collapses (at $x=$~0.04) faster than the spin gap with Ir substitution. Magnetic susceptibility, heat capacity, and muon spin relaxation measurements demonstrate that the system undergoes long-range antiferromagnetic order below a N\'eel temperature, $T_{\mathrm{N}}$, of 3.1(2)~K for $x = 0.15$. The ordered moment is estimated to be smaller than 0.07(1)~$\mu_\mathrm{B}$/Ce although the trivalent state of Ce is confirmed by Ce L$_3$-edge x-ray absorption near edge spectroscopy. It is suggested that the $c \mhyphen f$ hybridization gap, which plays an important role in the unusually high ordering temperatures observed in Ce$T_2$Al$_{10}$ ($T$ = Ru and Os), may not be necessary for the onset of magnetic order with a low $T_{\mathrm{N}}$ seen here in Ce(Fe$_{1-x}$Ir$_x$)$_2$Al$_{10}$.


title: SketchGen: Generating Constrained CAD Sketches

abstract: Computer-aided design (CAD) is the most widely used modeling approach for technical design. The typical starting point in these designs is 2D sketches which can later be extruded and combined to obtain complex three-dimensional assemblies. Such sketches are typically composed of parametric primitives, such as points, lines, and circular arcs, augmented with geometric constraints linking the primitives, such as coincidence, parallelism, or orthogonality. Sketches can be represented as graphs, with the primitives as nodes and the constraints as edges. Training a model to automatically generate CAD sketches can enable several novel workflows, but is challenging due to the complexity of the graphs and the heterogeneity of the primitives and constraints. In particular, each type of primitive and constraint may require a record of different size and parameter types. We propose SketchGen as a generative model based on a transformer architecture to address the heterogeneity problem by carefully designing a sequential language for the primitives and constraints that allows distinguishing between different primitive or constraint types and their parameters, while encouraging our model to re-use information across related parameters, encoding shared structure. A particular highlight of our work is the ability to produce primitives linked via constraints that enables the final output to be further regularized via a constraint solver. We evaluate our model by demonstrating constraint prediction for given sets of primitives and full sketch generation from scratch, showing that our approach significantly out performs the state-of-the-art in CAD sketch generation.


title: Exactly solvable model behind Bose-Hubbard dimers, Ince-Gauss beams, and aberrated optical cavities

abstract: By studying the effects of quadratic anisotropy and quartic perturbations on the two-dimensional harmonic oscillator, one arrives at a simple model termed here the Ince oscillator, whose analytic solutions are given in terms of Ince polynomials. This one model unifies diverse physical systems, including aberrated optical cavities that are shown to support Ince-Gauss beams as their modes, and the two-mode Bose-Hubbard dimer describing two coupled superfluids. The Ince oscillator model describes a topological transition which can have very different origins: in the optical case, which is fundamentally linear, it is driven by the ratio of astigmatic to spherical mirror aberrations, whereas in the superfluid case it is driven by the ratio of particle tunneling to interparticle interactions and corresponds to macroscopic quantum self trapping.


title: Learning Curves for SGD on Structured Features

abstract: The generalization performance of a machine learning algorithm such as a neural network depends in a non-trivial way on the structure of the data distribution. To analyze the influence of data structure on test loss dynamics, we study an exactly solveable model of stochastic gradient descent (SGD) on mean square loss which predicts test loss when training on features with arbitrary covariance structure. We solve the theory exactly for both Gaussian features and arbitrary features and we show that the simpler Gaussian model accurately predicts test loss of nonlinear random-feature models and deep neural networks trained with SGD on real datasets such as MNIST and CIFAR-10. We show that the optimal batch size at a fixed compute budget is typically small and depends on the feature correlation structure, demonstrating the computational benefits of SGD with small batch sizes. Lastly, we extend our theory to the more usual setting of stochastic gradient descent on a fixed subsampled training set, showing that both training and test error can be accurately predicted in our framework on real data.


title: Point Cloud Failure Criterion for Composites using k-Nearest Neighbor Classification

abstract: Numerous theories of failure have been postulated and implemented in various commercial programs for composite materials. Even the best theories have had limited success in predicting damage and failure in validation exercises. In view of this background, many researchers have started exploring the use of multiscale modeling to improve the fidelity of the modeling and simulation of various structural and materials systems. In this paper, a multi-scale modeling scheme is used to illustrate how a combination of virtual and laboratory testing programs can be used to generate a point cloud of failure surface data that can then be queried during finite element analysis at the continuum scale to ascertain if the onset of failure has occurred. The k-nearest neighbor (k-NN) classification concept is used to obtain the answer to the query. A linear, elastic, static finite element example using a unidirectional composite shows that the framework can be generated and used effectively and efficiently with the possibility to extend the approach for all types of composite architectures and behaviors.


title: Auditing Source Diversity Bias in Video Search Results Using Virtual Agents

abstract: We audit the presence of domain-level source diversity bias in video search results. Using a virtual agent-based approach, we compare outputs of four Western and one non-Western search engines for English and Russian queries. Our findings highlight that source diversity varies substantially depending on the language with English queries returning more diverse outputs. We also find disproportionately high presence of a single platform, YouTube, in top search outputs for all Western search engines except Google. At the same time, we observe that Youtube's major competitors such as Vimeo or Dailymotion do not appear in the sampled Google's video search results. This finding suggests that Google might be downgrading the results from the main competitors of Google-owned Youtube and highlights the necessity for further studies focusing on the presence of own-content bias in Google's search results.


title: VEER: Enhancing the Interpretability of Model-based Optimizations

abstract: Many software systems can be tuned for multiple objectives (e.g., faster runtime, less required memory, less network traffic or energy consumption, etc.). Optimizers built for different objectives suffer from "model disagreement"; i.e., they have different (or even opposite) insights and tactics on how to optimize a system. Model disagreement is rampant (at least for configuration problems). Yet prior to this paper, it has barely been explored. This paper shows that model disagreement can be mitigated via VEER, a one-dimensional approximation to the N-objective space. Since it is exploring a simpler goal space, VEER runs very fast (for eleven configuration problems). Even for our largest problem (with tens of thousands of possible configurations), VEER finds as good or better optimizations with zero model disagreements, three orders of magnitude faster (since its one-dimensional output no longer needs the sorting procedure). Based on the above, we recommend VEER as a very fast method to solve complex configuration problems, while at the same time avoiding model disagreement.


title: Dispersive estimates for linearized water wave type equations in $\mathbb R^d$

abstract: We derive a $L^1_x (\mathbb R^d)-L^{\infty}_x ( \mathbb R^d)$ decay estimate of order $\mathcal O \left( t^{-d/2}\right)$ for the linear propagators $$\exp \left( {\pm it \sqrt{ |D|\left(1+ \beta |D|^2\right) \tanh |D | } }\right), \qquad \beta \in \{0, 1\}. \quad D = -i\nabla,$$ with a loss of $3d/4$ or $d/4$-derivatives in the case $\beta=0$ or $\beta=1$, respectively. These linear propagators are known to be associated with the linearized water wave equations, where the parameter $\beta$ measures surface tension effects. As an application we prove low regularity well-posedness for a Whitham-Boussinesq type system in $\mathbb R^d$, $d\ge 2$. This generalizes a recent result by Dinvay, Selberg and the third author where they proved low regularity well-posedness in $\mathbb R$ and $\mathbb R^2$.


title: Simultaneous Confidence Corridors for Mean Functions in Functional Data Analysis of Imaging Data

abstract: Motivated by recent work involving the analysis of biomedical imaging data, we present a novel procedure for constructing simultaneous confidence corridors for the mean of imaging data. We propose to use flexible bivariate splines over triangulations to handle irregular domain of the images that is common in brain imaging studies and in other biomedical imaging applications. The proposed spline estimators of the mean functions are shown to be consistent and asymptotically normal under some regularity conditions. We also provide a computationally efficient estimator of the covariance function and derive its uniform consistency. The procedure is also extended to the two-sample case in which we focus on comparing the mean functions from two populations of imaging data. Through Monte Carlo simulation studies we examine the finite-sample performance of the proposed method. Finally, the proposed method is applied to analyze brain Positron Emission Tomography (PET) data in two different studies. One dataset used in preparation of this article was obtained from the Alzheimer's Disease Neuroimaging Initiative (ADNI) database.


title: Hierarchical Video Generation for Complex Data

abstract: Videos can often be created by first outlining a global description of the scene and then adding local details. Inspired by this we propose a hierarchical model for video generation which follows a coarse to fine approach. First our model generates a low resolution video, establishing the global scene structure, that is then refined by subsequent levels in the hierarchy. We train each level in our hierarchy sequentially on partial views of the videos. This reduces the computational complexity of our generative model, which scales to high-resolution videos beyond a few frames. We validate our approach on Kinetics-600 and BDD100K, for which we train a three level model capable of generating 256x256 videos with 48 frames.


title: An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning

abstract: We present and analyze an algorithm for optimizing smooth and convex or strongly convex objectives using minibatch stochastic gradient estimates. The algorithm is optimal with respect to its dependence on both the minibatch size and minimum expected loss simultaneously. This improves over the optimal method of Lan (2012), which is insensitive to the minimum expected loss; over the optimistic acceleration of Cotter et al. (2011), which has suboptimal dependence on the minibatch size; and over the algorithm of Liu and Belkin (2018), which is limited to least squares problems and is also similarly suboptimal with respect to the minibatch size. Applied to interpolation learning, the improvement over Cotter et al. and Liu and Belkin translates to a linear, rather than square-root, parallelization speedup.


title: Reflections in excitable media linked to existence and stability of one-dimensional spiral waves

abstract: When propagated action potentials in cardiac tissue interact with local heterogeneities, reflected waves can sometimes be induced. These reflected waves have been associated with the onset of cardiac arrhythmias, and while their generation is not well understood, their existence is linked to that of one-dimensional (1D) spiral waves. Thus, understanding the existence and stability of 1D spirals plays a crucial role in determining the likelihood of the unwanted reflected pulses. Mathematically, we probe these issues by viewing the 1D spiral as a time-periodic antisymmetric source defect. Through a combination of direct numerical simulation and continuation methods, we investigate existence and stability of a 1D spiral wave in a qualitative ionic model to determine how the systems propensity for reflections are influenced by system parameters. Our results support and extend a previous hypothesis that the 1D spiral is an unstable periodic orbit that emerges through a global rearrangement of heteroclinic orbits and we identify key parameters and physiological processes that promote and deter reflection behavior.


title: Wigner analysis of operators. Part I: pseudodifferential operators and wave fronts

abstract: We perform Wigner analysis of linear operators. Namely, the standard time-frequency representation \emph{Short-time Fourier Transform} (STFT) is replaced by the $\mathcal{A}$-\emph{Wigner distribution} defined by $W_{\mathcal A} (f)=\mu({\mathcal A})(f\otimes\bar{f})$, where ${\mathcal A}$ is a $4d\times 4d$ symplectic matrix and $\mu({\mathcal A})$ is an associate metaplectic operator. Basic examples are given by the so-called $\tau$-Wigner distributions. Such representations provide a new characterization for modulation spaces when $\tau\in (0,1)$. Furthermore, they can be efficiently employed in the study of the off-diagonal decay for pseudodifferential operators with symbols in the Sj\"ostrand class (in particular, in the H\"{o}rmander class $S^0_{0,0}$). The novelty relies on defining time-frequency representations via metaplectic operators, developing a conceptual framework and paving the way for a new understanding of quantization procedures. We deduce micro-local properties for pseudodifferential operators in terms of the Wigner wave front set. Finally, we compare the Wigner with the global H\"{o}rmander wave front set and identify the possible presence of a ghost region in the Wigner wave front. \par In the second part of the paper applications to Fourier integral operators and Schr\"{o}dinger equations will be given.


title: A determination of the blowup solutions to the focusing NLS with mass equal to the mass of the soliton

abstract: In this paper we prove rigidity for blowup solutions to the focusing, mass-critical nonlinear Schr{\"o}dinger equation in dimensions $2 \leq d \leq 15$ with mass equal to the mass of the soliton. We prove that the only such solutions are the solitons and the pseudoconformal transformation of the solitons.


title: Statistical summaries of unlabelled evolutionary trees and ranked hierarchical clustering trees

abstract: Rooted and ranked binary trees are mathematical objects of great importance used to model hierarchical data and evolutionary relationships with applications in many fields including evolutionary biology and genetic epidemiology. Bayesian phylogenetic inference usually explore the posterior distribution of trees via Markov Chain Monte Carlo methods, however assessing uncertainty and summarizing distributions or samples of such trees remains challenging. While labelled phylogenetic trees have been extensively studied, relatively less literature exists for unlabelled trees which are increasingly useful, for example when one seeks to summarize samples of trees obtained with different methods, or from different samples and environments, and wishes to assess stability and generalizability of these summaries. In our paper, we exploit recently proposed distance metrics of unlabelled ranked binary trees and unlabelled ranked genealogies (equipped with branch lengths) to define the Frechet mean and variance as summaries of these tree distributions. We provide an efficient combinatorial optimization algorithm for computing the Frechet mean from a sample of or distribution on unlabelled ranked tree shapes and unlabelled ranked genealogies. We show the applicability of our summary statistics for studying popular tree distributions and for comparing the SARS-CoV-2 evolutionary trees across different locations during the COVID-19 epidemic in 2020.


title: MultiOpEd: A Corpus of Multi-Perspective News Editorials

abstract: We propose MultiOpEd, an open-domain news editorial corpus that supports various tasks pertaining to the argumentation structure in news editorials, focusing on automatic perspective discovery. News editorial is a genre of persuasive text, where the argumentation structure is usually implicit. However, the arguments presented in an editorial typically center around a concise, focused thesis, which we refer to as their perspective. MultiOpEd aims at supporting the study of multiple tasks relevant to automatic perspective discovery, where a system is expected to produce a single-sentence thesis statement summarizing the arguments presented. We argue that identifying and abstracting such natural language perspectives from editorials is a crucial step toward studying the implicit argumentation structure in news editorials. We first discuss the challenges and define a few conceptual tasks towards our goal. To demonstrate the utility of MultiOpEd and the induced tasks, we study the problem of perspective summarization in a multi-task learning setting, as a case study. We show that, with the induced tasks as auxiliary tasks, we can improve the quality of the perspective summary generated. We hope that MultiOpEd will be a useful resource for future studies on argumentation in the news editorial domain.


title: Popular individuals process the world in particularly normative ways

abstract: People differ in how they attend to, interpret, and respond to their surroundings. Convergent processing of the world may be one factor that contributes to social connections between individuals. We used neuroimaging and network analysis to investigate whether the most central individuals in their communities (as measured by in-degree centrality, a notion of popularity) process the world in a particularly normative way. We found that more central individuals had exceptionally similar neural responses to their peers and especially to each other in brain regions that are associated with high-level interpretations and social cognition (e.g., in the default-mode network), whereas less-central individuals exhibited more idiosyncratic responses. Self-reported enjoyment of and interest in stimuli followed a similar pattern, but accounting for these data did not change our main results. These findings suggest that highly-central individuals process the world in exceptionally similar ways, whereas less-central individuals process the world in idiosyncratic ways.


title: Confidence bands for exponential distribution functions under progressive type-II censoring

abstract: Based on a progressively type-II censored sample from the exponential distribution with unknown location and scale parameter, confidence bands are proposed for the underlying distribution function by using confidence regions for the parameters and Kolmogorov-Smirnov type statistics. Simple explicit representations for the boundaries and for the coverage probabilities of the confidence bands are analytically derived, and the performance of the bands is compared in terms of band width and area by means of a data example. As a by-product, a novel confidence region for the location-scale parameter is obtained. Extensions of the results to related models for ordered data, such as sequential order statistics, as well as to other underlying location-scale families of distributions are discussed.


title: Model-free Data-Driven Inference

abstract: We present a model-free data-driven inference method that enables inferences on system outcomes to be derived directly from empirical data without the need for intervening modeling of any type, be it modeling of a material law or modeling of a prior distribution of material states. We specifically consider physical systems with states characterized by points in a phase space determined by the governing field equations. We assume that the system is characterized by two likelihood measures: one $\mu_D$ measuring the likelihood of observing a material state in phase space; and another $\mu_E$ measuring the likelihood of states satisfying the field equations, possibly under random actuation. We introduce a notion of intersection between measures which can be interpreted to quantify the likelihood of system outcomes. We provide conditions under which the intersection can be characterized as the athermal limit $\mu_\infty$ of entropic regularizations $\mu_\beta$, or thermalizations, of the product measure $\mu = \mu_D\times \mu_E$ as $\beta \to +\infty$. We also supply conditions under which $\mu_\infty$ can be obtained as the athermal limit of carefully thermalized $(\mu_{h,\beta_h})$ sequences of empirical data sets $(\mu_h)$ approximating weakly an unknown likelihood function $\mu$. In particular, we find that the cooling sequence $\beta_h \to +\infty$ must be slow enough, corresponding to quenching, in order for the proper limit $\mu_\infty$ to be delivered. Finally, we derive explicit analytic expressions for expectations $\mathbb{E}[f]$ of outcomes $f$ that are explicit in the data, thus demonstrating the feasibility of the model-free data-driven paradigm as regards making convergent inferences directly from the data without recourse to intermediate modeling steps.


title: Optical read-out of the N\'eel vector in metallic antiferromagnet Mn$_{2}$Au

abstract: Metallic antiferromagnets with broken inversion symmetry on the two sublattices, strong spin-orbit coupling and high N\'{e}el temperatures offer new opportunities for applications in spintronics. Especially Mn$_{2}$Au, with high N\'{e}el temperature and conductivity, is particularly interesting for real-world applications. Here, manipulation of the orientation of the staggered magnetization,\textit{\ i.e.} the N\'{e}el vector, by current pulses has been recently demonstrated, with the read-out limited to studies of anisotropic magnetoresistance or X-ray magnetic linear dichroism. Here, we report on the in-plane reflectivity anisotropy of Mn$_{2}$Au (001) films, which were N\'{e}el vector aligned in pulsed magnetic fields. In the near-infrared, the anisotropy is $\approx$ 0.6\%, with higher reflectivity for the light polarized along the N\'{e}el vector. The observed magnetic linear dichroism is about four times larger than the anisotropic magnetoresistance. This suggests the dichroism in Mn$_{2}$Au is a result of the strong spin-orbit interactions giving rise to anisotropy of interband optical transitions, in-line with recent studies of electronic band-structure. The considerable magnetic linear dichroism in the near-infrared could be used for ultrafast optical read-out of the N\'{e}el vector in Mn$_{2}$Au.


title: "Spectrally gapped" random walks on networks: a Mean First Passage Time formula

abstract: We derive an approximate but explicit formula for the Mean First Passage Time of a random walker between a source and a target node of a directed and weighted network. The formula does not require any matrix inversion, and it takes as only input the transition probabilities into the target node. It is derived from the calculation of the average resolvent of a deformed ensemble of random sub-stochastic matrices $H=\langle H\rangle +\delta H$, with $\langle H\rangle$ rank-$1$ and non-negative. The accuracy of the formula depends on the spectral gap of the reduced transition matrix, and it is tested numerically on several instances of (weighted) networks away from the high sparsity regime, with an excellent agreement.


title: Man-in-the-Middle Attack Resistant Secret Key Generation via Channel Randomization

abstract: Physical-layer based key generation schemes exploit the channel reciprocity for secret key extraction, which can achieve information-theoretic secrecy against eavesdroppers. Such methods, although practical, have been shown to be vulnerable against man-in-the-middle (MitM) attacks, where an active adversary, Mallory, can influence and infer part of the secret key generated between Alice and Bob by injecting her own packet upon observing highly correlated channel/RSS measurements from Alice and Bob. As all the channels remain stable within the channel coherence time, Mallory's injected packets cause Alice and Bob to measure similar RSS, which allows Mallory to successfully predict the derived key bits. To defend against such a MitM attack, we propose to utilize a reconfigurable antenna at one of the legitimate transceivers to proactively randomize the channel state across different channel probing rounds. The randomization of the antenna mode at every probing round breaks the temporal correlation of the channels from the adversary to the legitimate devices, while preserving the reciprocity of the channel between the latter. This prevents key injection from the adversary without affecting Alice and Bob's ability to measure common randomness. We theoretically analyze the security of the protocol and conduct extensive simulations and real-world experiments to evaluate its performance. Our results show that our approach eliminates the advantage of an active MitM attack by driving down the probability of successfully guessing bits of the secret key to a random guess.


title: BO-DBA: Query-Efficient Decision-Based Adversarial Attacks via Bayesian Optimization

abstract: Decision-based attacks (DBA), wherein attackers perturb inputs to spoof learning algorithms by observing solely the output labels, are a type of severe adversarial attacks against Deep Neural Networks (DNNs) requiring minimal knowledge of attackers. State-of-the-art DBA attacks relying on zeroth-order gradient estimation require an excessive number of queries. Recently, Bayesian optimization (BO) has shown promising in reducing the number of queries in score-based attacks (SBA), in which attackers need to observe real-valued probability scores as outputs. However, extending BO to the setting of DBA is nontrivial because in DBA only output labels instead of real-valued scores, as needed by BO, are available to attackers. In this paper, we close this gap by proposing an efficient DBA attack, namely BO-DBA. Different from existing approaches, BO-DBA generates adversarial examples by searching so-called \emph{directions of perturbations}. It then formulates the problem as a BO problem that minimizes the real-valued distortion of perturbations. With the optimized perturbation generation process, BO-DBA converges much faster than the state-of-the-art DBA techniques. Experimental results on pre-trained ImageNet classifiers show that BO-DBA converges within 200 queries while the state-of-the-art DBA techniques need over 15,000 queries to achieve the same level of perturbation distortion. BO-DBA also shows similar attack success rates even as compared to BO-based SBA attacks but with less distortion.


title: DISCO: accurate Discrete Scale Convolutions

abstract: Scale is often seen as a given, disturbing factor in many vision tasks. When doing so it is one of the factors why we need more data during learning. In recent work scale equivariance was added to convolutional neural networks. It was shown to be effective for a range of tasks. We aim for accurate scale-equivariant convolutional neural networks (SE-CNNs) applicable for problems where high granularity of scale and small kernel sizes are required. Current SE-CNNs rely on weight sharing and kernel rescaling, the latter of which is accurate for integer scales only. To reach accurate scale equivariance, we derive general constraints under which scale-convolution remains equivariant to discrete rescaling. We find the exact solution for all cases where it exists, and compute the approximation for the rest. The discrete scale-convolution pays off, as demonstrated in a new state-of-the-art classification on MNIST-scale and on STL-10 in the supervised learning setting. With the same SE scheme, we also improve the computational effort of a scale-equivariant Siamese tracker on OTB-13.


title: Revisiting Hilbert-Schmidt Information Bottleneck for Adversarial Robustness

abstract: We investigate the HSIC (Hilbert-Schmidt independence criterion) bottleneck as a regularizer for learning an adversarially robust deep neural network classifier. In addition to the usual cross-entropy loss, we add regularization terms for every intermediate layer to ensure that the latent representations retain useful information for output prediction while reducing redundant information. We show that the HSIC bottleneck enhances robustness to adversarial attacks both theoretically and experimentally. In particular, we prove that the HSIC bottleneck regularizer reduces the sensitivity of the classifier to adversarial examples. Our experiments on multiple benchmark datasets and architectures demonstrate that incorporating an HSIC bottleneck regularizer attains competitive natural accuracy and improves adversarial robustness, both with and without adversarial examples during training. Our code and adversarially robust models are publicly available.


title: Learning particle swarming models from data with Gaussian processes

abstract: Interacting particle or agent systems that display a rich variety of swarming behaviours are ubiquitous in science and engineering. A fundamental and challenging goal is to understand the link between individual interaction rules and swarming. In this paper, we study the data-driven discovery of a second-order particle swarming model that describes the evolution of $N$ particles in $\mathbb{R}^d$ under radial interactions. We propose a learning approach that models the latent radial interaction function as Gaussian processes, which can simultaneously fulfill two inference goals: one is the nonparametric inference of {the} interaction function with pointwise uncertainty quantification, and the other one is the inference of unknown scalar parameters in the non-collective friction forces of the system. We formulate the learning problem as a statistical inverse problem and provide a detailed analysis of recoverability conditions, establishing that a coercivity condition is sufficient for recoverability. Given data collected from $M$ i.i.d trajectories with independent Gaussian observational noise, we provide a finite-sample analysis, showing that our posterior mean estimator converges in a Reproducing kernel Hilbert space norm, at an optimal rate in $M$ equal to the one in the classical 1-dimensional Kernel Ridge regression. As a byproduct, we show we can obtain a parametric learning rate in $M$ for the posterior marginal variance using $L^{\infty}$ norm, and the rate could also involve $N$ and $L$ (the number of observation time instances for each trajectory), depending on the condition number of the inverse problem. Numerical results on systems that exhibit different swarming behaviors demonstrate efficient learning of our approach from scarce noisy trajectory data.

categories: stat.ML cs.LG cs.NA math.NA math.ST stat.TH


title: Exposing the Implicit Energy Networks behind Masked Language Models via Metropolis--Hastings

abstract: While recent work has shown that scores from models trained by the ubiquitous masked language modeling (MLM) objective effectively discriminate probable from improbable sequences, it is still an open question if these MLMs specify a principled probability distribution over the space of possible sequences. In this paper, we interpret MLMs as energy-based sequence models and propose two energy parametrizations derivable from the trained MLMs. In order to draw samples correctly from these models, we develop a tractable sampling scheme based on the Metropolis--Hastings Monte Carlo algorithm. In our approach, samples are proposed from the same masked conditionals used for training the masked language models, and they are accepted or rejected based on their energy values according to the target distribution. We validate the effectiveness of the proposed parametrizations by exploring the quality of samples drawn from these energy-based models for both open-ended unconditional generation and a conditional generation task of machine translation. We theoretically and empirically justify our sampling algorithm by showing that the masked conditionals on their own do not yield a Markov chain whose stationary distribution is that of our target distribution, and our approach generates higher quality samples than other recently proposed undirected generation approaches (Wang et al., 2019, Ghazvininejad et al., 2019).


title: Negotiation-Aware Reachability-Based Safety Verification for AutonomousDriving in Interactive Scenarios

abstract: Safety assurance is a critical yet challenging aspect when developing self-driving technologies. Hamilton-Jacobi backward-reachability analysis is a formal verification tool for verifying the safety of dynamic systems in the presence of disturbances. However, the standard approach is too conservative to be applied to self-driving applications due to its worst-case assumption on humans' behaviors (i.e., guard against worst-case outcomes). In this work, we integrate a learning-based prediction algorithm and a game-theoretic human behavioral model to online update the conservativeness of backward-reachability analysis. We evaluate our approach using real driving data. The results show that, with reasonable assumptions on human behaviors, our approach can effectively reduce the conservativeness of the standard approach without sacrificing its safety verification ability.


title: Encoder-Decoder Neural Architecture Optimization for Keyword Spotting

abstract: Keyword spotting aims to identify specific keyword audio utterances. In recent years, deep convolutional neural networks have been widely utilized in keyword spotting systems. However, their model architectures are mainly based on off-the shelfbackbones such as VGG-Net or ResNet, instead of specially designed for the task. In this paper, we utilize neural architecture search to design convolutional neural network models that can boost the performance of keyword spotting while maintaining an acceptable memory footprint. Specifically, we search the model operators and their connections in a specific search space with Encoder-Decoder neural architecture optimization. Extensive evaluations on Google's Speech Commands Dataset show that the model architecture searched by our approach achieves a state-of-the-art accuracy of over 97%.


title: Measurement of the muon flux in the bunker of Monte Soratte with the CRC detector

abstract: In the context of the PTOLEMY project, the need for a site with a rather low cosmogenic induced background led us to measure the differential muon flux inside the bunker of Monte Soratte, located about 50~km north of Rome (Italy). The measurement was performed with the Cosmic Ray Cube (CRC), a portable tracking device. The simple operation of the Cosmic Ray Cube was crucial to finalise the measurements, as they were carried out during the COVID-19 lockdown and in a site devoid of scientific equipment. The muon flux measured at the Soratte hypogeum is above two orders of magnitude lower than the flux observed on the surface, suggesting the possible use of the Mt. Soratte bunker for hosting astroparticle physics experiments requiring a low environmental background.


title: ZeroWaste Dataset: Towards Deformable Object Segmentation in Cluttered Scenes

abstract: Less than 35% of recyclable waste is being actually recycled in the US, which leads to increased soil and sea pollution and is one of the major concerns of environmental researchers as well as the common public. At the heart of the problem are the inefficiencies of the waste sorting process (separating paper, plastic, metal, glass, etc.) due to the extremely complex and cluttered nature of the waste stream. Recyclable waste detection poses a unique computer vision challenge as it requires detection of highly deformable and often translucent objects in cluttered scenes without the kind of context information usually present in human-centric datasets. This challenging computer vision task currently lacks suitable datasets or methods in the available literature. In this paper, we take a step towards computer-aided waste detection and present the first in-the-wild industrial-grade waste detection and segmentation dataset, ZeroWaste. We believe that ZeroWaste will catalyze research in object detection and semantic segmentation in extreme clutter as well as applications in the recycling domain. Our project page can be found at http://ai.bu.edu/zerowaste/.


title: Semiparametric inference on Gini indices of two semicontinuous populations under density ratio models

abstract: The Gini index is a popular inequality measure with many applications in social and economic studies. This paper studies semiparametric inference on the Gini indices of two semicontinuous populations. We characterize the distribution of each semicontinuous population by a mixture of a discrete point mass at zero and a continuous skewed positive component. A semiparametric density ratio model is then employed to link the positive components of the two distributions. We propose the maximum empirical likelihood estimators of the two Gini indices and their difference, and further investigate the asymptotic properties of the proposed estimators. The asymptotic results enable us to construct confidence intervals and perform hypothesis tests for the two Gini indices and their difference. We show that the proposed estimators are more efficient than the existing fully nonparametric estimators. The proposed estimators and the asymptotic results are also applicable to cases without excessive zero values. Simulation studies show the superiority of our proposed method over existing methods. Two real-data applications are presented using the proposed methods.


title: Latent Time-Adaptive Drift-Diffusion Model

abstract: Animals can quickly learn the timing of events with fixed intervals and their rate of acquisition does not depend on the length of the interval. In contrast, recurrent neural networks that use gradient based learning have difficulty predicting the timing of events that depend on stimulus that occurred long ago. We present the latent time-adaptive drift-diffusion model (LTDDM), an extension to the time-adaptive drift-diffusion model (TDDM), a model for animal learning of timing that exhibits behavioural properties consistent with experimental data from animals. The performance of LTDDM is compared to that of a state of the art long short-term memory (LSTM) recurrent neural network across three timing tasks. Differences in the relative performance of these two models is discussed and it is shown how LTDDM can learn these events time series orders of magnitude faster than recurrent neural networks.


title: SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networks

abstract: Graph Neural Networks (GNNs) are the first choice methods for graph machine learning problems thanks to their ability to learn state-of-the-art level representations from graph-structured data. However, centralizing a massive amount of real-world graph data for GNN training is prohibitive due to user-side privacy concerns, regulation restrictions, and commercial competition. Federated Learning is the de-facto standard for collaborative training of machine learning models over many distributed edge devices without the need for centralization. Nevertheless, training graph neural networks in a federated setting is vaguely defined and brings statistical and systems challenges. This work proposes SpreadGNN, a novel multi-task federated training framework capable of operating in the presence of partial labels and absence of a central server for the first time in the literature. SpreadGNN extends federated multi-task learning to realistic serverless settings for GNNs, and utilizes a novel optimization algorithm with a convergence guarantee, Decentralized Periodic Averaging SGD (DPA-SGD), to solve decentralized multi-task learning problems. We empirically demonstrate the efficacy of our framework on a variety of non-I.I.D. distributed graph-level molecular property prediction datasets with partial labels. Our results show that SpreadGNN outperforms GNN models trained over a central server-dependent federated learning system, even in constrained topologies. The source code is publicly available at https://github.com/FedML-AI/SpreadGNN


title: 3-D Stochastic Numerical Breast Phantoms for Enabling Virtual Imaging Trials of Ultrasound Computed Tomography

abstract: Ultrasound computed tomography (USCT) is an emerging imaging modality for breast imaging that can produce quantitative images that depict the acoustic properties of tissues. Computer-simulation studies, also known as virtual imaging trials, provide researchers with an economical and convenient route to systematically explore imaging system designs and image reconstruction methods. When simulating an imaging technology intended for clinical use, it is essential to employ realistic numerical phantoms that can facilitate the objective, or task-based, assessment of image quality. Moreover, when computing objective image quality measures, an ensemble of such phantoms should be employed that display the variability in anatomy and object properties that is representative of the to-be-imaged patient cohort. Such stochastic phantoms for clinically relevant applications of USCT are currently lacking. In this work, a methodology for producing realistic three-dimensional (3D) numerical breast phantoms for enabling clinically relevant computer-simulation studies of USCT breast imaging is presented. By extending and adapting an existing stochastic 3D breast phantom for use withUSCT, methods for creating ensembles of numerical acoustic breast phantoms are established. These breast phantoms will possess clinically relevant variations in breast size, composition, acoustic properties, tumor locations, and tissue textures. To demonstrate the use of the phantoms in virtual USCT studies, two brief case studies are presented that address the development and assessment of image reconstruction procedures. Examples of breast phantoms produced by use of the proposed methods and a collection of 52 sets of simulated USCT measurement data have been made open source for use in image reconstruction development


title: Neural Auto-Curricula

abstract: When solving two-player zero-sum games, multi-agent reinforcement learning (MARL) algorithms often create populations of agents where, at each iteration, a new agent is discovered as the best response to a mixture over the opponent population. Within such a process, the update rules of "who to compete with" (i.e., the opponent mixture) and "how to beat them" (i.e., finding best responses) are underpinned by manually developed game theoretical principles such as fictitious play and Double Oracle. In this paper, we introduce a novel framework -- Neural Auto-Curricula (NAC) -- that leverages meta-gradient descent to automate the discovery of the learning update rule without explicit human design. Specifically, we parameterise the opponent selection module by neural networks and the best-response module by optimisation subroutines, and update their parameters solely via interaction with the game engine, where both players aim to minimise their exploitability. Surprisingly, even without human design, the discovered MARL algorithms achieve competitive or even better performance with the state-of-the-art population-based game solvers (e.g., PSRO) on Games of Skill, differentiable Lotto, non-transitive Mixture Games, Iterated Matching Pennies, and Kuhn Poker. Additionally, we show that NAC is able to generalise from small games to large games, for example training on Kuhn Poker and outperforming PSRO on Leduc Poker. Our work inspires a promising future direction to discover general MARL algorithms solely from data.


title: Logarithmic heat kernels estimates without curvature restrictions

abstract: The main results of the article are short time estimates and asymptotic estimates for the first two order derivatives of the logarithmic heat kernel of a complete Riemannian manifold. We remove all curvature restrictions and also develop several techniques. A basic tool developed here is intrinsic stochastic variations with prescribed second order covariant differentials, allowing to obtain a path integration representation for the second order derivatives of the heat semigroup $P_t$ on a complete Riemannian manifold, again without any assumptions on the curvature. The novelty is the introduction of an $\epsilon^2$ term in the variation allowing greater control. We also construct a family of cut-off stochastic processes adapted to an exhaustion by compact subsets with smooth boundaries, each process is constructed path by path and differentiable in time, furthermore the differentials have locally uniformly bounded moments with respect to the Brownian motion measures, allowing to by-pass the lack of continuity of the exit time of the Brownian motions on its initial position.


title: Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

abstract: We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes Stehl\'e-Steinfield-Tanaka-Xagawa' re-interpretation of Regev's quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is always unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and cannot be used, as such, for the reduction with codes. This problem was solved by using instead a truncated Bernoulli distribution.


title: Decentralized Q-Learning in Zero-sum Markov Games

abstract: We study multi-agent reinforcement learning (MARL) in infinite-horizon discounted zero-sum Markov games. We focus on the practical but challenging setting of decentralized MARL, where agents make decisions without coordination by a centralized controller, but only based on their own payoffs and local actions executed. The agents need not observe the opponent's actions or payoffs, possibly being even oblivious to the presence of the opponent, nor be aware of the zero-sum structure of the underlying game, a setting also referred to as radically uncoupled in the literature of learning in games. In this paper, we develop a radically uncoupled Q-learning dynamics that is both rational and convergent: the learning dynamics converges to the best response to the opponent's strategy when the opponent follows an asymptotically stationary strategy; when both agents adopt the learning dynamics, they converge to the Nash equilibrium of the game. The key challenge in this decentralized setting is the non-stationarity of the environment from an agent's perspective, since both her own payoffs and the system evolution depend on the actions of other agents, and each agent adapts her policies simultaneously and independently. To address this issue, we develop a two-timescale learning dynamics where each agent updates her local Q-function and value function estimates concurrently, with the latter happening at a slower timescale.


title: Predify: Augmenting deep neural networks with brain-inspired predictive coding dynamics

abstract: Deep neural networks excel at image classification, but their performance is far less robust to input perturbations than human perception. In this work we explore whether this shortcoming may be partly addressed by incorporating brain-inspired recurrent dynamics in deep convolutional networks. We take inspiration from a popular framework in neuroscience: 'predictive coding'. At each layer of the hierarchical model, generative feedback 'predicts' (i.e., reconstructs) the pattern of activity in the previous layer. The reconstruction errors are used to iteratively update the network's representations across timesteps, and to optimize the network's feedback weights over the natural image dataset-a form of unsupervised training. We show that implementing this strategy into two popular networks, VGG16 and EfficientNetB0, improves their robustness against various corruptions and adversarial attacks. We hypothesize that other feedforward networks could similarly benefit from the proposed framework. To promote research in this direction, we provide an open-sourced PyTorch-based package called Predify, which can be used to implement and investigate the impacts of the predictive coding dynamics in any convolutional neural network.


title: Do You Listen with One or Two Microphones? A Unified ASR Model for Single and Multi-Channel Audio

abstract: Automatic speech recognition (ASR) models are typically designed to operate on a single input data type, e.g. a single or multi-channel audio streamed from a device. This design decision assumes the primary input data source does not change and if an additional (auxiliary) data source is occasionally available, it cannot be used. An ASR model that operates on both primary and auxiliary data can achieve better accuracy compared to a primary-only solution; and a model that can serve both primary-only (PO) and primary-plus-auxiliary (PPA) modes is highly desirable. In this work, we propose a unified ASR model that can serve both modes. We demonstrate its efficacy in a realistic scenario where a set of devices typically stream a single primary audio channel, and two additional auxiliary channels only when upload bandwidth allows it. The architecture enables a unique methodology that uses both types of input audio during training time. Our proposed approach achieves up to 12.5% relative word-error-rate reduction (WERR) compared to a PO baseline, and up to 16.0% relative WERR in low-SNR conditions. The unique training methodology achieves up to 2.5% relative WERR compared to a PPA baseline.


title: Asymptotic Analysis of the Pauli Potential for Atoms

abstract: Modeling the Pauli energy, the contribution to the kinetic energy caused by Pauli statistics, without using orbitals is the open problem of orbital-free density functional theory. An important aspect of this problem is correctly reproducing the Pauli potential, the response of the Pauli kinetic energy to a change in density. We analyze the behavior of the Pauli potential of non-relativistic neutral atoms under Lieb-Simon scaling -- the process of taking nuclear charge and particle number to infinity, in which the kinetic energy tends to the Thomas-Fermi limit. We do this by mathematical analysis of the near-nuclear region and by calculating the exact orbital-dependent Pauli potential using the approach of Ouyang and Levy for closed-shell atoms out to element Z=976. In rough analogy to Lieb and Simon's own findings for the charge density, we find that the potential does not converge smoothly to the Thomas-Fermi limit on a point-by-point basis but separates into several distinct regions of behavior. Near the nucleus, the potential approaches a constant given by the difference in energy between the lowest and highest occupied eigenvalues. We discover a transition region in the outer core where the potential deviates unexpectedly and predictably from both the Thomas-Fermi potential and the gradient expansion correction to it. These results may provide insight into semi-classical description of Pauli statistics, and new constraints to aid the improvement of orbital-free DFT functionals.


title: Living cells on the move

abstract: Spectacular collective phenomena such as jamming, turbulence, wetting, and waves emerge when living cells migrate in groups.


title: Magnetic states of quasi-one-dimensional iron chalcogenide Ba$_2$FeS$_3$

abstract: Quasi-one-dimensional iron-based ladders and chains, with the 3$d$ iron electronic density $n = 6$, are attracting considerable attention. Recently, a new iron chain system Ba$_2$FeS$_3$, also with $n = 6$, was prepared under high-pressure and high-temperature conditions. Here, the magnetic and electronic phase diagrams are theoretically studied for this quasi-one-dimensional compound. Based on first-principles calculations, a strongly anisotropic one-dimensional electronic band behavior near the Fermi level was observed. In addition, a three-orbital electronic Hubbard model for this chain was constructed. Introducing the Hubbard and Hund couplings and studying the model via the density matrix renormalization group (DMRG) method, we studied the ground-state phase diagram. A robust staggered $\uparrow$-$\downarrow$-$\uparrow$-$\downarrow$ AFM region was unveiled in the chain direction, consistent with our density functional theory (DFT) calculations. Furthermore, at intermediate Hubbard $U$ coupling strengths, this system was found to display an orbital selective Mott phase (OSMP) with one localized orbital and two itinerant metallic orbitals. At very large $U/W$ ($W$ = bandwidth), the system displays Mott insulator characteristics, with two orbitals half-filled and one doubly occupied. Our results for high pressure Ba$_2$FeS$_3$ provide guidance to experimentalists and theorists working on this one-dimensional iron chalcogenide chain material.


title: Unconditionally energy stable and first-order accurate numerical schemes for the heat equation with uncertain temperature-dependent conductivity

abstract: In this paper, we present first-order accurate numerical methods for solution of the heat equation with uncertain temperature-dependent thermal conductivity. Each algorithm yields a shared coefficient matrix for the ensemble set improving computational efficiency. Both mixed and Robin-type boundary conditions are treated. In contrast with alternative, related methodologies, stability and convergence are unconditional. In particular, we prove unconditional, energy stability and optimal-order error estimates. A battery of numerical tests are presented to illustrate both the theory and application of these algorithms.


title: Kernel approximation on algebraic varieties

abstract: Low-rank approximation of kernels is a fundamental mathematical problem with widespread algorithmic applications. Often the kernel is restricted to an algebraic variety, e.g., in problems involving sparse or low-rank data. We show that significantly better approximations are obtainable in this setting: the rank required to achieve a given error depends on the variety's dimension rather than the ambient dimension, which is typically much larger. This is true in both high-precision and high-dimensional regimes. Our results are presented for smooth isotropic kernels, the predominant class of kernels used in applications. Our main technical insight is to approximate smooth kernels by polynomial kernels, and leverage two key properties of polynomial kernels that hold when they are restricted to a variety. First, their ranks decrease exponentially in the variety's co-dimension. Second, their maximum values are governed by their values over a small set of points. Together, our results provide a general approach for exploiting (approximate) "algebraic structure" in datasets in order to efficiently solve large-scale data science problems.


title: Topological phases and entanglement in real space for 1D SSH topological insulator: effects of first and second neighbor-hoppings

abstract: The hybrid atoms-cell site entanglement in a one-dimensional Su-Schrieffer-Heeger (SSH) topological insulator with first and second neighbor hopping interaction in space representation of finite chains is analyzed. The geometric phase is calculated by the Resta electric polarization and the entanglement in the atomic basis by the Schmidt number. A relation between entanglement and the topological phase transitions (TPT) is given since the Schmidt number has critical points of maximal entangled (ME) states in the singularities of the geometrical phase. States with second-neighbors have higher entanglement than first-order hopping. The general conditions to produce ME hybrid Bell states and the localization-entanglement relation are given.


title: Heuristic-Guided Reinforcement Learning

abstract: We provide a framework for accelerating reinforcement learning (RL) algorithms by heuristics constructed from domain knowledge or offline data. Tabula rasa RL algorithms require environment interactions or computation that scales with the horizon of the sequential decision-making task. Using our framework, we show how heuristic-guided RL induces a much shorter-horizon subproblem that provably solves the original task. Our framework can be viewed as a horizon-based regularization for controlling bias and variance in RL under a finite interaction budget. On the theoretical side, we characterize properties of a good heuristic and its impact on RL acceleration. In particular, we introduce the novel concept of an improvable heuristic, a heuristic that allows an RL agent to extrapolate beyond its prior knowledge. On the empirical side, we instantiate our framework to accelerate several state-of-the-art algorithms in simulated robotic control tasks and procedurally generated games. Our framework complements the rich literature on warm-starting RL with expert demonstrations or exploratory datasets, and introduces a principled method for injecting prior knowledge into RL.


title: The Black Hole Mass of NGC 4151 from Stellar Dynamical Modeling

abstract: The mass of a supermassive black hole ($M_\mathrm{BH}$) is a fundamental property that can be obtained through observational methods. Constraining $M_\mathrm{BH}$ through multiple methods for an individual galaxy is important for verifying the accuracy of different techniques, and for investigating the assumptions inherent in each method. NGC 4151 is one of those rare galaxies for which multiple methods can be used: stellar and gas dynamical modeling because of its proximity ($D=15.8\pm0.4$ Mpc from Cepheids), and reverberation mapping because of its active accretion. In this work, we re-analyzed $H-$band integral field spectroscopy of the nucleus of NGC 4151 from Gemini NIFS, improving the analysis at several key steps. We then constructed a wide range of axisymmetric dynamical models with the new orbit-superposition code Forstand. One of our primary goals is to quantify the systematic uncertainties in $M_\mathrm{BH}$ arising from different combinations of the deprojected density profile, inclination, intrinsic flattening, and mass-to-light ratio. As a consequence of uncertainties on the stellar luminosity profile arising from the presence of the AGN, our constraints on \mbh are rather weak. Models with a steep central cusp are consistent with no black hole; however, in models with more moderate cusps, the black hole mass lies within the range of $0.25\times10^7\,M_\odot \lesssim M_\mathrm{BH} \lesssim 3\times10^7\,M_\odot$. This measurement is somewhat smaller than the earlier analysis presented by Onken et al., but agrees with previous $M_\mathrm{BH}$ values from gas dynamical modeling and reverberation mapping. Future dynamical modeling of reverberation data, as well as IFU observations with JWST, will aid in further constraining $M_\mathrm{BH}$ in NGC 4151.


title: Virtual resolutions of points in $\mathbb{P}^1 \times \mathbb{P}^1$

abstract: We explore explicit virtual resolutions, as introduced by Berkesch, Erman, and Smith, for ideals of sets of points in $\mathbb{P}^1 \times \mathbb{P}^1$. Specifically, we describe a virtual resolution for a sufficiently general set of points $X$ in $\mathbb{P}^1 \times \mathbb{P}^1$ that only depends on $|X|$. We also improve an existence result of Berkesch, Erman, and Smith in the special case of points in $\mathbb{P}^1 \times \mathbb{P}^1$; more precisely, we give an effective bound for their construction that gives a virtual resolution of length two for any set of points in $\mathbb{P}^1 \times \mathbb{P}^1$.


title: Cluster Analysis via Random Partition Distributions

abstract: Hierarchical and k-medoids clustering are deterministic clustering algorithms based on pairwise distances. Using these same pairwise distances, we propose a novel stochastic clustering method based on random partition distributions. We call our method CaviarPD, for cluster analysis via random partition distributions. CaviarPD first samples clusterings from a random partition distribution and then finds the best cluster estimate based on these samples using algorithms to minimize an expected loss. We compare CaviarPD with hierarchical and k-medoids clustering through eight case studies. Cluster estimates based on our method are competitive with those of hierarchical and k-medoids clustering. They also do not require the subjective choice of the linkage method necessary for hierarchical clustering. Furthermore, our distribution-based procedure provides an intuitive graphical representation to assess clustering uncertainty.


title: Weak anti-localization in spin-orbit coupled lattice systems: effect of non-adiabatic transitions and estimation of spin relaxation length

abstract: This study investigates the quantum correction effect on electrical conductivity using a two-dimensional Wolff Hamiltonian, which is an effective model of the spin-orbit coupling (SOC) lattice system. The non-adiabatic transition processes in impurity scattering suppress the weak anti-localization (WAL) effect. The WAL effect in the SOC lattice system strongly depends on the spin relaxation length when compared with the Hikami-Larkin-Nagaoka (HLN) theory. The spin relaxation length in Bi thin film is discussed.


title: Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering

abstract: Triangle counting is a fundamental technique in network analysis, that has received much attention in various input models. The vast majority of triangle counting algorithms are targeted to static graphs. Yet, many real-world graphs are directed and temporal, where edges come with timestamps. Temporal triangles yield much more information, since they account for both the graph topology and the timestamps. Temporal triangle counting has seen a few recent results, but there are varying definitions of temporal triangles. In all cases, temporal triangle patterns enforce constraints on the time interval between edges (in the triangle). We define a general notion $(\delta_{1,3}, \delta_{1,2}, \delta_{2,3})$-temporal triangles that allows for separate time constraints for all pairs of edges. Our main result is a new algorithm, DOTTT (Degeneracy Oriented Temporal Triangle Totaler), that exactly counts all directed variants of $(\delta_{1,3}, \delta_{1,2}, \delta_{2,3})$-temporal triangles. Using the classic idea of degeneracy ordering with careful combinatorial arguments, we can prove that DOTTT runs in $O(m\kappa\log m)$ time, where $m$ is the number of (temporal) edges and $\kappa$ is the graph degeneracy (max core number). Up to log factors, this matches the running time of the best static triangle counters. Moreover, this running time is better than existing. DOTTT has excellent practical behavior and runs twice as fast as existing state-of-the-art temporal triangle counters (and is also more general). For example, DOTTT computes all types of temporal queries in Bitcoin temporal network with half a billion edges in less than an hour on a commodity machine.