cssi/SciSciGPT-SciSciNet huggingface dataset:
Preperiodic points for quadratic polynomials with small cycles over quadratic fields

Given a number field K and a polynomial $$f(z) \in K[z]$$ , one can naturally construct a finite directed graph G(f, K) whose vertices are the K-rational preperiodic points of f, with an edge $$\alpha \rightarrow \beta $$ if and only if $$f(\alpha ) = \beta $$ . The dynamical uniform boundedness conjecture of Morton and Silverman suggests that, for fixed integers $$n \ge 1$$ and $$d \ge 2$$ , there are only finitely many isomorphism classes of directed graphs G(f, K) as one ranges over all number fields K of degree n and polynomials $$f(z) \in K[z]$$ of degree d. In the case $$(n,d) = (1,2)$$ , Poonen has given a complete classification of all directed graphs which may be realized as $$G(f,\mathbb {Q})$$ for some quadratic polynomial $$f(z) \in \mathbb {Q}[z]$$ , under the assumption that f does not admit rational points of large period. The purpose of the present article is to continue the work begun by the author, Faber, and Krumm on the case $$(n,d) = (2,2)$$ . By combining the results of the previous article with a number of new results, we arrive at a partial result toward a theorem like Poonen’s—with a similar assumption on points of large period—but over all quadratic extensions of $$\mathbb {Q}$$ .
Distributed Simultaneous Action and Target Assignment for Multi-Robot Multi-Target Tracking

We study two multi-robot assignment problems for multi-target tracking. We consider distributed approaches in order to deal with limited sensing and communication ranges. We seek to simultaneously assign trajectories and targets to the robots. Our focus is on local algorithms that achieve performance close to the optimal algorithms with limited communication. We show how to use a local algorithm that guarantees a bounded approximate solution within $\mathcal{O}(h\log 1/\epsilon)$ communication rounds. We compare with a greedy approach that achieves a 2-approximation in as many rounds as the number of robots. Simulation results show that the local algorithm is an effective solution to the assignment problem.
Coverage and rate analysis of super Wi-Fi networks using stochastic geometry

Recent regulatory changes proposed by the Federal Communications Commission (FCC) permitting unlicensed use of television white space (TVWS) channels present new opportunities for designing wireless networks that make efficient use of this spectrum. The favorable propagation characteristics of these channels and their widespread availability, especially in rural areas, make them well-suited for providing broadband services in sparsely populated regions where economic factors hinder deployment of such services on licensed spectrum. In this context, this paper explores the deployment of an outdoor Wi-Fi-like network operating in TVWS channels, referred to commonly as a Super Wi-Fi network. Since regulations governing unlicensed use of these channels allow (a) mounting fixed devices up to a height of 30 m and operation at transmit powers of up to 4 W EIRP, and (b) operation at transmit powers of up to 100 mW EIRP for portable devices, such networks can provide extended coverage and higher rates than traditional Wi-Fi networks. However, these gains are subject to the viability of the uplink from the portable devices (clients) to the fixed devices (access points (AP)) because of tighter restrictions on transmit power of clients compared to APs. This paper leverages concepts from stochastic geometry to study the performance of such networks with specific focus on the effect of (a) transmit power asymmetry between APs and clients and its impact on uplink viability and coverage, and (b) the interplay between height and transmit power of APs in determining the network throughput. Such an analysis reveals that (a) maximum coverage of no more than 700 m is obtained even when APs are deployed at 30 m height, and (b) operating APs at transmit power of more than 1 W is beneficial only at sparse deployment densities when rate is prioritized over coverage.
Capacity and Rate Regions of a Class of Broadcast Interference Channels

In this paper, a class of broadcast interference channels (BIC) is investigated, where one of the two broadcast receivers is subject to interference coming from a point-to-point transmission. For a general discrete memoryless broadcast interference channel (DM-BIC), an achievable scheme based on message splitting, superposition, and binning is proposed and a concise representation of the corresponding achievable rate region $\mathcal {R}$ is obtained. Two partial-order broadcast conditions interference-oblivious less noisy and interference-cognizant less noisy are defined, thereby extending the usual less noisy condition for a regular broadcast channel by taking interference into account. Under these conditions, a reduced form of $\mathcal {R}$ is shown to be equivalent to a rate region based on a simpler scheme, where the broadcast transmitter uses only superposition. Furthermore, if interference is strong for the interference-oblivious less noisy DM-BIC, the capacity region is given by the aforementioned two equivalent rate regions. For the interference-cognizant less noisy DM-BIC, it is argued that the strong but not very strong interference condition does not exist, and in this case, the capacity region for the very strong interference is obtained. For a Gaussian broadcast interference channel, channel parameters are categorized into three regimes. For the first two regimes, which are closely related to the two partial-order broadcast conditions, achievable rate regions are derived by specializing the corresponding achievable schemes of DM-BICs with Gaussian input distributions. The entropy power inequality-based outer bounds are obtained by combining bounding techniques for a Gaussian broadcast channel and a Gaussian interference channel. These inner and outer bounds lead to either exact or approximate characterizations of capacity regions and sum capacity under various conditions. For the remaining complementing regime, inner and outer bounds are also provided.
Phylotastic: An Experiment in Creating, Manipulating, and Evolving Phylogenetic Biology Workflows Using Logic Programming

Evolutionary Biologists have long struggled with the challenge of developing analysis workflows in a flexible manner, thus facilitating the reuse of phylogenetic knowledge. An evolutionary biology workflow can be viewed as a plan which composes web services that can retrieve, manipulate, and produce phylogenetic trees. The Phylotastic project was launched two years ago as a collaboration between evolutionary biologists and computer scientists, with the goal of developing an open architecture to facilitate the creation of such analysis workflows. While composition of web services is a problem that has been extensively explored in the literature, including within the logic programming domain, the incarnation of the problem in Phylotastic provides a number of additional challenges. Along with the need to integrate preferences and formal ontologies in the description of the desired workflow, evolutionary biologists tend to construct workflows in an incremental manner, by successively refining the workflow, by indicating desired changes (e.g., exclusion of certain services, modifications of the desired output). This leads to the need of successive iterations of incremental replanning, to develop a new workflow that integrates the requested changes while minimizing the changes to the original workflow. This paper illustrates how Phylotastic has addressed the challenges of creating and refining phylogenetic analysis workflows using logic programming technology and how such solutions have been used within the general framework of the Phylotastic project.
Forward table-based presynaptic event-triggered spike-timing-dependent plasticity

Spike-timing-dependent plasticity (STDP) incurs both causal and acausal synaptic weight updates, for negative and positive time differences between pre-synaptic and postsynaptic spike events. For realizing such updates in neuromorphic hardware, current implementations either require forward and reverse lookup access to the synaptic connectivity table, or rely on memory-intensive architectures such as crossbar arrays. We present a novel method for realizing both causal and acausal weight updates using only forward lookup access of the synaptic connectivity table, permitting memory-efficient implementation. A simplified implementation in FPGA, using a single timer variable for each neuron, closely approximates exact STDP cumulative weight updates, and reduces to exact STDP for refractory periods greater than the STDP time window. Compared to conventional crossbar implementation, the forward table-based implementation using run-length encoding leads to substantial memory savings for sparsely connected networks supporting scalable neuromorphic systems with fully reconfigurable synaptic connectivity and plasticity.
Effects of Sidewalls and Leading-Edge Blowing on Flows over Long Rectangular Cavities

The present work investigates sidewall effects on the characteristics of three-dimensional (3-D) compressible flows over a rectangular cavity with aspect ratios of L/D=6 and W/D=2 at ReD=104 using ...
Model predictive load scheduling using solar power forecasting

In this paper a model is developed to solve the on/off scheduling of (non-linear) dynamic electric loads based on predictions of the power delivery of a (standalone) solar power source. Knowledge of variations in the solar power output is used to optimally select the timing and the combinations of a set of given electric loads, where each load has a desired dynamic power profile. The optimization exploits the desired power profiles of the electric loads in terms of dynamic power ramp up/down and minimum time on/off of each load to track a finite number of load switching combinations over a moving finite prediction horizon. Subsequently, a user-specified optimization function with possible power constraints is evaluated over the finite number of combinations to allow for real-time computation of the optimal timing and switching of loads. A case study for scheduling electric on/off loads with switching dynamics and solar forecast data at UC San Diego is carried out.
Higher order multipoint flux mixed finite element methods on quadrilaterals and hexahedra

We develop higher order multipoint flux mixed finite element (MFMFE) methods for solving elliptic problems on quadrilateral and hexahedral grids that reduce to cell-based pressure systems. The meth...
Threshold-based obfuscated keys with quantifiable security against invasive readout

Advances in reverse engineering make it challenging to deploy any on-chip information in a way that is hidden from a determined attacker. A variety of techniques have been proposed for design obfuscation including look-alike cells in which functionality is determined by hard to observe mechanisms including dummy vias or transistor threshold voltages. Threshold-based obfuscation is especially promising because threshold voltages cannot be observed optically and require more sophisticated measurements by the attacker. In this work, we demonstrate the effectiveness of a methodology that applies threshold-defined behavior to memory cells, in combination with error correcting codes to achieve a high degree of protection against invasive reverse engineering. The combination of error correction and small threshold manipulations is significant because it makes the attacker's job harder without compromising the reliability of the obfuscated key. We present analysis to quantify key reliability of our approach, and its resistance to reverse engineering attacks that seek to extract the key through imperfect measurement of transistor threshold voltages. The security analysis and cost metrics we provide allow designers to make a quantifiable tradeoff between cost and security. We find that the combination of small threshold offsets and stronger error correcting codes are advantageous when security is the primary objective.
Sequential Ensemble Learning for Outlier Detection: A Bias-Variance Perspective

Ensemble methods for classification have been effectively used for decades, while for outlier detection it has only been studied recently. In this work, we design a new ensemble approach for outlier detection in multi-dimensional point data, which provides improved accuracy by reducing error through both bias and variance by considering outlier detection as a binary classification task with unobserved labels. In this paper, we propose a sequential ensemble approach called CARE that employs a two-phase aggregation of the intermediate results in each iteration to reach the final outcome. Unlike existing outlier ensembles, our ensemble incorporates both the parallel and sequential building blocks to reduce bias as well as variance by (i) successively eliminating outliers from the original dataset to build a better data model on which outlierness is estimated (sequentially), and (ii) combining the results from individual base detectors and across iterations (parallelly). Through extensive experiments on 16 real-world datasets mainly from the UCI machine learning repository [1], we show that CARE performs significantly better than or at least similar to the individual baselines as well as the existing state-of-the-art outlier ensembles.
Torus equivariant D-modules and hypergeometric systems

Abstract We formalize, at the level of D-modules, the notion that A-hypergeometric systems are equivariant versions of the classical hypergeometric equations. For this purpose, we construct a functor Π B A ˜ on a suitable category of torus equivariant D-modules and show that it preserves key properties, such as holonomicity, regularity, and reducibility of monodromy representation. We also examine its effect on solutions, characteristic varieties, and singular loci. By applying Π B A ˜ to suitable binomial D-modules, we shed new light on the D-module theoretic properties of systems of classical hypergeometric differential equations.
Confederated modular differential equation APIs for accelerated algorithm development and benchmarking

Abstract Performant numerical solving of differential equations is required for large-scale scientific modeling. In this manuscript we focus on two questions: (1) how can researchers empirically verify theoretical advances and consistently compare methods in production software settings and (2) how can users (scientific domain experts) keep up with the state-of-the-art methods to select those which are most appropriate? Here we describe how the confederated modular API of DifferentialEquations.jl addresses these concerns. We detail the package-free API which allows numerical methods researchers to readily utilize and benchmark any compatible method directly in full-scale scientific applications. In addition, we describe how the complexity of the method choices is abstracted via a polyalgorithm. We show how scientific tooling built on top of DifferentialEquations.jl, such as packages for dynamical systems quantification and quantum optics simulation, both benefit from this structure and provide themselves as convenient benchmarking tools.
Unifying count-based exploration and intrinsic motivation

We consider an agent's uncertainty about its environment and the problem of generalizing this uncertainty across states. Specifically, we focus on the problem of exploration in non-tabular reinforcement learning. Drawing inspiration from the intrinsic motivation literature, we use density models to measure uncertainty, and propose a novel algorithm for deriving a pseudo-count from an arbitrary density model. This technique enables us to generalize count-based exploration algorithms to the non-tabular case. We apply our ideas to Atari 2600 games, providing sensible pseudo-counts from raw pixels. We transform these pseudo-counts into exploration bonuses and obtain significantly improved exploration in a number of hard games, including the infamously difficult MONTEZUMA'S REVENGE.
Deriving Neural Architectures from Sequence and Graph Kernels

The design of neural architectures for structured objects is typically guided by experimental insights rather than a formal process. In this work, we appeal to kernels over combinatorial structures, such as sequences and graphs, to derive appropriate neural operations. We introduce a class of deep recurrent neural operations and formally characterize their associated kernel spaces. Our recurrent modules compare the input to virtual reference objects (cf. filters in CNN) via the kernels. Similar to traditional neural operations, these reference objects are parameterized and directly optimized in end-to-end training. We empirically evaluate the proposed class of neural architectures on standard applications such as language modeling and molecular graph regression, achieving state-of-the-art results across these applications.
UNCERTAINTY QUANTIFICATION FOR MOLECULAR DYNAMICS

The goals of this chapter are twofold. First, we wish to introduce molecular dynamics (MD) and uncertainty quantification (UQ) in a common setting in order to demonstrate how the latter can increase confidence in the former. In some cases, this discussion culminates in our providing practical, mathematical tools that can be used to answer the question, "is this simulation reliable?" However, many questions remain unanswered. Thus, a second goal of this work is to highlight open problems where progress would aid the larger community.
On the problem of classifying simple compact quantum groups

We review the notion of simple compact quantum groups and examples, and discuss the problem of construction and classification of simple compact quantum groups. Several new quantum groups constructed by Banica, Curran and Speicher since the author's first paper on simple quantum groups are shown to be simple using results of Raum and Weber.
Abrahamse's interpolation theorem and Fuchsian groups

Abstract We generalize Abrahamse's interpolation theorem from the setting of a multiply connected domain to that of a more general Riemann surface. Our main result provides the scalar-valued interpolation theorem for the fixed-point subalgebra of H ∞ associated to the action of a Fuchsian group. We rely on two results from a paper of Forelli. This allows us to prove the interpolation result using duality techniques that parallel Sarason's approach to the interpolation problem for H ∞ [Donald Sarason, Generalized interpolation in H ∞ , Trans. Amer. Math. Soc. 127 (1967) 179–203, MR0208383. [26] ]. In this process we prove a more general distance formula, very much like Nehari's theorem, and obtain relations between the kernel function for the character automorphic Hardy spaces and the Szego kernel for the disk. Finally, we examine our interpolation results in the context of the two simplest examples of Fuchsian groups acting on the disk.
Amorphous Intergranular Films Enable the Creation of Bulk Nanocrystalline Cu‐Zr with Full Density

Nanocrystalline metal alloys show great potential as structural materials, but are often only available in small volumes such as thin films or powders. However, recent research has suggested that dopant segregation and grain boundary structural transitions between states known as complexions can dramatically alter grain size stability and potentially enable activated sintering. In this study, we explore strategic consolidation routes for mechanically alloyed Cu-4 at.% Zr powders to capture the effects of amorphous complexion formation on the densification of bulk nanostructured metals. We observed an increase in density of the consolidated samples which coincides with the formation of amorphous intergranular films. At the same time, the grain size is reasonably stable after exposure to these temperatures. As a result, we are able to produce a bulk nano-grained metal with a grain size of 57 nm and a density of 99.8%, which shows an impressive balance of small grain size and high density using simple consolidation techniques.
Unseparated pairs and fixed points in random permutations

Abstract In a uniform random permutation Π of [ n ] : = { 1 , 2 , … , n } , the set of elements k ∈ [ n − 1 ] such that Π ( k + 1 ) = Π ( k ) + 1 has the same distribution as the set of fixed points of Π that lie in [ n − 1 ] . We give three different proofs of this fact using, respectively, an enumeration relying on the inclusion–exclusion principle, the introduction of two different Markov chains to generate uniform random permutations, and the construction of a combinatorial bijection. We also obtain the distribution of the analogous set for circular permutations that consists of those k ∈ [ n ] such that Π ( k + 1 mod n ) = Π ( k ) + 1 mod n . This latter random set is just the set of fixed points of the commutator [ ρ , Π ] , where ρ is the n -cycle ( 1 , 2 , … , n ) . We show for a general permutation η that, under weak conditions on the number of fixed points and 2-cycles of η , the total variation distance between the distribution of the number of fixed points of [ η , Π ] and a Poisson distribution with expected value 1 is small when n is large.
Dynamic Watermarking: Active Defense of Networked Cyber–Physical Systems

The coming decades may see the large scale deployment of networked cyber–physical systems to address global needs in areas such as energy, water, health care, and transportation. However, as recent events have shown, such systems are vulnerable to cyber attacks. Being safety critical, their disruption or misbehavior can cause economic losses or injuries and loss of life. It is therefore important to secure such networked cyber–physical systems against attacks. In the absence of credible security guarantees, there will be resistance to the proliferation of cyber–physical systems, which are much needed to meet global needs in critical infrastructures and services. This paper addresses the problem of secure control of networked cyber–physical systems. This problem is different from the problem of securing the communication network, since cyber–physical systems at their very essence need sensors and actuators that interface with the physical plant, and malicious agents may tamper with sensors or actuators, as recent attacks have shown. We consider physical plants that are being controlled by multiple actuators and sensors communicating over a network, where some sensors could be “malicious,” meaning that they may not report the measurements that they observe. We address a general technique by which the actuators can detect the actions of malicious sensors in the system and disable closed-loop control based on their information. This technique, called “watermarking,” employs the technique of actuators injecting private excitation into the system, which will reveal malicious tampering with signals. We show how such an active defense can be used to secure networked systems of sensors and actuators.
Stochastic Gradient MCMC with Stale Gradients

Stochastic gradient MCMC (SG-MCMC) has played an important role in large-scale Bayesian learning, with well-developed theoretical convergence properties. In such applications of SG-MCMC, it is becoming increasingly popular to employ distributed systems, where stochastic gradients are computed based on some outdated parameters, yielding what are termed stale gradients. While stale gradients could be directly used in SG-MCMC, their impact on convergence properties has not been well studied. In this paper we develop theory to show that while the bias and MSE of an SG-MCMC algorithm depend on the staleness of stochastic gradients, its estimation variance (relative to the expected estimate, based on a prescribed number of samples) is independent of it. In a simple Bayesian distributed system with SG-MCMC, where stale gradients are computed asynchronously by a set of workers, our theory indicates a linear speedup on the decrease of estimation variance w.r.t. the number of workers. Experiments on synthetic data and deep neural networks validate our theory, demonstrating the effectiveness and scalability of SG-MCMC with stale gradients.
Scaling limits of the Schelling model

The Schelling model of segregation, introduced by Schelling in 1969 as a model for residential segregation in cities, describes how populations of multiple types self-organize to form homogeneous clusters of one type. In this model, vertices in an N-dimensional lattice are initially assigned types randomly. As time evolves, the type at a vertex v has a tendency to be replaced with the most common type within distance w of v. We present the first mathematical description of the dynamical scaling limit of this model as w tends to infinity and the lattice is correspondingly rescaled. We do this by deriving an integro-differential equation for the limiting Schelling dynamics and proving almost sure existence and uniqueness of the solutions when the initial conditions are described by white noise. The evolving fields are in some sense very “rough” but we are able to make rigorous sense of the evolution. In a key lemma, we show that for certain Gaussian fields h, the supremum of the occupation density of $$h-\phi $$ at zero (taken over all 1-Lipschitz functions $$\phi $$) is almost surely finite, thereby extending a result of Bass and Burdzy. In the one dimensional case, we also describe the scaling limit of the limiting clusters obtained at time infinity, thereby resolving a conjecture of Brandt, Immorlica, Kamath, and Kleinberg.
Lifting representations of finite reductive groups I: semisimple conjugacy classes

Suppose that is a connected reductive group defined over a field , and is a finite group acting via -automorphisms of satisfying a certain quasi-semisimplicity condition. Then the identity component of the group of -fixed points in is reductive. We axiomatize the main features of the relationship between this fixed-point group and the pair , and consider any group satisfying the axioms. If both and are -quasisplit, then we can consider their duals and . We show the existence of and give an explicit formula for a natural map from the set of semisimple stable conjugacy classes in to the analogous set for . If is finite, then our groups are automatically quasisplit, and our result specializes to give a map of semisimple conjugacy classes. Since such classes parametrize packets of irreducible representations of and , one obtains a mapping of such packets.
Minimal reversible nonsymmetric rings

Abstract Marks showed that F 2 Q 8 , the F 2 group algebra over the quaternion group, is a reversible nonsymmetric ring, then questioned whether or not this ring is minimal with respect to cardinality. In this work, it is shown that the cardinality of a minimal reversible nonsymmetric ring is indeed 256. Furthermore, it is shown that although F 2 Q 8 is a duo ring, there are also examples of minimal reversible nonsymmetric rings which are nonduo.
Bayesian Policy Optimization for Model Uncertainty

Addressing uncertainty is critical for autonomous systems to robustly adapt to the real world. We formulate the problem of model uncertainty as a continuous Bayes-Adaptive Markov Decision Process (BAMDP), where an agent maintains a posterior distribution over latent model parameters given a history of observations and maximizes its expected long-term reward with respect to this belief distribution. Our algorithm, Bayesian Policy Optimization, builds on recent policy optimization algorithms to learn a universal policy that navigates the exploration-exploitation trade-off to maximize the Bayesian value function. To address challenges from discretizing the continuous latent parameter space, we propose a new policy network architecture that encodes the belief distribution independently from the observable state. Our method significantly outperforms algorithms that address model uncertainty without explicitly reasoning about belief distributions and is competitive with state-of-the-art Partially Observable Markov Decision Process solvers.
Novel Heavy Quark Phenomena in QCD

Heavy quarks provide a new dimension to QCD, allowing tests of fundamental theory, the nature of color confinement, and the production of new exotic multiquark states. I also discuss novel explanations for several apparently anomalous experimental results, such as the large tt forwardbackward asymmetry observed in pp colisions at the Tevatron, the large rates for γ or Z plus highpT charm jets observed at the Tevatron, the strong nuclear absorption of the J/ψ observed in pA collisions at the LHC, as well as fixed target experiments at high xF . Precision measurements of the heavy quark distribution in hadrons at high x are needed since intrinsic heavy quarks can play an important role in high x phenomenology as well as predicting a new mechanism for high-xF Higgs production. The role of multi-parton interactions, such as di-gluon initiated subprocesses for forward quarkonium hadroproduction, is discussed. I also briefly discuss a new approach to the QCD confinement potential and the origin of the QCD mass scale based on AdS/QCD, light-front holography and a unique extension of conformal theory. The renormalization scale ambiguity can be eliminated at finite orders in pQCD using the scheme-independent PMC procedure, thus increasing the precision of predictions and eliminating an unnecessary source of theoretical systematic error.
Learning HMMs with Nonparametric Emissions via Spectral Decompositions of Continuous Matrices

Recently, there has been a surge of interest in using spectral methods for estimating latent variable models. However, it is usually assumed that the distribution of the observations conditioned on the latent variables is either discrete or belongs to a parametric family. In this paper, we study the estimation of an $m$-state hidden Markov model (HMM) with only smoothness assumptions, such as H\"olderian conditions, on the emission densities. By leveraging some recent advances in continuous linear algebra and numerical analysis, we develop a computationally efficient spectral algorithm for learning nonparametric HMMs. Our technique is based on computing an SVD on nonparametric estimates of density functions by viewing them as \emph{continuous matrices}. We derive sample complexity bounds via concentration results for nonparametric density estimation and novel perturbation theory results for continuous matrices. We implement our method using Chebyshev polynomial approximations. Our method is competitive with other baselines on synthetic and real problems and is also very computationally efficient.
The fractional Riesz transform and an exponential potential

In this paper we study the $s$-dimensional Riesz transform of a finite measure $\mu$ in $\mathbf{R}^d$, with $s\in (d-1,d)$. We show that the boundedness of the Riesz transform of $\mu$ implies that a nonlinear potential of exponential type is finite $\mu$-almost everywhere. It appears to be the first result of this type for $s>1$.
Tracking Tetrahymena pyriformis cells using decision trees

Matching cells over time has long been the most difficult step in cell tracking. In this paper, we approach this problem by recasting it as a classification problem. We construct a feature set for each cell, and compute a feature difference vector between a cell in the current frame and a cell in a previous frame. Then we determine whether the two cells represent the same cell over time by training decision trees as our binary classifiers. With the output of decision trees, we are able to formulate an assignment problem for our cell association task and solve it using a modified version of the Hungarian algorithm.
Feature Learning of Virus Genome Evolution With the Nucleotide Skip-Gram Neural Network:

Recent studies reveal that even the smallest genomes such as viruses evolve through complex and stochastic processes, and the assumption of independent alleles is not valid in most applications. Advances in sequencing technologies produce multiple time-point whole-genome data, which enable potential interactions between these alleles to be investigated empirically. To investigate these interactions, we represent alleles as distributed vectors that encode for relationships with other alleles in the course of evolution and apply artificial neural networks to time-sampled whole-genome datasets for feature learning. We build this platform using methods and algorithms derived from natural language processing (NLP), and we denote it as the nucleotide skip-gram neural network. We learn distributed vectors of alleles using the changes in allele frequency of echovirus 11 in the presence or absence of the disinfectant (ClO2) from the experimental evolution data. Results from the training using a new open-source software TensorFlow show that the learned distributed vectors can be clustered using principal component analysis and hierarchical clustering to reveal a list of non-synonymous mutations that arise on the structural protein VP1 in connection to the candidate mutation for ClO2 adaptation. Furthermore, this method can account for recombination rates by setting the extent of interactions as a biological hyper-parameter, and the results show that the most realistic scenario of mid-range interactions across the genome is most consistent with the previous studies.
Efficient Training on Very Large Corpora via Gramian Estimation

We study the problem of learning similarity functions over very large corpora using neural network embedding models. These models are typically trained using SGD with sampling of random observed and unobserved pairs, with a number of samples that grows quadratically with the corpus size, making it expensive to scale to very large corpora. We propose new efficient methods to train these models without having to sample unobserved pairs. Inspired by matrix factorization, our approach relies on adding a global quadratic penalty to all pairs of examples and expressing this term as the matrix-inner-product of two generalized Gramians. We show that the gradient of this term can be efficiently computed by maintaining estimates of the Gramians, and develop variance reduction schemes to improve the quality of the estimates. We conduct large-scale experiments that show a significant improvement in training time and generalization quality compared to traditional sampling methods.
SO(3) quantum invariants are dense

We show that when r ≥ 5 is prime, the SO(3) Witten–Reshetikhin–Turaev quantum invariants for three-manifolds at the level r form a dense set in the complex plane. This confirms a conjecture of Larsen and Wang.
Recursive partitioning for personalization using observational data

We study the problem of learning to choose from m discrete treatment options (e.g., news item or medical drug) the one with best causal effect for a particular instance (e.g., user or patient) where the training data consists of passive observations of covariates, treatment, and the outcome of the treatment. The standard approach to this problem is regress and compare: split the training data by treatment, fit a regression model in each split, and, for a new instance, predict all m outcomes and pick the best. By reformulating the problem as a single learning task rather than m separate ones, we propose a new approach based on recursively partitioning the data into regimes where different treatments are optimal. We extend this approach to an optimal partitioning approach that finds a globally optimal partition, achieving a compact, interpretable, and impactful personalization model. We develop new tools for validating and evaluating personalization models on observational data and use these to demonstrate the power of our novel approaches in a personalized medicine and a job training application.
Analysis of Hand Segmentation in the Wild

A large number of works in egocentric vision have concentrated on action and object recognition. Detection and segmentation of hands in first-person videos, however, has less been explored. For many applications in this domain, it is necessary to accurately segment not only hands of the camera wearer but also the hands of others with whom he is interacting. Here, we take an in-depth look at the hand segmentation problem. In the quest for robust hand segmentation methods, we evaluated the performance of the state of the art semantic segmentation methods, off the shelf and fine-tuned, on existing datasets. We fine-tune RefineNet, a leading semantic segmentation method, for hand segmentation and find that it does much better than the best contenders. Existing hand segmentation datasets are collected in the laboratory settings. To overcome this limitation, we contribute by collecting two new datasets: a) EgoYouTube-Hands including egocentric videos containing hands in the wild, and b) HandOverFace to analyze the performance of our models in presence of similar appearance occlusions. We further explore whether conditional random fields can help refine generated hand segmentations. To demonstrate the benefit of accurate hand maps, we train a CNN for hand-based activity recognition and achieve higher accuracy when a CNN was trained using hand maps produced by the fine-tuned RefineNet. Finally, we annotate a subset of the EgoHands dataset for fine-grained action recognition and show that an accuracy of 58.6% can be achieved by just looking at a single hand pose which is much better than the chance level (12.5%).
Estimation of sparsity via simple measurements

We consider several related problems of estimating the ‘sparsity’ or number of nonzero elements d in a length n vector x by observing only b = M ⊙ x, where M is a predesigned test matrix independent of x, and the operation ⊙ varies between problems. We aim to provide a Δ-approximation of sparsity for some constant Δ with a minimal number of measurements (rows of M). This framework generalizes multiple problems, such as estimation of sparsity in group testing and compressed sensing. We use techniques from coding theory as well as probabilistic methods to show that O(D log D log n) rows are sufficient when the operation ⊙ is logical OR (i.e., group testing), and nearly this many are necessary, where D is a known upper bound on d. When instead the operation ⊙ is multiplication over R or a finite field, we show that respectively Θ(D) and Θ(D log n/D) measurements are necessary and sufficient.
Generic case completeness

In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete.
Relaxed leverage sampling for low-rank matrix completion

Abstract We show that any m × n matrix of rank ϱ can be recovered exactly via nuclear norm minimization from Θ ( λ ⋅ log 2 ( m + n ) ) randomly sampled entries ( λ = ( m + n ) ϱ − ϱ 2 being the degrees of freedom), if we observe each entry with probability proportional to the sum of corresponding row and column leverage scores, minus their product . This relaxation in probabilities (as opposed to sum of leverage scores in [1] ) can give us O ( ϱ 2 log 2 ( m + n ) ) additive improvement on the (best known) sample size of [1] . Further, we can use our relaxed leverage score sampling to achieve additive improvement on sample size for exact recovery of ( a ) incoherent matrices (with restricted leverage scores), and ( b ) row (or column) incoherent matrices, without knowing the leverage scores a priori.
Autostacker: a compositional evolutionary learning system

In this work, an automatic machine learning (AutoML) modeling architecture called Autostacker is introduced. Autostacker combines an innovative hierarchical stacking architecture and an evolutionary algorithm (EA) to perform efficient parameter search without the need for prior domain knowledge about the data or feature preprocessing. Using EA, Autostacker quickly evolves candidate pipelines with high predictive accuracy. These pipelines can be used in their given form, or serve as a starting point for further augmentation and refinement by human experts. Autostacker finds innovative machine learning model combinations and structures, rather than selecting a single model and optimizing its hyperparameters. When its performance on fifteen datasets is compared with that of other AutoML systems, Autostacker produces superior or competitive results in terms of both test accuracy and time cost.
The equivariant complex cobordism ring of a finite abelian group

We compute the equivariant (stable) complex cobordism ring (MUG)∗ for finite abelian groups G.
Perfect matchings as IID factors on non-amenable groups

We prove that in every bipartite Cayley graph of every non-amenable group, there is a perfect matching that is obtained as a factor of independent uniform random variables. We also discuss expansion properties of factors and improve the Hoffman spectral bound on the independence number of finite graphs.
Higher decay inequalities for multilinear oscillatory integrals

In this paper we establish sharp estimates (up to logarithmic losses) for the multilinear oscillatory integral operator studied by Phong, Stein, and Sturm and Carbery and Wright on any product $\prod_{j=1}^d L^{p_j}(\mathbb R)$ with each $p_j \geq 2$, expanding the known results for this operator well outside the previous range $\sum_{j=1}^d p_j^{-1} = d-1$. Our theorem assumes second-order nondegeneracy condition of Varchenko type, and as a corollary reproduces Varchenko's theorem and implies Fourier decay estimates for measures of smooth density on degenerate hypersurfaces in $\mathbb R^d$.
Symmetry and Dirac points in graphene spectrum

Existence and stability of Dirac points in the dispersion relation of operators periodic with respect to the hexagonal lattice is investigated for different sets of additional symmetries. The following symmetries are considered: rotation by $2\pi/3$ and inversion, rotation by $2\pi/3$ and horizontal reflection, inversion or reflection with weakly broken rotation symmetry, and the case where no Dirac points arise: rotation by $2\pi/3$ and vertical reflection. All proofs are based on symmetry considerations. In particular, existence of degeneracies in the spectrum is deduced from the (co)representation of the relevant symmetry group. The conical shape of the dispersion relation is obtained from its invariance under rotation by $2\pi/3$. Persistence of conical points when the rotation symmetry is weakly broken is proved using a geometric phase in one case and parity of the eigenfunctions in the other.
Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection

In the Bayesian online selection problem, the goal is to find a pricing algorithm for serving a sequence of arriving buyers that maximizes the expected social-welfare (or revenue) subject to different types of structural constraints. The focus of this paper is on the case where the allowable subsets of served customers are characterized by a laminar matroid with constant depth. This problem is a special case of the well-known matroid Bayesian online selection problem studied in [Kleinberg & Weinberg, 2012], when the underlying matroid is laminar. We give the first Polynomial-Time Approximation Scheme (PTAS) for the above problem. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that can approximate the optimum online solution with any degree of accuracy as well as a concentration argument that shows our rounding does not have a considerable loss in the expected social welfare. We also introduce the production constrained problem, for which the allowable subsets of served customers are characterized by joint production/shipping constraints that can be modeled by a special case of laminar matroids. We show that by leveraging the special structure of this problem, and using a similar approach as before, we can design a PTAS for this problem too even in the case where the depth of the laminar matroid is not constant. To achieve our result we exploit the negative dependence property of the selection rule in the lower-levels of the laminar family.
Asymptotic properties of the derivative of self-intersection local time of fractional Brownian motion

Abstract Let { B t } t ≥ 0 be a fractional Brownian motion with Hurst parameter 2 3 H 1 . We prove that the approximation of the derivative of self-intersection local time, defined as α e = ∫ 0 T ∫ 0 t p e ′ ( B t − B s ) d s d t , where p e ( x ) is the heat kernel, satisfies a central limit theorem when renormalized by e 3 2 − 1 H . We prove as well that for q ≥ 2 , the q th chaotic component of α e converges in L 2 when 2 3 H 3 4 , and satisfies a central limit theorem when renormalized by a multiplicative factor e 1 − 3 4 H in the case 3 4 H 4 q − 3 4 q − 2 .
Towards Human Computable Passwords

An interesting challenge for the cryptography community is to design authentication protocols that are so simple that a human can execute them without relying on a fully trusted computer. We propose several candidate authentication protocols for a setting in which the human user can only receive assistance from a semi-trusted computer - a computer that stores information and performs computations correctly but does not provide confidentiality. Our schemes use a semi-trusted computer to store and display public challenges C_i\in[n]^k. The human user memorizes a random secret mapping \sigma:[n]\rightarrow \mathbb{Z}_d and authenticates by computing responses f(\sigma(C_i)) to a sequence of public challenges where f:\mathbb{Z}_d^k\rightarrow \mathbb{Z}_d is a function that is easy for the human to evaluate. We prove that any statistical adversary needs to sample m=\tilde{\Omega}\paren{n^{s(f)}} challenge-response pairs to recover \sigma, for a security parameter s(f) that depends on two key properties of f. Our lower bound generalizes recent results of Feldman et al. [Feldman'15] who proved analogous results for the special case d=2. To obtain our results, we apply the general hypercontractivity theorem [O'Donnell'14] to lower bound the statistical dimension of the distribution over challenge-response pairs induced by f and \sigma. Our statistical dimension lower bounds apply to arbitrary functions f:\mathbb{Z}_d^k\rightarrow \mathbb{Z}_d (not just to functions that are easy for a human to evaluate). As an application, we propose a family of human computable password functions f_{k_1,k_2} in which the user needs to perform 2k_1+2k_2+1 primitive operations (e.g., adding two digits or remembering a secret value \sigma(i)), and we show that s(f) = \min{k_1+1, (k_2+1)/2}. For these schemes, we prove that forging passwords is equivalent to recovering the secret mapping. Thus, our human computable password schemes can maintain strong security guarantees even after an adversary has observed the user login to many different accounts.
Open quantum systems and random matrix theory

A simple model for open quantum systems is analyzed with random matrix theory. The system is coupled to the continuum in a minimal way. In this paper the effect on the level statistics of opening the system is seen. In particular the ${\ensuremath{\Delta}}_{3}(L)$ statistic, the width distribution and the level spacing are examined as a function of the strength of this coupling. The emergence of a super-radiant transition is observed. The level spacing and ${\ensuremath{\Delta}}_{3}(L)$ statistics exhibit the signatures of missed levels or intruder levels as the super-radiant state is formed.