cssi/SciSciGPT-SciSciNet huggingface dataset:
Learning riemannian metrics

We consider the problem of learning a Riemannian metric associated with a given differentiable manifold and a set of points. Our approach to the problem involves choosing a metric from a parametric family that is based on maximizing the inverse volume of a given dataset of points. From a statistical perspective, it is related to maximum likelihood under a model that assigns probabilities inversely proportional to the Riemannian volume element. We discuss in detail learninga metric on the multinomial simplex where the metric candidates are pull-back metrics of the Fisher information under a continuous group of transformations. When applied to documents, the resulting geodesics resemble, but outperform, the TFIDF cosine similarity measure in classification.
Data attacks on power grids: Leveraging detection

Data attacks on meter measurements in the power grid can lead to errors in state estimation. This paper presents a new data attack model where an adversary produces changes in state estimation despite failing bad-data detection checks. The adversary achieves its objective by making the estimator incorrectly identify correct measurements as bad data. The proposed attack regime's significance lies in reducing the minimum sizes of successful attacks to more than half of that of undetectable data attacks. Additionally, the attack model is able to construct attacks on systems that are resilient to undetectable attacks. The conditions governing a successful data attack of the proposed model are presented along with guarantees on its performance. The complexity of constructing an optimal attack is discussed and two polynomial time approximate algorithms for attack vector construction are developed. The performance of the proposed algorithms and efficacy of the hidden attack model are demonstrated through simulations on IEEE test systems.
Towards Open Set Deep Networks

Deep networks have produced significant gains for various visual recognition problems, leading to high impact academic and commercial applications. Recent work in deep networks highlighted that it is easy to generate images that humans would never classify as a particular object class, yet networks classify such images high confidence as that given class – deep network are easily fooled with images humans do not consider meaningful. The closed set nature of deep networks forces them to choose from one of the known classes leading to such artifacts. Recognition in the real world is open set, i.e. the recognition system should reject unknown/unseen classes at test time. We present a methodology to adapt deep networks for open set recognition, by introducing a new model layer, OpenMax, which estimates the probability of an input being from an unknown class. A key element of estimating the unknown probability is adapting Meta-Recognition concepts to the activation patterns in the penultimate layer of the network. Open-Max allows rejection of "fooling" and unrelated open set images presented to the system, OpenMax greatly reduces the number of obvious errors made by a deep network. We prove that the OpenMax concept provides bounded open space risk, thereby formally providing an open set recognition solution. We evaluate the resulting open set deep networks using pre-trained networks from the Caffe Model-zoo on ImageNet 2012 validation data, and thousands of fooling and open set images. The proposed OpenMax model significantly outperforms open set recognition accuracy of basic deep networks as well as deep networks with thresholding of SoftMax probabilities.
On the Harnack inequality for degenerate and singular elliptic equations with unbounded lower order terms via sliding paraboloids

We use the method of sliding paraboloids to establish a Harnack inequality for linear, degenerate and singular elliptic equation with unbounded lower order terms. The equations we consider include uniformly elliptic equations and linearized Monge–Ampere equations. Our argument allows us to prove the doubling estimate for functions which, at points of large gradient, are solutions of (degenerate and singular) elliptic equations with unbounded drift.
Specializations of elliptic surfaces, and divisibility in the Mordell–Weil group

Let ℰ→C be an elliptic surface defined over a number field k, let P:C→ℰ be a section, and let l be a rational prime. We bound the number of points of low algebraic degree in the l-division hull of P at the fibre ℰt. Specifically, for t∈C(k) with [k(t):k]≤B1 such that ℰt is nonsingular, we obtain a bound on the number of Q∈ℰt(k) such that [k(Q):k]≤B2, and such that lnQ=Pt for some n≥1. This bound depends on ℰ, P, l, B1, and B2, but is independent of t.
Analysis of millimeter wave networked wearables in crowded environments

The millimeter wave (mmWave) band has the potential to provide high throughput among wearable devices. When mmWave wearable networks are used in crowded environments, such as on a bus or train, antenna directivity and orientation hold the key to achieving Gbps rates. Previous work using stochastic geometry often assumes an infinite number of interfering nodes drawn from a Poisson Point Process (PPP). Since indoor wearable networks will be isolated due to walls, a network with a finite number of nodes may be a more suitable model. In this paper, we characterize the significant sources of interference and develop closed-form expressions for the spatially averaged performance of a typical user's wearable communication link. The effect of human body blockage on the mmWave signals and the role of network density are investigated to show that an increase in interferer density reduces the mean number of significant interferers.
Group-type subfactors and Hadamard matrices

A hyperfinite II1 subfactor may be obtained from a symmetric commuting square via iteration of the basic construction. For certain commuting squares constructed from Hadamard matrices, we describe this subfactor as a group-type inclusion R HR o K, where H and K are finite groups with outer actions on the hyperfinite II1 factor R. We find the group of outer automorphisms generated by H and K, and use the method of Bisch and Haagerup to determine the principal and dual principal graphs. In some cases a complete classification is obtained by examining the element of H 3 (HK/IntR) associated with
Asymptotic uncorrelation for Mexican needlets

Abstract We recall Mexican needlets from [D. Geller, A. Mayeli, Continuous wavelets on compact manifolds, Math. Z. 262 (4) (2009) 895–927; D. Geller, A. Mayeli, Nearly tight frames and space-frequency analysis on compact manifolds, Math. Z. 263 (2) (2009) 234–264]. We derive an estimate for certain types of Legendre series, which we apply to the statistical properties of Mexican needlets. More precisely, we shall show that, under isotropy assumption, the Mexican needlet coefficients of a random field on the sphere are asymptotically uncorrelated, as the frequency parameter goes to infinity. This property is important in the analysis of spherical random fields, in particular in connection to the analysis of Cosmic Microwave Background (CMB) radiation data.
A Nonequilibrium Statistical Model of Spectrally Truncated Burgers‐Hopf Dynamics

Exact spectral truncations of the unforced, inviscid Burgers-Hopf equation are Hamiltonian systems with many degrees of freedom that exhibit intrinsic stochasticity and coherent scaling behavior. For this reason recent studies have employed these systems as prototypes to test stochastic mode reduction strategies. In the present paper the Burgers-Hopf dynamics truncated to n Fourier modes is treated by a new statistical model reduction technique, and a closed system of evolution equations for the mean values of the m lowest modes is derived for m ≪ n. In the reduced model the m-mode macrostates are associated with trial probability densities on the phase space of the n-mode microstates, and a cost functional is introduced to quantify the lack of fit of paths of these densities to the Liouville equation. The best-fit macrodynamics is obtained by minimizing the cost functional over paths, and the equations governing the closure are then derived from Hamilton-Jacobi theory. The resulting reduced equations have a fractional diffusion and modified nonlinear interactions, and the explicit form of both are determined up to a single closure parameter. The accuracy and range of validity of this nonequilibrium closure is assessed by comparison against direct numerical simulations of statistical ensembles, and the predicted behavior is found to be well represented by the reduced equations. © 2014 Wiley Periodicals, Inc.
Measuring the muon content of air showers with IceTop

IceTop, the surface component of the IceCube detector, has been used to measure the energy spectrum of cosmic ray primaries in the range between 1.58 PeV and 1.26 EeV. It can also be used to study the low energy muons in air showers by looking at large distances (> 300 m) from the shower axis. We will show the muon lateral distribution function at large lateral distances as measured with IceTop and discuss the implications of this measurement. We will also discuss the prospects for low energy muon studies with IceTop.
Likelihood adaptively modified penalties

A new family of penalty functions, adaptive to likelihood, is introduced for model selection in general regression models. It arises naturally through assuming certain types of prior distribution on the regression parameters. To study stability properties of the penalized maximum likelihood estimator, two types of asymptotic stability are defined. Theoretical properties, including the parameter estimation consistency, model selection consistency, and asymptotic stability, are established under suitable regularity conditions. An efficient coordinate-descent algorithm is proposed. Simulation results and real data analysis show that the proposed method has competitive performance in comparison with existing ones.
The goodness of covariance selection problem from AUC bounds

We conduct a study of graphical models and discuss the quality of model selection approximation by formulating the problem as a detection problem and examining the area under the curve (AUC). We are specifically looking at the model selection problem for jointly Gaussian random vectors. For Gaussian random vectors, this problem simplifies to the covariance selection problem which is widely discussed in literature by Dempster [1]. In this paper, we give the definition for the correlation approximation matrix (CAM) which contains all information about the model selection problem and discuss the pth order Markov chain model and the pth order star network model for the a Gaussian distribution with Toeplitz covariance matrix. For each model, we compute the model covariance matrix as well as the KL divergence between the Gaussian distribution and its model. We also show that if the model order, p, is proportional to the number of nodes, n, then the model selection is asymptotically good as the number of nodes, n, goes to infinity since the AUC in this case is bounded away from one. We conduct some simulations which confirm the theoretical analysis and also show that the selected model quality increases as the model order, p, increases.
On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms

The need for scalable solvers for massive optimization problems has motivated the development of asynchronous-parallel algorithms, where a set of nodes runs in parallel with little or no synchronization, thus computing with delayed information. This paper develops powerful Lyapunov-functions techniques, and uses them to study the convergence of the asynchronous-parallel algorithm ARock under potentially unbounded delays. ARock is a very general asynchronous algorithm, that takes many popular algorithms as special cases: for instance, asynchronous block gradient descent, forward backward, ADMM, etc. Therefore our results have broad implications, and a range of applications. ARock parallelizes a fixed-point iterations by letting a set of nodes randomly choose solution coordinates to update in an asynchronous parallel fashion. The existing analysis of ARock assumes the delays to be bounded, and uses this bound to set a step size that is important to both convergence and efficiency. Other works, though allowing unbounded delays, impose strict conditions on the underlying fixed-point operator, resulting in limited applications. In this paper, convergence is established under unbounded delays, which can be either stochastic or deterministic. The proposed step sizes are more practical and larger than those in the existing work. The step size adapts to the delay distribution or the current delay being experienced in the system, instead of being limited by worst-case scenario delays. New Lyapunov functions, which are the key to analyzing asynchronous algorithms, are generated to obtain our results. A general strategy for generating Lyapunov functions is presented, which may find application in convergence analyses of other algorithms. A set of applicable optimization algorithms with large-scale applications are given, including machine learning and scientific computing algorithms.
The arithmetic of curves defined by iteration

We show how the size of the Galois groups of iterates of a quadratic polynomial $f(x)$ can be parametrized by certain rational points on the curves $C_n:y^2=f^n(x)$ and their quadratic twists. To that end, we study the arithmetic of such curves over global and finite fields, translating key problems in the arithmetic of polynomial iteration into a geometric framework. This point of view has several dynamical applications. For instance, we establish a maximality theorem for the Galois groups of the fourth iterate of quadratic polynomials $x^2+c$, using techniques in the theory of rational points on curves. Moreover, we show that the Hall-Lang conjecture on integral points of elliptic curves implies a Serre-type finite index result for these dynamical Galois groups, and we use conjectural bounds for the Mordell curves to predict the index in the still unknown case when $f(x)=x^2+3$. Finally, we provide evidence that these curves defined by iteration have geometrical significance, as we construct a family of curves whose rational points we completely determine and whose geometrically simple Jacobians have complex multiplication and positive rank.
Taelman L -values for Drinfeld modules over Tate algebras

In the present paper, we investigate Taelman L-values corresponding to Drinfeld modules over Tate algebras of arbitrary rank. Using our results, we also introduce an L-series converging in Tate algebras which can be seen as a generalization of Pellarin L-series.
Client-side straggler-aware I/O scheduler for object-based parallel file systems

Abstract Object-based parallel file systems have emerged as promising storage solutions for high-performance computing (HPC) systems. Despite the fact that object storage provides a flexible interface, scheduling highly concurrent I/O requests that access a large number of objects still remains as a challenging problem, especially in the case when stragglers (storage servers that are significantly slower than others) exist in the system. An efficient I/O scheduler needs to avoid possible stragglers to achieve low latency and high throughput. In this paper, we introduce a log-assisted straggler-aware I/O scheduling to mitigate the impact of storage server stragglers. The contribution of this study is threefold. First, we introduce a client-side, log-assisted, straggler-aware I/O scheduler architecture to tackle the storage straggler issue in HPC systems. Second, we present three scheduling algorithms that can make efficient decision for scheduling I/Os while avoiding stragglers based on such an architecture. Third, we evaluate the proposed I/O scheduler using simulations, and the simulation results have confirmed the promise of the newly introduced straggler-aware I/O scheduler.
Groups with Exactly Two Supercharacter Theories

ABSTRACTIn this paper, we classify those finite groups with exactly two supercharacter theories. We show that the solvable groups with two supercharacter theories are ℤ3 and S3. We also show that the only nonsolvable group with two supercharacter theories is Sp(6,2).
Derivative free optimization via repeated classification

We develop an algorithm for minimizing a function using $n$ batched function value measurements at each of $T$ rounds by using classifiers to identify a function's sublevel set. We show that sufficiently accurate classifiers can achieve linear convergence rates, and show that the convergence rate is tied to the difficulty of active learning sublevel sets. Further, we show that the bootstrap is a computationally efficient approximation to the necessary classification scheme. The end result is a computationally efficient derivative-free algorithm requiring no tuning that consistently outperforms other approaches on simulations, standard benchmarks, real-world DNA binding optimization, and airfoil design problems whenever batched function queries are natural.
Self-confirming Games: Unawareness, Discovery, and Equilibrium.

Equilibrium notions for games with unawareness in the literature cannot be interpreted as steady-states of a learning process because players may discover novel actions during play. In this sense, many games with unawareness are "self-destroying" as a player's representation of the game must change after playing it once. We define discovery processes where at each state there is an extensive-form game with unawareness that together with the players' play determines the transition to possibly another extensive-form games with unawareness in which players are now aware of actions that they have previously discovered. A discovery process is rationalizable if players play extensive-form rationalizable strategies in each game with unawareness. We show that for any game with unawareness there is a rationalizable discovery process that leads to a self-confirming game that possesses an extensive-form rationalizable self-confirming equilibrium. This notion of equilibrium can be interpreted as steady-state of a learning and discovery process.
Many-broadcast channels: Definition and capacity in the degraded case

Classical multiuser information theory studies the fundamental limits of models with a fixed (often small) number of users as the coding blocklength goes to infinity. Motivated by emerging systems with a massive number of users, this paper studies the new many-user paradigm, where the number of users is allowed to grow with the blocklength. The focus of this paper is the degraded many-broadcast channel model, whose number of users may grow as fast as linearly with the blocklength. A notion of capacity in terms of message length is defined and an example of Gaussian degraded many-broadcast channel is studied. In addition, a numerical example for the Gaussian degraded many-broadcast channel with fixed transmit power constraint is solved, where every user achieves strictly positive message length asymptotically.
Differential forms, fluids, and finite models

By rewriting the Navier-Stokes equation in terms of differential forms we give a formulation which is abstracted and reproduced in a finite dimensional setting. We give two examples of these finite models and, in the latter case, prove some approximation results. Some useful properties of these finite models are derived.
The Friedrichs extension for elliptic wedge operators of second order

Let ${\mathcal M}$ be a smooth compact manifold whose boundary is the total space of a fibration ${\mathcal N}\to {\mathcal Y}$ with compact fibers, let $E\to{\mathcal M}$ be a vector bundle. Let \begin{equation} A:C_c^\infty( \overset{\,\,\circ} {\mathcal M};E)\subset x^{-\nu} L^2_b({\mathcal M};E)\to x^{-\nu} L^2_b({\mathcal M};E) $ \tag*{(†)} \end{equation} be a second order elliptic semibounded wedge operator. Under certain mild natural conditions on the indicial and normal families of $A$, the trace bundle of $A$ relative to $\nu$ splits as a direct sum ${\mathscr T}={\mathscr T}_F\oplus{\mathscr T}_{aF}$ and there is a natural map ${\mathfrak P} :C^\infty({\mathcal Y};{\mathscr T}_F)\to C^\infty( \overset{\,\,\circ} {\mathcal M};E)$ such that $C^\infty_{{\mathscr T}_F}({\mathcal M};E)={\mathfrak P} (C^\infty({\mathcal Y};{\mathscr T}_F)) +\dot C^\infty({\mathcal M};E)\subset {\mathcal D}_{\max}(A)$. It is shown that the closure of $A$ when given the domain $C^\infty_{{\mathscr T}_F}({\mathcal M};E)$ is the Friedrichs extension of (†) and that this extension is a Fredholm operator with compact resolvent. Also given are theorems pertaining the structure of the domain of the extension which completely characterize the regularity of its elements at the boundary.
On the Conditional Logic of Simulation Models

We propose analyzing conditional reasoning by appeal to a notion of intervention on a simulation program, formalizing and subsuming a number of approaches to conditional thinking in the recent AI literature. Our main results include a series of axiomatizations, allowing comparison between this framework and existing frameworks (normality-ordering models, causal structural equation models), and a complexity result establishing NP-completeness of the satisfiability problem. Perhaps surprisingly, some of the basic logical principles common to all existing approaches are invalidated in our causal simulation approach. We suggest that this additional flexibility is important in modeling some intuitive examples.
The anomalous transport of axial charge: topological vs non-topological fluctuations

Axial charge imbalance is an essential ingredient in novel effects associated with chiral anomaly such as chiral magnetic effects (CME). In a non-Abelian plasma with chiral fermions, local axial charge can be generated a) by topological fluctuations which would create domains with non-zero winding number b) by conventional non-topological thermal fluctuations. We provide a holographic evaluations of medium’s response to dynamically generated axial charge density in hydrodynamic limit and examine if medium’s response depends on the microscopic origins of axial charge imbalance. We show a local domain with non-zero winding number would induce a non-dissipative axial current due to chiral anomaly. We illustrate holographically that a local axial charge imbalance would be damped out with the damping rate related to Chern-Simon diffusive constant. By computing chiral magnetic current in the presence of dynamically generated axial charge density, we found that the ratio of CME current over the axial charge density is independent of the origin of axial charge imbalance in low frequency and momentum limit. Finally, a stochastic hydrodynamic equation of the axial charge is formulated by including both types of fluctuations.
Substrate Affinity and Specificity of the ScSth1p Bromodomain Are Fine-Tuned for Versatile Histone Recognition

Bromodomains recognize a wide range of acetylated lysines in histones and other nuclear proteins. Substrate specificity is critical for their biological function and arises from unique acetyl-lysine binding sites formed by variable loop regions. Here, we analyzed substrate affinity and specificity of the yeast ScSth1p bromodomain, an essential component of the "Remodels the Structure of Chromatin" complex, and found that the wild-type bromodomain preferentially recognizes H3K14ac and H4K20ac peptides. Mutagenesis studies-guided by our crystal structure determined at 2.7-A resolution-revealed loop residues Ser1276 and Trp1338 as key determinants for such interactions. Strikingly, point mutations of each of these residues substantially increased peptide binding affinity and selectivity, respectively. Our data demonstrate that the ScSth1p bromodomain is not optimized for binding to an individual acetylation mark, but fine-tuned for interactions with several such modifications, consistent with the versatile and multivalent nature of histone recognition by reader modules such as bromodomains.
Attacking Automatic Video Analysis Algorithms: A Case Study of Google Cloud Video Intelligence API

Due to the growth of video data on Internet, automatic video analysis has gained a lot of attention from academia as well as companies such as Facebook, Twitter and Google. In this paper, we examine the robustness of video analysis algorithms in adversarial settings. Specifically, we propose targeted attacks on two fundamental classes of video analysis algorithms, namely video classification and shot detection. We show that an adversary can subtly manipulate a video in such a way that a human observer would perceive the content of the original video, but the video analysis algorithm will return the adversary's desired outputs. We then apply the attacks on the recently released Google Cloud Video Intelligence API. The API takes a video file and returns the video labels (objects within the video), shot changes (scene changes within the video) and shot labels (description of video events over time). Through experiments, we show that the API generates video and shot labels by processing only the first frame of every second of the video. Hence, an adversary can deceive the API to output only her desired video and shot labels by periodically inserting an image into the video at the rate of one frame per second. We also show that the pattern of shot changes returned by the API can be mostly recovered by an algorithm that compares the histograms of consecutive frames. Based on our equivalent model, we develop a method for slightly modifying the video frames, in order to deceive the API into generating our desired pattern of shot changes. We perform extensive experiments with different videos and show that our attacks are consistently successful across videos with different characteristics. At the end, we propose introducing randomness to video analysis algorithms as a countermeasure to our attacks.
Stable Distribution Alignment Using the Dual of the Adversarial Distance

Methods that align distributions by minimizing an adversarial distance between them have recently achieved impressive results. However, these approaches are difficult to optimize with gradient descent and they often do not converge well without careful hyperparameter tuning and proper initialization. We investigate whether turning the adversarial min-max problem into an optimization problem by replacing the maximization part with its dual improves the quality of the resulting alignment and explore its connections to Maximum Mean Discrepancy. Our empirical results suggest that using the dual formulation for the restricted family of linear discriminators results in a more stable convergence to a desirable solution when compared with the performance of a primal min-max GAN-like objective and an MMD objective under the same restrictions. We test our hypothesis on the problem of aligning two synthetic point clouds on a plane and on a real-image domain adaptation problem on digits. In both cases, the dual formulation yields an iterative procedure that gives more stable and monotonic improvement over time.
Deep visual perception for dynamic walking on discrete terrain

Dynamic bipedal walking on discrete terrain, like stepping stones, is a challenging problem requiring feedback controllers to enforce safety-critical constraints. To enforce such constraints in real-world experiments, fast and accurate perception for foothold detection and estimation is needed. In this work, a deep visual perception model is designed to accurately estimate step length of the next step, which serves as input to the feedback controller to enable vision-in-the-loop dynamic walking on discrete terrain. In particular, a custom convolutional neural network architecture is designed and trained to predict step length to the next foothold using a sampled image preview of the upcoming terrain at foot impact. The visual input is offered only at the beginning of each step and is shown to be sufficient for the job of dynamically stepping onto discrete footholds. Through extensive numerical studies, we show that the robot is able to successfully autonomously walk for over 100 steps without failure on a discrete terrain with footholds randomly positioned within a step length range of [45 : 85] centimeters.
Local cohomology and F-stability

Abstract We study the relationship between the Frobenius stability of an Artinian module over an F-injective ring and its stable part.
Information Complexity Is Computable

The information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function f to within any additive error epsilon > 0, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f.
Blockwise Parallel Decoding for Deep Autoregressive Models

Deep autoregressive sequence-to-sequence models have demonstrated impressive performance across a wide variety of tasks in recent years. While common architecture classes such as recurrent, convolutional, and self-attention networks make different trade-offs between the amount of computation needed per layer and the length of the critical path at training time, generation still remains an inherently sequential process. To overcome this limitation, we propose a novel blockwise parallel decoding scheme in which we make predictions for multiple time steps in parallel then back off to the longest prefix validated by a scoring model. This allows for substantial theoretical improvements in generation speed when applied to architectures that can process output sequences in parallel. We verify our approach empirically through a series of experiments using state-of-the-art self-attention models for machine translation and image super-resolution, achieving iteration reductions of up to 2x over a baseline greedy decoder with no loss in quality, or up to 7x in exchange for a slight decrease in performance. In terms of wall-clock time, our fastest models exhibit real-time speedups of up to 4x over standard greedy decoding.
Simplified Khovanov–Rozansky chain complexes of open 2-braids

Abstract Motivated by the works of Krasner (2009) [8] and Lobb [11] , we simplify the Khovanov–Rozansky chain complexes of open 2-braids. As an application, we show that, for a knot containing a “long” 2-braid, the sl ( N ) Rasmussen invariant of this knot depends linearly on the length of this 2-braid. We refine this result for ( 2 , 2 k + 1 ) cable knots and, as a simple corollary, compute the sl ( 2 ) Rasmussen invariants of ( 2 , 2 k + 1 ) cables of slice and amphicheiral knots.
Critical points of master functions and integrable hierarchies

Abstract We consider the population of critical points generated from the trivial critical point of the master function with no variables and associated with the trivial representation of the affine Lie algebra sl ˆ N . We show that the critical points of this population define rational solutions of the equations of the mKdV hierarchy associated with sl ˆ N . We also construct critical points from suitable N-tuples of tau-functions. The construction is based on a Wronskian identity for tau-functions. In particular, we construct critical points from suitable N-tuples of Schur polynomials and prove a Wronskian identity for Schur polynomials.
Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication

Understanding the query complexity for testing linear-invariant properties has been a central open problem in the study of algebraic property testing. Triangle-freeness in Boolean functions is a simple property whose testing complexity is unknown. Three Boolean functions f1, f2 and f3, mapping {0,1}^k to {0,1}, are said to be triangle free if there is no x, y in {0,1}^k such that f1(x) = f2(y) = f3(x + y) = 1. This property is known to be strongly testable (Green 2005), but the number of queries needed is upper-bounded only by a tower of twos whose height is polynomial in 1 / epsislon, where epsislon is the distance between the tested function triple and triangle-freeness, i.e., the minimum fraction of function values that need to be modified to make the triple triangle free. A lower bound of (1 / epsilon)^2.423 for any one-sided tester was given by Bhattacharyya and Xie (2010). In this work we improve this bound to (1 / epsilon)^6.619. Interestingly, we prove this by way of a combinatorial construction called uniquely solvable puzzles that was at the heart of Coppersmith and Winograd's renowned matrix multiplication algorithm.
On the existence of solutions to stochastic quasi-variational inequality and complementarity problems

Variational inequality problems allow for capturing an expansive class of problems, including convex optimization problems, convex Nash games and economic equilibrium problems, amongst others. Yet in most practical settings, such problems are complicated by uncertainty, motivating the examination of a stochastic generalization of the variational inequality problem and its extensions in which the components of the mapping contain expectations. When the associated sets are unbounded, ascertaining existence requires having access to analytical forms of the expectations. Naturally, in practical settings, such expressions are often difficult to derive, severely limiting the applicability of such an approach. Consequently, our goal lies in developing techniques that obviate the need for integration and our emphasis lies in developing tractable and verifiable sufficiency conditions for claiming existence. We begin by recapping almost-sure sufficiency conditions for stochastic variational inequality problems with single-valued maps provided in our prior work Ravat and Shanbhag (in: Proceedings of the American Control Conference (ACC), 2010), Ravat and Shanbhag (SIAM J Optim 21: 1168–1199, 2011) and provide extensions to multi-valued mappings. Next, we extend these statements to quasi-variational regimes where maps can be either single or set-valued. Finally, we refine the obtained results to accommodate stochastic complementarity problems where the maps are either general or co-coercive. The applicability of our results is demonstrated on practically occuring instances of stochastic quasi-variational inequality problems and stochastic complementarity problems, arising as nonsmooth generalized Nash-Cournot games and power markets, respectively.
Equivalence for Rank-Metric and Matrix Codes and Automorphism Groups of Gabidulin Codes

For a growing number of applications, such as cellular, peer-to-peer, and sensor networks, efficient error-free transmission of data through a network is essential. Toward this end, Kotter and Kschischang propose the use of subspace codes to provide error correction in the network coding context. The primary construction for subspace codes is the lifting of rank-metric or matrix codes, a process that preserves the structural and distance properties of the underlying code. Thus, to characterize the structure and error-correcting capability of these subspace codes, it is valuable to perform such a characterization of the underlying rank-metric and matrix codes. This paper lays a foundation for this analysis through a framework for classifying rank-metric and matrix codes based on their structure and distance properties. To enable this classification, we extend work by Berger on equivalence for rank-metric codes to define a notion of equivalence for matrix codes, and we characterize the group structure of the collection of maps that preserve such equivalence. We then compare the notions of equivalence for these two related types of codes and show that matrix equivalence is strictly more general than rank-metric equivalence. Finally, we characterize the set of equivalence maps that fix the prominent class of rank-metric codes known as Gabidulin codes. In particular, we give a complete characterization of the rank-metric automorphism group of Gabidulin codes, correcting work by Berger, and give a partial characterization of the matrix-automorphism group of the expanded matrix codes that arise from Gabidulin codes.
Counterexamples to local monomialization in positive characteristic

A local monomialization of an algebraic map between varieties along a valuation is a sequence of blowups of nonsingular subvarieties along the valuation in the domain and target of the map such that the resulting map can be expressed by monomial inclusion in a suitable sense. In this paper we give examples showing that a local monomialization does not always exist over fields of positive characteristic. It was shown in earlier work of the author that a local monomialization always exists over fields of characteristic zero.
Explaining Wrong Queries Using Small Examples

For testing the correctness of SQL queries, a standard practice is to execute the query in question on some test database instance and compare its result with that of the correct query. Given two queries $Q_1$ and $Q_2$, we say that a database instance D is a counterexample (for $Q_1$ and $Q_2$) if $Q_1(D)$ differs from $Q_2(D)$; such a counterexample can serve as an explanation of why $Q_1$ and $Q_2$ are not equivalent. While the test database instance may serve as a counterexample, it may be too large or complex to understand where the inequivalence arises. Therefore, in this paper, given a known counterexample D for $Q_1$ and $Q_2$, we aim to find the smallest counterexample $D' \subseteq D$ where $Q_1(D') \neq Q_2(D')$. The problem in general is NP-hard. Drawing techniques from provenance and constraint solving, we develop a suite of algorithms for finding small counterexamples for different classes of queries, including those involving negation and aggregation. We evaluate the effectiveness and scalability of our algorithms on student queries from an undergraduate database course, and on queries from the TPC-H benchmark. We also report a user study from the course where we deployed our tool to help students with an assignment on relational algebra.
Remarks on the Böttcher-Wenzel inequality

Abstract In 2005, Bottcher and Wenzel raised the conjecture that if X , Y are real square matrices, then | | XY - YX | | 2 ≤ 2 | | X | | 2 | | Y | | 2 , where | | · | | is the Frobenius norm. Various proofs of this conjecture were found in the last few years by several authors. We here give another proof. This proof is highly conceptual and requires minimal computation. We also briefly discuss related inequalities, in particular, the classical Chern-do Camo–Kobayashi inequality.
Multiband models for field theories with anomalous current dimension

We give simple examples of weakly coupled or free quantum mechanical systems that exhibit scale invariance with an anomalous dimension for a conserved current. In these models scaling as an exact symmetry only emerges in a large N limit, but it remains as an approximate symmetry even at finite N.
Ray RLlib: A Composable and Scalable Reinforcement Learning Library

Reinforcement learning (RL) algorithms involve the deep nesting of distinct components, where each component typically exhibits opportunities for distributed computation. Current RL libraries offer parallelism at the level of the entire program, coupling all the components together and making existing implementations difficult to extend, combine, and reuse. We argue for building composable RL components by encapsulating parallelism and resource requirements within individual components, which can be achieved by building on top of a flexible task-based programming model. We demonstrate this principle by building Ray RLLib on top of Ray and show that we can implement a wide range of state-of-the-art algorithms by composing and reusing a handful of standard components. This composability does not come at the cost of performance --- in our experiments, RLLib matches or exceeds the performance of highly optimized reference implementations. Ray RLLib is available as part of Ray at this https URL
The topology of the space of J-holomorphic maps to CP 2

The purpose of this paper is to generalize a theorem of Segal proving that the space of holomorphic maps from a Riemann surface to a complex projective space is homology equivalent to the corresponding space of continuous maps through a range of dimensions increasing with degree. We will address if a similar result holds when other almost-complex structures are put on a projective space. For any compatible almost complex structure J on CP 2 , we prove that the inclusion map from the space of J‐holomorphic maps to the space of continuous maps induces a homology surjection through a range of dimensions tending to infinity with degree. The proof involves comparing the scanning map of topological chiral homology with analytic gluing maps for J‐holomorphic curves . This is an extension of the author’s work regarding genus-zero case. 53D05; 55P48
Theoretical guarantees for sampling and inference in generative models with latent diffusions

We introduce and study a class of probabilistic generative models, where the latent object is a finite-dimensional diffusion process on a finite time interval and the observed variable is drawn conditionally on the terminal point of the diffusion. We make the following contributions: We provide a unified viewpoint on both sampling and variational inference in such generative models through the lens of stochastic control. We quantify the expressiveness of diffusion-based generative models. Specifically, we show that one can efficiently sample from a wide class of terminal target distributions by choosing the drift of the latent diffusion from the class of multilayer feedforward neural nets, with the accuracy of sampling measured by the Kullback-Leibler divergence to the target distribution. Finally, we present and analyze a scheme for unbiased simulation of generative models with latent diffusions and provide bounds on the variance of the resulting estimators. This scheme can be implemented as a deep generative model with a random number of layers.
Reducing Radiation Damage in Soft Matter with Femtosecond-Timed Single-Electron Packets

Despite the development of a myriad of mitigation methods, radiation damage continues to be a major limiting factor in transmission electron microscopy. Intriguing results have been reported using ...
A path-integral approximation for non-linear diffusions

Using the path-integral formalism we develop an accurate and easy-to-compute semi-analytical approximation to transition probabilities and Arrow–Debreu densities for arbitrary diffusions. We illust...
Fintech and banking: What do we know?

Abstract This paper is a review of the literature on fintech and its interaction with banking. Included in fintech are innovations in payment systems (including cryptocurrencies), credit markets (including P2P lending), and insurance, with Blockchain-assisted smart contracts playing a role. The paper provides a definition of fintech, examines some statistics and stylized facts, and then reviews the theoretical and empirical literature. The review is organized around four main research questions. The paper summarizes our knowledge on these questions and concludes with questions for future research.
Ask not what AI can do, but what AI should do: Towards a framework of task delegability

While artificial intelligence (AI) holds promise for addressing societal challenges, issues of exactly which tasks to automate and to what extent to do so remain understudied. We approach this problem of task delegability from a human-centered perspective by developing a framework on human perception of task delegation to AI. We consider four high-level factors that can contribute to a delegation decision: motivation, difficulty, risk, and trust. To obtain an empirical understanding of human preferences in different tasks, we build a dataset of 100 tasks from academic papers, popular media portrayal of AI, and everyday life, and administer a survey based on our proposed framework. We find little preference for full AI control and a strong preference for machine-in-the-loop designs, in which humans play the leading role. Among the four factors, trust is the most correlated with human preferences of optimal human-machine delegation. This framework represents a first step towards characterizing human preferences of AI automation across tasks. We hope this work encourages future efforts towards understanding such individual attitudes; our goal is to inform the public and the AI research community rather than dictating any direction in technology development.
Accurate and efficient cell lineage tree inference from noisy single cell data: the maximum likelihood perfect phylogeny approach

Motivation Cells in an organism share a common evolutionary history, called cell lineage tree. Cell lineage tree can be inferred from single cell genotypes at genomic variation sites. Cell lineage tree inference from noisy single cell data is a challenging computational problem. Most existing methods for cell lineage tree inference assume uniform uncertainty in genotypes. A key missing aspect is that real single cell data usually has non-uniform uncertainty in individual genotypes. Moreover, existing methods are often sampling based and can be very slow for large data. Results In this article, we propose a new method called ScisTree, which infers cell lineage tree and calls genotypes from noisy single cell genotype data. Different from most existing approaches, ScisTree works with genotype probabilities of individual genotypes (which can be computed by existing single cell genotype callers). ScisTree assumes the infinite sites model. Given uncertain genotypes with individualized probabilities, ScisTree implements a fast heuristic for inferring cell lineage tree and calling the genotypes that allow the so-called perfect phylogeny and maximize the likelihood of the genotypes. Through simulation, we show that ScisTree performs well on the accuracy of inferred trees, and is much more efficient than existing methods. The efficiency of ScisTree enables new applications including imputation of the so-called doublets. Availability and implementation The program ScisTree is available for download at: https://github.com/yufengwudcs/ScisTree. Supplementary information Supplementary data are available at Bioinformatics online.
Pretraining by Backtranslation for End-to-end ASR in Low-Resource Settings

We explore training attention-based encoder-decoder ASR in low-resource settings. These models perform poorly when trained on small amounts of transcribed speech, in part because they depend on having sufficient target-side text to train the attention and decoder networks. In this paper we address this shortcoming by pretraining our network parameters using only text-based data and transcribed speech from other languages. We analyze the relative contributions of both sources of data. Across 3 test languages, our text-based approach resulted in a 20% average relative improvement over a text-based augmentation technique without pretraining. Using transcribed speech from nearby languages gives a further 20-30% relative reduction in character error rate.
The Maximum Exposure Problem.

Given a set of points P and axis-aligned rectangles R in the plane, a point p in P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k^2) rectangles, we can expose at least Omega(1/k) of the optimal number of points.