OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Inter-Cell Interference Mitigation Via Joint Scheduling and Power Control Under Noise Rise Constraints
Venue: arXiv cs.NI 2013
Year: 2013

Consider the problem of joint uplink scheduling and power allocation. Being inherent to almost any wireless system, this resource allocation problem has received extensive attention. Yet, most common techniques either adopt classical power control, in which mobile stations are received with the same Signal-to-Interference-plus-Noise Ratio, or use centralized schemes, in which base stations coordinate their allocations. In this work, we suggest a novel scheduling approach in which each base station, besides allocating the time and frequency according to given constraints, also manages its uplink power budget such that the aggregate interference, "Noise Rise", caused by its subscribers at the neighboring cells is bounded. Our suggested scheme is distributed, requiring neither coordination nor message exchange. We rigorously define the allocation problem under noise rise constraints, give the optimal solution and derive an efficient iterative algorithm to achieve it. We then discuss a relaxed problem, where the noise rise is constrained separately for each sub-channel or resource unit. While sub-optimal, this view renders the scheduling and power allocation problems separate, yielding an even simpler and more efficient solution, while the essence of the scheme is kept. Via extensive simulations, we show that the suggested approach increases overall performance dramatically, with the same level of fairness and power consumption.
Symmetries of Quasi-Values
Venue: arXiv cs.GT 2013
Year: 2013

According to Shapley's game-theoretical result, there exists a unique game value of finite cooperative games that satisfies axioms on additivity, efficiency, null-player property and symmetry. The original setting requires symmetry with respect to arbitrary permutations of players. We analyze the consequences of weakening the symmetry axioms and study quasi-values that are symmetric with respect to permutations from a group $G\leq S_n$. We classify all the permutation groups $G$ that are large enough to assure a unique $G$-symmetric quasi-value, as well as the structure and dimension of the space of all such quasi-values for a general permutation group $G$. We show how to construct $G$-symmetric quasi-values algorithmically by averaging certain basic quasi-values (marginal operators).
Generalization Bounds for Metric and Similarity Learning
Venue: arXiv cs.LG 2013
Year: 2013

Recently, metric learning and similarity learning have attracted a large amount of interest. Many models and optimisation algorithms have been proposed. However, there is relatively little work on the generalization analysis of such methods. In this paper, we derive novel generalization bounds of metric and similarity learning. In particular, we first show that the generalization analysis reduces to the estimation of the Rademacher average over "sums-of-i.i.d." sample-blocks related to the specific matrix norm. Then, we derive generalization bounds for metric/similarity learning with different matrix-norm regularisers by estimating their specific Rademacher complexities. Our analysis indicates that sparse metric/similarity learning with $L^1$-norm regularisation could lead to significantly better bounds than those with Frobenius-norm regularisation. Our novel generalization analysis develops and refines the techniques of U-statistics and Rademacher complexity analysis.
Distance Distributions in Regular Polygons
Venue: arXiv cs.IT 2013
Year: 2013

This paper derives the exact cumulative density function of the distance between a randomly located node and any arbitrary reference point inside a regular $\el$-sided polygon. Using this result, we obtain the closed-form probability density function (PDF) of the Euclidean distance between any arbitrary reference point and its $n$-th neighbour node, when $N$ nodes are uniformly and independently distributed inside a regular $\ell$-sided polygon. First, we exploit the rotational symmetry of the regular polygons and quantify the effect of polygon sides and vertices on the distance distributions. Then we propose an algorithm to determine the distance distributions given any arbitrary location of the reference point inside the polygon. For the special case when the arbitrary reference point is located at the center of the polygon, our framework reproduces the existing result in the literature.
Degrees of Freedom of MIMO X Networks: Spatial Scale Invariance, One-Sided Decomposability and Linear Feasibility
Venue: arXiv cs.IT 2013
Year: 2013

We show that an M X N user MIMO X network with A antennas at each node has AMN/(M+N-1) degrees of freedom (DoF), thus resolving in this case a discrepancy between the spatial scale invariance conjecture (scaling the number of antennas at each node by a constant factor will scale the total DoF by the same factor) and a decomposability property of overconstrained wireless networks. While the best previously-known general DoF outer bound is consistent with the spatial invariance conjecture, the best previously-known general DoF inner bound, inspired by the K user MIMO interference channel, was based on the decomposition of every transmitter and receiver into multiple single antenna nodes, transforming the network into an AM X AN user SISO X network. While such a decomposition is DoF optimal for the K user MIMO interference channel, a gap remained between the best inner and outer bound for the MIMO X channel. Here we close this gap with the new insight that the MIMO X network is only one-sided decomposable, i.e., either all the transmitters or all the receivers (but not both) can be decomposed by splitting multiple antenna nodes into multiple single antenna nodes without loss of DoF. The result is extended to SIMO and MISO X networks as well and in each case the DoF results satisfy the spatial scale invariance property. In addition, the feasibility of linear interference alignment is investigated based only on spatial beamforming without symbol extensions. Similar to MIMO interference networks, we show that when the problem is improper, it is infeasible.
An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction
Venue: arXiv cs.LO 2013
Year: 2013

We prove an algebraic preservation theorem for positive Horn definability in aleph-zero categorical structures. In particular, we define and study a construction which we call the periodic power of a structure, and define a periomorphism of a structure to be a homomorphism from the periodic power of the structure to the structure itself. Our preservation theorem states that, over an aleph-zero categorical structure, a relation is positive Horn definable if and only if it is preserved by all periomorphisms of the structure. We give applications of this theorem, including a new proof of the known complexity classification of quantified constraint satisfaction on equality templates.
Distributed Broadcasting in Wireless Networks under the SINR Model
Venue: arXiv cs.DC 2013
Year: 2013

In the advent of large-scale multi-hop wireless technologies, such as MANET, VANET, iThings, it is of utmost importance to devise efficient distributed protocols to maintain network architecture and provide basic communication tools. One of such fundamental communication tasks is broadcast, also known as a 1-to-all communication. We propose several new efficient distributed algorithms and evaluate their time performance both theoretically and by simulations. First randomized algorithm accomplishes broadcast in O(D+log(1/d)) rounds with probability at least 1-d on any uniform-power network of n nodes and diameter D, when equipped with local estimate of network density. Additionally, we evaluate average performance of this protocols by simulations on two classes of generated networks - uniform and social - and compare the results with performance of exponential backoff heuristic. Ours is the first provably efficient and well-scalable distributed solution for the (global) broadcast task. The second randomized protocol developed in this paper does not rely on the estimate of local density, and achieves only slightly higher time performance O((D+log(1/d))log n). Finally, we provide a deterministic algorithm achieving similar time O(D log^2 n), supported by theoretical analysis.
Hamming Approximation of NP Witnesses
Venue: arXiv cs.CC 2013
Year: 2013

Given a satisfiable 3-SAT formula, how hard is it to find an assignment to the variables that has Hamming distance at most n/2 to a satisfying assignment? More generally, consider any polynomial-time verifier for any NP-complete language. A d(n)-Hamming-approximation algorithm for the verifier is one that, given any member x of the language, outputs in polynomial time a string a with Hamming distance at most d(n) to some witness w, where (x,w) is accepted by the verifier. Previous results have shown that, if P != NP, then every NP-complete language has a verifier for which there is no (n/2-n^(2/3+d))-Hamming-approximation algorithm, for various constants d > 0. Our main result is that, if P != NP, then every paddable NP-complete language has a verifier that admits no (n/2+O(sqrt(n log n)))-Hamming-approximation algorithm. That is, one cannot get even half the bits right. We also consider natural verifiers for various well-known NP-complete problems. They do have n/2-Hamming-approximation algorithms, but, if P != NP, have no (n/2-n^epsilon)-Hamming-approximation algorithms for any constant epsilon > 0. We show similar results for randomized algorithms.
Linear Time Algorithm for Optimal Feed-link Placement
Venue: arXiv cs.CG 2013
Year: 2013

Given a polygon representing a transportation network together with a point p in its interior, we aim to extend the network by inserting a line segment, called a feed-link, which connects p to the boundary of the polygon. Once a feed link is fixed, the geometric dilation of some point q on the boundary is the ratio between the length of the shortest path from p to q through the extended network, and their Euclidean distance. The utility of a feed-link is inversely proportional to the maximal dilation over all boundary points. We give a linear time algorithm for computing the feed-link with the minimum overall dilation, thus improving upon the previously known algorithm of complexity that is roughly O(n log n).
An Upper Bound on the Convergence Time for Distributed Binary Consensus
Venue: arXiv cs.PF 2013
Year: 2013

The problem addressed in this paper is the analysis of a distributed consensus algorithm for arbitrary networks, proposed by Bénézit et al.. In the initial setting, each node in the network has one of two possible states ("yes" or "no"). Nodes can update their states by communicating with their neighbors via a 2-bit message in an asynchronous clock setting. Eventually, all nodes reach consensus on the majority states. We use the theory of electric networks, random walks, and couplings of Markov chains to derive an O(N4 logN) upper bound for the expected convergence time on an arbitrary graph of size N.
A Random Walk Based Model Incorporating Social Information for Recommendations
Venue: arXiv cs.IR 2013
Year: 2013

Collaborative filtering (CF) is one of the most popular approaches to build a recommendation system. In this paper, we propose a hybrid collaborative filtering model based on a Makovian random walk to address the data sparsity and cold start problems in recommendation systems. More precisely, we construct a directed graph whose nodes consist of items and users, together with item content, user profile and social network information. We incorporate user's ratings into edge settings in the graph model. The model provides personalized recommendations and predictions to individuals and groups. The proposed algorithms are evaluated on MovieLens and Epinions datasets. Experimental results show that the proposed methods perform well compared with other graph-based methods, especially in the cold start case.
The Best Answers? Think Twice: Online Detection of Commercial Campaigns in the CQA Forums
Venue: arXiv cs.IR 2013
Year: 2013

In an emerging trend, more and more Internet users search for information from Community Question and Answer (CQA) websites, as interactive communication in such websites provides users with a rare feeling of trust. More often than not, end users look for instant help when they browse the CQA websites for the best answers. Hence, it is imperative that they should be warned of any potential commercial campaigns hidden behind the answers. However, existing research focuses more on the quality of answers and does not meet the above need. In this paper, we develop a system that automatically analyzes the hidden patterns of commercial spam and raises alarms instantaneously to end users whenever a potential commercial campaign is detected. Our detection method integrates semantic analysis and posters' track records and utilizes the special features of CQA websites largely different from those in other types of forums such as microblogs or news reports. Our system is adaptive and accommodates new evidence uncovered by the detection algorithms over time. Validated with real-world trace data from a popular Chinese CQA website over a period of three months, our system shows great potential towards adaptive online detection of CQA spams.
Offloading in Heterogeneous Networks: Modeling, Analysis, and Design Insights
Venue: arXiv cs.IT 2013
Year: 2013

Pushing data traffic from cellular to WiFi is an example of inter radio access technology (RAT) offloading. While this clearly alleviates congestion on the over-loaded cellular network, the ultimate potential of such offloading and its effect on overall system performance is not well understood. To address this, we develop a general and tractable model that consists of $M$ different RATs, each deploying up to $K$ different tiers of access points (APs), where each tier differs in transmit power, path loss exponent, deployment density and bandwidth. Each class of APs is modeled as an independent Poisson point process (PPP), with mobile user locations modeled as another independent PPP, all channels further consisting of i.i.d. Rayleigh fading. The distribution of rate over the entire network is then derived for a weighted association strategy, where such weights can be tuned to optimize a particular objective. We show that the optimum fraction of traffic offloaded to maximize $\SINR$ coverage is not in general the same as the one that maximizes rate coverage, defined as the fraction of users achieving a given rate.
Inverse Reinforcement Learning with Gaussian Process
Venue: arXiv cs.LG 2013
Year: 2013

We present new algorithms for inverse reinforcement learning (IRL, or inverse optimal control) in convex optimization settings. We argue that finite-space IRL can be posed as a convex quadratic program under a Bayesian inference framework with the objective of maximum a posterior estimation. To deal with problems in large or even infinite state space, we propose a Gaussian process model and use preference graphs to represent observations of decision trajectories. Our method is distinguished from other approaches to IRL in that it makes no assumptions about the form of the reward function and yet it retains the promise of computationally manageable implementations for potential real-world applications. In comparison with an establish algorithm on small-scale numerical problems, our method demonstrated better accuracy in apprenticeship learning and a more robust dependence on the number of observations.
The Complexity of the Comparator Circuit Value Problem
Venue: arXiv cs.CC 2013
Year: 2013

In 1990 Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL \subseteq CC \subseteq P, and proved that in addition to CCV several other problems are complete for CC, including the stable marriage problem, and finding the lexicographically first maximal matching in a bipartite graph. We are interested in CC because we conjecture that it is incomparable with the parallel class NC which also satisfies NL \subseteq NC \subseteq P, and note that this conjecture implies that none of the CC-complete problems has an efficient polylog time parallel algorithm. We provide evidence for our conjecture by giving oracle settings in which relativized CC and relativized NC are incomparable. We give several alternative definitions of CC, including (among others) the class of problems computed by uniform polynomial-size families of comparator circuits supplied with copies of the input and its negation, the class of problems AC^0-reducible to CCV, and the class of problems computed by uniform AC^0 circuits with CCV gates. We also give a machine model for CC, which corresponds to its characterization as log-space uniform polynomial-size families of comparator circuits. These various characterizations show that CC is a robust class. The main technical tool we employ is universal comparator circuits. Other results include a simpler proof of NL \subseteq CC, and an explanation of the relation between the Gale-Shapley algorithm and Subramanian's algorithm for stable marriage. This paper continues the previous work of Cook, Lê and Ye which focused on Cook-Nguyen style uniform proof complexity, answering several open questions raised in that paper.
Analysis and Construction of Functional Regenerating Codes with Uncoded Repair for Distributed Storage Systems
Venue: arXiv cs.IT 2013
Year: 2013

Modern distributed storage systems apply redundancy coding techniques to stored data. One form of redundancy is based on regenerating codes, which can minimize the repair bandwidth, i.e., the amount of data transferred when repairing a failed storage node. Existing regenerating codes mainly require surviving storage nodes encode data during repair. In this paper, we study functional minimum storage regenerating (FMSR) codes, which enable uncoded repair without the encoding requirement in surviving nodes, while preserving the minimum repair bandwidth guarantees and also minimizing disk reads. Under double-fault tolerance settings, we formally prove the existence of FMSR codes, and provide a deterministic FMSR code construction that can significantly speed up the repair process. We further implement and evaluate our deterministic FMSR codes to show the benefits. Our work is built atop a practical cloud storage system that implements FMSR codes, and we provide theoretical validation to justify the practicality of FMSR codes.
A differential Lyapunov framework for contraction analysis
Venue: arXiv cs.SY 2013
Year: 2013

Lyapunov's second theorem is an essential tool for stability analysis of differential equations. The paper provides an analog theorem for incremental stability analysis by lifting the Lyapunov function to the tangent bundle. The Lyapunov function endows the state-space with a Finsler structure. Incremental stability is inferred from infinitesimal contraction of the Finsler metrics through integration along solutions curves.
First-Passage Time and Large-Deviation Analysis for Erasure Channels with Memory
Venue: arXiv cs.IT 2013
Year: 2013

This article considers the performance of digital communication systems transmitting messages over finite-state erasure channels with memory. Information bits are protected from channel erasures using error-correcting codes; successful receptions of codewords are acknowledged at the source through instantaneous feedback. The primary focus of this research is on delay-sensitive applications, codes with finite block lengths and, necessarily, non-vanishing probabilities of decoding failure. The contribution of this article is twofold. A methodology to compute the distribution of the time required to empty a buffer is introduced. Based on this distribution, the mean hitting time to an empty queue and delay-violation probabilities for specific thresholds can be computed explicitly. The proposed techniques apply to situations where the transmit buffer contains a predetermined number of information bits at the onset of the data transfer. Furthermore, as additional performance criteria, large deviation principles are obtained for the empirical mean service time and the average packet-transmission time associated with the communication process. This rigorous framework yields a pragmatic methodology to select code rate and block length for the communication unit as functions of the service requirements. Examples motivated by practical systems are provided to further illustrate the applicability of these techniques.
Impedance mismatch is not an "Objects vs. Relations" problem
Venue: arXiv cs.DB 2013
Year: 2013

A problem of impedance mismatch between applications written in OO languages and relational DB is not a problem of discrepancy between object-oriented and relational approaches themselves. Its real causes can be found in usual implementation of the OO approach. Direct comparison of the two approaches cannot be used as a base for the conclusion that they are discrepant or mismatched. Experimental proof of absence of contradiction between object-oriented paradigm and relational data model is also presented
Improved Successive Cancellation Decoding of Polar Codes
Venue: arXiv cs.IT 2013
Year: 2013

As improved versions of successive cancellation (SC) decoding algorithm, successive cancellation list (SCL) decoding and successive cancellation stack (SCS) decoding are used to improve the finite-length performance of polar codes. Unified descriptions of SC, SCL and SCS decoding algorithms are given as path searching procedures on the code tree of polar codes. Combining the ideas of SCL and SCS, a new decoding algorithm named successive cancellation hybrid (SCH) is proposed, which can achieve a better trade-off between computational complexity and space complexity. Further, to reduce the complexity, a pruning technique is proposed to avoid unnecessary path searching operations. Performance and complexity analysis based on simulations show that, with proper configurations, all the three improved successive cancellation (ISC) decoding algorithms can have a performance very close to that of maximum-likelihood (ML) decoding with acceptable complexity. Moreover, with the help of the proposed pruning technique, the complexities of ISC decoders can be very close to that of SC decoder in the moderate and high signal-to-noise ratio (SNR) regime.
A Quantitative Study of Social Organisation in Open Source Software Communities
Venue: arXiv cs.SE 2013
Year: 2013

The success of open source projects crucially depends on the voluntary contributions of a sufficiently large community of users. Apart from the mere size of the community, interesting questions arise when looking at the evolution of structural features of collaborations between community members. In this article, we discuss several network analytic proxies that can be used to quantify different aspects of the social organisation in social collaboration networks. We particularly focus on measures that can be related to the cohesiveness of the communities, the distribution of responsibilities and the resilience against turnover of community members. We present a comparative analysis on a large-scale dataset that covers the full history of collaborations between users of 14 major open source software communities. Our analysis covers both aggregate and time-evolving measures and highlights differences in the social organisation across communities. We argue that our results are a promising step towards the definition of suitable, potentially multi-dimensional, resilience and risk indicators for open source software communities.