cssi/SciSciGPT-SciSciNet huggingface dataset:
MACH: Fast Randomized Tensor Decompositions.

Tensors naturally model many real world processes which generate multi-aspect data. Such processes appear in many different research disciplines, e.g, chemometrics, computer vision, psychometrics and neuroimaging analysis. Tensor decompositions such as the Tucker decomposition are used to analyze multi-aspect data and extract latent factors, which capture the multilinear data structure. Such decompositions are powerful mining tools for extracting patterns from large data volumes. However, most frequently used algorithms for such decompositions involve the computationally expensive Singular Value Decomposition. In this paper we propose MACH, a new sampling algorithm to compute such decompositions. Our method is of significant practical value for tensor streams, such as environmental monitoring systems, IP traffic matrices over time, where large amounts of data are accumulated and the analysis is computationally intensive but also in “post-mortem” data analysis cases where the tensor does not fit in the available memory. We provide the theoretical analysis of our proposed method and verify its efficacy on synthetic data and two real world monitoring system applications.
BIBI: Bayesian inference of breed composition.

The aim of this paper was to develop statistical models to estimate individual breed composition based on the previously proposed idea of regressing discrete random variables corresponding to counts of reference alleles of biallelic molecular markers located across the genome on the allele frequencies of each marker in the pure (base) breeds. Some of the existing regression-based methods do not guarantee that estimators of breed composition will lie in the appropriate parameter space, and none of them account for uncertainty about allele frequencies in the pure breeds, that is, uncertainty about the design matrix. To overcome these limitations, we proposed two Bayesian generalized linear models. For each individual, both models assume that the counts of the reference allele at each marker locus follow independent Binomial distributions, use the logit link and pose a Dirichlet prior over the vector of regression coefficients (which corresponds to breed composition). This prior guarantees that point estimators of breed composition such as the posterior mean pertain to the appropriate space. The difference between these models is that model termed BIBI does not account for uncertainty about the design matrix, while model termed BIBI2 accounts for such an uncertainty by assigning independent Beta priors to the entries of this matrix. We implemented these models in a data set from the University of Florida's multibreed Angus-Brahman population. Posterior means were used as point estimators of breed composition. In addition, the ordinary least squares estimator proposed by Kuehn et al. () (OLSK) was also computed. BIBI and BIBI2 estimated breed composition more accurately than OLSK, and BIBI2 had a 7.69% improvement in accuracy as compared to BIBI.
A REMARK ON ROBERTS' TOTALLY TWISTED KHOVANOV HOMOLOGY

We offer an alternative construction of Roberts' totally twisted Khovanov homology and prove that for knots, it agrees with δ-graded reduced characteristic-2 Khovanov homology.
Fault detection effectiveness of source test case generation strategies for metamorphic testing

Metamorphic testing is a well known approach to tackle the oracle problem in software testing. This technique requires the use of source test cases that serve as seeds for the generation of follow-up test cases. Systematic design of test cases is crucial for the test quality. Thus, source test case generation strategy can make a big impact on the fault detection effectiveness of metamorphic testing. Most of the previous studies on metamorphic testing have used either random test data or existing test cases as source test cases. There has been limited research done on systematic source test case generation for metamorphic testing. This paper provides a comprehensive evaluation on the impact of source test case generation techniques on the fault finding effectiveness of metamorphic testing. We evaluated the effectiveness of line coverage, branch coverage, weak mutation and random test generation strategies for source test case generation. The experiments are conducted with 77 methods from 4 open source code repositories. Our results show that by systematically creating source test cases, we can significantly increase the fault finding effectiveness of metamorphic testing. Further, in this paper we introduce a simple metamorphic testing tool called "METtester" that we use to conduct metamorphic testing on these methods.
Strategic Execution in the Presence of an Uninformed Arbitrageur

Abstract We consider a trader who aims to liquidate a large position in the presence of an arbitrageur who hopes to profit from the trader's activity. The arbitrageur is uncertain about the trader's position and learns from observed price fluctuations. This is a dynamic game with asymmetric information. We present an algorithm for computing perfect Bayesian equilibrium behavior and conduct numerical experiments. Our results demonstrate that the trader's strategy differs significantly from one that would be optimal in the absence of the arbitrageur. In particular, the trader must balance the conflicting desires of minimizing price impact and minimizing information that is signaled through trading. Accounting for information signaling and the presence of strategic adversaries can greatly reduce execution costs.
Modulational instability in the Whitham equation with surface tension and vorticity

Abstract We study modulational stability and instability in the Whitham equation, combining the dispersion relation of water waves and a nonlinearity of the shallow water equations, and modified to permit the effects of surface tension and constant vorticity. When the surface tension coefficient is large, we show that a periodic traveling wave of sufficiently small amplitude is unstable to long wavelength perturbations if the wave number is greater than a critical value, and stable otherwise, similarly to the Benjamin–Feir instability of gravity waves. In the case of weak surface tension, we find intervals of stable and unstable wave numbers, whose boundaries are associated with the extremum of the group velocity, the resonance between the first and second harmonics, the resonance between long and short waves, and a resonance between dispersion and the nonlinearity. For each constant vorticity, we show that a periodic traveling wave of sufficiently small amplitude is unstable if the wave number is greater than a critical value, and stable otherwise. Moreover it can be made stable for a sufficiently large vorticity. The results agree with those based upon numerical computations or formal multiple-scale expansions to the physical problem.
500+ times faster than deep learning: a case study exploring faster methods for text mining stackoverflow

Deep learning methods are useful for high-dimensional data and are becoming widely used in many areas of software engineering. Deep learners utilizes extensive computational power and can take a long time to train- making it difficult to widely validate and repeat and improve their results. Further, they are not the best solution in all domains. For example, recent results show that for finding related Stack Overflow posts, a tuned SVM performs similarly to a deep learner, but is significantly faster to train. This paper extends that recent result by clustering the dataset, then tuning every learners within each cluster. This approach is over 500 times faster than deep learning (and over 900 times faster if we use all the cores on a standard laptop computer). Significantly, this faster approach generates classifiers nearly as good (within 2% F1 Score) as the much slower deep learning method. Hence we recommend this faster methods since it is much easier to reproduce and utilizes far fewer CPU resources. More generally, we recommend that before researchers release research results, that they compare their supposedly sophisticated methods against simpler alternatives (e.g applying simpler learners to build local models).
Parametrizing Shimura subvarieties of \({\mathrm{A}_1}\) Shimura varieties and related geometric problems

This paper gives a complete parametrization of the commensurability classes of totally geodesic subspaces of irreducible arithmetic quotients of \({X_{a, b} = (\mathbf{H}^2)^a \times (\mathbf{H}^3)^b}\). A special case describes all Shimura subvarieties of type \({\mathrm{A}_1}\) Shimura varieties. We produce, for any \({n\geq 1}\), examples of manifolds/Shimura varieties with precisely n commensurability classes of totally geodesic submanifolds/Shimura subvarieties. This is in stark contrast with the previously studied cases of arithmetic hyperbolic 3-manifolds and quaternionic Shimura surfaces, where the presence of one commensurability class of geodesic submanifolds implies the existence of infinitely many classes.
Dynamic belief fusion for object detection

A novel approach for the fusion of heterogeneous object detection methods is proposed. In order to effectively integrate the outputs of multiple detectors, the level of ambiguity in each individual detection score is estimated using the precision/recall relationship of the corresponding detector. The main contribution of the proposed work is a novel fusion method, called Dynamic Belief Fusion (DBF), which dynamically assigns probabilities to hypotheses (target, non-target, intermediate state (target or non-target)) based on confidence levels in the detection results conditioned on the prior performance of individual detectors. In DBF, a joint basic probability assignment, optimally fusing information from all detectors, is determined by the Dempster's combination rule, and is easily reduced to a single fused detection score. Experiments on ARL and PASCAL VOC 07 datasets demonstrate that the detection accuracy of DBF is considerably greater than conventional fusion approaches as well as individual detectors used for the fusion.
A new Fourier transform

In order to define a geometric Fourier transform, one usually works with either $\ell$-adic sheaves in characteristic $p>0$ or with $D$-modules in characteristic 0. If one considers $\ell$-adic sheaves on the stack quotient of a vector bundle $V$ by the homothety action of $\mathbb{G}_m$, however, Laumon provides a uniform geometric construction of the Fourier transform in any characteristic. The category of sheaves on $[V/\mathbb{G}_m]$ is closely related to the category of (unipotently) monodromic sheaves on $V$. In this article, we introduce a new functor, which is defined on all sheaves on $V$ in any characteristic, and we show that it restricts to an equivalence on monodromic sheaves. We also discuss the relation between this new functor and Laumon's homogeneous transform, the Fourier-Deligne transform, and the usual Fourier transform on $D$-modules (when the latter are defined).
It's All a Matter of Degree: Using Degree Information to Optimize Multiway Joins

We optimize multiway equijoins on relational tables using degree information. We give a new bound that uses degree information to more tightly bound the maximum output size of a query. On real data, our bound on the number of triangles in a social network can be up to 95 times tighter than existing worst case bounds. We show that using only a constant amount of degree information, we are able to obtain join algorithms with a running time that has a smaller exponent than existing algorithms - for any database instance. We also show that this degree information can be obtained in nearly linear time, which yields asymptotically faster algorithms in the serial setting and lower communication algorithms in the MapReduce setting. In the serial setting, the data complexity of join processing can be expressed as a function O(IN^x + OUT) in terms of input size IN and output size OUT in which x depends on the query. An upper bound for x is given by fractional hypertreewidth. We are interested in situations in which we can get algorithms for which x is strictly smaller than the fractional hypertreewidth. We say that a join can be processed in subquadratic time if x < 2. Building on the AYZ algorithm for processing cycle joins in quadratic time, for a restricted class of joins which we call 1-series-parallel graphs, we obtain a complete decision procedure for identifying subquadratic solvability (subject to the 3-SUM problem requiring quadratic time). Our 3-SUM based quadratic lower bound is tight, making it the only known tight bound for joins that does not require any assumption about the matrix multiplication exponent omega. We also give a MapReduce algorithm that meets our improved communication bound and handles essentially optimal parallelism.
ON NON-ISOTOPIC SPANNING SURFACES FOR A CLASS OF ARBORESCENT KNOTS

We use the methods of Hedden, Juhasz and Sarkar to exhibit a set of arborescent knots that bound large numbers of non-isotopic minimal genus spanning surfaces. In particular, we describe a sequence of prime knots Kn which will bound at least 22n-1 non-isotopic minimal spanning surfaces of genus n.
High-Dimensional Continuous Control Using Generalized Advantage Estimation

Abstract: Policy gradient methods are an appealing approach in reinforcement learning because they directly optimize the cumulative reward and can straightforwardly be used with nonlinear function approximators such as neural networks. The two main challenges are the large number of samples typically required, and the difficulty of obtaining stable and steady improvement despite the nonstationarity of the incoming data. We address the first challenge by using value functions to substantially reduce the variance of policy gradient estimates at the cost of some bias, with an exponentially-weighted estimator of the advantage function that is analogous to TD(lambda). We address the second challenge by using trust region optimization procedure for both the policy and the value function, which are represented by neural networks. Our approach yields strong empirical results on highly challenging 3D locomotion tasks, learning running gaits for bipedal and quadrupedal simulated robots, and learning a policy for getting the biped to stand up from starting out lying on the ground. In contrast to a body of prior work that uses hand-crafted policy representations, our neural network policies map directly from raw kinematics to joint torques. Our algorithm is fully model-free, and the amount of simulated experience required for the learning tasks on 3D bipeds corresponds to 1-2 weeks of real time.
Results from RHIC with Implications for LHC

High energy nucleus-nucleus collisions provide the means of creating nuclear matter in conditions of extreme temperature and density [1, 2, 3]. The kinetic energy of the incident projectiles would be dissipated in the large volume of nuclear matter involved in the reaction. At large energy or baryon density, a phase transition is expected from a state of nucleons containing confined quarks and gluons to a state of “deconfined” (from their individual nucleons) quarks and gluons, in chemical and thermal equilibrium, covering a volume that is many units of the confining length scale. This state of nuclear matter was originally given the name Quark Gluon Plasma(QGP) [4], a plasma being an ionized gas. However the results at RHIC [2] indicated that instead of behaving like a gas of free quarks and gluons, the matter created in heavy ion collisions at nucleon-nucleon c.m. energy √ sNN = 200 GeV appears to be more like a liquid. This matter interacts much more strongly than originally expected, as elaborated in peer reviewed articles by the 4 RHIC
From Apollonius to Zaremba: Local-global phenomena in thin orbits

We discuss a number of naturally arising problems in arithmetic, culled from completely unrelated sources, which turn out to have a common formulation involving "thin" orbits. These include the local-global problem for integral Apollonian gaskets and Zaremba's Conjecture on finite continued fractions with absolutely bounded partial quotients. Though these problems could have been posed by the ancient Greeks, recent progress comes from a pleasant synthesis of modern techniques from a variety of fields, including harmonic analysis, algebra, geometry, combinatorics, and dynamics. We describe the problems, partial progress, and some of the tools alluded to above.
Pointwise asymptotic behavior of modulated periodic reaction–diffusion waves

Abstract By working with the periodic resolvent kernel and the Bloch-decomposition, we establish pointwise bounds for the Green function of the linearized equation associated with spatially periodic traveling waves of a system of reaction–diffusion equations. With our linearized estimates together with a nonlinear iteration scheme developed by Johnson–Zumbrun, we obtain L p -behavior ( p ⩾ 1 ) of a nonlinear solution to a perturbation equation of a reaction–diffusion equation with respect to initial data in L 1 ∩ H 2 recovering and slightly sharpening results obtained by Schneider using weighted energy and renormalization techniques. We obtain also pointwise nonlinear estimates with respect to two different initial perturbations | u 0 | ⩽ E 0 e − | x | 2 / M , | u 0 | H 2 ⩽ E 0 and | u 0 | ⩽ E 0 ( 1 + | x | ) − r , r > 2 , | u 0 | H 2 ⩽ E 0 respectively, E 0 > 0 sufficiently small and M > 1 sufficiently large, showing that behavior is that of a heat kernel. These pointwise bounds have not been obtained elsewhere, and do not appear to be accessible by previous techniques.
Tightening McCormick Relaxations for Nonlinear Programs via Dynamic Multivariate Partitioning

In this work, we propose a two-stage approach to strengthen piecewise McCormick relaxations for mixed-integer nonlinear programs (MINLP) with multi-linear terms. In the first stage, we exploit Constraint Programing (CP) techniques to contract the variable bounds. In the second stage we partition the variables domains using a dynamic multivariate partitioning scheme. Instead of equally partitioning the domains of variables appearing in multi-linear terms, we construct sparser partitions yet tighter relaxations by iteratively partitioning the variable domains in regions of interest. This approach decouples the number of partitions from the size of the variable domains, leads to a significant reduction in computation time, and limits the number of binary variables that are introduced by the partitioning. We demonstrate the performance of our algorithm on well-known benchmark problems from MINLPLIB and discuss the computational benefits of CP-based bound tightening procedures.
An ergodic algorithm for generating knots with a prescribed injectivity radius

The first provably ergodic algorithm for sampling the space of thick equilateral knots off-lattice, as a function of thickness, will be described. This algorithm is based on previous algorithms of ...
Monochromatic subgraphs in randomly colored graphons

Abstract Let T ( H , G n ) be the number of monochromatic copies of a fixed connected graph H in a uniformly random coloring of the vertices of the graph G n . In this paper we give a complete characterization of the limiting distribution of T ( H , G n ) , when { G n } n ≥ 1 is a converging sequence of dense graphs. When the number of colors grows to infinity, depending on whether the expected value remains bounded, T ( H , G n ) either converges to a finite linear combination of independent Poisson variables or a normal distribution. On the other hand, when the number of colors is fixed, T ( H , G n ) converges to a (possibly infinite) linear combination of independent centered chi-squared random variables. This generalizes the classical birthday problem, which involves understanding the asymptotics of T ( K s , K n ) , the number of monochromatic s -cliques in a complete graph K n ( s -matching birthdays among a group of n friends), to general monochromatic subgraphs in a network.
Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting

Spatiotemporal forecasting has various applications in neuroscience, climate and transportation domain. Traffic forecasting is one canonical example of such learning task. The task is challenging due to (1) complex spatial dependency on road networks, (2) non-linear temporal dynamics with changing road conditions and (3) inherent difficulty of long-term forecasting. To address these challenges, we propose to model the traffic flow as a diffusion process on a directed graph and introduce Diffusion Convolutional Recurrent Neural Network (DCRNN), a deep learning framework for traffic forecasting that incorporates both spatial and temporal dependency in the traffic flow. Specifically, DCRNN captures the spatial dependency using bidirectional random walks on the graph, and the temporal dependency using the encoder-decoder architecture with scheduled sampling. We evaluate the framework on two real-world large scale road network traffic datasets and observe consistent improvement of 12% - 15% over state-of-the-art baselines.
Badly approximable systems of affine forms and incompressibility on fractals

We explore and refine techniques for estimating the Hausdorff dimension of Diophantine exceptional sets and their diffeomorphic images. This work is directly motivated by a recent advance in geometric measure theory, which facilitates the use of games in bounding the dimension of a setʼs intersection with a sufficiently regular fractal. Specifically, we use a variant of Schmidtʼs game to deduce the strong C1 incompressibility of the set of badly approximable systems of linear forms as well as of the set of vectors which are badly approximable with respect to a fixed system of linear forms.
Real-Time Dense Stereo Embedded in a UAV for Road Inspection

The condition assessment of road surfaces is essential to ensure their serviceability while still providing maximum road traffic safety. This paper presents a robust stereo vision system embedded in an unmanned aerial vehicle (UAV). The perspective view of the target image is first transformed into the reference view, and this not only improves the disparity accuracy, but also reduces the algorithm's computational complexity. The cost volumes generated from stereo matching are then filtered using a bilateral filter. The latter has been proved to be a feasible solution for the functional minimisation problem in a fully connected Markov random field model. Finally, the disparity maps are transformed by minimising an energy function with respect to the roll angle and disparity projection model. This makes the damaged road areas more distinguishable from the road surface. The proposed system is implemented on an NVIDIA Jetson TX2 GPU with CUDA for real-time purposes. It is demonstrated through experiments that the damaged road areas can be easily distinguished from the transformed disparity maps.
Self-reciprocal polynomials and coterm polynomials

We classify all self-reciprocal polynomials arising from reversed Dickson polynomials over $$\mathbb {Z}$$ and $$\mathbb {F}_p$$ , where p is prime. As a consequence, we also obtain coterm polynomials arising from reversed Dickson polynomials.
NONLOCALITY AS EVIDENCE FOR A MULTIVERSE COSMOLOGY

We show that observations of quantum nonlocaltiy can be interpreted as purely local phenomena, provided one assumes that the cosmos is a multiverse. Conversely, the observation of quantum nonlocality can be interpreted as observation evidence for a multiverse cosmology, just as observation of the setting of the Sun can be interpreted as evidence for the Earth's rotation.
Monotonicity of actuated flows on dissipative transport networks

We derive a monotonicity property for general, transient flows of a commodity transferred throughout a network, where the flow is characterized by density and mass flux dynamics on the edges with density continuity and mass balance conditions at the nodes. The dynamics on each edge are represented by a general system of partial differential equations that approximates subsonic compressible fluid flow with energy dissipation. The transferred commodity may be injected or withdrawn at any of the nodes, and is propelled throughout the network by nodally located compressors. These compressors are controllable actuators that provide a means to manipulate flows through the network, which we therefore consider as a control system. A canonical problem requires compressor control protocols to be chosen such that time-varying nodal commodity withdrawal profiles are delivered and the density remains within strict limits while an economic or operational cost objective is optimized. In this manuscript, we consider the situation where each nodal commodity withdrawal profile is uncertain, but is bounded within known maximum and minimum time-dependent limits. We introduce the monotone parameterized control system property, and prove that general dynamic dissipative network flows possess this characteristic under certain conditions. This property facilitates very efficient formulation of optimal control problems for such systems in which the solutions must be robust with respect to commodity withdrawal uncertainty. We discuss several applications in which such control problems arise and where monotonicity enables simplified characterization of system behavior.
An explicit staggered-grid method for numerical simulation of large-scale natural gas pipeline networks

Abstract We present an explicit second order staggered finite difference (FD) discretization scheme for forward simulation of natural gas transport in pipeline networks. By construction, this discretization approach guarantees that the conservation of mass condition is satisfied exactly. The mathematical model is formulated in terms of density, pressure, and mass flux variables, and as a result permits the use of a general equation of state to define the relation between the gas density and pressure for a given temperature. In a single pipe, the model represents the dynamics of the density by propagation of a non-linear wave according to a variable wave speed. We derive compatibility conditions for linking domain boundary values to enable efficient, explicit simulation of gas flows propagating through a network with pressure changes created by gas compressors. We compare our staggered grid method with an explicit operator splitting method and a lumped element scheme, and perform numerical experiments to validate the convergence order of the new discretization approach. In addition, we perform several computations to investigate the influence of non-ideal equation of state models and temperature effects on pipeline simulations with boundary conditions on various time and space scales.
An Underactuated Vehicle Localization Method in Marine Environments

The underactuated vehicles are apposite for the long-term deployment and data collection in spatiotemporally varying marine environments. However, these vehicles need to estimate their positions (states) with intrinsic sensing in their long-term trajectories. In previous studies, autonomous underwater vehicles have commonly used vision and range sensors for autonomous state estimation. Inspired by the intrinsic sensing and the persistent deployment, we investigate the localization problem (state estimation) for an inexpensive and underactuated drifting vehicle called a drifter. In this paper, we present a localization method for the drifter making use of the observations of a proprioceptive sensor, i.e., compass. We create the water flow pattern within a given region from ocean model predictions, develop a stochastic motion model, and analyze the persistent water flow behavior. Given a distribution of initial deployment states of the drifter at a particular depth of the water column within the region and the water flow pattern, our method finds attractors and their transient groups at the given depth as the persistent behavior of the water flow. A most-likely localized trajectory of the drifter for a sequence of compass observations is generated based on the persistent behavior of the water flow and hidden Markov model. Our simulation results based on data from ocean model predictions substantiate good performance of our proposed localization method with a low error rate of the state estimation in the long-term trajectory of the drifter.
Microstructure Representation and Reconstruction of Heterogeneous Materials Via Deep Belief Network for Computational Material Design

Integrated Computational Materials Engineering (ICME) aims to accelerate optimal design of complex material systems by integrating material science and design automation. For tractable ICME, it is required that (1) a structural feature space be identified to allow reconstruction of new designs, and (2) the reconstruction process be property-preserving. The majority of existing structural presentation schemes rely on the designer's understanding of specific material systems to identify geometric and statistical features, which could be biased and insufficient for reconstructing physically meaningful microstructures of complex material systems. In this paper, we develop a feature learning mechanism based on convolutional deep belief network to automate a two-way conversion between microstructures and their lower-dimensional feature representations, and to achieves a 1000-fold dimension reduction from the microstructure space. The proposed model is applied to a wide spectrum of heterogeneous material systems with distinct microstructural features including Ti-6Al-4V alloy, Pb63-Sn37 alloy, Fontainebleau sandstone, and Spherical colloids, to produce material reconstructions that are close to the original samples with respect to 2-point correlation functions and mean critical fracture strength. This capability is not achieved by existing synthesis methods that rely on the Markovian assumption of material microstructures.
Beyond Bilingual: Multi-sense Word Embeddings using Multilingual Context.

Word embeddings, which represent a word as a point in a vector space, have become ubiquitous to several NLP tasks. A recent line of work uses bilingual (two languages) corpora to learn a different vector for each sense of a word, by exploiting crosslingual signals to aid sense identification. We present a multi-view Bayesian non-parametric algorithm which improves multi-sense wor d embeddings by (a) using multilingual (i.e., more than two languages) corpora to significantly improve sense embeddings beyond what one achieves with bilingual information, and (b) uses a principled approach to learn a variable number of senses per word, in a data-driven manner. Ours is the first approach with the ability to leverage multilingual corpora efficiently for multi-sense representation learning. Experiments show that multilingual training significantly improves performance over monolingual and bilingual training, by allowing us to combine different parallel corpora to leverage multilingual context. Multilingual training yields comparable performance to a state of the art monolingual model trained on five times more training data.
A Tutorial on Kernel Density Estimation and Recent Advances

This tutorial provides a gentle introduction to kernel density estimation (KDE) and recent advances regarding confidence bands and geometric/topological features. We begin with a discussion of basi...
A counting lemma for binary matroids and applications to extremal problems

Abstract In graph theory, the Szemeredi regularity lemma gives a decomposition of the indicator function for any graph G into a structured component, a uniform part, and a small error. This result, in conjunction with a counting lemma that guarantees many copies of a subgraph H provided a copy of H appears in the structured component, is used in many applications to extremal problems. An analogous decomposition theorem exists for functions over F p n . Specializing to p = 2 , we obtain a statement about the indicator functions of simple binary matroids. In this paper we extend previous results to prove a corresponding counting lemma for binary matroids. We then apply this counting lemma to give simple proofs of some known extremal results, analogous to the proofs of their graph-theoretic counterparts, and discuss how to use similar methods to attack a problem concerning the critical numbers of dense binary matroids avoiding a fixed submatroid.
Zero entropy subgroups of mapping class groups

Given a group action on a surface with a finite invariant set we investigate how the algebraic properties of the induced group of permutations of that set affects the dynamical properties of the group. Our main result shows that in many circumstances if the induced permutation group is not solvable then among the homeomorphisms in the group there must be one with a pseudo-Anosov component. We formulate this in terms of the mapping class group relative to the finite set and show the stronger result that in many circumstances (e.g. if the surface has boundary) if this mapping class group has no elements with pseudo-Anosov components then it is itself solvable.
Fairness in reinforcement learning

We initiate the study of fairness in reinforcement learning, where the actions of a learning algorithm may affect its environment and future rewards. Our fairness constraint requires that an algorithm never prefers one action over another if the long-term (discounted) reward of choosing the latter action is higher. Our first result is negative: despite the fact that fairness is consistent with the optimal policy, any learning algorithm satisfying fairness must take time exponential in the number of states to achieve non-trivial approximation to the optimal policy. We then provide a provably fair polynomial time algorithm under an approximate notion of fairness, thus establishing an exponential gap between exact and approximate fairness.
Deep Exponential Families

We describe deep exponential families (DEFs), a class of latent variable models that are inspired by the hidden structures used in deep neural networks. DEFs capture a hierarchy of dependencies between latent variables, and are easily generalized to many settings through exponential families. We perform inference using recent \black box" variational inference techniques. We then evaluate various DEFs on text and combine multiple DEFs into a model for pairwise recommendation data. In an extensive study, we show going beyond one layer improves predictions for DEFs. We demonstrate that DEFs nd interesting exploratory structure in large data sets, and give better predictive performance than state-of-the-art models.
Shortest non-trivial cycles in directed and undirected surface graphs

Let G be a graph embedded on a surface of genus g with b boundary cycles. We describe algorithms to compute multiple types of non-trivial cycles in G, using different techniques depending on whether or not G is an undirected graph. If G is undirected, then we give an algorithm to compute a shortest non-separating cycle in G in 2O(g)n log log n time. Similar algorithms are given to compute a shortest non-contractible or non-null-homologous cycle in 2O(g+b)n log log n time. Our algorithms for undirected G combine an algorithm of Kutz with known techniques for efficiently enumerating homotopy classes of curves that may be shortest non-trivial cycles.Our main technical contributions in this work arise from assuming G is a directed graph with possibly asymmetric edge weights. For this case, we give an algorithm to compute a shortest non-contractible cycle in G in O((g3 + gb)n log n) time. In order to achieve this time bound, we use a restriction of the infinite cyclic cover that may be useful in other contexts. We also describe an algorithm to compute a shortest non-null-homologous cycle in G in O((g2 + gb)n log n) time, extending a known algorithm of Erickson to compute a shortest non-separating cycle. In both the undirected and directed cases, our algorithms improve the best time bounds known for many values of g and b.
Invariants of the harmonic conformal class of an asymptotically flat manifold

Consider an asymptotically flat Riemannian manifold $(M,g)$ of dimension $n \geq 3$ with nonempty compact boundary. We recall the harmonic conformal class $[g]_h$ of the metric, which consists of all conformal rescalings given by a harmonic function raised to an appropriate power. The geometric significance is that every metric in $[g]_h$ has the same pointwise sign of scalar curvature. For this reason, the harmonic conformal class appears in the study of general relativity, where scalar curvature is related to energy density. Our purpose is to introduce and study invariants of the harmonic conformal class. These invariants are closely related to constrained geometric optimization problems involving hypersurface area-minimizers and the ADM mass. In the final section, we discuss possible applications of the invariants and their relationship with zero area singularities and the positive mass theorem.
Knots without cosmetic crossings

Abstract Let K ′ be a knot that admits no cosmetic crossing changes and let C be a non-trivial, prime, non-cable knot. Then any knot that is a satellite of C with winding number zero and pattern K ′ admits no cosmetic crossing changes. As a consequence we prove the nugatory crossing conjecture for Whitehead doubles of prime, non-cable knots.
Robotic mapping with polygonal random fields

Two types of probabilistic maps are popular in the mobile robotics literature: occupancy grids and geometric maps. Occupancy grids have the advantages of simplicity and speed, but they represent only a restricted class of maps and they make incorrect independence assumptions. On the other hand, current geometric approaches, which characterize the environment by features such as line segments, can represent complex environments compactly. However, they do not reason explicitly about occupancy, a necessity for motion planning; and, they lack a complete probability model over environmental structures. In this paper we present a probabilistic mapping technique based on polygonal random fields (PRF), which combines the advantages of both approaches. Our approach explicitly represents occupancy using a geometric representation, and it is based upon a consistent probability distribution over environments which avoids the incorrect independence assumptions made by occupancy grids. We show how sampling techniques for PRFs can be applied to localized laser and sonar data, and we demonstrate significant improvements in mapping performance over occupancy grids.
Fluctuations of TASEP on a Ring in Relaxation Time Scale

We consider the totally asymmetric simple exclusion process on a ring with flat and step initial conditions. We assume that the size of the ring and the number of particles tend to infinity proportionally and evaluate the fluctuations of tagged particles and currents. The crossover from the KPZ dynamics to the equilibrium dynamics occurs when the time is proportional to the 3/2 power of the ring size. We compute the limiting distributions in this relaxation time scale. The analysis is based on an explicit formula of the finite-time one-point distribution obtained from the coordinate Bethe ansatz method.© 2017 Wiley Periodicals, Inc.
Callias-Type Operators in von Neumann Algebras

We study differential operators on complete Riemannian manifolds which act on sections of a bundle of finite type modules over a von Neumann algebra with a trace. We prove a relative index and a Callias-type index theorem for von Neumann indexes of such operators. We apply these results to obtain a version of Atiyah’s $$L^2$$ -index theorem, which states that the index of a Callias-type operator on a non-compact manifold M is equal to the $$\Gamma $$ -index of its lift to a Galois cover of M. We also prove the cobordism invariance of the index of Callias-type operators. In particular, we give a new proof of the cobordism invariance of the von Neumann index of operators on compact manifolds.
Inhomogeneous Patlak-Keller-Segel models and Aggregation Equations with Nonlinear Diffusion in $\Real^d$

Aggregation equations and parabolic-elliptic Patlak-Keller-Segel (PKS) systems for chemotaxis with nonlinear diffusion are popular models for nonlocal aggregation phenomenon and are a source of many interesting mathematical problems in nonlinear PDEs. The purpose of this work is to give a more complete study of local, subcritical and small-data critical/supercritical theory in $\mathbb{R}^d$, $d \geq 2$. Some existing results can be found in the literature; however, one of the most important cases in biological applications, that is the $\mathbb{R}^2$ case, had not been studied. In this paper, we treat two related systems, which are different generalizations of the classical parabolic-elliptic PKS model. In the first class, nonlocal aggregation is modeled by convolution with a general interaction potential, studied in this generality in our previous work [6]. For this class of models we also present several large data global existence results for critical problems. The second class is a variety of PKS models with spatially inhomogeneous diffusion and decay rate of the chemo-attractant, which is potentially relevant to biological applications and raises interesting mathematical questions.
A faster algorithm for minimum-cost bipartite matching in minor-free graphs

We give O(n7/5 log(nC)) time1 algorithm to compute a minimum-cost maximum cardinality matching (optimal matching) in Kh-minor free graphs with h = O(1) and integer edge weights having magnitude at most C. This improves upon the O(n10/7 log C) algorithm of Cohen et al.. [SODA 2017] and the O(n3/2 log(nC)) algorithm of Gabow and Tarjan [SIAM J. Comput. 1989]. For a graph with m edges and n vertices, the well-known Hungarian Algorithm computes a shortest augmenting path in each phase in O(m) time, yielding an optimal matching in O(mn) time. The Gabow-Tarjan [SIAM J. Comput. 1989] algorithm computes, in each phase, a maximal set of vertex-disjoint shortest augmenting paths (for appropriately defined costs) in O(m) time. This reduces the number of phases from n to [MATH HERE] and the total execution time to [MATH HERE]. To obtain our speed-up, we relax the conditions on the augmenting paths and iteratively compute, in each phase, a set of carefully selected augmenting paths that are not restricted to be shortest or vertex-disjoint. As a result, our algorithm computes substantially more augmenting paths in each phase, reducing the number of phases from [MATH HERE] to O(n2/5). By using small vertex separators, the execution of each phase takes O(m) time on average. For planar graphs, we combine our algorithm with efficient shortest path data structures to obtain a minimum-cost perfect matching in O(n6/5 log (nC)) time. This improves upon the recent O(n4/3 log (nC)) time algorithm by Asathulla et al. [SODA 2018].
Query-Reduction Networks for Question Answering

In this paper, we study the problem of question answering when reasoning over multiple facts is required. We propose Query-Reduction Network (QRN), a variant of Recurrent Neural Network (RNN) that effectively handles both short-term (local) and long-term (global) sequential dependencies to reason over multiple facts. QRN considers the context sentences as a sequence of state-changing triggers, and reduces the original query to a more informed query as it observes each trigger (context sentence) through time. Our experiments show that QRN produces the state-of-the-art results in bAbI QA and dialog tasks, and in a real goal-oriented dialog dataset. In addition, QRN formulation allows parallelization on RNN's time axis, saving an order of magnitude in time complexity for training and inference.
Dual-Based Approximation Algorithms for Cut-Based Network Connectivity Problems

We consider a variety of NP-Complete network connectivity problems. We introduce a novel dual-based approach to approximating network design problems with cut-based linear programming relaxations. This approach gives a 3/2-approximation to Minimum 2-Edge-Connected Spanning Subgraph that is equivalent to a previously proposed algorithm. One well-studied branch of network design models ad hoc networks where each node can either operate at high or low power. If we allow unidirectional links, we can formalize this into the problem Dual Power Assignment (DPA). Our dual-based approach gives a 3 / 2-approximation to DPA, improving the previous best approximation known of $$11/7\approx 1.57$$ . Another standard network design problem is Minimum Strongly Connected Spanning Subgraph (MSCS). We propose a new problem generalizing MSCS and DPA called Star Strong Connectivity (SSC). Then we show that our dual-based approach achieves a 1.6-approximation ratio on SSC. As a consequence of our dual-based approximations, we prove new upper bounds on the integrality gaps of these problems.
Subcritical approach to conformally invariant extension operators on the upper half space

Abstract In this work we obtain sharp embedding inequalities for a family of conformally invariant integral extension operators. This family includes (among others) the classical Poisson extension operator and the extension operator with Riesz kernel. We show that the sharp constants in these inequalities are attained and classify the corresponding extremal functions. We also compute the limiting behavior at the boundary of the extensions of the extremal functions.
Parallel Tracking and Verifying: A Framework for Real-Time and High Accuracy Visual Tracking

Being intensively studied, visual tracking has seen great recent advances in either speed (e.g., with correlation filters) or accuracy (e.g., with deep features). Real-time and high accuracy tracking algorithms, however, remain scarce. In this paper we study the problem from a new perspective and present a novel parallel tracking and verifying (PTAV) framework, by taking advantage of the ubiquity of multithread techniques and borrowing from the success of parallel tracking and mapping in visual SLAM. Our PTAV framework typically consists of two components, a tracker T and a verifier V, working in parallel on two separate threads. The tracker T aims to provide a super real-time tracking inference and is expected to perform well most of the time; by contrast, the verifier V checks the tracking results and corrects T when needed. The key innovation is that, V does not work on every frame but only upon the requests from T; on the other end, T may adjust the tracking according to the feedback from V. With such collaboration, PTAV enjoys both the high efficiency provided by T and the strong discriminative power by V. In our extensive experiments on popular benchmarks including OTB2013, OTB2015, TC128 and UAV20L, PTAV achieves the best tracking accuracy among all real-time trackers, and in fact performs even better than many deep learning based solutions. Moreover, as a general framework, PTAV is very flexible and has great rooms for improvement and generalization.
The equivariant Kazhdan–Lusztig polynomial of a matroid

Abstract We define the equivariant Kazhdan–Lusztig polynomial of a matroid equipped with a group of symmetries, generalizing the nonequivariant case. We compute this invariant for arbitrary uniform matroids and for braid matroids of small rank.
Sparse univariate polynomials with many roots over finite fields

Abstract Suppose q is a prime power and f ∈ F q [ x ] is a univariate polynomial with exactly t monomial terms and degree q − 1 . To establish a finite field analogue of Descartes' Rule, Bi, Cheng, and Rojas (2013) proved an upper bound of 2 ( q − 1 ) t − 2 t − 1 on the number of cosets in F q ⁎ needed to cover the roots of f in F q ⁎ . Here, we give explicit f with root structure approaching this bound: When q is a perfect ( t − 1 ) -st power we give an explicit t-nomial vanishing on q t − 2 t − 1 distinct cosets of F q ⁎ . Over prime fields F p , computational data we provide suggests that it is harder to construct explicit sparse polynomials with many roots. Nevertheless, assuming the Generalized Riemann Hypothesis, we find explicit trinomials having Ω ( log ⁡ p log ⁡ log ⁡ p ) distinct roots in F p .