OpenRaiser/Intern-Atlas huggingface dataset:
On the Capacity of Multiplicative Finite-Field Matrix Channels
Venue: arXiv cs.IT 2013
Year: 2013

This paper deals with the multiplicative finite-field matrix channel, a discrete memoryless channel whose input and output are matrices (over a finite field) related by a multiplicative transfer matrix. The model considered here assumes that all transfer matrices with the same rank are equiprobable, so that the channel is completely characterized by the rank distribution of the transfer matrix. This model is seen to be more flexible than previously proposed ones in describing random linear network coding systems subject to link erasures, while still being sufficiently simple to allow tractability. The model is also conservative in the sense that its capacity provides a lower bound on the capacity of any channel with the same rank distribution. A main contribution is to express the channel capacity as the solution of a convex optimization problem which can be easily solved by numerical computation. For the special case of constant-rank input, a closed-form expression for the capacity is obtained. The behavior of the channel for asymptotically large field size or packet length is studied, and it is shown that constant-rank input suffices in this case. Finally, it is proved that the well-known approach of treating inputs and outputs as subspaces is information-lossless even in this more general model.
How to Construct Polar Codes
Venue: arXiv cs.IT 2013
Year: 2013

A method for efficiently constructing polar codes is presented and analyzed. Although polar codes are explicitly defined, straightforward construction is intractable since the resulting polar bit-channels have an output alphabet that grows exponentially with he code length. Thus the core problem that needs to be solved is that of faithfully approximating a bit-channel with an intractably large alphabet by another channel having a manageable alphabet size. We devise two approximation methods which "sandwich" the original bit-channel between a degraded and an upgraded version thereof. Both approximations can be efficiently computed, and turn out to be extremely close in practice. We also provide theoretical analysis of our construction algorithms, proving that for any fixed $ε> 0$ and all sufficiently large code lengths $n$, polar codes whose rate is within $ε$ of channel capacity can be constructed in time and space that are both linear in $n$.
A Large-Scale Community Structure Analysis In Facebook
Venue: arXiv cs.SI 2013
Year: 2013

Understanding social dynamics that govern human phenomena, such as communications and social relationships is a major problem in current computational social sciences. In particular, given the unprecedented success of online social networks (OSNs), in this paper we are concerned with the analysis of aggregation patterns and social dynamics occurring among users of the largest OSN as the date: Facebook. In detail, we discuss the mesoscopic features of the community structure of this network, considering the perspective of the communities, which has not yet been studied on such a large scale. To this purpose, we acquired a sample of this network containing millions of users and their social relationships; then, we unveiled the communities representing the aggregation units among which users gather and interact; finally, we analyzed the statistical features of such a network of communities, discovering and characterizing some specific organization patterns followed by individuals interacting in online social networks, that emerge considering different sampling techniques and clustering methodologies. This study provides some clues of the tendency of individuals to establish social interactions in online social networks that eventually contribute to building a well-connected social structure, and opens space for further social studies.
The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems
Venue: arXiv cs.DS 2013
Year: 2013

We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an {\em independent set} in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such {\em submodular matroid secretary problems}. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a {\em constant} number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.
Multi-User MIMO Scheduling in the Fourth Generation Cellular Uplink
Venue: arXiv cs.NI 2013
Year: 2013

We consider Multi-User MIMO (MU-MIMO) scheduling in the 3GPP LTE-Advanced (3GPP LTE-A) cellular uplink. The 3GPP LTE-A uplink allows for precoded multi-stream (precoded MIMO) transmission from each scheduled user and also allows flexible multi-user (MU) scheduling wherein multiple users can be assigned the same time-frequency resource. However, exploiting these features is made challenging by certain practical constraints that have been imposed in order to maintain a low signaling overhead. We show that while the scheduling problem in the 3GPP LTE-A cellular uplink is NP-hard, it can be formulated as the maximization of a submodular set function subject to one matroid and multiple knapsack constraints. We then propose constant-factor polynomial-time approximation algorithms and demonstrate their superior performance via simulations.
Analysis of Buffer Starvation with Application to Objective QoE Optimization of Streaming Services
Venue: arXiv cs.PF 2013
Year: 2013

Our purpose in this paper is to characterize buffer starvations for streaming services. The buffer is modeled as an M/M/1 queue, plus the consideration of bursty arrivals. When the buffer is empty, the service restarts after a certain amount of packets are \emph{prefetched}. With this goal, we propose two approaches to obtain the \emph{exact distribution} of the number of buffer starvations, one of which is based on \emph{Ballot theorem}, and the other uses recursive equations. The Ballot theorem approach gives an explicit result. We extend this approach to the scenario with a constant playback rate using Tàkacs Ballot theorem. The recursive approach, though not offering an explicit result, can obtain the distribution of starvations with non-independent and identically distributed (i.i.d.) arrival process in which an ON/OFF bursty arrival process is considered in this work. We further compute the starvation probability as a function of the amount of prefetched packets for a large number of files via a fluid analysis. Among many potential applications of starvation analysis, we show how to apply it to optimize the objective quality of experience (QoE) of media streaming, by exploiting the tradeoff between startup/rebuffering delay and starvations.
SparseAssembler2: Sparse k-mer Graph for Memory Efficient Genome Assembly
Venue: arXiv cs.DS 2013
Year: 2013

The formal version of our work has been published in BMC Bioinformatics and can be found here: http://www.biomedcentral.com/1471-2105/13/S6/S1 Motivation: To tackle the problem of huge memory usage associated with de Bruijn graph-based algorithms, upon which some of the most widely used de novo genome assemblers have been built, we released SparseAssembler1. SparseAssembler1 can save as much as 90% memory consumption in comparison with the state-of-art assemblers, but it requires rounds of denoising to accurately assemble genomes. In this paper, we introduce a new general model for genome assembly that uses only sparse k-mers. The new model replaces the idea of the de Bruijn graph from the beginning, and achieves similar memory efficiency and much better robustness compared with our previous SparseAssembler1. Results: We demonstrate that the decomposition of reads of all overlapping k-mers, which is used in existing de Bruijn graph genome assemblers, is overly cautious. We introduce a sparse k-mer graph structure for saving sparse k-mers, which greatly reduces memory space requirements necessary for de novo genome assembly. In contrast with the de Bruijn graph approach, we devise a simple but powerful strategy, i.e., finding links between the k-mers in the genome and traversing following the links, which can be done by saving only a few k-mers. To implement the strategy, we need to only select some k-mers that may not even be overlapping ones, and build the links between these k-mers indicated by the reads. We can traverse through this sparse k-mer graph to build the contigs, and ultimately complete the genome assembly. Since the new sparse k-mers graph shares almost all advantages of de Bruijn graph, we are able to adapt a Dijkstra-like breadth-first search algorithm to circumvent sequencing errors and resolve polymorphisms.
Learning from Complex Systems: On the Roles of Entropy and Fisher Information in Pairwise Isotropic Gaussian Markov Random Fields
Venue: arXiv cs.IT 2013
Year: 2013

Markov Random Field models are powerful tools for the study of complex systems. However, little is known about how the interactions between the elements of such systems are encoded, especially from an information-theoretic perspective. In this paper, our goal is to enlight the connection between Fisher information, Shannon entropy, information geometry and the behavior of complex systems modeled by isotropic pairwise Gaussian Markov random fields. We propose analytical expressions to compute local and global versions of these measures using Besag's pseudo-likelihood function, characterizing the system's behavior through its \emph{Fisher curve}, a parametric trajectory accross the information space that provides a geometric representation for the study of complex systems. Computational experiments show how the proposed tools can be useful in extrating relevant information from complex patterns. The obtained results quantify and support our main conclusion, which is: in terms of information, moving towards higher entropy states (A --> B) is different from moving towards lower entropy states (B --> A), since the \emph{Fisher curves} are not the same given a natural orientation (the direction of time).
A W[1]-Completeness Result for Generalized Permutation Pattern Matching
Venue: arXiv cs.CC 2013
Year: 2013

The NP-complete Permutation Pattern Matching problem asks whether a permutation P (the pattern) can be matched into a permutation T (the text). A matching is an order-preserving embedding of P into T. In the Generalized Permutation Pattern Matching problem one can additionally enforce that certain adjacent elements in the pattern must be mapped to adjacent elements in the text. This paper studies the parameterized complexity of this more general problem. We show W[1]-completeness with respect to the length of the pattern P. Under standard complexity theoretic assumptions this implies that no fixed-parameter tractable algorithm can be found for any parameter depending solely on P.
Using Lotteries to Approximate the Optimal Revenue
Venue: arXiv cs.GT 2013
Year: 2013

There has been much recent work on the revenue-raising properties of truthful mechanisms for selling goods to selfish bidders. Typically the revenue of a mechanism is compared against a benchmark (such as, the maximum revenue obtainable by an omniscient seller selling at a fixed price to at least two customers), with a view to understanding how much lower the mechanism's revenue is than the benchmark, in the worst case. We study this issue in the context of {\em lotteries}, where the seller may sell a probability of winning an item. We are interested in two general issues. Firstly, we aim at using the true optimum revenue as benchmark for our auctions. Secondly, we study the extent to which the expressive power resulting from lotteries, helps to improve the worst-case ratio. We study this in the well-known context of {\em digital goods}, where the production cost is zero. We show that in this scenario, collusion-resistant lotteries (these are lotteries for which no coalition of bidders exchanging side payments has an advantage in lying) are as powerful as truthful ones.
Minimum Latency Submodular Cover
Venue: arXiv cs.DS 2013
Year: 2013

We study the Minimum Latency Submodular Cover problem (MLSC), which consists of a metric $(V,d)$ with source $r\in V$ and $m$ monotone submodular functions $f_1, f_2, ..., f_m: 2^V \rightarrow [0,1]$. The goal is to find a path originating at $r$ that minimizes the total cover time of all functions. This generalizes well-studied problems, such as Submodular Ranking [AzarG11] and Group Steiner Tree [GKR00]. We give a polynomial time $O(\log \frac{1}{\eps} \cdot \log^{2+δ} |V|)$-approximation algorithm for MLSC, where $ε>0$ is the smallest non-zero marginal increase of any $\{f_i\}_{i=1}^m$ and $δ>0$ is any constant. We also consider the Latency Covering Steiner Tree problem (LCST), which is the special case of \mlsc where the $f_i$s are multi-coverage functions. This is a common generalization of the Latency Group Steiner Tree [GuptaNR10a,ChakrabartyS11] and Generalized Min-sum Set Cover [AzarGY09, BansalGK10] problems. We obtain an $O(\log^2|V|)$-approximation algorithm for LCST. Finally we study a natural stochastic extension of the Submodular Ranking problem, and obtain an adaptive algorithm with an $O(\log 1/ \eps)$ approximation ratio, which is best possible. This result also generalizes some previously studied stochastic optimization problems, such as Stochastic Set Cover [GoemansV06] and Shared Filter Evaluation [MunagalaSW07, LiuPRY08].
Towards Quantifying Vertex Similarity in Networks
Venue: arXiv cs.SI 2013
Year: 2013

Vertex similarity is a major problem in network science with a wide range of applications. In this work we provide novel perspectives on finding (dis)similar vertices within a network and across two networks with the same number of vertices (graph matching). With respect to the former problem, we propose to optimize a geometric objective which allows us to express each vertex uniquely as a convex combination of a few extreme types of vertices. Our method has the important advantage of supporting efficiently several types of queries such as "which other vertices are most similar to this vertex?" by the use of the appropriate data structures and of mining interesting patterns in the network. With respect to the latter problem (graph matching), we propose the generalized condition number --a quantity widely used in numerical analysis-- $κ(L_G,L_H)$ of the Laplacian matrix representations of $G,H$ as a measure of graph similarity, where $G,H$ are the graphs of interest. We show that this objective has a solid theoretical basis and propose a deterministic and a randomized graph alignment algorithm. We evaluate our algorithms on both synthetic and real data. We observe that our proposed methods achieve high-quality results and provide us with significant insights into the network structure.
Exchange Economy in Two-User Multiple-Input Single-Output Interference Channels
Venue: arXiv cs.GT 2013
Year: 2013

We study the conflict between two links in a multiple-input single-output interference channel. This setting is strictly competitive and can be related to perfectly competitive market models. In such models, general equilibrium theory is used to determine equilibrium measures that are Pareto optimal. First, we consider the links to be consumers that can trade goods within themselves. The goods in our setting correspond to beamforming vectors. We utilize the conflict representation of the consumers in the Edgeworth box, a graphical tool that depicts the allocation of the goods for the two consumers, to provide closed-form solution to all Pareto optimal outcomes. Afterwards, we model the situation between the links as a competitive market which additionally defines prices for the goods. The equilibrium in this economy is called Walrasian and corresponds to the prices that equate the demand to the supply of goods. We calculate the unique Walrasian equilibrium and propose a coordination process that is realized by an arbitrator which distributes the Walrasian prices to the consumers. The consumers then calculate in a decentralized manner their optimal demand corresponding to beamforming vectors that achieve the Walrasian equilibrium. This outcome is Pareto optimal and dominates the noncooperative outcome of the systems. Thus, based on the game theoretic model and solution concept, an algorithm for a distributed implementation of the beamforming problem in multiple-input single-output interference channels is provided.
Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems
Venue: arXiv cs.LG 2013
Year: 2013

Crowdsourcing systems, in which numerous tasks are electronically distributed to numerous "information piece-workers", have emerged as an effective paradigm for human-powered solving of large scale problems in domains such as image classification, data entry, optical character recognition, recommendation, and proofreading. Because these low-paid workers can be unreliable, nearly all such systems must devise schemes to increase confidence in their answers, typically by assigning each task multiple times and combining the answers in an appropriate manner, e.g. majority voting. In this paper, we consider a general model of such crowdsourcing tasks and pose the problem of minimizing the total price (i.e., number of task assignments) that must be paid to achieve a target overall reliability. We give a new algorithm for deciding which tasks to assign to which workers and for inferring correct answers from the workers' answers. We show that our algorithm, inspired by belief propagation and low-rank matrix approximation, significantly outperforms majority voting and, in fact, is optimal through comparison to an oracle that knows the reliability of every worker. Further, we compare our approach with a more general class of algorithms which can dynamically assign tasks. By adaptively deciding which questions to ask to the next arriving worker, one might hope to reduce uncertainty more efficiently. We show that, perhaps surprisingly, the minimum price necessary to achieve a target reliability scales in the same manner under both adaptive and non-adaptive scenarios. Hence, our non-adaptive approach is order-optimal under both scenarios. This strongly relies on the fact that workers are fleeting and can not be exploited. Therefore, architecturally, our results suggest that building a reliable worker-reputation system is essential to fully harnessing the potential of adaptive designs.
Effectiveness and detection of denial of service attacks in Tor
Venue: arXiv cs.CR 2013
Year: 2013

Tor is currently one of the more popular systems for anonymizing near real-time communications on the Internet. Recently, Borisov et al. proposed a denial of service based attack on Tor (and related systems) that significantly increases the probability of compromising the anonymity provided. In this paper, we analyze the effectiveness of the attack using both an analytic model and simulation. We also describe two algorithms for detecting such attacks, one deterministic and proved correct, the other probabilistic and verified in simulation.
Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
Venue: arXiv cs.IT 2013
Year: 2013

Compressed sensing posits that, within limits, one can undersample a sparse signal and yet reconstruct it accurately. Knowing the precise limits to such undersampling is important both for theory and practice. We present a formula that characterizes the allowed undersampling of generalized sparse objects. The formula applies to Approximate Message Passing (AMP) algorithms for compressed sensing, which are here generalized to employ denoising operators besides the traditional scalar soft thresholding denoiser. This paper gives several examples including scalar denoisers not derived from convex penalization -- the firm shrinkage nonlinearity and the minimax nonlinearity -- and also nonscalar denoisers -- block thresholding, monotone regression, and total variation minimization. Let the variables eps = k/N and delta = n/N denote the generalized sparsity and undersampling fractions for sampling the k-generalized-sparse N-vector x_0 according to y=Ax_0. Here A is an n\times N measurement matrix whose entries are iid standard Gaussian. The formula states that the phase transition curve delta = delta(eps) separating successful from unsuccessful reconstruction of x_0 by AMP is given by: delta = M(eps| Denoiser), where M(eps| Denoiser) denotes the per-coordinate minimax mean squared error (MSE) of the specified, optimally-tuned denoiser in the directly observed problem y = x + z. In short, the phase transition of a noiseless undersampling problem is identical to the minimax MSE in a denoising problem.
Adaptive Regret Minimization in Bounded-Memory Games
Venue: arXiv cs.GT 2013
Year: 2013

Online learning algorithms that minimize regret provide strong guarantees in situations that involve repeatedly making decisions in an uncertain environment, e.g. a driver deciding what route to drive to work every day. While regret minimization has been extensively studied in repeated games, we study regret minimization for a richer class of games called bounded memory games. In each round of a two-player bounded memory-m game, both players simultaneously play an action, observe an outcome and receive a reward. The reward may depend on the last m outcomes as well as the actions of the players in the current round. The standard notion of regret for repeated games is no longer suitable because actions and rewards can depend on the history of play. To account for this generality, we introduce the notion of k-adaptive regret, which compares the reward obtained by playing actions prescribed by the algorithm against a hypothetical k-adaptive adversary with the reward obtained by the best expert in hindsight against the same adversary. Roughly, a hypothetical k-adaptive adversary adapts her strategy to the defender's actions exactly as the real adversary would within each window of k rounds. Our definition is parametrized by a set of experts, which can include both fixed and adaptive defender strategies. We investigate the inherent complexity of and design algorithms for adaptive regret minimization in bounded memory games of perfect and imperfect information. We prove a hardness result showing that, with imperfect information, any k-adaptive regret minimizing algorithm (with fixed strategies as experts) must be inefficient unless NP=RP even when playing against an oblivious adversary. In contrast, for bounded memory games of perfect and imperfect information we present approximate 0-adaptive regret minimization algorithms against an oblivious adversary running in time n^{O(1)}.