OpenRaiser/Intern-Atlas huggingface dataset:
Kernelization and Sparseness: the case of Dominating Set
Venue: arXiv cs.DS 2015
Year: 2015

We prove that for every positive integer $r$ and for every graph class $\mathcal G$ of bounded expansion, the $r$-Dominating Set problem admits a linear kernel on graphs from $\mathcal G$. Moreover, when $\mathcal G$ is only assumed to be nowhere dense, then we give an almost linear kernel on $\mathcal G$ for the classic Dominating Set problem, i.e., for the case $r=1$. These results generalize a line of previous research on finding linear kernels for Dominating Set and $r$-Dominating Set. However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related Connected Dominating Set problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on $H$-topological-minor-free graphs. Also, we prove that for any somewhere dense class $\mathcal G$, there is some $r$ for which $r$-Dominating Set is W[$2$]-hard on $\mathcal G$. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of $r$-Dominating Set on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.
Survey of End-to-End Mobile Network Measurement Testbeds, Tools, and Services
Venue: arXiv cs.NI 2015
Year: 2015

Mobile (cellular) networks enable innovation, but can also stifle it and lead to user frustration when network performance falls below expectations. As mobile networks become the predominant method of Internet access, developer, research, network operator, and regulatory communities have taken an increased interest in measuring end-to-end mobile network performance to, among other goals, minimize negative impact on application responsiveness. In this survey we examine current approaches to end-to-end mobile network performance measurement, diagnosis, and application prototyping. We compare available tools and their shortcomings with respect to the needs of researchers, developers, regulators, and the public. We intend for this survey to provide a comprehensive view of currently active efforts and some auspicious directions for future work in mobile network measurement and mobile application performance evaluation.
I Always Feel Like Somebody's Watching Me. Measuring Online Behavioural Advertising
Venue: arXiv cs.CY 2015
Year: 2015

Online Behavioural targeted Advertising (OBA) has risen in prominence as a method to increase the effectiveness of online advertising. OBA operates by associating tags or labels to users based on their online activity and then using these labels to target them. This rise has been accompanied by privacy concerns from researchers, regulators and the press. In this paper, we present a novel methodology for measuring and understanding OBA in the online advertising market. We rely on training artificial online personas representing behavioural traits like 'cooking', 'movies', 'motor sports', etc. and build a measurement system that is automated, scalable and supports testing of multiple configurations. We observe that OBA is a frequent practice and notice that categories valued more by advertisers are more intensely targeted. In addition, we provide evidences showing that the advertising market targets sensitive topics (e.g, religion or health) despite the existence of regulation that bans such practices. We also compare the volume of OBA advertising for our personas in two different geographical locations (US and Spain) and see little geographic bias in terms of intensity of OBA targeting. Finally, we check for targeting with do-not-track (DNT) enabled and discovered that DNT is not yet enforced in the web.
Global Practical Node and Edge Synchronization in Kuramoto Networks: A Submodular Optimization Framework
Venue: arXiv cs.SY 2015
Year: 2015

Synchronization underlies phenomena including memory and perception in the brain, coordinated motion of animal flocks, and stability of the power grid. These synchronization phenomena are often modeled through networks of phase-coupled oscillating nodes. Heterogeneity in the node dynamics, however, may prevent such networks from achieving the required level of synchronization. In order to guarantee synchronization, external inputs can be used to pin a subset of nodes to a reference frequency, while the remaining nodes are steered toward synchronization via local coupling. In this paper, we present a submodular optimization framework for selecting a set of nodes to act as external inputs in order to achieve synchronization from almost any initial network state. We derive threshold-based sufficient conditions for synchronization, and then prove that these conditions are equivalent to connectivity of a class of augmented network graphs. Based on this connection, we map the sufficient conditions for synchronization to constraints on submodular functions, leading to efficient algorithms with provable optimality bounds for selecting input nodes. We illustrate our approach via numerical studies of synchronization in networks from power systems, wireless networks, and neuronal networks.
Planar Reachability in Linear Space and Constant Time
Venue: arXiv cs.DS 2015
Year: 2015

We show how to represent a planar digraph in linear space so that distance queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reachability is thus optimal in both time and space, and has optimal construction time. The previous best solution used $O(n\log n)$ space for constant query time [Thorup FOCS'01].
Optimal Encodings for Range Top-k, Selection, and Min-Max
Venue: arXiv cs.DS 2015
Year: 2015

We consider encoding problems for range queries on arrays. In these problems the goal is to store a structure capable of recovering the answer to all queries that occupies the information theoretic minimum space possible, to within lower order terms. As input, we are given an array $A[1..n]$, and a fixed parameter $k \in [1,n]$. A range top-$k$ query on an arbitrary range $[i,j] \subseteq [1,n]$ asks us to return the ordered set of indices $\{\ell_1, ..., \ell_{k}\}$ such that $A[\ell_m]$ is the $m$-th largest element in $A[i..j]$, for $1 \le m \le k$. A range selection query for an arbitrary range $[i,j] \subseteq [1,n]$ and query parameter $k' \in [1,k]$ asks us to return the index of the $k'$-th largest element in $A[i..j]$. We completely resolve the space complexity of both of these heavily studied problems---to within lower order terms---for all $k = o(n)$. Previously, the constant factor in the space complexity was known only for $k=1$. We also resolve the space complexity of another problem, that we call range min-max, in which the goal is to return the indices of both the minimum and maximum elements in a range.
Kernelization Algorithms for Packing Problems Allowing Overlaps (Extended Version)
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of discovering overlapping communities in networks which we model as generalizations of Graph Packing problems with overlap. We seek a collection $\mathcal{S}' \subseteq \mathcal{S}$ consisting of at least $k$ sets subject to certain disjointness restrictions. In the $r$-Set Packing with $t$-Membership, each element of $\mathcal{U}$ belongs to at most $t$ sets of $\mathcal{S'}$ while in $t$-Overlap each pair of sets in $\mathcal{S'}$ overlaps in at most $t$ elements. Each set of $\mathcal{S}$ has at most $r$ elements. Similarly, both of our graph packing problems seek a collection $\mathcal{K}$ of at least $k$ subgraphs in a graph $G$ each isomorphic to a graph $H \in \mathcal{H}$. In $\mathcal{H}$-Packing with $t$-Membership, each vertex of $G$ belongs to at most $t$ subgraphs of $\mathcal{K}$ while in $t$-Overlap each pair of subgraphs in $\mathcal{K}$ overlaps in at most $t$ vertices. Each member of $\mathcal{H}$ has at most $r$ vertices and $m$ edges. We show NP-Completeness results for all of our packing problems and we give a dichotomy result for the $\mathcal{H}$-Packing with $t$-Membership problem analogous to the Kirkpatrick and Hell \cite{Kirk78}. We reduce the $r$-Set Packing with $t$-Membership to a problem kernel with $O((r+1)^r k^{r})$ elements while we achieve a kernel with $O(r^r k^{r-t-1})$ elements for the $r$-Set Packing with $t$-Overlap. In addition, we reduce the $\mathcal{H}$-Packing with $t$-Membership and its edge version to problem kernels with $O((r+1)^r k^{r})$ and $O((m+1)^{m} k^{m})$ vertices, respectively. On the other hand, we achieve kernels with $O(r^r k^{r-t-1})$ and $O(m^{m} k^{m-t-1})$ vertices for the $\mathcal{H}$-Packing with $t$-Overlap and its edge version, respectively. In all cases, $k$ is the input parameter while $t$, $r$, and $m$ are constants.
Post-acquisition image based compensation for thickness variation in microscopy section series
Venue: arXiv cs.CV 2015
Year: 2015

Serial section Microscopy is an established method for volumetric anatomy reconstruction. Section series imaged with Electron Microscopy are currently vital for the reconstruction of the synaptic connectivity of entire animal brains such as that of Drosophila melanogaster. The process of removing ultrathin layers from a solid block containing the specimen, however, is a fragile procedure and has limited precision with respect to section thickness. We have developed a method to estimate the relative z-position of each individual section as a function of signal change across the section series. First experiments show promising results on both serial section Transmission Electron Microscopy (ssTEM) data and Focused Ion Beam Scanning Electron Microscopy (FIB-SEM) series. We made our solution available as Open Source plugins for the TrakEM2 software and the ImageJ distribution Fiji.
Analyzing the BrowserID SSO System with Primary Identity Providers Using an Expressive Model of the Web
Venue: arXiv cs.CR 2015
Year: 2015

BrowserID is a complex, real-world Single Sign-On (SSO) System for web applications recently developed by Mozilla. It employs new HTML5 features (such as web messaging and web storage) and cryptographic assertions to provide decentralized login, with the intent to respect users' privacy. It can operate in a primary and a secondary identity provider mode. While in the primary mode BrowserID runs with arbitrary identity providers (IdPs), in the secondary mode there is one IdP only, namely Mozilla's default IdP. We recently proposed an expressive general model for the web infrastructure and, based on this web model, analyzed the security of the secondary IdP mode of BrowserID. The analysis revealed several severe vulnerabilities. In this paper, we complement our prior work by analyzing the even more complex primary IdP mode of BrowserID. We do not only study authentication properties as before, but also privacy properties. During our analysis we discovered new and practical attacks that do not apply to the secondary mode: an identity injection attack, which violates a central authentication property of SSO systems, and attacks that break an important privacy promise of BrowserID and which do not seem to be fixable without a major redesign of the system. Some of our attacks on privacy make use of a browser side channel that has not gained a lot of attention so far. For the authentication bug, we propose a fix and formally prove in a slight extension of our general web model that the fixed system satisfies all the requirements we consider. This constitutes the most complex formal analysis of a web application based on an expressive model of the web infrastructure so far. As another contribution, we identify and prove important security properties of generic web features in the extended web model to facilitate future analysis efforts of web standards and web applications.
Signal Recovery on Graphs: Variation Minimization
Venue: arXiv cs.SI 2015
Year: 2015

We consider the problem of signal recovery on graphs as graphs model data with complex structure as signals on a graph. Graph signal recovery implies recovery of one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We propose a graph signal model and formulate signal recovery as a corresponding optimization problem. We provide a general solution by using the alternating direction methods of multipliers. We next show how signal inpainting, matrix completion, robust principal component analysis, and anomaly detection all relate to graph signal recovery, and provide corresponding specific solutions and theoretical analysis. Finally, we validate the proposed methods on real-world recovery problems, including online blog classification, bridge condition identification, temperature estimation, recommender system, and expert opinion combination of online blog classification.
Uniformity of point samples in metric spaces using gap ratio
Venue: arXiv cs.CG 2015
Year: 2015

Teramoto et al. defined a new measure called the gap ratio that measures the uniformity of a finite point set sampled from $\cal S$, a bounded subset of $\mathbb{R}^2$. We generalize this definition of measure over all metric spaces by appealing to covering and packing radius. The definition of gap ratio needs only a metric unlike discrepancy, a widely used uniformity measure, that depends on the notion of a range space and its volume. We also show some interesting connections of gap ratio to Delaunay triangulation and discrepancy in the Euclidean plane. The major focus of this work is on solving optimization related questions about selecting uniform point samples from metric spaces; the uniformity being measured using gap ratio. We consider discrete spaces like graph and set of points in the Euclidean space and continuous spaces like the unit square and path connected spaces. We deduce lower bounds, prove hardness and approximation hardness results. We show that a general approximation algorithm framework gives different approximation ratios for different metric spaces based on the lower bound we deduce. Apart from the above, we show existence of coresets for sampling uniform points from the Euclidean space -- for both the static and the streaming case. This leads to a $\left( 1+ε\right)$-approximation algorithm for uniform sampling from the Euclidean space.
The Complexity of Finding Effectors
Venue: arXiv cs.DS 2015
Year: 2015

The NP-hard EFFECTORS problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation processes in social networks. In the corresponding model the arcs carry probabilities and there is a probabilistic diffusion process activating nodes by neighboring activated nodes with probabilities as specified by the arcs. The point is to explain a given network activation state as well as possible by using a minimum number of "effector nodes"; these are selected before the activation process starts. We correct, complement, and extend previous work from the data mining community by a more thorough computational complexity analysis of EFFECTORS, identifying both tractable and intractable cases. To this end, we also exploit a parameterization measuring the "degree of randomness" (the number of "really" probabilistic arcs) which might prove useful for analyzing other probabilistic network diffusion problems as well.
RoboBrain: Large-Scale Knowledge Engine for Robots
Venue: arXiv cs.AI 2015
Year: 2015

In this paper we introduce a knowledge engine, which learns and shares knowledge representations, for robots to carry out a variety of tasks. Building such an engine brings with it the challenge of dealing with multiple data modalities including symbols, natural language, haptic senses, robot trajectories, visual features and many others. The \textit{knowledge} stored in the engine comes from multiple sources including physical interactions that robots have while performing tasks (perception, planning and control), knowledge bases from the Internet and learned representations from several robotics research groups. We discuss various technical aspects and associated challenges such as modeling the correctness of knowledge, inferring latent information and formulating different robotic tasks as queries to the knowledge engine. We describe the system architecture and how it supports different mechanisms for users and robots to interact with the engine. Finally, we demonstrate its use in three important research areas: grounding natural language, perception, and planning, which are the key building blocks for many robotic tasks. This knowledge engine is a collaborative effort and we call it RoboBrain.
Matrix Multiplication, Trilinear Decompositions, APA Algorithms, and Summation
Venue: arXiv cs.DS 2015
Year: 2015

Matrix multiplication (hereafter we use the acronym MM) is among the most fundamental operations of modern computations. The efficiency of its performance depends on various factors, in particular vectorization, data movement and arithmetic complexity of the computations, but here we focus just on the study of the arithmetic cost and the impact of this study on other areas of modern computing. In the early 1970s it was expected that the straightforward cubic time algorithm for MM will soon be accelerated to enable MM in nearly quadratic arithmetic time, with some far fetched implications. While pursuing this goal the mainstream research had its focus on the decrease of the classical exponent 3 of the complexity of MM towards its lower bound 2, disregarding the growth of the input size required to support this decrease. Eventually, surprising combinations of novel ideas and sophisticated techniques enabled the decrease of the exponent to its benchmark value of about 2.38, but the supporting MM algorithms improved the straightforward one only for the inputs of immense sizes. Meanwhile, the communication complexity, rather than the arithmetic complexity, has become the bottleneck of computations in linear algebra. This development may seem to undermine the value of the past and future research aimed at the decrease of the arithmetic cost of MM, but we feel that the study should be reassessed rather than closed and forgotten. We review the old and new work in this area in the present day context, recall some major techniques introduced in the study of MM, discuss their impact on the modern theory and practice of computations for MM and beyond MM, and link one of these techniques to some simple algorithms for inner product and summation.
Longest Common Extensions in Trees
Venue: arXiv cs.DS 2015
Year: 2015

The longest common extension (LCE) of two indices in a string is the length of the longest identical substrings starting at these two indices. The LCE problem asks to preprocess a string into a compact data structure that supports fast LCE queries. In this paper we generalize the LCE problem to trees and suggest a few applications of LCE in trees to tries and XML databases. Given a labeled and rooted tree $T$ of size $n$, the goal is to preprocess $T$ into a compact data structure that support the following LCE queries between subpaths and subtrees in $T$. Let $v_1$, $v_2$, $w_1$, and $w_2$ be nodes of $T$ such that $w_1$ and $w_2$ are descendants of $v_1$ and $v_2$ respectively. \begin{itemize} \item $\LCEPP(v_1, w_1, v_2, w_2)$: (path-path $\LCE$) return the longest common prefix of the paths $v_1 \leadsto w_1$ and $v_2 \leadsto w_2$. \item $\LCEPT(v_1, w_1, v_2)$: (path-tree $\LCE$) return maximal path-path LCE of the path $v_1 \leadsto w_1$ and any path from $v_2$ to a descendant leaf. \item $\LCETT(v_1, v_2)$: (tree-tree $\LCE$) return a maximal path-path LCE of any pair of paths from $v_1$ and $v_2$ to descendant leaves. \end{itemize} We present the first non-trivial bounds for supporting these queries. For $\LCEPP$ queries, we present a linear-space solution with $O(\log^{*} n)$ query time. For $\LCEPT$ queries, we present a linear-space solution with $O((\log\log n)^{2})$ query time, and complement this with a lower bound showing that any path-tree LCE structure of size $O(n \polylog(n))$ must necessarily use $Ω(\log\log n)$ time to answer queries. For $\LCETT$ queries, we present a time-space trade-off, that given any parameter $τ$, $1 \leq τ\leq n$, leads to an $O(nτ)$ space and $O(n/τ)$ query-time solution. This is complemented with a reduction to the the set intersection problem implying that a fast linear space solution is not likely to exist.
Fast-Decodable Space-Time Codes for the $N$-Relay and Multiple-Access MIMO Channel
Venue: arXiv cs.IT 2015
Year: 2015

In this article, the first general constructions of fast-decodable, more specifically (conditionally) $g$-group decodable, space-time block codes for the Nonorthogonal Amplify and Forward (NAF) Multiple-Input Multiple-Output (MIMO) relay channel under the half-duplex constraint are proposed. In this scenario, the source and the intermediate relays used for data amplification are allowed to employ multiple antennas for data transmission and reception. The worst-case decoding complexity of the obtained codes is reduced by up to $75%$. In addition to being fast-decodable, the proposed codes achieve full-diversity and have nonvanishing determinants, which has been shown to be useful for achieving the optimal Diversity-Multiplexing Tradeoff (DMT) of the NAF channel. Further, it is shown that the same techniques as in the cooperative scenario can be utilized to achieve fast-decodability for $K$-user MIMO Multiple-Access Channel (MAC) space-time block codes. The resulting codes in addition exhibit the conditional nonvanishing determinant property which, for its part, has been shown to be useful for achieving the optimal MAC-DMT.
On testing single connectedness in directed graphs and some related problems
Venue: arXiv cs.DS 2015
Year: 2015

Let $G=(V,E)$ be a directed graph with $n$ vertices and $m$ edges. The graph $G$ is called singly-connected if for each pair of vertices $v,w \in V$ there is at most one simple path from $v$ to $w$ in $G$. Buchsbaum and Carlisle (1993) gave an algorithm for testing whether $G$ is singly-connected in $O(n^{2})$ time. In this paper we describe a refined version of this algorithm with running time $O(s\cdot t+m)$, where $s$ and $t$ are the number of sources and sinks, respectively, in the reduced graph $G^{r}$ obtained by first contracting each strongly connected component of $G$ into one vertex and then eliminating vertices of indegree or outdegree $1$ by a contraction operation. Moreover, we show that the problem of finding a minimum cardinality edge subset $C\subseteq E$ (respectively, vertex subset $F\subseteq V$) whose removal from $G$ leaves a singly-connected graph is NP-hard.
Topological analysis of scalar fields with outliers
Venue: arXiv cs.CG 2015
Year: 2015

Given a real-valued function $f$ defined over a manifold $M$ embedded in $\mathbb{R}^d$, we are interested in recovering structural information about $f$ from the sole information of its values on a finite sample $P$. Existing methods provide approximation to the persistence diagram of $f$ when geometric noise and functional noise are bounded. However, they fail in the presence of aberrant values, also called outliers, both in theory and practice. We propose a new algorithm that deals with outliers. We handle aberrant functional values with a method inspired from the k-nearest neighbors regression and the local median filtering, while the geometric outliers are handled using the distance to a measure. Combined with topological results on nested filtrations, our algorithm performs robust topological analysis of scalar fields in a wider range of noise models than handled by current methods. We provide theoretical guarantees and experimental results on the quality of our approximation of the sampled scalar field.