OpenRaiser/Intern-Atlas huggingface dataset:
The Two-user Causal Cognitive Interference Channel: Novel Outer Bounds and Constant Gap Result for the Symmetric Gaussian Noise Channel in Weak Interference
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the two-user Causal Cognitive Interference Channel (CCIC), where two transmitters aim to communicate independent messages to two different receivers via a common channel. One source, referred to as the cognitive, is capable of overhearing the other source, referred to as the primary, through a noisy in-band link and thus can assist in sending the primary's data. Two novel outer bounds of the type $2R_p+R_c$ and $R_p+2R_c$ are derived for the class of injective semi-deterministic CCICs where the noises at the different source-destination pairs are independent. An achievable rate region is derived based on Gelfand-Pinsker binning, superposition coding and simultaneous decoding at the receivers. The lower and outer bounds are then specialized to the practically relevant Gaussian noise case. The authors of this paper recently characterized to within a constant gap the capacity of the symmetric Gaussian CCIC in (a) the strong interference regime, and (b) for a subset of the weak interference regime when the cooperation link is larger than a given threshold. This work characterizes to within a constant gap the capacity for the symmetric Gaussian CCIC in the regime that was still open. In particular, it is shown that the novel outer bounds are necessary to characterize the capacity to within a constant gap when the cooperation link is weaker than the direct links, that is, in this regime unilateral cooperation leaves some system resources underutilized.
A Tale of Two Mechanisms: Incentivizing Investments in Security Games
Venue: arXiv cs.GT 2015
Year: 2015

In a system of interdependent users, the security of an entity is affected not only by that user's investment in security measures, but also by the positive externality of the security decisions of (some of) the other users. The provision of security in such system is therefore modeled as a public good provision problem, and is referred to as a security game. In this paper, we compare two well-known incentive mechanisms in this context for incentivizing optimal security investments among users, namely the Pivotal and the Externality mechanisms. The taxes in a Pivotal mechanism are designed to ensure users' voluntary participation, while those in an Externality mechanism are devised to maintain a balanced budget. We first show the more general result that, due to the non-excludable nature of security, no mechanism can incentivize the socially optimal investment profile, while at the same time ensuring voluntary participation and maintaining a balanced budget for all instances of security games. To further illustrate, we apply the Pivotal and Externality mechanisms to the special case of weighted total effort interdependence models, and identify some of the effects of varying interdependency between users on the budget deficit in the Pivotal mechanism, as well as on the participation incentives in the Externality mechanism.
Router-level community structure of the Internet Autonomous Systems
Venue: arXiv cs.NI 2015
Year: 2015

The Internet is composed of routing devices connected between them and organized into independent administrative entities: the Autonomous Systems. The existence of different types of Autonomous Systems (like large connectivity providers, Internet Service Providers or universities) together with geographical and economical constraints, turns the Internet into a complex modular and hierarchical network. This organization is reflected in many properties of the Internet topology, like its high degree of clustering and its robustness. In this work, we study the modular structure of the Internet router-level graph in order to assess to what extent the Autonomous Systems satisfy some of the known notions of community structure. We show that the modular structure of the Internet is much richer than what can be captured by the current community detection methods, which are severely affected by resolution limits and by the heterogeneity of the Autonomous Systems. Here we overcome this issue by using a multiresolution detection algorithm combined with a small sample of nodes. We also discuss recent work on community structure in the light of our results.
Precoder Design with Limited Feedback and Backhauling for Joint Transmission
Venue: arXiv cs.IT 2015
Year: 2015

A centralized coordinated multipoint downlink joint transmission in a frequency division duplex system requires channel state information (CSI) to be fed back from the cell-edge users to their serving BS, and aggregated at the central coordination node for precoding, so that interference can be mitigated. The control signals comprising of CSI and the precoding weights can easily overwhelm the backhaul resources. Relative thresholding has been proposed to alleviate the burden; however, this is at the cost of reduction in throughput. In this paper, we propose utilizing the long term channel statistics comprising of pathloss and shadow fading in the precoder design to model the statistical interference for the unknown CSI. In this regard, a successive second order cone programming (SSOCP) based precoder for maximizing the weighted sum rate is proposed. The accuracy of the solution obtained is bounded with the branch and bound technique. An alternative optimization framework via weighted mean square error minimization is also derived. Both these approaches provide an efficient solution close to the optimal, and also achieve efficient backhauling, in a sense that the precoding weights are generated only for the active links. For comparison, a stochastic approach based on particle swarm optimization is also considered.
Unsupervised authorship attribution
Venue: arXiv cs.CL 2015
Year: 2015

We describe a technique for attributing parts of a written text to a set of unknown authors. Nothing is assumed to be known a priori about the writing styles of potential authors. We use multiple independent clusterings of an input text to identify parts that are similar and dissimilar to one another. We describe algorithms necessary to combine the multiple clusterings into a meaningful output. We show results of the application of the technique on texts having multiple writing styles.
Indoor Localization Algorithm For Smartphones
Venue: arXiv cs.NI 2015
Year: 2015

Increasing sources of sensor measurements and prior knowledge have become available for indoor localization on smartphones. How to effectively utilize these sources for enhancing localization accuracy is an important yet challenging problem. In this paper, we present an area state-aided localization algorithm that exploits various sources of information. Specifically, we introduce the concept of area state to indicate the area where the user is on an indoor map. The position of the user is then estimated using inertial measurement unit (IMU) measurements with the aid of area states. The area states are in turn updated based on the position estimates. To avoid accumulated errors of IMU measurements, our algorithm uses WiFi received signal strength indicator (RSSI) to indicate the vicinity of the user to the routers. The experiment results show that our system can achieve satisfactory localization accuracy in a typical indoor environment.
Robust Eye Centers Localization with Zero--Crossing Encoded Image Projections
Venue: arXiv cs.CV 2015
Year: 2015

This paper proposes a new framework for the eye centers localization by the joint use of encoding of normalized image projections and a Multi Layer Perceptron (MLP) classifier. The encoding is novel and it consists in identifying the zero-crossings and extracting the relevant parameters from the resulting modes. The compressed normalized projections produce feature descriptors that are inputs to a properly-trained MLP, for discriminating among various categories of image regions. The proposed framework forms a fast and reliable system for the eye centers localization, especially in the context of face expression analysis in unconstrained environments. We successfully test the proposed method on a wide variety of databases including BioID, Cohn-Kanade, Extended Yale B and Labelled Faces in the Wild (LFW) databases.
Log-concavity and lower bounds for arithmetic circuits
Venue: arXiv cs.CC 2015
Year: 2015

One question that we investigate in this paper is, how can we build log-concave polynomials using sparse polynomials as building blocks? More precisely, let $f = \sum\_{i = 0}^d a\_i X^i \in \mathbb{R}^+[X]$ be a polynomial satisfying the log-concavity condition $a\_i^2 \textgreater{} τa\_{i-1}a\_{i+1}$ for every $i \in \{1,\ldots,d-1\},$ where $τ\textgreater{} 0$. Whenever $f$ can be written under the form $f = \sum\_{i = 1}^k \prod\_{j = 1}^m f\_{i,j}$ where the polynomials $f\_{i,j}$ have at most $t$ monomials, it is clear that $d \leq k t^m$. Assuming that the $f\_{i,j}$ have only non-negative coefficients, we improve this degree bound to $d = \mathcal O(k m^{2/3} t^{2m/3} {\rm log^{2/3}}(kt))$ if $τ\textgreater{} 1$, and to $d \leq kmt$ if $τ= d^{2d}$. This investigation has a complexity-theoretic motivation: we show that a suitable strengthening of the above results would imply a separation of the algebraic complexity classes VP and VNP. As they currently stand, these results are strong enough to provide a new example of a family of polynomials in VNP which cannot be computed by monotone arithmetic circuits of polynomial size.
Voting Behaviour and Power in Online Democracy: A Study of LiquidFeedback in Germany's Pirate Party
Venue: arXiv cs.CY 2015
Year: 2015

In recent years, political parties have adopted Online Delegative Democracy platforms such as LiquidFeedback to organise themselves and their political agendas via a grassroots approach. A common objection against the use of these platforms is the delegation system, where a user can delegate his vote to another user, giving rise to so-called super-voters, i.e. powerful users who receive many delegations. It has been asserted in the past that the presence of these super-voters undermines the democratic process, and therefore delegative democracy should be avoided. In this paper, we look at the emergence of super-voters in the largest delegative online democracy platform worldwide, operated by Germany's Pirate Party. We investigate the distribution of power within the party systematically, study whether super-voters exist, and explore the influence they have on the outcome of votings conducted online. While we find that the theoretical power of super-voters is indeed high, we also observe that they use their power wisely. Super-voters do not fully act on their power to change the outcome of votes, but they vote in favour of proposals with the majority of voters in many cases thereby exhibiting a stabilising effect on the system. We use these findings to present a novel class of power indices that considers observed voting biases and gives significantly better predictions than state-of-the-art measures.
Business Rule Mining from Spreadsheets
Venue: arXiv cs.SE 2015
Year: 2015

Business rules represent the knowledge that guides the operations of a business organization. They are implemented in software applications used by organizations, and the activity of extracting them from software is known as business rule mining. It has various purposes amongst which migration and generating documentation are the most common. However, apart from conventional software, organizations also use spreadsheets for a large part of their operations and decision-making activities. Therefore we believe that spreadsheets are also rich in business rules. We thus propose to develop an automated system for extracting business rules from spreadsheets in a human comprehensible natural language format. This position paper describes our motivation, the problem description, related work, and challenges we foresee.
A Survey of Manoeuvring Target Tracking Methods
Venue: arXiv cs.SY 2015
Year: 2015

A comprehensive review of the literature on manoeuvring target tracking for both uncluttered and cluttered measurements is presented. Various discrete-time dynamical models including non-random input, random-input and switching or hybrid system manoeuvre models are presented. The problem of manoeuvre detection is covered. Classical and current filtering methods for manoeuvre tracking are presented including multi-level process noise, input estimation, variable dimension filtering, two-stage filter, the interacting multiple model algorithm, and generalised pseudo-Bayesian algorithms. Various extensions of these algorithms to the case of cluttered measurements are also described and these include: joint manoeuvre and measurement association, probabilistic data association and multi-hypothesis tracking. Smoothing schemes, including IMM smoothing and batch expectation-maximisation using the Viterbi algorithm, are also described. The use of amplitude information for target measurement discrimination is discussed. It is noted that although many manoeuvre tacking techniques exist, the literature contains surprisingly few performance comparisons to guide the design engineer although a performance benchmark has recently been introduced.
D3-Tree: A Dynamic Distributed Deterministic Load - Balancer for decentralized tree structures
Venue: arXiv cs.DS 2015
Year: 2015

In this work, we propose D3-Tree, a dynamic distributed deterministic structure for data management in decentralized networks. We present in brief the theoretical algorithmic analysis, in which our proposed structure is based on, and we describe thoroughly the key aspects of the implementation. Conducting experiments, we verify that the implemented structure outperforms other well-known hierarchical tree-based structures, since it provides better complexities regarding load-balancing operations. More specifically, the structure achieves a logarithmic amortized bound, using an efficient deterministic load-balancing mechanism, which is general enough to be applied to other hierarchical tree-based structures. Moreover, we investigate the structure's fault tolerance, which hasn't been sufficiently tackled in previous work, both theoretically and through rigorous experimentation. We prove that D3-Tree is highly fault tolerant, since, even for massive node failures, it achieves a significant success rate in element queries. Afterwards we go one step further, in order to achieve sub-logarithmic complexity and propose the ART+ structure (Autonomous Range Tree), exploiting the excellent performance of D3-Tree. ART+ is a fully dynamic and fault-tolerant structure, which achieves sub-logarithmic performance for query and update operations and performs load-balancing in sub-logarithmic amortized cost.
Spread-Spectrum Based on Finite Field Fourier Transforms
Venue: arXiv cs.IT 2015
Year: 2015

Spread-spectrum systems are presented, which are based on Finite Field Fourier Transforms. Orthogonal spreading sequences defined over a finite field are derived. New digital multiplex schemes based on such spread-spectrum systems are also introduced, which are multilevel Coding Division Multiplex. These schemes termed Galois-field Division Multiplex (GDM) offer compact bandwidth requirements because only leaders of cyclotomic cosets are needed to be transmitted.
Revisable Justified Belief: Preliminary Report
Venue: arXiv cs.LO 2015
Year: 2015

The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision theory in which Boolean combinations of revisions are expressible in the language. We introduce a theory $\mathsf{JCDL}$ of Justified Conditional Doxastic Logic that replaces conditional belief formulas $B^ψφ$ by expressions $t{\,:^ψ}φ$ made up of a term $t$ whose syntactic structure suggests a derivation of the belief $φ$ after revision by $ψ$. This allows us to think of terms $t$ as reasons justifying a belief in various formulas after a revision takes place. We show that $\mathsf{JCDL}$-theorems are the exact analogs of $\mathsf{CDL}$-theorems, and that this result holds the other way around as well. This allows us to think of $\mathsf{JCDL}$ as a theory of revisable justified belief.
Statistical Network Topology for Crisis Informetrics
Venue: arXiv cs.SI 2015
Year: 2015

Crisis informetrics is considered to be a relatively new and emerging area of research, which deals with the application of analytical approaches of network and information science combined with experimental learning approaches of statistical mechanics to explore communication and information flow, robustness as well as tolerance of complex crisis networks under threats. In this paper, we discuss the scale free network property of an organizational communication network and test both traditional (static) and dynamic topology of social networks during organizational crises Both types of topologies exhibit similar characteristics of prominent actors reinforcing the power law distribution nature of scale free networks. There are no significant fluctuations among the actor prominence in daily and aggregated networks. We found that email communication network display a high degree of scale free behavior described by power law.
CIUV: Collaborating Information Against Unreliable Views
Venue: arXiv cs.DB 2015
Year: 2015

In many real world applications, the information of an object can be obtained from multiple sources. The sources may provide different point of views based on their own origin. As a consequence, conflicting pieces of information are inevitable, which gives rise to a crucial problem: how to find the truth from these conflicts. Many truth-finding methods have been proposed to resolve conflicts based on information trustworthy (i.e. more appearance means more trustworthy) as well as source reliability. However, the factor of men's involvement, i.e., information may be falsified by men with malicious intension, is more or less ignored in existing methods. Collaborating the possible relationship between information's origins and men's participation are still not studied in research. To deal with this challenge, we propose a method -- Collaborating Information against Unreliable Views (CIUV) --- in dealing with men's involvement for finding the truth. CIUV contains 3 stages for interactively mitigating the impact of unreliable views, and calculate the truth by weighting possible biases between sources. We theoretically analyze the error bound of CIUV, and conduct intensive experiments on real dataset for evaluation. The experimental results show that CIUV is feasible and has the smallest error compared with other methods.
Fair Scheduling Policies Exploiting Multiuser Diversity in Cellular Systems with Device-to-Device Communications
Venue: arXiv cs.IT 2015
Year: 2015

We consider the resource allocation problem in cellular networks which support Device-to-Device Communications (D2D). For systems that enable D2D via only orthogonal resource sharing, we propose and analyze two resource allocation policies that guarantee access fairness among all users, while taking advantage of multi-user diversity and local D2D communications, to provide marked improvements over existing cellular-only policies. The first policy, the Cellular Fairness Scheduling (CFS) Policy, provides the simplest D2D extension to existing cellular systems, while the second policy, the D2D Fairness Scheduling (DFS) Policy, harnesses maximal performance from D2D-enabled systems under the orthogonal sharing setting. For even higher spectral efficiency, cellular systems with D2D can schedule the same frequency resource for more than one D2D pairs. Under this non-orthogonal sharing environment, we propose a novel group scheduling policy, the Group Fairness Scheduling (GFS) Policy, that exploits both spatial frequency reuse and multiuser diversity in order to deliver dramatic improvements to system performance with perfect fairness among the users, regardless of whether they are cellular or D2D users.
Fast Optimal Transport Averaging of Neuroimaging Data
Venue: arXiv cs.CV 2015
Year: 2015

Knowing how the Human brain is anatomically and functionally organized at the level of a group of healthy individuals or patients is the primary goal of neuroimaging research. Yet computing an average of brain imaging data defined over a voxel grid or a triangulation remains a challenge. Data are large, the geometry of the brain is complex and the between subjects variability leads to spatially or temporally non-overlapping effects of interest. To address the problem of variability, data are commonly smoothed before group linear averaging. In this work we build on ideas originally introduced by Kantorovich to propose a new algorithm that can average efficiently non-normalized data defined over arbitrary discrete domains using transportation metrics. We show how Kantorovich means can be linked to Wasserstein barycenters in order to take advantage of an entropic smoothing approach. It leads to a smooth convex optimization problem and an algorithm with strong convergence guarantees. We illustrate the versatility of this tool and its empirical behavior on functional neuroimaging data, functional MRI and magnetoencephalography (MEG) source estimates, defined on voxel grids and triangulations of the folded cortical surface.
Liquid FM: Recommending Music through Viscous Democracy
Venue: arXiv cs.SI 2015
Year: 2015

Most modern recommendation systems use the approach of collaborative filtering: users that are believed to behave alike are used to produce recommendations. In this work we describe an application (Liquid FM) taking a completely different approach. Liquid FM is a music recommendation system that makes the user responsible for the recommended items. Suggestions are the result of a voting scheme, employing the idea of viscous democracy. Liquid FM can also be thought of as the first testbed for this voting system. In this paper we outline the design and architecture of the application, both from the theoretical and from the implementation viewpoints.
Generalized Integral Siding Mode Manifold Design: A Sum of Squares Approach
Venue: arXiv cs.SY 2015
Year: 2015

This paper presents a general form of integral sliding mode manifold, and proposes an algorithmic approach based on Sum of Squares (SOS) programming to design generalized integral sliding mode manifold and controller for nonlinear systems with both matched and unmatched uncertainties. The approach also gives a sufficient condition for successful design of controller and manifold parameters. The result of the paper is then verified by several simulation examples and two practical applications, namely Glucose-insulin regulation problem and the unicycle dynamics steering problem are considered.