cssi/SciSciGPT-SciSciNet huggingface dataset:
An almost-linear time algorithm for uniform random spanning tree generation

We give an m1+o(1)βo(1)-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix. Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut the random walk from a vertex v to the boundary of a set of vertices assigned to v called a “shortcutter.” We depart from prior work by introducing a new way of employing Laplacian solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most random walk steps occur far away from an unvisited vertex. We apply this observation by charging uses of a shortcutter S to random walk steps in the Schur complement obtained by eliminating all vertices in S that are not assigned to it.
COMPARISONS OF TWO- AND THREE-DIMENSIONAL CONVECTION IN TYPE I X-RAY BURSTS

We perform the first detailed three-dimensional simulation of low Mach number convection preceding runaway thermonuclear ignition in a mixed H/He X-ray burst. Our simulations include a moderate-sized, approximate network that captures hydrogen and helium burning up through rp-process breakout. We look at the difference between two- and three-dimensional convective fields, including the details of the turbulent convection.
Bone cancer rates in dinosaurs compared with modern vertebrates

Abstract Data on the prevalence of bone cancer in dinosaurs is available from past radiological examination of preserved bones. We statistically test this data for consistency with rates extrapolated from information on bone cancer in modern vertebrates, and find that there is no evidence of a different rate. Thus, this test provides no support for a possible role of ionizing radiation in the K-T extinction event.
Convolutional-Recurrent Neural Networks for Speech Enhancement

We propose an end-to-end model based on convolutional and recurrent neural networks for speech enhancement. Our model is purely data-driven and does not make any assumptions about the type or the stationarity of the noise. In contrast to existing methods that use multilayer perceptrons (MLPs), we employ both convolutional and recurrent neural network architectures. Thus, our approach allows us to exploit local structures in both the frequency and temporal domains. By incorporating prior knowledge of speech signals into the design of model structures, we build a model that is more data-efficient and achieves better generalization on both seen and unseen noise. Based on experiments with synthetic data, we demonstrate that our model outperforms existing methods, improving PESQ by up to 0.6 on seen noise and 0.64 on unseen noise.
Provision of Public Goods on Networks: On Existence, Uniqueness, and Centralities

We consider the provision of public goods on networks of strategic agents. We study different effort outcomes of these network games, namely, the Nash equilibria, Pareto efficient effort profiles, and semi-cooperative equilibria (resulting from interactions among coalitions of agents). We identify necessary and sufficient conditions on the structure of the network for the uniqueness of the Nash equilibrium by using a connection between these outcomes and linear complementarity problems. We show that our finding unifies, and extends, existing results in the literature. We also identify conditions for the existence of Nash equilibria for two subclasses of games at the two extremes of our model, namely games of strategic complements and games of strategic substitutes. We provide a graph-theoretical interpretation of agents’ efforts at the Nash equilibrium, as well as the Pareto efficient outcomes and semi-cooperative equilibria, by linking an agent's decision to her centrality in the interaction network. Using this connection, we separate the effects of incoming and outgoing edges on agents’ efforts and uncover an alternating effect over walks of different length in the network.
The Disk-Halo Connection and Where Has All The Gas Gone?

The wealth of data in the past decades, and especially in the past 15 years has transformed our picture of the gas around the Milky Way and other spiral galaxies. There is good evidence for extraplanar gas that is a few kpc in height and is seen in all gaseous phases: neutral; warm atomic; and hot, X-ray emitting gas. This medium is seen not only around the Milky Way, but other spiral galaxies and it is related to the star formation rate, so it is likely produced by the activity in the disk through a galactic fountain. More extended examples of halo gas are seen, such as the HVC around the Milky Way and around M 31. This gas is typically 10–20 kpc from the galaxy and is not seen beyond 50 kpc. This gas is most likely being accreted. A hot dilute halo (106 K) is present with a similar size, although its size is poorly determined.An ongoing controversy surrounds the relative amounts of outflow from the disk and accretion onto galaxies such as the Milky Way. There is good evidence for accretion of cold material onto the Milky Way and other galaxies, but it is not clear if there is enough to modify the gas content and star formation properties in the disk. The reservoir of accretion material is as yet unidentified. Some of these findings may be related to the issue that galaxies are baryon-poor: their baryon to dark matter ratio is well below the cosmological value. The absence of baryons may be due to extremely violent outflow events in the early stages of galaxy formation. We may be able to understand this stage of galaxy evolution by applying our deepening understanding of our local disk-halo environment.
MULTIPLICATION GROUPS AND INNER MAPPING GROUPS OF CAYLEY–DICKSON LOOPS

The Cayley–Dickson loop Qn is the multiplicative closure of basic elements of the algebra constructed by n applications of the Cayley–Dickson doubling process (the first few examples of such algebras are real numbers, complex numbers, quaternions, octonions, sedenions). We establish that the inner mapping group Inn(Qn) is an elementary abelian 2-group of order 22n-2 and describe the multiplication group Mlt(Qn) as a semidirect product of Inn(Qn) × ℤ2 and an elementary abelian 2-group of order 2n. We prove that one-sided inner mapping groups Innl(Qn) and Innr(Qn) are equal, elementary abelian 2-groups of order 22n-1-1. We establish that one-sided multiplication groups Mltl(Qn) and Mltr(Qn) are isomorphic, and show that Mltl(Qn) is a semidirect product of Innl(Qn) × ℤ2 and an elementary abelian 2-group of order 2n.
Vector diffusion maps and the connection Laplacian

We introduce vector diffusion maps (VDM), a new mathematical framework for organizing and analyzing massive high-dimensional data sets, images, and shapes. VDMis a mathematical and algorithmic generalization of diffusion maps and other nonlinear dimensionality reduction methods, such as LLE, ISOMAP, and Laplacian eigenmaps. While existing methods are either directly or indirectly related to the heat kernel for functions over the data, VDM is based on the heat kernel for vector fields. VDM provides tools for organizing complex data sets, embedding them in a low-dimensional space, and interpolating and regressing vector fields over the data. In particular, it equips the data with a metric, which we refer to as the vector diffusion distance. In the manifold learning setup, where the data set is distributed on a low-dimensional manifold embedded in , we prove the relation between VDM and the connection Laplacian operator for vector fields over the manifold. © 2012 Wiley Periodicals, Inc.
LOCAL GRADIENT ESTIMATES OF p-HARMONIC FUNCTIONS, 1/H-FLOW, AND AN ENTROPY FORMULA

Dans la premiere partie de cet article, nous etablissons des estimees locales de gradient pour les fonctions p-harmoniques a l'interieur et au bord, sur les varietes riemanniennes generales. Grâce a ces estimations et suivant une idee recente de R. Moser, nous obtenons un theoreme d'existence de solutions faibles au sens de la formulation d'ensemble de niveau pour le flot 1/H (inverse de la courbure moyenne) des hypersurfaces dans les varietes ambiantes ayant la propriete de la croissance optimale du volume. Dans la deuxieme partie, nous considerons deux types d'equations paraboliques pour les fonctions p-harmoniques et nous etablissons une estimation optimale du type de Li-Yau pour les solutions positives pour ces equations sur les varietes a courbure de Ricci non-negative. Nous montrons aussi une formule de monotonie des entropies associees a ces equations. Cette formule generalise un resultat anterieur du deuxieme auteur pour l'equation de la chaleur lineaire. Comme application, nous montrons que toute variete riemannienne complete a courbure de Ricci positive ou nulle et admettant une inegalite logarithmique L P optimale est isometrique a l'espace euclidien.
Random self-similar trees and a hierarchical branching process

Abstract We study self-similarity in random binary rooted trees. In a well-understood case of Galton–Watson trees, a distribution on a space of trees is said to be self-similar if it is invariant with respect to the operation of pruning, which cuts the tree leaves. This only happens for the critical Galton–Watson tree (a constant process progeny), which also exhibits other special symmetries. We extend the prune-invariance setup to arbitrary binary trees with edge lengths. In this general case the class of self-similar processes becomes much richer and covers a variety of practically important situations. The main result is construction of the hierarchical branching processes that satisfy various self-similarity definitions (including mean self-similarity and self-similarity in edge-lengths) depending on the process parameters. Taking the limit of averaged stochastic dynamics, as the number of trajectories increases, we obtain a deterministic system of differential equations that describes the process evolution. This system is used to establish a phase transition that separates fading and explosive behavior of the average process progeny. We describe a class of critical Tokunaga processes that happen at the phase transition boundary. They enjoy multiple additional symmetries and include the celebrated critical binary Galton–Watson tree with independent exponential edge length as a special case. Finally, we discuss a duality between trees and continuous functions, and introduce a class of extreme-invariant processes, constructed as the Harris paths of a self-similar hierarchical branching process, whose local minima has the same (linearly scaled) distribution as the original process.
The derived category of a GIT quotient

Given a quasiprojective algebraic variety with a reductive group action, we describe a relationship between its equivariant derived category and the derived category of its geometric invariant theory quotient. This generalizes classical descriptions of the category of coherent sheaves on projective space and categorifies several results in the theory of Hamiltonian group actions on projective manifolds. This perspective generalizes and provides new insight into examples of derived equivalences between birational varieties. We provide a criterion under which two different GIT quotients are derived equivalent, and apply it to prove that any two generic GIT quotients of an equivariantly Calabi-Yau projective-over-affine manifold by a torus are derived equivalent.
Choices, intervals and equidistribution

We give a sufficient condition for a random sequence in [0,1] generated by a Psi-process to be equidistributed. The condition is met by the canonical example - the max-2 process - where the $n$th term is whichever of two uniformly placed points falls in the larger gap formed by the previous $n$-1 points. Also, we deduce equidistribution for an interpolation of the min-2 and max-2 processes that is biased towards min-2, as well as more general interpolations. This solves an open problem from Itai Benjamini, Pascal Maillard and Elliot Paquette.
The degree of irrationality of hypersurfaces in various Fano varieties

The purpose of this paper is to compute the degree of irrationality of hypersurfaces of sufficiently high degree in various Fano varieties: quadrics, Grassmannians, products of projective space, cubic threefolds, cubic fourfolds, and complete intersection threefolds of type (2,2). This extends the techniques of Bastianelli, De Poi, Ein, Lazarsfeld, and the second author who computed the degree of irrationality of hypersurfaces of sufficiently high degree in projective space. A theme in the paper is that the fibers of low degree rational maps from the hypersurfaces to projective space tend to lie on curves of low degree contained in the Fano varieties. This allows us to study these maps by studying the geometry of curves in these Fano varieties.
Quickest Change Detection Under Transient Dynamics: Theory and Asymptotic Analysis

The problem of quickest change detection under transient dynamics is studied, where the change from the initial distribution to the final persistent distribution does not happen instantaneously, but after a series of transient phases. The observations within the different phases are generated by different distributions. The objective is to detect the change as quickly as possible, while controlling the average run length (ARL) to false alarm, when the durations of the transient phases are completely unknown. Two algorithms are considered: the dynamic Cumulative Sum (CuSum) algorithm, proposed in earlier work, and a newly constructed weighted dynamic CuSum algorithm. Both algorithms admit recursions that facilitate their practical implementation, and they are adaptive to the unknown transient durations. Specifically, their asymptotic optimality is established with respect to both Lorden’s and Pollak’s criteria as the ARL to false alarm and the durations of the transient phases go to infinity at any relative rate. Numerical results are provided to demonstrate the adaptivity of the proposed algorithms and to validate the theoretical results.
Optimal sweepouts of a Riemannian 2-sphere

Given a sweepout of a Riemannian 2-sphere which is composed of curves of length less than L, we construct a second sweepout composed of curves of length less than L which are either constant curves or simple curves. This result, and the methods used to prove it, have several consequences; we answer a question of M. Freedman concerning the existence of min-max embedded geodesics, we partially answer a question due to N. Hingston and H.-B. Rademacher, and we also extend the results of [CL] concerning converting homotopies to isotopies in an effective way.
Weak Pseudogap Behavior in the Underdoped Cuprate Superconductors

We report on a novel solution of the nearly antiferromagnetic (AF) spin fermion model in the limit $\ensuremath{\pi}T\ensuremath{\gg}{\ensuremath{\omega}}_{\mathrm{sf}}$, which demonstrates that the broad high energy features found in angular resolved photoemission spectroscopy measurements of the spectral density of the underdoped cuprates are determined by strong (AF) correlations and precursor effects of a spin density wave state. We show that the onset temperature, ${T}^{\mathrm{cr}}$, of weak pseudogap behavior is determined by the strength, $\ensuremath{\xi}$, of the (AF) correlations, and obtain the generic changes in low frequency magnetic behavior seen in NMR experiments with $\ensuremath{\xi}({T}^{\mathrm{cr}})\ensuremath{\approx}2$, confirming the Barzykin and Pines crossover criterion.
Unphysical diagonal modular invariants

Abstract A modular invariant for a chiral conformal field theory is physical if there is a full conformal field theory with the given chiral halves realising the modular invariant. The easiest modular invariants are the charge conjugation and the diagonal modular invariants. While the charge conjugation modular invariant is always physical there are examples of chiral CFTs for which the diagonal modular invariant is not physical. Here we give (in group theoretical terms) a necessary and sufficient condition for diagonal modular invariants of G-orbifolds of holomorphic conformal field theories to be physical. Mathematically a physical modular invariant is an invariant of a Lagrangian algebra in the product of (chiral) modular categories. The chiral modular category of a G-orbifold of a holomorphic conformal field theory is the so-called (twisted) Drinfeld centre Z ( G , α ) of the finite group G. We show that the diagonal modular invariant for Z ( G ) is physical if and only if the group G has a double class inverting automorphism, that is an automorphism ϕ : G → G with the property that for any commuting x , y ∈ G there is g ∈ G such that ϕ ( x ) = g x − 1 g − 1 , ϕ ( y ) = g y − 1 g − 1 . Groups without double class inverting automorphisms are abundant and provide examples of chiral conformal field theories for which the diagonal modular invariant is unphysical.
The G-invariant spectrum and non-orbifold singularities

We consider the G-invariant spectrum of the Laplacian on an orbit space M/G where M is a compact Riemannian manifold and G acts by isometries. We generalize the Sunada–Pesce–Sutton technique to the G-invariant setting to produce pairs of isospectral non-isometric orbit spaces. One of these spaces is isometric to an orbifold with constant sectional curvature whereas the other admits non-orbifold singularities and therefore has unbounded sectional curvature. We conclude that constant sectional curvature and the presence of non-orbifold singularities are inaudible to the G-invariant spectrum.
On the complexity of role colouring planar graphs, trees and cographs

Abstract We prove several results about the complexity of the role colouring problem. A role colouring of a graph G is an assignment of colours to the vertices of G such that two vertices of the same colour have identical sets of colours in their neighbourhoods. We show that the problem of finding a role colouring with 1 k n colours is NP-hard for planar graphs. We show that restricting the problem to trees yields a polynomially solvable case, as long as k is either constant or has a constant difference with n , the number of vertices in the tree. Finally, we prove that cographs are always k -role-colourable for 1 k ≤ n and construct such a colouring in polynomial time.
Polynomial-Time Random Oracles and Separating Complexity Classes

Bennett and Gill [1981] showed that PA ≠ NPA ≠ coNPA for a random oracle A, with probability 1. We investigate whether this result extends to individual polynomial-time random oracles. We consider two notions of random oracles: p-random oracles in the sense of martingales and resource-bounded measure [Lutz 1992; Ambos-Spies et al. 1997], and p-betting-game random oracles using the betting games generalization of resource-bounded measure [Buhrman et al. 2000]. Every p-betting-game random oracle is also p-random; whether the two notions are equivalent is an open problem. (1) We first show that PA ≠ NPA for every oracle A that is p-betting-game random. Ideally, we would extend (1) to p-random oracles. We show that answering this either way would imply an unrelativized complexity class separation: (2) If PA ≠ NPA relative to every p-random oracle A, then BPP ≠ EXP. (3) If PA ≠ NPA relative to some p-random oracle A, then P ≠ PSPACE. Rossman, Servedio, and Tan [2015] showed that the polynomial-time hierarchy is infinite relative to a random oracle, solving a longstanding open problem. We consider whether we can extend (1) to show that PHA is infinite relative to oracles A that are p-betting-game random. Showing that PHA separates at even its first level would also imply an unrelativized complexity class separation: (4) If NPA ≠ coNPA for a p-betting-game measure 1 class of oracles A, then NP ≠ EXP. (5) If PHA is infinite relative to every p-random oracle A, then PH ≠ EXP. We also consider random oracles for time versus space, for example: (6) LA ≠ PA relative to every oracle A that is p-betting-game random.
Intriguing Properties of Adversarial Examples

It is becoming increasingly clear that many machine learning classifiers are vulnerable to adversarial examples. In attempting to explain the origin of adversarial examples, previous studies have typically focused on the fact that neural networks operate on high dimensional data, they overfit, or they are too linear. Here we argue that the origin of adversarial examples is primarily due to an inherent uncertainty that neural networks have about their predictions. We show that the functional form of this uncertainty is independent of architecture, dataset, and training protocol; and depends only on the statistics of the logit differences of the network, which do not change significantly during training. This leads to adversarial error having a universal scaling, as a power-law, with respect to the size of the adversarial perturbation. We show that this universality holds for a broad range of datasets (MNIST, CIFAR10, ImageNet, and random data), models (including state-of-the-art deep networks, linear models, adversarially trained networks, and networks trained on randomly shuffled labels), and attacks (FGSM, step l.l., PGD). Motivated by these results, we study the effects of reducing prediction entropy on adversarial robustness. Finally, we study the effect of network architectures on adversarial sensitivity. To do this, we use neural architecture search with reinforcement learning to find adversarially robust architectures on CIFAR10. Our resulting architecture is more robust to white \emph{and} black box attacks compared to previous attempts.
An Elementary, First Principles Approach to the Indefinite Spin Groups

In this work we provide an elementary novel derivation of the indefinite spin groups Spin+(p, q) in low-dimensions. Our approach relies on the isomorphism Cl(p+1, q+1) = M(2, Cl(p, q)), simple properties of Kronecker products, characterization of when an even dimensional real (resp. complex) matrix represents a complex (resp. quaternionic) linear transformation, and basic aspects of the isomorphism \({{\mathbf{H}} \otimes {\mathbf{H}} = M(4, {\mathbf{R}})}\). Of these the last is arguably the most vital. Among other things it yields, naturally, a surprisingly ubiquitous role for the matrix \({\left(\begin{array} {cc} 0 & i \sigma_{y} \\ i \sigma_{y} & 0\end{array}\right)}\). Our approach has the benefit of identifying these spin groups as explicit groups of matrices within the same collection of matrices which define Cl(p, q). In other words, we do not work in the algebra of matrices that the collection of even vectors in Cl(p, q) is isomorphic to. This is crucial in some applications and also has the advantage of being didactically simple. Furthermore, all constructions are fully explicit and never require eigencomputations beyond those for \({2\times 2}\) matrices.
Splitting algebras: Koszul, Cohen–Macaulay and numerically Koszul

Abstract We study a finite dimensional quadratic graded algebra R Γ defined from a finite ranked poset Γ. This algebra has been central to the study of the splitting algebras A Γ introduced by Gelfand, Retakh, Serconek and Wilson [4] . Those algebras are known to be quadratic when Γ satisfies a combinatorial condition known as uniform. A central question in this theory has been: when are the algebras Koszul? We prove that R Γ is Koszul and Γ is cyclic and uniform if and only if the poset Γ is Cohen–Macaulay. We also show that the cohomology of the order complex of Γ can be identified with certain cohomology groups defined internally to the ring R Γ , H R Γ ( n , 0 ) (introduced in [2] ) whenever Γ is Cohen–Macaulay. Finally, we settle in the negative the long-standing question: Does numerically Koszul imply Koszul for algebras of the form R Γ .
IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM

This paper presents an improved analysis of a structured dimension-reduction map called the subsampled randomized Hadamard transform. This argument demonstrates that the map preserves the Euclidean geometry of an entire subspace of vectors. The new proof is much simpler than previous approaches, and it offers — for the first time — optimal constants in the estimate on the number of dimensions required for the embedding.
Computational approaches for zero forcing and related problems

Abstract In this paper, we propose computational approaches for the zero forcing problem, the connected zero forcing problem, and the problem of forcing a graph within a specified number of timesteps. Our approaches are based on a combination of integer programming models and combinatorial algorithms, and include formulations for zero forcing as a dynamic process, and as a set-covering problem. We explore several solution strategies for these models, test them on various types of graphs, and show that they are competitive with the state-of-the-art algorithm for zero forcing. Our proposed algorithms for connected zero forcing and for controlling the number of zero forcing timesteps are the first general-purpose computational methods for these problems, and are superior to brute force computation.
ResNet with one-neuron hidden layers is a Universal Approximator

We demonstrate that a very deep ResNet with stacked modules that have one neuron per hidden layer and ReLU activation functions can uniformly approximate any Lebesgue integrable function in d dimensions, i.e. \ell_1(R^d). Due to the identity mapping inherent to ResNets, our network has alternating layers of dimension one and d. This stands in sharp contrast to fully connected networks, which are not universal approximators if their width is the input dimension d [21,11]. Hence, our result implies an increase in representational power for narrow deep networks by the ResNet architecture.
Proof of a conjecture of Kenyon and Wilson on semicontiguous minors

Abstract Kenyon and Wilson showed how to test if a circular planar electrical network with n nodes is well-connected by checking the positivity of ( n 2 ) central minors of the response matrix. Their test is based on the fact that any contiguous minor of a matrix can be expressed as a Laurent polynomial in the central minors. Moreover, the Laurent polynomial is the generating function of domino tilings of a weighted Aztec diamond. They conjectured that a larger family of minors, semicontiguous minors, can also be written in terms of domino tilings of a region on the square lattice. In this paper, we present a proof of the conjecture.
A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update

Nonconvex optimization arises in many areas of computational science and engineering. However, most nonconvex optimization algorithms are only known to have local convergence or subsequence convergence properties. In this paper, we propose an algorithm for nonconvex optimization and establish its global convergence (of the whole sequence) to a critical point. In addition, we give its asymptotic convergence rate and numerically demonstrate its efficiency. In our algorithm, the variables of the underlying problem are either treated as one block or multiple disjoint blocks. It is assumed that each non-differentiable component of the objective function, or each constraint, applies only to one block of variables. The differentiable components of the objective function, however, can involve multiple blocks of variables together. Our algorithm updates one block of variables at a time by minimizing a certain prox-linear surrogate, along with an extrapolation to accelerate its convergence. The order of update can be either deterministically cyclic or randomly shuffled for each cycle. In fact, our convergence analysis only needs that each block be updated at least once in every fixed number of iterations. We show its global convergence (of the whole sequence) to a critical point under fairly loose conditions including, in particular, the Kurdyka–Łojasiewicz condition, which is satisfied by a broad class of nonconvex/nonsmooth applications. These results, of course, remain valid when the underlying problem is convex. We apply our convergence results to the coordinate descent iteration for non-convex regularized linear regression, as well as a modified rank-one residue iteration for nonnegative matrix factorization. We show that both applications have global convergence. Numerically, we tested our algorithm on nonnegative matrix and tensor factorization problems, where random shuffling clearly improves the chance to avoid low-quality local solutions.
Direct monocular odometry using points and lines

Most visual odometry algorithm for a monocular camera focuses on points, either by feature matching, or direct alignment of pixel intensity, while ignoring a common but important geometry entity: edges. In this paper, we propose an odometry algorithm that combines points and edges to benefit from the advantages of both direct and feature based methods. It works better in texture-less environments and is also more robust to lighting changes and fast motion by increasing the convergence basin. We maintain a depth map for the keyframe then in the tracking part, the camera pose is recovered by minimizing both the photometric error and geometric error to the matched edge in a probabilistic framework. In the mapping part, edge is used to speed up and increase stereo matching accuracy. On various public datasets, our algorithm achieves better or comparable performance than state-of-the-art monocular odometry methods. In some challenging texture-less environments, our algorithm reduces the state estimation error over 50%.
Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove e n edges from G to make it H-minor free (for some small constant e > 0). We give an n^1/2+o(1)-time randomized procedure that, with high probability, finds an H-minor in such a graph. As an application, suppose one must remove e n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K_3,3 or K_5 minor in G. No prior sublinear time bound was known for this problem. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n^o(1) factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an Ω(√n) lower bound of Czumaj et al (RSA 2014). Prior to this work, the only graphs H for which non-trivial one-sided property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_2, k, (k× 2)-grid, and the k-circus (Fichtenberger et al, Arxiv 2017).
Restricting Homology to Hypersurfaces

This paper concerns the homological properties of a module M over a ring R relative to a presentation \(R\cong P/I\), where P is local ring. It is proved that the Betti sequence of M with respect to P / (f) for a regular element f in I depends only on the class of f in \(I/\mathfrak {n} I\), where \(\mathfrak {n}\) is the maximal ideal of P. Applications to the theory of supports sets in local algebra and in the modular representation theory of elementary abelian groups are presented.
The Alexander polynomial for virtual twist knots

We define a family of virtual knots generalizing the classical twist knots. We develop a recursive formula for the Alexander polynomial Δ0 (as defined by Silver and Williams [Polynomial invariants of virtual links, J. Knot Theory Ramifications 12 (2003) 987–1000]) of these virtual twist knots. These results are applied to provide evidence for a conjecture that the odd writhe of a virtual knot can be obtained from Δ0.
Asymptotic properties of solutions of the Maxwell Klein Gordon equation with small data

We prove peeling estimates for the small data solutions of the Maxwell Klein Gordon equations with non-zero charge and with a non-compactly supported scalar field, in $(3+1)$ dimensions. We obtain the same decay rates as in an earlier work by Lindblad and Sterbenz, but giving a simpler proof. In particular we dispense with the fractional Morawetz estimates for the electromagnetic field, as well as certain space-time estimates. In the case that the scalar field is compactly supported we can avoid fractional Morawetz estimates for the scalar field as well. All of our estimates are carried out using the double null foliation and in a gauge invariant manner.
Adversarial examples from computational constraints

Why are classifiers in high dimension vulnerable to "adversarial" perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due to computational constraints. First we prove that, for a broad set of classification tasks, the mere existence of a robust classifier implies that it can be found by a possibly exponential-time algorithm with relatively few training examples. Then we give a particular classification task where learning a robust classifier is computationally intractable. More precisely we construct a binary classification task in high dimensional space which is (i) information theoretically easy to learn robustly for large perturbations, (ii) efficiently learnable (non-robustly) by a simple linear separator, (iii) yet is not efficiently robustly learnable, even for small perturbations, by any algorithm in the statistical query (SQ) model. This example gives an exponential separation between classical learning and robust learning in the statistical query model. It suggests that adversarial examples may be an unavoidable byproduct of computational limitations of learning algorithms.
Empirically Grounded Agent-Based Models of Innovation Diffusion: A Critical Review

Innovation diffusion has been studied extensively in a variety of disciplines, including sociology, economics, marketing, ecology, and computer science. Traditional literature on innovation diffusion has been dominated by models of aggregate behavior and trends. However, the agent-based modeling (ABM) paradigm is gaining popularity as it captures agent heterogeneity and enables fine-grained modeling of interactions mediated by social and geographic networks. While most ABM work on innovation diffusion is theoretical, empirically grounded models are increasingly important, particularly in guiding policy decisions. We present a critical review of empirically grounded agent-based models of innovation diffusion, developing a categorization of this research based on types of agent models as well as applications. By connecting the modeling methodologies in the fields of information and innovation diffusion, we suggest that the maximum likelihood estimation framework widely used in the former is a promising paradigm for calibration of agent-based models for innovation diffusion. Although many advances have been made to standardize ABM methodology, we identify four major issues in model calibration and validation, and suggest potential solutions.
Rational maps whose Fatou components are Jordan domains

We prove: If f(z) is a critically finite rational map which has exactly two critical points and which is not conjugate to a polynomial, then the boundary of every Fatou component of f is a Jordan curve. If f(z) is a hyperbolic critically finite rational map all of whose postcritical points are periodic, then there exists a cycle of Fatou components whose boundaries are Jordan curves. We give examples of critically finite hyperbolic rational maps f with a Fatou component ω satisfying f(ω) = ω and f|∂ω not topologically conjugate to the dynamics of any polynomial on its Julia set.
Advancing Acoustic-to-Word CTC Model

The acoustic-to-word model based on the connectionist temporal classification (CTC) criterion was shown as a natural end-to-end (E2E) model directly targeting words as output units. However, the word-based CTC model suffers from the out-of-vocabulary (OOV) issue as it can only model limited number of words in the output layer and maps all the remaining words into an OOV output node. Hence, such a word-based CTC model can only recognize the frequent words modeled by the network output nodes. Our first attempt to improve the acoustic-to-word model is a hybrid CTC model which consults a letter-based CTC when the word-based CTC model emits OOV tokens during testing time. Then, we propose a much better solution by training a mixed-unit CTC model which decomposes all the OOV words into sequences of frequent words and multi-letter units. Evaluated on a 3400 hours Microsoft Cortana voice assistant task, the final acoustic-to-word solution improves the baseline word-based CTC by relative 12.09% word error rate (WER) reduction when combined with our proposed attention CTC. Such an E2E model without using any language model (LM) or complex decoder outperforms the traditional context-dependent phoneme CTC which has strong LM and decoder by relative 6.79%.
Efficient characteristic refinements for finite groups

Abstract Filters were introduced by J.B. Wilson in 2013 to generalize work of Lazard with associated graded Lie rings. It holds promise in improving isomorphism tests, but the formulas introduced then were impractical for computation. Here, we provide an efficient algorithm for these formulas, and we demonstrate their usefulness on several examples of p -groups.
Hausdorff stability of the round two-sphere under small perturbations of the entropy

We show that if a closed surface in $\mathbb{R}^3$ has entropy near to that of the unit two-sphere, then the surface is close to a round two-sphere in the Hausdorff distance.
Experimental evaluation of a reconfigurable antenna system for blind interference alignment

In recent years, several experimental studies have come out to validate the theoretical findings of interference alignment (IA), but only a handful of studies have focused on blind interference alignment. Unlike IA and other interference mitigation techniques, blind IA does not require channel state information at the transmitter (CSIT). The key insight is that the transmitter uses the knowledge of channel coherence intervals and receivers utilize reconfigurable antennas to create channel fluctuations exploited by the transmitter. In this work, we present a novel experimental evaluation of a reconfigurable antenna system for achieving blind IA. We present a blind IA technique based on reconfigurable antennas for a 2-user multiple-input single-output (MISO) broadcast channel implemented on a software defined radio platform where each of the receivers is equipped with a reconfigurable antenna. We further compare this blind IA implementation with traditional TDMA scheme for benchmarking purposes. We show that the achievable rates for blind IA can be realized in practice using measured channels under practical channel conditions. Additionally, the average error vector magnitude and bit error rate (BER) performances are evaluated.
A new type of neurons for machine learning.

In machine learning, the use of an artificial neural network is the mainstream approach. Such a network consists of layers of neurons. These neurons are of the same type characterized by the two features: (1) an inner product of an input vector and a matching weighting vector of trainable parameters and (2) a nonlinear excitation function. Here we investigate the possibility of replacing the inner product with a quadratic function of the input vector, thereby upgrading the 1st order neuron to the 2nd order neuron, empowering individual neurons, and facilitating the optimization of neural networks. Also, numerical examples are provided to illustrate the feasibility and merits of the 2nd order neurons. Finally, further topics are discussed.
Double exponential growth of the vorticity gradient for the two-dimensional Euler equation

For the two-dimensional Euler equation on the torus, we prove that the L∞–norm of the vorticity gradient can grow as double exponential over arbitrary long but finite time provided that at time zero it is already sufficiently large. The method is based on the perturbative analysis around the singular stationary solution studied by Bahouri and Chemin in [1]. Our result on the growth of the vorticity gradient is equivalent to the statement that the operator of Euler evolution is not bounded in the linear sense in Lipschitz norm for any time t > 0.
Frame potential for finite-dimensional Banach spaces

Abstract We define the frame potential for a Schauder frame on a finite dimensional Banach space as the square of the 2-summing norm of the frame operator. As is the case for frames for Hilbert spaces, we prove that the frame potential can be used to characterize finite unit norm tight frames (FUNTFs) for finite dimensional Banach spaces. We prove the existence of FUNTFs for a variety of spaces, and in particular that every n-dimensional complex Banach space with a 1-unconditional basis has a FUNTF of N vectors for every N ≥ n . However, many interesting results on FUNTFs and sums of rank-one projections for Hilbert spaces remain unknown for Banach spaces and we conclude the paper with multiple open questions.
RAY CLASS GROUPS OF QUADRATIC AND CYCLOTOMIC FIELDS

This paper studies Galois extensions over real quadratic number fields or cyclotomic number fields ramified only at one prime. In both cases, the ray class groups are computed, and they give restrictions on the finite groups that can occur as such Galois groups. Let be a real quadratic number field with a prime P lying above p in ℚ. If p splits in K/ℚ and p does not divide the big class number of K, then any pro-p extension of K ramified only at P is finite cyclic. If p is inert in K/ℚ, then there exist infinite extensions of K ramified only at P. Furthermore, for big enough integer k, the ray class field (mod Pk+1) is obtained from the ray class field (mod Pk) by adjoining ζpk+1. In the case of a regular cyclotomic number field K = ℚ(ζp), the explicit structure of ray class groups (mod Pk) is given for any positive integer k, where P is the unique prime in K above p.
Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits

We propose a new oracle-based algorithm, BISTRO+, for the adversarial contextual bandit problem, where either contexts are drawn i.i.d. or the sequence of contexts is known a priori, but where the losses are picked adversarially. Our algorithm is computationally efficient, assuming access to an offline optimization oracle, and enjoys a regret of order $O((KT)^{\frac{2}{3}}(\log N)^{\frac{1}{3}})$, where $K$ is the number of actions, $T$ is the number of iterations, and $N$ is the number of baseline policies. Our result is the first to break the $O(T^{\frac{3}{4}})$ barrier achieved by recent algorithms, which was left as a major open problem. Our analysis employs the recent relaxation framework of (Rakhlin and Sridharan, ICML'16).
Strong transience of one-dimensional random walk in a random environment

A transient stochastic process is considered strongly transient if conditioned on returning to the starting location, the expected time it takes to return the the starting location is finite. We characterize strong transience for a one-dimensional random walk in a random environment. We show that under the quenched measure transience is equivalent to strong transience, while under the averaged measure strong transience is equivalent to ballisticity (transience with non zero limiting speed).
Multi-Agent Distributed Lifelong Learning for Collective Knowledge Acquisition

Lifelong machine learning methods acquire knowledge over a series of consecutive tasks, continually building upon their experience. Current lifelong learning algorithms rely upon a single learning agent that has centralized access to all data. In this paper, we extend the idea of lifelong learning from a single agent to a network of multiple agents that collectively learn a series of tasks. Each agent faces some (potentially unique) set of tasks; the key idea is that knowledge learned from these tasks may benefit other agents trying to learn different (but related) tasks. Our Collective Lifelong Learning Algorithm (CoLLA) provides an efficient way for a network of agents to share their learned knowledge in a distributed and decentralized manner, while eliminating the need to share locally observed data. We provide theoretical guarantees for robust performance of the algorithm and empirically demonstrate that CoLLA outperforms existing approaches for distributed multi-task learning on a variety of datasets.
Linear Quadratic Optimal Control Problems with Fixed Terminal States and Integral Quadratic Constraints

This paper is concerned with a linear quadratic (LQ, for short) optimal control problem with fixed terminal states and integral quadratic constraints. A Riccati equation with infinite terminal value is introduced, which is uniquely solvable and whose solution can be approximated by the solution for a suitable unconstrained LQ problem with penalized terminal state. Using results from duality theory, the optimal control is explicitly derived by solving the Riccati equation together with an optimal parameter selection problem. It turns out that the optimal control is a target-dependent feedback of the current state. Some examples are presented to illustrate the theory developed.
Families Of K3 surfaces and Lyapunov exponents

Consider a family of K3 surfaces over a hyperbolic curve (i.e., Riemann surface). Their second cohomology groups form a local system, and we show that its top Lyapunov exponent is a rational number. One proof uses the Kuga–Satake construction, which reduces the question to Hodge structures of weight 1. A second proof uses integration by parts. The case of maximal Lyapunov exponent corresponds to modular families coming from the Kummer construction.
Design Principles for Sparse Matrix Multiplication on the GPU

We implement two novel algorithms for sparse-matrix dense-matrix multiplication (SpMM) on the GPU. Our algorithms expect the sparse input in the popular compressed-sparse-row (CSR) format and thus do not require expensive format conversion. While previous SpMM work concentrates on thread-level parallelism, we additionally focus on latency hiding with instruction-level parallelism and load-balancing. We show, both theoretically and experimentally, that the proposed SpMM is a better fit for the GPU than previous approaches. We identify a key memory access pattern that allows efficient access into both input and output matrices that is crucial to getting excellent performance on SpMM. By combining these two ingredients—(i) merge-based load-balancing and (ii) row-major coalesced memory access—we demonstrate a 4.1\(\times \) peak speedup and a 31.7% geomean speedup over state-of-the-art SpMM implementations on real-world datasets.
The impact of time delay in a tumor model

Abstract In this paper we consider a free boundary tumor growth model with a time delay in cell proliferation and study how time delay affects the stability and the size of the tumor. The model is a coupled system of an elliptic equation, a parabolic equation and an ordinary differential equation. It incorporates the cell location under the presence of time delay, with the tumor boundary as a free boundary. A parameter μ in the model is proportional to the “aggressiveness” of the tumor. It is proved that there exists a unique classical radially symmetric stationary solution ( σ ∗ , p ∗ , R ∗ ) which is stable for any μ > 0 with respect to all radially symmetric perturbations (c.f. Xu et al. (2015)). However, under non-radially symmetric perturbations, we prove that there exists a critical value μ ∗ , such that if μ μ ∗ then the stationary solution ( σ ∗ , p ∗ , R ∗ ) is linearly stable; whereas if μ > μ ∗ the stationary solution is unstable. It is actually unrealistic to expect the problem to be stable for large tumor aggressiveness parameter, therefore our result is more reasonable. Furthermore, we established that adding the time delay in the model would result in a larger stationary tumor, and if the tumor aggressiveness parameter is larger, then the time delay would have a greater impact on the size of the tumor.