cssi/SciSciGPT-SciSciNet huggingface dataset:
Simulation of carbon nanotube welding through Ar bombardment

Single-walled carbon nanotubes show promise as nanoscale transistors for nanocomputing applications. This use will require appropriate methods for creating electrical connections between distinct nanotubes, analogous to welding of metallic wires at larger length scales, but methods for performing nanoscale chemical welding are not yet sufficiently understood. This study examines the effect of Ar bombardment on the junction of two crossed single-walled carbon nanotubes, to understand the value and limitations of this method for generating connections between nanotubes. A geometric criterion was used to assess the quality of the junctions formed, with the goal of identifying the most productive conditions for experimental ion bombardment. In particular, the effects of nanotube chirality, Ar impact kinetic energy, impact particle flux and fluence, and annealing temperature were considered. The most productive bombardment conditions, leading to the most crosslinking of the tubes with the smallest loss of graphitic (i.e., conductive) character, were found to be at relatively mild impact energies (100 eV), with low flux and high-temperature (3000 K) annealing. Particularly noteworthy for experimental application, a high junction quality is maintained for a relatively broad range of fluences, from 3 × 1019 m−2 to at least 1 × 1020 m−2.
A Note on a Conjecture of Watanabe and Yoshida

We consider a conjecture of Watanabe and Yoshida in [12] concerning the Hilbert–Kunz multiplicity of an ideal in a Cohen–Macaulay ring and provide a proof of the conjecture in the case the ring is graded.
Maximum likelihood fitting of acyclic directed mixed graphs to binary data

Acyclic directed mixed graphs, also known as semi-Markov models represent the conditional independence structure induced on an observed margin by a DAG model with latent variables. In this paper we present the first method for fitting these models to binary data using maximum likelihood estimation.
Anchored rectangle and square packings

Abstract For points p 1 , … , p n in the unit square [ 0 , 1 ] 2 , an anchored rectangle packing consists of interior-disjoint axis-aligned empty rectangles r 1 , … , r n ⊆ [ 0 , 1 ] 2 such that point p i is a corner of the rectangle r i (that is, r i is anchored at p i ) for i = 1 , … , n . We show that for every set of n points in [ 0 , 1 ] 2 , there is an anchored rectangle packing of area at least 7 ∕ 12 − O ( 1 ∕ n ) , and for every n ∈ N , there are point sets for which the area of every anchored rectangle packing is at most 2 ∕ 3 . The maximum area of an anchored square packing is always at least 5 ∕ 32 and sometimes at most 7 ∕ 27 . The above constructive lower bounds immediately yield constant-factor approximations, of 7 ∕ 12 − e for rectangles and 5 ∕ 32 for squares, for computing anchored packings of maximum area in O ( n log n ) time. We prove that a simple greedy strategy achieves a 9 ∕ 47 -approximation for anchored square packings, and 1 ∕ 3 for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS for anchored rectangle packings in exp ( poly ( e − 1 log n ) ) time and a PTAS for anchored square packings in n O ( 1 ∕ e ) time.
On the dimension growth of groups

We prove that the Thompson group F has exponential dimension growth. We also prove that every solvable finitely generated subgroup of F has polynomial dimension growth while some elementary amenable subgroups of F and some solvable groups of class 3 have dimension growth at least exp(n).
Polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel

We provide polylog sparse quantum codes for correcting the Erasure channel arbitrarily close to the capacity. Specifically, we provide the $[[n, k, d]]$ quantum stabilizer codes that correct for the erasure channel arbitrarily close to the capacity if the erasure probability is at least 0.33 and with a generating set $\langle S_{1}, S_{2}, \cdots {} S_{n-k} \rangle $ such that $|S_{i}|\leq {\mathrm{ log}} ^{2+\zeta }(n)$ for all $i$ and for any $\zeta > 0$ with high probability. In this paper, we show that the result of Delfosse et al. is tight: one can construct capacity approaching codes with weight almost $O(1)$ .
On the signed Euler characteristic property for subvarieties of abelian varieties

We give an elementary proof of the fact that a pure-dimensional closed subvariety of a complex abelian variety has a signed intersection homology Euler characteristic. We also show that such subvarieties which, moreover, are local complete intersections, have a signed Euler-Poincar\'e characteristic. Both results are special cases of the fact, proved by Franecki-Kapranov, that the Euler characteristic of a perverse sheaves on a semi-abelian variety is non-negative. Our arguments use in an essential way the stratified Morse theory of Goresky-MacPherson.
Scalable bicriteria algorithms for the threshold activation problem in online social networks

We consider the Threshold Activation Problem (TAP): given social network G and positive threshold T, find a minimum-size seed set A that can trigger expected activation of at least T. We introduce the first scalable, parallelizable algorithm with performance guarantee for TAP suitable for datasets with millions of nodes and edges; we exploit the bicriteria nature of solutions to TAP to allow the user to control the running time versus accuracy of our algorithm through a parameter α ∊ (0, 1): given η > 0, with probability 1 − η our algorithm returns a solution A with expected activation greater than T — 2αΤ, and the size of the solution A is within factor 1−h 4αΤ + log(T) of the optimal size. The algorithm runs in time O (α−2 log (n/η) (n + m)|A|), where n, m, refer to the number of nodes, edges in the network. The performance guarantee holds for the general triggering model of internal influence and also incorporates external influence, provided a certain condition is met on the cost-effectivity of seed selection.
Two-dimensional exciton-polariton—light guiding by transition metal dichalcogenide monolayers

Two-dimensional (2D) monolayer-thick materials with a direct bandgap, such as MoS2, WSe2, and other transition metal dichalcogenides (TMDCs), are being actively explored for future nanophotonic applications in the visible and UV ranges. Here I show that a monolayer of TMDCs is capable of supporting a guided optical mode below the exciton resonance—a 2D exciton–polariton. I evaluate the characteristics of these guided modes and conditions required for their existence, including derivations of mode dispersion relations, mode confinements, and propagation lengths. The visible or near-IR mode is confined to within roughly a micrometer of the monolayer and has a propagation length exceeding 100 μm. This light guiding ability in the visible and IR ranges makes TMDC monolayers a versatile and potentially attractive platform for future optoelectronic devices.
The Generalized Degrees of Freedom Region of the MIMO Z-Interference Channel With Delayed CSIT

The generalized degrees of freedom (GDoF) region of the multiple-input multiple-output (MIMO) Gaussian Z-interference channel with an arbitrary number of antennas at each node is established under the assumption of delayed channel state information at transmitters (CSIT). The GDoF region is parameterized by $\alpha$ , which links the interference-to-noise ratio (INR) to the signal-to-noise ratio (SNR) via $\mathrm {INR}=\mathrm {SNR}^{\alpha }$ . A new outer bound for the GDoF region is established by maximizing a bound on the weighted sum-rate of the two users, which in turn is obtained by using a combination of genie-aided side-information and an extremal inequality. The maximum weighted sum-rate in the high SNR regime is shown to occur when the transmission covariance matrix of the interfering transmitter has full rank. An achievability scheme based on block-Markov encoding and backward decoding is developed which uses interference quantization and digital multicasting to take advantage of the channel statistics of the cross-link, and the scheme is separately shown to be GDoF-optimal in both the weak ( $\alpha \leq 1$ ) and strong ( ${\alpha >1}$ ) interference regimes. This is the first complete characterization of the GDoF region of any interference network with delayed CSIT, as well as the first such GDoF characterization of a MIMO network with delayed CSIT and arbitrary number of antennas at each node. For all antenna tuples, the GDoF region is shown to be equal to or larger than the degrees of freedom (DoF) region over the entire range of $\alpha$ , which leads to a V-shaped maximum sum-GDoF as a function of $\alpha$ , with the minimum occurring at $\alpha =1$ . The delayed CSIT GDoF region and the sum-DoF are compared with their counterparts under perfect CSIT, thereby characterizing all antenna tuples and ranges of $\alpha$ for which delayed CSIT is sufficient to achieve the perfect CSIT GDoF region (or sum-DoF). It is also shown that treating interference as noise is not, in general, GDoF-optimal for the MIMO Z-IC, even in the weak interference regime.
Totally unimodular congestion games

We investigate a new class of congestion games, called Totally Unimodular (TU) Congestion Games, where the players' strategies are binary vectors inside polyhedra defined by totally unimodular constraint matrices. Network congestion games belong to this class.In the symmetric case, when all players have the same strategy set, we design an algorithm that finds an optimal aggregated strategy and then decomposes it into the single players' strategies. This approach yields strongly polynomial-time algorithms to (i) find a pure Nash equilibrium, and (ii) compute a socially optimal state, if the delay functions are weakly convex. We also show how this technique can be extended to matroid congestion games.We then introduce some combinatorial TU congestion games, where the players' strategies are matchings, vertex covers, edge covers, and stable sets of a given bipartite graph. In the asymmetric case, we show that for these games (i) it is PLS-complete to find a pure Nash equilibrium even in case of linear delay functions, and (ii) it is NP-hard to compute a socially optimal state, even in case of weakly convex delay functions.
Enhancement of low-cost GNSS localization in connected vehicle networks using Rao-Blackwellized particle filters

An essential function for automated vehicle technologies is accurate localization. It is difficult, however, to achieve lane-level accuracy with low-cost Global Navigation Satellite System (GNSS) receivers due to the biased noisy pseudo-range measurements. Approaches such as Differential GNSS can improve the accuracy, but usually require an enormous amount of investment in base stations. The emerging connected vehicle technologies provide an alternative approach to improving the localization accuracy. It has been shown in this paper that localization accuracy can be enhanced by fusing GNSS information within a group of connected vehicles and matching the configuration of the group to a digital map to eliminate the common bias in localization. A Rao-Blackwellized particle filter (RBPF) was used to jointly estimate the common biases of the pseudo-ranges and the vehicles positions. Multipath biases, which are non-common to vehicles, were mitigated by a multi-hypothesis detection-rejection approach. The temporal correlation was exploited through the prediction-update process. The proposed approach was compared to the existing static and smoothed static methods in the intersection scenario. Simulation results show that the proposed algorithm reduced the estimation error by fifty percent and reduced the estimation variance by two orders of magnitude.
Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers.

The 1-center clustering with outliers problem asks about identifying a prototypical robust statistic that approximates the location of a cluster of points. Given some constant $0 < \alpha < 1$ and $n$ points such that $\alpha n$ of them are in some (unknown) ball of radius $r,$ the goal is to compute a ball of radius $O(r)$ that also contains $\alpha n$ points. This problem can be formulated with the points in a normed vector space such as $\mathbb{R}^d$ or in a general metric space. The problem has a simple randomized solution: a randomly selected point is a correct solution with constant probability, and its correctness can be verified in linear time. However, the deterministic complexity of this problem was not known. In this paper, for any $\ell_p$ vector space, we show an $O(nd)$-time solution with a ball of radius $O(r)$ for a fixed $\alpha > \frac{1}{2},$ and for any normed vector space, we show an $O(nd)$-time solution with a ball of radius $O(r)$ when $\alpha > \frac{1}{2}$ as well as an $O (nd \log^{(k)}(n))$-time solution with a ball of radius $O(r)$ for all $\alpha > 0, k \in \mathbb{N},$ where $\log^{(k)}(n)$ represents the $k$th iterated logarithm, assuming distance computation and vector space operations take $O(d)$ time. For an arbitrary metric space, we show for any $C \in \mathbb{N}$ an $O(n^{1+1/C})$-time solution that finds a ball of radius $2Cr,$ assuming distance computation between any pair of points takes $O(1)$-time. Moreover, this algorithm is optimal for general metric spaces, as we show that for any fixed $\alpha, C,$ there is no $o(n^{1+1/C})$-query and thus no $o(n^{1+1/C})$-time solution that deterministically finds a ball of radius $2Cr$.
Central limit theorem and Diophantine approximations

Let $$F_n$$ denote the distribution function of the normalized sum $$Z_n = (X_1 + \cdots + X_n)/(\sigma \sqrt{n})$$ of i.i.d. random variables with finite fourth absolute moment. In this paper, polynomial rates of convergence of $$F_n$$ to the normal law with respect to the Kolmogorov distance, as well as polynomial approximations of $$F_n$$ by the Edgeworth corrections (modulo logarithmically growing factors in n), are given in terms of the characteristic function of $$X_1$$ . Particular cases of the problem are discussed in connection with Diophantine approximations.
An Invariant-Region-Preserving (IRP) Limiter to DG Methods for Compressible Euler Equations

We introduce an explicit invariant-region-preserving limiter applied to DG methods for compressible Euler equations. The invariant region considered consists of positivity of density and pressure and a maximum principle of a specific entropy. The modified polynomial by the limiter preserves the cell average, lies entirely within the invariant region, and does not destroy the high order of accuracy for smooth solutions, as long as the cell average stays away from the boundary of the invariant region. Numerical tests are presented to illustrate the properties of the limiter. In particular, the tests on Riemann problems show that the limiter helps to damp the oscillations near discontinuities.
Long range correlations in high multiplicity hadron collisions: Building bridges with ridges

Abstract We discuss the physics of the ridge–azimuthally collimated long range rapidity correlations–in high multiplicity proton–proton and proton–nucleus collisions. We outline some of the theoretical discussions in the literature that address the systematics of these ridge correlations.
Logarithmic Sobolev inequalities for mollified compactly supported measures

Abstract We show that the convolution of a compactly supported measure on R with a Gaussian measure satisfies a logarithmic Sobolev inequality (LSI). We use this result to give a new proof of a classical result in random matrix theory that states that, under certain hypotheses, the empirical law of eigenvalues of a sequence of random real symmetric matrices converges weakly in probability to its mean. We then examine the optimal constants in the LSIs for the convolved measures in terms of the variance of the convolving Gaussian. We conclude with partial results on the extension of our main theorem to higher dimensions.
Determinacy separations for class games

We show, assuming weak large cardinals, that in the context of games of length $$\omega $$ with moves coming from a proper class, clopen determinacy is strictly weaker than open determinacy. The proof amounts to an analysis of a certain level of L that exists under large cardinal assumptions weaker than an inaccessible. Our argument is sufficiently general to give a family of determinacy separation results applying in any setting where the universal class is sufficiently closed; e.g., in third, seventh, or $$(\omega +2)$$ th order arithmetic. We also prove bounds on the strength of Borel determinacy for proper class games. These results answer questions of Gitman and Hamkins.
Holography and off-center collisions of localized shock waves

Using numerical holography, we study the collision, at non-zero impact parameter, of bounded, localized distributions of energy density chosen to mimic relativistic heavy ion collisions, in strongly coupled $$ \mathcal{N}=4 $$ supersymmetric Yang-Mills theory. Both longitudinal and transverse dynamics in the dual field theory are properly described. Using the gravitational description, we solve 5D Einstein equations with no dimensionality reducing symmetry restrictions to find the asymptotically anti-de Sitter spacetime geometry. Implications of our results on the understanding of early stages of heavy ion collisions, including the development of transverse radial flow, are discussed.
Improved local well-posedness for the periodic "good" Boussinesq equation

Abstract We prove that the “good” Boussinesq model is locally well-posed in the space H − α × H − α − 2 , α 3 8 . In the proof, we employ the method of normal forms, which allows us to explicitly extract the rougher part of the solution, while we show that the remainder is in the smoother space C ( [ 0 , T ] , H β ( T ) ) , β min ( 1 − 3 α , 1 2 − α ) . Thus, we establish a smoothing effect of order min ( 1 − 2 α , 1 2 ) for the nonlinear evolution. This is new even in the previously considered cases α ∈ ( 0 , 1 4 ) .
On a transport equation with nonlocal drift

In \cite{CordobaCordobaFontelos05}, Cordoba, Cordoba, and Fontelos proved that for some initial data, the following nonlocal-drift variant of the 1D Burgers equation does not have global classical solutions \[ \partial_t \theta +u \; \partial_x \theta = 0, \qquad u = H \theta, \] where $H$ is the Hilbert transform. We provide four essentially different proofs of this fact. Moreover, we study possible Holder regularization effects of this equation and its consequences to the equation with diffusion \[ \partial_t \theta + u \; \partial_x \theta + \Lambda^\gamma \theta = 0, \qquad u = H \theta, \] where $\Lambda = (-\Delta)^{1/2}$, and $1/2 \leq \gamma <1$. Our results also apply to the model with velocity field $u = \Lambda^s H \theta$, where $s \in (-1,1)$. We conjecture that solutions which arise as limits from vanishing viscosity approximations are bounded in the Holder class in $C^{(s+1)/2}$, for all positive time.
Foundational Principles for Large-Scale Inference: Illustrations Through Correlation Mining

When can reliable inference be drawn in the “Big Data” context? This paper presents a framework for answering this fundamental question in the context of correlation mining, with implications for general large-scale inference. In large-scale data applications like genomics, connectomics, and eco-informatics, the data set is often variable rich but sample starved: a regime where the number $n$ of acquired samples (statistical replicates) is far fewer than the number $p$ of observed variables (genes, neurons, voxels, or chemical constituents) . Much of recent work has focused on understanding the computational complexity of proposed methods for “Big Data.” Sample complexity, however, has received relatively less attention, especially in the setting when the sample size $n$ is fixed, and the dimension $p$ grows without bound. To address this gap, we develop a unified statistical framework that explicitly quantifies the sample complexity of various inferential tasks. Sampling regimes can be divided into several categories: 1) the classical asymptotic regime where the variable dimension is fixed and the sample size goes to infinity; 2) the mixed asymptotic regime where both variable dimension and sample size go to infinity at comparable rates; and 3) the purely high-dimensional asymptotic regime where the variable dimension goes to infinity and the sample size is fixed. Each regime has its niche but only the latter regime applies to exa-scale data dimension. We illustrate this high-dimensional framework for the problem of correlation mining, where it is the matrix of pairwise and partial correlations among the variables that are of interest. Correlation mining arises in numerous applications and subsumes the regression context as a special case. We demonstrate various regimes of correlation mining based on the unifying perspective of high-dimensional learning rates and sample complexity for different structured covariance models and different inference tasks.
Piatetski-Shapiro primes in a Beatty sequence

Abstract Let α , β be real numbers such that α > 1 is irrational and of finite type, and let c be a real number in the range 1 c 14 13 . In this paper, it is shown that there are infinitely many Piatetski-Shapiro primes p = ⌊ n c ⌋ in the non-homogeneous Beatty sequence ( ⌊ α m + β ⌋ ) m = 1 ∞ .
Think Visually: Question Answering through Virtual Imagery

In this paper, we study the problem of geometric reasoning (a form of visual reasoning) in the context of question-answering. We introduce Dynamic Spatial Memory Network (DSMN), a new deep network architecture that specializes in answering questions that admit latent visual representations, and learns to generate and reason over such representations. Further, we propose two synthetic benchmarks, FloorPlanQA and ShapeIntersection, to evaluate the geometric reasoning capability of QA systems. Experimental results validate the effectiveness of our proposed DSMN for visual thinking tasks.
Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting

Given the success of Douglas–Rachford splitting (DRS), it is natural to ask whether DRS can be generalized. Are there other 2 operator resolvent-splittings sharing the favorable properties of DRS? Can DRS be generalized to 3 operators? This work presents the answers: no and no. In a certain sense, DRS is the unique 2 operator resolvent-splitting, and generalizing DRS to 3 operators is impossible without lifting, where lifting roughly corresponds to enlarging the problem size. The impossibility result further raises a question. How much lifting is necessary to generalize DRS to 3 operators? This work presents the answer by providing a novel 3 operator resolvent-splitting with provably minimal lifting that directly generalizes DRS.
A note on the topological sliceness of some 2-bridge knots

We use twisted Alexander polynomials to show that certain algebraically slice 2-bridge knots are not topologically slice, even though all prime power Casson–Gordon signatures vanish. We also provide some computations indicating the efficacy of Casson–Gordon signatures in obstructing the smooth sliceness of 2-bridge knots.
MAGNETIC SPECTRAL BOUNDS ON STARLIKE PLANE DOMAINS

We develop sharp upper bounds for energy levels of the magnetic Laplacian on starlike plane domains, under either Dirichlet or Neumann boundary conditions and assuming a constant magnetic field in the transverse direction. Our main result says that n=1 Φ λjA/G is maximal for a disk whenever Φ is concave increasing, n ≥ 1, the domain has area A ,a ndλj is the jth Dirichlet eigenvalue of the magnetic Laplacian i∇ + β 2A (−x2 ,x 1) 2 . Here the flux β is constant, and the scale invariant factor G penalizes deviations from roundness, meaning G ≥ 1 for all domains and G =1f or disks.
Secure Face Matching Using Fully Homomorphic Encryption

Face recognition technology has demonstrated tremendous progress over the past few years, primarily due to advances in representation learning. As we witness the widespread adoption of these systems, it is imperative to consider the security of face representations. In this pa per, we explore the practicality of using a fully homomorphic encryption based framework to secure a database of face templates. This framework is designed to preserve the privacy of users and prevent information leakage from the templates, while maintaining their utility through tem plate matching directly in the encrypted domain. Additionally, we also explore a batching and dimensionality reduction scheme to trade-off face matching accuracy and computational complexity. Experiments on benchmark face datasets (LFW, IJB-A, IJB-B, CASIA) indicate that secure face matching can be practically feasible (16KB template size and 0.01 sec per match pair for 512-dimensional features from SphereFace I231) while exhibiting minimal loss in matching performance.
A New Characterization of the Mappings of Bounded Length Distortion

In this paper, we present a new characterization of the mappings of bounded length distortion (BLD for short). In the original geometric definition it is assumed that a BLD mapping is open, discrete and sense preserving. We prove that the first two of the three conditions are redundant and the sense-preserving condition can be replaced by a weaker assumption that the Jacobian is non-negative.
Reconstruction of real depth-3 circuits with top fan-in 2

Reconstruction of arithmetic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing ΣΠΣ(2) circuits over F (char(F) = 0), i.e. depth-3 circuits with fan-in 2 at the top addition gate and having coefficients from a field of characteristic 0. The algorithm needs only a blackbox query access to the polynomial f ∈ F[x1, ..., xn] of degree d, computable by a ΣΠΣ(2) circuit C. In addition, we assume that the "simple rank" of this polynomial (essential number of variables after removing the gcd of the two multiplication gates) is bigger than a fixed constant. Our algorithm runs in time poly(n, d) and returns an equivalent ΣΠΣ(2) circuit (with high probability). The problem of reconstructing ΣΠΣ(2) circuits over finite fields was first proposed by Shpilka [24]. The generalization to ΣΠΣ(k) circuits, k = O(1) (over finite fields) was addressed by Karnin and Shpilka in [15]. The techniques in these previous involve iterating over all objects of certain kinds over the ambient field and thus the running time depends on the size of the field F. Their reconstruction algorithm uses lower bounds on the lengths of Linear Locally Decodable Codes with 2 queries. In our settings, such ideas immediately pose a problem and we need new ideas to handle the case of the characteristic 0 field F. Our main techniques are based on the use of Quantitative Sylvester Gallai Theorems from the work of Barak et al. [3] to find a small collection of "nice" subspaces to project onto. The heart of our paper lies in subtle applications of the Quantitative Sylvester Gallai theorems to prove why projections w.r.t. the "nice" subspaces can be "glued". We also use Brill's Equations from [8] to construct a small set of candidate linear forms (containing linear forms from both gates). Another important technique which comes very handy is the polynomial time randomized algorithm for factoring multivariate polynomials given by Kaltofen [14].
Zamolodchikov integrability via rings of invariants

Zamolodchikov periodicity is periodicity of certain recursions associated with box products of two finite type Dynkin diagrams. We suggest an affine analog of Zamolodchikov periodicity, which we call Zamolodchikov integrability. We conjecture that it holds for products of a finite type Dynkin diagram and an affine extended Dynkin diagram. We prove this conjecture for the case of Am□A 􏷡n−􏷠. The proof employs cluster structures in certain classical rings of invariants, previously studied by S. Fomin and the author.
Asynchronous Adaptation and Learning Over Networks—Part III: Comparison Analysis

In Part II of this paper, also in this issue, we carried out a detailed mean-square-error analysis of the performance of asynchronous adaptation and learning over networks under a fairly general model for asynchronous events including random topologies, random link failures, random data arrival times, and agents turning on and off randomly. In this Part III, we compare the performance of synchronous and asynchronous networks. We also compare the performance of decentralized adaptation against centralized stochastic-gradient (batch) solutions. Two interesting conclusions stand out. First, the results establish that the performance of adaptive networks is largely immune to the effect of asynchronous events: the mean and mean-square convergence rates and the asymptotic bias values are not degraded relative to synchronous or centralized implementations. Only the steady-state mean-square-deviation suffers a degradation in the order of ν, which represents the small step-size parameters used for adaptation. Second, the results show that the adaptive distributed network matches the performance of the centralized solution. These conclusions highlight another critical benefit of cooperation by networked agents: cooperation does not only enhance performance in comparison to stand-alone single-agent processing, but it also endows the network with remarkable resilience to various forms of random failure events and is able to deliver performance that is as powerful as batch solutions.
An asynchronous parallel approach to sparse recovery

Asynchronous parallel computing and sparse recovery are two areas that have received recent interest. Asynchronous algorithms are often studied to solve optimization problems where the cost function takes the form Σ i=1 Mƒ i (x), with a common assumption that each ƒ i is sparse; that is, each ƒ i acts only on a small number of components of x ∈ ℝn. Sparse recovery problems, such as compressed sensing, can be formulated as optimization problems, however, the cost functions ƒ i are dense with respect to the components of x, and instead the signal x is assumed to be sparse, meaning that it has only s non-zeros where s ≪ n. Here we address how one may use an asynchronous parallel architecture when the cost functions ƒ i are not sparse in x, but rather the signal x is sparse. We propose an asynchronous parallel approach to sparse recovery via a stochastic greedy algorithm, where multiple processors asynchronously update a vector in shared memory containing information on the estimated signal support. We include numerical simulations that illustrate the potential benefits of our proposed asynchronous method.
Strong Data Processing Inequalities for Input Constrained Additive Noise Channels

This paper quantifies the intuitive observation that adding noise reduces available information by means of nonlinear strong data processing inequalities. Consider the random variables $W\to X\to Y$ forming a Markov chain, where $Y = X + Z$ with $X$ and $Z$ real valued, independent and $X$ bounded in $L_{p}$ -norm. It is shown that $I(W; Y) \le F_{I}(I(W;X))$ with $F_{I}(t) whenever $t > 0$ , if and only if $Z$ has a density whose support is not disjoint from any translate of itself. A related question is to characterize for what couplings $(W, X)$ the mutual information $I(W; Y)$ is close to maximum possible. To that end we show that in order to saturate the channel, i.e., for $I(W; Y)$ to approach capacity, it is mandatory that $I(W; X)\to \infty $ (under suitable conditions on the channel). A key ingredient for this result is a deconvolution lemma which shows that postconvolution total variation distance bounds the preconvolution Kolmogorov–Smirnov distance. Explicit bounds are provided for the special case of the additive Gaussian noise channel with quadratic cost constraint. These bounds are shown to be order optimal. For this case, simplified proofs are provided leveraging Gaussian-specific tools such as the connection between information and estimation (I-MMSE) and Talagrand’s information-transportation inequality.
Analyzing the Quantum Annealing Approach for Solving Linear Least Squares Problems

With the advent of quantum computers, researchers are exploring if quantum mechanics can be leveraged to solve important problems in ways that may provide advantages not possible with conventional or classical methods. A previous work by O’Malley and Vesselinov in 2016 briefly explored using a quantum annealing machine for solving linear least squares problems for real numbers. They suggested that it is best suited for binary and sparse versions of the problem. In our work, we propose a more compact way to represent variables using two’s and one’s complement on a quantum annealer. We then do an in-depth theoretical analysis of this approach, showing the conditions for which this method may be able to outperform the traditional classical methods for solving general linear least squares problems. Finally, based on our analysis and observations, we discuss potentially promising areas of further research where quantum annealing can be especially beneficial.
On Translation Invariant Symmetric Polynomials and Haldane's Conjecture

We establish an isomorphism between the ring of translation invariant symmetric polynomials in n variables and the full polynomial ring in n − 1 variables, over any field of characteristic 0. In addition, we give a counterexample to a conjecture of Haldane3 regarding the structure of translation invariant symmetric polynomials. Our motivation is the fractional quantum Hall effect, where translation invariant (anti)symmetric complex polynomials in n variables characterize n-electron wavefunctions.
Exploiting Domain Knowledge via Grouped Weight Sharing with Application to Text Categorization

A fundamental advantage of neural models for NLP is their ability to learn representations from scratch. However, in practice this often means ignoring existing external linguistic resources, e.g., WordNet or domain specific ontologies such as the Unified Medical Language System (UMLS). We propose a general, novel method for exploiting such resources via weight sharing. Prior work on weight sharing in neural networks has considered it largely as a means of model compression. In contrast, we treat weight sharing as a flexible mechanism for incorporating prior knowledge into neural models. We show that this approach consistently yields improved performance on classification tasks compared to baseline strategies that do not exploit weight sharing.
Oscillatory thermocapillary instability of a film heated by a thick substrate

In this work we consider a new class of oscillatory instabilities that pertain to thermocapillary destabilization of a liquid film heated by a solid substrate. We assume the substrate thickness and substrate–film thermal conductivity ratio are large so that the effect of substrate thermal diffusion is retained at leading order in the long-wave approximation. As a result, the system dynamics is described by a nonlinear partial differential equation for the film thickness that is non-locally coupled to the full substrate heat equation. Perturbing about a steady quiescent state, we find that its stability is described by a non-self-adjoint eigenvalue problem. We show that, under appropriate model parameters, the linearized eigenvalue problem admits complex eigenvalues that physically correspond to oscillatory (in time) instabilities of the thin-film height. As the principal results of our work, we provide a complete picture of the susceptibility to oscillatory instabilities for different model parameters. Using this description, we conclude that oscillatory instabilities are more relevant experimentally for films heated by insulating substrates. Furthermore, we show that oscillatory instability where the fastest-growing (most unstable) wavenumber is complex, arises only for systems with sufficiently large substrate thicknesses. Finally, we discuss adaptation of our model to a practical setting and make predictions of conditions at which the reported instabilities can be observed.
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective

The free energy is a key quantity of interest in Ising models, but unfortunately, computing it in general is computationally intractable. Two popular (variational) approximation schemes for estimating the free energy of general Ising models (in particular, even in regimes where correlation decay does not hold) are: (i) the mean-field approximation with roots in statistical physics, which estimates the free energy from below, and (ii) hierarchies of convex relaxations with roots in theoretical computer science, which estimate the free energy from above. We show, surprisingly, that the tight regime for both methods to compute the free energy to leading order is identical. More precisely, we show that the mean-field approximation to the free energy is within O((n||J||F)2/3) of the true free energy, where ||J||F denotes the Frobenius norm of the interaction matrix of the Ising model. This simultaneously subsumes both the breakthrough work of Basak and Mukherjee, who showed the tight result that the mean-field approximation is within o(n) whenever ||J||F = o(√n), as well as the work of Jain, Koehler, and Mossel, who gave the previously best known non-asymptotic bound of O((n||J||F)2/3log1/3(n||J||F)). We give a simple, algorithmic proof of this result using a convex relaxation proposed by Risteski based on the Sherali-Adams hierarchy, automatically giving sub-exponential time approximation schemes for the free energy in this entire regime. Our algorithmic result is tight under Gap-ETH. We furthermore combine our techniques with spin glass theory to prove (in a strong sense) the optimality of correlation rounding, refuting a recent conjecture of Allen, O’Donnell, and Zhou. Finally, we give the tight generalization of all of these results to k-MRFs, capturing as a special case previous work on approximating MAX-k-CSP.
On the Spectrum of 1D Quantum Ising Quasicrystal

We consider one-dimensional quantum Ising spin-1/2 chains with two-valued nearest neighbor couplings arranged in a quasi-periodic sequence, with uniform, transverse magnetic field. By employing the Jordan–Wigner transformation of the spin operators to spinless fermions, the energy spectrum can be computed exactly on a finite lattice. By employing the transfer matrix technique and investigating the dynamics of the corresponding trace map, we show that in the thermodynamic limit the energy spectrum is a Cantor set of zero Lebesgue measure. Moreover, we show that local Hausdorff dimension is continuous and non-constant over the spectrum. This forms a rigorous counterpart of numerous numerical studies.
A Continuation Method for Tensor Complementarity Problems

We introduce a Kojima–Megiddo–Mizuno type continuation method for solving tensor complementarity problems. We show that there exists a bounded continuation trajectory when the tensor is strictly semi-positive and any limit point tracing the trajectory gives a solution of the tensor complementarity problem. Moreover, when the tensor is strong strictly semi-positive, tracing the trajectory will converge to the unique solution. Some numerical results are given to illustrate the effectiveness of the method.
Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time

Many applications, including rank aggregation and crowd-labeling, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and columns. We consider the problem of estimating such a matrix based on noisy observations of a subset of its entries, and design and analyze a polynomial-time algorithm that improves upon the state of the art. In particular, our results imply that any such $n \times n$ matrix can be estimated efficiently in the normalized Frobenius norm at rate $\widetilde{\mathcal O}(n^{-3/4})$, thus narrowing the gap between $\widetilde{\mathcal O}(n^{-1})$ and $\widetilde{\mathcal O}(n^{-1/2})$, which were hitherto the rates of the most statistically and computationally efficient methods, respectively.
Branched Cauchy–Riemann structures on once-punctured torus bundles

Unlike in hyperbolic geometry, the monodromy ideal triangulation of a hyperbolic once-punctured torus bundle $M_f$ has no natural geometric realisation in Cauchy-Riemann (CR) space. By introducing a new type of $3$--cell, we construct a different cell decomposition $\mathcal{D}_f$ of $M_f$ that is always realisable in CR space. As a consequence, we show that every hyperbolic once-punctured torus bundle admits a branched CR structure, whose branch locus is the set of edges of $\mathcal{D}_f$. Furthermore, we explicitly compute the ramification order around each component of the branch locus and analyse the corresponding holonomy representations.
An intrinsic flat limit of Riemannian manifolds with no geodesics

In this paper we produce a sequence of Riemannian manifolds $$M_j^m$$, $$m \ge 2$$, which converge in the intrinsic flat sense to the unit m-sphere with the restricted Euclidean distance. This limit space has no geodesics achieving the distances between points, exhibiting previously unknown behavior of intrinsic flat limits. In contrast, any compact Gromov–Hausdorff limit of a sequence of Riemannian manifolds is a geodesic space. Moreover, if $$m\ge 3$$, the manifolds $$M_j^m$$ may be chosen to have positive scalar curvature.
LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain

We study k-SVD that is to obtain the first k singular vectors of a matrix A. Recently, a few breakthroughs have been discovered on k-SVD: Musco and Musco [1] proved the first gap-free convergence result using the block Krylov method, Shamir [2] discovered the first variance-reduction stochastic method, and Bhojanapalli et al. [3] provided the fastest $O(\mathsf{nnz}(A) + \mathsf{poly}(1/\varepsilon))$-time algorithm using alternating minimization. In this paper, we put forward a new and simple LazySVD framework to improve the above breakthroughs. This framework leads to a faster gap-free method outperforming [1], and the first accelerated and stochastic method outperforming [2]. In the $O(\mathsf{nnz}(A) + \mathsf{poly}(1/\varepsilon))$ running-time regime, LazySVD outperforms [3] in certain parameter regimes without even using alternating minimization.
Multilingual Relation Extraction using Compositional Universal Schema

Universal schema builds a knowledge base (KB) of entities and relations by jointly embedding all relation types from input KBs as well as textual patterns observed in raw text. In most previous applications of universal schema, each textual pattern is represented as a single embedding, preventing generalization to unseen patterns. Recent work employs a neural network to capture patterns’ compositional semantics, providing generalization to all possible input text. In response, this paper introduces significant further improvements to the coverage and flexibility of universal schema relation extraction: predictions for entities unseen in training and multilingual transfer learning to domains with no annotation. We evaluate our model through extensive experiments on the English and Spanish TAC KBP benchmark, outperforming the top system from TAC 2013 slot-filling using no handwritten patterns or additional annotation. We also consider a multilingual setting in which English training data entities overlap with the seed KB, but Spanish text does not. Despite having no annotation for Spanish data, we train an accurate predictor, with additional improvements obtained by tying word embeddings across languages. Furthermore, we find that multilingual training improves English relation extraction accuracy. Our approach is thus suited to broad-coverage automated knowledge base construction in a variety of languages and domains.
Information percolation and cutoff for the stochastic Ising model

We introduce a new framework for analyzing Glauber dynamics for the Ising model. The traditional approach for obtaining sharp mixing results has been to appeal to estimates on spatial properties of the stationary measure from within a multi-scale analysis of the dynamics. Here we propose to study these simultaneously by examining “information percolation” clusters in the space-time slab. Using this framework, we obtain new results for the Ising model on (Z/nZ) throughout the high temperature regime: total-variation mixing exhibits cutoff with an O(1)-window around the time at which the magnetization is the square-root of the volume. (Previously, cutoff in the full high temperature regime was only known in dimensions d ≤ 2, and only with an O(log log n)-window.) Furthermore, the new framework opens the door to understanding the effect of the initial state on the mixing time. We demonstrate this on the 1d Ising model, showing that starting from the uniform (“disordered”) initial distribution asymptotically halves the mixing time, whereas almost every deterministic starting state is asymptotically as bad as starting from the (“ordered”) all-plus state.
1-Dimensional representations and parabolic induction for W-algebras

A W-algebra is an associative algebra constructed from a reductive Lie algebra and its nilpotent element. This paper concentrates on the study of 1-dimensional representations of W-algebras. Under some conditions on a nilpotent element (satisfied by all rigid elements) we obtain a criterium for a finite dimensional module to have dimension 1. It is stated in terms of the Brundan–Goodwin–Kleshchev highest weight theory. This criterium allows to compute highest weights for certain completely prime primitive ideals in universal enveloping algebras. We make an explicit computation in a special case in type E8. Our second principal result is a version of a parabolic induction for W-algebras. In this case, the parabolic induction is an exact functor between the categories of finite dimensional modules for two different W-algebras. The most important feature of the functor is that it preserves dimensions. In particular, it preserves one-dimensional representations. A closely related result was obtained previously by Premet. We also establish some other properties of the parabolic induction functor.
Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection

We study the problem of selecting a subset of k random variables from a large set, in order to obtain the best linear prediction of another variable of interest. This problem can be viewed in the context of both feature selection and sparse approximation. We analyze the performance of widely used greedy heuristics, using insights from the maximization of submodular functions and spectral analysis. We introduce the submod-ularity ratio as a key quantity to help understand why greedy algorithms perform well even when the variables are highly correlated. Using our techniques, we obtain the strongest known approximation guarantees for this problem, both in terms of the submodularity ratio and the smallest k-sparse eigenvalue of the covariance matrix. We also analyze greedy algorithms for the dictionary selection problem, and significantly improve the previously known guarantees. Our theoretical analysis is complemented by experiments on real-world and synthetic data sets; the experiments show that the submodularity ratio is a stronger predictor of the performance of greedy algorithms than other spectral parameters.