cssi/SciSciGPT-SciSciNet huggingface dataset:
Flexibility Reserve in Power Systems: Definition and Stochastic Multi-Fidelity Optimization

This paper defines flexibility reserve trajectory as a single reserve product that not only supplies the energy imbalance in real-time operation but also the resulting ramping requirements by embedding the flexible ramping trajectories as time derivative of the reserve trajectories. Further, a stochastic optimization model is proposed for multi-fidelity co-optimization of energy and flexibility reserve in day-ahead power systems operation. The proposed model integrates operation decisions with different levels of modeling fidelity in a single stochastic optimization problem. More specifically, day-ahead energy trajectories, day-ahead flexibility reserve capacity trajectories, and real-time flexibility reserve deployment trajectories are modeled by Bernstein polynomials with different degrees as required to match the load and renewable generation with different levels of variability in day-ahead and real-time operations. The proposed model is implemented on the IEEE reliability test system using load and solar generation data of California ISO, where the numerical results demonstrate that the proposed model schedules a reserve capacity that more accurately matches the real-time energy imbalance and ramping requirements of net-load, while reducing the total operation cost of the system.
A construction of slice knots via annulus modifications

Abstract We define an operation on a homology B 4 that we call an n-twist annulus modification. We give a new construction of smoothly slice knots and exotically slice knots via n-twist annulus modifications. As an application, we present a new example of a smoothly slice knot with non-slice derivatives. Such examples were first discovered by Cochran and Davis. Also, we relate n-twist annulus modifications to n-fold annulus twists which was first introduced by Osoinach and has been used by Abe and Tange to construct smoothly slice knots. Furthermore we show that any exotic slice disk can be obtained by an annulus modification performed on some exotic slice disk bounding the unknot.
Nonequilibrium Fluctuations in Small Systems: From Physics to Biology

In this paper I am presenting an overview on several topics related to nonequilibrium fluctuations in small systems. I start with a general discussion about fluctuation theorems and applications to physical examples extracted from physics and biology: a bead in an optical trap and single molecule force experiments. Next I present a general discussion on path thermodynamics and consider distributions of work/heat fluctuations as large deviation functions. Then I address the topic of glassy dynamics from the perspective of nonequilibrium fluctuations due to small cooperatively rearranging regions. Finally, I conclude with a brief digression on future perspectives.
Personalized neural language models for real-world query auto completion.

Query auto completion (QAC) systems are a standard part of search engines in industry, helping users formulate their query. Such systems update their suggestions after the user types each character, predicting the user’s intent using various signals – one of the most common being popularity. Recently, deep learning approaches have been proposed for the QAC task, to specifically address the main limitation of previous popularity-based methods: the inability to predict unseen queries. In this work we improve previous methods based on neural language modeling, with the goal of building an end-to-end system. We particularly focus on using real-world data by integrating user information for personalized suggestions when possible. We also make use of time information and study how to increase diversity in the suggestions while studying the impact on scalability. Our empirical results demonstrate a marked improvement on two separate datasets over previous best methods in both accuracy and scalability, making a step towards neural query auto-completion in production search engines.
On the Properties of Neutrinos

This article reviews our present understanding of neutrino properties with a particular emphasis on observable differences between Majorana and Dirac neutrinos. We summarize current and future expe...
HIGHER ORDER SCHWARZIANS FOR GEODESIC FLOWS, MOMENT SEQUENCES AND THE RADIUS OF ADAPTED COMPLEXIFICATIONS

In the first part of the paper, comprising section 1 through 6, we introduce a sequence of functions in the tangent bundle TM of any smooth two-dimensional manifold M with smooth Riemannian metric g that correspond to the higher order Schwarzians of the linearized geodesic flow. With these functions and a classical theorem of Loewner on analytic continuation we are able to characterize the existence of the adapted complex structure induced by g on the set T^RM of vectors in TM of length up to R, equivalently for M compact, to the existence of a Grauert tube of radius R in terms of infinite Hankel matrices involving these Schwarzian functions. The basic characterization so obtained can be expressed as a sequence of differential inequalities of increasing order polynomial in the covariant derivatives of the Gauss curvature on M and in {\pi}/R that should be regarded as the higher order versions of a curvature inequality by L. Lempert and R. Sz\"oke. The second part of the paper, sections 7 through 11, includes a discussion of the rank of the infinite Hankel matrix of the Schwarzians from part 1 and of new Schwarzians defined now for purely imaginary radius, as well as some computations and examples. A characterization of the existence of the adapted structure on T^RM in terms of moment sequences with parameters R and v in TM is also noted.
Cell-cycle coupled expression minimizes random fluctuations in gene product levels

Expression of many genes varies as a cell transitions through different cell-cycle stages. How coupling between stochastic expression and cell cycle impacts cell-to-cell variability (noise) in the level of protein is not well understood. We analyze a model, where a stable protein is synthesized in random bursts, and the frequency with which bursts occur varies within the cell cycle. Formulas quantifying the extent of fluctuations in the protein copy number are derived and decomposed into components arising from the cell cycle and stochastic processes. The latter stochastic component represents contributions from bursty expression and errors incurred during partitioning of molecules between daughter cells. These formulas reveal an interesting trade-off: cell-cycle dependencies that amplify the noise contribution from bursty expression also attenuate the contribution from partitioning errors. We investigate existence of optimum strategies for coupling expression to the cell cycle that minimize the stochastic component. Intriguingly, results show that a zero production rate throughout the cell cycle, with expression only occurring just before cell division minimizes noise from bursty expression for a fixed mean protein level. In contrast, the optimal strategy in the case of partitioning errors is to make the protein just after cell division. We provide examples of regulatory proteins that are expressed only towards the end of cell cycle, and argue that such strategies enhance robustness of cell-cycle decisions to the intrinsic stochasticity of gene expression.
Are There Really Two Different Bell’s Theorems?

This is a polemical response to Howard Wiseman’s recent paper, “The two Bell’s theorems of John Bell”. Wiseman argues that, in 1964, Bell established a conflict between the quantum mechanical predictions and the joint assumptions of determinism and (what is now usually known as) “parameter independence”. Only later, in 1976, did Bell, according to Wiseman, first establish a conflict between the quantum mechanical predictions and locality alone (in the specific form that Bell would sometimes call “local causality”). Thus, according to Wiseman, the long-standing disagreements about what, exactly, Bell’s theorem does and does not prove can be understood largely as miscommunications resulting from the fact that there are really two quite distinct “Bell’s theorems”. My goal here is to lay out what Wiseman briefly describes as an “alternate reading” of Bell’s 1964 paper, according to which (quoting Wiseman here) “the first paragraph of Bell’s ‘Formulation’ section [should be seen] as an essential part of his 1964 theorem, the first part of a two-part argument.” I will argue in particular that this “alternate reading” is the correct way to understand Bell’s 1964 paper and that Wiseman’s reading is strongly inconsistent with the available evidence.
A Proof of Onsager's Conjecture

For any α < 1/3, we construct weak solutions to the 3D incompressible Euler equations in the class C_tC_^xα that have nonempty, compact support in time on R × T^3 and therefore fail to conserve the total kinetic energy. This result, together with the proof of energy conservation for α < 1/3 due to [Eyink] and [Constantin, E, Titi], solves Onsager's conjecture that the exponent α = 1/3 marks the threshold for conservation of energy for weak solutions in the class L_t^∞C_x^α. The previous best results were solutions in the classC_tC_x^α for α < 1/5, due to [Isett], and in the class L_t^1C_x^α for α < 1/3 due to [Buckmaster, De Lellis, Szekelyhidi], both based on the method of convex integration developed for the incompressible Euler equations by [De Lellis, Szekelyhidi]. The present proof combines the method of convex integration and a new “Gluing Approximation” technique. The convex integration part of the proof relies on the “Mikado flows” introduced by [Daneri, Szekelyhidi] and the framework of estimates developed in the author's previous work.
Regularity lemma for distal structures

It is known that families of graphs with a semialgebraic edge relation of bounded complexity satisfy much stronger regularity properties than arbitrary graphs, and that they can be decomposed into very homogeneous semialgebraic pieces up to a small error (e.g., see [33, 2, 16, 18]). We show that similar results can be obtained for families of graphs with the edge relation uniformly definable in a structure satisfying a certain model theoretic property called distality, with respect to a large class of generically stable measures. Moreover, distality characterizes these strong regularity properties. This applies in particular to graphs definable in arbitrary $o$-minimal structures and in $p$-adics.
Unique conditional expectations for abelian C⁎-inclusions

Abstract Let D ⊆ A be an inclusion of unital abelian C ⁎ -algebras. In this note we characterize (in topological terms) when there is a unique conditional expectation E : A → D , at least when A is separable. We also provide the first example of an inclusion with a unique conditional expectation, but multiple pseudo-expectations (in the sense of Pitts).
Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example

We propose a new method, probabilistic divide-and-conquer, for improving the success probability in rejection sampling. For the example of integer partitions, there is an ideal recursive scheme which improves the rejection cost from asymptotically order n 3/4 to a constant. We show other examples for which a non-recursive, one-time application of probabilistic divide-and-conquer removes a substantial fraction of the rejection sampling cost. We also present a variation of probabilistic divide-and-conquer for generating i.i.d. samples that exploits features of the coupon collector's problem, in order to obtain a cost that is sublinear in the number of samples.
Support theorems for the light ray transform on analytic Lorentzian manifolds

We study the weighted ray transform of integrating functions on a Lorentzian manifold over lightlike geodesics. We prove support theorems if the manifold and the weight are analytic.
Semiparametric regression analysis of interval-censored competing risks data.

Summary Interval-censored competing risks data arise when each study subject may experience an event or failure from one of several causes and the failure time is not observed directly but rather is known to lie in an interval between two examinations. We formulate the effects of possibly time-varying (external) covariates on the cumulative incidence or sub-distribution function of competing risks (i.e., the marginal probability of failure from a specific cause) through a broad class of semiparametric regression models that captures both proportional and non-proportional hazards structures for the sub-distribution. We allow each subject to have an arbitrary number of examinations and accommodate missing information on the cause of failure. We consider nonparametric maximum likelihood estimation and devise a fast and stable EM-type algorithm for its computation. We then establish the consistency, asymptotic normality, and semiparametric efficiency of the resulting estimators for the regression parameters by appealing to modern empirical process theory. In addition, we show through extensive simulation studies that the proposed methods perform well in realistic situations. Finally, we provide an application to a study on HIV-1 infection with different viral subtypes.
The moduli space of cubic fourfolds via the period map

We characterize the image of the period map for cubic fourfolds with at worst simple singularities as the complement of an arrangement of hyperplanes in the period space. It follows then that the geometric invariant theory (GIT) compactification of the moduli space of cubic fourfolds is isomorphic to the Looijenga compactification associated to this arrangement. This paper builds on and is a natural continuation of our previous work on the GIT compactification of the moduli space of cubic fourfolds.
$K$-homology and Fredholm operators II: elliptic operators

This is an expository paper which gives a proof of the Atiyah-Singer index theorem for elliptic operators. Specifcally, we compute the geometric K-cycle that corresponds to the analytic K-cycle determined by the operator. This paper and its companion ("K-homology and index theory II: Dirac Operators") was written to clear up basic points about index theory that are generally accepted as valid, but for which no proof has been published. Some of these points are needed for the solution of the Heisenberg-elliptic index problem in our paper "K-homology and index theory on contact manifolds" Acta. Math. 2014.
Background cohomology of a non-compact Kähler G -manifold

For a compact Lie group G we define a regularized version of the Dolbeault cohomology of a G-equivariant holomorphic vector bundles over non-compact Kahler manifolds. The new cohomology is infinite-dimensional, but as a representation of G it decomposes into a sum of irreducible components, each of which appears in it with finite multiplicity. Thus equivariant Betti numbers are well defined. We study various properties of the new cohomology and prove that it satisfies a Kodaira-type vanishing theorem.
Coding of Graphs with Application to Graph Anomaly Detection

This paper has dual aims. First is to develop practical universal coding methods for unlabeled graphs. Second is to use these for graph anomaly detection. The paper develops two coding methods for unlabeled graphs: one based on the degree distribution, the second based on the triangle distribution. It is shown that these are efficient for different types of random graphs, and on real-world graphs. These coding methods is then used for detecting anomalous graphs, based on structure alone. It is shown that anomalous graphs can be detected with high probability.
Finding Intermediate Subgroups

This article describes a practical approach for determining the lattice of subgroups U < V < G between given subgroups U and G, provided the total number of such subgroups is not too large. It builds on existing functionality for element conjugacy, double cosets and maximal subgroups.
Optimal Linear Bernoulli Factories for Small Mean Problems

Suppose a coin with unknown probability p of heads can be flipped as often as desired. A Bernoulli factory for a function f is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability f(p) of heads. Applications include perfect sampling from the stationary distribution of certain regenerative processes. When f is analytic, the problem can be reduced to a Bernoulli factory of the form f(p) = Cp for constant C. Presented here is a new algorithm that for small values of Cp, requires roughly only C coin flips. From information theoretic considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For large values of Cp, the new algorithm can also be used to build a new Bernoulli factory that uses only 80 % of the expected coin flips of the older method. In addition, the new method also applies to the more general problem of a linear multivariate Bernoulli factory, where there are k coins, the kth coin has unknown probability pk of heads, and the goal is to simulate a coin flip with probability C1p1+⋯ + Ckpk of heads.
Separating principles below WKL0

In this paper, we study the Ramsey-type weak Kőnig's Lemma, written RWKL, using a technique introduced by Lerman, Solomon, and the second author. This technique uses iterated forcing to construct an ω-model satisfying one principle T1 but not another T2. The technique often allows one to translate a “one step” construction (building an instance of T2 along with a collection of solutions to each computable instance of T1) into an ω-model separation (building a computable instance of T2 together with a Turing ideal where T1 holds but this instance has no solution). We illustrate this translation by separating d-DNR from DNR (reproving a result of Ambos-Spies, Kjos-Hanssen, Lempp, and Slaman), and then apply this technique to separate RWKL from DNR (which has been shown separately by Bienvenu, Patey, and Shafer).
Filtrations of Totally Reflexive Modules

In this paper, we introduce a subcategory of totally reflexive modules that have a saturated filtration by other totally reflexive modules. We will prove these are precisely the totally reflexive modules with an upper triangular presentation matrix and that such a module has a complete resolution in which every differential can be simultaneously represented by upper triangular matrices.
Approximate joint MAP detection of co-channel signals

We consider joint detection of co-channel signals— specifically, signals which do not possess a natural separability due to, for example, the multiple access technique or the use of multiple antennas. Iterative joint detection and decoding is a well known approach for utilizing the error correction code to improve detection performance. However, the joint maximum a posteriori probability (MAP) detector may be prohibitively complex, especially in a multipath channel. In this paper, we present an approximation to the joint MAP detector motivated by a factor graph model of the received signal. The proposed algorithm is designed to approximate the joint MAP detector as closely as possible within the computational capability of the receiver.
Chief complaint classification with recurrent neural networks.

Abstract Syndromic surveillance detects and monitors individual and population health indicators through sources such as emergency department records. Automated classification of these records can improve outbreak detection speed and diagnosis accuracy. Current syndromic systems rely on hand-coded keyword-based methods to parse written fields and may benefit from the use of modern supervised-learning classifier models. In this paper, we implement two recurrent neural network models based on long short-term memory (LSTM) and gated recurrent unit (GRU) cells and compare them to two traditional bag-of-words classifiers: multinomial naive Bayes (MNB) and a support vector machine (SVM). The MNB classifier is one of only two machine learning algorithms currently being used for syndromic surveillance. All four models are trained to predict diagnostic code groups as defined by Clinical Classification Software, first to predict from discharge diagnosis, and then from chief complaint fields. The classifiers are trained on 3.6 million de-identified emergency department records from a single United States jurisdiction. We compare performance of these models primarily using the F1 score, and we measure absolute model performance to determine which conditions are the most amenable to surveillance based on chief complaint alone. Using discharge diagnoses, the LSTM classifier performs best, though all models exhibit an F1 score above 96.00. Using chief complaints, the GRU performs best (F1 = 47.38), and MNB with bigrams performs worst (F1 = 39.40). We also note that certain syndrome types are easier to detect than others. For example, chief complaints using the GRU model predicts alcohol-related disorders well (F1 = 78.91) but predicts influenza poorly (F1 = 14.80). In all instances, the RNN models outperformed the bag-of-words classifiers suggesting deep learning models could substantially improve the automatic classification of unstructured text for syndromic surveillance.
Amorphous complexions enable a new region of high temperature stability in nanocrystalline Ni-W

Abstract Solute segregation is used to limit grain growth in nanocrystalline metals, but this stabilization often breaks down at high temperatures. Amorphous intergranular films can form in certain alloys at sufficiently high temperatures, providing a possible alternative route to lower grain boundary energy and therefore limit grain growth. In this study, nanocrystalline Ni W that is annealed at temperatures of 1000 °C and above, then rapidly quenched, is found to contain amorphous intergranular films. These complexions lead to a new, unexpected region of nanocrystalline stability at elevated temperatures.
Poisson Traces for Symmetric Powers of Symplectic Varieties

We compute the space of Poisson traces on symmetric powers of affine symplectic varieties. In the case of symplectic vector spaces, we also consider the quotient by the diagonal translation action, which includes the quotient singularities T ∗ C n−1 /Sn associated to the type A Weyl group Sn and its reflection representation C n−1 . We also compute the full structure of the natural D-module, previously defined by the authors, whose solution space over algebraic distributions identifies with the space of Poisson traces. As a consequence, we deduce bounds on the numbers of finite-dimensional irreducible representations and prime ideals of quantizations of these varieties. Finally, motivated by these results, we pose conjectures on symplectic resolutions, and give related examples of the natural D-module. In an appendix, the second author computes the Poisson traces and associated D-module for the quotients T ∗ C n /Dn associated to type D Weyl groups. In a second appendix, the same author provides a direct proof of one of the main theorems.
Global optimality of local search for low rank matrix recovery

We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent from random initialization.
Higher equivariant excision

Abstract We develop a theory of Goodwillie calculus for functors between G-equivariant homotopy theories, where G is a finite group. We construct J-excisive approximations for any finite G-set J. These combine into a poset, the Goodwillie tree, that extends the classical Goodwillie tower. We prove convergence results for the tree of a functor on pointed G-spaces that commutes with fixed-points, and we reinterpret the Tom Dieck-splitting as an instance of a more general splitting phenomenon that occurs for the fixed-points of the equivariant derivatives of these functors. As our main example we describe the layers of the tree of the identity functor in terms of the equivariant Spanier–Whitehead duals of the partition complexes.
Fluctuation analysis and short time asymptotics for multiple scales diffusion processes

We consider the limiting behavior of fluctuations of small noise diffusions with multiple scales around their homogenized deterministic limit. We allow full dependence of the coefficients on the slow and fast motion. These processes arise naturally when one is interested in short time asymptotics of multiple scale diffusions. We do not make periodicity assumptions, but we impose conditions on the fast motion to guarantee ergodicity. Depending on the order of interaction between the fast scale and the size of the noise, we get different behavior. In certain cases additional drift terms arise in the limiting process, which are explicitly characterized. These results provide a better approximation to the limiting behavior of such processes when compared to the law of large numbers homogenization limit.
On the convergence time of the drift-plus-penalty algorithm for strongly convex programs

This paper studies the convergence time of the drift-plus-penalty algorithm for strongly convex programs. The drift-plus-penalty algorithm was originally developed to solve more general stochastic optimization and is closely related to the dual subgradient algorithm when applied to deterministic convex programs. For general convex programs, the convergence time of the drift-plus-penalty algorithm is known to be O(1/e2). This paper shows that the convergence time for general strongly convex programs is O(1/e). This paper also proposes a new variation of the drift-plus-penalty algorithm, the drift-plus-penalty algorithm with shifted running averages, and shows that if the dual function of the strongly convex program is smooth and locally quadratic then the convergence time of the new algorithm is O(1/e2/3). The convergence time analysis is further verified by numerical experiments.
Autoregressive Quantile Networks for Generative Modeling

We introduce autoregressive implicit quantile networks (AIQN), a fundamentally different approach to generative modeling than those commonly used, that implicitly captures the distribution using quantile regression. AIQN is able to achieve superior perceptual quality and improvements in evaluation metrics, without incurring a loss of sample diversity. The method can be applied to many existing models and architectures. In this work we extend the PixelCNN model with AIQN and demonstrate results on CIFAR-10 and ImageNet using Inception score, FID, non-cherry-picked samples, and inpainting results. We consistently observe that AIQN yields a highly stable algorithm that improves perceptual quality while maintaining a highly diverse distribution.
A non-commutative homogeneous coordinate ring for the degree six del Pezzo surface

Abstract Let R be the free C -algebra on x and y modulo the relations x 5 = y x y and y 2 = x y x endowed with the Z -grading deg x = 1 and deg y = 2 . The ring R appears, in somewhat hidden guise, in a paper on quiver gauge theories. Let B 3 denote the blow up of CP 2 at three non-colinear points. The main result in this paper is that the category of quasi-coherent O B 3 -modules is equivalent to the quotient of the category of Z -graded R-modules modulo the full subcategory of modules that are the sum of their finite dimensional submodules. This reduces almost all representation-theoretic questions about R to algebraic geometric questions about the del Pezzo surface B 3 . For example, the generic simple R-module has dimension six. Furthermore, the main result combined with results of Artin, Tate, Van den Bergh, and Stephenson implies that R is a noetherian domain of global dimension three.
A posteriori error estimator for adaptive local basis functions to solve Kohn–Sham density functional theory

Kohn-Sham density functional theory is one of the most widely used electronic structure theories. The recently developed adaptive local basis functions form an accurate and systematically improvable basis set for solving Kohn-Sham density functional theory using discontinuous Galerkin methods, requiring a small number of basis functions per atom. In this paper we develop residual-based a posteriori error estimates for the adaptive local basis approach, which can be used to guide non-uniform basis refinement for highly inhomogeneous systems such as surfaces and large molecules. The adaptive local basis functions are non-polynomial basis functions, and standard a posteriori error estimates for $hp$-refinement using polynomial basis functions do not directly apply. We generalize the error estimates for $hp$-refinement to non-polynomial basis functions. We demonstrate the practical use of the a posteriori error estimator in performing three-dimensional Kohn-Sham density functional theory calculations for quasi-2D aluminum surfaces and a single-layer graphene oxide system in water.
Discontinuous homomorphisms, selectors, and automorphisms of the complex field

We show, in Zermelo-Fraenkel set theory without the Axiom of Choice, that the existence of a discontinuous homomorphism of the additive group of real numbers induces a selector for the Vitali equivalence relation $\mathbb{R}/\mathbb{Q}$. This shows that a nonprincipal ultrafilter on the integers is not sufficient to construct a discontinuous automorphism of the complex field, confirming a conjecture of Simon Thomas. This is an improved version of our paper in the Proceedings of the American Mathematical Society, which used a weak version of the Axiom of Choice for the same result.
Pions: Experimental Tests of Chiral Symmetry Breaking

Based on the spontaneous breaking of chiral symmetry, chiral perturbation theory (ChPT) is believed to approximate confinement scale QCD. Dedicated and increasingly accurate experiments and improving lattice calculations are confirming this belief, and we are entering a new era in which we can test confinement scale QCD in some well chosen reactions. This is demonstrated with an overview of low energy experimental tests of ChPT predictions of ππ scattering, pion properties, πN scattering and electromagnetic pion production. These predictions have been shown to be consistent with QCD in the meson sector by increasingly accurate lattice calculations. At present there is good agreement between experiment and ChPT calculations, including the ππ and πN s wave scattering lengths and the π0 lifetime. Recent, accurate pionic atom data are in agreement with chiral calculations once isospin breaking effects due to the mass difference of the up and down quarks are taken into account, as was required to extract the ππ scattering lengths. In addition to tests of the theory, comparisons between ππ and πN interactions based on general chiral principles are discussed. Lattice calculations are now providing results for the fundamental, long and inconclusively studied, πN σ term and the contribution of the strange quark to the mass of the proton. Increasingly accurate experiments in electromagnetic pion production experiments from the proton which test ChPT calculations (and their energy region of validity) are presented. These experiments are also beginning to measure the final state πN interaction. This paper is based on the concluding remarks made at the Chiral Dynamics Workshop CD12 held at Jefferson Lab in Aug. 2012.
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?

Low-rank approximation is a common tool used to accelerate kernel methods: the $n \times n$ kernel matrix $K$ is approximated via a rank-$k$ matrix $\tilde K$ which can be stored in much less space and processed more quickly. In this work we study the limits of computationally efficient low-rank kernel approximation. We show that for a broad class of kernels, including the popular Gaussian and polynomial kernels, computing a relative error $k$-rank approximation to $K$ is at least as difficult as multiplying the input data matrix $A \in R^{n \times d}$ by an arbitrary matrix $C \in R^{d \times k}$. Barring a breakthrough in fast matrix multiplication, when $k$ is not too large, this requires $\Omega(nnz(A)k)$ time where $nnz(A)$ is the number of non-zeros in $A$. This lower bound matches, in many parameter regimes, recent work on subquadratic time algorithms for low-rank approximation of general kernels [MM16,MW17], demonstrating that these algorithms are unlikely to be significantly improved, in particular to $O(nnz(A))$ input sparsity runtimes. At the same time there is hope: we show for the first time that $O(nnz(A))$ time approximation is possible for general radial basis function kernels (e.g., the Gaussian kernel) for the closely related problem of low-rank approximation of the kernelized dataset.
Computing the Rectilinear Center of Uncertain Points in the Plane

In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set &#x1d4ab; of n (weighted) uncertain points in the plane and each uncertain point has m possible locations each associated with a probability for the point appearing at that location. The goal is to find a point q∗ in the plane which minimizes the maximum expected rectilinear distance from q∗ to all uncertain points of &#x1d4ab;, and q∗ is called a rectilinear center. We present an algorithm that solves the problem in O(mn) time. Since the input size of the problem is Θ(mn), our algorithm is optimal.
From Declarative Languages to Declarative Processing in Computer Games

Recent work has shown that we can dramatically improve the performance of computer games and simulations through declarative processing: Character AI can be written in an imperative scripting language which is then compiled to relational algebra and executed by a special games engine with features similar to a main memory database system. In this paper we lay out a challenging research agenda built on these ideas. We discuss several research ideas for novel language features to support atomic actions and reactive programming. We also explore challenges for main memory query processing in games and simulations including adaptive query plan selection, support for multi-core and parallel architectures, debugging simulation scripts, and extensions for multi-player games and virtual worlds. We believe that these research challenges will result in a dramatic change in the design of game engines over the next decade.
Strong L-spaces and left-orderability

We introduce the notion of a strong L-space, a closed, oriented rational homology 3-sphere whose Heegaard Floer homology can be determined at the chain level. We prove that the fundamental group of a strong L-space is not left-orderable. Examples of strong L-spaces include the double branched covers of alternating links in S^3.
Parity-Time Symmetry Breaking beyond One Dimension: The Role of Degeneracy

Scientists studying multidimensional systems invariant under a combined mirror-reflection and time-reversal operation find that the presence of degeneracy plays an important role in determining the spontaneous symmetry-breaking transition.
Graph Symmetry Detection and Canonical Labeling: Differences and Synergies

Symmetries of combinatorial objects are known to complicate search algorithms, but such obstacles can often be removed by detecting symmetries early and discarding symmetric subproblems. Canonical labeling of combinatorial objects facilitates easy equivalence checking through quick matching. All existing canonical labeling software also finds symmetries, but the fastest symmetry-finding software does not perform canonical labeling. In this work, we contrast the two problems and dissect typical algorithms to identify their similarities and differences. We then develop a novel approach to canonical labeling where symmetries are found first and then used to speed up the canonical labeling algorithms. Empirical results show that this approach outperforms state-of-the-art canonical labelers.
An estimation-theoretic view of privacy

We study the central problem in data privacy: how to share data with an analyst while providing both privacy and utility guarantees to the user that owns the data. We present an estimation-theoretic analysis of the privacy-utility trade-off (PUT) in this setting. Here, an analyst is allowed to reconstruct (in a mean-squared error sense) certain functions of the data (utility), while other private functions should not be reconstructed with distortion below a certain threshold (privacy). We demonstrate how a x2-based information measure captures the fundamental PUT, and characterize several properties of this function. In particular, we give a sharp bound for the PUT. We then propose a convex program to compute privacy-assuring mappings when the functions to be disclosed and hidden are known a priori. Finally, we evaluate the robustness of our approach to finite samples.
Parallel Streaming Wasserstein Barycenters

Efficiently aggregating data from different sources is a challenging problem, particularly when samples from each source are distributed differently. These differences can be inherent to the inference task or present for other reasons: sensors in a sensor network may be placed far apart, affecting their individual measurements. Conversely, it is computationally advantageous to split Bayesian inference tasks across subsets of data, but data need not be identically distributed across subsets. One principled way to fuse probability distributions is via the lens of optimal transport: the Wasserstein barycenter is a single distribution that summarizes a collection of input measures while respecting their geometry. However, computing the barycenter scales poorly and requires discretization of all input distributions and the barycenter itself. Improving on this situation, we present a scalable, communication-efficient, parallel algorithm for computing the Wasserstein barycenter of arbitrary distributions. Our algorithm can operate directly on continuous input distributions and is optimized for streaming data. Our method is even robust to nonstationary input distributions and produces a barycenter estimate that tracks the input measures over time. The algorithm is semi-discrete, needing to discretize only the barycenter estimate. To the best of our knowledge, we also provide the first bounds on the quality of the approximate barycenter as the discretization becomes finer. Finally, we demonstrate the practical effectiveness of our method, both in tracking moving distributions on a sphere, as well as in a large-scale Bayesian inference task.
Generalized Comparison Trees for Point-Location Problems.

Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$ can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear combination of two hyperplanes from $H$; in particular, if all hyperplanes in $H$ are $k$-sparse then generalized comparisons are $2k$-sparse. The depth of the obtained linear decision tree is polynomial in $d$ and logarithmic in $|H|$, which is comparable to previous results in the literature that use general linear queries. This extends the study of comparison trees from a previous work by the authors [Kane {et al.}, FOCS 2017]. The main benefit is that using generalized comparison queries allows to overcome limitations that apply for the more restricted type of comparison queries. Our analysis combines a seminal result of Forster regarding sets in isotropic position [Forster, JCSS 2002], the margin-based inference dimension analysis for comparison queries from [Kane {et al.}, FOCS 2017], and compactness arguments.
A System-Level Approach to Controller Synthesis

Biological and advanced cyber-physical control systems often have limited, sparse, uncertain, and distributed communication and computing in addition to sensing and actuation. Fortunately, the corresponding plants and performance requirements are also sparse and structured, and this must be exploited to make constrained controller design feasible and tractable. We introduce a new “system level” (SL) approach involving three complementary SL elements. SL parameterizations (SLPs) provide an alternative to the Youla parameterization of all stabilizing controllers and the responses they achieve, and combine with SL constraints (SLCs) to parameterize the largest known class of constrained stabilizing controllers that admit a convex characterization, generalizing quadratic invariance. SLPs also lead to a generalization of detectability and stabilizability, suggesting the existence of a rich separation structure, that when combined with SLCs is naturally applicable to structurally constrained controllers and systems. We further provide a catalog of useful SLCs, most importantly including sparsity, delay, and locality constraints on both communication and computing internal to the controller, and external system performance. Finally, we formulate SL synthesis problems, which define the broadest known class of constrained optimal control problems that can be solved using convex programming.
The structure of promises in quantum speedups

In 1998, Beals, Buhrman, Cleve, Mosca, and de Wolf showed that no super-polynomial quantum speedup is possible in the query complexity setting unless there is a promise on the input. We examine several types of "unstructured" promises, and show that they also are not compatible with super-polynomial quantum speedups. We conclude that such speedups are only possible when the input is known to have some structure. Specifically, we show that there is a polynomial relationship of degree 18 between D(f) and Q(f) for any Boolean function f defined on permutations (elements of [n]^n in which each alphabet element occurs exactly once). More generally, this holds for all f defined on orbits of the symmetric group action (which acts on an element of [M]^n by permuting its entries). We also show that any Boolean function f defined on a "symmetric" subset of the Boolean hypercube has a polynomial relationship between R(f) and Q(f) - although in that setting, D(f) may be exponentially larger.
Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions

We present many new results related to reliable (interactive) communication over insertion-deletion channels. Synchronization errors, such as insertions and deletions, strictly generalize the usual symbol corruption errors and are much harder to protect against. We show how to hide the complications of synchronization errors in many applications by introducing very general channel simulations which efficiently transform an insertion-deletion channel into a regular symbol corruption channel with an error rate larger by a constant factor and a slightly smaller alphabet. We utilize and generalize synchronization string based methods which were recently introduced as a tool to design essentially optimal error correcting codes for insertion-deletion channels. Our channel simulations depend on the fact that, at the cost of increasing the error rate by a constant factor, synchronization strings can be decoded in a streaming manner that preserves linearity of time. Interestingly, we provide a lower bound showing that this constant factor cannot be improved to 1+epsilon, in contrast to what is achievable for error correcting codes. Our channel simulations drastically and cleanly generalize the applicability of synchronization strings. We provide new interactive coding schemes which simulate any interactive two-party protocol over an insertion-deletion channel. Our results improve over the interactive coding schemes of Braverman et al. [TransInf `17] and Sherstov and Wu [FOCS `17] which achieve a small constant rate and require exponential time computations with respect to computational and communication complexities. We provide the first computationally efficient interactive coding schemes for synchronization errors, the first coding scheme with a rate approaching one for small noise rates, and also the first coding scheme that works over arbitrarily small alphabet sizes. We also show tight connections between synchronization strings and edit-distance tree codes which allow us to transfer results from tree codes directly to edit-distance tree codes. Finally, using on our channel simulations, we provide an explicit low-rate binary insertion-deletion code that improves over the state-of-the-art codes by Guruswami and Wang [TransInf `17] in terms of rate-distance trade-off.
Grasp Planning for Customized Grippers by Iterative Surface Fitting

Customized grippers have broad applications in industrial assembly lines. Compared with general parallel grippers, the customized grippers have specifically designed fingers to increase the contact area with the workpieces and improve the grasp robustness. However, grasp planning for customized grippers is challenging due to the object variations, surface contacts and structural constraints of the grippers. In this paper, an iterative surface fitting (ISF) algorithm is proposed to plan grasps for customized grippers. ISF simultaneously searches for optimal gripper transformation and finger displacement by minimizing the surface fitting error. A guided sampling is introduced to avoid ISF getting stuck in local optima and improve the collision avoidance performance. The proposed algorithm is able to consider the structural constraints of the gripper and plan optimal grasps in real-time. The effectiveness of the algorithm is verified by both simulations and experiments. The experimental videos are available at [1].
Twitter speaks: A case of national disaster situational awareness:

In recent years, we have been faced with a series of natural disasters causing a tremendous amount of financial, environmental and human losses. The unpredictable nature of natural disasters behavi...
Efficient Multicasting in Content-Centric Networks Using Datagrams

The Named Data Networking (NDN) and Content-Centric Networking (CCNx) architectures are the leading approaches for content-centric networking, and both require using Interests (requests that elicit content) and maintaining per-Interest forwarding state in Pending Interest Tables (PIT) to store per- Interest forwarding state. To date, PITs have been assumed to be necessary to enable native support for multicasting in the data plane, such that multicast forwarding trees (MFT) are established by the forwarding and aggregation of Interests using PITs. We present a new approach to content-centric networks based on anonymous datagrams that provides native support for multicasting, but does so without the need to maintain per-Interest forwarding state. Simulation experiments are used to show that the proposed new approach attains the same end-to-end delays for multicasting while requiring orders of magnitude fewer forwarding entries.