OpenRaiser/Intern-Atlas huggingface dataset:
Network Mapping by Replaying Hyperbolic Growth
Venue: arXiv cs.SI 2014
Year: 2014

Recent years have shown a promising progress in understanding geometric underpinnings behind the structure, function, and dynamics of many complex networks in nature and society. However these promises cannot be readily fulfilled and lead to important practical applications, without a simple, reliable, and fast network mapping method to infer the latent geometric coordinates of nodes in a real network. Here we present HyperMap, a simple method to map a given real network to its hyperbolic space. The method utilizes a recent geometric theory of complex networks modeled as random geometric graphs in hyperbolic spaces. The method replays the network's geometric growth, estimating at each time step the hyperbolic coordinates of new nodes in a growing network by maximizing the likelihood of the network snapshot in the model. We apply HyperMap to the AS Internet, and find that: 1) the method produces meaningful results, identifying soft communities of ASs belonging to the same geographic region; 2) the method has a remarkable predictive power: using the resulting map, we can predict missing links in the Internet with high precision, outperforming popular existing methods; and 3) the resulting map is highly navigable, meaning that a vast majority of greedy geometric routing paths are successful and low-stretch. Even though the method is not without limitations, and is open for improvement, it occupies a unique attractive position in the space of trade-offs between simplicity, accuracy, and computational complexity.
The Approximate Sum Capacity of the Symmetric Gaussian K-User Interference Channel
Venue: arXiv cs.IT 2014
Year: 2014

Interference alignment has emerged as a powerful tool in the analysis of multi-user networks. Despite considerable recent progress, the capacity region of the Gaussian K-user interference channel is still unknown in general, in part due to the challenges associated with alignment on the signal scale using lattice codes. This paper develops a new framework for lattice interference alignment, based on the compute-and-forward approach. Within this framework, each receiver decodes by first recovering two or more linear combinations of the transmitted codewords with integer-valued coefficients and then solving these equations for its desired codeword. For the special case of symmetric channel gains, this framework is used to derive the approximate sum capacity of the Gaussian interference channel, up to an explicitly defined outage set of the channel gains. The key contributions are the capacity lower bounds for the weak through strong interference regimes, where each receiver should jointly decode its own codeword along with part of the interfering codewords. As part of the analysis, it is shown that decoding K linear combinations of the codewords can approach the sum capacity of the K-user Gaussian multiple-access channel up to a gap of no more than K log(K)/2 bits.
Time Warp on the Go (Updated Version)
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we deal with the impact of multi and many-core processor architectures on simulation. Despite the fact that modern CPUs have an increasingly large number of cores, most softwares are still unable to take advantage of them. In the last years, many tools, programming languages and general methodologies have been proposed to help building scalable applications for multi-core architectures, but those solutions are somewhat limited. Parallel and distributed simulation is an interesting application area in which efficient and scalable multi-core implementations would be desirable. In this paper we investigate the use of the Go Programming Language to implement optimistic parallel simulations based on the Time Warp mechanism. Specifically, we describe the design, implementation and evaluation of a new parallel simulator. The scalability of the simulator is studied when in presence of a modern multi-core CPU and the effects of the Hyper-Threading technology on optimistic simulation are analyzed.
Data Minimisation in Communication Protocols: A Formal Analysis Framework and Application to Identity Management
Venue: arXiv cs.CR 2014
Year: 2014

With the growing amount of personal information exchanged over the Internet, privacy is becoming more and more a concern for users. One of the key principles in protecting privacy is data minimisation. This principle requires that only the minimum amount of information necessary to accomplish a certain goal is collected and processed. "Privacy-enhancing" communication protocols have been proposed to guarantee data minimisation in a wide range of applications. However, currently there is no satisfactory way to assess and compare the privacy they offer in a precise way: existing analyses are either too informal and high-level, or specific for one particular system. In this work, we propose a general formal framework to analyse and compare communication protocols with respect to privacy by data minimisation. Privacy requirements are formalised independent of a particular protocol in terms of the knowledge of (coalitions of) actors in a three-layer model of personal information. These requirements are then verified automatically for particular protocols by computing this knowledge from a description of their communication. We validate our framework in an identity management (IdM) case study. As IdM systems are used more and more to satisfy the increasing need for reliable on-line identification and authentication, privacy is becoming an increasingly critical issue. We use our framework to analyse and compare four identity management systems. Finally, we discuss the completeness and (re)usability of the proposed framework.
Distributed Secret Dissemination Across a Network
Venue: arXiv cs.CR 2014
Year: 2014

Shamir's (n, k) threshold secret sharing is an important component of several cryptographic protocols, such as those for secure multiparty-computation and key management. These protocols typically assume the presence of direct communication links from the dealer to all participants, in which case the dealer can directly pass the shares of the secret to each participant. In this paper, we consider the problem of secret sharing when the dealer does not have direct communication links to all the participants, and instead, the dealer and the participants form a general network. Existing methods are based on secure message transmissions from the dealer to each participant requiring considerable coordination in the network. In this paper, we present a distributed algorithm for disseminating shares over a network, which we call the SNEAK algorithm, requiring each node to know only the identities of its one-hop neighbours. While SNEAK imposes a stronger condition on the network by requiring the dealer to be what we call k-propagating rather than k-connected as required by the existing solutions, we show that in addition to being distributed, SNEAK achieves significant reduction in the communication cost and the amount of randomness required.
Reordering Rows for Better Compression: Beyond the Lexicographic Order
Venue: arXiv cs.DB 2014
Year: 2014

Sorting database tables before compressing them improves the compression rate. Can we do better than the lexicographical order? For minimizing the number of runs in a run-length encoding compression scheme, the best approaches to row-ordering are derived from traveling salesman heuristics, although there is a significant trade-off between running time and compression. A new heuristic, Multiple Lists, which is a variant on Nearest Neighbor that trades off compression for a major running-time speedup, is a good option for very large tables. However, for some compression schemes, it is more important to generate long runs rather than few runs. For this case, another novel heuristic, Vortex, is promising. We find that we can improve run-length encoding up to a factor of 3 whereas we can improve prefix coding by up to 80%: these gains are on top of the gains due to lexicographically sorting the table. We prove that the new row reordering is optimal (within 10%) at minimizing the runs of identical values within columns, in a few cases.
A Time and Space Efficient Algorithm for Contextual Linear Bandits
Venue: arXiv cs.DS 2014
Year: 2014

We consider a multi-armed bandit problem where payoffs are a linear function of an observed stochastic contextual variable. In the scenario where there exists a gap between optimal and suboptimal rewards, several algorithms have been proposed that achieve $O(\log T)$ regret after $T$ time steps. However, proposed methods either have a computation complexity per iteration that scales linearly with $T$ or achieve regrets that grow linearly with the number of contexts $|\myset{X}|$. We propose an $ε$-greedy type of algorithm that solves both limitations. In particular, when contexts are variables in $\reals^d$, we prove that our algorithm has a constant computation complexity per iteration of $O(poly(d))$ and can achieve a regret of $O(poly(d) \log T)$ even when $|\myset{X}| = Ω(2^d) $. In addition, unlike previous algorithms, its space complexity scales like $O(Kd^2)$ and does not grow with $T$.
SUMIS: Near-Optimal Soft-In Soft-Out MIMO Detection With Low and Fixed Complexity
Venue: arXiv cs.IT 2014
Year: 2014

The fundamental problem of our interest here is soft-input soft-output multiple-input multiple-output (MIMO) detection. We propose a method, referred to as subspace marginalization with interference suppression (SUMIS), that yields unprecedented performance at low and fixed (deterministic) complexity. Our method provides a well-defined tradeoff between computational complexity and performance. Apart from an initial sorting step consisting of selecting channel-matrix columns, the algorithm involves no searching nor algorithmic branching; hence the algorithm has a completely predictable run-time and allows for a highly parallel implementation. We numerically assess the performance of SUMIS in different practical settings: full/partial channel state information, sequential/iterative decoding, and low/high rate outer codes. We also comment on how the SUMIS method performs in systems with a large number of transmit antennas.
The Fast Cauchy Transform and Faster Robust Linear Regression
Venue: arXiv cs.DS 2014
Year: 2014

We provide fast algorithms for overconstrained $\ell_p$ regression and related problems: for an $n\times d$ input matrix $A$ and vector $b\in\mathbb{R}^n$, in $O(nd\log n)$ time we reduce the problem $\min_{x\in\mathbb{R}^d} \|Ax-b\|_p$ to the same problem with input matrix $\tilde A$ of dimension $s \times d$ and corresponding $\tilde b$ of dimension $s\times 1$. Here, $\tilde A$ and $\tilde b$ are a coreset for the problem, consisting of sampled and rescaled rows of $A$ and $b$; and $s$ is independent of $n$ and polynomial in $d$. Our results improve on the best previous algorithms when $n\gg d$, for all $p\in[1,\infty)$ except $p=2$. We also provide a suite of improved results for finding well-conditioned bases via ellipsoidal rounding, illustrating tradeoffs between running time and conditioning quality, including a one-pass conditioning algorithm for general $\ell_p$ problems. We also provide an empirical evaluation of implementations of our algorithms for $p=1$, comparing them with related algorithms. Our empirical results show that, in the asymptotic regime, the theory is a very good guide to the practical performance of these algorithms. Our algorithms use our faster constructions of well-conditioned bases for $\ell_p$ spaces and, for $p=1$, a fast subspace embedding of independent interest that we call the Fast Cauchy Transform: a distribution over matrices $Π:\mathbb{R}^n\mapsto \mathbb{R}^{O(d\log d)}$, found obliviously to $A$, that approximately preserves the $\ell_1$ norms: that is, with large probability, simultaneously for all $x$, $\|Ax\|_1 \approx \|ΠAx\|_1$, with distortion $O(d^{2+η})$, for an arbitrarily small constant $η>0$; and, moreover, $ΠA$ can be computed in $O(nd\log d)$ time. The techniques underlying our Fast Cauchy Transform include fast Johnson-Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.
Distributed Supervisory Control of Discrete-Event Systems with Communication Delay
Venue: arXiv cs.SY 2014
Year: 2014

This paper identifies a property of delay-robustness in distributed supervisory control of discrete-event systems (DES) with communication delays. In previous work a distributed supervisory control problem has been investigated on the assumption that inter-agent communications take place with negligible delay. From an applications viewpoint it is desirable to relax this constraint and identify communicating distributed controllers which are delay-robust, namely logically equivalent to their delay-free counterparts. For this we introduce inter-agent channels modeled as 2-state automata, compute the overall system behavior, and present an effective computational test for delay-robustness. From the test it typically results that the given delay-free distributed control is delay-robust with respect to certain communicated events, but not for all, thus distinguishing events which are not delay-critical from those that are. The approach is illustrated by a workcell model with three communicating agents.
Tight Analysis of Priority Queuing Policy for Egress Traffic
Venue: arXiv cs.DS 2014
Year: 2014

Recently, the problems of evaluating performances of switches and routers have been formulated as online problems, and a great amount of results have been presented. In this paper, we focus on managing outgoing packets (called {\em egress traffic}) on switches that support Quality of Service (QoS), and analyze the performance of one of the most fundamental scheduling policies {\em Priority Queuing} ($PQ$) using competitive analysis. We formulate the problem of managing egress queues as follows: An output interface is equipped with $m$ queues, each of which has a buffer of size $B$. The size of a packet is unit, and each buffer can store up to $B$ packets simultaneously. Each packet is associated with one of $m$ priority values $α_{j}$ ($1 \leq j \leq m$), where $α_{1} \leq α_{2} \leq \cdots \leq α_{m}$, $α_{1} = 1$, and $α_{m} = α$ and the task of an online algorithm is to select one of $m$ queues at each scheduling step. The purpose of this problem is to maximize the sum of the values of the scheduled packets. For any $B$ and any $m$, we show that the competitive ratio of $PQ$ is exactly $2 - \min_{x \in [1, m-1] } \{ \frac{ α_{x+1} }{ \sum_{j = 1}^{x+1} α_{j} } \}$. That is, we conduct a complete analysis of the performance of $PQ$ using worst case analysis. Moreover, we show that no deterministic online algorithm can have a competitive ratio smaller than $1 + \frac{ α^3 + α^2 + α}{ α^4 + 4 α^3 + 3 α^2 + 4 α+ 1 }$.
Optimal Non-Uniform Mapping for Probabilistic Shaping
Venue: arXiv cs.IT 2014
Year: 2014

The construction of optimal non-uniform mappings for discrete input memoryless channels (DIMCs) is investigated. An efficient algorithm to find optimal mappings is proposed and the rate by which a target distribution is approached is investigated. The results are applied to non-uniform mappings for additive white Gaussian noise (AWGN) channels with finite signal constellations. The mappings found by the proposed methods outperform those obtained via a central limit theorem approach as suggested in the literature.
Finite-Memory Strategy Synthesis for Robust Multidimensional Mean-Payoff Objectives
Venue: arXiv cs.LO 2014
Year: 2014

Two-player games on graphs provide the mathematical foundation for the study of reactive systems. In the quantitative framework, an objective assigns a value to every play, and the goal of player 1 is to minimize the value of the objective. In this framework, there are two relevant synthesis problems to consider: the quantitative analysis problem is to compute the minimal (or infimum) value that player 1 can assure, and the boolean analysis problem asks whether player 1 can assure that the value of the objective is at most $ν$ (for a given threshold $ν$). Mean-payoff expression games are played on a multidimensional weighted graph. An atomic mean-payoff expression objective is the mean-payoff value (the long-run average weight) of a certain dimension, and the class of mean-payoff expressions is the closure of atomic mean-payoff expressions under the algebraic operations of $\MAX,\MIN$, numerical complement and $\SUM$. In this work, we study for the first time the strategy synthesis problems for games with robust quantitative objectives, namely, games with mean-payoff expression objectives. While in general, optimal strategies for these games require infinite-memory, in synthesis we are typically interested in the construction of a finite-state system. Hence, we consider games in which player 1 is restricted to finite-memory strategies, and our main contribution is as follows. We prove that for mean-payoff expressions, the quantitative analysis problem is computable, and the boolean analysis problem is inter-reducible with Hilbert's tenth problem over rationals --- a fundamental long-standing open problem in computer science and mathematics.
Combinatorial Spaces And Order Topologies
Venue: arXiv cs.CC 2014
Year: 2014

An archetypal problem discussed in computer science is the problem of searching for a given number in a given set of numbers. Other than sequential search, the classic solution is to sort the list of numbers and then apply binary search. The binary search problem has a complexity of O(logN) for a list of N numbers while the sorting problem cannot be better than O(N) on any sequential computer following the usual assumptions. Whenever the problem of deciding partial order can be done in O(1), a variation of the problem on some bounded list of numbers is to apply binary search without resorting to sort. The overall complexity of the problem is then O(log R) for some radius R. A logarithmic upper-bound for finite encodings is shown. Also, the topology of orderings can provide efficient algorithms for search problems in combinatorial spaces. The main characteristic of those spaces is that they have typical exponential space complexities. The factorial case describes an order topology that can be illustrated using the combinatorial polytope . When a known order topology can be combined to a given formulation of a search problem, the resulting search problem has a polylogarithmic complexity. This logarithmic complexity can then become useful in combinatorial search by providing a logarithmic break-down. These algorithms can be termed as the class of search algorithms that do not require read and are equivalent to the class of logarithmically recursive functions. Also, the notion of order invariance is discussed.
Conditions for a Monotonic Channel Capacity
Venue: arXiv cs.IT 2014
Year: 2014

Motivated by results in optical communications, where the performance can degrade dramatically if the transmit power is sufficiently increased, the channel capacity is characterized for various kinds of memoryless vector channels. It is proved that for all static point-to-point channels, the channel capacity is a nondecreasing function of power. As a consequence, maximizing the mutual information over all input distributions with a certain power is for such channels equivalent to maximizing it over the larger set of input distributions with upperbounded power. For interference channels such as optical wavelength-division multiplexing systems, the primary channel capacity is always nondecreasing with power if all interferers transmit with identical distributions as the primary user. Also, if all input distributions in an interference channel are optimized jointly, then the achievable sum-rate capacity is again nondecreasing. The results generalizes to the channel capacity as a function of a wide class of costs, not only power.
Balanced Allocations and Double Hashing
Venue: arXiv cs.DS 2014
Year: 2014

Double hashing has recently found more common usage in schemes that use multiple hash functions. In double hashing, for an item $x$, one generates two hash values $f(x)$ and $g(x)$, and then uses combinations $(f(x) +k g(x)) \bmod n$ for $k=0,1,2,...$ to generate multiple hash values from the initial two. We first perform an empirical study showing that, surprisingly, the performance difference between double hashing and fully random hashing appears negligible in the standard balanced allocation paradigm, where each item is placed in the least loaded of $d$ choices, as well as several related variants. We then provide theoretical results that explain the behavior of double hashing in this context.
Ambiguity of ω-Languages of Turing Machines
Venue: arXiv cs.LO 2014
Year: 2014

An ω-language is a set of infinite words over a finite alphabet X. We consider the class of recursive ω-languages, i.e. the class of ω-languages accepted by Turing machines with a Büchi acceptance condition, which is also the class Σ11 of (effective) analytic subsets of Xω for some finite alphabet X. We investigate here the notion of ambiguity for recursive ω-languages with regard to acceptance by Büchi Turing machines. We first present in detail essentials on the literature on ω-languages accepted by Turing Machines. Then we give a complete and broad view on the notion of ambiguity and unambiguity of Büchi Turing machines and of the ω-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.
Simple, Fast and Deterministic Gossip and Rumor Spreading
Venue: arXiv cs.DS 2014
Year: 2014

We study gossip algorithms for the rumor spreading problem which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as message efficient, simple and robust solutions to the rumor spreading problem. Recently, non-uniform random gossip schemes were devised to allow efficient rumor spreading in networks with bottlenecks. In particular, [Censor-Hillel et al., STOC'12] gave an O(log^3 n) algorithm to solve the 1-local broadcast problem in which each node wants to exchange rumors locally with its 1-neighborhood. By repeatedly applying this protocol one can solve the global rumor spreading quickly for all networks with small diameter, independently of the conductance. This and all prior gossip algorithms for the rumor spreading problem have been inherently randomized in their design and analysis. This resulted in a parallel research direction trying to reduce and determine the amount of randomness needed for efficient rumor spreading. This has been done via lower bounds for restricted models and by designing gossip algorithms with a reduced need for randomness. The general intuition and consensus of these results has been that randomization plays a important role in effectively spreading rumors. In this paper we improves over this state of the art in several ways by presenting a deterministic gossip algorithm that solves the the k-local broadcast problem in 2(k+log n)log n rounds. Besides being the first efficient deterministic solution to the rumor spreading problem this algorithm is interesting in many aspects: It is simpler, more natural, more robust and faster than its randomized pendant and guarantees success with certainty instead of with high probability. Its analysis is furthermore simple, self-contained and fundamentally different from prior works.