OpenRaiser/Intern-Atlas huggingface dataset:
Data Survivability in Networks of Mobile Robots in Urban Disaster Environments
Venue: arXiv cs.RO 2013
Year: 2013

Mobile multi-robot teams deployed for monitoring or search-and-rescue missions in urban disaster areas can greatly improve the quality of vital data collected on-site. Analysis of such data can identify hazards and save lives. Unfortunately, such real deployments at scale are cost prohibitive and robot failures lead to data loss. Moreover, scaled-down deployments do not capture significant levels of interaction and communication complexity. To tackle this problem, we propose novel mobility and failure generation frameworks that allow realistic simulations of mobile robot networks for large scale disaster scenarios. Furthermore, since data replication techniques can improve the survivability of data collected during the operation, we propose an adaptive, scalable data replication technique that achieves high data survivability with low overhead. Our technique considers the anticipated robot failures and robot heterogeneity to decide how aggressively to replicate data. In addition, it considers survivability priorities, with some data requiring more effort to be saved than others. Using our novel simulation generation frameworks, we compare our adaptive technique with flooding and broadcast-based replication techniques and show that for failure rates of up to 60% it ensures better data survivability with lower communication costs.
Towards Swarm Calculus: Urn Models of Collective Decisions and Universal Properties of Swarm Performance
Venue: arXiv cs.NE 2013
Year: 2013

Methods of general applicability are searched for in swarm intelligence with the aim of gaining new insights about natural swarms and to develop design methodologies for artificial swarms. An ideal solution could be a `swarm calculus' that allows to calculate key features of swarms such as expected swarm performance and robustness based on only a few parameters. To work towards this ideal, one needs to find methods and models with high degrees of generality. In this paper, we report two models that might be examples of exceptional generality. First, an abstract model is presented that describes swarm performance depending on swarm density based on the dichotomy between cooperation and interference. Typical swarm experiments are given as examples to show how the model fits to several different results. Second, we give an abstract model of collective decision making that is inspired by urn models. The effects of positive feedback probability, that is increasing over time in a decision making system, are understood by the help of a parameter that controls the feedback based on the swarm's current consensus. Several applicable methods, such as the description as Markov process, calculation of splitting probabilities, mean first passage times, and measurements of positive feedback, are discussed and applications to artificial and natural swarms are reported.
Learning-Based Constraint Satisfaction With Sensing Restrictions
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we consider graph-coloring problems, an important subset of general constraint satisfaction problems that arise in wireless resource allocation. We constructively establish the existence of fully decentralized learning-based algorithms that are able to find a proper coloring even in the presence of strong sensing restrictions, in particular sensing asymmetry of the type encountered when hidden terminals are present. Our main analytic contribution is to establish sufficient conditions on the sensing behaviour to ensure that the solvers find satisfying assignments with probability one. These conditions take the form of connectivity requirements on the induced sensing graph. These requirements are mild, and we demonstrate that they are commonly satisfied in wireless allocation tasks. We argue that our results are of considerable practical importance in view of the prevalence of both communication and sensing restrictions in wireless resource allocation problems. The class of algorithms analysed here requires no message-passing whatsoever between wireless devices, and we show that they continue to perform well even when devices are only able to carry out constrained sensing of the surrounding radio environment.
A simpler load-balancing algorithm for range-partitioned data in peer-to-peer systems
Venue: arXiv cs.DC 2013
Year: 2013

Random hashing is a standard method to balance loads among nodes in Peer-to-Peer networks. However, hashing destroys locality properties of object keys, the critical properties to many applications, more specifically, those that require range searching. To preserve a key order while keeping loads balanced, Ganesan, Bawa and Garcia-Molina proposed a load-balancing algorithm that supports both object insertion and deletion that guarantees a ratio of 4.237 between the maximum and minimum loads among nodes in the network using constant amortized costs. However, their algorithm is not straightforward to implement in real networks because it is recursive. Their algorithm mostly uses local operations with global max-min load information. In this work, we present a simple non-recursive algorithm using essentially the same primitive operations as in Ganesan {\em et al.}'s work. We prove that for insertion and deletion, our algorithm guarantees a constant max-min load ratio of 7.464 with constant amortized costs.
Discovering Social Circles in Ego Networks
Venue: arXiv cs.SI 2013
Year: 2013

People's personal social networks are big and cluttered, and currently there is no good way to automatically organize them. Social networking sites allow users to manually categorize their friends into social circles (e.g. 'circles' on Google+, and 'lists' on Facebook and Twitter), however they are laborious to construct and must be updated whenever a user's network grows. In this paper, we study the novel task of automatically identifying users' social circles. We pose this task as a multi-membership node clustering problem on a user's ego-network, a network of connections between her friends. We develop a model for detecting circles that combines network structure as well as user profile information. For each circle we learn its members and the circle-specific user profile similarity metric. Modeling node membership to multiple circles allows us to detect overlapping as well as hierarchically nested circles. Experiments show that our model accurately identifies circles on a diverse set of data from Facebook, Google+, and Twitter, for all of which we obtain hand-labeled ground-truth.
Cryptanalysis of a New Knapsack Type Public-Key Cryptosystem
Venue: arXiv cs.CR 2013
Year: 2013

Recently, Hwang et al. introduced a knapsack type public-key cryptosystem. They proposed a new algorithm called permutation combination algorithm. By exploiting this algorithm, they attempt to increase the density of knapsack to avoid the low-density attack. We show that this cryptosystem is not secure, as it based on basic Merkel-Hellman knapsack cryptosystem and because of the superincreasing structure, we can use shamir's attack on the basic Merkel-Hellman knapsack to break this cryptosystem.
Super-Resolution from Noisy Data
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the recovery of a superposition of point sources from noisy bandlimited data. In the fewest possible words, we only have information about the spectrum of an object in a low-frequency band bounded by a certain cut-off frequency and seek to obtain a higher resolution estimate by extrapolating the spectrum up to a higher frequency. We show that as long as the sources are separated by twice the inverse of the cut-off frequency, solving a simple convex program produces a stable estimate in the sense that the approximation error between the higher-resolution reconstruction and the truth is proportional to the noise level times the square of the super-resolution factor (SRF), which is the ratio between the desired high frequency and the cut-off frequency of the data.
Large Deviation Delay Analysis of Queue-Aware Multi-user MIMO Systems with Multi-timescale Mobile-Driven Feedback
Venue: arXiv cs.SY 2013
Year: 2013

Multi-user multi-input-multi-output (MU-MIMO) systems transmit data to multiple users simultaneously using the spatial degrees of freedom with user feedback channel state information (CSI). Most of the existing literatures on the reduced feedback user scheduling focus on the throughput performance and the user queueing delay is usually ignored. As the delay is very important for real-time applications, a low feedback queue-aware user scheduling algorithm is desired for the MU-MIMO system. This paper proposed a two-stage queue-aware user scheduling algorithm, which consists of a queue-aware mobile-driven feedback filtering stage and a SINR-based user scheduling stage, where the feedback filtering policy is obtained from the solution of an optimization problem. We evaluate the queueing performance of the proposed scheduling algorithm by using the sample path large deviation analysis. We show that the large deviation decay rate for the proposed algorithm is much larger than that of the CSI-only user scheduling algorithm. The numerical results also demonstrate that the proposed algorithm performs much better than the CSI-only algorithm requiring only a small amount of feedback.
Learning using Local Membership Queries
Venue: arXiv cs.LG 2013
Year: 2013

We introduce a new model of membership query (MQ) learning, where the learning algorithm is restricted to query points that are \emph{close} to random examples drawn from the underlying distribution. The learning model is intermediate between the PAC model (Valiant, 1984) and the PAC+MQ model (where the queries are allowed to be arbitrary points). Membership query algorithms are not popular among machine learning practitioners. Apart from the obvious difficulty of adaptively querying labelers, it has also been observed that querying \emph{unnatural} points leads to increased noise from human labelers (Lang and Baum, 1992). This motivates our study of learning algorithms that make queries that are close to examples generated from the data distribution. We restrict our attention to functions defined on the $n$-dimensional Boolean hypercube and say that a membership query is local if its Hamming distance from some example in the (random) training data is at most $O(\log(n))$. We show the following results in this model: (i) The class of sparse polynomials (with coefficients in R) over $\{0,1\}^n$ is polynomial time learnable under a large class of \emph{locally smooth} distributions using $O(\log(n))$-local queries. This class also includes the class of $O(\log(n))$-depth decision trees. (ii) The class of polynomial-sized decision trees is polynomial time learnable under product distributions using $O(\log(n))$-local queries. (iii) The class of polynomial size DNF formulas is learnable under the uniform distribution using $O(\log(n))$-local queries in time $n^{O(\log(\log(n)))}$. (iv) In addition we prove a number of results relating the proposed model to the traditional PAC model and the PAC+MQ model.
Stochastic Combinatorial Optimization via Poisson Approximation
Venue: arXiv cs.DS 2013
Year: 2013

We study several stochastic combinatorial problems, including the expected utility maximization problem, the stochastic knapsack problem and the stochastic bin packing problem. A common technical challenge in these problems is to optimize some function of the sum of a set of random variables. The difficulty is mainly due to the fact that the probability distribution of the sum is the convolution of a set of distributions, which is not an easy objective function to work with. To tackle this difficulty, we introduce the Poisson approximation technique. The technique is based on the Poisson approximation theorem discovered by Le Cam, which enables us to approximate the distribution of the sum of a set of random variables using a compound Poisson distribution. We first study the expected utility maximization problem introduced recently [Li and Despande, FOCS11]. For monotone and Lipschitz utility functions, we obtain an additive PTAS if there is a multidimensional PTAS for the multi-objective version of the problem, strictly generalizing the previous result. For the stochastic bin packing problem (introduced in [Kleinberg, Rabani and Tardos, STOC97]), we show there is a polynomial time algorithm which uses at most the optimal number of bins, if we relax the size of each bin and the overflow probability by eps. For stochastic knapsack, we show a 1+eps-approximation using eps extra capacity, even when the size and reward of each item may be correlated and cancelations of items are allowed. This generalizes the previous work [Balghat, Goel and Khanna, SODA11] for the case without correlation and cancelation. Our algorithm is also simpler. We also present a factor 2+eps approximation algorithm for stochastic knapsack with cancelations. the current known approximation factor of 8 [Gupta, Krishnaswamy, Molinaro and Ravi, FOCS11].
Edge distribution in generalized graph products
Venue: arXiv cs.DM 2013
Year: 2013

Given a graph $G=(V,E)$, an integer $k$, and a function $f_G:V^k \times V^k \to {0,1}$, the $k^{th}$ graph product of $G$ w.r.t $f_G$ is the graph with vertex set $V^k$, and an edge between two vertices $x=(x_1,...,x_k)$ and $y=(y_1,...,y_k)$ iff $f_G(x,y)=1$. Graph products are a basic combinatorial object, widely studied and used in different areas such as hardness of approximation, information theory, etc. We study graph products for functions $f_G$ of the form $f_G(x,y)=1$ iff there are at least $t$ indices $i \in [k]$ s.t. $(x_i,y_i)\in E$, where $t \in [k]$ is a fixed parameter in $f_G$. This framework generalizes the well-known graph tensor-product (obtained for $t=k$) and the graph or-product (obtained for $t=1$). The property that interests us is the edge distribution in such graphs. We show that if $G$ has a spectral gap, then the number of edges connecting "large-enough" sets in $G^k$ is "well-behaved", namely, it is close to the expected value, had the sets been random. We extend our results to bi-partite graph products as well. For a bi-partite graph $G=(X,Y,E)$, the $k^{th}$ bi-partite graph product of $G$ w.r.t $f_G$ is the bi-partite graph with vertex sets $X^k$ and $Y^k$ and edges between $x \in X^k$ and $y \in Y^k$ iff $f_G(x,y)=1$. Finally, for both types of graph products, optimality is asserted using the "Converse to the Expander Mixing Lemma" obtained by Bilu and Linial in 2006. A byproduct of our proof technique is a new explicit construction of a family of co-spectral graphs.
K-Plane Regression
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we present a novel algorithm for piecewise linear regression which can learn continuous as well as discontinuous piecewise linear functions. The main idea is to repeatedly partition the data and learn a liner model in in each partition. While a simple algorithm incorporating this idea does not work well, an interesting modification results in a good algorithm. The proposed algorithm is similar in spirit to $k$-means clustering algorithm. We show that our algorithm can also be viewed as an EM algorithm for maximum likelihood estimation of parameters under a reasonable probability model. We empirically demonstrate the effectiveness of our approach by comparing its performance with the state of art regression learning algorithms on some real world datasets.
Accurate Sampling Timing Acquisition for Baseband OFDM Power-line Communication in Non-Gaussian Noise
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a novel technique is proposed to address the joint sampling timing acquisition for baseband and broadband power-line communication (BB-PLC) systems using Orthogonal-Frequency-Division-Multiplexing (OFDM), including the sampling phase offset (SPO) and the sampling clock offset (SCO). Under pairwise correlation and joint Gaussian assumption of received signals in frequency domain, an approximated form of the log-likelihood function is derived. Instead of a high complexity two-dimension grid-search on the likelihood function, a five-step method is employed for accurate estimations. Several variants are presented in the same framework with different complexities. Unlike conventional pilot-assisted schemes using the extra phase rotations within one OFDM block, the proposed technique turns to the phase rotations between adjacent OFDM blocks. Analytical expressions of the variances and biases are derived. Extensive simulation results indicate significant performance improvements over conventional schemes. Additionally, effects of several noise models including non-Gaussianity, cyclo-stationarity, and temporal correlation are analyzed and simulated. Robustness of the proposed technique against violation of the joint Gaussian assumption is also verified by simulations.
A Spectral Expression for the Frequency-Limited H2-norm
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, a new simple but yet efficient spectral expression of the frequency-limited H2-norm, denoted H2w-norm, is introduced. The proposed new formulation requires the computation of the system eigenvalues and eigenvectors only, and provides thus an alternative to the well established Gramian-based approach. The interest of this new formulation is in three-folds: (i) it provides a new theoretical framework for the H2w-norm-based optimization approach, such as controller synthesis, filter design and model approximation, (ii) it improves the H2w-norm computation velocity and it applicability to models of higher dimension, and (iii) under some conditions, it allows to handle systems with poles on the imaginary axis. Both mathematical proofs and numerical illustrations are provided to assess this new H2w-norm expression.
On the Inefficiency of the Uniform Price Auction
Venue: arXiv cs.GT 2013
Year: 2013

We present our results on Uniform Price Auctions, one of the standard sealed-bid multi-unit auction formats, for selling multiple identical units of a single good to multi-demand bidders. Contrary to the truthful and economically efficient multi-unit Vickrey auction, the Uniform Price Auction encourages strategic bidding and is socially inefficient in general. The uniform pricing rule is, however, widely popular by its appeal to the natural anticipation, that identical items should be identically priced. In this work we study equilibria of the Uniform Price Auction for bidders with (symmetric) submodular valuation functions, over the number of units that they win. We investigate pure Nash equilibria of the auction in undominated strategies; we produce a characterization of these equilibria that allows us to prove that a fraction 1-1/e of the optimum social welfare is always recovered in undominated pure Nash equilibrium -- and this bound is essentially tight. Subsequently, we study the auction under the incomplete information setting and prove a bound of 4-2/k on the economic inefficiency of (mixed) Bayes Nash equilibria that are supported by undominated strategies.
Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games
Venue: arXiv cs.GT 2013
Year: 2013

In this paper we show that the price of stability of Shapley network design games on undirected graphs with k players is at most (k^3(k+1)/2-k^2) / (1+k^3(k+1)/2-k^2) H_k = (1 - Θ(1/k^4)) H_k, where H_k denotes the k-th harmonic number. This improves on the known upper bound of H_k, which is also valid for directed graphs but for these, in contrast, is tight. Hence, we give the first non-trivial upper bound on the price of stability for undirected Shapley network design games that is valid for an arbitrary number of players. Our bound is proved by analyzing the price of stability restricted to Nash equilibria that minimize the potential function of the game. We also present a game with k=3 players in which such a restricted price of stability is 1.634. This shows that the analysis of Bilò and Bove (Journal of Interconnection Networks, Volume 12, 2011) is tight. In addition, we give an example for three players that improves the lower bound on the (unrestricted) price of stability to 1.571.
Belief Propagation Reconstruction for Discrete Tomography
Venue: arXiv cs.NA 2013
Year: 2013

We consider the reconstruction of a two-dimensional discrete image from a set of tomographic measurements corresponding to the Radon projection. Assuming that the image has a structure where neighbouring pixels have a larger probability to take the same value, we follow a Bayesian approach and introduce a fast message-passing reconstruction algorithm based on belief propagation. For numerical results, we specialize to the case of binary tomography. We test the algorithm on binary synthetic images with different length scales and compare our results against a more usual convex optimization approach. We investigate the reconstruction error as a function of the number of tomographic measurements, corresponding to the number of projection angles. The belief propagation algorithm turns out to be more efficient than the convex-optimization algorithm, both in terms of recovery bounds for noise-free projections, and in terms of reconstruction quality when moderate Gaussian noise is added to the projections.
Field-normalized Impact Factors: A Comparison of Rescaling versus Fractionally Counted IFs
Venue: arXiv cs.DL 2013
Year: 2013

Two methods for comparing impact factors and citation rates across fields of science are tested against each other using citations to the 3,705 journals in the Science Citation Index 2010 (CD-Rom version of SCI) and the 13 field categories used for the Science and Engineering Indicators of the US National Science Board. We compare (i) normalization by counting citations in proportion to the length of the reference list (1/N of references) with (ii) rescaling by dividing citation scores by the arithmetic mean of the citation rate of the cluster. Rescaling is analytical and therefore independent of the quality of the attribution to the sets, whereas fractional counting provides an empirical strategy for normalization among sets (by evaluating the between-group variance). By the fairness test of Radicchi & Castellano (2012a), rescaling outperforms fractional counting of citations for reasons that we consider.
Rotational Symmetry and the Transformation of Innovation Systems in a Triple Helix of University-Industry-Government Relations
Venue: arXiv cs.CY 2013
Year: 2013

Using a mathematical model, we show that a Triple Helix (TH) system contains self-interaction, and therefore self-organization of innovations can be expected in waves, whereas a Double Helix (DH) remains determined by its linear constituents. (The mathematical model is fully elaborated in the Appendices.) The ensuing innovation systems can be expected to have a fractal structure: innovation systems at different scales can be considered as spanned in a Cartesian space with the dimensions of (S)cience, (B)usiness, and (G)overnment. A national system, for example, contains sectorial and regional systems, and is a constituent part in technological and supra-national systems of innovation. The mathematical modeling enables us to clarify the mechanisms, and provides new possibilities for the prediction. Emerging technologies can be expected to be more diversified and their life cycles will become shorter than before. In terms of policy implications, the model suggests a shift from the production of material objects to the production of innovative technologies.