cssi/SciSciGPT-SciSciNet huggingface dataset:
Efficient, High-Quality Stack Rearrangement

This work studies rearrangement problems involving the sorting of robots or objects in stack-like containers, which can be accessed only from one side. Two scenarios are considered: one where every robot or object needs to reach a particular stack, and a setting in which each robot has a distinct position within a stack. In both cases, the goal is to minimize the number of stack removals that need to be performed. Stack rearrangement is shown to be intimately connected to pebble motion problems, a useful abstraction in multi-robot path planning. Through this connection, feasibility of stack rearrangement can be readily addressed. Lower and upper bounds on optimality are established, which differ only by a logarithmic factor, in terms of stack removals. An algorithmic solution is then developed that produces suboptimal paths much quicker than a pebble motion solver. Furthermore, informed search-based methods are proposed for finding high-quality solutions. The efficiency and desirable scalability of the methods are demonstrated in simulation.
A Comparison of Classifiers in Performing Speaker Accent Recognition Using MFCCs

An algorithm involving Mel-Frequency Cepstral Coefficients (MFCCs) is provided to perform signal feature extraction for the task of speaker accent recognition. Then different classifiers are compared based on the MFCC feature. For each signal, the mean vector of MFCC matrix is used as an input vector for pattern recognition. A sample of 330 signals, containing 165 US voice and 165 non-US voice, is analyzed. By comparison, k-nearest neighbors yield the highest average test accuracy, after using a cross-validation of size 500, and least time being used in the computation.
How to decompose a permutation into a pair of labeled Dyck paths by playing a game

We give a bijection between permutations of 1, . . . , 2n and certain pairs of Dyck paths with labels on the down steps. The bijection arises from a game in which two players alternate selecting from a set of 2n items: the permutation encodes the players’ preference ordering of the items, and the Dyck paths encode the order in which items are selected under optimal play. We enumerate permutations by certain new statistics, AA inversions and BB inversions, which have natural interpretations in terms of the game. We derive identities such as ∑
Fast and Accurate Approximation of the Full Conditional for Gamma Shape Parameters

The gamma distribution arises frequently in Bayesian models, but there is not an easy-to-use conjugate prior for the shape parameter of a gamma. This inconvenience is usually dealt with by using ei...
The phase limit set of a variety

MOUNIR NISSE AND FRANK SOTTILEAbstract. A coamoeba is the image of a subvariety of a complex torus under the argumentmap to the realtorus. We describe the structure ofthe boundary ofthe coamoebaofavariety,which we relate to its logarithmic limit set. Detailed examples of lines in three-dimensionalspace illustrate and motivate these results.
Uniform $\varepsilon$-Stability of Distributed Nonlinear Filtering Over DNAs: Gaussian-Finite HMMs

In this paper, we study stability of distributed filtering of Markov chains with finite state space, partially observed in conditionally Gaussian noise. We consider a nonlinear filtering scheme over a distributed network of agents, which relies on the distributed evaluation of the likelihood part of the respective centralized estimator. Distributed evaluation of likelihoods is based on a particular specialization of the alternating direction method of multipliers for fast average consensus. Assuming the same number of consensus steps between any two consecutive noisy measurements for each sensor in the network, we fully characterize a minimal number of such steps, so that the distributed filter remains uniformly stable with a prescribed accuracy level, $\varepsilon \in (0,1]$ , within a finite operational horizon, $T$ , and across all sensors. Stability is in the sense of the $\ell _{1}$ -norm between the centralized and distributed versions of the posterior at each sensor, and at each time within $T$ . Roughly speaking, our main result shows that uniform $\varepsilon$ -stability of the distributed filtering process depends loglinearly on $T$ and the size of the network, and logarithmically on $1/\varepsilon$ . If this total loglinear bound is fulfilled, any additional consensus iterations will incur a fully quantified further exponential decay in the consensus error. Our bounds are universal, in the sense that they are independent of the particular structure of the Gaussian Hidden Markov Model under consideration.
Debye Sources, Beltrami Fields, and a Complex Structure on Maxwell Fields

The Debye source representation for solutions to the time-harmonic Maxwell equations is extended to bounded domains with finitely many smooth boundary components. A strong uniqueness result is proved for this representation. Natural complex structures are identified on the vector spaces of time-harmonic Maxwell fields. It is shown that these complex structures are uniformized by the Debye source representation, that is, represented by a fixed linear map on a fixed vector space, independent of the frequency. This complex structure relates time-harmonic Maxwell fields to constant-k Beltrami fields, i.e., solutions of the equation ∇×E=k E. A family of self-adjoint boundary conditions are defined for the Beltrami operator. This leads to a proof of the existence of zero-flux, constant-k, force-free Beltrami fields for any bounded region in ℝ3, as well as a constructive method to find them. The family of self-adjoint boundary value problems defines a new spectral invariant for bounded domains in ℝ3.© 2015 Wiley Periodicals, Inc.
Spatially Resolved Thermometry of Resistive Memory Devices.

The operation of resistive and phase-change memory (RRAM and PCM) is controlled by highly localized self-heating effects, yet detailed studies of their temperature are rare due to challenges of nanoscale thermometry. Here we show that the combination of Raman thermometry and scanning thermal microscopy (SThM) can enable such measurements with high spatial resolution. We report temperature-dependent Raman spectra of HfO2, TiO2 and Ge2Sb2Te5 (GST) films, and demonstrate direct measurements of temperature profiles in lateral PCM devices. Our measurements reveal that electrical and thermal interfaces dominate the operation of such devices, uncovering a thermal boundary resistance of 28 ± 8 m2K/GW at GST-SiO2 interfaces and an effective thermopower 350 ± 50 µV/K at GST-Pt interfaces. We also discuss possible pathways to apply Raman thermometry and SThM techniques to nanoscale and vertical resistive memory devices.
Anderson localization in a partially random Bragg grating and a conserved area theorem

We investigate the gradual emergence of the disorder-related phenomena in intermediate regimes between a deterministic periodic Bragg grating and a fully random grating and highlight two critical properties of partially disordered Bragg gratings. First, the integral of the logarithm of the transmittance over the reciprocal wavevector space is a conserved quantity. Therefore, adding disorder merely redistributes the transmittance over the reciprocal space. Second, for any amount of disorder, the average transmittance decays exponentially with the number of grating layers in the simple form of exp(-ηN) for sufficiently large N, where η is a constant, and N is the number of layers. Conversely, the simple exponential decay form does not hold for small N except for a highly disordered system. Implications of these findings are demonstrated.
On Some Conformally Invariant Operators in Euclidean Space

The aim of this paper is to correct a mistake in earlier work on the conformal invariance of Rarita-Schwinger operators and use the method of correction to develop properties of some conformally invariant operators in the Rarita-Schwinger setting. We also study properties of some other Rarita-Schwinger type operators, for instance, twistor operators and dual twistor operators. This work is also intended as an attempt to motivate the study of Rarita-Schwinger operators via some representation theory. This calls for a review of earlier work by Stein and Weiss.
This before That: Causal Precedence in the Biomedical Domain

Causal precedence between biochemical interactions is crucial in the biomedical domain, because it transforms collections of individual interactions, e.g., bindings and phosphorylations, into the causal mechanisms needed to inform meaningful search and inference. Here, we analyze causal precedence in the biomedical domain as distinct from open-domain, temporal precedence. First, we describe a novel, hand-annotated text corpus of causal precedence in the biomedical domain. Second, we use this corpus to investigate a battery of models of precedence, covering rule-based, feature-based, and latent representation models. The highest-performing individual model achieved a micro F1 of 43 points, approaching the best performers on the simpler temporal-only precedence tasks. Feature-based and latent representation models each outperform the rule-based models, but their performance is complementary to one another. We apply a sieve-based architecture to capitalize on this lack of overlap, achieving a micro F1 score of 46 points.
A machine learning framework to forecast wave conditions

Abstract A machine learning framework is developed to estimate ocean-wave conditions. By supervised training of machine learning models on many thousands of iterations of a physics-based wave model, accurate representations of significant wave heights and period can be used to predict ocean conditions. A model of Monterey Bay was used as the example test site; it was forced by measured wave conditions, ocean-current nowcasts, and reported winds. These input data along with model outputs of spatially variable wave heights and characteristic period were aggregated into supervised learning training and test data sets, which were supplied to machine learning models. These machine learning models replicated wave heights from the physics-based model with a root-mean-squared error of 9 cm and correctly identify over 90% of the characteristic periods for the test-data sets. Impressively, transforming model inputs to outputs through matrix operations requires only a fraction ( 1 / 1 , 000 th ) of the computation time compared to forecasting with the physics-based model.
Covert Communication Over a $K$ -User Multiple-Access Channel

We consider a scenario in which $K$ transmitters attempt to communicate covert messages reliably to a legitimate receiver over a discrete memoryless multiple-access channel (MAC) while simultaneously escaping detection from an adversary who observes their communication through another discrete memoryless MAC. We assume that each transmitter may use a secret key that is shared only between itself and the legitimate receiver. We show that each of the $K$ transmitters can transmit on the order of $\sqrt {n}$ reliable and covert bits per $n$ channel uses, exceeding which, the warden will be able to detect the communication. We identify the optimal pre-constants of the scaling, which leads to a complete characterization of the covert capacity region of the $K$ -user binary-input MAC. We show that, asymptotically, all sum-rate constraints are inactive unlike the traditional MAC capacity region. We also characterize the channel conditions that have to be satisfied for the transmitters to operate without a secret key.
Diffusion of real-time information in social-physical networks

We study the diffusion behavior of real-time information. Typically, real-time information is valuable only for a limited time duration, and hence needs to be delivered before its “deadline.” Therefore, real-time information is much easier to spread among a group of people with frequent interactions than between isolated individuals. With this insight, we consider a social network which consists of many cliques and information can spread quickly within a clique. Furthermore, information can also be shared through online social networks, such as Facebook, twitter, Youtube, etc. We characterize the diffusion of real-time information by studying the phase transition behaviors. Capitalizing on the theory of inhomogeneous random networks, we show that the social network has a critical threshold above which information epidemics are very likely to happen. We also theoretically quantify the fractional size of individuals that finally receive the message. The numerical results indicate that real-time information could be much easier to propagate in a social network when large size cliques exist.
Identifying and removing the cell-cycle effect from single-cell RNA-Sequencing data

Single-cell RNA-Sequencing (scRNA-Seq) is a revolutionary technique for discovering and describing cell types in heterogeneous tissues, yet its measurement of expression often suffers from large systematic bias. A major source of this bias is the cell cycle, which introduces large within-cell-type heterogeneity that can obscure the differences in expression between cell types. The current method for removing the cell-cycle effect is unable to effectively identify this effect and has a high risk of removing other biological components of interest, compromising downstream analysis. We present ccRemover, a new method that reliably identifies the cell-cycle effect and removes it. ccRemover preserves other biological signals of interest in the data and thus can serve as an important pre-processing step for many scRNA-Seq data analyses. The effectiveness of ccRemover is demonstrated using simulation data and three real scRNA-Seq datasets, where it boosts the performance of existing clustering algorithms in distinguishing between cell types.
Area spectral efficiency and coverage for mixed duplexing networks with directional transmissions

In this paper, we consider a system of small cells assuming full duplex (FD) capable base stations (BSs) and half duplex (HD) user equipment (UEs). We investigate a mixed duplexing cellular system composed of FD and HD cells, when BSs are using directional transmissions. A stochastic geometry based model of the proposed system is used to derive the coverage and area spectral efficiency (ASE) of both BSs and UEs. The effect of FD cells on the performance of the mixed system is presented under different degree of directionality at the BSs. We show that enabling directional transmissions at the BSs yields significant ASE and coverage gain in both downlink and uplink. With directional transmissions, the ASE increases rapidly with the number of FD cells while the drop in the coverage rate due to FD operations reduces significantly.
Learning to Draw Samples with Amortized Stein Variational Gradient Descent.

We propose a simple algorithm to train stochastic neural networks to draw samples from given target distributions for probabilistic inference. Our method is based on iteratively adjusting the neural network parameters so that the output changes along a Stein variational gradient direction (Liu & Wang, 2016) that maximally decreases the KL divergence with the target distribution. Our method works for any target distribution specified by their unnormalized density function, and can train any black-box architectures that are differentiable in terms of the parameters we want to adapt. We demonstrate our method with a number of applications, including variational autoencoder (VAE) with expressive encoders to model complex latent space structures, and hyper-parameter learning of MCMC samplers that allows Bayesian inference to adaptively improve itself when seeing more data.
Reverse iterative volume sampling for linear regression

We study the following basic machine learning task: Given a fixed set of input points in ℝd for a linear regression problem, we wish to predict a hidden response value for each of the points. We can only afford to attain the responses for a small subset of the points that are then used to construct linear predictions for all points in the dataset. The performance of the predictions is evaluated by the total square loss on all responses (the attained as well as the remaining hidden ones). We show that a good approximate solution to this least squares problem can be obtained from just dimension d many responses by using a joint sampling technique called volume sampling. Moreover, the least squares solution obtained for the volume sampled subproblem is an unbiased estimator of optimal solution based on all n responses. This unbiasedness is a desirable property that is not shared by other common subset selection techniques. Motivated by these basic properties, we develop a theoretical framework for studying volume sampling, resulting in a number of new matrix expectation equalities and statistical guarantees which are of importance not only to least squares regression but also to numerical linear algebra in general. Our methods also lead to a regularized variant of volume sampling, and we propose the first efficient algorithm for volume sampling which makes this technique a practical tool in the machine learning toolbox. Finally, we provide experimental evidence which confirms our theoretical findings.
Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization

As application demands for zeroth-order (gradient-free) optimization accelerate, the need for variance reduced and faster converging approaches is also intensifying. This paper addresses these challenges by presenting: a) a comprehensive theoretical analysis of variance reduced zeroth-order (ZO) optimization, b) a novel variance reduced ZO algorithm, called ZO-SVRG, and c) an experimental evaluation of our approach in the context of two compelling applications, black-box chemical material classification and generation of adversarial examples from black-box deep neural network models. Our theoretical analysis uncovers an essential difficulty in the analysis of ZO-SVRG: the unbiased assumption on gradient estimates no longer holds. We prove that compared to its first-order counterpart, ZO-SVRG with a two-point random gradient estimator could suffer an additional error of order $O(1/b)$, where $b$ is the mini-batch size. To mitigate this error, we propose two accelerated versions of ZO-SVRG utilizing variance reduced gradient estimators, which achieve the best rate known for ZO stochastic optimization (in terms of iterations). Our extensive experimental results show that our approaches outperform other state-of-the-art ZO algorithms, and strike a balance between the convergence rate and the function query complexity.
Optimal Decentralized Control With Asymmetric One-Step Delayed Information Sharing

We consider optimal control of decentralized LQG problems for plants having nested subsystems controlled by two players with asymmetric information sharing patterns between them. In the main scenario, the players are assumed to have a unidirectional error-free, unlimited-rate communication channel with a unit delay in one direction and no communication in the other. A second model, presented for completeness, considers a channel with no delay in one direction and a unit delay in the other. Delayed information-sharing patterns do not, in general, admit linear optimal control laws and are thus difficult to control optimally. However, in these scenarios, we show that the problems have a partially nested information structure and, thus, linear optimal control laws exist. Summary statistics are identified and analytical solutions to the optimal control laws are derived. State and output feedback cases are solved for both scenarios.
Indecomposable and noncrossed product division algebras over curves over complete discrete valuation rings

Abstract Let T be a complete discrete valuation ring and X ˆ a smooth projective curve over S = spec ( T ) with closed fibre X . Denote by F the function field of X ˆ and by F ˆ the completion of F with respect to the discrete valuation defined by X , the closed fibre. In this paper, we construct indecomposable and noncrossed product division algebras over F . This is done by defining an index preserving group homomorphism s : Br ( F ˆ ) ′ → Br ( F ) ′ , and using it to lift indecomposable and noncrossed product division algebras over F ˆ .
Multiple phase transitions in long-range first-passage percolation on square lattices

We consider a model of long-range first-passage percolation on the d-dimensional square lattice in which any two distinct vertices are connected by an edge having exponentially distributed passage time with mean , where α > 0 is a fixed parameter and is the l1 –norm on . We analyze the asymptotic growth rate of the set ℬt, which consists of all such that the first-passage time between the origin 0 and x is at most t as t ∞. We show that depending on the values of α there are four growth regimes: (i) instantaneous growth for α 2d + 1 like the nearest-neighbor first-passage percolation model corresponding to α = ∞.© 2015 Wiley Periodicals, Inc.
On a family of symmetric rational functions

Abstract This paper is about a family of symmetric rational functions that form a one-parameter generalization of the classical Hall–Littlewood polynomials. We introduce two sets of (skew and non-skew) functions that are akin to the P and Q Hall–Littlewood polynomials. We establish (a) a combinatorial formula that represents our functions as partition functions for certain path ensembles in the square grid; (b) symmetrization formulas for non-skew functions; (c) identities of Cauchy and Pieri type; (d) explicit formulas for principal specializations; (e) two types of orthogonality relations for non-skew functions. Our construction is closely related to the half-infinite volume, finite magnon sector limit of the higher spin six-vertex (or XXZ) model, with both sets of functions representing higher spin six-vertex partition functions and/or transfer-matrices for certain domains.
Minimal elementary end extensions

Suppose that \({\mathcal M}\models \mathsf{PA}\) and \({\mathfrak X} \subseteq {\mathcal P}(M)\). If \({\mathcal M}\) has a finitely generated elementary end extension \({\mathcal N}\succ _\mathsf{end} {\mathcal M}\) such that \(\{X \cap M : X \in {{\mathrm{Def}}}({\mathcal N})\} = {\mathfrak X}\), then there is such an \({\mathcal N}\) that is, in addition, a minimal extension of \({\mathcal M}\) iff every subset of M that is \(\Pi _1^0\)-definable in \(({\mathcal M}, {\mathfrak X})\) is the countable union of \(\Sigma _1^0\)-definable sets.
Valuations of semirings

We develop notions of valuations on a semiring, with a view toward extending the classical theory of abstract nonsingular curves and discrete valuation rings to this general algebraic setting; the novelty of our approach lies in the implementation of hyperrings to yield a new definition ( hyperfield valuation ). In particular, we classify valuations on the semifield Q max Q m a x (the max-plus semifield of rational numbers) and also valuations on the ‘function field’ Q max (T) Q m a x ( T ) (the semifield of rational functions over Q max Q m a x ) which are trivial on Q max Q m a x . We construct and study the abstract curve associated to Q max (T) Q m a x ( T ) in relation to the projective line P F 1 1 over the field with one element F 1 F 1 and the tropical projective line. Finally, we discuss possible connections to tropical curves and Berkovich's theory of analytic spaces.
Differential Privacy on Finite Computers

We consider the problem of designing and analyzing differentially private algorithms that can be implemented on discrete models of computation in strict polynomial time, motivated by known attacks on floating point implementations of real-arithmetic differentially private algorithms (Mironov, CCS 2012) and the potential for timing attacks on expected polynomial-time algorithms. We use a case study: the basic problem of approximating the histogram of a categorical dataset over a possibly large data universe X. The classic Laplace Mechanism (Dwork, McSherry, Nissim, Smith, TCC 2006 and J. Privacy & Confidentiality 2017) does not satisfy our requirements, as it is based on real arithmetic, and natural discrete analogues, such as the Geometric Mechanism (Ghosh, Roughgarden, Sundarajan, STOC 2009 and SICOMP 2012), take time at least linear in |X|, which can be exponential in the bit length of the input. In this paper, we provide strict polynomial-time discrete algorithms for approximate histograms whose simultaneous accuracy (the maximum error over all bins) matches that of the Laplace Mechanism up to constant factors, while retaining the same (pure) differential privacy guarantee. One of our algorithms produces a sparse histogram as output. Its "per-bin accuracy" (the error on individual bins) is worse than that of the Laplace Mechanism by a factor of log |X|, but we prove a lower bound showing that this is necessary for any algorithm that produces a sparse histogram. A second algorithm avoids this lower bound, and matches the per-bin accuracy of the Laplace Mechanism, by producing a compact and efficiently computable representation of a dense histogram; it is based on an (n+1)-wise independent implementation of an appropriately clamped version of the Discrete Geometric Mechanism.
P-paracompact and P-metrizable spaces ☆

Abstract Let P be a directed set and X a space. A collection C of subsets of X is P-locally finite if C = ⋃ { C p : p ∈ P } where (i) if p ≤ p ′ then C p ⊆ C p ′ and (ii) each C p is locally finite. Then X is P-paracompact if every open cover has a P -locally finite open refinement. Further, X is P-metrizable if it has a ( P × N ) -locally finite base. This work provides the first detailed study of P -paracompact and P -metrizable spaces, particularly in the case when P is a K ( M ) , the set of all compact subsets of a separable metrizable space M ordered by set inclusion.
Badly approximable S-numbers and absolute Schmidt games

Abstract Let K be a number field, let S be the set of all normalized, non-conjugate Archimedean valuations of K, and let K S = ∏ v ∈ S K v be the Minkowski space associated with K. We strengthen recent results of [ESK10] and [EGL15] by showing that the set of badly approximable elements of K S is H -absolute winning for a certain family of subspaces of K S .
Harnack inequalities in infinite dimensions

Abstract We consider the Harnack inequality for harmonic functions with respect to three types of infinite-dimensional operators. For the infinite-dimensional Laplacian, we show no Harnack inequality is possible. We also show that the Harnack inequality fails for a large class of Ornstein–Uhlenbeck processes, although functions that are harmonic with respect to these processes do satisfy an a priori modulus of continuity. Many of these processes also have a coupling property. The third type of operator considered is the infinite-dimensional analog of operators in Hormanderʼs form. In this case a Harnack inequality does hold.
The rapid decay property and centroids in groups

This is a survey of methods of proving or disproving the rapid decay property in groups. We present a centroid property of group actions on metric spaces. That property is a generalized (and corrected) version of the "(**)-relative hyperbolicity" from [9] and implies the rapid decay (RD) property. We show that several properties which are known to imply RD also imply the centroid property. Thus uniform lattices in many semi-simple Lie groups, graph products of groups, Artin groups of large type and the mapping class groups have the (relative) centroid property. We also present a simple "non-amenability-like" property that follows from RD, and give an easy example of a group without RD and without any amenable subgroup with superpolynomial growth.
Challenging Fuel Cycle Modeling Assumptions: Facility and Time-Step Discretization Effects

Because of the diversity of fuel cycle simulator modeling assumptions, direct comparison and benchmarking can be difficult. In 2012 the Organisation for Economic Co-operation and Development comple...
Probabilistic and Distributed Control of a Large-Scale Swarm of Autonomous Agents

We present a distributed control algorithm simultaneously solving both the stochastic target assignment and optimal motion control for large-scale swarms to achieve complex formation shapes. Our probabilistic swarm guidance using inhomogeneous Markov chains (PSG–IMC) algorithm adopts a Eulerian density-control framework, under which the physical space is partitioned into multiple bins and the swarm's density distribution over each bin is controlled in a probabilistic fashion to efficiently handle loss or the addition of agents. We assume that the number of agents is much larger than the number of bins and that each agent knows in which bin it is located, the desired formation shape, and the objective function and motion constraints. PSG–IMC determines the bin-to-bin transition probabilities of each agent using a time IMC. These time-varying Markov matrices are computed by each agent in real time using the feedback from the current swarm distribution, which is estimated in a distributed manner. The PSG–IMC algorithm minimizes the expected cost of transitions per time instant that are required to achieve and maintain the desired formation shape, even if agents are added to or removed from the swarm. PSG–IMC scales well with a large number of agents and complex formation shapes and can also be adapted for area exploration applications. We demonstrate the effectiveness of this proposed swarm guidance algorithm by using numerical simulations and hardware experiments with multiple quadrotors.
BIKEI, INVOLUTORY BIRACKS AND UNORIENTED LINK INVARIANTS

We identify a subcategory of biracks which define counting invariants of unoriented links, which we call involutory biracks. In particular, involutory biracks of birack rank N = 1 are biquandles, which we call bikei or 双圭. We define counting invariants of unoriented classical and virtual links using finite involutory biracks, and we give an example of a non-involutory birack whose counting invariant detects the non-invertibility of a virtual knot.
A Statistical Investigation of Long Memory in Language and Music.

Representation and learning of long-range dependencies is a central challenge confronted in modern applications of machine learning to sequence data. Yet despite the prominence of this issue, the basic problem of measuring long-range dependence, either in a given data source or as represented in a trained deep model, remains largely limited to heuristic tools. We contribute a statistical framework for investigating long-range dependence in current applications of deep sequence modeling, drawing on the well-developed theory of long memory stochastic processes. This framework yields testable implications concerning the relationship between long memory in real-world data and its learned representation in a deep learning architecture, which are explored through a semiparametric framework adapted to the high-dimensional setting.
Tight Hardness Results for Maximum Weight Rectangles

Given n weighted points (positive or negative) in d dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? The best known algorithm for this problem is based on a reduction to a related problem, the Weighted Depth problem [Chan, FOCS, 2013], and runs in time O(n^d). It was conjectured [Barbay et al., CCCG, 2013] that this runtime is tight up to subpolynomial factors. We answer this conjecture affirmatively by providing a matching conditional lower bound. We also provide conditional lower bounds for the special case when points are arranged in a grid (a well studied problem known as Maximum Subarray problem) as well as for other related problems. All our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially optimal.
Characterization of the allowed patterns of signed shifts

The allowed patterns of a map are those permutations in the same relative order as the initial segments of orbits realized by the map. In this paper, we characterize and provide enumerative bounds for the allowed patterns of signed shifts, a family of maps on infinite words.
The Gauss–Bonnet formula for harmonic surfaces

We consider harmonic immersions in R of compact Riemann surfaces with finitely many punctures where the harmonic coordinate functions are given as real parts of meromorphic functions. We prove that such surfaces have finite total Gauss curvature. The contribution of each end is a multiple of 2π, determined by the maximal pole order of the meromorphic functions. This generalizes the well known Gackstatter-Jorge-Meeks formula for minimal surfaces. The situation is complicated as the ends with their induced metrics are generally not conformally equivalent to punctured disks, nor do the surfaces generally have limit tangent planes at the ends. Date: June 7, 2016. 2010 Mathematics Subject Classification. Primary 53C43; Secondary 53C45. This work was partially supported by a grant from the Simons Foundation (246039 to Matthias Weber). 1 ar X iv :1 30 9. 46 59 v2 [ m at h. D G ] 4 J un 2 01 6
Pairwise ranking: Choice of method can produce arbitrarily different rank order

Abstract We examine three methods for ranking by pairwise comparison: PerronRank (Principal Eigenvector), HodgeRank and TropicalRank. We show that the choice of method can produce arbitrarily different rank order. To be precise, for any two of the three methods, and for any pair of rankings of at least four items, there exists a comparison matrix for the items such that the rankings found by the two methods are the prescribed ones. We discuss the implications of this result in practice, study the geometry of the methods, and state some open problems.
What Factors Control Shale-Gas Production and Production-Decline Trend in Fractured Systems: A Comprehensive Analysis and Investigation

A multi-physics model for shale gas production in fractured system, that couples real gas property, nano-flow mechanism and geomechanics
Smoothing spline ANOVA for super-large samples: scalable computation via rounding parameters

In the current era of big data, researchers routinely collect and analyze data of super-large sample sizes. Data-oriented statistical methods have been developed to extract information from super-large data. Smoothing spline ANOVA (SSANOVA) is a promising approach for extracting information from noisy data; however, the heavy computational cost of SSANOVA hinders its wide application. In this paper, we propose a new algorithm for fitting SSANOVA models to super-large sample data. In this algorithm, we introduce rounding parameters to make the computation scalable. To demonstrate the benefits of the rounding parameters, we present a simulation study and a real data example using electroencephalography data. Our results reveal that (using the rounding parameters) a researcher can fit nonparametric regression models to very large samples within a few seconds using a standard laptop or tablet computer.
Minimal Reachability is Hard To Approximate

In this note, we consider the problem of choosing, which nodes of a linear dynamical system should be actuated so that the state transfer from the system's initial condition to a given final state is possible. Assuming a standard complexity hypothesis, we show that this problem cannot be efficiently solved or approximated in polynomial, or even quasi-polynomial, time.
A p-ADIC PERRON-FROBENIUS THEOREM

We prove a result for square matrices over the p-adic numbers akin to the Perron-Frobenius Theorem for square matrices over the real numbers. In particular, we show that if a square n n matrix A has all entries p-adically close to 1, then this matrix will possess a unique maximal eigenvalue 0 such that: (a) 0 is a p-adic integer, (b) 0 has an algebraic multiplicity of one, and (c) there exists an eigenvector associated to 0 with all entries p-adically close to 1. Furthermore, we show that iteration of A= 0 converges to a projection operator onto the eigenspace of 0.
A Class of Logistic Functions for Approximating State-Inclusive Koopman Operators

An outstanding challenge in nonlinear systems theory is identification or learning of a given nonlinear system's Koopman operator directly from data or models. Advances in extended dynamic mode decomposition approaches and machine learning methods have enabled data-driven discovery of Koopman operators, for both continuous and discrete-time systems. Since Koopman operators are often infinite-dimensional, they are approximated in practice using finite-dimensional systems. The fidelity and convergence of a given finite-dimensional Koopman approximation is a subject of ongoing research. In this paper we introduce a class of Koopman observable functions that confer an approximate closure property on their corresponding finite-dimensional approximations of the Koopman operator. We derive error bounds for the fidelity of this class of observable functions, as well as identify two key learning parameters which can be used to tune performance. We illustrate our approach on two classical nonlinear system models: the Van Der Pol oscillator and the bistable toggle switch.
Optimal Sensing and Data Estimation in a Large Sensor Network

An energy efficient use of large scale sensor networks necessitates activating a subset of possible sensors for estimation at a fusion center. The problem is inherently com- binatorial; to this end, a set of iterative, randomized algorithms are developed for sensor subset selection by exploiting the underlying statistics. Gibbs sampling-based methods are designed to optimize the estimation error and the mean number of activated sensors. The optimality of the proposed strategy is proven, along with guarantees on their convergence speeds. Also, another new algorithm exploiting stochastic approximation in conjunction with Gibbs sampling is derived for a constrained version of the sensor selection problem. The methodology is extended to the scenario where the fusion center has access to only a parametric form of the joint statistics, but not the true underlying distribution. Therein, expectation-maximization is effectively employed to learn the distribution. Strategies for iid time- varying data are also outlined. Numerical results show that the proposed methods converge very fast to the respective optimal solutions, and therefore can be employed for optimal sensor subset selection in practical sensor networks.
Pose estimation for non-cooperative spacecraft rendezvous using convolutional neural networks

On-board estimation of the pose of an uncooperative target spacecraft is an essential task for future on-orbit servicing and close-proximity formation flying missions. However, two issues hinder reliable on-board monocular vision based pose estimation: robustness to illumination conditions due to a lack of reliable visual features and scarcity of image datasets required for training and benchmarking. To address these two issues, this work details the design and validation of a monocular vision based pose determination architecture for spaceborne applications. The primary contribution to the state-of-the-art of this work is the introduction of a novel pose determination method based on Convolutional Neural Networks (CNN) to provide an initial guess of the pose in real-time on-board. The method involves discretizing the pose space and training the CNN with images corresponding to the resulting pose labels. Since reliable training of the CNN requires massive image datasets and computational resources, the parameters of the CNN must be determined prior to the mission with synthetic imagery. Moreover, reliable training of the CNN requires datasets that appropriately account for noise, color, and illumination characteristics expected in orbit. Therefore, the secondary contribution of this work is the introduction of an image synthesis pipeline, which is tailored to generate high fidelity images of any spacecraft 3D model. In contrast to prior techniques demonstrated for close-range pose determination of spacecraft, the proposed architecture relies on neither hand-engineered image features nor a-priori relative state information. Hence, the proposed technique is scalable to spacecraft of different structural and physical properties as well as robust to the dynamic illumination conditions of space. Through metrics measuring classification and pose accuracy, it is shown that the presented architecture has desirable robustness and scalable properties. Therefore, the proposed technique can be used to augment the current state-of-the-art monocular vision-based pose estimation techniques used in spaceborne applications.
Anatomical entrapment of the dorsal scapular and long thoracic nerves, secondary to brachial plexus piercing variation

Circumscapular pain is a frequent complaint in clinical practice. The dorsal scapular and long thoracic nerves course through the neck, where they may become entrapped between or within adjacent scalene muscles. Additionally, a high frequency of brachial plexus “piercing” variants have recently been documented, and it is unclear how they influence branching patterns distally along the brachial plexus. In the project reported here we strived to identify and quantify variations in dorsal scapular nerve and long thoracic nerve secondary to brachial plexus piercing variation. Ninety brachial plexuses from human cadavers (45 female/45 male) were evaluated to identify nerve branching patterns, specifically piercing versus non-piercing variants in the brachial plexus roots and nerves. Anatomical entrapment of the dorsal scapular nerve and long thoracic nerve was found in high frequencies (60.8% and 44.6%, respectively). Anomalous brachial plexus piercing variants were associated with higher frequencies of distal nerve branches also coursing through the scalene musculature, and there was a statistically significant correlation between brachial plexus and long thoracic nerve piercings (p = 0.027). Anatomical entrapment of nerves within scalene musculature is common and may be causative factors for idiopathic circumscapular pain, dorsalgia, and dysfunction of scapulohumeral rhythm. This study revealed a link between anatomical arrangement of the brachial plexus and occurrence of long thoracic nerve entrapment, which may lead to a series of cascading neurologic effects in which affected individuals may suffer from increased incidence of thoracic outlet syndrome and long thoracic nerve entrapment resulting in additional symptoms of interscapular pain and compromised shoulder mobility.
Gamma-ray Burst Host Galaxies as Probes of Galaxy Formation and Evolution

Host galaxies are an excellent means of probing the natal environments that generate gammaray bursts (GRBs). Surveys of long-duration GRB (LGRB) host environments and their ISM properties have produced intriguing new results with important implications for LGRB progenitor models. These host studies are also critical in evaluating t he utility of LGRBs as potential tracers of star formation and metallicity at high redshifts, partic ularly when considering the implications for properties of host galaxies above z ∼ 6. I will summarize our group’s latest research on LGRB host galaxies, and discuss the resulting impact on our understanding of these events’ progenitors, energetics, afterglow properties, and cosmological appli cations.
Through a Glass, Darkly: Three Important Conversations for Human Rights Professionals

The current moment in history is marked by a sense of anxiety about the future of human rights as a global project. In many instances, human rights pessimism has eclipsed a larger empirical picture of human rights progress. In assessing this paradox of perception, I argue that human rights professionals themselves contribute to this sense of pessimism and crisis in ways that can become counterproductive and demobilizing. Promoting a more positive and balanced human rights vision reflecting both progress and challenges will require several shifts in emphasis over the coming decade, beginning with some neglected conversations for the broader field of human rights. These conversations relate to (1) an assessment of the ways in which professional experience has shaped the messaging and worldview of human rights advocates; (2) the role of human rights critics in promoting new thinking and reform; and (3) the need for advocates to go beyond what I call the ‘legalistic referee model’ in their attempts to promote positive change.
Lower bounds for codimension-1 measure in metric manifolds

We establish Euclidean-type lower bounds for the codimen\-sion-1 Hausdorff measure of sets that separate points in doubling and linearly locally contractible metric manifolds. This gives a quantitative topological isoperimetric inequality in the setting of metric manifolds, in the sense that lower bounds for the codimension-1 measure of a set depend not on some notion of filling or volume but rather on in-radii of complementary components. As a consequence, we show that balls in a closed, connected, doubling,
Connected components of Hurwitz schemes and Malle's conjecture

Abstract Let Z ( X ) be the number of degree-n extensions of F q ( t ) with some specified Galois group and with discriminant bounded by X. The problem of computing the asymptotics for Z ( X ) can be related to a problem of counting F q -rational points on certain Hurwitz spaces. Ellenberg and Venkatesh used this idea to develop a heuristic for the asymptotic behavior of Z 0 ( X ) , the number of – geometrically connected – extensions, and showed that this agrees with the conjectures of Malle for function fields. We extend Ellenberg–Venkatesh's argument to handle the more complicated case of covers of P 1 which may not be geometrically connected, and show that the resulting heuristic suggests a natural modification to Malle's conjecture which avoids the counterexamples, due to Kluners, to the original conjecture.
Star Bodies with Completely Symmetric Sections

We say that a star body $K$ is completely symmetric if it has centroid at the origin and its symmetry group $G$ forces any ellipsoid whose symmetry group contains $G$, to be a ball. In this short note, we prove that if all central sections of a star body $L$ are completely symmetric, then $L$ has to be a ball. A special case of our result states that if all sections of $L$ are origin symmetric and 1-symmetric, then $L$ has to be a Euclidean ball. This answers a question from \cite{R2}. Our result is a consequence of a general theorem that we establish, stating that if the restrictions in almost all equators of a real function $f$ defined on the sphere, are isotropic functions, then $f$ is constant a.e. In the last section of this note, applications, improvements and related open problems are discussed and two additional open questions from \cite{R} and \cite{R2} are answered.}
Word Affect Intensities

Words often convey affect -- emotions, feelings, and attitudes. Lexicons of word-affect association have applications in automatic emotion analysis and natural language generation. However, existing lexicons indicate only coarse categories of affect association. Here, for the first time, we create an affect intensity lexicon with real-valued scores of association. We use a technique called best-worst scaling that improves annotation consistency and obtains reliable fine-grained scores. The lexicon includes terms common from both general English and terms specific to social media communications. It has close to 6,000 entries for four basic emotions. We will be adding entries for other affect dimensions shortly.