cssi/SciSciGPT-SciSciNet huggingface dataset:
Muckenhoupt-Wheeden conjectures for sparse operators

We provide an explicit example of a pair of weights and a dyadic sparse operator for which the Hardy–Littlewood maximal function is bounded from \(L^p(v)\) to \(L^p(u)\) and from \(L^{p'}(u^{1-p'})\) to \(L^{p'}(v^{1-p'})\) while the sparse operator is not bounded on the same spaces. Our construction also provides an example of a single weight for which the weak-type endpoint does not hold for sparse operators.
An explicit hybrid estimate for $L(1/2+it,\chi)$

An explicit hybrid estimate for $L(1/2+it,\chi)$ is derived, where $\chi$ is a Dirichlet character modulo $q$. The estimate applies when $t$ is bounded away from zero, and is most effective when $q$ is powerfull, yielding an explicit Weyl bound in this case. The estimate takes a particularly simple form if $q$ is a sixth power. Several hybrid lemmas of van der Corput--Weyl type are presented.
Accurate, robust, and reliable calculations of Poisson-Boltzmann binding energies.

Poisson-Boltzmann (PB) model is one of the most popular implicit solvent models in biophysical modeling and computation. The ability of providing accurate and reliable PB estimation of electrostatic solvation free energy, ΔGel, and binding free energy, ΔΔGel, is important to computational biophysics and biochemistry. In this work, we investigate the grid dependence of our PB solver (MIBPB) with solvent excluded surfaces for estimating both electrostatic solvation free energies and electrostatic binding free energies. It is found that the relative absolute error of ΔGel obtained at the grid spacing of 1.0 A compared to ΔGel at 0.2 A averaged over 153 molecules is less than 0.2%. Our results indicate that the use of grid spacing 0.6 A ensures accuracy and reliability in ΔΔGel calculation. In fact, the grid spacing of 1.1 A appears to deliver adequate accuracy for high throughput screening. © 2017 Wiley Periodicals, Inc.
BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies

Abstract: We propose BlackOut, an approximation algorithm to efficiently train massive recurrent neural network language models (RNNLMs) with million word vocabularies. BlackOut is motivated by using a discriminative loss, and we describe a new sampling strategy which significantly reduces computation while improving stability, sample efficiency, and rate of convergence. One way to understand BlackOut is to view it as an extension of the DropOut strategy to the output layer, wherein we use a discriminative training loss and a weighted sampling scheme. We also establish close connections between BlackOut, importance sampling, and noise contrastive estimation (NCE). Our experiments, on the recently released one billion word language modeling benchmark, demonstrate scalability and accuracy of BlackOut; we outperform the state-of-the art, and achieve the lowest perplexity scores on this dataset. Moreover, unlike other established methods which typically require GPUs or CPU clusters, we show that a carefully implemented version of BlackOut requires only 1-10 days on a single machine to train a RNNLM with a million word vocabulary and billions of parameters on one billion words. Although we describe BlackOut in the context of RNNLM training, it can be used to any networks with large softmax output layers.
PixelNN: Example-based Image Synthesis

We present a simple nearest-neighbor (NN) approach that synthesizes high-frequency photorealistic images from an "incomplete" signal such as a low-resolution image, a surface normal map, or edges. Current state-of-the-art deep generative models designed for such conditional image synthesis lack two important things: (1) they are unable to generate a large set of diverse outputs, due to the mode collapse problem. (2) they are not interpretable, making it difficult to control the synthesized output. We demonstrate that NN approaches potentially address such limitations, but suffer in accuracy on small datasets. We design a simple pipeline that combines the best of both worlds: the first stage uses a convolutional neural network (CNN) to maps the input to a (overly-smoothed) image, and the second stage uses a pixel-wise nearest neighbor method to map the smoothed output to multiple high-quality, high-frequency outputs in a controllable manner. We demonstrate our approach for various input modalities, and for various domains ranging from human faces to cats-and-dogs to shoes and handbags.
AN INVERSION FORMULA FOR THE GAUSSIAN RADON TRANSFORM FOR BANACH SPACES

We prove a disintegration theorem for the Gaussian Radon transform Gf on Banach spaces and use the Segal–Bargmann transform on abstract Wiener spaces to find a procedure to obtain f from its Gaussian Radon transform Gf.
Dual-axis high-data-rate atom interferometer via cold ensemble exchange

Atom interferometers use light to track the Doppler effect as ensembles of cold atoms such as ${}^{87}$Rb travel ballistically in vacuum. These systems are used as ultrasensitive gravimeters and could also be exceptional broadband inertial sensors for vehicle navigation and guidance, but typically they are designed for a static laboratory environment. The authors present a compact atom interferometer that measures acceleration and rotation simultaneously and at a high rate, to be used in a dynamic environment for real-time integration of a vehicle's equations of motion.
A surface of maximal canonical degree

It is known since the 1970s from a paper of Beauville that the degree of the rational canonical map of a smooth projective algebraic surface of general type is at most 36. Though it has been conjectured that a surface with optimal canonical degree 36 exists, the highest canonical degree known earlier for a minimal surface of general type was 16 by Persson. The purpose of this paper is to give an affirmative answer to the conjecture by providing an explicit surface.
Modular Catalan numbers

The Catalan number C n enumerates parenthesizations of x 0 ź ź ź x n where ź is a binary operation. We introduce the modular Catalan number C k , n to count equivalence classes of parenthesizations of x 0 ź ź ź x n when ź satisfies a k -associative law generalizing the usual associativity. This leads to a study of restricted families of Catalan objects enumerated by C k , n with emphasis on binary trees, plane trees, and Dyck paths, each avoiding certain patterns. We give closed formulas for C k , n with two different proofs. For each n ź 0 we compute the largest size of k -associative equivalence classes and show that the number of classes with this size is a Catalan number.
Distance between two random k-out digraphs, with and without preferential attachment

A random k-out mapping (digraph) on [n] is generated by choosing k random images of each vertex one at a time, subject to a 'preferential attachment' rule: the current vertex selects an image i with probability proportional to a given parameter α = α(n) plus the number of times i has already been selected. Intuitively, the larger α becomes, the closer the resulting k-out mapping is to the uniformly random k-out mapping. We prove that α = Θ(n 1/2) is the threshold for α growing 'fast enough' to make the random digraph approach the uniformly random digraph in terms of the total variation distance. We also determine an exact limit for this distance for the α = β n 1/2 case.
Pangea: monolithic distributed storage for data analytics

Storage and memory systems for modern data analytics are heavily layered, managing shared persistent data, cached data, and nonshared execution data in separate systems such as a distributed file system like HDFS, an in-memory file system like Alluxio, and a computation framework like Spark. Such layering introduces significant performance and management costs. In this paper we propose a single system called Pangea that can manage all data---both intermediate and long-lived data, and their buffer/caching, data placement optimization, and failure recovery---all in one monolithic distributed storage system, without any layering. We present a detailed performance evaluation of Pangea and show that its performance compares favorably with several widely used layered systems such as Spark.
Word Maps in Finite Simple Groups

Elements of the free group define interesting maps, known as word maps, on groups. It was previously observed by Lubotzky that every subset of a finite simple group that is closed under endomorphisms occurs as the image of some word map. We improve upon this result by showing that the word in question can be chosen to be in $$v(\mathbf F _n),$$ the verbal subgroup of the free group generated by the word v, provided that v is not a law on the finite simple group in question. In addition, we provide an example of a word w that witnesses the chirality of the Mathieu group $$M_{11}$$. The paper concludes by demonstrating that not every subset of a group closed under endomorphisms occurs as the image of a word map.
Structured prediction: from Gaussian perturbations to linear-time principled algorithms

Margin-based structured prediction commonly uses a maximum loss over all possible structured outputs (Altun & Hofmann, 2003; Collins, 2004; Taskar et al., 2003). In natural language processing, recent work (Zhang et al., 2014; Zhang et al., 2015) has proposed the use of the maximum loss over random structured outputs sampled independently from some proposal distribution. This method is linear-time in the number of random structured outputs and trivially parallelizable. We study this family of loss functions in the PAC-Bayes framework under Gaussian perturbations (McAllester, 2007). Under some technical conditions and up to statistical accuracy, we show that this family of loss functions produces a tighter upper bound of the Gibbs decoder distortion than commonly used methods. Thus, using the maximum loss over random structured outputs is a principled way of learning the parameter of structured prediction models. Besides explaining the experimental success of (Zhang et al., 2014; Zhang et al., 2015), our theoretical results show that more general techniques are possible.
On the negative-one shift functor for FI-modules

We show that the negative-one shift functor S˜−1 on the category of FI-modules is a left adjoint of the shift functor S and a right adjoint of the derivative functor D. We show that for any FI-module V, the coinduction QV of V is an extension of V by S˜−1V.
FIT-MART: Quantum Magnetism with a Gentle Learning Curve

Abstract We present a new open-source software package, FIT-MART, that allows non-experts to quickly get started sim- ulating quantum magnetism. FIT-MART can be downloaded as a platform-idependent executable Java (JAR) file. It allows the user to define (Heisenberg) Hamiltonians by electronically drawing pictures that represent quantum spins and operators. Sliders are automatically generated to control the values of the parameters in the model, and when the values change, several plots are updated in real time to display both the resulting energy spectra and the equilibruim magnetic properties. Several experimental data sets for real magnetic molecules are included in FIT-MART to allow easy comparison between simulated and experimental data, and FIT-MART users can also import their own data for analysis and compare the goodness of fit for different models.
The Number of Languages with Maximum State Complexity

Champarnaud and Pin (1989) found that the minimal deterministic automaton of a language \(L\subset \Sigma ^n\), where \(\Sigma =\{0,1\}\), has at most $$ \sum _{i=0}^n \min (2^i, 2^{2^{n-i}}-1) $$ states, and for each n there exists L attaining this bound. Câmpeanu and Ho (2004) have shown more generally that the tight upper bound for \(\Sigma \) of cardinality k and for complete automata is $$ \frac{k^r-1}{k-1} + \sum _{j=0}^{n-r}(2^{k^j}-1) + 1 $$ where \(r=\min \{m:k^m\ge 2^{k^{n-m}}-1\}\). (In these results, requiring totality of the transition function adds 1 to the state count.) Câmpeanu and Ho’s result can be viewed as concerning functions \(f:[k]^n\rightarrow [2]\) where \([k]=\{0,\dots ,k-1\}\) is a set of cardinality k. We generalize their result to arbitrary function \(f:[k]^n\rightarrow [c]\) where c is a positive integer.
Uncanny Subsequence Selections That Generate Normal Numbers

Given a real number $0.a_1a_2 a_3\dots$ that is normal to base $b$, we examine increasing sequences $n_i$ so that the number $0.a_{n_1}a_{n_2}a_{n_3}\dots$ are normal to base $b$. Classically it is known that if the $n_i$ form an arithmetic progression then this will work. We give several more constructions, including $n_i$ that are recursively defined based on the digits $a_i$. Of particular interest, we show that if a number is normal to base $b$, then removing all the digits from its expansion which equal $(b-1)$ leaves a base-$(b-1)$ expansion that is normal to base $(b-1)$.
Einstein manifolds with nonnegative isotropic curvature are locally symmetric

Let (M,g) be an Einstein manifold of dimension n≥4 with nonnegative isotropic curvature. We show that (M,g) is locally symmetric
Training and spontaneous reinforcement of neuronal assemblies by spike timing

The synaptic connectivity of cortex is plastic, with experience shaping the ongoing interactions between neurons. Theoretical studies of spike timing-dependent plasticity (STDP) have focused on either just pairs of neurons or large-scale simulations where analytic insight is lacking. A simple account for how fast spike time correlations affect both micro- and macroscopic network structure remains lacking. We develop a low-dimensional mean field theory showing how STDP gives rise to strongly coupled assemblies of neurons with shared stimulus preferences, with the connectivity actively reinforced by spike train correlations during spontaneous dynamics. Furthermore, the stimulus coding by cell assemblies is actively maintained by these internally generated spiking correlations, suggesting a new role for noise correlations in neural coding. Assembly formation has been often associated with firing rate-based plasticity schemes; our theory provides an alternative and complementary framework, where temporal correlations and STDP form and actively maintain learned structure in cortical networks.
Boundary Integrals and Approximations of Harmonic Functions

Steklov expansions for a harmonic function on a rectangle are derived and studied with a view to determining an analog of the mean value theorem for harmonic functions. It is found that the value of a harmonic function at the center of a rectangle is well approximated by the mean value of the function on the boundary plus a very small number (often 3 or fewer) of specific further boundary integrals. These integrals are coefficients in the Steklov representation of the function. Similar approximations are found for the central values of solutions of Robin and Neumann boundary value problems. The results follow from analyses of the explicit expressions for the Steklov eigenvalues and eigenfunctions.
Counterexamples to Okounkov’s log-concavity conjecture

We give counterexamples to Okounkov's log-concavity conjecture for Littlewood-Richardson coefficients.
Bridging between 0/1 and linear programming via random walks

Under the Strong Exponential Time Hypothesis, an integer linear program with n Boolean-valued variables and m equations cannot be solved in cn time for any constant c
Multipoint Estimates for Radial and Whole-Plane SLE

We prove upper bounds for the probability that a radial $$\hbox {SLE}_{\kappa }$$ curve, $$\kappa \in (0,8)$$ , comes within specified radii of n different points in the unit disc. Using this estimate, we then prove a similar upper bound for a whole-plane $$\hbox {SLE}_{\kappa }$$ curve. We then use these estimates to show that the lower Minkowski content of both the radial and whole-plane $$\hbox {SLE}_{\kappa }$$ traces restricted in a bounded region have finite moments of any order.
Distribution Market as a Ramping Aggregator for Grid Flexibility Support

The growing proliferation of microgrids and distributed energy resources in distribution networks has resulted in the development of Distribution Market Operator (DMO). This new entity will facilitate the management of the distributed resources and their interactions with upstream network and the wholesale market. At the same time, DMOs can tap into the flexibility potential of these distributed resources to address many of the challenges that system operators are facing. This paper investigates this opportunity and develops a distribution market scheduling model based on upstream network ramping flexibility requirements. That is, the distribution network will play the role of a flexibility resource in the system, with a relatively large size and potential, to help bulk system operators to address emerging ramping concerns. Numerical simulations demonstrate the effectiveness of the proposed model on when tested on a distribution system with several microgrids.
End-to-End Goal-Driven Web Navigation

We propose a goal-driven web navigation as a benchmark task for evaluating an agent with abilities to understand natural language and plan on partially observed environments. In this challenging task, an agent navigates through a website, which is represented as a graph consisting of web pages as nodes and hyperlinks as directed edges, to find a web page in which a query appears. The agent is required to have sophisticated high-level reasoning based on natural languages and efficient sequential decision-making capability to succeed. We release a software tool, called WebNav, that automatically transforms a website into this goal-driven web navigation task, and as an example, we make WikiNav, a dataset constructed from the English Wikipedia. We extensively evaluate different variants of neural net based artificial agents on WikiNav and observe that the proposed goal-driven web navigation well reflects the advances in models, making it a suitable benchmark for evaluating future progress. Furthermore, we extend the WikiNav with question-answer pairs from Jeopardy! and test the proposed agent based on recurrent neural networks against strong inverted index based search engines. The artificial agents trained on WikiNav outperforms the engined based approaches, demonstrating the capability of the proposed goal-driven navigation as a good proxy for measuring the progress in real-world tasks such as focused crawling and question-answering.
Are ‘Water Smart Landscapes’ Contagious? An Epidemic Approach on Networks to Study Peer Effects

We test the existence of a neighborhood based peer effect around participation in an incentive based conservation program called ‘Water Smart Landscapes’ (WSL) in the city of Las Vegas, Nevada. We use 15 years of geo-coded daily records of WSL program applications and approvals compiled by the Southern Nevada Water Authority and Clark County Tax Assessors rolls for home characteristics. We use this data to test whether a spatially mediated peer effect can be observed in WSL participation likelihood at the household level. We show that epidemic spreading models provide more flexibility in modeling assumptions, and also provide one mechanism for addressing problems associated with correlated unobservables than hazards models which can also be applied to address the same questions. We build networks of neighborhood based peers for 16 randomly selected neighborhoods in Las Vegas and test for the existence of a peer based influence on WSL participation by using a Susceptible-Exposed-Infected-Recovered epidemic spreading model (SEIR), in which a home can become infected via autoinfection or through contagion from its infected neighbors. We show that this type of epidemic model can be directly recast to an additive-multiplicative hazard model, but not to purely multiplicative one. Using both inference and prediction approaches we find evidence of peer effects in several Las Vegas neighborhoods.
Approximate IPA: Trading unbiasedness for simplicity

When Perturbation Analysis (PA) yields unbiased sensitivity estimators for expected-value performance functions in discrete event dynamic systems, it can be used for performance optimization of those functions. However, when PA is known to be unbiased, the complexity of its estimators often does not scale with the system's size. The purpose of this paper is to suggest an alternative approach to optimization which balances precision with computing efforts by trading off complicated, unbiased PA estimators for simple, biased approximate estimators. Furthermore, we provide guidelines for developing such estimators, that are largely based on the Stochastic Flow Modeling framework. We suggest that if the relative error (or bias) is not too large, then optimization algorithms such as stochastic approximation converge to a (local) minimum just like in the case where no approximation is used. We apply this approach to an example of balancing loss with buffer-cost in a finite-buffer queue, and prove a crucial upper bound on the relative error. This paper presents the initial study of the proposed approach, and we believe that if the idea gains traction then it may lead to a significant expansion of the scope of PA in optimization of discrete event systems.
The threshold for SDP-refutation of random regular NAE-3SAT

Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has the property that spectral/SDP algorithms can efficiently refute random instances when the constraint density is a large constant (with high probability). But do these methods work immediately above the "satisfiability threshold", or is there still a range of constraint densities for which random NAE-3SAT instances are unsatisfiable but hard to refute?We show that the latter situation prevails, at least in the context of random regular instances and SDP-based refutation. More precisely, whereas a random d-regular instance of NAE-3SAT is easily shown to be unsatisfiable (whp) once d ≥ 8, we establish the following sharp threshold result regarding efficient refutation: If d 13.5 then even the most basic spectral algorithm refutes satisfiability (whp).
Convergence rates in homogenization of Stokes systems

Abstract This paper studies the convergence rates in L 2 and H 1 of Dirichlet problems for Stokes systems with rapidly oscillating periodic coefficients, without any regularity assumptions on the coefficients.
Generic Schemes for Single-Molecule Kinetics. 2: Information Content of the Poisson Indicator.

Recently, we described a pathway analysis technique (paper 1) for analyzing generic schemes for single-molecule kinetics based upon the first-passage time distribution. Here, we employ this method to derive expressions for the Poisson indicator, a normalized measure of stochastic variation (essentially equivalent to the Fano factor and Mandel’s Q parameter), for various renewal (i.e., memoryless) enzymatic reactions. We examine its dependence on substrate concentration, without assuming all steps follow Poissonian kinetics. Based upon fitting to the functional forms of the first two waiting time moments, we show that, to second order, the non-Poissonian kinetics are generally underdetermined but can be specified in certain scenarios. For an enzymatic reaction with an arbitrary intermediate topology, we identify a generic minimum of the Poisson indicator as a function of substrate concentration, which can be used to tune substrate concentration to the stochastic fluctuations and to estimate the largest num...
Computations in Symmetric Fusion Categories in Characteristic p

We study properties of symmetric fusion categories in characteristic $p$. In particular, we introduce the notion of a super Frobenius-Perron dimension of an object $X$ of such a category, and derive an explicit formula for the Verlinde fiber functor $F(X)$ of $X$ (defined by the second author) in terms of the usual and super Frobenius-Perron dimension of $X$. We also compute the decomposition of symmetric powers of objects of the Verlinde category, generalizing a classical formula of Cayley and Sylvester for invariants of binary forms. Finally, we show that the Verlinde fiber functor is unique, and classify braided fusion categories of rank two and triangular semisimple Hopf algebras in any characteristic.
Accelerating Hessian-free optimization for Deep Neural Networks by implicit preconditioning and sampling

Hessian-free training has become a popular parallel second order optimization technique for Deep Neural Network training. This study aims at speeding up Hessian-free training, both by means of decreasing the amount of data used for training, as well as through reduction of the number of Krylov subspace solver iterations used for implicit estimation of the Hessian. In this paper, we develop an L-BFGS based preconditioning scheme that avoids the need to access the Hessian explicitly. Since L-BFGS cannot be regarded as a fixed-point iteration, we further propose the employment of flexible Krylov subspace solvers that retain the desired theoretical convergence guarantees of their conventional counterparts. Second, we propose a new sampling algorithm, which geometrically increases the amount of data utilized for gradient and Krylov subspace iteration calculations. On a 50-hr English Broadcast News task, we find that these methodologies provide roughly a 1.5× speed-up, whereas, on a 300-hr Switchboard task, these techniques provide over a 2.3× speedup, with no loss in WER. These results suggest that even further speed-up is expected, as problems scale and complexity grows.
Knapsack problems in groups

We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete.
Coded Sparse Matrix Multiplication

In a large-scale and distributed matrix multiplication problem $C=A^{\intercal}B$, where $C\in\mathbb{R}^{r\times t}$, the coded computation plays an important role to effectively deal with "stragglers" (distributed computations that may get delayed due to few slow or faulty processors). However, existing coded schemes could destroy the significant sparsity that exists in large-scale machine learning problems, and could result in much higher computation overhead, i.e., $O(rt)$ decoding time. In this paper, we develop a new coded computation strategy, we call \emph{sparse code}, which achieves near \emph{optimal recovery threshold}, \emph{low computation overhead}, and \emph{linear decoding time} $O(nnz(C))$. We implement our scheme and demonstrate the advantage of the approach over both uncoded and current fastest coded strategies.
Gromov-Wasserstein Alignment of Word Embedding Spaces

Cross-lingual or cross-domain correspondences play key roles in tasks ranging from machine translation to transfer learning. Recently, purely unsupervised methods operating on monolingual embeddings have become effective alignment tools. Current state-of-the-art methods, however, involve multiple steps, including heuristic post-hoc refinement strategies. In this paper, we cast the correspondence problem directly as an optimal transport (OT) problem, building on the idea that word embeddings arise from metric recovery algorithms. Indeed, we exploit the Gromov-Wasserstein distance that measures how similarities between pairs of words relate across languages. We show that our OT objective can be estimated efficiently, requires little or no tuning, and results in performance comparable with the state-of-the-art in various unsupervised word translation tasks.
Modeling human understanding of complex intentional action with a Bayesian nonparametric subgoal model

Most human behaviors consist of multiple parts, steps, or sub-tasks. These structures guide our action planning and execution, but when we observe others, the latent structure of their actions is typically unobservable, and must be inferred in order to learn new skills by demonstration, or to assist others in completing their tasks. For example, an assistant who has learned the subgoal structure of a colleague's task can more rapidly recognize and support their actions as they unfold. Here we model how humans infer subgoals from observations of complex action sequences using a nonparametric Bayesian model, which assumes that observed actions are generated by approximately rational planning over unknown subgoal sequences. We test this model with a behavioral experiment in which humans observed different series of goal-directed actions, and inferred both the number and composition of the subgoal sequences associated with each goal. The Bayesian model predicts human subgoal inferences with high accuracy, and significantly better than several alternative models and straightforward heuristics. Motivated by this result, we simulate how learning and inference of subgoals can improve performance in an artificial user assistance task. The Bayesian model learns the correct subgoals from fewer observations, and better assists users by more rapidly and accurately inferring the goal of their actions than alternative approaches.
The adversarial noise threshold for distributed protocols

We consider the problem of implementing distributed protocols, despite adversarial channel errors, on synchronous-messaging networks with arbitrary topology.In our first result we show that any n-party T-round protocol on an undirected communication network G can be compiled into a robust simulation protocol on a sparse (O(n) edges) subnetwork so that the simulation tolerates an adversarial error rate of Ω(1/n); the simulation has a round complexity of O([EQUATION]), where m is the number of edges in G. (So the simulation is work-preserving up to a log factor.) The adversary's error rate is within a constant factor of optimal. Given the error rate, the round complexity blowup is within a factor of O(k log n) of optimal, where k is the edge connectivity of G. We also determine that the maximum tolerable error rate on directed communication networks is Θ(1/s) where s is the number of edges in a minimum equivalent digraph.Next we investigate adversarial per-edge error rates, where the adversary is given an error budget on each edge of the network. We determine the limit for tolerable per-edge error rates on an arbitrary directed graph to within a factor of 2. However, the construction that approaches this limit has exponential round complexity, so we give another compiler, which transforms T-round protocols into O(mT)-round simulations, and prove that for polynomial-query black box compilers, the per-edge error rate tolerated by this last compiler is within a constant factor of optimal.
Cluster algebras: an introduction

Cluster algebras are commutative rings with a set of distinguished generators having a remarkable combinatorial structure. They were introduced by Fomin and Zelevinsky in 2000 in the context of Lie theory, but have since appeared in many other contexts, from Poisson geometry to triangulations of surfaces and Teichmuller theory. In this expository paper we give an introduction to cluster algebras, and illustrate how this framework naturally arises in Teichmuller theory. We then sketch how the theory of cluster algebras led to a proof of the Zamolodchikov periodicity conjecture in mathematical physics.
Predicting User-Interactions on Reddit

In order to keep up with the demand of curating the deluge of crowd-sourced content, social media platforms leverage user interaction feedback to make decisions about which content to display, highlight, and hide. User interactions such as likes, votes, clicks, and views are assumed to be a proxy of a content’s quality, popularity, or news-worthiness. In this paper we ask: how predictable are the interactions of a user on social mediaƒ To answer this question we recorded the clicking, browsing, and voting behavior of 186 Reddit users over a year. We present interesting descriptive statistics about their combined 339,270 interactions, and we find that relatively simple models are able to predict users’ individual browse- or vote-interactions with reasonable accuracy.
The singular locus of semisimple Hessenberg varieties

Abstract Although regular semisimple Hessenberg varieties are smooth and irreducible, semisimple Hessenberg varieties are not necessarily smooth in general. In this paper we determine the irreducible components of semisimple Hessenberg varieties corresponding to the standard Hessenberg space in all Lie types. We prove that these irreducible components are smooth and give an explicit description of their intersections, which constitute the singular locus. We conclude with an example of a semisimple Hessenberg variety corresponding to another Hessenberg space which is singular and irreducible, showing that results of this nature do not hold for all semisimple Hessenberg varieties.
The transfer is functorial

Abstract We prove that the Becker–Gottlieb transfer is functorial up to homotopy, for all fibrations with finitely dominated fibers. This resolves a lingering foundational question about the transfer, which was originally defined in the late 1970s in order to simplify the proof of the Adams conjecture. Our approach differs from previous attempts in that we closely emulate the geometric argument in the case of a smooth fiber bundle. This leads to a “multiplicative” description of the transfer, different from the standard presentation as the trace of a diagonal map.
Rapid prototyping of a novel and flexible paper based oxygen sensing patch via additive inkjet printing process

A novel and flexible oxygen sensing patch was successfully developed for wearable, industrial, food packaging, pharmaceutical and biomedical applications using a cost-efficient and rapid prototypable additive inkjet print manufacturing process. An oxygen sensitive ink was formulated by dissolving ruthenium dye and ethyl cellulose polymer in ethanol in a 1 : 1 : 98 (w/w/w) ratio. The patch was fabricated by depositing the oxygen sensitive ink on a flexible parchment paper substrate using an inkjet printing process. A maximum absorbance from 430 nm to 480 nm and a fluorescence of 600 nm was observed for the oxygen sensitive ink. The capability of the oxygen sensitive patch was investigated by measuring the fluorescence quenching lifetime of the printed dye for varying oxygen concentration levels. A fluorescence lifetime decay (τ) from ≈4 μs to ≈1.9 μs was calculated for the printed oxygen sensor patch, for oxygen concentrations varying from ≈5 mg L−1 to ≈25 mg L−1. A sensitivity of 0.11 μs mg L−1 and a correlation coefficient of 0.9315 was measured for the printed patches. The results demonstrated the feasibility of employing an inkjet printing process for the rapid prototyping of flexible and moisture resistant oxygen sensitive patches which facilitates a non-invasive method for monitoring oxygen and its concentration levels.
Fault Tolerant Clustering Revisited

In discrete k-center and k-median clustering, we are given a set of points P in a metric space M, and the task is to output a set C P, jCj = k, such that the cost of clustering P using C is as small as possible. For k-center, the cost is the furthest a point has to travel to its nearest center, whereas for k-median, the cost is the sum of all point to nearest center distances. In the fault-tolerant versions of these problems, we are given an additional parameter 1 ‘ k, such that when computing the cost of clustering, points are assigned to their ‘th nearest-neighbor in C, instead of their nearest neighbor. We provide constant factor approximation algorithms for these problems that are both conceptually simple and highly practical from an implementation stand-point.
Accurate Least-Squares P$_N$ Scaling based on Problem Optical Thickness for solving Neutron Transport Problems

Abstract In this paper, we present an accurate and robust scaling operator based on material optical thickness (OT) for the least-squares spherical harmonics (LSP N ) method for solving neutron transport problems. LSP N without proper scaling is known to be erroneous in highly scattering medium, if the optical thickness of the material is large. A previously presented scaling developed by Manteuffel et al. does improve the accuracy of LSP N in problems where the material is optically thick. With that method, however, essentially no scaling is applied in optically thin materials, which can lead to an erroneous solutions in the presence of a highly scattering medium. Another scaling approach, called the reciprocal-removal (RR) scaled LSP N , which is equivalent to the self-adjoint angular flux (SAAF) equation, has numerical issues in highly-scattering materials due to a singular weighting. We propose a scaling based on optical thickness that improves the solution in optically thick media while avoiding the singularity in the SAAF formulation.
Homogeneity for a class of Riemannian quotient manifolds

Abstract We study Riemannian coverings φ : M ˜ → Γ \ M ˜ where M ˜ is a normal homogeneous space G / K 1 fibered over another normal homogeneous space M = G / K and K is locally isomorphic to a nontrivial product K 1 × K 2 . The most familiar such fibrations π : M ˜ → M are the natural fibrations of Stiefel manifolds S O ( n 1 + n 2 ) / S O ( n 1 ) over Grassmann manifolds S O ( n 1 + n 2 ) / [ S O ( n 1 ) × S O ( n 2 ) ] and the twistor space bundles over quaternionic symmetric spaces (= quaternion-Kaehler symmetric spaces = Wolf spaces). The most familiar of these coverings φ : M ˜ → Γ \ M ˜ are the universal Riemannian coverings of spherical space forms. When M = G / K is reasonably well understood, in particular when G / K is a Riemannian symmetric space or when K is a connected subgroup of maximal rank in G, we show that the Homogeneity Conjecture holds for M ˜ . In other words we show that Γ \ M ˜ is homogeneous if and only if every γ ∈ Γ is an isometry of constant displacement. In order to find all the isometries of constant displacement on M ˜ we work out the full isometry group of M ˜ , extending Elie Cartan's determination of the full group of isometries of a Riemannian symmetric space. We also discuss some pseudo-Riemannian extensions of our results.
Seeing Invisible Poses: Estimating 3D Body Pose from Egocentric Video

Understanding the camera wearers activity is central to egocentric vision, yet one key facet of that activity is inherently invisible to the camera&#x2014;the wearers body pose. Prior work focuses on estimating the pose of hands and arms when they come into view, but this 1) gives an incomplete view of the full body posture, and 2) prevents any pose estimate at all in many frames, since the hands are only visible in a fraction of daily life activities. We propose to infer the invisible pose of a person behind the egocentric camera. Given a single video, our efficient learning-based approach returns the full body 3D joint positions for each frame. Our method exploits cues from the dynamic motion signatures of the surrounding scene&#x2014;which change predictably as a function of body pose&#x2014;as well as static scene structures that reveal the viewpoint (e.g., sitting vs. standing). We further introduce a novel energy minimization scheme to infer the pose sequence. It uses soft predictions of the poses per time instant together with a non-parametric model of human pose dynamics over longer windows. Our method outperforms an array of possible alternatives, including typical deep learning approaches for direct pose regression from images.
In search of the Hohenberg-Kohn theorem

The Hohenberg-Kohn theorem, a cornerstone of electronic density functional theory, concerns uniqueness of external potentials yielding given ground densities of an N-body system. The problem is rigorously explored in a universe of three-dimensional Kato-class potentials, with emphasis on trade-offs between conditions on the density and conditions on the potential sufficient to ensure uniqueness. Sufficient conditions range from none on potentials coupled with everywhere strict positivity of the density to none on the density coupled with something a little weaker than local 3N/2-power integrability of the potential on a connected full-measure set. A second theme is localizability, that is, the possibility of uniqueness over subsets of R3 under less stringent conditions.
Exploiting channel correlation and PU traffic memory for opportunistic spectrum scheduling

We consider a cognitive radio network with multiple primary users (PUs) and one secondary user (SU), where a spectrum server is utilized for scheduling the SU to transmit over one of the PU channels opportunistically. One practical yet challenging scenario is when both the PU occupancy and the channel fading vary over time and exhibit temporal correlations. Little work has been done for exploiting such temporal memory in the channel fading and the PU occupancy simultaneously for opportunistic spectrum scheduling. Further, the scenario where PU occupancy possesses a long temporal memory has been underexplored as well. By casting the problem as a partially observable Markov decision process, we aim to understand the intricate tradeoffs resulting from the interactions of the two sets of system states (i.e., channel fading and PU occupancy) and the impact of the associated temporal memory. We identify and illustrate a set of multi-tier tradeoffs that go beyond the classic “exploitation vs. exploration” tradeoff. For certain special cases, we establish the optimality of a simple greedy policy. To build a more comprehensive understanding, we then introduce a full-observation genie-aided system that helps in decomposing the tradeoffs in the original system into multiple layers, which we examine progressively. Numerical examples indicate that the optimal scheduler in the original system, with observation on the scheduled channel only, achieves a performance very close to the genie-aided system. In addition, the optimal policy in the original system significantly outperforms randomized scheduling, as well as a policy that explores memory in one system state only, pointing to the merit of jointly exploiting the temporal correlation structure in both channel fading and PU occupancy.
Functions of nearly maximal Gowers-Host-Kra norms on Euclidean spaces

Let $$k\ge 2, n\ge 1$$ be integers. Let $$f: {\mathbb {R}}^{n} \rightarrow {\mathbb {C}}$$. The kth Gowers–Host–Kra norm of f is defined recursively by $$\begin{aligned} \Vert f\Vert _{U^{k}}^{2^{k}} =\int _{{\mathbb {R}}^{n}} \Vert T^{h}f \cdot {\bar{f}} \Vert _{U^{k-1}}^{2^{k-1}} \, \text {d}h \end{aligned}$$with $$T^{h}f(x) = f(x+h)$$ and $$\Vert f\Vert _{U^1} = | \int _{{\mathbb {R}}^{n}} f(x)\, \text {d}x |$$. These norms were introduced by Gowers (Geom Funct Anal 11:465–588, 2001) in his work on Szemeredi’s theorem, and by Host and Kra (in Ann Math 161:398–488, 2005) in ergodic setting. These norms are also discussed extensively in Tao and Vu (in Additive combinatorics, Cambridge University Press, 2016). It is shown by Eisner and Tao (in J Anal Math 117:133–186, 2012) that for every $$k\ge 2$$ there exist $$A(k,n)< \infty $$ and $$p_{k} = 2^{k}/(k+1)$$ such that $$\Vert f\Vert _{U^{k}} \le A(k,n)\Vert f\Vert _{p_{k}}$$, for all $$f \in L^{p_{k}}({\mathbb {R}}^{n})$$. The optimal constant A(k, n) and the extremizers for this inequality are known [9]. In this dissertation, it is shown that if the ratio $$\Vert f \Vert _{U^{k}}/\Vert f\Vert _{p_{k}}$$ is nearly maximal, then f is close in $$L^{p_{k}}$$ norm to an extremizer.
Singular loci of Bruhat-Hibi toric varieties

For the toric variety X associated to the Bruhat poset of Schubert varieties in a minuscule G/P, we describe the singular locus in terms of the faces of the associated polyhedral cone. We further show that the singular locus is pure of codimension 3 in X, and the generic singularities are of cone type.
Contact localization through spatially overlapping piezoresistive signals

Achieving high spatial resolution in contact sensing for robotic manipulation often comes at the price of increased complexity in fabrication and integration. One traditional approach is to fabricate a large number of taxels, each delivering an individual, isolated response to a stimulus. In contrast, we propose a method where the sensor simply consists of a continuous volume of piezoresistive elastomer with a number of electrodes embedded inside. We measure piezoresistive effects between all pairs of electrodes in the set, and count on this rich signal set containing the information needed to pinpoint contact location with high accuracy using regression algorithms. In our validation experiments, we demonstrate submillimeter median accuracy in locating contact on a 10mm by 16mm sensor using only four electrodes (creating six unique pairs). In addition to extracting more information from fewer wires, this approach lends itself to simple fabrication methods and makes no assumptions about the underlying geometry, simplifying future integration on robot fingers.
Asynchronous parallel stochastic gradient for nonconvex optimization

Asynchronous parallel implementations of stochastic gradient (SG) have been broadly used in solving deep neural network and received many successes in practice recently. However, existing theories cannot explain their convergence and speedup properties, mainly due to the nonconvexity of most deep learning formulations and the asynchronous parallel mechanism. To fill the gaps in theory and provide theoretical supports, this paper studies two asynchronous parallel implementations of SG: one is over a computer network and the other is on a shared memory system. We establish an ergodic convergence rate O(1/ √K) for both algorithms and prove that the linear speedup is achievable if the number of workers is bounded by √K (K is the total number of iterations). Our results generalize and improve existing analysis for convex minimization.
SMART: SEMANTICALLY MASHUP REST WEB SERVICES

A mashup is a combination of information from more than one source, mixed up in a way to create something new, or at least useful. Anyone can find mashups on the internet, but these are always specifically designed for a predefined purpose. To change that fact, we implemented a new platform we called the SMART platform. SMART enables the user to make his own choices as for the REST web services he needs to call in order to build an intelligent personalized mashup, from a Google-like simple search interface, without needing any programming skills. In order to achieve this goal, we defined an ontology that can hold REST web services descriptions. These descriptions encapsulate mainly, the input type needed for a service, its output type, and the kind of relation that ties the input to the output. Then, by matching the user input query keywords, with the REST web services definitions in our ontology, we can find registered services individuals in this ontology, and construct the raw REST query for each service found. The wrap up from the keywords, into semantic definitions, in order to find the matching service individual, then the wrap down from the semantic service description of the found individual, to the raw REST call, and finally the wrap up of the result again into semantic individuals, is done for two main purposes: the first to let the user use simple keywords in order to build complex mashups, and the second to benefit from the ontology’s inference engine in a way, where services instances can be tied together into an intelligent mashup, simply by making each service output individuals, stand as the next service input.