cssi/SciSciGPT-SciSciNet huggingface dataset:
Approximating the partition function by deleting and then correcting for model edges

We propose an approach for approximating the partition function which is based on two steps: (1) computing the partition function of a simplified model which is obtained by deleting model edges, and (2) rectifying the result by applying an edge-by-edge correction. The approach leads to an intuitive framework in which one can trade-off the quality of an approximation with the complexity of computing it. It also includes the Bethe free energy approximation as a degenerate case. We develop the approach theoretically in this paper and provide a number of empirical results that reveal its practical utility.
In2I: Unsupervised Multi-Image-to-Image Translation Using Generative Adversarial Networks

In unsupervised image-to-image translation, the goal is to learn the mapping between an input image and an output image using a set of unpaired training images. In this paper, we propose an extension of the unsupervised image-to-image translation problem to multiple input setting. Given a set of paired images from multiple modalities, a transformation is learned to translate the input into a specified domain. For this purpose, we introduce a Generative Adversarial Network (GAN) based framework along with a multi-modal generator structure and a new loss term, latent consistency loss. Through various experiments we show that leveraging multiple inputs generally improves the visual quality of the translated images. Moreover, we show that the proposed method outperforms current state-of-the-art unsupervised image-to-image translation methods.
Allocating indivisible items in categorized domains

We initiate a research agenda of mechanism design for categorized domain allocation problems (CDAPs), where indivisible items from multiple categories are allocated to agents without monetary transfer and each agent gets at least one item per category. We focus on basic CDAPs, where each agent gets exactly one item per category. We first characterize serial dictatorships by a minimal set of three axiomatic properties: strategy-proofness, non-bossiness, and category-wise neutrality. Then, we propose a natural extension of serial dictatorships called categorial sequential allocation mechanisms (CSAMs), which allocate the items in multiple rounds: in each round, the designated agent chooses an item from a designated category. We fully characterize the worst-case rank efficiency of CSAMs for optimistic and pessimistic agents.
Zero-truncated Poisson tensor factorization for massive binary tensors

We present a scalable Bayesian model for low-rank factorization of massive tensors with binary observations. The proposed model has the following key properties: (1) in contrast to the models based on the logistic or probit likelihood, using a zero-truncated Poisson likelihood for binary data allows our model to scale up in the number of ones in the tensor, which is especially appealing for massive but sparse binary tensors; (2) side-information in form of binary pairwise relationships (e.g., an adjacency network) between objects in any tensor mode can also be leveraged, which can be especially useful in "cold-start" settings; and (3) the model admits simple Bayesian inference via batch, as well as online MCMC; the latter allows scaling up even for dense binary data (i.e., when the number of ones in the tensor/network is also massive). In addition, non-negative factor matrices in our model provide easy interpretability, and the tensor rank can be inferred from the data. We evaluate our model on several large-scale real-world binary tensors, achieving excellent computational scalability, and also demonstrate its usefulness in leveraging side-information provided in form of mode-network(s).
Error analysis of a fully discrete Morley finite element approximation for the Cahn-Hilliard equation

This paper proposes and analyzes the Morley element method for the Cahn–Hilliard equation. It is a fourth order nonlinear singular perturbation equation arises from the binary alloy problem in materials science, and its limit is proved to approach the Hele-Shaw flow. If the $$L^2(\Omega )$$ error estimate is considered directly as in paper [14], we can only prove that the error bound depends on the exponential function of $$\frac{1}{\epsilon }$$ . Instead, this paper derives the error bound which depends on the polynomial function of $$\frac{1}{\epsilon }$$ by considering the discrete $$H^{-1}$$ error estimate first. There are two main difficulties in proving this polynomial dependence of the discrete $$H^{-1}$$ error estimate. Firstly, it is difficult to prove discrete energy law and discrete stability results due to the complex structure of the bilinear form of the Morley element discretization. This paper overcomes this difficulty by defining four types of discrete inverse Laplace operators and exploring the relations between these discrete inverse Laplace operators and continuous inverse Laplace operator. Each of these operators plays important roles, and their relations are crucial in proving the discrete energy law, discrete stability results and error estimates. Secondly, it is difficult to prove the discrete spectrum estimate in the Morley element space because the Morley element space intersects with the $$C^1$$ conforming finite element space but they are not contained in each other. Instead of proving this discrete spectrum estimate in the Morley element space, this paper proves a generalized coercivity result by exploring properties of the enriching operators and using the discrete spectrum estimate in its $$C^1$$ conforming relative finite element space, which can be obtained by using the spectrum estimate of the Cahn–Hilliard operator. The error estimate in this paper provides an approach to prove the convergence of the numerical interfaces of the Morley element method to the interface of the Hele-Shaw flow.
Unbiased estimates for linear regression via volume sampling

Given a full rank matrix X with more columns than rows consider the task of estimating the pseudo inverse $X^+$ based on the pseudo inverse of a sampled subset of columns (of size at least the number of rows). We show that this is possible if the subset of columns is chosen proportional to the squared volume spanned by the rows of the chosen submatrix (ie, volume sampling). The resulting estimator is unbiased and surprisingly the covariance of the estimator also has a closed form: It equals a specific factor times $X^+X^{+\top}$. Pseudo inverse plays an important part in solving the linear least squares problem, where we try to predict a label for each column of $X$. We assume labels are expensive and we are only given the labels for the small subset of columns we sample from $X$. Using our methods we show that the weight vector of the solution for the sub problem is an unbiased estimator of the optimal solution for the whole problem based on all column labels. We believe that these new formulas establish a fundamental connection between linear least squares and volume sampling. We use our methods to obtain an algorithm for volume sampling that is faster than state-of-the-art and for obtaining bounds for the total loss of the estimated least-squares solution on all labeled columns.
Automated generation and ensemble-learned matching of X-ray absorption spectra

X-ray absorption spectroscopy (XAS) is a widely used materials characterization technique to determine oxidation states, coordination environment, and other local atomic structure information. Analysis of XAS relies on comparison of measured spectra to reliable reference spectra. However, existing databases of XAS spectra are highly limited both in terms of the number of reference spectra available as well as the breadth of chemistry coverage. In this work, we report the development of XASdb, a large database of computed reference XAS, and an Ensemble-Learned Spectra IdEntification (ELSIE) algorithm for the matching of spectra. XASdb currently hosts more than 800,000 K-edge X-ray absorption near-edge spectra (XANES) for over 40,000 materials from the open-science Materials Project database. We discuss a high-throughput automation framework for FEFF calculations, built on robust, rigorously benchmarked parameters. FEFF is a computer program uses a real-space Green’s function approach to calculate X-ray absorption spectra. We will demonstrate that the ELSIE algorithm, which combines 33 weak “learners” comprising a set of preprocessing steps and a similarity metric, can achieve up to 84.2% accuracy in identifying the correct oxidation state and coordination environment of a test set of 19 K-edge XANES spectra encompassing a diverse range of chemistries and crystal structures. The XASdb with the ELSIE algorithm has been integrated into a web application in the Materials Project, providing an important new public resource for the analysis of XAS to all materials researchers. Finally, the ELSIE algorithm itself has been made available as part of veidt, an open source machine-learning library for materials science. Analyzing X-ray absorption spectra (XAS) just became easier thanks to a publically-available database and spectra matching web tool. Interpreting XAS data is currently hindered by a lack of reference spectra, which are laborious to obtain as they require finely tunable X-rays only accessible at synchrotron facilities. Here, a collaboration led by Kristin Persson at the University of California Berkeley, and Shyu Ping Ong at the University of California San Diego developed a ‘high-throughput’ approach generating a large database of computed XAS data, along with a machine-learning algorithm matching unknown spectra with ones in the database. The program correctly identified the oxidation states and coordination environments of a diverse test set of materials with high accuracy. The authors hope their web app will provide a valuable public resource for materials science researchers.
Geometric controls for a tethered quadrotor UAV

This paper deals with the dynamics and controls of a quadrotor unmanned aerial vehicle that is connected to a fixed point on the ground via a tether. Tethered quadrotors have been envisaged for long-term aerial surveillance with high-speed communications. This paper presents an intrinsic form of the dynamic model of a tethered quadrotor including the coupling between deformations of the tether and the motion of the quadrotor, and it constructs geometric control systems to asymptotically stabilize the coupled dynamics of the quadrotor and the tether. The proposed global formulation of dynamics and control also avoids complexities and singularities associated with local coordinates.
ZERO-POINTED MANIFOLDS

We formulate a theory of pointed manifolds, accommodating both embeddings and Pontryagin–Thom collapse maps, so as to present a common generalization of Poincare duality in topology and Koszul duality in -algebra.
Berline–Vergne Valuation and Generalized Permutohedra

Generalizing a conjecture by De Loera et al., we conjecture that integral generalized permutohedra all have positive Ehrhart coefficients. Berline and Vergne construct a valuation that assigns values to faces of polytopes, which provides a way to write Ehrhart coefficients of a polytope as positive sums of these values. Based on available results, we pose a stronger conjecture: Berline–Vergne’s valuation is always positive on permutohedra, which implies our first conjecture. This article proves that our strong conjecture on Berline–Vergne’s valuation is true for dimension up to 6, and is true if we restrict to faces of codimension up to 3. In addition to investigating the positivity conjectures, we study the Berline–Vergne’s valuation, and show that it is the unique construction for McMullen’s formula used to describe number of lattice points in permutohedra under certain symmetry constraints. We also give an equivalent statement to the strong conjecture in terms of mixed valuations.
Electron transport in graphene/graphene side-contact junction by plane-wave multiple-scattering method

Electron transport in graphene is along the sheet but junction devices are often made by stacking different sheets together in a ``side-contact'' geometry which causes the current to flow perpendicular to the sheets within the device. Such geometry presents a challenge to first-principles transport methods. We solve this problem by implementing a plane-wave-based multiple-scattering theory for electron transport. This implementation improves the computational efficiency over the existing plane-wave transport code, scales better for parallelization over large number of nodes, and does not require the current direction to be along a lattice axis. As a first application, we calculate the tunneling current through a side-contact graphene junction formed by two separate graphene sheets with the edges overlapping each other. We find that transport properties of this junction depend strongly on the AA or AB stacking within the overlapping region as well as the vacuum gap between two graphene sheets. Such transport behaviors are explained in terms of carbon orbital orientation, hybridization, and delocalization as the geometry is varied.
HoNVis: Visualizing and exploring higher-order networks

Unlike the conventional first-order network (FoN), the higher-order network (HoN) provides a more accurate description of transitions by creating additional nodes to encode higher-order dependencies. However, there exists no visualization and exploration tool for the HoN. For applications such as the development of strategies to control species invasion through global shipping which is known to exhibit higher-order dependencies, the existing FoN visualization tools are limited. In this paper, we present HoNVis, a novel visual analytics framework for exploring higher-order dependencies of the global ocean shipping network. Our framework leverages coordinated multiple views to reveal the network structure at three levels of detail (i.e., the global, local, and individual port levels). Users can quickly identify ports of interest at the global level and specify a port to investigate its higher-order nodes at the individual port level. Investigating a larger-scale impact is enabled through the exploration of HoN at the local level. Using the global ocean shipping network data, we demonstrate the effectiveness of our approach with a real-world use case conducted by domain experts specializing in species invasion. Finally, we discuss the generalizability of this framework to other real-world applications such as information diffusion in social networks and epidemic spreading through air transportation.
DeepPhys: Video-Based Physiological Measurement Using Convolutional Attention Networks

Non-contact video-based physiological measurement has many applications in health care and human-computer interaction. Practical applications require measurements to be accurate even in the presence of large head rotations. We propose the first end-to-end system for video-based measurement of heart and breathing rate using a deep convolutional network. The system features a new motion representation based on a skin reflection model and a new attention mechanism using appearance information to guide motion estimation, both of which enable robust measurement under heterogeneous lighting and major motions. Our approach significantly outperforms all current state-of-the-art methods on both RGB and infrared video datasets. Furthermore, it allows spatial-temporal distributions of physiological signals to be visualized via the attention mechanism.
Heights on groups and small multiplicative dependencies

We generalize the absolute logarithmic Weil height from elements of the multiplicative group of algebraic numbers modulo torsion, to finitely generated subgoups. The height of a finitely generated subgroup is shown to equal the volume of a certain naturally occurring, convex, symmetric subset of Euclidean space. This connection leads to a bound on the norm of integer vectors that give multiplicative dependencies among finite sets of algebraic numbers.
Six Challenges for Neural Machine Translation.

We explore six challenges for neural machine translation: domain mismatch, amount of training data, rare words, long sentences, word alignment, and beam search. We show both deficiencies and improvements over the quality of phrase-based statistical machine translation.
Tight Complexity Bounds for Optimizing Composite Objectives

We provide tight upper and lower bounds on the complexity of minimizing the average of m convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient descent (AGD) and an accelerated variant of SVRG are optimal in the deterministic and randomized settings respectively, and that a gradient oracle is sufficient for the optimal rate. For non-smooth functions, having access to prox oracles reduces the complexity and we present optimal methods based on smoothing that improve over methods using just gradient accesses.
Capacity region of layered erasure one-sided interference channels without CSIT

This paper studies a layered erasure model for interference channels, which is a simplification of the Gaussian fading interference channel using the deterministic model approach. It is assumed that interference is one-sided, so that one of the receivers is not subject to interference. Moreover, the channel state information (CSI) is known to the receivers, but there is no CSI at transmitters (CSIT). Under these assumptions, the capacity region of the one-sided layered-erasure interference channel is completely determined for arbitrary fading statistics. Previous results of Aggarwal, Sankar, Calderbank and Poor on the capacity region or sum capacity under several interference configurations are shown to be special cases of the capacity region found in this paper.
Closed-Form Expressions for the n-Queens Problem and Related Problems

In this paper, we derive simple closed-form expressions for the $n$-queens problem and three related problems in terms of permanents of $(0,1)$ matrices. These formulas are the first of their kind. Moreover, they provide the first method for solving these problems with polynomial space that has a nontrivial time complexity bound. We then show how a closed-form for the number of Latin squares of order $n$ follows from our method. Finally, we prove lower bounds. In particular, we show that the permanent of Schur's complex valued matrix is a lower bound for the toroidal semi-queens problem, or equivalently, the number of transversals in a cyclic Latin square.
Certified Defenses against Adversarial Examples

While neural networks have achieved high accuracy on standard image classification benchmarks, their accuracy drops to nearly zero in the presence of small adversarial perturbations to test inputs. Defenses based on regularization and adversarial training have been proposed, but often followed by new, stronger attacks that defeat these defenses. Can we somehow end this arms race? In this work, we study this problem for neural networks with one hidden layer. We first propose a method based on a semidefinite relaxation that outputs a certificate that for a given network and test input, no attack can force the error to exceed a certain value. Second, as this certificate is differentiable, we jointly optimize it with the network parameters, providing an adaptive regularizer that encourages robustness against all attacks. On MNIST, our approach produces a network and a certificate that no attack that perturbs each pixel by at most \epsilon = 0.1 can cause more than 35% test error.
Hypergraphs with high projective dimension and 1-dimensional hypergraphs

(Dual) hypergraphs have been used by Kimura, Rinaldo and Terai to characterize squarefree monomial ideals J with pd(R/J) ≤ μ(J) − 1, i.e. whose projective dimension equals the minimal number of generators of J minus 1. In this paper, we prove sufficient and necessary combinatorial conditions for pd(R/J) ≤ μ(J) − 2. The second main result is an effective explicit procedure to compute the projective dimension of a large class of 1-dimensional hypergraphs ℋ (the ones in which every connected component contains at most one cycle). An algorithm to compute the projective dimension is also provided. Applications of these results are given; they include, for instance, computing the projective dimension of monomial ideals whose associated hypergraph has a spanning Ferrers graph.
Glare suppression by coherence gated negation

Imaging of a weak target hidden behind a scattering medium can be significantly confounded by glare. We report a method, termed coherence gated negation (CGN), that uses destructive optical interference to suppress glare and allow improved imaging of a weak target. As a demonstration, we show that by permuting through a set range of amplitude and phase values for a reference beam interfering with the optical field from the glare and target reflection, we can suppress glare by an order of magnitude, even when the optical wavefront is highly disordered. This strategy significantly departs from conventional coherence gating methods in that CGN actively “gates out” the unwanted optical contributions while conventional methods “gate in” the target optical signal. We further show that the CGN method can outperform conventional coherence gating image quality in certain scenarios by more effectively rejecting unwanted optical contributions.
A Parabolic Flow of Pluriclosed Metrics

We define a parabolic flow of pluriclosed metrics. This flow is of the same family introduced by the authors in [15]. We study the relationship of the existence of the flow and associated static metrics to topological information on the underlying complex manifold. Solutions to the static equation are automatically Hermitian-symplectic, a condition we define herein. These static metrics are classified on K3 surfaces, complex toroidal surfaces, nonminimal Hopf surfaces, surfaces of general type, and class VII + surfaces. To finish, we discuss how the flow may potentially be used to study the topology of class VII + surfaces.
Nodal Sets and Doubling Conditions in Elliptic Homogenization

This paper is concerned with uniform measure estimates for nodal sets of solutions in elliptic homogenization. We consider a family of second-order elliptic operators {Le} in divergence form with rapidly oscillating and periodic coefficients. We show that the (d-1)-dimensional Hausdorff measures of the nodal sets of solutions to Le(ue) = 0 in a ball in ℝd are bounded uniformly in e > 0. The proof relies on a uniform doubling condition and approximation of ue by solutions of the homogenized equation.
Computational Transition at the Uniqueness Threshold

The hardcore model is a model of lattice gas systems which has received much attention in statistical physics, probability theory and theoretical computer science. It is the probability distribution over independent sets $I$ of a graph weighted proportionally to $\lambda^{|I|}$ with fugacity parameter $\lambda$. We prove that at the uniqueness threshold of the hardcore model on the $d$-regular tree, approximating the partition function becomes computationally hard on graphs of maximum degree $d$. Specifically, we show that unless NP$=$RP there is no polynomial time approximation scheme for the partition function (the sum of such weighted independent sets) on graphs of maximum degree $d$ for fugacity $\lambda_c(d) 0$. Weitz produced an FPTAS for approximating the partition function when $0
Robocentric visual–inertial odometry:

In this paper, we propose a novel robocentric formulation of the visual–inertial navigation system (VINS) within a sliding-window filtering framework and design an efficient, lightweight, robocentr...
EXISTENCE AND SOAP FILM REGULARITY OF SOLUTIONS TO PLATEAU'S PROBLEM

Plateau's soap lm problem is to nd a surface of least area spanning a given boundary. We begin with a compact orientable (n 2)-dimensional submanifold M of R n . If M is connected, we say a compact set X \spans" M if X intersects every Jordan curve whose linking number with M is 1. Picture a soap lm that spans a loop of wire. Using ( n 1)-dimensional Hausdor spherical measure as the measure of the size of a compact set X in R n , we prove there exists a smallest compact set X0 that spans M. We also show that X0 is almost everywhere a real analytic (n 1)-dimensional minimal submanifold and if n = 3, then X0 has the structure of a soap lm as predicted by Plateau. We provide more details about the minimizer X0. Primarily, X0 is the support of a current S0 and M is the support of the algebraic boundary of S0. We also discuss the more general case where M has codimension > 2.
Revisiting Recurrent Networks for Paraphrastic Sentence Embeddings

We consider the problem of learning general-purpose, paraphrastic sentence embeddings, revisiting the setting of Wieting et al. (2016b). While they found LSTM recurrent networks to underperform word averaging, we present several developments that together produce the opposite conclusion. These include training on sentence pairs rather than phrase pairs, averaging states to represent sequences, and regularizing aggressively. These improve LSTMs in both transfer learning and supervised settings. We also introduce a new recurrent architecture, the Gated Recurrent Averaging Network, that is inspired by averaging and LSTMs while outperforming them both. We analyze our learned models, finding evidence of preferences for particular parts of speech and dependency relations.
DOD-CNN: Doubly-injecting Object Information for Event Recognition

Recognizing an event in an image can be enhanced by detecting relevant objects in two ways: 1) indirectly utilizing object detection information within the unified architecture or 2) directly making use of the object detection output results. We introduce a novel approach, referred to as Doubly-injected Object Detection CNN (DOD-CNN), exploiting the object information in both ways for the task of event recognition. The structure of this network is inspired by the Integrated Object Detection CNN (IOD-CNN) where object information is indirectly exploited by the event recognition module through the shared portion of the network. In the DOD-CNN architecture, the intermediate object detection outputs are directly injected into the event recognition network while keeping the indirect sharing structure inherited from the IOD-CNN, thus being ‘doubly-injected’. We also introduce a batch pooling layer which constructs one representative feature map from multiple object hypotheses. We have demonstrated the effectiveness of injecting the object detection information in two different ways in the task of malicious event recognition.
Data Poisoning Attacks on Factorization-Based Collaborative Filtering

Recommendation and collaborative filtering systems are important in modern information and e-commerce applications. As these systems are becoming increasingly popular in industry, their outputs could affect business decision making, introducing incentives for an adversarial party to compromise the availability or integrity of such systems. We introduce a data poisoning attack on collaborative filtering systems. We demonstrate how a powerful attacker with full knowledge of the learner can generate malicious data so as to maximize his/her malicious objectives, while at the same time mimicking normal user behaviors to avoid being detected. While the complete knowledge assumption seems extreme, it enables a robust assessment of the vulnerability of collaborative filtering schemes to highly motivated attacks. We present efficient solutions for two popular factorization-based collaborative filtering algorithms: the alternative minimization formulation and the nuclear norm minimization method. Finally, we test the effectiveness of our proposed algorithms on real-world data and discuss potential defensive strategies.
Computational Complexity of Generalized Push Fight

We analyze the computational complexity of optimally playing the two-player board game Push Fight, generalized to an arbitrary board and number of pieces. We prove that the game is PSPACE-hard to decide who will win from a given position, even for simple (almost rectangular) hole-free boards. We also analyze the mate-in-1 problem: can the player win in a single turn? One turn in Push Fight consists of up to two "moves" followed by a mandatory "push". With these rules, or generalizing the number of allowed moves to any constant, we show mate-in-1 can be solved in polynomial time. If, however, the number of moves per turn is part of the input, the problem becomes NP-complete. On the other hand, without any limit on the number of moves per turn, the problem becomes polynomially solvable again.
Rational Associahedra and Noncrossing Partitions

Each positive rational number $x>0$ can be written uniquely as $x=a/(b-a)$ for coprime positive integers $0 0$ a simplicial complex $\mathsf{Ass}(x)=\mathsf{Ass}(a,b)$ called the rational associahedron . It is a pure simplicial complex of dimension $a-2$, and its maximal faces are counted by the rational Catalan number $$\mathsf{Cat}(x)=\mathsf{Cat}(a,b):=\frac{(a+b-1)!}{a!\,b!}.$$The cases $(a,b)=(n,n+1)$ and $(a,b)=(n,kn+1)$ recover the classical associahedron and its "Fuss-Catalan" generalization studied by Athanasiadis-Tzanaki and Fomin-Reading. We prove that $\mathsf{Ass}(a,b)$ is shellable and give nice product formulas for its $h$-vector (the rational Narayana numbers ) and $f$-vector (the rational Kirkman numbers ). We define $\mathsf{Ass}(a,b)$ via rational Dyck paths : lattice paths from $(0,0)$ to $(b,a)$ staying above the line $y = \frac{a}{b}x$. We also use rational Dyck paths to define a rational generalization of noncrossing perfect matchings of $[2n]$. In the case $(a,b) = (n, mn+1)$, our construction produces the noncrossing partitions of $[(m+1)n]$ in which each block has size $m+1$.
Low-Rank Semidefinite Programming for the MAX2SAT Problem

This paper proposes a new algorithm for solving MAX2SAT problems based on combining search methods with semidefinite programming approaches. Semidefinite programming techniques are well-known as a theoretical tool for approximating maximum satisfiability problems, but their application has traditionally been very limited by their speed and randomized nature. Our approach overcomes this difficult by using a recent approach to low-rank semidefinite programming, specialized to work in an incremental fashion suitable for use in an exact search algorithm. The method can be used both within complete or incomplete solver, and we demonstrate on a variety of problems from recent competitions. Our experiments show that the approach is faster (sometimes by orders of magnitude) than existing state-of-the-art complete and incomplete solvers, representing a substantial advance in search methods specialized for MAX2SAT problems.
Models vs. inductive inference for dealing with probabilistic knowledge

Publisher Summary This chapter discusses models vs. inductive inference for dealing with probabilistic knowledge. From the standpoint of the model approach, the basic properties of a web—the product is a probability and an extension of a system PC—make webs a highly convenient representation of probabilistic knowledge. For the complex systems of many descriptors common in expert systems, maximum entropy formalisms are cumbersome. Maximum entropy is an instance of min-score inference that has the dual properties: (1) guaranteed expectation—in the case of maximum entropy, the conclusion is always at least as informative as it claims to be—and (2) positive value of information—a conclusion based on additional knowledge can be at least as informative as a conclusion without that knowledge. Substantive inputs can be restricted to the subdistributions in PC for the forest; the product extension is automatically consistent with the inputs. Independence is a common simplifying assumption in expert systems. There is no systematic procedure for determining the most informative forest contained in the knowledge available to the analyst.
New Proofs for the Abhyankar-Gurjar Inversion Formula and the Equivalence of the Jacobian Conjecture and the Vanishing Conjecture

We first give a new proof and also a new formulation for the Abhyankar-Gurjar inversion formula for formal maps of affine spaces. We then use the reformulated Abhyankar-Gurjar formula to give a more straightforward proof for the equivalence of the Jacobian Conjecture with a special case of the Vanishing Conjecture of (homogeneous) quadratic differential operators with constant coefficients.
Why so? or why no? functional causality for explaining query answers

In this paper, we propose causality as a unified framework to explain query answers and non-answers, thus generalizing and extending several previously proposed approaches of provenance and missing query result explanations. We develop our framework starting from the well-studied definition of actual causes by Halpern and Pearl [13]. After identifying some undesirable characteristics of the original definition, we propose functional causes as a refined definition of causality with several desirable properties. These properties allow us to apply our notion of causality in a database context and apply it uniformly to define the causes of query results and their individual contributions in several ways: (i) we can model both provenance as well as nonanswers, (ii) we can define explanations as either data in the input relations or relational operations in a query plan, and (iii) we can give graded degrees of responsibility to individual causes, thus allowing us to rank causes. In particular, our approach allows us to explain contributions to relational aggregate functions and to rank causes according to their respective responsibilities. We give complexity results and describe polynomial algorithms for evaluating causality in tractable cases. Throughout the paper, we illustrate the applicability of our framework with several examples. Overall, we develop in this paper the theoretical foundations of causality theory in a database context.
Interpolation and the weak Lefschetz property

Our starting point is a basic problem in Hermite interpolation theory, namely determining the least degree of a homogeneous polynomial that vanishes to some specified order at every point of a given finite set. We solve this problem if the number of points is small compared to the dimension of their linear span. This also allows us to establish results on the Hilbert function of ideals generated by powers of linear forms. The Verlinde formula determines such a Hilbert function in a specific instance. We complement this result and also determine the Castelnuovo-Mumford regularity of the corresponding ideals. As applications we establish new instances of conjectures by Chudnovsky and by Demailly on the Waldschmidt constant. Moreover, we show that conjectures on the failure of the weak Lefschetz property by Harbourne, Schenck, and Seceleanu as well as by Migliore, Mir\'o-Roig, and the first author are true asymptotically. The latter also relies on a new result about Eulerian numbers.
Blocking duality for $p$-modulus on networks and applications

This paper explores the implications of blocking duality—pioneered by Fulkerson et al.—in the context of p-modulus on networks. Fulkerson blocking duality is an analog on networks to the method of conjugate families of curves in the plane. The technique presented here leads to a general framework for studying families of objects on networks; each such family has a corresponding dual family whose p-modulus is essentially the reciprocal of the original family’s. As an application, we give a modulus-based proof for the fact that effective resistance is a metric on graphs. This proof immediately generalizes to yield a family of graph metrics, depending on the parameter p, that continuously interpolates among the shortest-path metric, the effective resistance metric, and the min-cut ultrametric. In a second application, we establish a connection between Fulkerson blocking duality and the probabilistic interpretation of modulus. This connection, in turn, provides a straightforward proof of several monotonicity properties of modulus that generalize known monotonicity properties of effective resistance. Finally, we use this framework to expand on a result of Lovasz in the context of randomly weighted graphs.
Mesh-Based Affine Abstraction of Nonlinear Systems with Tighter Bounds

In this paper, we consider the problem of piecewise affine abstraction of nonlinear systems, i.e., the over-approximation of its nonlinear dynamics by a pair of piecewise affine functions that “includes” the dynamical characteristics of the original system. As such, guarantees for controllers or estimators based on the affine abstraction also apply to the original nonlinear system. Our approach consists of solving a linear programming (LP) problem that over-approximates the nonlinear function at only the grid points of a mesh with a given resolution and then accounting for the entire domain via an appropriate correction term. To achieve a desired approximation accuracy, we also iteratively subdivide the domain into subregions. Our method applies to nonlinear functions with different degrees of smoothness, including Lipschitz continuous functions, and improves on existing approaches by enabling the use of tighter bounds. Finally, we compare the effectiveness of our approach with existing optimization-based methods in simulation and illustrate its applicability for estimator design.
On the generic and typical ranks of 3-tensors

Abstract We study the generic and typical ranks of 3-tensors of dimension l × m × n using results from matrices and algebraic geometry. We state a conjecture about the exact values of the generic rank of 3-tensors over the complex numbers, which is verified numerically for l , m , n ≤ 14 . We also discuss the typical ranks over the real numbers, and give an example of an infinite family of 3-tensors of the form l = m , n = ( m - 1 ) 2 + 1 , m = 3 , 4 , … , which have at least two typical ranks.
Moment-Based Spectral Analysis of Random Graphs with Given Expected Degrees

We analyze the eigenvalues of a random graph ensemble, proposed by Chung and Lu, in which a given sequence of expected degrees, denoted by $\overline{w}_n = (w^{(n)}_1,\ldots, w^{(n)}_n)$ , is prescribed on the $n$ nodes of a random graph. We focus on the eigenvalues of the normalized (random) adjacency matrix of the graph ensemble, defined as $\mathbf {A}_n$ $=$ $\sqrt{n\rho _n}[\mathbf {a}^{(n)}_{i,j}]_{i,j=1}^{n}$ , where $\rho _n = 1/\sum _{i=1}^{n} w^{(n)}_i$ and $\mathbf {a}^{(n)}_{i,j} =1$ if there is an edge between the nodes $\lbrace i,j\rbrace$ , 0 otherwise. The empirical spectral distribution of $\mathbf {A}_n$ , denoted by $\mathbf {F}_n(\mathord {\cdot})$ , is the empirical measure putting a mass $1/n$ at each of the $n$ real eigenvalues of the symmetric matrix $\mathbf {A}_n$ . Under some technical conditions on the expected degree sequence, we show that with probability one $\mathbf {F}_n(\mathord {\cdot})$ converges weakly to a deterministic distribution $F(\mathord {\cdot})$ as $n\rightarrow \infty$ . Furthermore, we fully characterize this deterministic distribution by providing explicit closed-form expressions for the moments of $F(\mathord {\cdot})$ . We illustrate our results with two well-known degree distributions, namely, the power-law and the exponential degree distributions. Based on our results, we provide significant insights about the bulk behavior of the eigenvalue spectrum; in particular, we analyze the quasi-triangular spectral distribution of power-law networks.
Density Matching for Bilingual Word Embedding.

Recent approaches to cross-lingual word embedding have generally been based on linear transformations between the sets of embedding vectors in the two languages. In this paper, we propose an approach that instead expresses the two monolingual embedding spaces as probability densities defined by a Gaussian mixture model, and matches the two densities using a method called normalizing flow. The method requires no explicit supervision, and can be learned with only a seed dictionary of words that have identical strings. We argue that this formulation has several intuitively attractive properties, particularly with the respect to improving robustness and generalization to mappings between difficult language pairs or word pairs. On a benchmark data set of bilingual lexicon induction and cross-lingual word similarity, our approach can achieve competitive or superior performance compared to state-of-the-art published results, with particularly strong results being found on etymologically distant and/or morphologically rich languages.
Implementing Support for Pointers to Private Data in a General-Purpose Secure Multi-Party Compiler

Recent compilers allow a general-purpose program (written in a conventional programming language) that handles private data to be translated into a secure distributed implementation of the corresponding functionality. The resulting program is then guaranteed to provably protect private data using secure multi-party computation techniques. The goals of such compilers are generality, usability, and efficiency, but the complete set of features of a modern programming language has not been supported to date by the existing compilers. In particular, recent compilers PICCO and the two-party ANSI C compiler strive to translate any C program into its secure multi-party implementation, but they currently lack support for pointers and dynamic memory allocation, which are important components of many C programs. In this work, we mitigate the limitation and add support for pointers to private data and consequently dynamic memory allocation to the PICCO compiler, enabling it to handle a more diverse set of programs over private data. Because doing so opens up a new design space, we investigate the use of pointers to private data (with known as well as private locations stored in them) in programs and report our findings. Aside from dynamic memory allocation, we examine other important topics associated with common pointer use such as reference by pointer/address, casting, and building various data structures in the context of secure multi-party computation. This results in enabling the compiler to automatically translate a user program that uses pointers to private data into its distributed implementation that provably protects private data throughout the computation. We empirically evaluate the constructions and report on the performance of representative programs.
Small zeros of hermitian forms over a quaternion algebra

Let D be a positive definite quaternion algebra over a totally real number field K, F(X, Y ) a hermitian form in 2N variables over D, and Z a right D-vector space which is isotropic with respect to F. We prove the existence of a small-height basis for Z over D, such that F(X, X) vanishes at each of the basis vectors. This constitutes a non-commutative analogue of a theorem of Vaaler (19), and presents an extension of the classical theorem of Cassels (1) on small zeros of rational quadratic forms to the context of quaternion algebras.
A Tableau Approach to the Representation Theory of 0-Hecke Algebras

A 0-Hecke algebra is a deformation of the group algebra of a Coxeter group. Based on work of Norton and Krob-Thibon, we introduce a tableau approach to the representation theory of 0-Hecke algebras of type A, which resembles the classic approach to the representation theory of symmetric groups by Young tableaux and tabloids. We extend this approach to types B and D, and obtain a correspondence between the representation theory of 0-Hecke algebras of types B and D and quasisymmetric functions and noncommutative symmetric functions of types B and D. Other applications are also provided.
Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach

This paper develops theoretical results regarding noisy 1-bit compressed sensing and sparse binomial regression. We demonstrate that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We show that an -sparse signal in can be accurately estimated from m = O(s log(n/s)) single-bit measurements using a simple convex program. This remains true even if each measurement bit is flipped with probability nearly 1/2. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O (s log (2n/s)) Bernoulli trials are sufficient to estimate a coefficient vector in which is approximately -sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension.
DynaSOAr: A Parallel Memory Allocator for Object-Oriented Programming on GPUs with Efficient Memory Access

Object-oriented programming has long been regarded as too inefficient for SIMD high-performance computing, despite the fact that many important HPC applications have an inherent object structure. On SIMD accelerators, including GPUs, this is mainly due to performance problems with memory allocation and memory access: There are a few libraries that support parallel memory allocation directly on accelerator devices, but all of them suffer from uncoalesed memory accesses. We discovered a broad class of object-oriented programs with many important real-world applications that can be implemented efficiently on massively parallel SIMD accelerators. We call this class Single-Method Multiple-Objects (SMMO), because parallelism is expressed by running a method on all objects of a type. To make fast GPU programming available to domain experts who are less experienced in GPU programming, we developed DynaSOAr, a CUDA framework for SMMO applications. DynaSOAr consists of (1) a fully-parallel, lock-free, dynamic memory allocator, (2) a data layout DSL and (3) an efficient, parallel do-all operation. DynaSOAr achieves performance superior to state-of-the-art GPU memory allocators by controlling both memory allocation and memory access. DynaSOAr improves the usage of allocated memory with a Structure of Arrays (SOA) data layout and achieves low memory fragmentation through efficient management of free and allocated memory blocks with lock-free, hierarchical bitmaps. Contrary to other allocators, our design is heavily based on atomic operations, trading raw (de)allocation performance for better overall application performance. In our benchmarks, DynaSOAr achieves a speedup of application code of up to 3x over state-of-the-art allocators. Moreover, DynaSOAr manages heap memory more efficiently than other allocators, allowing programmers to run up to 2x larger problem sizes with the same amount of memory.