OpenRaiser/Intern-Atlas huggingface dataset:
Robustness of Complex Networks with Implications for Consensus and Contagion
Venue: arXiv cs.SI 2013
Year: 2013

We study a graph-theoretic property known as robustness, which plays a key role in certain classes of dynamics on networks (such as resilient consensus, contagion and bootstrap percolation). This property is stronger than other graph properties such as connectivity and minimum degree in that one can construct graphs with high connectivity and minimum degree but low robustness. However, we show that the notions of connectivity and robustness coincide on common random graph models for complex networks (Erdos-Renyi, geometric random, and preferential attachment graphs). More specifically, the properties share the same threshold function in the Erdos-Renyi model, and have the same values in one-dimensional geometric graphs and preferential attachment networks. This indicates that a variety of purely local diffusion dynamics will be effective at spreading information in such networks. Although graphs generated according to the above constructions are inherently robust, we also show that it is coNP-complete to determine whether any given graph is robust to a specified extent.
Improved matrix algorithms via the Subsampled Randomized Hadamard Transform
Venue: arXiv cs.DS 2013
Year: 2013

Several recent randomized linear algebra algorithms rely upon fast dimension reduction methods. A popular choice is the Subsampled Randomized Hadamard Transform (SRHT). In this article, we address the efficacy, in the Frobenius and spectral norms, of an SRHT-based low-rank matrix approximation technique introduced by Woolfe, Liberty, Rohklin, and Tygert. We establish a slightly better Frobenius norm error bound than currently available, and a much sharper spectral norm error bound (in the presence of reasonable decay of the singular values). Along the way, we produce several results on matrix operations with SRHTs (such as approximate matrix multiplication) that may be of independent interest. Our approach builds upon Tropp's in "Improved analysis of the Subsampled Randomized Hadamard Transform".
Decomposition Methods for Large Scale LP Decoding
Venue: arXiv cs.IT 2013
Year: 2013

When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). This LP decoder can be used to decode error-correcting codes at bit-error-rates comparable to state-of-the-art belief propagation (BP) decoders, but with significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper we draw on decomposition methods from optimization theory, specifically the Alternating Directions Method of Multipliers (ADMM), to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a "two-slice" characterization of the geometry of the parity polytope, which is the convex hull of all codewords of a single parity check code. This new characterization simplifies the representation of points in the polytope. Using this simplification, we develop an efficient algorithm for Euclidean norm projection onto the parity polytope. This projection is required by ADMM and allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently. We present numerical results for LDPC codes of lengths more than 1000. The waterfall region of LP decoding is seen to initiate at a slightly higher signal-to-noise ratio than for sum-product BP, however an error floor is not observed for LP decoding, which is not the case for BP. Our implementation of LP decoding using ADMM executes as fast as our baseline sum-product BP decoder, is fully parallelizable, and can be seen to implement a type of message-passing with a particularly simple schedule.
Online submodular welfare maximization: Greedy is optimal
Venue: arXiv cs.DS 2013
Year: 2013

We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless $NP = RP$. Since the Greedy algorithm is known to be 1/2-competitive for monotone submodular valuations, of which coverage is a special case, this proves that Greedy provides the optimal competitive ratio. On the other hand, we prove that Greedy in a stochastic setting with i.i.d.items and valuations satisfying diminishing returns is $(1-1/e)$-competitive, which is optimal even for coverage valuations, unless $NP=RP$. For online budget-additive allocation, we prove that no algorithm can be 0.612-competitive with respect to a natural LP which has been used previously for this problem.
Dynamic Bayesian diffusion estimation
Venue: arXiv cs.IT 2013
Year: 2013

The rapidly increasing complexity of (mainly wireless) ad-hoc networks stresses the need of reliable distributed estimation of several variables of interest. The widely used centralized approach, in which the network nodes communicate their data with a single specialized point, suffers from high communication overheads and represents a potentially dangerous concept with a single point of failure needing special treatment. This paper's aim is to contribute to another quite recent method called diffusion estimation. By decentralizing the operating environment, the network nodes communicate just within a close neighbourhood. We adopt the Bayesian framework to modelling and estimation, which, unlike the traditional approaches, abstracts from a particular model case. This leads to a very scalable and universal method, applicable to a wide class of different models. A particularly interesting case - the Gaussian regressive model - is derived as an example.
Lower Bound on Weights of Large Degree Threshold Functions
Venue: arXiv cs.CC 2013
Year: 2013

An integer polynomial $p$ of $n$ variables is called a \emph{threshold gate} for a Boolean function $f$ of $n$ variables if for all $x \in \zoon$ $f(x)=1$ if and only if $p(x)\geq 0$. The \emph{weight} of a threshold gate is the sum of its absolute values. In this paper we study how large a weight might be needed if we fix some function and some threshold degree. We prove $2^{Ω(2^{2n/5})}$ lower bound on this value. The best previous bound was $2^{Ω(2^{n/8})}$ (Podolskii, 2009). In addition we present substantially simpler proof of the weaker $2^{Ω(2^{n/4})}$ lower bound. This proof is conceptually similar to other proofs of the bounds on weights of nonlinear threshold gates, but avoids a lot of technical details arising in other proofs. We hope that this proof will help to show the ideas behind the construction used to prove these lower bounds.
On the Role of Mobility for Multi-message Gossip
Venue: arXiv cs.SI 2013
Year: 2013

We consider information dissemination in a large $n$-user wireless network in which $k$ users wish to share a unique message with all other users. Each of the $n$ users only has knowledge of its own contents and state information; this corresponds to a one-sided push-only scenario. The goal is to disseminate all messages efficiently, hopefully achieving an order-optimal spreading rate over unicast wireless random networks. First, we show that a random-push strategy -- where a user sends its own or a received packet at random -- is order-wise suboptimal in a random geometric graph: specifically, $Ω(\sqrt{n})$ times slower than optimal spreading. It is known that this gap can be closed if each user has "full" mobility, since this effectively creates a complete graph. We instead consider velocity-constrained mobility where at each time slot the user moves locally using a discrete random walk with velocity $v(n)$ that is much lower than full mobility. We propose a simple two-stage dissemination strategy that alternates between individual message flooding ("self promotion") and random gossiping. We prove that this scheme achieves a close to optimal spreading rate (within only a logarithmic gap) as long as the velocity is at least $v(n)=ω(\sqrt{\log n/k})$. The key insight is that the mixing property introduced by the partial mobility helps users to spread in space within a relatively short period compared to the optimal spreading time, which macroscopically mimics message dissemination over a complete graph.
A Consensual Linear Opinion Pool
Venue: arXiv cs.MA 2013
Year: 2013

An important question when eliciting opinions from experts is how to aggregate the reported opinions. In this paper, we propose a pooling method to aggregate expert opinions. Intuitively, it works as if the experts were continuously updating their opinions in order to accommodate the expertise of others. Each updated opinion takes the form of a linear opinion pool, where the weight that an expert assigns to a peer's opinion is inversely related to the distance between their opinions. In other words, experts are assumed to prefer opinions that are close to their own opinions. We prove that such an updating process leads to consensus, \textit{i.e.}, the experts all converge towards the same opinion. Further, we show that if rational experts are rewarded using the quadratic scoring rule, then the assumption that they prefer opinions that are close to their own opinions follows naturally. We empirically demonstrate the efficacy of the proposed method using real-world data.
A lower bound on seller revenue in single buyer monopoly auctions
Venue: arXiv cs.GT 2013
Year: 2013

We consider a monopoly seller who optimally auctions a single object to a single potential buyer, with a known distribution of valuations. We show that a tight lower bound on the seller's expected revenue is $1/e$ times the geometric expectation of the buyer's valuation, and that this bound is uniquely achieved for the equal revenue distribution. We show also that when the valuation's expectation and geometric expectation are close, then the seller's expected revenue is close to the expected valuation.
A combinatorial model of malware diffusion via Bluetooth connections
Venue: arXiv cs.CR 2013
Year: 2013

We outline here the mathematical expression of a diffusion model for cellphones malware transmitted through Bluetooth channels. In particular, we provide the deterministic formula underlying the proposed infection model, in its equivalent recursive (simple but computationally heavy) and closed form (more complex but efficiently computable) expression.
Remote sensing via $\ell_1$ minimization
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of detecting the locations of targets in the far field by sending probing signals from an antenna array and recording the reflected echoes. Drawing on key concepts from the area of compressive sensing, we use an $\ell_1$-based regularization approach to solve this, in general ill-posed, inverse scattering problem. As common in compressed sensing, we exploit randomness, which in this context comes from choosing the antenna locations at random. With $n$ antennas we obtain $n^2$ measurements of a vector $x \in \C^{N}$ representing the target locations and reflectivities on a discretized grid. It is common to assume that the scene $x$ is sparse due to a limited number of targets. Under a natural condition on the mesh size of the grid, we show that an $s$-sparse scene can be recovered via $\ell_1$-minimization with high probability if $n^2 \geq C s \log^2(N)$. The reconstruction is stable under noise and under passing from sparse to approximately sparse vectors. Our theoretical findings are confirmed by numerical simulations.
The Extraction of Community Structures from Publication Networks to Support Ethnographic Observations of Field Differences in Scientific Communication
Venue: arXiv cs.SI 2013
Year: 2013

The scientific community of researchers in a research specialty is an important unit of analysis for understanding the field specific shaping of scientific communication practices. These scientific communities are, however, a challenging unit of analysis to capture and compare because they overlap, have fuzzy boundaries, and evolve over time. We describe a network analytic approach that reveals the complexities of these communities through examination of their publication networks in combination with insights from ethnographic field studies. We suggest that the structures revealed indicate overlapping sub- communities within a research specialty and we provide evidence that they differ in disciplinary orientation and research practices. By mapping the community structures of scientific fields we aim to increase confidence about the domain of validity of ethnographic observations as well as of collaborative patterns extracted from publication networks thereby enabling the systematic study of field differences. The network analytic methods presented include methods to optimize the delineation of a bibliographic data set in order to adequately represent a research specialty, and methods to extract community structures from this data. We demonstrate the application of these methods in a case study of two research specialties in the physical and chemical sciences.
Bayesian Hypothesis Test for Sparse Support Recovery using Belief Propagation
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we introduce a new support recovery algorithm from noisy measurements called Bayesian hypothesis test via belief propagation (BHT-BP). BHT-BP focuses on sparse support recovery rather than sparse signal estimation. The key idea behind BHT-BP is to detect the support set of a sparse vector using hypothesis test where the posterior densities used in the test are obtained by aid of belief propagation (BP). Since BP provides precise posterior information using the noise statistic, BHT-BP can recover the support with robustness against the measurement noise. In addition, BHT-BP has low computational cost compared to the other algorithms by the use of BP. We show the support recovery performance of BHT-BP on the parameters (N; M; K; SNR) and compare the performance of BHT-BP to OMP and Lasso via numerical results.
Multi-Stage Classifier Design
Venue: arXiv cs.CV 2013
Year: 2013

In many classification systems, sensing modalities have different acquisition costs. It is often {\it unnecessary} to use every modality to classify a majority of examples. We study a multi-stage system in a prediction time cost reduction setting, where the full data is available for training, but for a test example, measurements in a new modality can be acquired at each stage for an additional cost. We seek decision rules to reduce the average measurement acquisition cost. We formulate an empirical risk minimization problem (ERM) for a multi-stage reject classifier, wherein the stage $k$ classifier either classifies a sample using only the measurements acquired so far or rejects it to the next stage where more attributes can be acquired for a cost. To solve the ERM problem, we show that the optimal reject classifier at each stage is a combination of two binary classifiers, one biased towards positive examples and the other biased towards negative examples. We use this parameterization to construct stage-by-stage global surrogate risk, develop an iterative algorithm in the boosting framework and present convergence and generalization results. We test our work on synthetic, medical and explosives detection datasets. Our results demonstrate that substantial cost reduction without a significant sacrifice in accuracy is achievable.
ExpTime Tableaux for the Description Logic SHIQ Based on Global State Caching and Integer Linear Feasibility Checking
Venue: arXiv cs.LO 2013
Year: 2013

We give the first ExpTime (complexity-optimal) tableau decision procedure for checking satisfiability of a knowledge base in the description logic SHIQ when numbers are coded in unary. Our procedure is based on global state caching and integer linear feasibility checking.
Multiaccess Channel with Partially Cooperating Encoders and Security Constraints
Venue: arXiv cs.IT 2013
Year: 2013

We study a special case of Willems's two-user multi-access channel with partially cooperating encoders from a security perspective. This model differs from Willems's setup in that only one encoder, Encoder 1, is allowed to conference; Encoder 2 does not transmit any message, and there is an additional passive eavesdropper from whom the communication should be kept secret. For the discrete memoryless (DM) case, we establish inner and outer bounds on the capacity-equivocation region. The inner bound is based on a combination of Willems's coding scheme, noise injection and additional binning that provides randomization for security. For the memoryless Gaussian model, we establish lower and upper bounds on the secrecy capacity. We also show that, under certain conditions, these bounds agree in some extreme cases of cooperation between the encoders. We illustrate our results through some numerical examples.
Universal Regular Autonomous Asynchronous Systems: Fixed Points, Equivalencies and Dynamic Bifurcations
Venue: arXiv cs.OH 2013
Year: 2013

The asynchronous systems are the non-deterministic models of the asynchronous circuits from the digital electrical engineering. In the autonomous version, such a system is a set of functions x:R{\to}{0,1}^{n} called states (R is the time set). If an asynchronous system is defined by making use of a so called generator function Φ:{0,1}^{n}{\to}{0,1}^{n}, then it is called regular. The property of universality means the greatest in the sense of the inclusion. The purpose of the paper is that of defining and of characterizing the fixed points, the equivalencies and the dynamical bifurcations of the universal regular autonomous asynchronous systems. We use analogies with the dynamical systems theory.
Near-Optimal Online Multiselection in Internal and External Memory
Venue: arXiv cs.DS 2013
Year: 2013

We introduce an online version of the multiselection problem, in which q selection queries are requested on an unsorted array of n elements. We provide the first online algorithm that is 1-competitive with Kaligosi et al. [ICALP 2005] in terms of comparison complexity. Our algorithm also supports online search queries efficiently. We then extend our algorithm to the dynamic setting, while retaining online functionality, by supporting arbitrary insertions and deletions on the array. Assuming that the insertion of an element is immediately preceded by a search for that element, we show that our dynamic online algorithm performs an optimal number of comparisons, up to lower order terms and an additive O(n) term. For the external memory model, we describe the first online multiselection algorithm that is O(1)-competitive. This result improves upon the work of Sibeyn [Journal of Algorithms 2006] when q > m, where m is the number of blocks that can be stored in main memory. We also extend it to support searches, insertions, and deletions of elements efficiently.
Information Source Detection in the SIR Model: A Sample Path Based Approach
Venue: arXiv cs.SI 2013
Year: 2013

This paper studies the problem of detecting the information source in a network in which the spread of information follows the popular Susceptible-Infected-Recovered (SIR) model. We assume all nodes in the network are in the susceptible state initially except the information source which is in the infected state. Susceptible nodes may then be infected by infected nodes, and infected nodes may recover and will not be infected again after recovery. Given a snapshot of the network, from which we know all infected nodes but cannot distinguish susceptible nodes and recovered nodes, the problem is to find the information source based on the snapshot and the network topology. We develop a sample path based approach where the estimator of the information source is chosen to be the root node associated with the sample path that most likely leads to the observed snapshot. We prove for infinite-trees, the estimator is a node that minimizes the maximum distance to the infected nodes. A reverse-infection algorithm is proposed to find such an estimator in general graphs. We prove that for $g$-regular trees such that $gq>1,$ where $g$ is the node degree and $q$ is the infection probability, the estimator is within a constant distance from the actual source with a high probability, independent of the number of infected nodes and the time the snapshot is taken. Our simulation results show that for tree networks, the estimator produced by the reverse-infection algorithm is closer to the actual source than the one identified by the closeness centrality heuristic. We then further evaluate the performance of the reverse infection algorithm on several real world networks.
Automatically Securing Permission-Based Software by Reducing the Attack Surface: An Application to Android
Venue: arXiv cs.CR 2013
Year: 2013

A common security architecture, called the permission-based security model (used e.g. in Android and Blackberry), entails intrinsic risks. For instance, applications can be granted more permissions than they actually need, what we call a "permission gap". Malware can leverage the unused permissions for achieving their malicious goals, for instance using code injection. In this paper, we present an approach to detecting permission gaps using static analysis. Our prototype implementation in the context of Android shows that the static analysis must take into account a significant amount of platform-specific knowledge. Using our tool on two datasets of Android applications, we found out that a non negligible part of applications suffers from permission gaps, i.e. does not use all the permissions they declare.
On the Feasibility of Linear Interference Alignment for MIMO Interference Broadcast Channels with Constant Coefficients
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we analyze the feasibility of linear interference alignment (IA) for multi-input-multi-output (MIMO) interference broadcast channel (MIMO-IBC) with constant coefficients. We pose and prove the necessary conditions of linear IA feasibility for general MIMO-IBC. Except for the proper condition, we find another necessary condition to ensure a kind of irreducible interference to be eliminated. We then prove the necessary and sufficient conditions for a special class of MIMO-IBC, where the numbers of antennas are divisible by the number of data streams per user. Since finding an invertible Jacobian matrix is crucial for the sufficiency proof, we first analyze the impact of sparse structure and repeated structure of the Jacobian matrix. Considering that for the MIMO-IBC the sub-matrices of the Jacobian matrix corresponding to the transmit and receive matrices have different repeated structure, we find an invertible Jacobian matrix by constructing the two sub-matrices separately. We show that for the MIMO-IBC where each user has one desired data stream, a proper system is feasible. For symmetric MIMO-IBC, we provide proper but infeasible region of antenna configurations by analyzing the difference between the necessary conditions and the sufficient conditions of linear IA feasibility.
Cups Products in Z2-Cohomology of 3D Polyhedral Complexes
Venue: arXiv cs.CV 2013
Year: 2013

Let $I=(\mathbb{Z}^3,26,6,B)$ be a 3D digital image, let $Q(I)$ be the associated cubical complex and let $\partial Q(I)$ be the subcomplex of $Q(I)$ whose maximal cells are the quadrangles of $Q(I)$ shared by a voxel of $B$ in the foreground -- the object under study -- and by a voxel of $\mathbb{Z}^3\smallsetminus B$ in the background -- the ambient space. We show how to simplify the combinatorial structure of $\partial Q(I)$ and obtain a 3D polyhedral complex $P(I)$ homeomorphic to $\partial Q(I)$ but with fewer cells. We introduce an algorithm that computes cup products on $H^*(P(I);\mathbb{Z}_2)$ directly from the combinatorics. The computational method introduced here can be effectively applied to any polyhedral complex embedded in $\mathbb{R}^3$.