OpenRaiser/Intern-Atlas huggingface dataset:
Fast keyed hash/pseudo-random function using SIMD multiply and permute
Venue: arXiv cs.CR 2017
Year: 2017

HighwayHash is a new pseudo-random function based on SIMD multiply and permute instructions for thorough and fast hashing. It is 5.2 times as fast as SipHash for 1 KiB inputs. An open-source implementation is available under a permissive license. We discuss design choices and provide statistical analysis, speed measurements and preliminary cryptanalysis. Assuming it withstands further analysis, strengthened variants may also substantially accelerate file checksums and stream ciphers.
Computing Human-Understandable Strategies
Venue: arXiv cs.GT 2017
Year: 2017

Algorithms for equilibrium computation generally make no attempt to ensure that the computed strategies are understandable by humans. For instance the strategies for the strongest poker agents are represented as massive binary files. In many situations, we would like to compute strategies that can actually be implemented by humans, who may have computational limitations and may only be able to remember a small number of features or components of the strategies that have been computed. We study poker games where private information distributions can be arbitrary. We create a large training set of game instances and solutions, by randomly selecting the information probabilities, and present algorithms that learn from the training instances in order to perform well in games with unseen information distributions. We are able to conclude several new fundamental rules about poker strategy that can be easily implemented by humans.
The Best of Both Worlds: Linear Functional Programming without Compromise
Venue: arXiv cs.PL 2017
Year: 2017

We present a linear functional calculus with both the safety guarantees expressible with linear types and the rich language of combinators and composition provided by functional programming. Unlike previous combinations of linear typing and functional programming, we compromise neither the linear side (for example, our linear values are first-class citizens of the language) nor the functional side (for example, we do not require duplicate definitions of compositions for linear and unrestricted functions). To do so, we must generalize abstraction and application to encompass both linear and unrestricted functions. We capture the typing of the generalized constructs with a novel use of qualified types. Our system maintains the metatheoretic properties of the theory of qualified types, including principal types and decidable type inference. Finally, we give a formal basis for our claims of expressiveness, by showing that evaluation respects linearity, and that our language is a conservative extension of existing functional calculi.
Unsupervised Perceptual Rewards for Imitation Learning
Venue: arXiv cs.CV 2017
Year: 2017

Reward function design and exploration time are arguably the biggest obstacles to the deployment of reinforcement learning (RL) agents in the real world. In many real-world tasks, designing a reward function takes considerable hand engineering and often requires additional sensors to be installed just to measure whether the task has been executed successfully. Furthermore, many interesting tasks consist of multiple implicit intermediate steps that must be executed in sequence. Even when the final outcome can be measured, it does not necessarily provide feedback on these intermediate steps. To address these issues, we propose leveraging the abstraction power of intermediate visual representations learned by deep models to quickly infer perceptual reward functions from small numbers of demonstrations. We present a method that is able to identify key intermediate steps of a task from only a handful of demonstration sequences, and automatically identify the most discriminative features for identifying these steps. This method makes use of the features in a pre-trained deep model, but does not require any explicit specification of sub-goals. The resulting reward functions can then be used by an RL agent to learn to perform the task in real-world settings. To evaluate the learned reward, we present qualitative results on two real-world tasks and a quantitative evaluation against a human-designed reward function. We also show that our method can be used to learn a real-world door opening skill using a real robot, even when the demonstration used for reward learning is provided by a human using their own hand. To our knowledge, these are the first results showing that complex robotic manipulation skills can be learned directly and without supervised labels from a video of a human performing the task. Supplementary material and data are available at https://sermanet.github.io/rewards
From Images to 3D Shape Attributes
Venue: arXiv cs.CV 2017
Year: 2017

Our goal in this paper is to investigate properties of 3D shape that can be determined from a single image. We define 3D shape attributes -- generic properties of the shape that capture curvature, contact and occupied space. Our first objective is to infer these 3D shape attributes from a single image. A second objective is to infer a 3D shape embedding -- a low dimensional vector representing the 3D shape. We study how the 3D shape attributes and embedding can be obtained from a single image by training a Convolutional Neural Network (CNN) for this task. We start with synthetic images so that the contribution of various cues and nuisance parameters can be controlled. We then turn to real images and introduce a large scale image dataset of sculptures containing 143K images covering 2197 works from 242 artists. For the CNN trained on the sculpture dataset we show the following: (i) which regions of the imaged sculpture are used by the CNN to infer the 3D shape attributes; (ii) that the shape embedding can be used to match previously unseen sculptures largely independent of viewpoint; and (iii) that the 3D attributes generalize to images of other (non-sculpture) object classes.
Private Information Retrieval in Distributed Storage Systems Using an Arbitrary Linear Code
Venue: arXiv cs.IT 2017
Year: 2017

We propose an information-theoretic private information retrieval (PIR) scheme for distributed storage systems where data is stored using a linear systematic code of rate $R > 1/2$. The proposed scheme generalizes the PIR scheme for data stored using maximum distance separable codes recently proposed by Tajeddine and El Rouayheb for the scenario of a single spy node. We further propose an algorithm to optimize the communication price of privacy (cPoP) using the structure of the underlying linear code. As an example, we apply the proposed algorithm to several distributed storage codes, showing that the cPoP can be significantly reduced by exploiting the structure of the distributed storage code.
Transmission and Storage Rates for Sequential Massive Random Access
Venue: arXiv cs.IT 2017
Year: 2017

This paper introduces a new source coding paradigm called Sequential Massive Random Access (SMRA). In SMRA, a set of correlated sources is encoded once for all and stored on a server, and clients want to successively access to only a subset of the sources. Since the number of simultaneous clients can be huge, the server is only allowed to extract a bitstream from the stored data: no re-encoding can be performed before the transmission of the specific client's request. In this paper, we formally define the SMRA framework and introduce both storage and transmission rates to characterize the performance of SMRA. We derive achievable transmission and storage rates for lossless source coding of i.i.d. and non i.i.d. sources, and transmission and storage rates-distortion regions for Gaussian sources. We also show two practical implementations of SMRA systems based on rate-compatible LDPC codes. Both theoretical and experimental results demonstrate that SMRA systems can reach the same transmission rates as in traditional point to point source coding schemes, while having a reasonable overhead in terms of storage rate. These results constitute a breakthrough for many recent data transmission applications in which different parts of the data are requested by the clients.
Random generation of closed simply-typed $λ$-terms: a synergy between logic programming and Boltzmann samplers
Venue: arXiv cs.LO 2017
Year: 2017

A natural approach to software quality assurance consists in writing unit tests securing programmer-declared code invariants. Throughout the literature a great body of work has been devoted to tools and techniques automating this labour-intensive process. A prominent example is the successful use of randomness, in particular random typeable $λ$-terms, in testing functional programming compilers such as the Glasgow Haskell Compiler. Unfortunately, due to the intrinsically difficult combinatorial structure of typeable $λ$-terms no effective uniform sampling method is known, setting it as a fundamental open problem in the random software testing approach. In this paper we combine the framework of Boltzmann samplers, a powerful technique of random combinatorial structure generation, with today's Prolog systems offering a synergy between logic variables, unification with occurs check and efficient backtracking. This allows us to develop a novel sampling mechanism able to construct uniformly random closed simply-typed $λ$-terms of up size 120. We apply our techniques to the generation of uniformly random closed simply-typed normal forms and design a parallel execution mechanism pushing forward the achievable term size to 140. Under consideration in Theory and Practice of Logic Programming (TPLP).
Set Similarity Search Beyond MinHash
Venue: arXiv cs.DS 2017
Year: 2017

We consider the problem of approximate set similarity search under Braun-Blanquet similarity $B(\mathbf{x}, \mathbf{y}) = |\mathbf{x} \cap \mathbf{y}| / \max(|\mathbf{x}|, |\mathbf{y}|)$. The $(b_2, b_2)$-approximate Braun-Blanquet similarity search problem is to preprocess a collection of sets $P$ such that, given a query set $\mathbf{q}$, if there exists $\mathbf{x} \in P$ with $B(\mathbf{q}, \mathbf{x}) \geq b_1$, then we can efficiently return $\mathbf{x}' \in P$ with $B(\mathbf{q}, \mathbf{x}') > b_2$. We present a simple data structure that solves this problem with space usage $O(n^{1+ρ}\log n + \sum_{\mathbf{x} \in P}|\mathbf{x}|)$ and query time $O(|\mathbf{q}|n^ρ \log n)$ where $n = |P|$ and $ρ= \log(1/b_1)/\log(1/b_2)$. Making use of existing lower bounds for locality-sensitive hashing by O'Donnell et al. (TOCT 2014) we show that this value of $ρ$ is tight across the parameter space, i.e., for every choice of constants $0 < b_2 < b_1 < 1$. In the case where all sets have the same size our solution strictly improves upon the value of $ρ$ that can be obtained through the use of state-of-the-art data-independent techniques in the Indyk-Motwani locality-sensitive hashing framework (STOC 1998) such as Broder's MinHash (CCS 1997) for Jaccard similarity and Andoni et al.'s cross-polytope LSH (NIPS 2015) for cosine similarity. Surprisingly, even though our solution is data-independent, for a large part of the parameter space we outperform the currently best data-dependent method by Andoni and Razenshteyn (STOC 2015).
Teechan: Payment Channels Using Trusted Execution Environments
Venue: arXiv cs.CR 2017
Year: 2017

Blockchain protocols are inherently limited in transaction throughput and latency. Recent efforts to address performance and scale blockchains have focused on off-chain payment channels. While such channels can achieve low latency and high throughput, deploying them securely on top of the Bitcoin blockchain has been difficult, partly because building a secure implementation requires changes to the underlying protocol and the ecosystem. We present Teechan, a full-duplex payment channel framework that exploits trusted execution environments. Teechan can be deployed securely on the existing Bitcoin blockchain without having to modify the protocol. It: (i) achieves a higher transaction throughput and lower transaction latency than prior solutions; (ii) enables unlimited full-duplex payments as long as the balance does not exceed the channel's credit; (iii) requires only a single message to be sent per payment in any direction; and (iv) places at most two transactions on the blockchain under any execution scenario. We have built and deployed the Teechan framework using Intel SGX on the Bitcoin network. Our experiments show that, not counting network latencies, Teechan can achieve 2,480 transactions per second on a single channel, with sub-millisecond latencies.
Node Aware Sparse Matrix-Vector Multiplication
Venue: arXiv cs.DC 2017
Year: 2017

The sparse matrix-vector multiply (SpMV) operation is a key computational kernel in many simulations and linear solvers. The large communication requirements associated with a reference implementation of a parallel SpMV result in poor parallel scalability. The cost of communication depends on the physical locations of the send and receive processes: messages injected into the network are more costly than messages sent between processes on the same node. In this paper, a node aware parallel SpMV (NAPSpMV) is introduced to exploit knowledge of the system topology, specifically the node-processor layout, to reduce costs associated with communication. The values of the input vector are redistributed to minimize both the number and the size of messages that are injected into the network during a SpMV, leading to a reduction in communication costs. A variety of computational experiments that highlight the efficiency of this approach are presented.
A green program lifecycle supporting energy-efficient applications
Venue: arXiv cs.SE 2017
Year: 2017

With the advent of the Internet of Things (IoT), the percentage of global emissions attributable to Information Systems is expected to further increase in the coming years, due to a proliferation of Internet-connected devices omnipresent in our daily lives (e.g., electric meters, wearable devices, etc.). Although software systems do not directly consume energy, they strongly affect the energy consumption of the hardware. So, developers should be more aware of the energy consumed by these systems during their lifetime, and think about the long-term consequences in the sustainability of our planet Earth. Indeed, once deployed, the energy consumed by a system depends on several factors determined mainly by the usage context. This means that the area of energy-efficient software development needs green development lifecycles that provide appropriate methodologies and tools to identify and analyze the energy hotspots of applications early at design time, and see how they can be self-adapted to the runtime context usage. Regrettably, there is a narrow view of developers and users and their responsibility in the energy consumed during application execution. Developers rarely address energy efficiency as some recent studies show, mostly because they lack appropriate methodologies and tools that help them to produce green software at runtime. So, although software energy efficiency is becoming increasingly important in an ever more technology-dependent world, development processes of self-greening systems supported by tools are still in their infancy. On the other hand, considering that many of current applications are normally deployed in smartphones or in any kind of smart objects (e.g., sensors, watches, etc.), optimizing the energy consumption during the execution will also have a strong impact in battery saving, enhancing the quality of experience of final users.
All-Pairs 2-Reachability in $\mathcal{O}(n^ω\log n)$ Time
Venue: arXiv cs.DS 2017
Year: 2017

In the $2$-reachability problem we are given a directed graph $G$ and we wish to determine if there are two (edge or vertex) disjoint paths from $u$ to $v$, for a given pair of vertices $u$ and $v$. In this paper, we present an algorithm that computes $2$-reachability information for all pairs of vertices in $\mathcal{O}(n^ω\log n)$ time, where $n$ is the number of vertices and $ω$ is the matrix multiplication exponent. Hence, we show that the running time of all-pairs $2$-reachability is only within a $\log$ factor of transitive closure. Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex) for all pair of vertices where $2$-reachability does not hold. By processing these witnesses, we can compute all the edge- and vertex-dominator trees of $G$ in $\mathcal{O}(n^2)$ additional time, which in turn enables us to answer various connectivity queries in $\mathcal{O}(1)$ time. For instance, we can test in constant time if there is a path from $u$ to $v$ avoiding an edge $e$, for any pair of query vertices $u$ and $v$, and any query edge $e$, or if there is a path from $u$ to $v$ avoiding a vertex $w$, for any query vertices $u$, $v$, and $w$.
A Very Low Complexity Successive Symbol-by-Symbol Sequence Estimator for Faster-than-Nyquist Signaling
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate the sequence estimation problem of binary and quadrature phase shift keying faster-than-Nyquist (FTN) signaling and propose two novel low-complexity sequence estimation techniques based on concepts of successive interference cancellation. To the best of our knowledge, this is the first approach in the literature to detect FTN signaling on a symbol-by-symbol basis. In particular, based on the structure of the self-interference inherited in FTN signaling, we first find the operating region boundary---defined by the root-raised cosine (rRC) pulse shape, its roll-off factor, and the time acceleration parameter of the FTN signaling---where perfect estimation of the transmit data symbols on a symbol-by-symbol basis is guaranteed, assuming noise-free transmission. For noisy transmission, we then propose a novel low-complexity technique that works within the operating region and is capable of estimating the transmit data symbols on a symbol-by-symbol basis. To reduce the error propagation of the proposed successive symbol-by-symbol sequence estimator (SSSSE), we propose a successive symbol-by-symbol with go-back-$K$ sequence estimator (SSSgb$K$SE) that goes back to re-estimate up to $K$ symbols, and subsequently improves the estimation accuracy of the current data symbol. Simulation results show that the proposed sequence estimation techniques perform well for low intersymbol interference (ISI) scenarios and can significantly increase the data rate and spectral efficiency. Additionally, results reveal that choosing the value of $K$ as low as $2$ or $3$ data symbols is sufficient to significantly improve the bit-error-rate performance. Results also show that the performance of the proposed SSSgb$K$SE, with $K = 1$ or $2$, surpasses the performance of the lowest complexity equalizers reported in the literature, with reduced computational complexity.
The probability of a computable output from a random oracle
Venue: arXiv cs.CC 2017
Year: 2017

Consider a universal Turing machine that produces a partial or total function (or a binary stream), based on the answers to the binary queries that it makes during the computation. We study the probability that the machine will produce a computable function when it is given a random stream of bits as the answers to its queries. Surprisingly, we find that these probabilities are the entire class of real numbers in (0, 1) that can be written as the difference of two halting probabilities relative to the halting problem. In particular, there are universal Turing machines which produce a computable output with probability exactly 1/2. Our results contrast a large array of facts (the most well-known being the randomness of Chaitin's halting probability) which witness maximal initial segment complexity of probabilities associated with universal machines. Our proof uses recent advances in algorithmic randomness.
Semantic Video Segmentation by Gated Recurrent Flow Propagation
Venue: arXiv cs.CV 2017
Year: 2017

Semantic video segmentation is challenging due to the sheer amount of data that needs to be processed and labeled in order to construct accurate models. In this paper we present a deep, end-to-end trainable methodology to video segmentation that is capable of leveraging information present in unlabeled data in order to improve semantic estimates. Our model combines a convolutional architecture and a spatio-temporal transformer recurrent layer that are able to temporally propagate labeling information by means of optical flow, adaptively gated based on its locally estimated uncertainty. The flow, the recognition and the gated temporal propagation modules can be trained jointly, end-to-end. The temporal, gated recurrent flow propagation component of our model can be plugged into any static semantic segmentation architecture and turn it into a weakly supervised video processing one. Our extensive experiments in the challenging CityScapes and Camvid datasets, and based on multiple deep architectures, indicate that the resulting model can leverage unlabeled temporal frames, next to a labeled one, in order to improve both the video segmentation accuracy and the consistency of its temporal labeling, at no additional annotation cost and with little extra computation.
Inference of Phylogenetic Trees from the Knowledge of Rare Evolutionary Events
Venue: arXiv cs.DM 2017
Year: 2017

Rare events have played an increasing role in molecular phylogenetics as potentially homoplasy-poor characters.In this contribution we analyze the phylogenetic information content from a combinatorial point of view by consid-ering the binary relation on the set of taxa defined by the existence of a single event separating two taxa. We showthat the graph-representation of this relation must be a tree. Moreover, we characterize completely the relationshipbetween the tree of such relations and the underlying phylogenetic tree. With directed operations such as tandem-duplication-random-loss events in mind we demonstrate how non-symmetric information constrains the position ofthe root in the partially reconstructed phylogeny.
Linear Learning with Sparse Data
Venue: arXiv cs.LG 2017
Year: 2017

Linear predictors are especially useful when the data is high-dimensional and sparse. One of the standard techniques used to train a linear predictor is the Averaged Stochastic Gradient Descent (ASGD) algorithm. We present an efficient implementation of ASGD that avoids dense vector operations. We also describe a translation invariant extension called Centered Averaged Stochastic Gradient Descent (CASGD).
Advice Complexity of the Online Search Problem
Venue: arXiv cs.DS 2017
Year: 2017

The online search problem is a fundamental problem in finance. The numerous direct applications include searching for optimal prices for commodity trading and trading foreign currencies. In this paper, we analyze the advice complexity of this problem. In particular, we are interested in identifying the minimum amount of information needed in order to achieve a certain competitive ratio. We design an algorithm that reads b bits of advice and achieves a competitive ratio of (M/m)^(1/(2^b+1)) where M and m are the maximum and minimum price in the input. We also give a matching lower bound. Furthermore, we compare the power of advice and randomization for this problem.