OpenRaiser/Intern-Atlas huggingface dataset:
Reconstruction Algorithms for Sums of Affine Powers
Venue: arXiv cs.CC 2017
Year: 2017

In this paper we study sums of powers of affine functions in (mostly) one variable. Although quite simple, this model is a generalization of two well-studied models: Waring decomposition and sparsest shift. For these three models there are natural extensions to several variables, but this paper is mostly focused on univariate polynomials. We present structural results which compare the expressive power of the three models; and we propose algorithms that find the smallest decomposition of f in the first model (sums of affine powers) for an input polynomial f given in dense representation. We also begin a study of the multivariate case. This work could be extended in several directions. In particular, just as for Sparsest Shift and Waring decomposition, one could consider extensions to "supersparse" polynomials and attempt a fuller study of the multi-variate case. We also point out that the basic univariate problem studied in the present paper is far from completely solved: our algorithms all rely on some assumptions for the exponents in an optimal decomposition, and some algorithms also rely on a distinctness assumption for the shifts. It would be very interesting to weaken these assumptions, or even to remove them entirely. Another related and poorly understood issue is that of the bit size of the constants appearing in an optimal decomposition: is it always polynomially related to the bit size of the input polynomial given in dense representation?
Constructing a Natural Language Inference Dataset using Generative Neural Networks
Venue: arXiv cs.AI 2017
Year: 2017

Natural Language Inference is an important task for Natural Language Understanding. It is concerned with classifying the logical relation between two sentences. In this paper, we propose several text generative neural networks for generating text hypothesis, which allows construction of new Natural Language Inference datasets. To evaluate the models, we propose a new metric -- the accuracy of the classifier trained on the generated dataset. The accuracy obtained by our best generative model is only 2.7% lower than the accuracy of the classifier trained on the original, human crafted dataset. Furthermore, the best generated dataset combined with the original dataset achieves the highest accuracy. The best model learns a mapping embedding for each training example. By comparing various metrics we show that datasets that obtain higher ROUGE or METEOR scores do not necessarily yield higher classification accuracies. We also provide analysis of what are the characteristics of a good dataset including the distinguishability of the generated datasets from the original one.
Hybrid LSH: Faster Near Neighbors Reporting in High-dimensional Space
Venue: arXiv cs.DB 2017
Year: 2017

We study the $r$-near neighbors reporting problem ($r$-NN), i.e., reporting \emph{all} points in a high-dimensional point set $S$ that lie within a radius $r$ of a given query point $q$. Our approach builds upon on the locality-sensitive hashing (LSH) framework due to its appealing asymptotic sublinear query time for near neighbor search problems in high-dimensional space. A bottleneck of the traditional LSH scheme for solving $r$-NN is that its performance is sensitive to data and query-dependent parameters. On datasets whose data distributions have diverse local density patterns, LSH with inappropriate tuning parameters can sometimes be outperformed by a simple linear search. In this paper, we introduce a hybrid search strategy between LSH-based search and linear search for $r$-NN in high-dimensional space. By integrating an auxiliary data structure into LSH hash tables, we can efficiently estimate the computational cost of LSH-based search for a given query regardless of the data distribution. This means that we are able to choose the appropriate search strategy between LSH-based search and linear search to achieve better performance. Moreover, the integrated data structure is time efficient and fits well with many recent state-of-the-art LSH-based approaches. Our experiments on real-world datasets show that the hybrid search approach outperforms (or is comparable to) both LSH-based search and linear search for a wide range of search radii and data distributions in high-dimensional space.
Solving equations and optimization problems with uncertainty
Venue: arXiv cs.CG 2017
Year: 2017

We study the problem of detecting zeros of continuous functions that are known only up to an error bound, extending the earlier theoretical work with explicit algorithms and experiments with an implementation. More formally, the robustness of zero of a continuous map $f: X\to \mathbb{R}^n$ is the maximal $r>0$ such that each $g:X\to\mathbb{R}^n$ with $\|f-g\|_\infty\le r$ has a zero. We develop and implement an efficient algorithm approximating the robustness of zero. Further, we show how to use the algorithm for approximating worst-case optima in optimization problems in which the feasible domain is defined by equations that are only known approximately. An important ingredient is an algorithm for deciding the topological extension problem based on computing cohomological obstructions to extendability and their persistence. We describe an explicit algorithm for the primary and secondary obstruction, two stages of a sequence of algorithms with increasing complexity. We provide experimental evidence that for random Gaussian fields, the primary obstruction---a much less computationally demanding test than the secondary obstruction---is typically sufficient for approximating robustness of zero.
Joint Uplink/Downlink Optimization for Backhaul-Limited Mobile Cloud Computing with User Scheduling
Venue: arXiv cs.NI 2017
Year: 2017

Mobile cloud computing enables the offloading of computationally heavy applications, such as for gaming, object recognition or video processing, from mobile users (MUs) to cloudlet or cloud servers, which are connected to wireless access points, either directly or through finite-capacity backhaul links. In this paper, the design of a mobile cloud computing system is investigated by proposing the joint optimization of computing and communication resources with the aim of minimizing the energy required for offloading across all MUs under latency constraints at the application layer. The proposed design accounts for multiantenna uplink and downlink interfering transmissions, with or without cooperation on the downlink, along with the allocation of backhaul and computational resources and user selection. The resulting design optimization problems are nonconvex, and stationary solutions are computed by means of successive convex approximation (SCA) techniques. Numerical results illustrate the advantages in terms of energy-latency trade-off of the joint optimization of computing and communication resources, as well as the impact of system parameters, such as backhaul capacity, and of the network architecture.
Interpolation of Sparse Graph Signals by Sequential Adaptive Thresholds
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the problem of interpolating signals defined on graphs. A major presumption considered by many previous approaches to this problem has been lowpass/ band-limitedness of the underlying graph signal. However, inspired by the findings on sparse signal reconstruction, we consider the graph signal to be rather sparse/compressible in the Graph Fourier Transform (GFT) domain and propose the Iterative Method with Adaptive Thresholding for Graph Interpolation (IMATGI) algorithm for sparsity promoting interpolation of the underlying graph signal.We analytically prove convergence of the proposed algorithm. We also demonstrate efficient performance of the proposed IMATGI algorithm in reconstructing randomly generated sparse graph signals. Finally, we consider the widely desirable application of recommendation systems and show by simulations that IMATGI outperforms state-of-the-art algorithms on the benchmark datasets in this application.
Connectivity Oracles for Graphs Subject to Vertex Failures
Venue: arXiv cs.DS 2017
Year: 2017

We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes a batch of $d\leq d_{\star}$ failed vertices in $\tilde{O}(d^3)$ time and thereafter answers connectivity queries in $O(d)$ time. It occupies space $O(d_{\star} m\log n)$. We develop a randomized Monte Carlo version of our data structure with update time $\tilde{O}(d^2)$, query time $O(d)$, and space $\tilde{O}(m)$ for any failure bound $d\le n$. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. We also develop a more efficient Monte Carlo edge-failure connectivity oracle. Using space $O(n\log^2 n)$, $d$ edge failures are processed in $O(d\log d\log\log n)$ time and thereafter, connectivity queries are answered in $O(\log\log n)$ time, which are correct w.h.p. Our data structures are based on a new decomposition theorem for an undirected graph $G=(V,E)$, which is of independent interest. It states that for any terminal set $U\subseteq V$ we can remove a set $B$ of $|U|/(s-2)$ vertices such that the remaining graph contains a Steiner forest for $U-B$ with maximum degree $s$.
Performance of Lattice Coset Codes on Universal Software Radio Peripherals
Venue: arXiv cs.IT 2017
Year: 2017

We consider an experimental setup of three USRPs that implement a wiretap channel, two USRPs are the legitimate players Alice and Bob, while the third USRP is the eavesdropper, whose position we vary to evaluate information leakage. The experimented channels are close to slow fading channels, and coset coding of lattice constellations is used for transmission, allowing to introduce controlled randomness at the transmitter. Simulation and measurement results show to which extent coset coding can provide confidentiality, as a function of Eve's position, and the amount of randomness used.
Worst-case Redundancy of Optimal Binary AIFV Codes and their Extended Codes
Venue: arXiv cs.IT 2017
Year: 2017

Binary AIFV codes are lossless codes that generalize the class of instantaneous FV codes. The code uses two code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, which is the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to coincide with the worst-case redundancy of the codes. Along with this, the worst-case redundancy is derived in terms of $p_{\max}\geq$1/2, where $p_{\max}$ is the probability of the most likely source symbol. Additionally, we propose an extension of binary AIFV codes, which use $m$ code trees and allow at most $m$-bit decoding delay. We show that the worst-case redundancy of the extended binary AIFV codes is $1/m$ for $m \leq 4.$
The $ρ$-Capacity of a Graph
Venue: arXiv cs.IT 2017
Year: 2017

Motivated by the problem of zero-error broadcasting, we introduce a new notion of graph capacity, termed $ρ$-capacity, that generalizes the Shannon capacity of a graph. We derive upper and lower bounds on the $ρ$-capacity of arbitrary graphs, and provide a Lovász-type upper bound for regular graphs. We study the behavior of the $ρ$-capacity under two graph operations: the strong product and the disjoint union. Finally, we investigate the connection between the structure of a graph and its $ρ$-capacity.
The Descriptive Complexity of Subgraph Isomorphism without Numerics
Venue: arXiv cs.CC 2017
Year: 2017

Let $F$ be a connected graph with $\ell$ vertices. The existence of a subgraph isomorphic to $F$ can be defined in first-order logic with quantifier depth no better than $\ell$, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs $K_\ell$ and $K_{\ell-1}$. We show that, for some $F$, the existence of an $F$ subgraph in \emph{sufficiently large} connected graphs is definable with quantifier depth $\ell-3$. On the other hand, this is never possible with quantifier depth better than $\ell/2$. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some $F$ be arbitrarily small comparing to $\ell$ but never smaller than the treewidth of $F$. Moreover, the definitions over highly connected graphs require quantifier depth strictly more than the density of $F$. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs $F$ on 4 vertices.
"Open Innovation" and "Triple Helix" Models of Innovation: Can Synergy in Innovation Systems Be Measured?
Venue: arXiv cs.CY 2017
Year: 2017

The model of "Open Innovations" (OI) can be compared with the "Triple Helix of University-Industry-Government Relations" (TH) as attempts to find surplus value in bringing industrial innovation closer to public R&D. Whereas the firm is central in the model of OI, the TH adds multi-centeredness: in addition to firms, universities and (e.g., regional) governments can take leading roles in innovation eco-systems. In addition to the (transversal) technology transfer at each moment of time, one can focus on the dynamics in the feedback loops. Under specifiable conditions, feedback loops can be turned into feedforward ones that drive innovation eco-systems towards self-organization and the auto-catalytic generation of new options. The generation of options can be more important than historical realizations ("best practices") for the longer-term viability of knowledge-based innovation systems. A system without sufficient options, for example, is locked-in. The generation of redundancy -- the Triple Helix indicator -- can be used as a measure of unrealized but technologically feasible options given a historical configuration. Different coordination mechanisms (markets, policies, knowledge) provide different perspectives on the same information and thus generate redundancy. Increased redundancy not only stimulates innovation in an eco-system by reducing the prevailing uncertainty; it also enhances the synergy in and innovativeness of an innovation system.
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
Venue: arXiv cs.DS 2017
Year: 2017

Miller et al. \cite{MPVX15} devised a distributed\footnote{They actually showed a PRAM algorithm. The distributed algorithm with these properties is implicit in \cite{MPVX15}.} algorithm in the CONGEST model, that given a parameter $k = 1,2,\ldots$, constructs an $O(k)$-spanner of an input unweighted $n$-vertex graph with $O(n^{1+1/k})$ expected edges in $O(k)$ rounds of communication. In this paper we improve the result of \cite{MPVX15}, by showing a $k$-round distributed algorithm in the same model, that constructs a $(2k-1)$-spanner with $O(n^{1+1/k}/ε)$ edges, with probability $1- ε$, for any $ε>0$. Moreover, when $k = ω(\log n)$, our algorithm produces (still in $k$ rounds) {\em ultra-sparse} spanners, i.e., spanners of size $n(1+ o(1))$, with probability $1- o(1)$. To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large $k$, it provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm. We also devise improved bounds (and algorithms realizing these bounds) for $(1+ε,β)$-spanners and emulators. In particular, we show that for any unweighted $n$-vertex graph and any $ε> 0$, there exists a $(1+ ε, ({{\log\log n} \over ε})^{\log\log n})$-emulator with $O(n)$ edges. All previous constructions of $(1+ε,β)$-spanners and emulators employ a superlinear number of edges, for all choices of parameters. Finally, we provide some applications of our results to approximate shortest paths' computation in unweighted graphs.
Walking of the iCub humanoid robot in different scenarios: implementation and performance analysis
Venue: arXiv cs.RO 2017
Year: 2017

The humanoid robot iCub is a research platform of the Fondazione Istituto Italiano di Tecnologia (IIT), spread among different institutes around the world. In the most recent version of iCub, the robot is equipped with stronger legs and bigger feet, allowing it to perform balancing and walking motions that were not possible with the first generations. Despite the new legs hardware, walking has been rarely performed on the iCub robot. In this work the objective is to implement walking motions on the robot, from which we want to analyze its walking capabilities. We developed software modules based on extensions of classic techniques such as the ZMP based pattern generator and position control to identify which are the characteristics as well as limitations of the robot against different walking tasks in order to give the users a reference of the performance of the robot. Most of the experiments have been performed with HeiCub, a reduced version of iCub without arms and head.
Face Recognition Using Scattering Convolutional Network
Venue: arXiv cs.CV 2017
Year: 2017

Face recognition has been an active research area in the past few decades. In general, face recognition can be very challenging due to variations in viewpoint, illumination, facial expression, etc. Therefore it is essential to extract features which are invariant to some or all of these variations. Here a new image representation, called scattering transform/network, has been used to extract features from faces. The scattering transform is a kind of convolutional network which provides a powerful multi-layer representation for signals. After extraction of scattering features, PCA is applied to reduce the dimensionality of the data and then a multi-class support vector machine is used to perform recognition. The proposed algorithm has been tested on three face datasets and achieved a very high recognition rate.
Optimal Distance Labeling Schemes for Trees
Venue: arXiv cs.DS 2017
Year: 2017

Labeling schemes seek to assign a short label to each node in a network, so that a function on two nodes can be computed by examining their labels alone. For the particular case of trees, optimal bounds (up to low order terms) were recently obtained for adjacency labeling [FOCS'15], nearest common ancestor labeling [SODA'14], and ancestry labeling [SICOMP'06]. In this paper we obtain optimal bounds for distance labeling. We present labels of size $1/4\log^2n+o(\log^2n)$, matching (up to low order terms) the recent $1/4\log^2n-O(\log n)$ lower bound [ICALP'16]. Prior to our work, all distance labeling schemes for trees could be reinterpreted as universal trees. A tree $T$ is said to be universal if any tree on $n$ nodes can be found as a subtree of $T$. A universal tree with $|T|$ nodes implies a distance labeling scheme with label size $\log |T|$. In 1981, Chung et al. proved that any distance labeling scheme based on universal trees requires labels of size $1/2\log^2 n-\log n\cdot\log\log n+O(\log n)$. Our scheme is the first to break this lower bound, showing a separation between distance labeling and universal trees. The $Θ(\log^2 n)$ barrier has led researchers to consider distances bounded by $k$. The size of such labels was improved from $\log n+O(k\sqrt{\log n})$ [WADS'01] to $\log n+O(k^2(\log(k\log n))$ [SODA'03] and then to $\log n+O(k\log(k\log(n/k)))$ [PODC'07]. We show how to construct labels whose size is $\min\{\log n+O(k\log((\log n)/k)),O(\log n\cdot\log(k/\log n))\}$. We complement this with almost tight lower bounds of $\log n+Ω(k\log(\log n/(k\log k)))$ and $Ω(\log n\cdot\log(k/\log n))$. Finally, we consider $(1+\varepsilon)$-approximate distances. We show that the labeling scheme of [ICALP'16] can be easily modified to obtain an $O(\log(1/\varepsilon)\cdot\log n)$ upper bound and we prove a $Ω(\log(1/\varepsilon)\cdot\log n)$ lower bound.
A Neural Knowledge Language Model
Venue: arXiv cs.CL 2017
Year: 2017

Current language models have a significant limitation in the ability to encode and decode factual knowledge. This is mainly because they acquire such knowledge from statistical co-occurrences although most of the knowledge words are rarely observed. In this paper, we propose a Neural Knowledge Language Model (NKLM) which combines symbolic knowledge provided by the knowledge graph with the RNN language model. By predicting whether the word to generate has an underlying fact or not, the model can generate such knowledge-related words by copying from the description of the predicted fact. In experiments, we show that the NKLM significantly improves the performance while generating a much smaller number of unknown words.
Skipping Selected Steps of DWT Computation in Lossless JPEG 2000 for Improved Bitrates
Venue: arXiv cs.MM 2017
Year: 2017

In order to improve bitrates of lossless JPEG 2000, we propose to modify the discrete wavelet transform (DWT) by skipping selected steps of its computation. We employ a heuristic to construct the skipped steps DWT (SS-DWT) in an image-adaptive way and define fixed SS-DWT variants. For a large and diverse set of images, we find that SS-DWT significantly improves bitrates of non-photographic images. From a practical standpoint, the most interesting results are obtained by applying entropy estimation of coding effects for selecting among the fixed SS-DWT variants. This way we get the compression scheme that, as opposed to the general SS-DWT case, is compliant with the JPEG 2000 part 2 standard. It provides average bitrate improvement of roughly 5% for the entire test-set, whereas the overall compression time becomes only 3% greater than that of the unmodified JPEG 2000. Bitrates of photographic and non-photographic images are improved by roughly 0.5% and 14%, respectively. At a significantly increased cost of exploiting a heuristic, selecting the steps to be skipped based on the actual bitrate instead of an estimated one, and by applying reversible denoising and lifting steps to SS-DWT, we have attained greater bitrate improvements of up to about 17.5% for non-photographic images.
Kobayashi compressibility
Venue: arXiv cs.CC 2017
Year: 2017

Kobayashi introduced a uniform notion of compressibility of infinite binary sequences in terms of relative Turing computations with sub-identity use of the oracle. Kobayashi compressibility has remained a relatively obscure notion, with the exception of some work on resource bounded Kolmogorov complexity. The main goal of this note is to show that it is relevant to a number of topics in current research on algorithmic randomness. We prove that Kobayashi compressibility can be used in order to define Martin-Loef randomness, a strong version of finite randomness and Kurtz randomness, strictly in terms of Turing reductions. Moreover these randomness notions naturally correspond to Turing reducibility, weak truth-table reducibility and truth-table reducibility respectively. Finally we discuss Kobayashi's main result from his 1981 technical report regarding the compressibility of computably enumerable sets, and provide additional related original results.