The Subset Sum Problem (SSP) is one of those combinatorial problems that are very easy to understand (take a bunch of integer numbers and verify whether there exists a subset of these numbers which sums up to a given target integer), but it can be very difficult to solve.The SSP is actually an NPcomplete problem, but it is "weakly" NP-hard, implying that there are instances of SSP that can be solved in polynomial time.For this particular problem, the instance hardness can be measured by evaluating the so-called "density" index, which basically compares the number of involved integer numbers to the number of bits we need for their binary representation.In our preliminary study on the use of adiabatic quantum computing for the SSP, we investigate the actual feasibility in solving hard instances of the problem.In fact, hard SSP instances are those requiring a large number of bits for the representation of the integers, while the analog nature of the quantum computer does not allow us to ensure highly accurate integer representations.Some preliminary computational experiments performed on D-Wave quantum annealer are presented and compared to standard solvers for classical computers.

We discuss some properties of generative models for word embeddings. Namely, (Arora & Al., 2016) proposed a latent discourse model implying the concentration of the partition function of the word vectors. This concentration phenomenon led to an asymptotic linear relation between the pointwise mutual information (PMI) of pairs of words and the scalar product of their vectors. Here, we first revisit this concentration phenomenon and prove it under slightly weaker assumptions, for a set of random vectors symmetrically distributed around the origin. Second, we empirically evaluate the relation between PMI and scalar products of word vectors satisfying the concentration property. Our empirical results indicate that, in practice, this relation does not hold with arbitrarily small error. This observation is further supported by two theoretical results: (i) the error cannot be exactly zero because the corresponding shifted PMI matrix cannot be positive semidefinite; (ii) under mild assumptions, there exist pairs of words for which the error cannot be close to zero. We deduce that either natural language does not follow the assumptions of the considered generative model, or the current word vector generation methods do not allow the construction of the hypothesized word embeddings.

With the most recent releases of MD-JEEP, new relevant features have been included to our software tool.MD-JEEP solves instances of the class of Discretizable Distance Geometry Problems (DDGPs), which ask to find possible realizations, in a Euclidean space, of a simple weighted undirected graph for which distance constraints between vertices are given, and for which a discretization of the search space can be supplied.Since its version 0.3.0,MD-JEEP is able to deal with instances containing interval data.We focus in this short paper on the most recent release MD-JEEP 0.3.2:among the new implemented features, we will focus our attention on three features: (i) an improved procedure for the generation and update of the boxes used in the coarse-grained representation (necessary to deal with instances containing interval data); (ii) a new procedure for the selection of the so-called discretization vertices (necessary to perform the discretization of the search space); (iii) the implementation of a general parser which allows the user to easily load DDGP instances in a given specified format.The source code of MD-JEEP 0.3.2 is available on GitHub, where the reader can find all additional details about the implementation of such new features, as well as verify the effectiveness of such features by comparing MD-JEEP 0.3.2 with its previous releases.

Human-like characters can be modeled by suitable skeletal structures, which basically consist in trees where edges represent bones and vertices are joints between two adjacent bones.Motion is then defined as variations of the joints' configuration (i.e., partial rotations) over time, which also influences joint positions.However, this representation does not allow to easily represent the relationship between joints that are not directly connected by a bone.This work is therefore based on the premise that variations of the relative distances between such joints are important to represent complex human motions.While the former representations are currently used in practice for playing and analyzing motions, the latter can help in modeling a new class of problems where the relationships in human motions need to be simulated.Our main interest in this work is in adapting previously captured human postures (one frame of a given motion) with the aim of satisfying a certain number of geometrical constraints, which turn out to be easily definable in terms of distances.We present a novel procedure for approximating the relative inter-joint distances for skeletal structures having arbitrary features and respecting a predefined posture.This set of inter-joint distances defines an instance of the Distance Geometry Problem (DGP), that we tackle with a non-monotone spectral gradient method.

In character animation, it is often the case that motions created or captured on a specific morphology need to be reused on characters having a different morphology while maintaining specific relationships such as body contacts or spatial relationships between body parts. This process, called motion retargeting, requires determining which body part relationships are important in a given animation. This paper presents a novel frame-based approach to motion retargeting which relies on a normalized representation of body joints distances. We propose to abstract postures by computing all the inter-joint distances of each animation frame and store them in Euclidean Distance Matrices (EDMs). They 1) present the benefits of capturing all the subtle relationships between body parts, 2) can be adapted through a normalization process to create a morphology-independent distance-based representation, and 3) can be used to efficiently compute retargeted joint positions best satisfying newly computed distances. We demonstrate that normalized EDMs can be efficiently applied to a different skeletal morphology by using a Distance Geometry Problem (DGP) approach, and present results on a selection of motions and skeletal morphologies. Our approach opens the door to a new formulation of motion retargeting problems, solely based on a normalized distance representation.

The Molecular Distance Geometry Problem (MDGP) is the one of finding molecular conformations that satisfy a set of distance constraints obtained through experimental techniques such as Nuclear Magnetic Resonance (NMR).We consider a subclass of MDGP instances that can be discretized, where the search domain has the structure of a tree, which can be explored by using an interval Branch & Prune (iBP) algorithm.When all available distances are exact, all candidate positions for a given molecular conformation can be enumerated.This is however not possible in presence of interval distances, because a continuous subset of positions can actually be computed for some atoms.The focus of this work is on a new scheme for an adaptive generation of a discrete subset of candidate positions from this continuous subset.Our generated candidate positions do not only satisfy the distances employed in the discretization process, but also additional distances that might be available (the so-called pruning distances).Therefore, this new scheme is able to guide more efficiently the search in the feasible regions of the search domain.In this work, we motivate the development and formally introduce this new adaptive scheme.Presented computational experiments show that iBP, integrated with our new scheme, outperforms the standard iBP on a set of NMR-like instances.