OpenRaiser/Intern-Atlas huggingface dataset:
Counting $4\times 4$ Matrix Partitions of Graphs
Venue: arXiv cs.CC 2016
Year: 2016

Given a symmetric matrix $M\in \{0,1,*\}^{D\times D}$, an $M$-partition of a graph $G$ is a function from $V(G)$ to $D$ such that no edge of $G$ is mapped to a $0$ of $M$ and no non-edge to a $1$. We give a computer-assisted proof that, when $|D|=4$, the problem of counting the $M$-partitions of an input graph is either in FP or is #P-complete. Tractability is proved by reduction to the related problem of counting list $M$-partitions; intractability is shown using a gadget construction and interpolation. We use a computer program to determine which of the two cases holds for all but a small number of matrices, which we resolve manually to establish the dichotomy. We conjecture that the dichotomy also holds for $|D|>4$. More specifically, we conjecture that, for any symmetric matrix $M\in\{0,1,*\}^{D\times D}$, the complexity of counting $M$-partitions is the same as the related problem of counting list $M$-partitions.
Gaussian Multiple Access via Compute-and-Forward
Venue: arXiv cs.IT 2016
Year: 2016

Lattice codes used under the Compute-and-Forward paradigm suggest an alternative strategy for the standard Gaussian multiple-access channel (MAC): The receiver successively decodes integer linear combinations of the messages until it can invert and recover all messages. In this paper, a multiple-access technique called CFMA (Compute-Forward Multiple Access) is proposed and analyzed. For the two-user MAC, it is shown that without time-sharing, the entire capacity region can be attained using CFMA with a single-user decoder as soon as the signal-to-noise ratios are above $1+\sqrt{2}$. A partial analysis is given for more than two users. Lastly the strategy is extended to the so-called dirty MAC where two interfering signals are known non-causally to the two transmitters in a distributed fashion. Our scheme extends the previously known results and gives new achievable rate regions.
Traffic Network Control from Temporal Logic Specifications
Venue: arXiv cs.SY 2016
Year: 2016

We propose a framework for generating a signal control policy for a traffic network of signalized intersections to accomplish control objectives expressible using linear temporal logic. By applying techniques from model checking and formal methods, we obtain a correct-by-construction controller that is guaranteed to satisfy complex specifications. To apply these tools, we identify and exploit structural properties particular to traffic networks that allow for efficient computation of a finite state abstraction. In particular, traffic networks exhibit a componentwise monotonicity property which allows reach set computations that scale linearly with the dimension of the continuous state space.
Motion Deblurring for Plenoptic Images
Venue: arXiv cs.CV 2016
Year: 2016

We address for the first time the issue of motion blur in light field images captured from plenoptic cameras. We propose a solution to the estimation of a sharp high resolution scene radiance given a blurry light field image, when the motion blur point spread function is unknown, i.e., the so-called blind deconvolution problem. In a plenoptic camera, the spatial sampling in each view is not only decimated but also defocused. Consequently, current blind deconvolution approaches for traditional cameras are not applicable. Due to the complexity of the imaging model, we investigate first the case of uniform (shift-invariant) blur of Lambertian objects, i.e., when objects are sufficiently far away from the camera to be approximately invariant to depth changes and their reflectance does not vary with the viewing direction. We introduce a highly parallelizable model for light field motion blur that is computationally and memory efficient. We then adapt a regularized blind deconvolution approach to our model and demonstrate its performance on both synthetic and real light field data. Our method handles practical issues in real cameras such as radial distortion correction and alignment within an energy minimization framework.
Fast Shortest Path Routing in Transportation Networks with Time-Dependent Road Speeds
Venue: arXiv cs.DS 2016
Year: 2016

The current paper deals with the subject of shortest path routing in transportation networks (in terms of travelling time), where the speed in several of the network's roads is a function of the time interval. The main contribution of the paper is a procedure that is faster compared to the conventional approaches, that derives the road's traversal time according to the time instant of departure, for the case where the road's speed has a constant value inside each time interval (in general, different value for each time interval). Furthermore, the case where the road's speed is a linear function of time inside each time interval (in general, different linear function for each time interval) is investigated. A procedure that derives the road's traversal time according to the time instant of departure is proposed for this case as well. The proposed procedures are combined with Dijkstra's algorithm and the resulting algorithms, that are practically applicable and of low complexity, provide optimal shortest path routing in the networks under investigation.
GSPBOX: A toolbox for signal processing on graphs
Venue: arXiv cs.IT 2016
Year: 2016

This document introduces the Graph Signal Processing Toolbox (GSPBox) a framework that can be used to tackle graph related problems with a signal processing approach. It explains the structure and the organization of this software. It also contains a general description of the important modules.
Neural Machine Translation by Jointly Learning to Align and Translate
Venue: arXiv cs.CL 2016
Year: 2016

Neural machine translation is a recently proposed approach to machine translation. Unlike the traditional statistical machine translation, the neural machine translation aims at building a single neural network that can be jointly tuned to maximize the translation performance. The models proposed recently for neural machine translation often belong to a family of encoder-decoders and consists of an encoder that encodes a source sentence into a fixed-length vector from which a decoder generates a translation. In this paper, we conjecture that the use of a fixed-length vector is a bottleneck in improving the performance of this basic encoder-decoder architecture, and propose to extend this by allowing a model to automatically (soft-)search for parts of a source sentence that are relevant to predicting a target word, without having to form these parts as a hard segment explicitly. With this new approach, we achieve a translation performance comparable to the existing state-of-the-art phrase-based system on the task of English-to-French translation. Furthermore, qualitative analysis reveals that the (soft-)alignments found by the model agree well with our intuition.
Message Encoding and Retrieval for Spread and Cyclic Orbit Codes
Venue: arXiv cs.IT 2016
Year: 2016

Spread codes and cyclic orbit codes are special families of constant dimension subspace codes. These codes have been well-studied for their error correction capability, transmission rate and decoding methods, but the question of how to encode and retrieve messages has not been investigated. In this work we show how a message set of consecutive integers can be encoded and retrieved for these two code families.
When coding meets ranking: A joint framework based on local learning
Venue: arXiv cs.CV 2016
Year: 2016

Sparse coding, which represents a data point as a sparse reconstruction code with regard to a dictionary, has been a popular data representation method. Meanwhile, in database retrieval problems, learning the ranking scores from data points plays an important role. Up to now, these two problems have always been considered separately, assuming that data coding and ranking are two independent and irrelevant problems. However, is there any internal relationship between sparse coding and ranking score learning? If yes, how to explore and make use of this internal relationship? In this paper, we try to answer these questions by developing the first joint sparse coding and ranking score learning algorithm. To explore the local distribution in the sparse code space, and also to bridge coding and ranking problems, we assume that in the neighborhood of each data point, the ranking scores can be approximated from the corresponding sparse codes by a local linear function. By considering the local approximation error of ranking scores, the reconstruction error and sparsity of sparse coding, and the query information provided by the user, we construct a unified objective function for learning of sparse codes, the dictionary and ranking scores. We further develop an iterative algorithm to solve this optimization problem.
Imperfect-Recall Abstractions with Bounds in Games
Venue: arXiv cs.GT 2016
Year: 2016

Imperfect-recall abstraction has emerged as the leading paradigm for practical large-scale equilibrium computation in incomplete-information games. However, imperfect-recall abstractions are poorly understood, and only weak algorithm-specific guarantees on solution quality are known. In this paper, we show the first general, algorithm-agnostic, solution quality guarantees for Nash equilibria and approximate self-trembling equilibria computed in imperfect-recall abstractions, when implemented in the original (perfect-recall) game. Our results are for a class of games that generalizes the only previously known class of imperfect-recall abstractions where any results had been obtained. Further, our analysis is tighter in two ways, each of which can lead to an exponential reduction in the solution quality error bound. We then show that for extensive-form games that satisfy certain properties, the problem of computing a bound-minimizing abstraction for a single level of the game reduces to a clustering problem, where the increase in our bound is the distance function. This reduction leads to the first imperfect-recall abstraction algorithm with solution quality bounds. We proceed to show a divide in the class of abstraction problems. If payoffs are at the same scale at all information sets considered for abstraction, the input forms a metric space. Conversely, if this condition is not satisfied, we show that the input does not form a metric space. Finally, we use these results to experimentally investigate the quality of our bound for single-level abstraction.
Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume
Venue: arXiv cs.DS 2016
Year: 2016

We present an $O^*(n^3)$ randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of $O^*(n^4)$. The new algorithmic ingredient is an accelerated cooling schedule where the rate of cooling increases with the temperature. Previously, the known approach for potentially achieving this asymptotic complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry. We also obtain an $O^*(n^3)$ randomized algorithm for integrating a standard Gaussian distribution over an arbitrary convex set containing the unit ball. Both the volume and Gaussian volume algorithms use an improved algorithm for sampling a Gaussian distribution restricted to a convex body. In this latter setting, as we show, the KLS conjecture holds and for a spherical Gaussian distribution with variance $σ^2$, the sampling complexity is $O^*(\max\{n^3, σ^2n^2\})$ for the first sample and $O^*(\max\{n^2, σ^2n^2\})$ for every subsequent sample.
The meaning-frequency law in Zipfian optimization models of communication
Venue: arXiv cs.CL 2016
Year: 2016

According to Zipf's meaning-frequency law, words that are more frequent tend to have more meanings. Here it is shown that a linear dependency between the frequency of a form and its number of meanings is found in a family of models of Zipf's law for word frequencies. This is evidence for a weak version of the meaning-frequency law. Interestingly, that weak law (a) is not an inevitable of property of the assumptions of the family and (b) is found at least in the narrow regime where those models exhibit Zipf's law for word frequencies.
Online Ranking with Top-1 Feedback
Venue: arXiv cs.LG 2016
Year: 2016

We consider a setting where a system learns to rank a fixed set of $m$ items. The goal is produce good item rankings for users with diverse interests who interact online with the system for $T$ rounds. We consider a novel top-$1$ feedback model: at the end of each round, the relevance score for only the top ranked object is revealed. However, the performance of the system is judged on the entire ranked list. We provide a comprehensive set of results regarding learnability under this challenging setting. For PairwiseLoss and DCG, two popular ranking measures, we prove that the minimax regret is $Θ(T^{2/3})$. Moreover, the minimax regret is achievable using an efficient strategy that only spends $O(m \log m)$ time per round. The same efficient strategy achieves $O(T^{2/3})$ regret for Precision@$k$. Surprisingly, we show that for normalized versions of these ranking measures, i.e., AUC, NDCG \& MAP, no online ranking algorithm can have sublinear regret.
MoonGen: A Scriptable High-Speed Packet Generator
Venue: arXiv cs.NI 2016
Year: 2016

We present MoonGen, a flexible high-speed packet generator. It can saturate 10 GbE links with minimum sized packets using only a single CPU core by running on top of the packet processing framework DPDK. Linear multi-core scaling allows for even higher rates: We have tested MoonGen with up to 178.5 Mpps at 120 Gbit/s. We move the whole packet generation logic into user-controlled Lua scripts to achieve the highest possible flexibility. In addition, we utilize hardware features of Intel NICs that have not been used for packet generators previously. A key feature is the measurement of latency with sub-microsecond precision and accuracy by using hardware timestamping capabilities of modern commodity NICs. We address timing issues with software-based packet generators and apply methods to mitigate them with both hardware support on commodity NICs and with a novel method to control the inter-packet gap in software. Features that were previously only possible with hardware-based solutions are now provided by MoonGen on commodity hardware. MoonGen is available as free software under the MIT license at https://github.com/emmericp/MoonGen
Scaling in bidirectional platoons with dynamic controllers and proportional asymmetry
Venue: arXiv cs.SY 2016
Year: 2016

We consider platoons composed of identical vehicles with an asymmetric nearest-neighbor interaction. We restrict ourselves to intervehicular coupling realized with dynamic arbitrary-order onboard controllers such that the coupling to the immediately preceding vehicle is proportional to the coupling to the immediately following vehicle. Each vehicle is modeled using a transfer function and we impose no restriction on the order of the vehicle. The platoon is described by a transfer function in a convenient product form. We investigate how the H-infinity norm and the steady-state gain of the platoon scale with the number of vehicles. We conclude that if the open-loop transfer function of the vehicle contains two or more integrators and the Fiedler eigenvalue of the graph Laplacian is uniformly bounded from below, the norm scales exponentially with the growing distance in the graph. If there is just one integrator in the open loop, we give a condition under which the norm of the transfer function is bounded by its steady-state gain - the platoon is string-stable. Moreover, we argue that in this case it is always possible to design a controller the predecessor following strategy.
The Feasibility of Interference Alignment for Reverse TDD Systems in MIMO Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

The feasibility conditions of interference alignment (IA) are analyzed for reverse TDD systems, i.e., one cell operates as downlink (DL) but the other cell operates as uplink (UL). Under general multiple-input and multiple-output (MIMO) antenna configurations, a necessary condition and a sufficient condition for one-shot linear IA are established, i.e., linear IA without symbol or time extension. In several example networks, optimal sum degrees of freedom (DoF) is characterized by the derived necessary condition and sufficient condition. For symmetric DoF within each cell, a sufficient condition is established in a more compact expression, which yields the necessary and sufficient condition for a class of symmetric DoF. An iterative construction of transmit and received beamforming vectors is further proposed, which provides a specific beamforming design satisfying one-shot IA. Simulation results demonstrate that the proposed IA not only achieve lager DoF but also significantly improve the sum rate in the practical signal-to-noise ratio (SNR) regime.
Prediction of "Forwarding Whom" Behavior in Information Diffusion
Venue: arXiv cs.SI 2016
Year: 2016

Follow-ship network among users underlies the diffusion dynamics of messages on online social networks. Generally, the structure of underlying social network determines the visibility of messages and the diffusion process. In this paper, we study forwarding behavior of individuals, taking Sina Weibo as an example. We investigate multiple exposures in information diffusion and the "forwarding whom" problem associated with multiple exposures. Finally, we model and predict the "forwarding whom" behavior of individuals, combining structural, temporal, historical, and content features. Experimental results demonstrate that our method achieves a high accuracy 91.3%.
Multi-Class Source-Channel Coding
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases.
Multi-Cell Processing with Limited Cooperation: A Novel Framework to Timely Designs and Reduced CSI Feedback with General Inputs
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the optimal power allocation and optimal precoding for a multi-cell-processing (MCP) framework with limited cooperation. In particular, we consider two base stations(BSs) which maximize the achievable rate for two users connecting to each BS and sharing channel state information (CSI). We propose a two way channel estimation or prediction process. Such framework has promising outcomes in terms of feedback reduction and acheivable rates moving the system from one with unkown CSI at the transmitter to a system with instantanous CSI at both sides of the communication. We derive new extentions of the fundamental relation between the gradient of the mutual information and the MMSE for the conditional and non-conditional mutual information. Capitalizing on such relations, we provide the optimal power allocation and optimal precoding designs with respect to the estimated channel and MMSE. The designs introduced are optimal for multiple access (MAC) Gaussian coherent time-varying fading channels with general inputs and can be specialized to multiple input multiple output (MIMO) channels by decoding interference. The impact of interference on the capacity is quantified by the gradient of the mutual information with respect to the power, channel, and error covariance of the interferer. We provide two novel distributed MCP algorithms that provide the solutions for the optimal power allocation and optimal precoding for the UL and DL with a two way channel estimation to keep track of the channel variations over blocks of data transmission. Therefore, we provide a novel solution that allows with limited cooperation: a significant reduction in the CSI feedback from the receiver to the transmitter, and timely optimal designs of the precoding and power allocation.
Are you going to the party: depends, who else is coming? [Learning hidden group dynamics via conditional latent tree models]
Venue: arXiv cs.SI 2016
Year: 2016

Scalable probabilistic modeling and prediction in high dimensional multivariate time-series is a challenging problem, particularly for systems with hidden sources of dependence and/or homogeneity. Examples of such problems include dynamic social networks with co-evolving nodes and edges and dynamic student learning in online courses. Here, we address these problems through the discovery of hierarchical latent groups. We introduce a family of Conditional Latent Tree Models (CLTM), in which tree-structured latent variables incorporate the unknown groups. The latent tree itself is conditioned on observed covariates such as seasonality, historical activity, and node attributes. We propose a statistically efficient framework for learning both the hierarchical tree structure and the parameters of the CLTM. We demonstrate competitive performance in multiple real world datasets from different domains. These include a dataset on students' attempts at answering questions in a psychology MOOC, Twitter users participating in an emergency management discussion and interacting with one another, and windsurfers interacting on a beach in Southern California. In addition, our modeling framework provides valuable and interpretable information about the hidden group structures and their effect on the evolution of the time series.
Patterns in the Chaos - a Study of Performance Variation and Predictability in Public IaaS Clouds
Venue: arXiv cs.DC 2016
Year: 2016

Benchmarking the performance of public cloud providers is a common research topic. Previous research has already extensively evaluated the performance of different cloud platforms for different use cases, and under different constraints and experiment setups. In this paper, we present a principled, large-scale literature review to collect and codify existing research regarding the predictability of performance in public Infrastructure-as-a-Service (IaaS) clouds. We formulate 15 hypotheses relating to the nature of performance variations in IaaS systems, to the factors of influence of performance variations, and how to compare different instance types. In a second step, we conduct extensive real-life experimentation on Amazon EC2 and Google Compute Engine to empirically validate those hypotheses. At the time of our research, performance in EC2 was substantially less predictable than in GCE. Further, we show that hardware heterogeneity is in practice less prevalent than anticipated by earlier research, while multi-tenancy has a dramatic impact on performance and predictability.