cssi/SciSciGPT-SciSciNet huggingface dataset:
Pseudo-magnetic quantum Hall effect in oscillating graphene

Abstract When a graphene layer is stressed, the strain alters the phase an electron accumulates hopping between sites in a way that can be modeled as arising from a pseudo-magnetic vector potential. We examine the case of an oscillating, suspended graphene sample and explore a new effect - an oscillating resistance arising from an oscillating quantum Hall effect. This pseudo-magneto-resistance is large, and depends upon the frequency and the amplitude of the acoustic oscillations. We calculate some of the possible consequences for experiment.
Polytope Conditioning and Linear Convergence of the Frank–Wolfe Algorithm

It is well known that the gradient descent algorithm converges linearly when applied to a strongly convex function with Lipschitz gradient. In this case, the algorithm’s rate of convergence is determined by the condition number of the function. In a similar vein, it has been shown that a variant of the Frank–Wolfe algorithm with away steps converges linearly when applied to a strongly convex function with Lipschitz gradient over a polytope. In a nice extension of the unconstrained case, the algorithm’s rate of convergence is determined by the product of the condition number of the function and a certain condition number of the polytope. We shed new light on the latter type of polytope conditioning. In particular, we show that previous and seemingly different approaches to define a suitable condition measure for the polytope are essentially equivalent to each other. Perhaps more interesting, they can all be unified via a parameter of the polytope that formalizes a key premise linked to the algorithm’s line...
Unsupervised Text Style Transfer using Language Models as Discriminators

Binary classifiers are employed as discriminators in GAN-based unsupervised style transfer models to ensure that transferred sentences are similar to sentences in the target domain. One difficulty with the binary discriminator is that error signal is sometimes insufficient to train the model to produce rich-structured language. In this paper, we propose a technique of using a target domain language model as the discriminator to provide richer, token-level feedback during the learning process. Because our language model scores sentences directly using a product of locally normalized probabilities, it offers more stable and more useful training signal to the generator. We train the generator to minimize the negative log likelihood (NLL) of generated sentences evaluated by a language model. By using continuous approximation of the discrete samples, our model can be trained using back-propagation in an end-to-end way. Moreover, we find empirically with a language model as a structured discriminator, it is possible to eliminate the adversarial training steps using negative samples, thus making training more stable. We compare our model with previous work using convolutional neural networks (CNNs) as discriminators and show our model outperforms them significantly in three tasks including word substitution decipherment, sentiment modification and related language translation.
Every binary self-dual code arises from Hilbert symbols

In this paper we construct binary self-dual codes using the \'etale cohomology of $\mathbb{Z}/2$ on the spectra of rings of $S$-integers of global fields. We will show that up to equivalence, all self-dual codes of length at least 4 arise from Hilbert pairings on rings of $S$-integers of $\Q$. This is an arithmetic counterpart of a result of Kreck and Puppe, who used cobordism theory to show that all self-dual codes arise from Poincar\'e duality on real three manifolds.
Introducing Computer Science to High School Students Through Logic Programming

This paper investigates how high school students in an introductory computer science (CS) course approach computing in the logic programming (LP) paradigm. This qualitative study shows how novice students operate within the LP paradigm while engaging in foundational computing concepts and skills: students are engaged in a cyclical process of abstraction, reasoning, and creating representations of their ideas in code while also being informed by the (procedural) requirements and the revision/debugging process. As these computing concepts and skills are also expected in traditional approaches to introductory K-12 CS courses, this paper asserts that LP is a viable paradigm choice for high school novices.
Hopf automorphisms and twisted extensions

We give some applications of a Hopf algebra constructed from a group acting on another Hopf algebra A as Hopf automorphisms, namely Molnar's smash coproduct Hopf algebra. We find connections between the exponent and Frobenius–Schur indicators of a smash coproduct and the twisted exponents and twisted Frobenius–Schur indicators of the original Hopf algebra A. We study the category of modules of the smash coproduct.
Spatial Isolation Implies Zero Knowledge Even in a Quantum World

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable *physical assumption*: if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP^* model captures this setting. In this work we study the following question: does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover *zero knowledge* interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP^*. Our proof consists of constructing a zero knowledge interactive PCP with a strong algebraic structure, and then lifting it to the MIP^* model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.
Infinity-harmonic maps and morphisms

Abstract We propose a new notion called infinity-harmonic maps between Riemannian manifolds. These are natural generalizations of the well-known notion of infinity-harmonic functions and are also the limiting case of p-harmonic maps as p → ∞ . Infinity-harmonicity appears in many familiar contexts. For example, metric projection onto the orbit of an isometric group action from a tubular neighborhood is infinity-harmonic. Unfortunately, infinity-harmonicity is not preserved under composition. Those infinity-harmonic maps that always preserve infinity-harmonicity under pull back are called infinity-harmonic morphisms. We show that infinity-harmonic morphisms are precisely horizontally homothetic maps. Many examples of infinity-harmonic maps are also given, including some very important and well-known classes of maps between Riemannian manifolds.
Putting in all the stops: execution control for JavaScript

Scores of compilers produce JavaScript, enabling programmers to use many languages on the Web, reuse existing code, and even use Web IDEs. Unfortunately, most compilers inherit the browser's compromised execution model, so long-running programs freeze the browser tab, infinite loops crash IDEs, and so on. The few compilers that avoid these problems suffer poor performance and are difficult to engineer. This paper presents Stopify, a source-to-source compiler that extends JavaScript with debugging abstractions and blocking operations, and easily integrates with existing compilers. We apply Stopify to ten programming languages and develop a Web IDE that supports stopping, single-stepping, breakpointing, and long-running computations. For nine languages, Stopify requires no or trivial compiler changes. For eight, our IDE is the first that provides these features. Two of our subject languages have compilers with similar features. Stopify's performance is competitive with these compilers and it makes them dramatically simpler. Stopify's abstractions rely on first-class continuations, which it provides by compiling JavaScript to JavaScript. We also identify sub-languages of JavaScript that compilers implicitly use, and exploit these to improve performance. Finally, Stopify needs to repeatedly interrupt and resume program execution. We use a sampling-based technique to estimate program speed that outperforms other systems.
OneDataShare: A Vision for Cloud-hosted Data Transfer Scheduling and Optimization as a Service

Fast, reliable, and efficient data transmission across wide-area networks is a predominant bottleneck for data-intensive cloud applications. This paper introduces OneDataShare, which is designed to eliminate the issues plaguing effective cloud-based data transfers of varying file sizes and across incompatible transfer end-points. The vision of OneDataShare is to achieve high-speed data communication, interoperability between multiple transfer protocols, and accurate estimation of delivery time for advance planning, thereby maximizing user-profit through improved and faster data analysis for business intelligence. The paper elaborates on the desirable features of OneDataShare as a cloud-hosted data transfer scheduling and optimization service, and how it is aligned with the vision of harnessing the power of the cloud and distributed computing. Experimental evaluation and comparison with existing real-life file transfer services show that the transfer throughout achieved by OneDataShare is 6.5 times greater.
Invariances and Data Augmentation for Supervised Music Transcription

This paper explores a variety of models for frame-based music transcription, with an emphasis on the methods needed to reach state-of-the-art on human recordings. The translation-invariant network discussed in this paper, which combines a traditional filterbank with a convolutional neural network, was the top-performing model in the 2017 MIREX Multiple Fundamental Frequency Estimation evaluation. This class of models shares parameters in the log-frequency domain, which exploits the frequency invariance of music to reduce the number of model parameters and avoid overfitting to the training data. All models in this paper were trained with supervision by labeled data from the MusicNet dataset, augmented by random label-preserving pitch-shift transformations.
Classes of operators determined by ordinal indices

Abstract We introduce and study the Bourgain index of an operator between two Banach spaces. In particular, we study the Bourgain l p and c 0 indices of an operator. Several estimates for finite and infinite direct sums are established. We define classes determined by these indices and show that some of these classes form operator ideals. We characterize the ordinals which occur as the index of an operator and establish exactly when the defined classes are closed. We study associated indices for non-preservation of l p ξ and c 0 ξ spreading models and indices characterizing weak compactness of operators between separable Banach spaces. We also show that some of these classes are operator ideals and discuss closedness and distinctness of these classes.
Carries, Group Theory, and Additive Combinatorics

Given a group and a normal subgroup, we study the problem of choosing coset representatives with few “carries.” The problem is closely linked to the emerging field of additive combinatorics. We exp...
Results on stochastic reaction networks with non-mass action kinetics

In 2010, Anderson, Craciun, and Kurtz showed that if a deterministically modeled reaction network is complex balanced, then the associated stochastic model admits a stationary distribution that is a product of Poissons [1]. That work spurred a number of followup analyses. In 2015, Anderson, Craciun, Gopalkrishnan, and Wiuf considered a particular scaling limit of the stationary distribution detailed in [1], and proved it is a well known Lyapunov function [2]. In 2016, Cappelletti and Wiuf showed the converse of the main result in [1]: if a reaction network with stochastic mass action kinetics admits a stationary distribution that is a product of Poissons, then the deterministic model is complex balanced [3]. In 2017, Anderson, Koyama, Cappelletti, and Kurtz showed that the mass action models considered in [1] are non-explosive (so the stationary distribution characterizes the limiting behavior). In this paper, we generalize each of the three followup results detailed above to the case when the stochastic model has a particular form of non-mass action kinetics.
A parallel repetition theorem for all entangled games

The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known. We prove that the entangled value of a two-player game G repeated n times in parallel is at most c_G*n^{-1/4}*log(n) for a constant c_G depending on G, provided that the entangled value of G is less than 1. In particular, this gives the first proof that the entangled value of a parallel repeated game must converge to 0 for all games whose entangled value is less than 1. Central to our proof is a combination of both classical and quantum correlated sampling.
Leveraging energy storage to optimize data center electricity cost in emerging power markets

Energy storage in data centers has mainly been used as devices to backup generators during power outages. Recently there has been a growing interest in using energy storage devices to actively shape power consumption in data centers to reduce their skyrocketing electricity bills. In this paper, we consider using energy storage in data centers for two applications in a joint fashion: reducing peak demand charges and enabling data centers to participate in regulation markets. We develop an optimization framework that captures the cost of electricity degradation of energy storage devices, as well as the benefit from regulation markets. Under this framework, using real data Microsoft data center traces and PJM regulation signals, we show the electricity bill of a data center can be reduced by up to 20%. Furthermore, we demonstrate that the saving from joint optimization can be even larger than the sum of individually optimizing each component. We quantify the particular aspects of data center load profiles that lead to this superlinear gain. Compared to prior works that consider using energy storage devices for each single application alone, our results suggest that energy storage in data centers can have much larger impacts than previously thought possible.
Stable and convergent approximation of two-dimensional vector fields on unstructured meshes

A new framework is proposed for analyzing staggered-grid finite difference finite volume methods on unstructured meshes. The new framework employs the concept of external approximation of function spaces, and gauge convergence of numerical schemes through the quantities of vorticity and divergence, instead of individual derivatives of the velocity components. The construction of a stable and convergent external approximation of a simple but relevant vector-valued function space is demonstrated, and the new framework is applied to establish the convergence of the MAC scheme for the incompressible Stokes problem on unstructured meshes.
Gradient Flows in Filtering and Fisher-Rao Geometry

Uncertainty propagation and filtering can be interpreted as gradient flows with respect to suitable metrics in the infinite dimensional manifold of probability density functions. Such a viewpoint has been put forth in recent literature, and a systematic way to formulate and solve the same for linear Gaussian systems has appeared in our previous work where the gradient flows were realized via proximal operators with respect to Wasserstein metric arising in optimal mass transport. In this paper, we derive the evolution equations as proximal operators with respect to Fisher-Rao metric arising in information geometry. We develop the linear Gaussian case in detail and show that a template two step optimization procedure proposed earlier by the authors still applies. Our objective is to provide new geometric interpretations of known equations in filtering, and to clarify the implication of different choices of metric.
Hierarchical Approaches for Reinforcement Learning in Parameterized Action Space.

We explore Deep Reinforcement Learning in a parameterized action space. Specifically, we investigate how to achieve sample-efficient end-to-end training in these tasks. We propose a new compact architecture for the tasks where the parameter policy is conditioned on the output of the discrete action policy. We also propose two new methods based on the state-of-the-art algorithms Trust Region Policy Optimization (TRPO) and Stochastic Value Gradient (SVG) to train such an architecture. We demonstrate that these methods outperform the state of the art method, Parameterized Action DDPG, on test domains.
Two-fold quasi-alternating links, Khovanov homology and instanton homology

We introduce a class of links strictly containing quasi-alternating links for which mod 2 reduced Khovanov homology is always thin. We compute the framed instanton homology for double branched covers of such links. Aligning certain dotted markings on a link with bundle data over the branched cover, we also provide many computations of framed instanton homology in the presence of a non-trivial real 3-plane bundle. We discuss evidence for a spectral sequence from the twisted Khovanov homology of a link with mod 2 coefficients to the framed instanton homology of the double branched cover. We also discuss the relevant mod 4 gradings.
On the compactness theorem for embedded minimal surfaces in $3$-manifolds with locally bounded area and genus

Given a sequence of properly embedded minimal surfaces in a $3$-manifold with local bounds on area and genus, we prove subsequential convergence, smooth away from a discrete set, to a smooth embedded limit surface, possibly with multiplicity, and we analyze what happens when one blows up the surfaces near a point where the convergence is not smooth.
Analytic continuation and high energy estimates for the resolvent of the Laplacian on forms on asymptotically hyperbolic spaces

Abstract We prove the analytic continuation of the resolvent of the Laplacian on asymptotically hyperbolic spaces on differential forms, including high energy estimates in strips. This is achieved by placing the spectral family of the Laplacian within the framework developed, and applied to scalar problems, by the author recently, roughly by extending the problem across the boundary of the compactification of the asymptotically hyperbolic space in a suitable manner. The main novelty is that the non-scalar nature of the operator is dealt with by relating it to a problem on an asymptotically Minkowski space to motivate the choice of the extension across the conformal boundary.
ON EXOTIC MODULAR TENSOR CATEGORIES

It has been conjectured that every (2 + 1)-TQFT is a Chern-Simons-Witten (CSW) theory labeled by a pair (G, λ), where G is a compact Lie group, and λ ∈ H4(BG; ℤ) a cohomology class. We study two TQFTs constructed from Jones' subfactor theory which are believed to be counterexamples to this conjecture: one is the quantum double of the even sectors of the E6 subfactor, and the other is the quantum double of the even sectors of the Haagerup subfactor. We cannot prove mathematically that the two TQFTs are indeed counterexamples because CSW TQFTs, while physically defined, are not yet mathematically constructed for every pair (G, λ). The cases that are constructed mathematically include: (1) G is a finite group — the Dijkgraaf-Witten TQFTs; (2) G is torus Tn; (3) G is a connected semi-simple Lie group — the Reshetikhin-Turaev TQFTs. We prove that the two TQFTs are not among those mathematically constructed TQFTs or their direct products. Both TQFTs are of the Turaev-Viro type: quantum doubles of spherical tensor categories. We further prove that neither TQFT is a quantum double of a braided fusion category, and give evidence that neither is an orbifold or coset of TQFTs above. Moreover, representation of the braid groups from the half E6 TQFT can be used to build universal topological quantum computers, and the same is expected for the Haagerup case.
Classification via tensor decompositions of echo state networks

Typically when performing supervised classification tasks on data processed in an echo state network, the entire collection of hidden layer node states from the training dataset is shaped into a matrix, allowing one to use standard linear algebra techniques to train the output layer. However, the collection of hidden layer states is multidimensional in nature, and representing it as a matrix may lead to undesirable numerical conditions or loss of spatial and temporal correlations in the data. This work proposes a tensor-based supervised classification method on echo state network data that preserves and exploits the multidimensional nature of the hidden layer states of the reservoir. The method, which uses orthogonal Tucker-2 decompositions of tensors, is compared with the standard linear output weight approach in several numerical experiments on both synthetic and natural datasets, with results showing that the tensor-based approach tends to outperform the standard linear weights approach.
Fast Convergence for Stochastic and Distributed Gradient Descent in the Interpolation Limit

Modern supervised learning techniques, particularly those using deep nets, involve fitting high dimensional labelled data sets with functions containing very large numbers of parameters. Much of this work is empirical. Interesting phenomena have been observed that require theoretical explanations; however the non-convexity of the loss functions complicates the analysis. Recently it has been proposed that the success of these techniques rests partly in the effectiveness of the simple stochastic gradient descent algorithm in the so called interpolation limit in which all labels are fit perfectly. This analysis is made possible since the SGD algorithm reduces to a stochastic linear system near the interpolating minimum of the loss function. Here we exploit this insight by presenting and analyzing a new distributed algorithm for gradient descent, also in the interpolating limit. The distributed SGD algorithm presented in the paper corresponds to gradient descent applied to a simple penalized distributed loss function, $L(\mathbf{w}_{1},\ \ldots,\ \mathbf{w}_{n})=\Sigma_{i}l_{i}(\mathbf{w}_{i})+ \mu\sum_{ }-\vert \mathbf{w}_{i}-\mathbf{w}_{j}\vert ^{2}$ . Here each node holds only one sample, and its own parameter vector. The notation $ $ denotes edges of a connected graph defining the communication links between nodes. It is shown that this distributed algorithm converges linearly (ie the error reduces exponentially with iteration number), with a rate 1 $-\displaystyle \frac{\eta}{n}\lambda_{min}(H) where $\lambda_{min}(H)$ is the smallest nonzero eigenvalue of the sample covariance or the Hessian H. In contrast with previous usage of similar penalty functions to enforce consensus between nodes, in the interpolating limit it is not required to take the penalty parameter to infinity for consensus to occur. The analysis further reinforces the utility of the interpolation limit in the theoretical treatment of modern machine learning algorithms.
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration

An(e,φ)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V1∪…∪ Vx such that (1) each cluster Vi induces subgraph with conductance at least φ, and (2) the number of inter-cluster edges is at most e|E|. In this paper, we give an improved distributed expander decomposition, and obtain a nearly optimal distributed triangle enumeration algorithm in the CONGEST model.Specifically, we construct an (e,φ)-expander decomposition with φ=(e/log n)2 O(k) in O(n2/k ⋅ poly (1/φ, log n))rounds for any e ∈(0,1) and positive integer k. For example, a (1/no(1), 1/no(1))-expander decomposition only requires O(no(1)) rounds to compute, which is optimal up to subpolynomial factors, and a (0.01,1/poly log n)-expander decomposition can be computed in O(nγ) rounds, for any arbitrarily small constant γ > 0. Previously, the algorithm by Chang, Pettie, and Zhang can construct a (1/6,1/poly log n)-expander decomposition using O (n1-δ) rounds for any δ > 0, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which form a subgraph with arboricity at most nδ. Our algorithm does not have this caveat.By slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC'17], we obtain a triangle enumeration algorithm using O(n1/3) rounds. This matches the lower bound by Izumi and LeGall [PODC'17] and Pandurangan, Robinson and Scquizzato [SPAA'18] of O(n1/3) which holds even in the CONGESTED-CLIQUE model. To the best of our knowledge, this provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED-CLIQUE.The key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.
Spectrum of weighted composition operators part IV spectrum and essential spectra of weighted composition operators in spaces of smooth functions on [0, 1]

We provide a description of the spectrum and essential spectra of invertible weighted composition operators acting in spaces \(C^{(n)}[0,1]\) and Sobolev spaces \( W^{n,X} = \{ f \in C^{(n-1)}[0,1] : f^{(n)} \in X \}\) where X is an interpolation space between \(L^1[0,1]\) and \(L^\infty [0,1]\).
Generating a diverse set of high-quality clusterings

We provide a new framework for generating multiple good quality partitions (clusterings) of a single data set. Our approach decomposes this problem into two components, generating many high-quality partitions, and then grouping these partitions to obtain k representatives. The decomposition makes the approach extremely modular and allows us to optimize various criteria that control the choice of representative partitions.
Elliptic curves over function fields with a large set of integral points

We construct isotrivial and non-isotrivial elliptic curves over $\mathbb{F}_q(t)$ with an arbitrarily large set of separable integral points. As an application of this construction, we prove that there are isotrivial log-general type varieties over $\mathbb_{F}_q(t)$ with a Zariski dense set of separable integral points. This provides a counterexample to a natural translation of the Lang-Vojta conjecture to the function field setting. We also show that our main result provides examples of elliptic curves with an explicit and arbitrarily large set of linearly independent points.
Common voting rules as maximum likelihood estimators

Voting is a very general method of preference aggregation. A voting rule takes as input every voter's vote (typically, a ranking of the alternatives), and produces as output either just the winning alternative or a ranking of the alternatives. One potential view of voting is the following. There exists a "correct" outcome (winner/ranking), and each voter's vote corresponds to a noisy perception of this correct outcome. If we are given the noise model, then for any vector of votes, we can compute the maximum likelihood estimate of the correct outcome. This maximum likelihood estimate constitutes a voting rule. In this paper, we ask the following question: For which common voting rules does there exist a noise model such that the rule is the maximum likelihood estimate for that noise model? We require that the votes are drawn independently given the correct outcome (we show that without this restriction, all voting rules have the property). We study the question both for the case where outcomes are winners and for the case where outcomes are rankings. In either case, only some of the common voting rules have the property. Moreover, the sets of rules that satisfy the property are incomparable between the two cases (satisfying the property in the one case does not imply satisfying it in the other case).
Dynamic Radio Cooperation for Downlink Cloud-RANs with Computing Resource Sharing

A novel dynamic radio-cooperation strategy is proposed for Cloud Radio Access Networks (C-RANs) consisting of multiple Remote Radio Heads (RRHs) connected to a central Virtual Base Station (VBS) pool. In particular, the key capabilities of C-RANs in computing-resource sharing and real-time communication among the VBSs are leveraged to design a joint dynamic radio clustering and cooperative beam forming scheme that maximizes the downlink weighted sum-rate system utility (WSRSU). Due to the combinatorial nature of the radio clustering process and the non-convexity of the cooperative beam forming design, the underlying optimization problem is NP-hard, and is extremely difficult to solve for a large network. Our approach aims for a suboptimal solution by transforming the original problem into a Mixed-Integer Second-Order Cone Program (MI-SOCP), which can be solved efficiently using a proposed iterative algorithm. Numerical simulation results show that our low-complexity algorithm provides close-to-optimal performance in terms of WSRSU while significantly outperforming conventional radio clustering and beam forming schemes. Additionally, the results also demonstrate the significant improvement in computing-resource utilization of C-RANs over traditional RANs with distributed computing resources.
Tight Bounds for Collaborative PAC Learning via Multiplicative Weights

We study the collaborative PAC learning problem recently proposed in Blum et al.~\cite{BHPQ17}, in which we have $k$ players and they want to learn a target function collaboratively, such that the learned function approximates the target function well on all players' distributions simultaneously. The quality of the collaborative learning algorithm is measured by the ratio between the sample complexity of the algorithm and that of the learning algorithm for a single distribution (called the overhead). We obtain a collaborative learning algorithm with overhead $O(\ln k)$, improving the one with overhead $O(\ln^2 k)$ in \cite{BHPQ17}. We also show that an $\Omega(\ln k)$ overhead is inevitable when $k$ is polynomial bounded by the VC dimension of the hypothesis class. Finally, our experimental study has demonstrated the superiority of our algorithm compared with the one in Blum et al.~\cite{BHPQ17} on real-world datasets.
Pairwise optimal discrete coverage control for gossiping robots

We propose distributed algorithms to automatically deploy a group of robotic agents and provide coverage of a discretized environment represented by a graph. The classic Lloyd approach to coverage optimization involves separate centering and partitioning steps and converges to the set of centroidal Voronoi partitions. In this work we present a novel graph coverage algorithm which achieves better performance without this separation while requiring only pairwise “gossip” communication between agents. Our new algorithm provably converges to an element of the set of pairwise-optimal partitions, a subset of the set of centroidal Voronoi partitions. We illustrate that this new equilibrium set represents a significant performance improvement through numerical comparisons to existing Lloyd-type methods. Finally, we discuss ways to efficiently do the necessary computations.
Log‐ratio lasso: Scalable, sparse estimation for log‐ratio models

Positive-valued signal data is common in the biological and medical sciences, due to the prevalence of mass spectrometry other imaging techniques. With such data, only the relative intensities of the raw measurements are meaningful. It is desirable to consider models consisting of the log-ratios of all pairs of the raw features, since log-ratios are the simplest meaningful derived features. In this case, however, the dimensionality of the predictor space becomes large, and computationally efficient estimation procedures are required. In this work, we introduce an embedding of the log-ratio parameter space into a space of much lower dimension and use this representation to develop an efficient penalized fitting procedure. This procedure serves as the foundation for a two-step fitting procedure that combines a convex filtering step with a second non-convex pruning step to yield highly sparse solutions. On a cancer proteomics data set, the proposed method fits a highly sparse model consisting of features of known biological relevance while greatly improving upon the predictive accuracy of less interpretable methods.
Beyond endoscopy for the Rankin–Selberg L-function

Abstract We try to understand the poles of L-functions via taking a limit in a trace formula. This technique avoids endoscopic and Kim–Shahidi methods. In particular, we investigate the poles of the Rankin–Selberg L-function. Using analytic number theory techniques to take this limit, we essentially get a new proof of the analyticity of the Rankin–Selberg L-function at s = 1 . Along the way we discover the convolution operation for Bessel transforms.
Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap

In this paper, we study the problem of \textit{constrained} and \textit{stochastic} continuous submodular maximization. Even though the objective function is not concave (nor convex) and is defined in terms of an expectation, we develop a variant of the conditional gradient method, called \alg, which achieves a \textit{tight} approximation guarantee. More precisely, for a monotone and continuous DR-submodular function and subject to a \textit{general} convex body constraint, we prove that \alg achieves a $[(1-1/e)\text{OPT} -\eps]$ guarantee (in expectation) with $\mathcal{O}{(1/\eps^3)}$ stochastic gradient computations. This guarantee matches the known hardness results and closes the gap between deterministic and stochastic continuous submodular maximization. By using stochastic continuous optimization as an interface, we also provide the first $(1-1/e)$ tight approximation guarantee for maximizing a \textit{monotone but stochastic} submodular \textit{set} function subject to a general matroid constraint.
Identifiability and Stability in Blind Deconvolution Under Minimal Assumptions

Blind deconvolution (BD) arises in many applications. Without assumptions on the signal and the filter, BD does not admit a unique solution. In practice, subspace or sparsity assumptions have shown the ability to reduce the search space and yield the unique solution. However, existing theoretical analysis on uniqueness in BD is rather limited. In an earlier paper, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in $ \mathbb {C}^{n}$ , with subspace constraints of dimensions $m_{1}$ and $m_{2}$ , respectively, a sample complexity of $n\geq m_{1}m_{2}$ is sufficient. This result is suboptimal, since the number of degrees of freedom is merely $m_{1}+m_{2}-1$ . We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In this paper, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (respectively, all pairs) of vectors in $ \mathbb {C} ^{n}$ , with sparsity constraints of sparsity levels $s_{1}$ and $s_{2}$ , a sample complexity of $n > s_{1}+s_{2}$ [respectively, $n > 2(s_{1}+s_{2})$ ] is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in this paper, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities.
On almost-Riemannian surfaces

An almost-Riemannian structure on a surface is a generalized Riemannian structure whose local orthonormal frames are given by Lie bracket generating pairs of vector fields that can become collinear. The distribution generated locally by orthonormal frames has maximal rank at almost every point of the surface, but in general it has rank 1 on a nonempty set which is generically a smooth curve. In this paper we provide a short introduction to 2-dimensional almost-Riemannian geometry highlighting its novelties with respect to Riemannian geometry. We present some results that investigate topological, metric and geometric aspects of almostRiemannian surfaces from a local and global point of view.
Wilf equivalence relations for consecutive patterns

Abstract Two permutations π and τ are c-Wilf equivalent if, for each n, the number of permutations in S n avoiding π as a consecutive pattern (i.e., in adjacent positions) is the same as the number of those avoiding τ. In addition, π and τ are strongly c-Wilf equivalent if, for each n and k, the number of permutations in S n containing k occurrences of π as a consecutive pattern is the same as for τ. In this paper we introduce a third, more restrictive equivalence relation, defining π and τ to be super-strongly c-Wilf equivalent if the above condition holds for any set of prescribed positions for the k occurrences. We show that, when restricted to non-overlapping permutations, these three equivalence relations coincide. We also give a necessary condition for two permutations to be strongly c-Wilf equivalent. Specifically, we show that if π , τ ∈ S m are strongly c-Wilf equivalent, then | π m − π 1 | = | τ m − τ 1 | . In the special case of non-overlapping permutations π and τ, this proves a weaker version of a conjecture of the second author stating that π and τ are c-Wilf equivalent if and only if π 1 = τ 1 and π m = τ m , up to trivial symmetries. Finally, we strengthen a recent result of Nakamura and Khoroshkin–Shapiro giving sufficient conditions for strong c-Wilf equivalence.
Data Centers as Dispatchable Loads to Harness Stranded Power

We analyze how traditional data center placement and optimal placement of dispatchable data centers affect power grid efficiency. We use detailed network models, stochastic optimization formulations, and diverse renewable generation scenarios to perform our analysis. Our results reveal that significant spillage and stranded power will persist in power grids as wind power levels are increased. A counter-intuitive finding is that collocating data centers with inflexible loads next to wind farms has limited impacts on renewable portfolio standard (RPS) goals because it provides limited system-level flexibility. Such an approach can, in fact, increase stranded power and fossil-fueled generation. In contrast, optimally placing data centers that are dispatchable provides system-wide flexibility, reduces stranded power, and improves efficiency. In short, optimally placed dispatchable computing loads can enable better scaling to high RPS. In our case study, we find that these dispatchable computing loads are powered to 60–80% of their requested capacity, indicating that there are significant economic incentives provided by stranded power.
Random Extensions of Free Groups and Surface Groups are Hyperbolic

In this note, we prove that a random extension of either the free group FN of rank N ě 3 or of the fundamental group of a closed, orientable surface Sg of genus g ě 2 is a hyperbolic group. Here, a random extension is one corresponding to a subgroup of either OutpFN q or ModpSgq generated by k independent random walks. Our main theorem has several applications, including that a random subgroup of a weakly hyperbolic group is free and undistorted.
Spin–orbit misalignment of two-planet-system KOI-89 via gravity darkening

We constrain the true spin–orbit alignment of the KOI-89 system by numerically fitting the two Kepler photometric light curves produced by the transiting planets KOI-89.01 and KOI-89.02. The two planets have periods of 84.69 and 207.58 days, respectively. We find that the two bodies are low-density giant planets with radii of 0.45 ± 0.03 Rjup and 0.43 ± 0.05 Rjup and spin–orbit misalignments of 72° ± 3° and , respectively. Through dynamic stability tests, we demonstrate the general trend of higher system stability with the two planets close to mutual alignment and estimate their coalignment angle to 20° ± 20°—i.e., the planets are misaligned with the star but may be aligned with each other. From these results, we limit KOI-89's misalignment mechanisms to star–disk-binary interactions, disk warping via planet–disk interactions, planet–planet scattering, Kozai resonance, or internal gravity waves.
On resilience analysis and quantification for wide-area control of power systems

Wide-area control is an effective mean to reduce inter-area oscillations of the bulk power system. Its dependence on communication of remote measurement signals makes the closed-loop system vulnerable to cyber attacks. This paper develops a framework to analyze and quantify resilience of a given wide-area controller under disruptive attacks on certain communication links. Resilience of a given controller is measured in terms of closed-loop eigenvalues under the worst possible attack strategy. The computation of such a resilience metric is challenging especially for large-scale power systems due to the discrete nature of attack strategies. In this paper, we propose an optimization-based formulation and a convex relaxation approach to facilitate the computation. Furthermore, we develop an efficient algorithm for the relaxed problem with guaranteed convergence to identify structural vulnerabilities of the system. Simulations are performed on the IEEE 39-bus system to illustrate the proposed resilience analysis and computation framework.
Environment-Aware Deployment of Wireless Drones Base Stations with Google Earth Simulator

In this paper, a software-based simulator for the deployment of base station-equipped unmanned aerial vehicles (UAVs) in a cellular network is proposed. To this end, the Google Earth Engine platform and its included image processing functions are used to collect geospatial data and to identify obstacles that can disrupt the line-of-sight (LoS) communications between UAVs and ground users. Given such geographical information, three environment-aware optimal UAV deployment scenarios are investigated using the developed simulator. In the first scenario, the positions of UAVs are optimized such that the number of ground users covered by UAVs is maximized. In the second scenario, the minimum number of UAVs needed to provide full coverage for all ground users is determined. Finally, given the load requirements of the ground users, the total flight time (i.e., energy) that the UAVs need to completely serve the ground users is minimized. Simulation results using a real area of the Virginia Tech campus show that the proposed environment-aware drone deployment framework with Google Earth input significantly enhances the network performance in terms of coverage and energy consumption, compared to classical deployment approaches that do not exploit geographical information. In particular, the results show that the proposed approach yields a coverage enhancement by a factor of 2, and a 65% improvement in energy-efficiency. The results have also shown the existence of an optimal number of drones that leads to a maximum wireless coverage performance.
Light WIMPs and Equivalent Neutrinos

Abstract Very light WIMPs (χ), thermal relics that annihilate late in the early Universe, change the energy and entropy densities at BBN and at recombination. BBN, in combination with the CMB, can remove some of the degeneracies among light WIMPs and equivalent neutrinos, constraining the existence and properties of each. Depending on the nature of the light WIMP (Majorana or Dirac fermion, real or complex scalar) the joint BBN + CMB analyses set lower bounds to m χ in the range 0.5 − 5 MeV ( m χ / m e ≲1 − 10), and they identify best fit values for m χ in the range 5 − 10 MeV. The joint BBN + CMB analysis finds a best fit value for the number of equivalent neutrinos, ΔN ν ≈ 0.65, nearly independent of the nature of the WIMP. In the absence of a light WIMP ( m χ ≲20 MeV), N eff = 3.05(1 + ΔN ν /3). In this case, there is excellent agreement between BBN and the CMB, but the joint fit reveals ΔN ν = 0.40 ± 0.17, disfavoring standard big bang nucleosynthesis (SBBN) (ΔN ν = 0) at ∼ 2.4 σ, as well as a sterile neutrino (ΔN ν = 1) at ∼ 3.5 σ. The best BBN + CMB joint fit disfavors the absence of dark radiation (ΔN ν = 0 at ∼ 95% confidence), while allowing for the presence of a sterile neutrino (ΔN ν = 1 at ≲1 σ). For all cases considered here, the lithium problem persists. These results, presented at the TAUP 2013 Conference, are based on Nollett & Steigman [14] .
Polar Codes with Exponentially Small Error at Finite Block Length.

We show that the entire class of polar codes (up to a natural necessary condition) converge to capacity at block lengths polynomial in the gap to capacity, while simultaneously achieving failure probabilities that are exponentially small in the block length (i.e., decoding fails with probability $\exp(-N^{\Omega(1)})$ for codes of length $N$). Previously this combination was known only for one specific family within the class of polar codes, whereas we establish this whenever the polar code exhibits a condition necessary for any polarization. Our results adapt and strengthen a local analysis of polar codes due to the authors with Nakkiran and Rudra [Proc. STOC 2018]. Their analysis related the time-local behavior of a martingale to its global convergence, and this allowed them to prove that the broad class of polar codes converge to capacity at polynomial block lengths. Their analysis easily adapts to show exponentially small failure probabilities, provided the associated martingale, the ``Arikan martingale'', exhibits a corresponding strong local effect. The main contribution of this work is a much stronger local analysis of the Arikan martingale. This leads to the general result claimed above. In addition to our general result, we also show, for the first time, polar codes that achieve failure probability $\exp(-N^{\beta})$ for any $\beta < 1$ while converging to capacity at block length polynomial in the gap to capacity. Finally we also show that the ``local'' approach can be combined with any analysis of failure probability of an arbitrary polar code to get essentially the same failure probability while achieving block length polynomial in the gap to capacity.
A Problem on Track Runners.

Consider the unit circle $C$ and a circular arc $A$ of length $\ell=|A| < 1$. It is shown that there exists $k=k(\ell) \in \mathbb{N}$, and a schedule for $k$ runners with $k$ distinct but constant speeds so that at any time $t \geq 0$, at least one of the $k$ runners is \emph{not} in $A$.
Arp2/3 and Unc45 maintain heterochromatin stability in Drosophila polytene chromosomes:

Repairing DNA double-strand breaks is particularly challenging in pericentromeric heterochromatin, where the abundance of repeated sequences exacerbates the risk of ectopic recombination. In Drosop...