cssi/SciSciGPT-SciSciNet huggingface dataset:
Probabilistic divide-and-conquer: Deterministic second half

Abstract We present a probabilistic divide-and-conquer (PDC) method for exact sampling of conditional distributions of the form L ( X | X ∈ E ) , where X is a random variable on X , a complete, separable metric space, and event E with P ( E ) ≥ 0 is assumed to have sufficient regularity such that the conditional distribution exists and is unique up to almost sure equivalence. The PDC approach is to define a decomposition of X via sets A and B such that X = A × B , and sample from each separately. The deterministic second half approach is to select the sets A and B such that for each element a ∈ A , there is only one element b a ∈ B for which ( a , b a ) ∈ E . We show how this simple approach provides non-trivial improvements to several conventional random sampling algorithms in combinatorics, and we demonstrate its versatility with applications to sampling from sufficiently regular conditional distributions.
Molecular structure and reversible photodegradation in anthraquinone dyes

Abstract Reversible photodegradation is a process that has been observed in several dye molecules, but the underlying mechanisms are not still well understood. In this contribution, we characterize a series of anthraquinone dyes to determine how self-healing depends on molecular structure. Past studies have used probing techniques that rely on linear absorption, two-photon fluorescence, and amplified spontaneous emission. Each of these probes provide an indirect measure of the populations of the damaged and undamaged species, requiring calibrations or assumptions to be made that might affect the accuracy of the results. The present studies use fluorescence as a probe, which is shown to directly measure the undamaged population. It is found that certain anthraquinone classes share common structural features that are associated with self healing. Furthermore, the time and temperature dependence of photodegradation and self-healing is found to be consistent with the domain model of self healing.
Filtrations of Simplicial Functors and the Novikov Conjecture

Abstract. We show that the Strong Novikov Conjecture for the maximal C∗-algebra C∗(π) of a discrete group π is equivalent to a statement in topological K-theory for which the corresponding statement in algebraic K-theory is always true. We also show that for any group π , rational injectivity of the full assembly map for K ∗(C ∗(π)) follows from rational injectivity of the restricted assembly map.
Maximizing and minimizing the number of generalized colorings of trees

Abstract We classify the trees on n vertices with the maximum and the minimum number of certain generalized colorings, including conflict-free, odd, non-monochromatic, star, and star rainbow vertex colorings. We also extend a result of Cutler and Radcliffe on the maximum and minimum number of existence homomorphisms from a tree to a completely looped graph on q vertices.
Non-commutative discretize-then-optimize algorithms for elliptic PDE-constrained optimal control problems

Abstract In this paper, we analyze the convergence of several optimize-then-discretize and discretize-then-optimize algorithms, based on either a second-order or a fourth-order finite difference discretization, for solving elliptic PDE-constrained optimal control problems. To ensure the convergence of a discretize-then-optimize algorithm, one well-accepted criterion is to design the discretization scheme such that the resulting discretize-then-optimize algorithm commutes with the corresponding optimize-then-discretize algorithm. In other words, both algorithms should give rise to exactly the same discrete optimality system. However, such a restrictive criterion is not trivial to fulfill. By investigating a distributed control problem governed by an elliptic equation, we first show that enforcing such a stringent condition of commutative property is only sufficient but not necessary for achieving the desired convergence. We then introduce some suitable H 1 semi-norm penalty/regularization terms to recover the lost convergence due to the inconsistency caused by the loss of commutativity. Numerical experiments are carried out to verify our theoretical analysis and also validate the effectiveness of our proposed regularization techniques.
A deterministic algorithm for integer factorization

A deterministic algorithm for factoring $n$ using $n^{1/3+o(1)}$ bit operations is presented. The algorithm tests the divisibility of $n$ by all the integers in a short interval at once, rather than integer by integer as in trial division. The algorithm is implemented.
The directions of selection bias

Abstract We show that if the exposure and the outcome affect the selection indicator in the same direction and have non-positive interaction on the risk difference, risk ratio or odds ratio scale, the exposure-outcome odds ratio in the selected population is a lower bound for the true odds ratio.
Bifurcation of limit cycles of the nongeneric quadratic reversible system with discontinuous perturbations

By using the Picard-Fuchs equation and the property of the Chebyshev space to the discontinuous differential system, we obtain an upper bound of the number of limit cycles for the nongeneric quadratic reversible system when it is perturbed inside all discontinuous polynomials with degree n.
Detecting Data Leakage from Databases on Android Apps with Concept Drift

Mobile databases are the statutory backbones of many applications on smartphones, and they store a lot of sensitive information. However, vulnerabilities in the operating system or the app logic can lead to sensitive data leakage by giving the adversaries unauthorized access to the app's database. In this paper, we study such vulnerabilities to define a threat model, and we propose an OS-version independent protection mechanism that app developers can utilize to detect such attacks. To do so, we model the user behavior with the database query workload created by the original apps. Here, we model the drift in behavior by comparing probability distributions of the query workload features over time. We then use this model to determine if the app behavior drift is anomalous. We evaluate our framework on real-world workloads of three different popular Android apps, and we show that our system was able to detect more than 90% of such attacks.
Dijkgraaf–Witten type invariants of Seifert surfaces in 3-manifolds

We introduce defects, with internal gauge symmetries, on a knot and Seifert surface to a knot into the combinatorial construction of finite gauge-group Dijkgraaf–Witten theory. The appropriate initial data for the construction are certain three object categories, with coefficients satisfying a partially degenerate cocycle condition.
Uniform Sampling for Matrix Approximation

Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with probability proportional to its statistical leverage score. Unfortunately, leverage scores are difficult to compute. A simple alternative is to sample rows uniformly at random. While this often works, uniform sampling will eliminate critical row information for many natural instances.We take a fresh look at uniform sampling by examining what information it does preserve. Specifically, we show that uniform sampling yields a matrix that, in some sense, well approximates a large fraction of the original. While this weak form of approximation is not enough for solving linear regression directly, it is enough to compute a better approximation.This observation leads to simple iterative row sampling algorithms for matrix approximation that run in input-sparsity time and preserve row structure and sparsity at all intermediate steps. In addition to an improved understanding of uniform sampling, our main proof introduces a structural result of independent interest: we show that every matrix can be made to have low coherence by reweighting a small subset of its rows.
Adaptive synchrosqueezing based on a quilted short-time Fourier transform

In recent years, the synchrosqueezing transform (SST) has gained popularity as a method for the analysis of signals that can be broken down into multiple components determined by instantaneous amplitudes and phases. One such version of SST, based on the short-time Fourier transform (STFT), enables the sharpening of instantaneous frequency (IF) information derived from the STFT, as well as the separation of amplitude-phase components corresponding to distinct IF curves. However, this SST is limited by the time-frequency resolution of the underlying window function, and may not resolve signals exhibiting diverse time-frequency behaviors with sufficient accuracy. In this work, we develop a framework for an SST based on a “quilted" short-time Fourier transform (SST-QSTFT), which allows adaptation to signal behavior in separate time-frequency regions through the use of multiple windows. This motivates us to introduce a discrete reassignment frequency formula based on a finite difference of the phase spectrum, ensuring computational accuracy for a wider variety of windows. We develop a theoretical framework for the SST-QSTFT in both the continuous and the discrete settings, and describe an algorithm for the automatic selection of optimal windows depending on the region of interest. Using synthetic data, we demonstrate the superior numerical performance of SST-QSTFT relative to other SST methods in a noisy context. Finally, we apply SST-QSTFT to audio recordings of animal calls to demonstrate the potential of our method for the analysis of real bioacoustic signals.
Why adaptively collected data have negative bias and how to correct for it.

From scientific experiments to online A/B testing, the previously observed data often affects how future experiments are performed, which in turn affects which data will be collected. Such adaptivity introduces complex correlations between the data and the collection procedure. In this paper, we prove that when the data collection procedure satisfies natural conditions, then sample means of the data have systematic \emph{negative} biases. As an example, consider an adaptive clinical trial where additional data points are more likely to be tested for treatments that show initial promise. Our surprising result implies that the average observed treatment effects would underestimate the true effects of each treatment. We quantitatively analyze the magnitude and behavior of this negative bias in a variety of settings. We also propose a novel debiasing algorithm based on selective inference techniques. In experiments, our method can effectively reduce bias and estimation error.
NEON2: Finding Local Minima via First-Order Oracles

We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algorithm's performance. As applications, our reduction turns Natasha2 into a first-order method without hurting its theoretical performance. It also converts SGD, GD, SCSG, and SVRG into algorithms finding approximate local minima, outperforming some best known results.
Automated surgical skill assessment in RMIS training.

Manual feedback in basic robot-assisted minimally invasive surgery (RMIS) training can consume a significant amount of time from expert surgeons’ schedule and is prone to subjectivity. In this paper, we explore the usage of different holistic features for automated skill assessment using only robot kinematic data and propose a weighted feature fusion technique for improving score prediction performance. Moreover, we also propose a method for generating ‘task highlights’ which can give surgeons a more directed feedback regarding which segments had the most effect on the final skill score. We perform our experiments on the publicly available JHU-ISI Gesture and Skill Assessment Working Set (JIGSAWS) and evaluate four different types of holistic features from robot kinematic data—sequential motion texture (SMT), discrete Fourier transform (DFT), discrete cosine transform (DCT) and approximate entropy (ApEn). The features are then used for skill classification and exact skill score prediction. Along with using these features individually, we also evaluate the performance using our proposed weighted combination technique. The task highlights are produced using DCT features. Our results demonstrate that these holistic features outperform all previous Hidden Markov Model (HMM)-based state-of-the-art methods for skill classification on the JIGSAWS dataset. Also, our proposed feature fusion strategy significantly improves performance for skill score predictions achieving up to 0.61 average spearman correlation coefficient. Moreover, we provide an analysis on how the proposed task highlights can relate to different surgical gestures within a task. Holistic features capturing global information from robot kinematic data can successfully be used for evaluating surgeon skill in basic surgical tasks on the da Vinci robot. Using the framework presented can potentially allow for real-time score feedback in RMIS training and help surgical trainees have more focused training.
Structures and Transitions in Bcc Tungsten Grain Boundaries and their Role in the Absorption of Point Defects

Abstract We use atomistic simulations to investigate grain boundary (GB) phase transitions in elemental body-centered cubic (bcc) metal tungsten. Motivated by recent modeling study of grain boundary phase transitions in [100] symmetric tilt boundaries in face-centered cubic (fcc) copper, we perform a systematic investigation of [100] and [110] symmetric tilt high-angle and low-angle boundaries in bcc tungsten. The structures of these boundaries have been investigated previously by atomistic simulations in several different bcc metals including tungsten using the γ-surface method, which has limitations. In this work we use a recently developed computational tool based on the USPEX structure prediction code to perform an evolutionary grand canonical search of GB structure at 0 K. For high-angle [100] tilt boundaries the ground states generated by the evolutionary algorithm agree with the predictions of the γ-surface method. For the [110] tilt boundaries, the search predicts novel high-density low-energy grain boundary structures and multiple grain boundary phases within the entire misorientation range. Molecular dynamics simulation demonstrate that the new structures are more stable at high temperature. We observe first-order grain boundary phase transitions and investigate how the structural multiplicity affects the mechanisms of the point defect absorption. Specifically, we demonstrate a two-step nucleation process, when initially the point defects are absorbed through a formation of a metastable GB structure with higher density, followed by a transformation of this structure into a GB interstitial loop or a different GB phase.
Methods for large scale hydraulic fracture monitoring

In this paper we propose computationally efficient and robust methods for estimating the moment tensor and location of micro-seismic event(s) for large search volumes. Our contribution is two-fold. First, we propose a novel joint-complexity measure, namely the sum of nuclear norms which while imposing sparsity on the number of fractures (locations) over a large spatial volume, also captures the rank-1 nature of the induced wavefield pattern. This wavefield pattern is modeled as the outer-product of the source signature with the amplitude pattern across the receivers from a seismic source. A rank-1 factorization of the estimated wavefield pattern at each location can therefore be used to estimate the seismic moment tensor using the knowledge of the array geometry. In contrast to existing work this approach allows us to drop any other assumption on the source signature. Second, we exploit the recently proposed first-order incremental projection algorithms for a fast and efficient implementation of the resulting optimization problem and develop a hybrid stochastic & deterministic algorithm which results in significant computational savings.
Improvement to the Prediction of Fuel Cost Distributions Using ARIMA Model

Availability of a validated, realistic fuel cost model is a prerequisite to the development and validation of new optimization methods and control tools. This paper uses an autoregressive integrated moving average (ARIMA) model with historical fuel cost data in development of a three-step-ahead fuel cost distribution prediction. First, the data features of Form EIA-923 are explored and the natural gas fuel costs of Texas generating facilities are used to develop and validate the forecasting algorithm for the Texas example. Furthermore, the spot price associated with the natural gas hub in Texas is utilized to enhance the fuel cost prediction. The forecasted data is fit to a normal distribution and the Kullback-Leibler divergence is employed to evaluate the difference between the real fuel cost distributions and the estimated distributions. The comparative evaluation suggests the proposed forecasting algorithm is effective in general and is worth pursuing further.
Rational Noncrossing Partitions for all Coprime Pairs

For coprime positive integers $a<b$, Armstrong, Rhoades, and Williams (2013) defined a set $NC(a,b)$ of rational noncrossing partitions, a subset of the ordinary noncrossing partitions of $\{1, \ldots, b-1\}$. Bodnar and Rhoades (2015) confirmed their conjecture that $NC(a,b)$ is closed under rotation and proved an instance of the cyclic sieving phenomenon for this rotation action. We give a definition of $NC(a,b)$ which works for all coprime $a$ and $b$ and prove closure under rotation and cyclic sieving in this more general setting. We also generalize noncrossing parking functions to all coprime $a$ and $b$, and provide a character formula for the action of $\mathfrak{S}_a \times \mathbb{Z}_{b-1}$ on $\mathsf{Park}^{NC}(a,b)$.
Rigidity in the class of orientable compact surfaces of minimal total absolute curvature

Abstract Consider an orientable compact surface in three-dimensional Euclidean space with minimum total absolute curvature. If the Gaussian curvature changes sign to finite order and satisfies a nondegeneracy condition along closed asymptotic curves, we show that any other isometric surface differs by at most a Euclidean motion.
Numerical analysis of strongly nonlinear PDEs

We review the construction and analysis of numerical methods for strongly nonlinear PDEs, with an emphasis on convex and non-convex fully nonlinear equations and the convergence to viscosity solutions. We begin by describing a fundamental result in this area which states that stable, consistent and monotone schemes converge as the discretization parameter tends to zero. We review methodologies to construct finite difference, finite element and semi-Lagrangian schemes that satisfy these criteria, and, in addition, discuss some rather novel tools that have paved the way to derive rates of convergence within this framework.
Completeness of the set \(\{e^{ik\beta \cdot s}\}|_{\forall \beta \in S^2}\)

Let \(S^2\) be the unit sphere in \(\mathbb{R}^3\), \(k>0\) be a fixed constant, \(s\in S\), and \(S\) is a smooth, closed, connected surface, the boundary of a bounded domain \(D\) in \(\mathbb{R}^3\). It is proved that the set \(\{e^{ik\beta \cdot s}\}|_{\forall \beta \in S^2}\) is total in \(L^2(S)\) if and only if \(k^2\) is not a Dirichlet eigenvalue of the Laplacian in \(D\).
Probabilistic projection of subnational total fertility rates.

BACKGROUND We consider the problem of probabilistic projection of the total fertility rate (TFR) for subnational regions. OBJECTIVE We seek a method that is consistent with the UN's recently adopted Bayesian method for probabilistic TFR projections for all countries and works well for all countries. METHODS We assess various possible methods using subnational TFR data for 47 countries. RESULTS We find that the method that performs best in terms of out-of-sample predictive performance and also in terms of reproducing the within-country correlation in TFR is a method that scales each national trajectory from the national predictive posterior distribution by a region-specific scale factor that is allowed to vary slowly over time. CONCLUSIONS Probabilistic projections of TFR for subnational units are best produced by scaling the national projection by a slowly time-varying region-specific scale factor. This supports the hypothesis of Watkins (1990, 1991) that within-country TFR converges over time in response to country-specific factors, and thus extends the Watkins hypothesis to the last 50 years and to a much wider range of countries around the world. CONTRIBUTION We have developed a new method for probabilistic projection of subnational TFR that works well and outperforms other methods. This also sheds light on the extent to which within-country TFR converges over time.
Localization for quasiperiodic operators with unbounded monotone potentials

Abstract We establish non-perturbative Anderson localization for a wide class of 1D quasiperiodic operators with unbounded monotone potentials, extending the classical results on Maryland model, and perturbative results for analytic potentials by Bellissard, Lima, and Scoppola.
Knot fertility and lineage

In this paper, we introduce a new type of relation between knots called the descendant relation. One knot H is a descendant of another knot K if H can be obtained from a minimal crossing diagram of K by some number of crossing changes. We explore properties of the descendant relation and study how certain knots are related, paying particular attention to those knots, called fertile knots, that have a large number of descendants. Furthermore, we provide computational data related to various notions of knot fertility and propose several open questions for future exploration.
Deep Layer Aggregation

Visual recognition requires rich representations that span levels from low to high, scales from small to large, and resolutions from fine to coarse. Even with the depth of features in a convolutional network, a layer in isolation is not enough: compounding and aggregating these representations improves inference of what and where. Architectural efforts are exploring many dimensions for network backbones, designing deeper or wider architectures, but how to best aggregate layers and blocks across a network deserves further attention. Although skip connections have been incorporated to combine layers, these connections have been "shallow" themselves, and only fuse by simple, one-step operations. We augment standard architectures with deeper aggregation to better fuse information across layers. Our deep layer aggregation structures iteratively and hierarchically merge the feature hierarchy to make networks with better accuracy and fewer parameters. Experiments across architectures and tasks show that deep layer aggregation improves recognition and resolution compared to existing branching and merging schemes.
Interpolatory model reduction of parameterized bilinear dynamical systems

Interpolatory projection methods for model reduction of nonparametric linear dynamical systems have been successfully extended to nonparametric bilinear dynamical systems. However, this has not yet occurred for parametric bilinear systems. In this work, we aim to close this gap by providing a natural extension of interpolatory projections to model reduction of parametric bilinear dynamical systems. We introduce necessary conditions that the projection subspaces must satisfy to obtain parametric tangential interpolation of each subsystem transfer function. These conditions also guarantee that the parameter sensitivities (Jacobian) of each subsystem transfer function are matched tangentially by those of the corresponding reduced-order model transfer function. Similarly, we obtain conditions for interpolating the parameter Hessian of the transfer function by including additional vectors in the projection subspaces. As in the parametric linear case, the basis construction for two-sided projections does not require computing the Jacobian or the Hessian.
Optimal large-MIMO data detection with transmit impairments

Real-world transceiver designs for multiple-input multiple-output (MIMO) wireless communication systems are affected by a number of hardware impairments that already appear at the transmit side, such as amplifier non-linearities, quantization artifacts, and phase noise. While such transmit-side impairments are routinely ignored in the data-detection literature, they often limit reliable communication in practical systems. In this paper, we present a novel data-detection algorithm, referred to as large-MIMO approximate message passing with transmit impairments (short LAMA-I), which takes into account a broad range of transmit-side impairments in wireless systems with a large number of transmit and receive antennas. We provide conditions in the large-system limit for which LAMA-I achieves the error-rate performance of the individually-optimal (IO) data detector. We furthermore demonstrate that LAMA-I achieves near-IO performance at low computational complexity in realistic, finite dimensional large-MIMO systems.
Fast Single Shot Detection and Pose Estimation

For applications in navigation and robotics, estimating the 3D pose of objects is as important as detection. Many approaches to pose estimation rely on detecting or tracking parts or keypoints [11, 21]. In this paper we build on a recent state-of-the-art convolutional network for slidingwindow detection [10] to provide detection and rough pose estimation in a single shot, without intermediate stages of detecting parts or initial bounding boxes. While not the first system to treat pose estimation as a categorization problem, this is the first attempt to combine detection and pose estimation at the same level using a deep learning approach. The key to the architecture is a deep convolutional network where scores for the presence of an object category, the offset for its location, and the approximate pose are all estimated on a regular grid of locations in the image. The resulting system is as accurate as recent work on pose estimation (42.4% 8 View mAVP on Pascal 3D+ [21] ) and significantly faster (46 frames per second (FPS) on a TITAN X GPU). This approach to detection and rough pose estimation is fast and accurate enough to be widely applied as a pre-processing step for tasks including high-accuracy pose estimation, object tracking and localization, and vSLAM.
Constrained Factor Models for High-Dimensional Matrix-Variate Time Series

AbstractHigh-dimensional matrix-variate time series data are becoming widely available in many scientific fields, such as economics, biology, and meteorology. To achieve significant dimension reduction while preserving the intrinsic matrix structure and temporal dynamics in such data, Wang, Liu, and Chen proposed a matrix factor model, that is, shown to be able to provide effective analysis. In this article, we establish a general framework for incorporating domain and prior knowledge in the matrix factor model through linear constraints. The proposed framework is shown to be useful in achieving parsimonious parameterization, facilitating interpretation of the latent matrix factor, and identifying specific factors of interest. Fully utilizing the prior-knowledge-induced constraints results in more efficient and accurate modeling, inference, dimension reduction as well as a clear and better interpretation of the results. Constrained, multi-term, and partially constrained factor models for matrix-variate ti...
THE SIGN OF FOURIER COEFFICIENTS OF HALF-INTEGRAL WEIGHT CUSP FORMS

From a result of Waldspurger [W. Kohnen and D. Zagier, Values of L-series of modular forms at the center of the critical strip, Invent. Math.64 (1981) 175–198], it is known that the normalized Fourier coefficients a(m) of a half-integral weight holomorphic cusp eigenform &#x1d523; are, up to a finite set of factors, one of $\pm \sqrt{L(\frac{1}{2}, f, \chi_m)}$ when m is square-free and f is the integral weight cusp form related to &#x1d523; by the Shimura correspondence [G. Shimura, On modular forms of half-integral weight, Ann. of Math.97 (1973) 440–481]. In this paper we address a question posed by Kohnen: which square root is a(m)? In particular, if we look at the set of a(m) with m square-free, do these Fourier coefficients change sign infinitely often? By partially analytically continuing a related Dirichlet series, we are able to show that this is so.
ALE: Additive Latent Effect Models for Grade Prediction

The past decade has seen a growth in the development and deployment of educational technologies for assisting college-going students in choosing majors, selecting courses and acquiring feedback based on past academic performance. Grade prediction methods seek to estimate a grade that a student may achieve in a course that she may take in the future (e.g., next term). Accurate and timely prediction of students' academic grades is important for developing effective degree planners and early warning systems, and ultimately improving educational outcomes. Existing grade pre- diction methods mostly focus on modeling the knowledge components associated with each course and student, and often overlook other factors such as the difficulty of each knowledge component, course instructors, student interest, capabilities and effort. In this paper, we propose additive latent effect models that incorporate these factors to predict the student next-term grades. Specifically, the proposed models take into account four factors: (i) student's academic level, (ii) course instructors, (iii) student global latent factor, and (iv) latent knowledge factors. We compared the new models with several state-of-the-art methods on students of various characteristics (e.g., whether a student transferred in or not). The experimental results demonstrate that the proposed methods significantly outperform the baselines on grade prediction problem. Moreover, we perform a thorough analysis on the importance of different factors and how these factors can practically assist students in course selection, and finally improve their academic performance.
Quantitative Fatou Theorems and Uniform Rectifiability

We show that a suitable quantitative Fatou Theorem characterizes uniform rectifiability in the codimension 1 case.
Gains of Restricted Secondary Licensing in Millimeter Wave Cellular Systems

Sharing the spectrum among multiple operators seems promising in millimeter wave (mmWave) systems. One explanation is the highly directional transmission in mmWave, which reduces the interference caused by one network on the other networks sharing the same resources. In this paper, we model a mmWave cellular system, where an operator that primarily owns an exclusive-use license of a certain band can sell a restricted secondary license of the same band to another operator. This secondary network has a restriction on the maximum interference it can cause to the original network. Using stochastic geometry, we derive expressions for the coverage and the rate of both networks, and establish the feasibility of secondary licensing in licensed mmWave bands. To explain economic tradeoffs, we consider a revenue-pricing model for both operators in the presence of a central licensing authority. Our results show that the original operator and central network authority can benefit from secondary licensing when the maximum interference threshold is properly adjusted. This means that the original operator and central licensing authority have an incentive to permit a secondary network to restrictively share the spectrum. Our results also illustrate that the spectrum sharing gains increase with narrow beams and when the network densifies.
Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms

Tensor rank and low-rank tensor decompositions have many applications in learning and complexity theory. Most known algorithms use unfoldings of tensors and can only handle rank up to n^{\lfloor p/2 \rceil} for a p-th order tensor. Previously no efficient algorithm can decompose 3rd order tensors when the rank is super-linear in the dimension. Using ideas from sum-of-squares hierarchy, we give the first quasi-polynomial time algorithm that can decompose a random 3rd order tensor decomposition when the rank is as large as n^{3/2}/poly log n. We also give a polynomial time algorithm for certifying the injective norm of random low rank tensors. Our tensor decomposition algorithm exploits the relationship between injective norm and the tensor components. The proof relies on interesting tools for decoupling random variables to prove better matrix concentration bounds.
Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation

We give the first rigorous proof of the convergence of Riemannian Hamiltonian Monte Carlo, a general (and practical) method for sampling Gibbs distributions. Our analysis shows that the rate of convergence is bounded in terms of natural smoothness parameters of an associated Riemannian manifold. We then apply the method with the manifold defined by the log barrier function to the problems of (1) uniformly sampling a polytope and (2) computing its volume, the latter by extending Gaussian cooling to the manifold setting. In both cases, the total number of steps needed is O*(mn2/3), improving the state of the art. A key ingredient of our analysis is a proof of an analog of the KLS conjecture for Gibbs distributions over manifolds.
Strengthening the entropy power inequality

We tighten the entropy power inequality (EPI) when one of the random summands is Gaussian. Our strengthening is closely related to strong data processing for Gaussian channels and generalizes the (vector extension of) Costa's EPI. This leads to a new reverse EPI and, as a corollary, sharpens Stam's inequality relating entropy power and Fisher information. Applications to network information theory are given, including a short self-contained proof of the converse for the two-encoder quadratic Gaussian source coding problem. The proof of our main result is based on weak convergence and a doubling argument for establishing Gaussian optimality via rotational-invariance.
Modeling Individual Differences in Game Behavior Using HMM.

Player modeling is an important concept that has gained much attention in game research due to its utility in developing adaptive techniques to target better designs for engagement and retention. Previous work has explored modeling individual differences using machine learning algorithms per- formed on aggregated game actions. However, players' individual differences may be better manifested through sequential patterns of the in-game player's actions. While few works have explored sequential analysis of player data, none have explored the use of Hidden Markov Models (HMM) to model individual differences, which is the topic of this paper. In par- ticular, we developed a modeling approach using data col- lected from players playing a Role-Playing Game (RPG). Our proposed approach is two fold: 1. We present a Hidden Markov Model (HMM) of player in-game behaviors to model individual differences, and 2. using the output of the HMM, we generate behavioral features used to classify real world players' characteristics, including game expertise and the big five personality traits. Our results show predictive power for some of personality traits, such as game expertise and conscientiousness, but the most influential factor was game expertise.
Electron thermodynamics in GRMHD simulations of low-luminosity black hole accretion

Simple assumptions made regarding electron thermodynamics often limit the extent to which general relativistic magnetohydrodynamic (GRMHD) simulations can be applied to observations of low-luminosity accreting black holes. We present, implement, and test a model that self-consistently evolves an electron entropy equation and takes into account the effects of spatially varying electron heating and relativistic anisotropic thermal conduction along magnetic field lines. We neglect the back-reaction of electron pressure on the dynamics of the accretion flow. Our model is appropriate for systems accreting at $\ll 10^{-5}$ of the Eddington rate, so radiative cooling by electrons can be neglected. It can be extended to higher accretion rates in the future by including electron cooling and proton-electron Coulomb collisions. We present a suite of tests showing that our method recovers the correct solution for electron heating under a range of circumstances, including strong shocks and driven turbulence. Our initial applications to axisymmetric simulations of accreting black holes show that (1)~physically-motivated electron heating rates yield electron temperature distributions significantly different from the constant electron to proton temperature ratios assumed in previous work, with higher electron temperatures concentrated in the coronal region between the disc and the jet; (2)~electron thermal conduction significantly modifies the electron temperature in the inner regions of black hole accretion flows if the effective electron mean free path is larger than the local scale-height of the disc (at least for the initial conditions and magnetic field configurations we study). The methods developed in this work are important for producing more realistic predictions for the emission from accreting black holes such as Sagittarius A* and M87; these applications will be explored in future work.
Capacity lower bound for the Ising perceptron

We consider the Ising perceptron with gaussian disorder, which is equivalent to the discrete cube {−1,+1}N intersected by M random half-spaces. The perceptron’s capacity is the largest integer MN for which the intersection is nonempty. It is conjectured by Krauth and Mezard (1989) that the (random) ratio MN/N converges in probability to an explicit constant α⋆≐ 0.83. Kim and Roche (1998) proved the existence of a positive constant γ such that γ ≤ MN/N ≤ 1−γ with high probability; see also Talagrand (1999). In this paper we show that the Krauth–Mezard conjecture α⋆ is a lower bound with positive probability, under the condition that an explicit univariate function S(λ) is maximized at λ=0. Our proof is an application of the second moment method to a certain slice of perceptron configurations, as selected by the so-called TAP (Thouless, Anderson, and Palmer, 1977) or AMP (approximate message passing) iteration, whose scaling limit has been characterized by Bayati and Montanari (2011) and Bolthausen (2012). For verifying the condition on S(λ) we outline one approach, which is implemented in the current version using (nonrigorous) numerical integration packages. In a future version of this paper we intend to complete the verification by implementing a rigorous numerical method.
Tied Multitask Learning for Neural Speech Translation

We explore multitask models for neural translation of speech, augmenting them in order to reflect two intuitive notions. First, we introduce a model where the second task decoder receives information from the decoder of the first task, since higher-level intermediate representations should provide useful information. Second, we apply regularization that encourages transitivity and invertibility. We show that the application of these notions on jointly trained models improves performance on the tasks of low-resource speech transcription and translation. It also leads to better performance when using attention information for word discovery over unsegmented input.
TWAM: A Certifying Abstract Machine for Logic Programs

Type-preserving (or typed) compilation uses typing derivations to certify correctness properties of compilation. We have designed and implemented a typed compiler for an idealized logic programming language we call T-Prolog. The crux of our approach is a new certifying abstract machine which we call the Typed Warren Abstract Machine (TWAM). The TWAM has a dependent type system strong enough to show programs obey a semantics based on provability in first-order logic (FOL). We present a soundness metatheorem which (going beyond the guarantees provided by most typed compilers) constitutes a partial behavior correctness guarantee: well-typed TWAM programs are sound proof search procedures with respect to a FOL signature. We argue why this guarantee is a natural choice for significant classes of logic programs. This metatheorem justifies our design and implementation of a certifying compiler from T-Prolog to TWAM.
The Cantor-Bendixson Rank of Certain Bridgeland-Smith Stability Conditions

We provide a novel proof that the set of directions that admit a saddle connection on a meromorphic quadratic differential with at least one pole of order at least two is closed, which generalizes a result of Bridgeland and Smith, and Gaiotto, Moore, and Neitzke. Secondly, we show that this set has finite Cantor–Bendixson rank and give a tight bound. Finally, we present a family of surfaces realizing all possible Cantor–Bendixson ranks. The techniques in the proof of this result exclusively concern Abelian differentials on Riemann surfaces, also known as translation surfaces. The concept of a “slit translation surface” is introduced as the primary tool for studying meromorphic quadratic differentials with higher order poles.
Phase retrieval via randomized Kaczmarz: theoretical guarantees

Author(s): Tan, Yan Shuo; Vershynin, Roman | Abstract: We consider the problem of phase retrieval, i.e. that of solving systems of quadratic equations. A simple variant of the randomized Kaczmarz method was recently proposed for phase retrieval, and it was shown numerically to have a computational edge over state-of-the-art Wirtinger flow methods. In this paper, we provide the first theoretical guarantee for the convergence of the randomized Kaczmarz method for phase retrieval. We show that it is sufficient to have as many Gaussian measurements as the dimension, up to a constant factor. Along the way, we introduce a sufficient condition on measurement sets for which the randomized Kaczmarz method is guaranteed to work. We show that Gaussian sampling vectors satisfy this property with high probability; this is proved using a chaining argument coupled with bounds on VC dimension and metric entropy.
Active Learning for Convolutional Neural Networks: A Core-Set Approach

Convolutional neural networks (CNNs) have been successfully applied to many recognition and learning tasks using a universal recipe; training a deep model on a very large dataset of supervised examples. However, this approach is rather restrictive in practice since collecting a large set of labeled images is very expensive. One way to ease this problem is coming up with smart ways for choosing images to be labelled from a very large collection (ie. active learning). Our empirical study suggests that many of the active learning heuristics in the literature are not effective when applied to CNNs in batch setting. Inspired by these limitations, we define the problem of active learning as core-set selection, ie. choosing set of points such that a model learned over the selected subset is competitive for the remaining data points. We further present a theoretical result characterizing the performance of any selected subset using the geometry of the datapoints. As an active learning algorithm, we choose the subset which is expected to yield best result according to our characterization. Our experiments show that the proposed method significantly outperforms existing approaches in image classification experiments by a large margin.
Disjunctive normal networks

Artificial neural networks are powerful pattern classifiers. They form the basis of the highly successful and popular Convolutional Networks which offer the state-of-the-art performance on several computer visions tasks. However, in many general and non-vision tasks, neural networks are surpassed by methods such as support vector machines and random forests that are also easier to use and faster to train. One reason is that the backpropagation algorithm, which is used to train artificial neural networks, usually starts from a random weight initialization which complicates the optimization process leading to long training times and increases the risk of stopping in a poor local minima. Several initialization schemes and pre-training methods have been proposed to improve the efficiency and performance of training a neural network. However, this problem arises from the architecture of neural networks. We use the disjunctive normal form and approximate the boolean conjunction operations with products to construct a novel network architecture. The proposed model can be trained by minimizing an error function and it allows an effective and intuitive initialization which avoids poor local minima. We show that the proposed structure provides efficient coverage of the decision space which leads to state-of-the art classification accuracy and fast training times.
Gamma Processes, Stick-Breaking, and Variational Inference

While most Bayesian nonparametric models in machine learning have focused on the Dirichlet process, the beta process, or their variants, the gamma process has recently emerged as a useful nonparametric prior in its own right. Current inference schemes for models involving the gamma process are restricted to MCMC-based methods, which limits their scalability. In this paper, we present a variational inference framework for models involving gamma process priors. Our approach is based on a novel stick-breaking constructive definition of the gamma process. We prove correctness of this stick-breaking process by using the characterization of the gamma process as a completely random measure (CRM), and we explicitly derive the rate measure of our construction using Poisson process machinery. We also derive error bounds on the truncation of the infinite process required for variational inference, similar to the truncation analyses for other nonparametric models based on the Dirichlet and beta processes. Our representation is then used to derive a variational inference algorithm for a particular Bayesian nonparametric latent structure formulation known as the infinite Gamma-Poisson model, where the latent variables are drawn from a gamma process prior with Poisson likelihoods. Finally, we present results for our algorithm on nonnegative matrix factorization tasks on document corpora, and show that we compare favorably to both sampling-based techniques and variational approaches based on betaBernoulli priors, as well as a direct DP-based construction of the gamma process.
An achievable rate-distortion region for the multiple descriptions problem

A multiple-descriptions (MD) coding strategy is proposed and an inner bound to the achievable rate-distortion region is derived for discrete memoryless sources. The scheme utilizes linear codes. It is shown in two different MD set-ups that the linear coding scheme achieves a larger rate-distortion region than previously known random coding strategies. Furthermore, it is shown via an example that the best known random coding scheme for the set-up can be improved by including additional randomly generated codebooks.