cssi/SciSciGPT-SciSciNet huggingface dataset:
Optimal Gossip Algorithms for Exact and Approximate Quantile Computations

This paper gives drastically faster gossip algorithms to compute exact and approximate quantiles.Gossip algorithms, which allow each node to contact a uniformly random other node in each round, have been intensely studied and been adopted in many applications due to their fast convergence and their robustness to failures. Kempe et al. [24] gave gossip algorithms to compute important aggregate statistics if every node is given a value. In particular, they gave a beautiful O(logn + log 1 e ) round algorithm to e-approximate the sum of all values and an O(log2 n) round algorithm to compute the exact Φ-quantile, i.e., the ?Φn? smallest value.We give an quadratically faster and in fact optimal gossip algorithm for the exact Φ-quantile problem which runs in O(logn) rounds. We furthermore show that one can achieve an exponential speedup if one allows for an e-approximation. In particular, we give an O(log logn + log 1 e ) round gossip algorithm which computes a value of rank between Φn and (Φ + e)n at every node. Our algorithms are extremely simple and very robust - they can be operated with the same running times even if every transmission fails with a, potentially different, constant probability. We also give a matching Ω(log logn + log 1 e ) lower bound which shows that our algorithm is optimal for all values of e.
Moderate Deviations in Channel Coding

We consider block codes whose rate converges to the channel capacity with increasing blocklength at a certain speed and examine the best possible decay of the probability of error. For discrete memoryless channels, we prove that a moderate deviation principle holds for all convergence rates between the large deviation and the central limit theorem regimes.
Optimization Algorithms for Faster Computational Geometry

We study two fundamental problems in computational geometry: finding the maximum inscribed ball (MaxIB) inside a bounded polyhedron defined by m hyperplanes, and the minimum enclosing ball (MinEB) of a set of n points, both in d-dimensional space. We improve the running time of iterative algorithms on MaxIB from ~O(m*d*alpha^3/epsilon^3) to ~O(m*d + m*sqrt(d)*alpha/epsilon), a speed-up up to ~O(sqrt(d)*alpha^2/epsilon^2), and MinEB from ~O(n*d/sqrt(epsilon)) to ~O(n*d + n*sqrt(d)/sqrt(epsilon)), a speed-up up to ~O(sqrt(d)). Our improvements are based on a novel saddle-point optimization framework. We propose a new algorithm L1L2SPSolver for solving a class of regularized saddle-point problems, and apply a randomized Hadamard space rotation which is a technique borrowed from compressive sensing. Interestingly, the motivation of using Hadamard rotation solely comes from our optimization view but not the original geometry problem: indeed, it is not immediately clear why MaxIB or MinEB, as a geometric problem, should be easier to solve if we rotate the space by a unitary matrix. We hope that our optimization perspective sheds lights on solving other geometric problems as well.
Scalable Computation of 2D-Minkowski Sum of Arbitrary Non-Convex Domains: Modeling Flexibility in Energy Resources

The flexibility of active ($p$) and reactive power ($q$) consumption in distributed energy resources (DERs) can be represented as a (potentially non-convex) set of points in the $p$-$q$ plane. Modeling of the aggregated flexibility in a heterogeneous ensemble of DERs as a Minkowski sum (M-sum) is computationally intractable even for moderately sized populations. In this article, we propose a scalable method of computing the M-sum of the flexibility domains of a heterogeneous ensemble of DERs, which are allowed to be non-convex, non-compact. In particular, the proposed algorithm computes a guaranteed superset of the true M-sum, with desired accuracy. The worst-case complexity of the algorithm is computed. Special cases are considered, and it is shown that under certain scenarios, it is possible to achieve a complexity that is linear with the size of the ensemble. Numerical examples are provided by computing the aggregated flexibility of different mix of DERs under varying scenarios.
Learning a Prior over Intent via Meta-Inverse Reinforcement Learning

A significant challenge for the practical application of reinforcement learning in the real world is the need to specify an oracle reward function that correctly defines a task. Inverse reinforcement learning (IRL) seeks to avoid this challenge by instead inferring a reward function from expert behavior. While appealing, it can be impractically expensive to collect datasets of demonstrations that cover the variation common in the real world (e.g. opening any type of door). Thus in practice, IRL must commonly be performed with only a limited set of demonstrations where it can be exceedingly difficult to unambiguously recover a reward function. In this work, we exploit the insight that demonstrations from other tasks can be used to constrain the set of possible reward functions by learning a "prior" that is specifically optimized for the ability to infer expressive reward functions from limited numbers of demonstrations. We demonstrate that our method can efficiently recover rewards from images for novel tasks and provide intuition as to how our approach is analogous to learning a prior.
Parallel Pairwise Correlation Computation on Intel Xeon Phi Clusters

Co-expression network is a critical technique for the identification of inter-gene interactions, which usually relies on all-pairs correlation (or similar measure) computation between gene expression profiles across multiple samples. Pearson's correlation coefficient (PCC) is one widely used technique for gene co-expression network construction. However, all-pairs PCC computation is computationally demanding for large numbers of gene expression profiles, thus motivating our acceleration of its execution using high-performance computing. In this paper, we present LightPCC, the first parallel and distributed all-pairs PCC computation on Intel Xeon Phi (Phi) clusters. It achieves high speed by exploring the SIMD-instruction-level and thread-level parallelism within Phis as well as accelerator-level parallelism among multiple Phis. To facilitate balanced workload distribution, we have proposed a general framework for symmetric all-pairs computation by building bijective functions between job identifier and coordinate space for the first time. We have evaluated LightPCC and compared it to two CPU-based counterparts: a sequential C++ implementation in ALGLIB and an implementation based on a parallel general matrix-matrix multiplication routine in Intel Math Kernel Library (MKL) (all use double precision), using a set of gene expression datasets. Performance evaluation revealed that with one 5110P Phi and 16 Phis, LightPCC runs up to 20.6× and 218.2× faster than ALGLIB, and up to 6.8× and 71.4× faster than single-threaded MKL, respectively. In addition, LightPCC demonstrated good parallel scalability in terms of number of Phis. Source code of LightPCC is publicly available at http://lightpcc.sourceforge.net.
Compactifications of Manifolds with Boundary

This paper is concerned with compactifications of high-dimensional manifolds. Siebenmann’s iconic 1965 dissertation [L. C. Siebenmann, The obstruction to finding a boundary for an open manifold of ...
Shock-driven Accretion in Circumplanetary Disks: Observables and Satellite Formation

Circumplanetary disks (CPDs) control the growth of planets, supply material for satellites to form, and provide observational signatures of young forming planets. We have carried out two dimensional hydrodynamical simulations with radiative cooling to study CPDs, and suggested a new mechanism to drive the disk accretion. Two spiral shocks are present in CPDs, excited by the central star. We find that spiral shocks can at least contribute to, if not dominate the angular momentum transport and energy dissipation in CPDs. Meanwhile, dissipation and heating by spiral shocks have a positive feedback on shock-driven accretion itself. As the disk is heated up by spiral shocks, the shocks become more open, leading to more efficient angular momentum transport. This shock driven accretion is, on the other hand, unsteady on a timescale of months/years due to production and destruction of vortices in disks. After being averaged over time, a quasi-steady accretion is reached from the planet's Hill radius all the way to the planet surface, and the disk $\alpha$-coefficient characterizing angular momentum transport due to spiral shocks is $\sim$0.001-0.02. The disk surface density ranges from 10 to 1000 g cm$^{-2}$ in our simulations, which is at least 3 orders of magnitude smaller than the "minimum mass sub-nebula" model used to study satellite formation; instead it is more consistent with the "gas-starved" satellite formation model. Finally, we calculate the millimeter flux emitted by CPDs at ALMA and EVLA wavelength bands and predict the flux for several recently discovered CPD candidates, which suggests that ALMA is capable of discovering these accreting CPDs.
Direct Optimization of F-Measure for Retrieval-Based Personal Question Answering

Recent advances in spoken language technologies and the introduction of many customer facing products, have given rise to a wide customer reliance on smart personal assistants for many of their daily tasks. In this paper, we present a system to reduce users’ cognitive load by extending personal assistants with long-term personal memory where users can store and retrieve by voice, arbitrary pieces of information. The problem is framed as a neural retrieval based question answering system where answers are selected from previously stored user memories. We propose to directly optimize the end-to-end retrieval performance, measured by the F1-score, using reinforcement learning, leading to better performance on our experimental test set(s).
Loss-induced Enhanced Transmission in Anisotropic Density-near-zero Acoustic Metamaterials

Anisotropic density-near-zero (ADNZ) acoustic metamaterials are investigated theoretically and numerically in this paper and are shown to exhibit extraordinary transmission enhancement when material loss is induced. The enhanced transmission is due to the enhanced propagating and evanescent wave modes inside the ADNZ medium thanks to the interplay of near-zero density, material loss, and high wave impedance matching in the propagation direction. The equi-frequency contour (EFC) is used to reveal whether the propagating wave mode is allowed in ADNZ metamaterials. Numerical simulations based on plate-type acoustic metamaterials with different material losses were performed to demonstrate collimation and subwavelength imaging enabled by the induced loss in ADNZ media. This work provides a different way for manipulating acoustic waves.
Scarcity of periodic orbits in outer billiards

We give a simple proof of the result of Tumanov and Zharnitsky (Int Math Res Not, 2006) that the set of period 4 orbits in planar outer billiard with piecewise smooth convex boundary has empty interior, provided that no four corners of the boundary form a parallelogram. We also obtain results on period 5 and 6 orbits.
What Do Different Evaluation Metrics Tell Us About Saliency Models

How best to evaluate a saliency model's ability to predict where humans look in images is an open research question. The choice of evaluation metric depends on how saliency is defined and how the ground truth is represented. Metrics differ in how they rank saliency models, and this results from how false positives and false negatives are treated, whether viewing biases are accounted for, whether spatial deviations are factored in, and how the saliency maps are pre-processed. In this paper, we provide an analysis of 8 different evaluation metrics and their properties. With the help of systematic experiments and visualizations of metric computations, we add interpretability to saliency scores and more transparency to the evaluation of saliency models. Building off the differences in metric properties and behaviors, we make recommendations for metric selections under specific assumptions and for specific applications.
Evaluating Visual Conversational Agents via Cooperative Human-AI Games

As AI continues to advance, human-AI teams are inevitable. However, progress in AI is routinely measured in isolation, without a human in the loop. It is crucial to benchmark progress in AI, not just in isolation, but also in terms of how it translates to helping humans perform certain tasks, i.e., the performance of human-AI teams. In this work, we design a cooperative game — GuessWhich — to measure human-AI team performance in the specific context of the AI being a visual conversational agent. GuessWhich involves live interaction between the human and the AI. The AI, which we call ALICE, is provided an image which is unseen by the human. Following a brief description of the image, the human questions ALICE about this secret image to identify it from a fixed pool of images. We measure performance of the human-ALICE team by the number of guesses it takes the human to correctly identify the secret image after a fixed number of dialog rounds with ALICE. We compare performance of the human-ALICE teams for two versions of ALICE. Our human studies suggest a counterintuitive trend – that while AI literature shows that one version outperforms the other when paired with an AI questioner bot, we find that this improvement in AI-AI performance does not translate to improved human-AI performance. This suggests a mismatch between benchmarking of AI in isolation and in the context of human-AI teams.
Galois automorphisms on Harish-Chandra series and Navarro’s self-normalizing Sylow 2-subgroup conjecture

G. Navarro has conjectured a necessary and sufficient condition for a finite group $G$ to have a self-normalizing Sylow 2-subgroup, which is given in terms of the ordinary irreducible characters of $G$. In a previous article, the author has reduced the proof of this conjecture to showing that certain related statements hold for simple groups. In this article, we describe the action of Galois automorphisms on the Howlett-Lehrer parametrization of Harish-Chandra induced characters. We use this to complete the proof of the conjecture by showing that the remaining simple groups satisfy the required conditions.
High-Dimensional Longitudinal Classification with the Multinomial Fused Lasso

We study regularized estimation in high-dimensional longitudinal classification problems, using the lasso and fused lasso regularizers. The constructed coefficient estimates are piecewise constant across the time dimension in the longitudinal problem, with adaptively selected change points (break points). We present an efficient algorithm for computing such estimates, based on proximal gradient descent. We apply our proposed technique to a longitudinal data set on Alzheimer's disease from the Cardiovascular Health Study Cognition Study. Using data analysis and a simulation study, we motivate and demonstrate several practical considerations such as the selection of tuning parameters and the assessment of model stability. While race, gender, vascular and heart disease, lack of caregivers, and deterioration of learning and memory are all important predictors of dementia, we also find that these risk factors become more relevant in the later stages of life.
Chromatic Symmetric Functions of Hypertrees

The chromatic symmetric function $X_H$ of a hypergraph $H$ is the sum of all monomials corresponding to proper colorings of $H$. When $H$ is an ordinary graph, it is known that $X_H$ is positive in the fundamental quasisymmetric functions $F_S$, but this is not the case for general hypergraphs. We exhibit a class of hypergraphs $H$ — hypertrees with prime-sized edges — for which $X_H$ is $F$-positive, and give an explicit combinatorial interpretation for the $F$-coefficients of $X_H$.
Neuroevolution-based Inverse Reinforcement Learning

The problem of Learning from Demonstration is targeted at learning to perform tasks based on observed examples. One approach to Learning from Demonstration is Inverse Reinforcement Learning, in which actions are observed to infer rewards. This work combines a feature-based state evaluation approach to Inverse Reinforcement Learning with neuroevolution, a paradigm for modifying neural networks based on their performance on a given task. Neural networks are used to learn from a demonstrated expert policy and are evolved to generate a policy similar to the demonstration. The algorithm is discussed and evaluated against competitive feature-based Inverse Reinforcement Learning approaches. At the cost of execution time, neural networks allow for non-linear combinations of features in state evaluations. This results in better correspondence to observed examples as opposed to using linear combinations. This work also extends existing work on Bayesian Non-Parametric Feature construction for Inverse Reinforcement Learning by using non-linear combinations of intermediate data to improve performance. The algorithm is observed to be specifically suitable for a linearly solvable non-deterministic Markov Decision Processes in which multiple rewards are sparsely scattered in state space. This translates to real-world control problems such as those in robotics and automation (e.g. the robust output tracking problem or controlling an n-joint arm), where the underlying equations can be made linear. A conclusive performance hierarchy between evaluated algorithms is presented.
On the odd primary homology of free algebras over the spectral lie operad

The derivatives of the identity functor on spaces in Goodwillie calculus form an operad in spectra. Antolin-Camarena computed the mod 2 homology of free algebras over this operad for 1-connected spectra. In this present paper we carry out similar computations for mod p homology for odd primes p, also for non-connected spectra.
Scaling-Up Split-Merge MCMC with Locality Sensitive Sampling (LSS)

Split-Merge MCMC (Monte Carlo Markov Chain) is one of the essential and popular variants of MCMC for problems when an MCMC state consists of an unknown number of components. It is well known that state-of-the-art methods for split-merge MCMC do not scale well. Strategies for rapid mixing requires smart and informative proposals to reduce the rejection rate. However, all known smart proposals involve expensive operations to suggest informative transitions. As a result, the cost of each iteration is prohibitive for massive scale datasets. It is further known that uninformative but computationally efficient proposals, such as random split-merge, leads to extremely slow convergence. This tradeoff between mixing time and per update cost seems hard to get around.We leverage some unique properties of weighted MinHash, which is a popular LSH, to design a novel class of split-merge proposals which are significantly more informative than random sampling but at the same time efficient to compute. Overall, we obtain a superior tradeoff between convergence and per update cost. As a direct consequence, our proposals are around 6X faster than the state-of-the-art sampling methods on two large real datasets KDDCUP and PubMed with several millions of entities and thousands of clusters.
Repeated boundary slopes for 2-bridge knots

We investigate the question of when distinct branched surfaces in the complement of a 2-bridge knot support essential surfaces with identical boundary slopes. We determine all instances in which this occurs and identify an infinite family of knots for which no boundary slopes are repeated.
Duality of graphical models and tensor networks

In this article we show the duality between tensor networks and undirected graphical models with discrete variables. We study tensor networks on hypergraphs, which we call tensor hypernetworks. We show that the tensor hypernetwork on a hypergraph exactly corresponds to the graphical model given by the dual hypergraph. We translate various notions under duality. For example, marginalization in a graphical model is dual to contraction in the tensor network. Algorithms also translate under duality. We show that belief propagation corresponds to a known algorithm for tensor network contraction. This article is a reminder that the research areas of graphical models and tensor networks can benefit from interaction.
Exponential Weights on the Hypercube in Polynomial Time

We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of $n$ objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the total cost incurred over all iterations and the cost of the best fixed subset in hindsight. We consider Full Information and Bandit feedback for this problem. This problem is equivalent to OLO on the $\{0,1\}^n$ hypercube. The Exp2 algorithm and its bandit variant are commonly used strategies for this problem. It was previously unknown if it is possible to run Exp2 on the hypercube in polynomial time. In this paper, we present a polynomial time algorithm called PolyExp for OLO on the hypercube. We show that our algorithm is equivalent Exp2 on $\{0,1\}^n$, Online Mirror Descent(OMD), Follow The Regularized Leader(FTRL) and Follow The Perturbed Leader(FTPL) algorithms. We show PolyExp achieves expected regret bound that is a factor of $\sqrt{n}$ better than Exp2 in the full information setting under $L_\infty$ adversarial losses. Because of the equivalence of these algorithms, this implies an improvement on Exp2's regret bound in full information. We also show matching regret lower bounds. Finally, we show how to use PolyExp on the $\{-1,+1\}^n$ hypercube, solving an open problem in Bubeck et al (COLT 2012).
Viewpoint selection for grasp detection

In grasp detection, the robot estimates the position and orientation of potential grasp configurations directly from sensor data. This paper explores the relationship between viewpoint and grasp detection performance. Specifically, we consider the scenario where the approximate position and orientation of a desired grasp is known in advance and we want to select a viewpoint that will enable a grasp detection algorithm to localize it more precisely and with higher confidence. Our main findings are that the right viewpoint can dramatically increase the number of detected grasps and the classification accuracy of the top-n detections. We use this insight to create a viewpoint selection algorithm and compare it against a random viewpoint selection strategy and a strategy that views the desired grasp head-on. We find that the head-on strategy and our proposed viewpoint selection strategy can improve grasp success rates on a real robot by 8% and 4%, respectively. Moreover, we find that the combination of the two methods can improve grasp success rates by as much as 12%.
On interpreting Patterson--Sullivan measures of geometrically finite groups as Hausdorff and packing measures

We provide a new proof of a theorem whose proof was sketched by Sullivan ('82), namely that if the Poincar\'e exponent of a geometrically finite Kleinian group $G$ is strictly between its minimal and maximal cusp ranks, then the Patterson--Sullivan measure of $G$ is not proportional to the Hausdorff or packing measure of any gauge function. This disproves a conjecture of Stratmann ('97, '06).
Generative Adversarial Source Separation

Generative source separation methods such as non-negative matrix factorization (NMF) or auto-encoders, rely on the assumption of an output probability density. Generative Adversarial Networks (GANs) can learn data distributions without needing a parametric assumption on the output density. We show on a speech source separation experiment that, a multilayer perceptron trained with a Wasserstein-GAN formulation outperforms NMF, auto-encoders trained with maximum likelihood, and variational auto-encoders in terms of source to distortion ratio.
Robust sparse fourier transform based on the fourier projection-slice theorem

We have recently proposed a sparse Fourier transform based on the Fourier projection-slice theorem (FPS-SFT), which is an efficient implementation of the discrete Fourier transform for multidimensional signals that are sparse in the frequency domain. For a K-sparse signal, FPS-SFT achieves sample complexity of O(K) and computational complexity of O(K log K). While FPS-SFT considers the ideal scenario, i.e., exactly sparse data that contain on-grid frequencies, in this paper, we propose a robust FPS-SFT (RFPS-SFT), which applies to noisy signals that contain off-grid frequencies; such signals arise in radar applications. RFPS-SFT employs a windowing step and a voting-based frequency decoding step; the former reduces the frequency leakage of off-grid frequencies below the noise level, thus preserving the sparsity of the signal, while the latter significantly lowers the frequency localization error stemming from the noise. The performance of the proposed method is demonstrated both theoretically and numerically.
Are Efficient Deep Representations Learnable

Many theories of deep learning have shown that a deep network can require dramatically fewer resources to represent a given function compared to a shallow network. But a question remains: can these efficient representations be learned using current deep learning techniques? In this work, we test whether standard deep learning methods can in fact find the efficient representations posited by several theories of deep representation. Specifically, we train deep neural networks to learn two simple functions with known efficient solutions: the parity function and the fast Fourier transform. We find that using gradient-based optimization, a deep network does not learn the parity function, unless initialized very close to a hand-coded exact solution. We also find that a deep linear neural network does not learn the fast Fourier transform, even in the best-case scenario of infinite training data, unless the weights are initialized very close to the exact hand-coded solution. Our results suggest that not every element of the class of compositional functions can be learned efficiently by a deep network, and further restrictions are necessary to understand what functions are both efficiently representable and learnable.
A note on renormalized volume functionals

Abstract New properties are derived of renormalized volume functionals, which arise as coefficients in the asymptotic expansion of the volume of an asymptotically hyperbolic Einstein (AHE) manifold. A formula is given for the renormalized volume of an even-dimensional AHE manifold in terms of an arbitrary totally geodesic compactification. The second variation of renormalized volume functionals under conformal change is identified, and is used to show that Einstein metrics of nonzero scalar curvature are local extrema.
Multi-GPU Graph Analytics

We present a single-node, multi-GPU programmable graph processing library that allows programmers to easily extend single-GPU graph algorithms to achieve scalable performance on large graphs with billions of edges. Directly using the single-GPU implementations, our design only requires programmers to specify a few algorithm-dependent concerns, hiding most multi-GPU related implementation details. We analyze the theoretical and practical limits to scalability in the context of varying graph primitives and datasets. We describe several optimizations, such as direction optimizing traversal, and a just-enough memory allocation scheme, for better performance and smaller memory consumption. Compared to previous work, we achieve best-of-class performance across operations and datasets, including excellent strong and weak scalability on most primitives as we increase the number of GPUs in the system
Follower, predecessor, and extender entropies

Using the follower/predecessor/extender set sequences defined by the first author, we define quantities which we call the follower/predecessor/extender entropies, which can be associated to any shift space. We analyze the behavior of these quantities under conjugacies and factor maps, most notably showing that extender entropy is a conjugacy invariant and that having follower entropy zero is a conjugacy invariant. We give some applications, including examples of shift spaces with equal entropy which can be distinguished by extender entropy, and examples of shift spaces which can be shown to not be isomorphic to their inverse by using follower/predecessor entropy.
Multidimensional counting grids: Inferring word order from disordered bags of words

Models of bags of words typically assume topic mixing so that the words in a single bag come from a limited number of topics. We show here that many sets of bag of words exhibit a very different pattern of variation than the patterns that are efficiently captured by topic mixing. In many cases, from one bag of words to the next, the words disappear and new ones appear as if the theme slowly and smoothly shifted across documents (providing that the documents are somehow ordered). Examples of latent structure that describe such ordering are easily imagined. For example, the advancement of the date of the news stories is reflected in a smooth change over the theme of the day as certain evolving news stories fall out of favor and new events create new stories. Overlaps among the stories of consecutive days can be modeled by using windows over linearly arranged tight distributions over words. We show here that such strategy can be extended to multiple dimensions and cases where the ordering of data is not readily obvious. We demonstrate that this way of modeling covariation in word occurrences outperforms standard topic models in classification and prediction tasks in applications in biology, text modeling and computer vision.
The representation of integers by positive ternary quadratic polynomials

An integral quadratic polynomial is called regular if it represents every integer that is represented by the polynomial itself over the reals and over the p-adic integers for every prime p. It is called complete if it is of the form Q(x+v), where Q is an integral quadratic form in the variables x=(x1,…,xn) and v is a vector in Qn. Its conductor is defined to be the smallest positive integer c such that cv∈Zn. We prove that for a fixed positive integer c, there are only finitely many equivalence classes of positive primitive ternary regular complete quadratic polynomials with conductor c. This generalizes the analogous finiteness results for positive definite regular ternary quadratic forms by Watson [18,19] and for ternary triangular forms by Chan and Oh [8].
Rational vertex operator algebras are finitely generated

Abstract It is proved that any vertex operator algebra for which the image of the Virasoro element in Zhu's algebra is algebraic over complex numbers is finitely generated. In particular, any vertex operator algebra with a finite-dimensional Zhu's algebra is finitely generated. As a result, any rational vertex operator algebra is finitely generated.
Numerically safe Gaussian elimination with no pivoting

Abstract Gaussian elimination with no pivoting and block Gaussian elimination are attractive alternatives to the customary but communication intensive Gaussian elimination with partial pivoting 1 provided that the computations proceed safely and numerically safely , that is, run into neither division by 0 nor numerical problems. Empirically, safety and numerical safety of GENP have been consistently observed in a number of papers where an input matrix was pre-processed with various structured multipliers chosen ad hoc. Our present paper provides missing formal support for this empirical observation and explains why it was elusive so far. Namely we prove that GENP is numerically unsafe for a specific class of input matrices in spite of its pre-processing with some well-known and well-tested structured multipliers, but we also prove that GENP and BGE are safe and numerically safe for the average input matrix pre-processed with any nonsingular and well-conditioned multiplier. This should embolden search for sparse and structured multipliers, and we list and test some new classes of them. We also seek randomized pre-processing that universally (that is, for all input matrices) supports (i) safe GENP and BGE with probability 1 and/or (ii) numerically safe GENP and BGE with a probability close to 1. We achieve goal (i) with a Gaussian structured multiplier and goal (ii) with a Gaussian unstructured multiplier and alternatively with Gaussian structured augmentation. We consistently confirm all these formal results with our tests of GENP for benchmark inputs. We have extended our approach to other fundamental matrix computations and keep working on further extensions.
General Bounds on Satisfiability Thresholds for Random CSPs via Fourier Analysis.

Random constraint satisfaction problems (CSPs) have been widely studied both in AI and complexity theory. Empirically and theoretically, many random CSPs have been shown to exhibit a phase transition. As the ratio of constraints to variables passes certain thresholds, they transition from being almost certainly satisfiable to unsatisfiable. The exact location of this threshold has been thoroughly investigated, but only for certain common classes of constraints. In this paper, we present new bounds for the location of these thresholds in boolean CSPs. Our main contribution is that our bounds are fully general, and apply to any fixed constraint function that could be used to generate an ensemble of random CSPs. These bounds rely on a novel Fourier analysis and can be easily computed from the Fourier spectrum of a constraint function. Our bounds are within a constant factor of the exact threshold location for many well-studied random CSPs. We demonstrate that our bounds can be easily instantiated to obtain thresholds for many constraint functions that had not been previously studied, and evaluate them experimentally.
CR-GAN: Learning Complete Representations for Multi-view Generation

Generating multi-view images from a single-view input is an essential yet challenging problem. It has broad applications in vision, graphics, and robotics. Our study indicates that the widely-used generative adversarial network (GAN) may learn "incomplete" representations due to the single-pathway framework: an encoder-decoder network followed by a discriminator network. We propose CR-GAN to address this problem. In addition to the single reconstruction path, we introduce a generation sideway to maintain the completeness of the learned embedding space. The two learning pathways collaborate and compete in a parameter-sharing manner, yielding considerably improved generalization ability to "unseen" dataset. More importantly, the two-pathway framework makes it possible to combine both labeled and unlabeled data for self-supervised learning, which further enriches the embedding space for realistic generations. The experimental results prove that CR-GAN significantly outperforms state-of-the-art methods, especially when generating from "unseen" inputs in wild conditions.
Implementing Probabilistic Reasoning

Abstract General problems in analyzing information in a probabilistic database are considered. The practical difficulties (and occasional advantages) of storing uncertain data, of using it in conventional forward- or backward-chaining inference engines, and of working with a probabilistic version of resolution are discussed. The background for this paper is the incorporation of uncertain reasoning facilities in MRS, a general-purpose expert system building tool.
Recovery of sparsest signals via $\ell^q$-minimization

In this paper, it is proved that every s-sparse vector x∈Rn can be exactly recovered from the measurement vector z=Ax∈Rm via some lq-minimization with 0<q⩽1, as soon as each s-sparse vector x∈Rn is uniquely determined by the measurement z. Moreover it is shown that the exponent q in the lq-minimization can be so chosen to be about 0.6796×(1−δ2s(A)), where δ2s(A) is the restricted isometry constant of order 2s for the measurement matrix A.
Three-dimensional counter-examples to the Nash problem

The Nash problem asks about the existence of a correspondence between families of arcs through singularities of complex varieties and certain types of divisorial valuations. It has been positively settled in dimension 2 by Fernandez de Bobadilla and Pe Pereira, and it was shown to have a negative answer in all dimensions by Ishii and Kollar. In this note we discuss examples which show that the problem has a negative answer in dimension 3 as well. These examples also bring to light the different nature of the problem depending on whether it is formulated in the algebraic setting or in the analytic setting.
Sensor selection and power allocation via maximizing Bayesian fisher information for distributed vector estimation

In this paper we study the problem of distributed estimation of a Gaussian vector with linear observation model in a wireless sensor network (WSN) consisting of K sensors that transmit their modulated quantized observations over orthogonal erroneous wireless channels (subject to fading and noise) to a fusion center, which estimates the unknown vector. Due to limited network transmit power, only a subset of sensors can be active at each task period. Here, we formulate the problem of sensor selection and transmit power allocation that maximizes the trace of Bayesian Fisher Information Matrix (FIM) under network transmit power constraint, and propose three algorithms to solve it. Simulation results demonstarte the superiority of these algorithms compared to the algorithm that uniformly allocates power among all sensors.
An efficient model-free estimation of multiclass conditional probability

Abstract Conventional multiclass conditional probability estimation methods, such as Fisher's discriminate analysis and logistic regression, often require restrictive distributional model assumption. In this paper, a model-free estimation method is proposed to estimate multiclass conditional probability through a series of conditional quantile regression functions. Specifically, the conditional class probability is formulated as a difference of corresponding cumulative distribution functions, where the cumulative distribution functions can be converted from the estimated conditional quantile regression functions. The proposed estimation method is also efficient as its computation cost does not increase exponentially with the number of classes. The theoretical and numerical studies demonstrate that the proposed estimation method is highly competitive against the existing competitors, especially when the number of classes is relatively large.
General Tensor Spectral Co-clustering for Higher-Order Data

Spectral clustering and co-clustering are well-known techniques in data analysis, and recent work has extended spectral clustering to square, symmetric tensors and hypermatrices derived from a network. We develop a new tensor spectral co-clustering method that simultaneously clusters the rows, columns, and slices of a nonnegative three-mode tensor and generalizes to tensors with any number of modes. The algorithm is based on a new random walk model which we call the super-spacey random surfer. We show that our method out-performs state-of-the-art co-clustering methods on several synthetic datasets with ground truth clusters and then use the algorithm to analyze several real-world datasets.
Nonlinear traveling waves for the skeleton of the Madden-Julian oscillation

The Madden{Julian Oscillation (MJO) is the dominant component of intraseasonal (30{90 days) variability in the tropical atmosphere. Here, traveling wave solutions are presented for the MJO skeleton model of Majda and Stechmann. The model is a system of nonlinear partial dierential equations that describe the evolution of the tropical atmosphere on planetary (10,000{ 40,000 km) spatial scales. The nonlinear traveling waves come in four types, corresponding to the four types of linear wave solutions, one of which has the properties of the MJO. In the MJO traveling wave, the convective activity has a pulse-like shape, with a narrow region of enhanced convection and a wide region of suppressed convection. Furthermore, an amplitude-dependent dispersion relation is derived, and it shows that the nonlinear MJO has a lower frequency and slower propagation speed than the linear MJO. By taking the small-amplitude limit, an analytic formula is also derived for the dispersion relation of linear waves. To derive all of these results, a key aspect is the model's conservation of energy, which holds even in the presence of forcing. In the limit of weak forcing, it is shown that the nonlinear traveling waves have a simple sech-squared waveform.
Two-Sided Eulerian Numbers via Balls in Boxes

The Eulerian numbers count permutations according to the number of descents. The two-sided Eulerian numbers count permutations according to number of descents and the number of descents in the inve...
Bipartite Correlation Clustering: Maximizing Agreements

In Bipartite Correlation Clustering (BCC) we are given a complete bipartite graph $G$ with `+' and `-' edges, and we seek a vertex clustering that maximizes the number of agreements: the number of all `+' edges within clusters plus all `-' edges cut across clusters. BCC is known to be NP-hard. We present a novel approximation algorithm for $k$-BCC, a variant of BCC with an upper bound $k$ on the number of clusters. Our algorithm outputs a $k$-clustering that provably achieves a number of agreements within a multiplicative ${(1-\delta)}$-factor from the optimal, for any desired accuracy $\delta$. It relies on solving a combinatorially constrained bilinear maximization on the bi-adjacency matrix of $G$. It runs in time exponential in $k$ and $\delta^{-1}$, but linear in the size of the input. Further, we show that, in the (unconstrained) BCC setting, an ${(1-\delta)}$-approximation can be achieved by $O(\delta^{-1})$ clusters regardless of the size of the graph. In turn, our $k$-BCC algorithm implies an Efficient PTAS for the BCC objective of maximizing agreements.
Heat Engines running upon a Non-Ideal Fluid Model with Higher Efficiencies than upon the Ideal Gas Model

We consider both Otto and Diesel heat engine cycles running upon the working substances modeled by the van der Waals fluid as a simple non-ideal gas model. We extensively perform the efficiency study in these model engines. Then we find that this “real” engine model can go beyond its ideal-gas counterpart in efficiency, whereas as well-known, the maximum Carnot efficiency is the same for both ideal and non-ideal gas engines. In fact, the higher the density of non-ideality is, the higher efficiency tends to be found, especially in the low-temperature regime, but with more shrinkage in the range of physically allowed compression ratio determined by the Carnot upper bound, namely, the Second Law of thermodynamics. Our findings imply that in addition to the engine architectures and bath temperatures, the properties of working substances should also be taken into consideration in the performance study of heat engines, the theoretical model aspects of which have not sufficiently been discussed so far. It is straightforward that our methodology may also apply for other non-ideal fluid models.
Approximate Kernel-Based Conditional Independence Tests for Fast Non-Parametric Causal Discovery

Constraint-based causal discovery (CCD) algorithms require fast and accurate conditional independence (CI) testing. The Kernel Conditional Independence Test (KCIT) is currently one of the most popular CI tests in the non-parametric setting, but many investigators cannot use KCIT with large datasets because the test scales at least quadratically with sample size. We therefore devise two relaxations called the Randomized Conditional Independence Test (RCIT) and the Randomized conditional Correlation Test (RCoT) which both approximate KCIT by utilizing random Fourier features. In practice, both of the proposed tests scale linearly with sample size and return accurate p-values much faster than KCIT in the large sample size context. CCD algorithms run with RCIT or RCoT also return graphs at least as accurate as the same algorithms run with KCIT but with large reductions in run time.
Checking validity of monotone domain mean estimators

AbstractENTHIS LINK GOES TO A ENGLISH SECTIONFRTHIS LINK GOES TO A FRENCH SECTION Estimates of population characteristics such as domain means are often expected to follow monotonicity assumptions. Recently, a method to adaptively pool neighbouring domains was proposed, which ensures that the resulting domain mean estimates follow monotone constraints. The method leads to asymptotically valid estimation and inference, and can lead to substantial improvements in efficiency, in comparison with unconstrained domain estimators. However, assuming incorrect shape constraints may lead to biased estimators. Here, we develop the Cone Information Criterion for Survey Data as a diagnostic method to measure monotonicity departures on population domain means. We show that the criterion leads to a consistent methodology that makes an asymptotically correct decision choosing between unconstrained and constrained domain mean estimators. The Canadian Journal of Statistics 47: 315–331; 2019 © 2019 Statistical Society of Canada
An Energy Stable Approach for Discretizing Hyperbolic Equations with Nonconforming Discontinuous Galerkin Methods

When nonconforming discontinuous Galerkin methods are implemented for hyperbolic equations using quadrature, exponential energy growth can result even when the underlying scheme with exact integration does not support such growth. Using linear elasticity as a model problem, we propose a skew-symmetric formulation that has the same energy stability properties for both exact and inexact quadrature-based integration. These stability properties are maintained even when the material properties are variable and discontinuous, and the elements are non-affine (e.g., curved). Additionally, we show how the nonconforming scheme can be made conservative and constant preserving with variable material properties and curved elements. The analytic stability, conservation, and constant preserving results are confirmed through numerical experiments demonstrating the stability as well as the accuracy of the method.
Power allocation in team jamming games in wireless ad hoc networks

In this work, we study the problem of power allocation in teams. Each team consists of two agents who try to split their available power between the tasks of communication and jamming the nodes of the other team. The agents have constraints on their total energy and instantaneous power usage. The cost function is the difference between the rates of erroneously transmitted bits of each team. We model the problem as a zero-sum differential game between the two teams and use Isaacs' approach to obtain the necessary conditions for the optimal trajectories. This leads to a continuous-kernel power allocation game among the players. Based on the communications model, we present sufficient conditions on the physical parameters of the agents for the existence of a pure strategy saddle-point equilibrium (PSSPE). Finally, we present simulation results for the case when the agents are holonomic.
A partial entropic lattice Boltzmann MHD simulation of the Orszag-Tang vortex

Karlin has introduced an analytically determined entropic lattice Boltzmann (LB) algorithm for Navier-Stokes turbulence. Here, this is partially extended to an LB model of magnetohydrodynamics, on ...