OpenRaiser/Intern-Atlas huggingface dataset:
The Parity Hamiltonian Cycle Problem
Venue: arXiv cs.CC 2016
Year: 2016

Motivated by a relaxed notion of the celebrated Hamiltonian cycle, this paper investigates its variant, parity Hamiltonian cycle (PHC): A PHC of a graph is a closed walk which visits every vertex an odd number of times, where we remark that the walk may use an edge more than once. First, we give a complete characterization of the graphs which have PHCs, and give a linear time algorithm to find a PHC, in which every edge appears at most four times, in fact. In contrast, we show that finding a PHC is NP-hard if a closed walk is allowed to use each edge at most z times for each z=1,2,3 (PHCz for short), even when a given graph is two-edge connected. We then further investigate the PHC3 problem, and show that the problem is in P when an input graph is four-edge connected. Finally, we are concerned with three (or two)-edge connected graphs, and show that the PHC3 is in P for any C_>=5-free or P6-free graphs. Note that the Hamiltonian cycle problem is known to be NP-hard for those graph classes.
Edge Agreement of Multi-agent System with Quantized Measurements via the Directed Edge Laplacian
Venue: arXiv cs.SY 2016
Year: 2016

This work explores the edge agreement problem of second-order nonlinear multi-agent system under quantized measurements. Under the edge agreement framework, we introduce an important concept about the \emph{essential edge Laplacian} and also obtain a reduced model of the edge agreement dynamics based on the spanning tree subgraph. The quantized edge agreement problem of second-order nonlinear multi-agent system is studied, in which both uniform and logarithmic quantizers are considered. We do not only guarantee the stability of the proposed quantized control law, but also reveal the explicit mathematical connection of the quantized interval and the convergence properties for both uniform and logarithmic quantizers, which has not been addressed before. Particularly, for uniform quantizers, we provide the upper bound of the radius of the agreement neighborhood and indicate that the radius increases with the quantization interval. While for logarithmic quantizers, the agents converge exponentially to the desired agreement equilibrium. In addition, we figure out the relationship of the quantization interval and the convergence speed and also provide the estimates of the convergence rate. Finally, simulation results are given to verify the theoretical analysis.
Coordination Games on Graphs
Venue: arXiv cs.GT 2016
Year: 2016

We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and k-equilibria respectively). We show that pure Nash equilibria and 2-equilibria exist, and give an example in which no 3-equilibrium exists. Moreover, we prove that strong equilibria exist for various special cases. We also study the price of anarchy (PoA) and price of stability (PoS) for these solution concepts. We show that the PoS for strong equilibria is 1 in almost all of the special cases for which we have proven strong equilibria to exist. The PoA for pure Nash equilbria turns out to be unbounded, even when we fix the graph on which the coordination game is to be played. For the PoA for k-equilibria, we show that the price of anarchy is between 2(n-1)/(k-1) - 1 and 2(n-1)/(k-1). The latter upper bound is tight for $k=n$ (i.e., strong equilibria). Finally, we consider the problems of computing strong equilibria and of determining whether a joint strategy is a k-equilibrium or strong equilibrium. We prove that, given a coordination game, a joint strategy s, and a number k as input, it is co-NP complete to determine whether s is a k-equilibrium. On the positive side, we give polynomial time algorithms to compute strong equilibria for various special cases.
Disaggregation of Remotely Sensed Soil Moisture in Heterogeneous Landscapes using Holistic Structure based Models
Venue: arXiv cs.CV 2016
Year: 2016

In this study, a novel machine learning algorithm is presented for disaggregation of satellite soil moisture (SM) based on self-regularized regressive models (SRRM) using high-resolution correlated information from auxiliary sources. It includes regularized clustering that assigns soft memberships to each pixel at fine-scale followed by a kernel regression that computes the value of the desired variable at all pixels. Coarse-scale remotely sensed SM were disaggregated from 10km to 1km using land cover, precipitation, land surface temperature, leaf area index, and in-situ observations of SM. This algorithm was evaluated using multi-scale synthetic observations in NC Florida for heterogeneous agricultural land covers. It was found that the root mean square error (RMSE) for 96% of the pixels was less than 0.02 $m^3/m^3$. The clusters generated represented the data well and reduced the RMSE by upto 40% during periods of high heterogeneity in land-cover and meteorological conditions. The Kullback Leibler divergence (KLD) between the true SM and the disaggregated estimates is close to 0, for both vegetated and baresoil landcovers. The disaggregated estimates were compared to those generated by the Principle of Relevant Information (PRI) method. The RMSE for the PRI disaggregated estimates is higher than the RMSE for the SRRM on each day of the season. The KLD of the disaggregated estimates generated by the SRRM is at least four orders of magnitude lower than those for the PRI disaggregated estimates, while the computational time needed was reduced by three times. The results indicate that the SRRM can be used for disaggregating SM with complex non-linear correlations on a grid with high accuracy.
ECPR: Environment- and Context-aware Combined Power and Rate Distributed Congestion Control for Vehicular Communications
Venue: arXiv cs.OH 2016
Year: 2016

Safety and efficiency applications in vehicular networks rely on the exchange of periodic messages between vehicles. These messages contain position, speed, heading, and other vital information that makes the vehicles aware of their surroundings. The drawback of exchanging periodic cooperative messages is that they generate significant channel load. Decentralized Congestion Control (DCC) algorithms have been proposed to minimize the channel load. However, while the rationale for periodic message exchange is to improve awareness, existing DCC algorithms do not use awareness as a metric for deciding when, at what power, and at what rate the periodic messages need to be sent in order to make sure all vehicles are informed. We propose an environment- and context-aware DCC algorithm combines power and rate control in order to improve cooperative awareness by adapting to both specific propagation environments (e.g., urban intersections, open highways, suburban roads) as well as application requirements (e.g., different target cooperative awareness range). Studying various operational conditions (e.g., speed, direction, and application requirement), ECPR adjusts the transmit power of the messages in order to reach the desired awareness ratio at the target distance while at the same time controlling the channel load using an adaptive rate control algorithm. By performing extensive simulations, including realistic propagation as well as environment modeling and realistic vehicle operational environments (varying demand on both awareness range and rate), we show that ECPR can increase awareness by 20% while keeping the channel load and interference at almost the same level. When permitted by the awareness requirements, ECPR can improve the average message rate by 18% compared to algorithms that perform rate adaptation only.
On the Duality of Additivity and Tensorization
Venue: arXiv cs.IT 2016
Year: 2016

A function is said to be additive if, similar to mutual information, expands by a factor of $n$, when evaluated on $n$ i.i.d. repetitions of a source or channel. On the other hand, a function is said to satisfy the tensorization property if it remains unchanged when evaluated on i.i.d. repetitions. Additive rate regions are of fundamental importance in network information theory, serving as capacity regions or upper bounds thereof. Tensorizing measures of correlation have also found applications in distributed source and channel coding problems as well as the distribution simulation problem. Prior to our work only two measures of correlation, namely the hypercontractivity ribbon and maximal correlation (and their derivatives), were known to have the tensorization property. In this paper, we provide a general framework to obtain a region with the tensorization property from any additive rate region. We observe that hypercontractivity ribbon indeed comes from the dual of the rate region of the Gray-Wyner source coding problem, and generalize it to the multipartite case. Then we define other measures of correlation with similar properties from other source coding problems. We also present some applications of our results.
Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
Venue: arXiv cs.DS 2016
Year: 2016

Given an undirected, edge-weighted graph G together with pairs of vertices, called pairs of terminals, the minimum multicut problem asks for a minimum-weight set of edges such that, after deleting these edges, the two terminals of each pair belong to different connected components of the graph. Relying on topological techniques, we provide a polynomial-time algorithm for this problem in the case where G is embedded on a fixed surface of genus g (e.g., when G is planar) and has a fixed number t of terminals. The running time is a polynomial of degree O(sqrt{g^2+gt}) in the input size. In the planar case, our result corrects an error in an extended abstract by Bentz [Int. Workshop on Parameterized and Exact Computation, 109-119, 2012]. The minimum multicut problem is also a generalization of the multiway cut problem, a.k.a. multiterminal cut problem; even for this special case, no dedicated algorithm was known for graphs embedded on surfaces.
Text Understanding from Scratch
Venue: arXiv cs.LG 2016
Year: 2016

This article demontrates that we can apply deep learning to text understanding from character-level inputs all the way up to abstract text concepts, using temporal convolutional networks (ConvNets). We apply ConvNets to various large-scale datasets, including ontology classification, sentiment analysis, and text categorization. We show that temporal ConvNets can achieve astonishing performance without the knowledge of words, phrases, sentences and any other syntactic or semantic structures with regards to a human language. Evidence shows that our models can work for both English and Chinese.
Sparse Coding with Earth Mover's Distance for Multi-Instance Histogram Representation
Venue: arXiv cs.LG 2016
Year: 2016

Sparse coding (Sc) has been studied very well as a powerful data representation method. It attempts to represent the feature vector of a data sample by reconstructing it as the sparse linear combination of some basic elements, and a $L_2$ norm distance function is usually used as the loss function for the reconstruction error. In this paper, we investigate using Sc as the representation method within multi-instance learning framework, where a sample is given as a bag of instances, and further represented as a histogram of the quantized instances. We argue that for the data type of histogram, using $L_2$ norm distance is not suitable, and propose to use the earth mover's distance (EMD) instead of $L_2$ norm distance as a measure of the reconstruction error. By minimizing the EMD between the histogram of a sample and the its reconstruction from some basic histograms, a novel sparse coding method is developed, which is refereed as SC-EMD. We evaluate its performances as a histogram representation method in tow multi-instance learning problems --- abnormal image detection in wireless capsule endoscopy videos, and protein binding site retrieval. The encouraging results demonstrate the advantages of the new method over the traditional method using $L_2$ norm distance.
Planning for robotic exploration based on forward simulation
Venue: arXiv cs.RO 2016
Year: 2016

We address the problem of controlling a mobile robot to explore a partially known environment. The robot's objective is the maximization of the amount of information collected about the environment. We formulate the problem as a partially observable Markov decision process (POMDP) with an information-theoretic objective function, and solve it applying forward simulation algorithms with an open-loop approximation. We present a new sample-based approximation for mutual information useful in mobile robotics. The approximation can be seamlessly integrated with forward simulation planning algorithms. We investigate the usefulness of POMDP based planning for exploration, and to alleviate some of its weaknesses propose a combination with frontier based exploration. Experimental results in simulated and real environments show that, depending on the environment, applying POMDP based planning for exploration can improve performance over frontier exploration.
Algebraic structures of MRD Codes
Venue: arXiv cs.IT 2016
Year: 2016

Based on results in finite geometry we prove the existence of MRD codes in (F_q)_(n,n) with minimum distance n which are essentially different from Gabidulin codes. The construction results from algebraic structures which are closely related to those of finite fields. Some of the results may be known to experts, but to our knowledge have never been pointed out explicitly in the literature.
A Proof of the Strong Converse Theorem for Gaussian Multiple Access Channels
Venue: arXiv cs.IT 2016
Year: 2016

We prove the strong converse for the $N$-source Gaussian multiple access channel (MAC). In particular, we show that any rate tuple that can be supported by a sequence of codes with asymptotic average error probability less than one must lie in the Cover-Wyner capacity region. Our proof consists of the following. First, we perform an expurgation step to convert any given sequence of codes with asymptotic average error probability less than one to codes with asymptotic maximal error probability less than one. Second, we quantize the input alphabets with an appropriately chosen resolution. Upon quantization, we apply the wringing technique (by Ahlswede) on the quantized inputs to obtain further subcodes from the subcodes obtained in the expurgation step so that the resultant correlations among the symbols transmitted by the different sources vanish as the blocklength grows. Finally, we derive upper bounds on achievable sum-rates of the subcodes in terms of the type-II error of a binary hypothesis test. These upper bounds are then simplified through judicious choices of auxiliary output distributions. Our strong converse result carries over to the Gaussian interference channel under strong interference as long as the sum of the two asymptotic average error probabilities less than one.
From Closed-world Enforcement to Open-world Assessment of Privacy
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, we develop a user-centric privacy framework for quantitatively assessing the exposure of personal information in open settings. Our formalization addresses key-challenges posed by such open settings, such as the unstructured dissemination of heterogeneous information and the necessity of user- and context-dependent privacy requirements. We propose a new definition of information sensitivity derived from our formalization of privacy requirements, and, as a sanity check, show that hard non-disclosure guarantees are impossible to achieve in open settings. After that, we provide an instantiation of our framework to address the identity disclosure problem, leading to the novel notion of d-convergence. d-convergence is based on indistinguishability of entities and it bounds the likelihood with which an adversary successfully links two profiles of the same user across online communities. Finally, we provide a large-scale evaluation of our framework on a collection of 15 million comments collected from the Online Social Network Reddit. Our evaluation validates the notion of d-convergence for assessing the linkability of entities in our data set and provides deeper insights into the data set's structure.
Don't Trust the Cloud, Verify: Integrity and Consistency for Cloud Object Stores
Venue: arXiv cs.DC 2016
Year: 2016

Cloud services have turned remote computation into a commodity and enable convenient online collaboration. However, they require that clients fully trust the service provider in terms of confidentiality, integrity, and availability. Towards reducing this dependency, this paper introduces a protocol for verification of integrity and consistency for cloud object storage (VICOS), which enables a group of mutually trusting clients to detect data-integrity and consistency violations for a cloud object-storage service. It aims at services where multiple clients cooperate on data stored remotely on a potentially misbehaving service. VICOS enforces the consistency notion of fork-linearizability, supports wait-free client semantics for most operations, and reduces the computation and communication overhead compared to previous protocols. VICOS is based in a generic way on any authenticated data structure. Moreover, its operations cover the hierarchical name space of a cloud object store, supporting a real-world interface and not only a simplistic abstraction. A prototype of VICOS that works with the key-value store interface of commodity cloud storage services has been implemented, and an evaluation demonstrates its advantage compared to existing systems.
Noisy Channel-Output Feedback Capacity of the Linear Deterministic Interference Channel
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, the capacity region of the two-user linear deterministic (LD) interference channel with noisy output feedback (IC-NOF) is fully characterized. This result allows the identification of several asymmetric scenarios in which imple- menting channel-output feedback in only one of the transmitter- receiver pairs is as beneficial as implementing it in both links, in terms of achievable individual rate and sum-rate improvements w.r.t. the case without feedback. In other scenarios, the use of channel-output feedback in any of the transmitter-receiver pairs benefits only one of the two pairs in terms of achievable individual rate improvements or simply, it turns out to be useless, i.e., the capacity regions with and without feedback turn out to be identical even in the full absence of noise in the feedback links.
Unsupervised Learning of Video Representations using LSTMs
Venue: arXiv cs.LG 2016
Year: 2016

We use multilayer Long Short Term Memory (LSTM) networks to learn representations of video sequences. Our model uses an encoder LSTM to map an input sequence into a fixed length representation. This representation is decoded using single or multiple decoder LSTMs to perform different tasks, such as reconstructing the input sequence, or predicting the future sequence. We experiment with two kinds of input sequences - patches of image pixels and high-level representations ("percepts") of video frames extracted using a pretrained convolutional net. We explore different design choices such as whether the decoder LSTMs should condition on the generated output. We analyze the outputs of the model qualitatively to see how well the model can extrapolate the learned video representation into the future and into the past. We try to visualize and interpret the learned features. We stress test the model by running it on longer time scales and on out-of-domain data. We further evaluate the representations by finetuning them for a supervised learning problem - human action recognition on the UCF-101 and HMDB-51 datasets. We show that the representations help improve classification accuracy, especially when there are only a few training examples. Even models pretrained on unrelated datasets (300 hours of YouTube videos) can help action recognition performance.
A Survey of Word Reordering in Statistical Machine Translation: Computational Models and Language Phenomena
Venue: arXiv cs.CL 2016
Year: 2016

Word reordering is one of the most difficult aspects of statistical machine translation (SMT), and an important factor of its quality and efficiency. Despite the vast amount of research published to date, the interest of the community in this problem has not decreased, and no single method appears to be strongly dominant across language pairs. Instead, the choice of the optimal approach for a new translation task still seems to be mostly driven by empirical trials. To orientate the reader in this vast and complex research area, we present a comprehensive survey of word reordering viewed as a statistical modeling challenge and as a natural language phenomenon. The survey describes in detail how word reordering is modeled within different string-based and tree-based SMT frameworks and as a stand-alone task, including systematic overviews of the literature in advanced reordering modeling. We then question why some approaches are more successful than others in different language pairs. We argue that, besides measuring the amount of reordering, it is important to understand which kinds of reordering occur in a given language pair. To this end, we conduct a qualitative analysis of word reordering phenomena in a diverse sample of language pairs, based on a large collection of linguistic knowledge. Empirical results in the SMT literature are shown to support the hypothesis that a few linguistic facts can be very useful to anticipate the reordering characteristics of a language pair and to select the SMT framework that best suits them.
Simple Recognition of Halin Graphs and Their Generalizations
Venue: arXiv cs.DS 2016
Year: 2016

We describe and implement two local reduction rules that can be used to recognize Halin graphs in linear time, avoiding the complicated planarity testing step of previous linear time Halin graph recognition algorithms. The same two rules can be used as the basis for linear-time algorithms for other algorithmic problems on Halin graphs, including decomposing these graphs into a tree and a cycle, finding a Hamiltonian cycle, or constructing a planar embedding. These reduction rules can also be used to recognize a broader class of polyhedral graphs. These graphs, which we call the D3-reducible graphs, are the dual graphs of the polyhedra formed by gluing pyramids together on their triangular faces; their treewidth is bounded, and they necessarily have Lombardi drawings.
Planar Linkages Following a Prescribed Motion
Venue: arXiv cs.SC 2016
Year: 2016

Designing mechanical devices, called linkages, that draw a given plane curve has been a topic that interested engineers and mathematicians for hundreds of years, and recently also computer scientists. Already in 1876, Kempe proposed a procedure for solving the problem in full generality, but his constructions tend to be extremely complicated. We provide a novel algorithm that produces much simpler linkages, but works only for parametric curves. Our approach is to transform the problem into a factorization task over some noncommutative algebra. We show how to compute such a factorization, and how to use it to construct a linkage tracing a given curve.