cssi/SciSciGPT-SciSciNet huggingface dataset:
The Vertex Sample Complexity of Free Energy is Polynomial

We study the following question: given a massive Markov random field on $n$ nodes, can a small sample from it provide a rough approximation to the free energy $\mathcal{F}_n = \log{Z_n}$? Results in graph limit literature by Borgs, Chayes, Lovasz, Sos, and Vesztergombi show that for Ising models on $n$ nodes and interactions of strength $\Theta(1/n)$, an $\epsilon$ approximation to $\log Z_n / n$ can be achieved by sampling a randomly induced model on $2^{O(1/\epsilon^2)}$ nodes. We show that the sampling complexity of this problem is {\em polynomial in} $1/\epsilon$. We further show a polynomial dependence on $\epsilon$ cannot be avoided. Our results are very general as they apply to higher order Markov random fields. For Markov random fields of order $r$, we obtain an algorithm that achieves $\epsilon$ approximation using a number of samples polynomial in $r$ and $1/\epsilon$ and running time that is $2^{O(1/\epsilon^2)}$ up to polynomial factors in $r$ and $\epsilon$. For ferromagnetic Ising models, the running time is polynomial in $1/\epsilon$. Our results are intimately connected to recent research on the regularity lemma and property testing, where the interest is in finding which properties can tested within $\epsilon$ error in time polynomial in $1/\epsilon$. In particular, our proofs build on results from a recent work by Alon, de la Vega, Kannan and Karpinski, who also introduced the notion of polynomial vertex sample complexity. Another critical ingredient of the proof is an effective bound by the authors of the paper relating the variational free energy and the free energy.
A fast algorithm for identifying Friends-of-Friends halos

Abstract We describe a simple and fast algorithm for identifying friends-of-friends features and prove its correctness. The algorithm avoids unnecessary expensive neighbor queries, uses minimal memory overhead, and rejects slowdown in high over-density regions. We define our algorithm formally based on pair enumeration, a problem that has been heavily studied in fast 2-point correlation codes and our reference implementation employs a dual KD-tree correlation function code. We construct features in a hierarchical tree structure, and use a splay operation to reduce the average cost of identifying the root of a feature from O [ log L ] to O [ 1 ] ( L is the size of a feature) without additional memory costs. This reduces the overall time complexity of merging trees from O [ L log L ] to O [ L ] , reducing the number of operations per splay by orders of magnitude. We next introduce a pruning operation that skips merge operations between two fully self-connected KD-tree nodes. This improves the robustness of the algorithm, reducing the number of merge operations in high density peaks from O [ δ 2 ] to O [ δ ] . We show that for cosmological data set the algorithm eliminates more than half of merge operations for typically used linking lengths b ∼ 0 . 2 (relative to mean separation). Furthermore, our algorithm is extremely simple and easy to implement on top of an existing pair enumeration code, reusing the optimization effort that has been invested in fast correlation function codes.
Inferring Object Properties with a Tactile-Sensing Array Given Varying Joint Stiffness and Velocity

Whole-arm tactile sensing enables a robot to sense contact and infer contact properties across its entire arm. Within this paper, we demonstrate that using data-driven methods, a humanoid robot can infer mechanical properties of objects from contact with its forearm during a simple reaching motion. A key issue is the extent to which the performance of data-driven methods can generalize to robot actions that differ from those used during training. To investigate this, we developed an idealized physics-based lumped element model of a robot with a compliant joint making contact with an object. Using this physics-based model, we performed experiments with varied robot, object and environment parameters. We also collected data from a tactile-sensing forearm on a real robot as it made contact with various objects during a simple reaching motion with varied arm velocities and joint stiffnesses. The robot used 1-nearest-neighbor (1-NN) classifiers, hidden Markov models (HMMs), and long short-term memory (LSTM) ne...
Deep Texture Manifold for Ground Terrain Recognition

We present a texture network called Deep Encoding Pooling Network (DEP) for the task of ground terrain recognition. Recognition of ground terrain is an important task in establishing robot or vehicular control parameters, as well as for localization within an outdoor environment. The architecture of DEP integrates orderless texture details and local spatial information and the performance of DEP surpasses state-of-the-art methods for this task. The GTOS database (comprised of over 30,000 images of 40 classes of ground terrain in outdoor scenes) enables supervised recognition. For evaluation under realistic conditions, we use test images that are not from the existing GTOS dataset, but are instead from hand-held mobile phone videos of similar terrain. This new evaluation dataset, GTOS-mobile, consists of 81 videos of 31 classes of ground terrain such as grass, gravel, asphalt and sand. The resultant network shows excellent performance not only for GTOS-mobile, but also for more general databases (MINC and DTD). Leveraging the discriminant features learned from this network, we build a new texture manifold called DEP-manifold. We learn a parametric distribution in feature space in a fully supervised manner, which gives the distance relationship among classes and provides a means to implicitly represent ambiguous class boundaries. The source code and database are publicly available1.
Gromov-Witten Invariants of Symplectic Sums

The natural sum operation for symplectic manifolds is defined by gluing along codimension two submanifolds. Specifically, let X be a symplectic 2n-manifold with a symplectic (2n-2)-submanifold V. Given a similar pair (Y,W) with a symplectic identification V=W and a complex anti-linear isomorphism between the normal bundles of V and W, we can form the symplectic sum Z=X # Y. This note announces a general formula for computing the Gromov-Witten invariants of the sum Z in terms of relative Gromov-Witten invariants of (X,V) and (Y,W). Two applications are presented: a short derivation of the Caporaso-Harris formula [CH], and new proof that the rational enumerative invariants of the rational elliptic surface are given by the ``modular form'' (5.2).
On Functions Whose Mean Value Abscissas Are Midpoints, with Connections to Harmonic Functions

AbstractWe investigate functions with the property that for every interval, the slope at the midpoint of the interval is the same as the average slope. More generally, we find functions whose avera...
Trace asymptotics for fractional Schrödinger operators

This paper proves an analogue of a result of Banuelos and Sa Barreto [5] on the asymptotic expansion for the trace of Schrodinger operators on Rd when the Laplacian −Δ, which is the generator of the Brownian motion, is replaced by the non-local integral operator (−Δ)α/2, 0<α<2, which is the generator of the symmetric stable process of order α. These results also extend recent results of Banuelos and Yildirim [6] where the first two coefficients for (−Δ)α/2 are computed. Some extensions to Schrodinger operators arising from relativistic stable and mixed-stable processes are obtained.
Interactive Robot Transition Repair With SMT

Complex robot behaviors are often structured as state machines, where states encapsulate actions and a transition function switches between states. Since transitions depend on physical parameters, when the environment changes, a roboticist has to painstakingly readjust the parameters to work in the new environment. We present interactive SMT-based Robot Transition Repair (SRTR): instead of manually adjusting parameters, we ask the roboticist to identify a few instances where the robot is in a wrong state and what the right state should be. A lightweight automated analysis of the transition function's source code then 1) identifies adjustable parameters, 2) converts the transition function into a system of logical constraints, and 3) formulates the constraints and user-supplied corrections as MaxSMT problem that yields new parameter values. Our evaluation shows that SRTR is effective on real robots and in simulation. We show that SRTR finds new parameters 1) quickly, 2) with only a few corrections, and 3) that the parameters generalize to new scenarios. We also show that a simple state machine corrected by SRTR can out-perform a more complex, expert-tuned state machine in the real world.
Scaling and Performance of Simultaneously Heaving and Pitching Foils

The propulsive performance of an unsteady heaving and pitching foil is considered, and an extensive experimental parameter space of motion amplitudes, frequencies, and phase offsets between the hea...
Developing and analyzing boundary detection operators using probabilistic models

Most feature detectors such as edge detectors or circle finders are statistical, in the sense that they decide at each point in an image about the presence of a feature, this paper describes the use of Bayesian feature detectors.
Jacobi's triple product, mock theta functions, unimodal sequences and the $q$-bracket

In Ramanujan’s final letter to Hardy, he listed examples of a strange new class of infinite series he called “mock theta functions”. It turns out all of these examples are essentially specializatio...
Global Versus Localized Generative Adversarial Nets

In this paper, we present a novel localized Generative Adversarial Net (GAN) to learn on the manifold of real data. Compared with the classic GAN that globally parameterizes a manifold, the Localized GAN (LGAN) uses local coordinate charts to parameterize distinct local geometry of how data points can transform at different locations on the manifold. Specifically, around each point there exists a local generator that can produce data following diverse patterns of transformations on the manifold. The locality nature of LGAN enables local generators to adapt to and directly access the local geometry without need to invert the generator in a global GAN. Furthermore, it can prevent the manifold from being locally collapsed to a dimensionally deficient tangent subspace by imposing an orthonormality prior between tangents. This provides a geometric approach to alleviating mode collapse at least locally on the manifold by imposing independence between data transformations in different tangent directions. We will also demonstrate the LGAN can be applied to train a robust classifier that prefers locally consistent classification decisions on the manifold, and the resultant regularizer is closely related with the Laplace-Beltrami operator. Our experiments show that the proposed LGANs can not only produce diverse image transformations, but also deliver superior classification performances.
Characterizing complex particle morphologies through shape matching: Descriptors, applications, and algorithms

Many standard structural quantities, such as order parameters and correlation functions, exist for common condensed matter systems, such as spherical and rod-like particles. However, these structural quantities are often insufficient for characterizing the unique and highly complex structures often encountered in the emerging field of nano and microscale self-assembly, or other disciplines involving complex structures such as computational biology. Computer science algorithms known as ''shape matching'' methods pose a unique solution to this problem by providing robust metrics for quantifying the similarity between pairs of arbitrarily complex structures. This pairwise matching operation, either implicitly or explicitly, lies at the heart of most standard structural characterization schemes for particle systems. By substituting more robust ''shape descriptors'' into these schemes we extend their applicability to structures formed from more complex building blocks. Here, we describe several structural characterization schemes and shape descriptors that can be used to obtain various types of structural information about particle systems. We demonstrate the application of shape matching algorithms to a variety of example problems, for topics including local and global structure identification and classification, automated phase diagram mapping, and the construction of spatial and temporal correlation functions. The methods are applicable to a wide range of systems, both simulated and experimental, provided particle positions are known or can be accurately imaged.
The characteristic polynomial of an algebra and representations

We pose two new linear preserver problems. First, given a field k and a finite dimensional k-algebra B we show that the only linear maps ϕ:k×d→Bϕ:k×d→B which preserve the unit and the n -th roots of unity (for some n>2n>2 coprime to char(k)char(k)) are the algebra homomorphisms. Second, we consider linear maps ϕ:A→Bϕ:A→B between finite dimensional k-algebras which preserve the Cayley–Hamilton relations. We show that if preservation of the Cayley–Hamilton property is understood in a certain non-commutative sense, and A=k×dA=k×d, then the only such linear mappings are the algebra homomorphisms.
An explicit analysis of the entropic penalty in linear programming

Solving linear programs by using entropic penalization has recently attracted new interest in the optimization community, since this strategy forms the basis for the fastest-known algorithms for the optimal transport problem, with many applications in modern large-scale machine learning. Crucial to these applications has been an analysis of how quickly solutions to the penalized program approach true optima to the original linear program. More than 20 years ago, Cominetti and San Martin showed that this convergence is exponentially fast; however, their proof is asymptotic and does not give any indication of how accurately the entropic program approximates the original program for any particular choice of the penalization parameter. We close this long-standing gap in the literature regarding entropic penalization by giving a new proof of the exponential convergence, valid for any linear program. Our proof is non-asymptotic, yields explicit constants, and has the virtue of being extremely simple. We provide matching lower bounds and show that the entropic approach does not lead to a near-linear time approximation scheme for the linear assignment problem.
Prey cannibalism alters the dynamics of Holling–Tanner-type predator–prey models

Cannibalism, which is the act of killing and consumption of conspecifics, has been considered primarily in the predator, despite strong ecological evidence that it exists among prey. In the current manuscript, we investigate both the ODE and spatially explicit forms of a Holling–Tanner model, with ratio-dependent functional response, and show that cannibalism in the predator provides a stabilizing influence as expected. However, when cannibalism in the prey is considered, we show that it cannot stabilize the unstable interior equilibrium in the ODE case, in certain parameter regime, but can destabilize the stable interior equilibrium, leading to a stable limit cycle or “life boat” mechanism, for prey. We also show that prey cannibalism can lead to pattern forming Turing dynamics, which is an impossibility without it. The effects of a stochastic prey cannibalism rate are also considered.
Large Starspot Groups on HAT-P-11 in Activity Cycle 1

HAT-P-11 is a planet-hosting K4V star in the Kepler field, with an activity cycle that bear similarities to the Sun's. The chromospheric activity of HAT-P-11 indicates that a new activity cycle is beginning. We report ground-based observations with holographic diffuser photometry to measure the starspots of HAT-P-11 in its second observed magnetic activity cycle (Cycle 1). We find the area coverage of starspots within the transit chord for UTC 2017-10-30 is 14% --- which makes this transit the most spotted HAT-P-11 transit observed to date. We suggest that we are likely observing occultations of large spot groups appearing at the beginning of Cycle 1.
Improved Hardness for Cut, Interdiction, and Firefighter Problems

We study variants of the classic s-t cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC). * For Length-Bounded Cut and Shortest Path Interdiction, we show that both problems are hard to approximate within any constant factor, even if we allow bicriteria approximation. If we want to cut vertices or the graph is directed, our hardness ratio for Length-Bounded Cut matches the best approximation ratio up to a constant. Previously, the best hardness ratio was 1.1377 for Length-Bounded Cut and 2 for Shortest Path Interdiction. * For any constant k >= 2 and epsilon > 0, we show that Directed Multicut with k source-sink pairs is hard to approximate within a factor k - epsilon. This matches the trivial k-approximation algorithm. By a simple reduction, our result for k = 2 implies that Directed Multiway Cut with two terminals (also known as s-t Bicut} is hard to approximate within a factor 2 - epsilon, matching the trivial 2-approximation algorithm. * Assuming a variant of the UGC (implied by another variant of Bansal and Khot), we prove that it is hard to approximate Resource Minimization Fire Containment within any constant factor. Previously, the best hardness ratio was 2. For directed layered graphs with b layers, our hardness ratio Omega(log b) matches the best approximation algorithm. Our results are based on a general method of converting an integrality gap instance to a length-control dictatorship test for variants of the s-t cut problem, which may be useful for other problems.
A Unified Asymptotic Analysis of Area Spectral Efficiency in Ultradense Cellular Networks

This paper studies the asymptotic properties of average area spectral efficiency (ASE) of a downlink cellular network in the limit of very dense base station (BS) and user densities. This asymptotic analysis relies on three assumptions: 1) interference is treated as noise; 2) the BS locations are drawn from a Poisson point process; and 3) the path loss function is bounded above satisfying mild regularity conditions. We consider three possible definitions of the average ASE, all of which give units of bits per second per unit bandwidth per unit area. When there is no constraint on the minimum operational signal-to-interference-plus-noise ratio (SINR) and instantaneous full channel state information (CSI) is available at the transmitter, the average ASE is proven to saturate to a constant, which we derive in a closed form. For the other two ASE definitions, wherein either a minimum SINR is enforced or CSI is not available, the average ASE is instead shown to collapse to zero at high BS density. We provide several familiar case studies for the class of considered path loss models, and demonstrate that our results cover most previous models and results on ultradense networks as special cases.
Solving the Buyer and Seller’s Dilemma: A Dual-Deposit Escrow Smart Contract for Provably Cheat-Proof Delivery and Payment for a Digital Good without a Trusted Mediator

A fundamental problem for electronic commerce is the buying and selling of digital goods between individuals that may not know or trust each other. Traditionally, this problem has been addressed by the use of trusted third-parties such as credit-card companies, mediated escrows, legal adjudication, or reputation systems. Despite the rise of blockchain protocols as a way to send payments without trusted third parties, the important problem of exchanging a digital good for payment without trusted third parties has been paid much less attention. We refer to this problem as the Buyer and Seller’s Dilemma and present for it a dual-deposit escrow trade protocol which uses double-sided payment deposits in conjunction with simple cryptographic primitives, and that can be implemented using a blockchain-based smart contract. We analyze our protocol as an extensive-form game and prove that the Sub-game Perfect Nash Equilibrium for this game is for both the buyer and seller to cooperate and behave honestly. We address this problem under the assumption that the digital good being traded is known and verifiable, with a fixed price known to both parties.
PBW deformations of quadratic monomial algebras

A result of Braverman and Gaitsgory from 1996 gives necessary and sufficient conditions for a filtered algebra to be a Poincare-Birkhoff-Witt (PBW) deformation of a Koszul algebra. The main theorem...
A new event-driven Cooperative Receding Horizon controller for multi-agent systems in uncertain environments

In previous work, a Cooperative Receding Horizon (CRH) controller was developed for solving cooperative multi-agent problems in uncertain environments. In this paper, we overcome several limitations of this controller. We propose an event-driven CRH controller to solve the maximum reward collection problem (MRCP) where multiple agents cooperate to maximize the total reward collected from a set of stationary targets in a given mission space. Rewards are non-increasing functions of time and the environment is uncertain with new targets detected by agents at random time instants. The controller sequentially solves optimization problems over a planning horizon and executes the control for a shorter action horizon, where both are defined by certain events associated with new information becoming available. In contrast to the earlier CRH controller, we reduce the originally infinite-dimensional feasible control set to a finite set at each time step. We prove some properties of this new controller and include simulation results showing its improved performance.
A new time-dependent likelihood technique for detection of gamma-ray bursts with IACT arrays

In imaging atmospheric Cherenkov telescope (IACT) arrays, the standard method of statistically inferring the existence of a source is based on the maximum likelihood method of Li&Ma (1983). We present a new statistical approach, also based on maximum likelihood theory, which takes into account a priori knowledge of the source light curve. This approach is especially useful for observations of rapidly decaying gamma-ray bursts (GRBs). We also discuss results established by using this technique to analyze VERITAS GRB observations.
Milnor invariants of string links, trivalent trees, and configuration space integrals

Abstract We study configuration space integral formulas for Milnor's homotopy link invariants, showing that they are in correspondence with certain linear combinations of trivalent trees. Our proof is essentially a combinatorial analysis of a certain space of trivalent “homotopy link diagrams” which corresponds to all finite type homotopy link invariants via configuration space integrals. An important ingredient is the fact that configuration space integrals take the shuffle product of diagrams to the product of invariants. We ultimately deduce a partial recipe for writing explicit integral formulas for products of Milnor invariants from trivalent forests. We also obtain cohomology classes in spaces of link maps from the same data.
Spaces with polynomial hulls that contain no analytic discs

Extensions of the notions of polynomial and rational hull are introduced. Using these notions, a generalization of a result of Duval and Levenberg on polynomial hulls containing no analytic discs is presented. As a consequence it is shown that there exists a Cantor set in $${\mathbb {C}}^3$$ with a nontrivial polynomial hull that contains no analytic discs. Using this Cantor set, it is shown that there exist arcs and simple closed curves in $${\mathbb {C}}^4$$ with nontrivial polynomial hulls that contain no analytic discs. This answers a question raised by Bercovici in 2014 and can be regarded as a partial answer to a question raised by Wermer over 60 years ago. More generally, it is shown that every uncountable, compact subspace of a Euclidean space can be embedded as a subspace X of $${\mathbb {C}}^N$$ , for some N, in such a way as to have a nontrivial polynomial hull that contains no analytic discs. In the case when the topological dimension of the space is at most one, X can be chosen so as to have the stronger property that P(X) has a dense set of invertible elements.
Analysis of Student Behaviour in "Habitable" Worlds Using Continuous Representation Visualization.

We introduce a novel approach to visualizing temporal clickstream behaviour in the context of a degree-satisfying online course, Habitable Worlds, offered through Arizona State University. The current practice for visualizing behaviour within a digital learning environment is to generate plots based on hand-engineered or coded features using domain knowledge. While this approach has been effective in relating behaviour to known phenomena, features crafted from domain knowledge are not likely well suited to making unfamiliar phenomena salient and thus can preclude discovery. We introduce a methodology for organically surfacing behavioural regularities from clickstream data, conducting an expert in-the-loop hyperparameter search, and identifying anticipated as well as newly discovered patterns of behaviour. While these visualization techniques have been used before in the broader machine-learning community to better understand neural networks and relationships between word vectors, we apply them to online behavioural learner data and go a step further, exploring the impact of the parameters of the model on producing tangible, non-trivial observations of behaviour that suggest pedagogical improvement to the course designers and instructors. The methodology introduced in this paper led to an improved understanding of passing and non-passing student behaviour in the course and is applicable to other datasets of clickstream activity where investigators and stakeholders wish to organically surface principal patterns of behaviour.
Fast approximate computations with Cauchy matrices and polynomials

Multipoint polynomial evaluation and interpolation are fundamental for modern symbolic and numerical computing. The known algorithms solve both problems over any field of constants in nearly linear arithmetic time, but the cost grows to quadratic for numerical solution. We fix this discrepancy: our new numerical algorithms run in nearly linear arithmetic time. At first we restate our goals as the multiplication of an n-by-n Vandermonde matrix by a vector and the solution of a Vandermonde linear system of n equations. Then we transform the matrix into a Cauchy structured matrix with some special features. By exploiting them, we approximate the matrix by a generalized hierarchically semiseparable matrix, which is a structured matrix of a different class. Finally we accelerate our solution to the original problems by applying Fast Multipole Method to the latter matrix. Our resulting numerical algorithms run in nearly optimal arithmetic time when they perform the above fundamental computations with polynomials, Vandermonde matrices, transposed Vandermonde matrices, and a large class of Cauchy and Cauchy-like matrices. Some of our techniques may be of independent interest.
On the Impact of Various Types of Noise on Neural Machine Translation

We examine how various types of noise in the parallel training data impact the quality of neural machine translation systems. We create five types of artificial noise and analyze how they degrade performance in neural and statistical machine translation. We find that neural models are generally more harmed by noise than statistical models. For one especially egregious type of noise they learn to just copy the input sentence.
Using intermittent synchronization to compensate for rhythmic body motion during autonomous surgical cutting and debridement

Anatomical structures are rarely static during a surgical procedure due to breathing, heartbeats, and peristaltic movements. Inspired by observing an expert surgeon, we propose an intermittent synchronization with the extrema of the rhythmic motion (i.e., the lowest velocity windows). We performed 2 experiments: (1) pattern cutting and (2) debridement. In (1), we found that the intermittent synchronization approach, while 1.8× slower than tracking motion, is significantly more robust to noise and control latency, and it reduces the max cutting error by 2.6× except when motion is along 3 or more orthogonal axes. In (2), a baseline approach with no synchronization succeeds in 62% of debridement attempts while intermittent synchronization achieves an 80% success rate.
Off-diagonal hypergraph Ramsey numbers

The Ramsey number rk(s,n)rk(s,n) is the minimum N such that every red–blue coloring of the k -subsets of {1,…,N}{1,…,N} contains a red set of size s or a blue set of size n, where a set is red (blue) if all of its k -subsets are red (blue). Let rk(Ps,n)rk(Ps,n) be the minimum N such that every red–blue coloring of the k -subsets of {1,…,N}{1,…,N} results in a red ordered tight path with s vertices or a blue set of size n . The problem of estimating both rk(s,n)rk(s,n) and rk(Ps,n)rk(Ps,n) for k=2k=2 goes back to the seminal work of Erdős and Szekeres from 1935, while the case k≥3k≥3 was first investigated by Erdős and Rado in 1952. In this paper, we deduce the first quantitative relationship between multicolor variants of rk(Ps,n)rk(Ps,n) and rk(n,n)rk(n,n). This yields several consequences including the following: • We determine the correct tower growth rate for both rk(s,n)rk(s,n) and rk(Ps,n)rk(Ps,n) for s≥k+3s≥k+3. The question of determining the tower growth rate of rk(s,n)rk(s,n) for all s≥k+1s≥k+1 was posed by Erdős and Hajnal in 1972 and this is almost settled here. • We show that determining the tower growth rate of r4(P5,n)r4(P5,n) is equivalent to determining the tower growth rate of rk(n,n)rk(n,n) for all k≥3k≥3, which is a notorious conjecture of Erdős, Hajnal and Rado from 1965 that remains open.
Ricci flow on three-dimensional, unimodular metric Lie algebras

We give a global picture of the Ricci flow on the space of three-dimensional, unimodular, nonabelian metric Lie algebras considered up to isometry and scaling. The Ricci flow is viewed as a two-dimensional dynamical system for the evolution of structure constants of the metric Lie algebra with respect to an evolving orthonormal frame. This system is amenable to direct phase plane analysis, and we find that the fixed points and special trajectories in the phase plane correspond to special metric Lie algebras, including Ricci solitons and special Riemannian submersions. These results are one way to unify the study of Ricci flow on left invariant metrics on three-dimensional, simply-connected, unimodular Lie groups, which had previously been studied by a case-by-case analysis of the different Bianchi classes. In an appendix, we prove a characterization of the space of three-dimensional, unimodular, nonabelian metric Lie algebras modulo isometry and scaling.
A problem of Rankin on sets without geometric progressions

A geometric progression of length k and integer ratio is a set of numbers of the form {a, ar, . . . , ark−1} for some positive real number a and integer r ≥ 2. For each integer k ≥ 3, a greedy algorithm is used to construct a strictly decreasing sequence (ai) ∞ i=1 of positive real numbers with a1 = 1 such that the set G = ∞ ⋃ i=1 (a2i, a2i−1] contains no geometric progression of length k and integer ratio. Moreover, G(k) is a maximal subset of (0, 1] that contains no geometric progression of length k and integer ratio. It is also proved that there is a strictly increasing sequence (Ai) ∞ i=1 of positive integers with A1 = 1 such that ai = 1/Ai for all i = 1, 2, 3, . . .. The set G(k) gives a new lower bound for the maximum cardinality of a subset of the set of integers {1, 2, . . . , n} that contains no geometric progression of length k and integer ratio. 1. Real and integral geometric progressions Let R denote the real numbers. For t ∈ R, let R>t denote the set of all real numbers x > t. Let [x] denote the integer part of the real number x. For real numbers u 0 with u 0 is the set q ∗X = {qx : x ∈ X}. The reciprocal of the set X is the set X = { x : x ∈ X } . For example, q ∗ (u, v] = (qu, qv] and (1/v, 1/u] = [u, v). If A = (a0, a1, . . . , ak−1) is a finite sequence of positive real numbers, then the dilation of the sequence A by q is the sequence q ∗ A = (qa0, qa1, . . . , qak−1) and the reciprocal of A is the sequence A = (1/a0, 1/a1, . . . , 1/ak−1). Let N denote the set of positive integers, and let N = N \ {1} denote the set of all integers r > 1. Let k ∈ N and let r, a ∈ R>0. A geometric progression of length k and ratio r with first term a is a sequence of the form (a, ar, ar, . . . , ar) = a ∗ (1, r, r, . . . , r). Date: August 14, 2014. 2010 Mathematics Subject Classification. 11B05 11B25, 11B75, 11B83, 05D10.
Recovery guarantee of weighted low-rank approximation via alternating minimization

Many applications require recovering a ground truth low-rank matrix from noisy observations of the entries, which in practice is typically formulated as a weighted low-rank approximation problem and solved by non-convex optimization heuristics such as alternating minimization. In this paper, we provide provable recovery guarantee of weighted low-rank via a simple alternating minimization algorithm. In particular, for a natural class of matrices and weights and without any assumption on the noise, we bound the spectral norm of the difference between the recovered matrix and the ground truth, by the spectral norm of the weighted noise plus an additive error term that decreases exponentially with the number of rounds of alternating minimization, from either initialization by SVD or, more importantly, random initialization. These provide the first theoretical results for weighted low-rank approximation via alternating minimization with nonbinary deterministic weights, significantly generalizing those for matrix completion, the special case with binary weights, since our assumptions are similar or weaker than those made in existing works. Furthermore, this is achieved by a very simple algorithm that improves the vanilla alternating minimization with a simple clipping step.
Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow

We revisit the inductive matrix completion problem that aims to recover a rank-$r$ matrix with ambient dimension $d$ given $n$ features as the side prior information. The goal is to make use of the known $n$ features to reduce sample and computational complexities. We present and analyze a new gradient-based non-convex optimization algorithm that converges to the true underlying matrix at a linear rate with sample complexity only linearly depending on $n$ and logarithmically depending on $d$. To the best of our knowledge, all previous algorithms either have a quadratic dependency on the number of features in sample complexity or a sub-linear computational convergence rate. In addition, we provide experiments on both synthetic and real world data to demonstrate the effectiveness of our proposed algorithm.
A simple rule for the evolution of fast dispersal at the edge of expanding populations

Evolution by natural selection is commonly perceived as a process that favors those that replicate faster to leave more offspring; nature, however, seem to abound with examples where organisms forgo some replicative potential to disperse faster. When does selection favor invasion of the fastest? Motivated by evolution experiments with swarming bacteria we searched for a simple rule. In experiments, a fast hyperswarmer mutant that pays a reproductive cost to make many copies of its flagellum invades a population of mono-flagellated bacteria by reaching the expanding population edge; a two-species mathematical model explains that invasion of the edge occurs only if the invasive species' expansion rate, v_2, which results from the combination of the species growth rate and its dispersal speed (but not its carrying capacity), exceeds the established species', v_1. The simple rule that we derive, v_2>v_1, appears to be general: less favorable initial conditions, such as smaller initial sizes and longer distances to the population edge, delay but do not entirely prevent invasion. Despite intricacies of the swarming system, experimental tests agree well with model predictions suggesting that the general theory should apply to other expanding populations with trade-offs between growth and dispersal, including non-native invasive species and cancer metastases.
Towards secure and safe appified automated vehicles

The advancement in Autonomous Vehicles (AVs) has created an enormous market for the development of self-driving functionalities, raising the question of how it will transform the traditional vehicle development process. One adventurous proposal is to open the AV platform to third-party developers, so that AV functionalities can be developed in a crowd-sourcing way, which could provide tangible benefits to both automakers and end users. Some pioneering companies in the automotive industry have made the move to open the platform so that developers are allowed to test their code on the road. Such openness, however, brings serious security and safety issues by allowing untrusted code to run on the vehicle. In this paper, we introduce the concept of an Appified AV platform that opens the development framework to third-party developers. To further address the safety challenges, we propose an enhanced appified AV design schema called AVGUARD, which focuses primarily on mitigating the threats brought about by untrusted code, leveraging theory in the vehicle evaluation field, and conducting program analysis techniques in the cyber security area. Our study provides guidelines and suggested practice for the future design of open AV platforms.
Small perturbation solutions for nonlocal elliptic equations

ABSTRACTWe present a small perturbation result for nonlocal elliptic equations, which says that for a class of nonlocal operators, the solutions are in Cσ+α for any α∈(0,1) as long as the solutions are small. This is a nonlocal generalization of a celebrated result of Savin in the case of second order equations.
Convergence of Siegel–Veech constants

We show that for any weakly convergent sequence of ergodic \(SL_2(\mathbb {R})\)-invariant probability measures on a stratum of unit-area translation surfaces, the corresponding Siegel–Veech constants converge to the Siegel–Veech constant of the limit measure. Together with a measure equidistribution result due to Eskin–Mirzakhani–Mohammadi, this yields the (previously conjectured) convergence of sequences of Siegel–Veech constants associated to Teichmuller curves in genus two. The proof uses a recurrence result closely related to techniques developed by Eskin–Masur. We also use this recurrence result to get an asymptotic quadratic upper bound, with a uniform constant depending only on the stratum, for the number of saddle connections of length at most R on a unit-area translation surface.
Equations and syzygies of the first secant variety to a smooth curve

We show that if C is a linearly normal smooth curve embedded by a line bundle of degree at least 2g + 3 + p then the secant variety to the curve satises N3;p.
On the linearity defect of the residue field

Abstract Given a commutative Noetherian local ring R, the linearity defect of a finitely generated R-module M, denoted ld R ( M ) , is an invariant that measures how far M and its syzygies are from having a linear resolution. Motivated by a positive known answer in the graded case, we study the question of whether ld R ( k ) ∞ implies ld R ( k ) = 0 . We give answers in special cases, and we discuss several interpretations and refinements of the question.
Recent Progress and Next Directions for Embedded MRAM Technology

MRAM can play a variety of on-chip memory roles in advanced VLSI technology spanning from high retention, solder-reflow-capable non-volatile memory (NVM) to dense non-volatile or high retention working RAMs. This paper describes results for a solder-reflow-capable MRAM NVM and for extensions that trade off high retention against speed, power, and density.
Balanced ranking with diversity constraints

Many set selection and ranking algorithms have recently been enhanced with diversity constraints that aim to explicitly increase representation of historically disadvantaged populations, or to improve the overall representativeness of the selected set. An unintended consequence of these constraints, however, is reduced in-group fairness: the selected candidates from a given group may not be the best ones, and this unfairness may not be well-balanced across groups. In this paper we study this phenomenon using datasets that comprise multiple sensitive attributes. We then introduce additional constraints, aimed at balancing the in-group fairness across groups, and formalize the induced optimization problems as integer linear programs. Using these programs, we conduct an experimental evaluation with real datasets, and quantify the feasible trade-offs between balance and overall performance in the presence of diversity constraints.
Medical Time Series Classification with Hierarchical Attention-based Temporal Convolutional Networks: A Case Study of Myotonic Dystrophy Diagnosis

Myotonia, which refers to delayed muscle relaxation after contraction, is the main symptom of myotonic dystrophy patients. We propose a hierarchical attention-based temporal convolutional network (HA-TCN) for myotonic dystrohpy diagnosis from handgrip time series data, and introduce mechanisms that enable model explainability. We compare the performance of the HA-TCN model against that of benchmark TCN models, LSTM models with and without attention mechanisms, and SVM approaches with handcrafted features. In terms of classification accuracy and F1 score, we found all deep learning models have similar levels of performance, and they all outperform SVM. Further, the HA-TCN model outperforms its TCN counterpart with regards to computational efficiency regardless of network depth, and in terms of performance particularly when the number of hidden layers is small. Lastly, HA-TCN models can consistently identify relevant time series segments in the relaxation phase of the handgrip time series, and exhibit increased robustness to noise when compared to attention-based LSTM models.
Responses to Liability Immunization: Evidence from Medical Devices

The Supreme Court's decision in Riegel v. Medtronic unexpectedly and immediately immunized medical device manufacturers from certain types of state tort liability. Riegel immunized manufacturers from liability if their devices had been approved through the Food and Drug Administration's most rigorous|and costly|review process, premarket approval ("PMA"). Exploiting this unanticipated decision, we examine whether manufacturers strategically respond to this new immunity. We find evidence that, following the Riegel decision, device manufacturers file more PMA applications for high risk product categories (relative to the comparable change for low risk categories), suggesting that firms are sensitive to the newly immunized risk. We additionally find evidence that physician treatment patterns with respect to medical devices also change, consistent with Riegel shifting liability away from device manufacturers and towards physicians. The analysis provides evidence that sophisticated actors respond to changes in their expected legal liability and that technical legal decisions have important ramifications for the provision of health care.
Public-Key Cryptography in the Fine-Grained Setting

Cryptography is largely based on unproven assumptions, which, while believable, might fail. Notably if \(P = NP\), or if we live in Pessiland, then all current cryptographic assumptions will be broken. A compelling question is if any interesting cryptography might exist in Pessiland.
Large Particle Fluorescence-Activated Cell Sorting Enables High-Quality Single-Cell RNA Sequencing and Functional Analysis of Adult Cardiomyocytes.

ABSTRACT Rationale Single cell RNA sequencing (scRNA-seq) has emerged as a powerful tool to profile the transcriptome at single cell resolution, enabling comprehensive analysis of cellular trajectories and heterogeneity during development and disease. However, the use of scRNA-seq remains limited in cardiac pathology owing to technical difficulties associated with the isolation of single adult cardiomyocytes (CMs). Objective We investigated the capability of large-particle fluorescence-activated cell sorting (LP-FACS) for isolation of viable single adult CMs. Methods and Results We found that LP-FACS readily outperforms conventional FACS for isolation of struturally competent CMs, including large CMs. Additionally, LP-FACS enables isolation of fluorescent CMs from mosaic models. Importantly, the sorted CMs allow generation of high-quality scRNA-seq libraries. Unlike CMs isolated via previously utilized fluidic or manual methods, LP-FAC-isolated CMs generate libraries exhibiting normal levels of mitochondrial transcripts. Moreover, LP-FACS isolated CMs remain functionally competent and can be studied for contractile properties. Conclusions Our study enables high quality dissection of adult CM biology at single-cell resolution.
Extended Integrated Interleaved Codes Over Any Field With Applications to Locally Recoverable Codes

Integrated Interleaved (II) and Extended Integrated Interleaved (EII) codes are a versatile alternative for Locally Recoverable (LRC) codes, since they require fields of relatively small size. II and EII codes are generally defined over Reed-Solomon type of codes. A new comprehensive definition of EII codes is presented, allowing for EII codes over any field, and in particular, over the binary field $GF(2)$ . The traditional definition of II and EII codes is shown to be a special case of the new definition. Improvements over previous constructions of LRC codes, in particular, for binary codes, are given, as well as cases meeting an upper bound on the minimum distance. Properties of the codes are presented as well, in particular, an iterative decoding algorithm on rows and columns generalizing the iterative decoding algorithm of product codes. Two applications are also discussed: one is finding a systematic encoding of EII codes such that the parity symbols have a balanced distribution on rows, and the other is the problem of ordering the symbols of an EII code such that the maximum length of a correctable burst is achieved.
Layered Embeddings for Amodal Instance Segmentation

The proposed method extends upon the representational output of semantic instance segmentation by explicitly including both visible and occluded parts. A fully convolutional network is trained to produce consistent pixel-level embedding across two layers such that, when clustered, the results convey the full spatial extent and depth ordering of each instance. Results demonstrate that the network can accurately estimate complete masks in the presence of occlusion and outperform leading top-down bounding-box approaches. Source code available at https://github.com/yanfengliu/layered_embeddings.