OpenRaiser/Intern-Atlas huggingface dataset:
The guarding game is E-complete
Venue: arXiv cs.GT 2013
Year: 2013

The guarding game is a game in which several cops try to guard a region in a (directed or undirected) graph against Robber. Robber and the cops are placed on the vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, Robber on the remaining vertices (the robber-region). The goal of Robber is to enter the guarded region at a vertex with no cop on it. The problem is to determine whether for a given graph and given number of cops the cops are able to prevent Robber from entering the guarded region. Fomin et al. [Fomin, Golovach, Hall, Mihalak, Vicari, Widmayer: How to Guard a Graph? Algorithmica 61(4), 839--856 (2011)] proved that the problem is NP-complete when the robber-region is restricted to a tree. Further they prove that is it PSPACE-complete when the robber-region is restricted to a directed acyclic graph, and they ask about the problem complexity for arbitrary graphs. In this paper we prove that the problem is E-complete for arbitrary directed graphs.
Universal Estimation of Directed Information
Venue: arXiv cs.IT 2013
Year: 2013

Four estimators of the directed information rate between a pair of jointly stationary ergodic finite-alphabet processes are proposed, based on universal probability assignments. The first one is a Shannon--McMillan--Breiman type estimator, similar to those used by Verdú (2005) and Cai, Kulkarni, and Verdú (2006) for estimation of other information measures. We show the almost sure and $L_1$ convergence properties of the estimator for any underlying universal probability assignment. The other three estimators map universal probability assignments to different functionals, each exhibiting relative merits such as smoothness, nonnegativity, and boundedness. We establish the consistency of these estimators in almost sure and $L_1$ senses, and derive near-optimal rates of convergence in the minimax sense under mild conditions. These estimators carry over directly to estimating other information measures of stationary ergodic finite-alphabet processes, such as entropy rate and mutual information rate, with near-optimal performance and provide alternatives to classical approaches in the existing literature. Guided by these theoretical results, the proposed estimators are implemented using the context-tree weighting algorithm as the universal probability assignment. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the utility of directed information estimation in detecting and measuring causal influence and delay.
A Description Logic Primer
Venue: arXiv cs.AI 2013
Year: 2013

This paper provides a self-contained first introduction to description logics (DLs). The main concepts and features are explained with examples before syntax and semantics of the DL SROIQ are defined in detail. Additional sections review light-weight DL languages, discuss the relationship to the Web Ontology Language OWL and give pointers to further reading.
Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the long-existing idea of adding a nice smooth function to "smooth" a non-differentiable objective function in the context of sparse optimization, in particular, the minimization of $||x||_1+1/(2α)||x||_2^2$, where $x$ is a vector, as well as the minimization of $||X||_*+1/(2α)||X||_F^2$, where $X$ is a matrix and $||X||_*$ and $||X||_F$ are the nuclear and Frobenius norms of $X$, respectively. We show that they can efficiently recover sparse vectors and low-rank matrices. In particular, they enjoy exact and stable recovery guarantees similar to those known for minimizing $||x||_1$ and $||X||_*$ under the conditions on the sensing operator such as its null-space property, restricted isometry property, spherical section property, or RIPless property. To recover a (nearly) sparse vector $x^0$, minimizing $||x||_1+1/(2α)||x||_2^2$ returns (nearly) the same solution as minimizing $||x||_1$ almost whenever $α\ge 10||x^0||_\infty$. The same relation also holds between minimizing $||X||_*+1/(2α)||X||_F^2$ and minimizing $||X||_*$ for recovering a (nearly) low-rank matrix $X^0$, if $α\ge 10||X^0||_2$. Furthermore, we show that the linearized Bregman algorithm for minimizing $||x||_1+1/(2α)||x||_2^2$ subject to $Ax=b$ enjoys global linear convergence as long as a nonzero solution exists, and we give an explicit rate of convergence. The convergence property does not require a solution solution or any properties on $A$. To our knowledge, this is the best known global convergence result for first-order sparse optimization algorithms.
Compact Symbolic Execution
Venue: arXiv cs.PL 2013
Year: 2013

We present a generalisation of King's symbolic execution technique called compact symbolic execution. It proceeds in two steps. First, we analyse cyclic paths in the control flow graph of a given program, independently from the rest of the program. Our goal is to compute a so called template for each such a cyclic path. A template is a declarative parametric description of all possible program states, which may leave the analysed cyclic path after any number of iterations along it. In the second step, we execute the program symbolically with the templates in hand. The result is a compact symbolic execution tree. A compact tree always carry the same information in all its leaves as the corresponding classic symbolic execution tree. Nevertheless, a compact tree is typically substantially smaller than the corresponding classic tree. There are even programs for which compact symbolic execution trees are finite while classic symbolic execution trees are infinite.
A probabilistic methodology for multilabel classification
Venue: arXiv cs.AI 2013
Year: 2013

Multilabel classification is a relatively recent subfield of machine learning. Unlike to the classical approach, where instances are labeled with only one category, in multilabel classification, an arbitrary number of categories is chosen to label an instance. Due to the problem complexity (the solution is one among an exponential number of alternatives), a very common solution (the binary method) is frequently used, learning a binary classifier for every category, and combining them all afterwards. The assumption taken in this solution is not realistic, and in this work we give examples where the decisions for all the labels are not taken independently, and thus, a supervised approach should learn those existing relationships among categories to make a better classification. Therefore, we show here a generic methodology that can improve the results obtained by a set of independent probabilistic binary classifiers, by using a combination procedure with a classifier trained on the co-occurrences of the labels. We show an exhaustive experimentation in three different standard corpora of labeled documents (Reuters-21578, Ohsumed-23 and RCV1), which present noticeable improvements in all of them, when using our methodology, in three probabilistic base classifiers.
How Web 1.0 Fails: The Mismatch Between Hyperlinks and Clickstreams
Venue: arXiv cs.IR 2013
Year: 2013

The core of the Web is a hyperlink navigation system collaboratively set up by webmasters to help users find desired websites. But does this system really work as expected? We show that the answer seems to be negative: there is a substantial mismatch between hyperlinks and the pathways that users actually take. A closer look at empirical surfing activities reveals the reason of the mismatch: webmasters try to build a global virtual world without geographical or cultural boundaries, but users in fact prefer to navigate within more fragmented, language-based groups of websites. We call this type of behavior "preferential navigation" and find that it is driven by "local" search engines.
Optimal Index Codes with Near-Extreme Rates
Venue: arXiv cs.IT 2013
Year: 2013

The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. Additionally, a new upper bound on the min-rank of a digraph, the circuit-packing bound, is presented. This bound is often tighter than the previously known bounds. By employing this new bound, we present several families of digraphs whose min-ranks can be found in polynomial time.
List decoding of repeated codes
Venue: arXiv cs.IT 2013
Year: 2013

Assuming that we have a soft-decision list decoding algorithm of a linear code, a new hard-decision list decoding algorithm of its repeated code is proposed in this article. Although repeated codes are not used for encoding data, due to their parameters, we show that they have a good performance with this algorithm. We compare, by computer simulations, our algorithm for the repeated code of a Reed-Solomon code against a decoding algorithm of a Reed-Solomon code. Finally, we estimate the decoding capability of the algorithm for Reed-Solomon codes and show that performance is somewhat better than our estimates.
Symbolic Models and Control of Discrete-Time Piecewise Affine Systems: An Approximate Simulation Approach
Venue: arXiv cs.SY 2013
Year: 2013

Symbolic models have been recently used as a sound mathematical formalism for the formal verification and control design of purely continuous and hybrid systems. In this paper we propose a sequence of symbolic models that approximates a discrete-time Piecewise Affine (PWA) system in the sense of approximate simulation and converges to the PWA system in the so-called simulation metric. Symbolic control design is then addressed with specifications expressed in terms of non-deterministic finite automata. A sequence of symbolic control strategies is derived which converges, in the sense of simulation metric, to the maximal controller solving the given specification on the PWA system.
Multi-Scale Matrix Sampling and Sublinear-Time PageRank Computation
Venue: arXiv cs.DS 2013
Year: 2013

A fundamental problem arising in many applications in Web science and social network analysis is, given an arbitrary approximation factor $c>1$, to output a set $S$ of nodes that with high probability contains all nodes of PageRank at least $Δ$, and no node of PageRank smaller than $Δ/c$. We call this problem {\sc SignificantPageRanks}. We develop a nearly optimal, local algorithm for the problem with runtime complexity $\tilde{O}(n/Δ)$ on networks with $n$ nodes. We show that any algorithm for solving this problem must have runtime of $Ω(n/Δ)$, rendering our algorithm optimal up to logarithmic factors. Our algorithm comes with two main technical contributions. The first is a multi-scale sampling scheme for a basic matrix problem that could be of interest on its own. In the abstract matrix problem it is assumed that one can access an unknown {\em right-stochastic matrix} by querying its rows, where the cost of a query and the accuracy of the answers depend on a precision parameter $ε$. At a cost propositional to $1/ε$, the query will return a list of $O(1/ε)$ entries and their indices that provide an $ε$-precision approximation of the row. Our task is to find a set that contains all columns whose sum is at least $Δ$, and omits any column whose sum is less than $Δ/c$. Our multi-scale sampling scheme solves this problem with cost $\tilde{O}(n/Δ)$, while traditional sampling algorithms would take time $Θ((n/Δ)^2)$. Our second main technical contribution is a new local algorithm for approximating personalized PageRank, which is more robust than the earlier ones developed in \cite{JehW03,AndersenCL06} and is highly efficient particularly for networks with large in-degrees or out-degrees. Together with our multiscale sampling scheme we are able to optimally solve the {\sc SignificantPageRanks} problem.
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
Venue: arXiv cs.GT 2013
Year: 2013

We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou's network. We improve upon the value 4/3 by means of Coordination Mechanisms. We increase the latency functions of the edges in the network, i.e., if $\ell_e(x)$ is the latency function of an edge $e$, we replace it by $\hat{\ell}_e(x)$ with $\ell_e(x) \le \hat{\ell}_e(x)$ for all $x$. Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if $\CM(r)$ denotes the cost of the worst Nash flow in the modified network for rate $r$ and $\Copt(r)$ denotes the cost of the optimal flow in the original network for the same rate then [\ePoA = \max_{r \ge 0} \frac{\CM(r)}{\Copt(r)}.] We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4 = 1.25. Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.
On Dynamic Distributed Computing
Venue: arXiv cs.DC 2013
Year: 2013

This paper shows for the first time that distributed computing can be both reliable and efficient in an environment that is both highly dynamic and hostile. More specifically, we show how to maintain clusters of size $O(\log N)$, each containing more than two thirds of honest nodes with high probability, within a system whose size can vary \textit{polynomially} with respect to its initial size. Furthermore, the communication cost induced by each node arrival or departure is polylogarithmic with respect to $N$, the maximal size of the system. Our clustering can be achieved despite the presence of a Byzantine adversary controlling a fraction $\bad \leq \{1}{3}-ε$ of the nodes, for some fixed constant $ε> 0$, independent of $N$. So far, such a clustering could only be performed for systems who size can vary constantly and it was not clear whether that was at all possible for polynomial variances.
Social Contagion: An Empirical Study of Information Spread on Digg and Twitter Follower Graphs
Venue: arXiv cs.SI 2013
Year: 2013

Social networks have emerged as a critical factor in information dissemination, search, marketing, expertise and influence discovery, and potentially an important tool for mobilizing people. Social media has made social networks ubiquitous, and also given researchers access to massive quantities of data for empirical analysis. These data sets offer a rich source of evidence for studying dynamics of individual and group behavior, the structure of networks and global patterns of the flow of information on them. However, in most previous studies, the structure of the underlying networks was not directly visible but had to be inferred from the flow of information from one individual to another. As a result, we do not yet understand dynamics of information spread on networks or how the structure of the network affects it. We address this gap by analyzing data from two popular social news sites. Specifically, we extract follower graphs of active Digg and Twitter users and track how interest in news stories cascades through the graph. We compare and contrast properties of information cascades on both sites and elucidate what they tell us about dynamics of information flow on networks.
Balancing Work and Size with Bounded Buffers
Venue: arXiv cs.NI 2013
Year: 2013

We consider the fundamental problem of managing a bounded size queue buffer where traffic consists of packets of varying size, where each packet requires several rounds of processing before it can be transmitted from the queue buffer. The goal in such an environment is to maximize the overall size of packets that are successfully transmitted. This model is motivated by the ever-growing ubiquity of network processors architectures, which must deal with heterogeneously-sized traffic, with heterogeneous processing requirements. Our work addresses the tension between two conflicting algorithmic approaches in such settings: the tendency to favor packets with fewer processing requirements, thus leading to fast contributions to the accumulated throughput, as opposed to preferring packets of larger size, which imply a large increase in throughput at each step. We present a model for studying such systems, and present competitive algorithms whose performance depend on the maximum size a packet may have, and maximum amount of processing a packet may require. We further provide lower bounds on algorithms performance in such settings.
The Power of Local Information in Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

We study the power of \textit{local information algorithms} for optimization problems on social networks. We focus on sequential algorithms for which the network topology is initially unknown and is revealed only within a local neighborhood of vertices that have been irrevocably added to the output set. The distinguishing feature of this setting is that locality is necessitated by constraints on the network information visible to the algorithm, rather than being desirable for reasons of efficiency or parallelizability. In this sense, changes to the level of network visibility can have a significant impact on algorithm design. We study a range of problems under this model of algorithms with local information. We first consider the case in which the underlying graph is a preferential attachment network. We show that one can find the node of maximum degree in the network in a polylogarithmic number of steps, using an opportunistic algorithm that repeatedly queries the visible node of maximum degree. This addresses an open question of Bollob{á}s and Riordan. In contrast, local information algorithms require a linear number of queries to solve the problem on arbitrary networks. Motivated by problems faced by recruiters in online networks, we also consider network coverage problems such as finding a minimum dominating set. For this optimization problem we show that, if each node added to the output set reveals sufficient information about the set's neighborhood, then it is possible to design randomized algorithms for general networks that nearly match the best approximations possible even with full access to the graph structure. We show that this level of visibility is necessary. We conclude that a network provider's decision of how much structure to make visible to its users can have a significant effect on a user's ability to interact strategically with the network.
k-Color Multi-Robot Motion Planning
Venue: arXiv cs.RO 2013
Year: 2013

We present a simple and natural extension of the multi-robot motion planning problem where the robots are partitioned into groups (colors), such that in each group the robots are interchangeable. Every robot is no longer required to move to a specific target, but rather to some target placement that is assigned to its group. We call this problem k-color multi-robot motion planning and provide a sampling-based algorithm specifically designed for solving it. At the heart of the algorithm is a novel technique where the k-color problem is reduced to several discrete multi-robot motion planning problems. These reductions amplify basic samples into massive collections of free placements and paths for the robots. We demonstrate the performance of the algorithm by an implementation for the case of disc robots and polygonal robots translating in the plane. We show that the algorithm successfully and efficiently copes with a variety of challenging scenarios, involving many robots, while a simplified version of this algorithm, that can be viewed as an extension of a prevalent sampling-based algorithm for the k-color case, fails even on simple scenarios. Interestingly, our algorithm outperforms a well established implementation of PRM for the standard multi-robot problem, in which each robot has a distinct color.
Stable image reconstruction using total variation minimization
Venue: arXiv cs.CV 2013
Year: 2013

This article presents near-optimal guarantees for accurate and robust image recovery from under-sampled noisy measurements using total variation minimization. In particular, we show that from O(slog(N)) nonadaptive linear measurements, an image can be reconstructed to within the best s-term approximation of its gradient up to a logarithmic factor, and this factor can be removed by taking slightly more measurements. Along the way, we prove a strengthened Sobolev inequality for functions lying in the null space of suitably incoherent matrices.
Performance Analysis of l_0 Norm Constraint Least Mean Square Algorithm
Venue: arXiv cs.IT 2013
Year: 2013

As one of the recently proposed algorithms for sparse system identification, $l_0$ norm constraint Least Mean Square ($l_0$-LMS) algorithm modifies the cost function of the traditional method with a penalty of tap-weight sparsity. The performance of $l_0$-LMS is quite attractive compared with its various precursors. However, there has been no detailed study of its performance. This paper presents all-around and throughout theoretical performance analysis of $l_0$-LMS for white Gaussian input data based on some reasonable assumptions. Expressions for steady-state mean square deviation (MSD) are derived and discussed with respect to algorithm parameters and system sparsity. The parameter selection rule is established for achieving the best performance. Approximated with Taylor series, the instantaneous behavior is also derived. In addition, the relationship between $l_0$-LMS and some previous arts and the sufficient conditions for $l_0$-LMS to accelerate convergence are set up. Finally, all of the theoretical results are compared with simulations and are shown to agree well in a large range of parameter setting.
Proof of Convergence and Performance Analysis for Sparse Recovery via Zero-point Attracting Projection
Venue: arXiv cs.IT 2013
Year: 2013

A recursive algorithm named Zero-point Attracting Projection (ZAP) is proposed recently for sparse signal reconstruction. Compared with the reference algorithms, ZAP demonstrates rather good performance in recovery precision and robustness. However, any theoretical analysis about the mentioned algorithm, even a proof on its convergence, is not available. In this work, a strict proof on the convergence of ZAP is provided and the condition of convergence is put forward. Based on the theoretical analysis, it is further proved that ZAP is non-biased and can approach the sparse solution to any extent, with the proper choice of step-size. Furthermore, the case of inaccurate measurements in noisy scenario is also discussed. It is proved that disturbance power linearly reduces the recovery precision, which is predictable but not preventable. The reconstruction deviation of $p$-compressible signal is also provided. Finally, numerical simulations are performed to verify the theoretical analysis.