OpenRaiser/Intern-Atlas huggingface dataset:
Energy-Efficient Broadcasting for Cross Wireless Ad-Hoc Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we propose solutions for the energy-efficient broadcasting over cross networks, where N nodes are located on two perpendicular lines. Our solutions consist of an algorithm which finds the optimal range assignment in polynomial time (O(N^12)), a near-optimal algorithm with linear complexity (O(N)), and a distributed algorithm with complexity O(1). To the best of our knowledge, this is the first study presenting an optimal solution for the minimum-energy broadcasting problem for a 2-D network (with cross configuration). We compare our algorithms with the broadcast incremental power (BIP) algorithm, one of the most commonly used methods for solving this problem with complexity O(N^2). We demonstrate that our near-optimal algorithm outperforms BIP, and that the distributed algorithm performs close to it. Moreover, the proposed distributed algorithm can be used for more general two-dimensional networks, where the nodes are located on a grid consisting of perpendicular line-segments. The performance of the proposed near-optimal and distributed algorithms tend to be closer to the optimal solution for larger networks.
User-Centric Interference Nulling in Downlink Multi-Antenna Heterogeneous Networks
Venue: arXiv cs.IT 2015
Year: 2015

Heterogeneous networks (HetNets) have strong interference due to spectrum reuse. This affects the signal-to-interference ratio (SIR) of each user, and hence is one of the limiting factors of network performance. However, in previous works, interference management approaches in HetNets are mainly based on interference level, and thus cannot effectively utilize the limited resource to improve network performance. In this paper, we propose a user-centric interference nulling (IN) scheme in downlink two-tier HetNets to improve network performance by improving each user's SIR. This scheme has three design parameters: the maximum degree of freedom for IN (IN DoF), and the IN thresholds for the macro and pico users, respectively. Using tools from stochastic geometry, we first obtain a tractable expression of the coverage (equivalently outage) probability. Then, we characterize the asymptotic behavior of the outage probability in the high reliability regime. The asymptotic results show that the maximum IN DoF can affect the order gain of the asymptotic outage probability, while the IN thresholds only affect the coefficient of the asymptotic outage probability. Moreover, we show that the IN scheme can linearly improve the outage performance, and characterize the optimal maximum IN DoF which minimizes the asymptotic outage probability.
Reasoning about Unmodelled Concepts - Incorporating Class Taxonomies in Probabilistic Relational Models
Venue: arXiv cs.AI 2015
Year: 2015

A key problem in the application of first-order probabilistic methods is the enormous size of graphical models they imply. The size results from the possible worlds that can be generated by a domain of objects and relations. One of the reasons for this explosion is that so far the approaches do not sufficiently exploit the structure and similarity of possible worlds in order to encode the models more compactly. We propose fuzzy inference in Markov logic networks, which enables the use of taxonomic knowledge as a source of imposing structure onto possible worlds. We show that by exploiting this structure, probability distributions can be represented more compactly and that the reasoning systems become capable of reasoning about concepts not contained in the probabilistic knowledge base.
A Simple Algorithm for Approximation by Nomographic Functions
Venue: arXiv cs.IT 2015
Year: 2015

This paper introduces a novel algorithmic solution for the approximation of a given multivariate function by a nomographic function that is composed of a one-dimensional continuous and monotone outer function and a sum of univariate continuous inner functions. We show that a suitable approximation can be obtained by solving a cone-constrained Rayleigh-Quotient optimization problem. The proposed approach is based on a combination of a dimensionwise function decomposition known as Analysis of Variance (ANOVA) and optimization over a class of monotone polynomials. An example is given to show that the proposed algorithm can be applied to solve problems in distributed function computation over multiple-access channels.
Survey of Sybil Attacks in Social Networks
Venue: arXiv cs.CR 2015
Year: 2015

This paper reviews the Sybil attack in social networks, which has the potential to compromise the whole distributed network. In the Sybil attack, the malicious user claims multiple identities to compromise the network. Sybil attacks can be used to change the overall ranking in voting applications, bad-mouth an opinion, access resources or to break the trust mechanism behind a P2P network. In this paper, different defense mechanisms used to mitigate Sybil attacks are also reviewed.
Secret Key Generation with One Communicator and a One-Shot Converse via Hypercontractivity
Venue: arXiv cs.IT 2015
Year: 2015

A new model of multi-party secret key agreement is proposed, in which one terminal called the communicator can transmit public messages to other terminals before all terminals agree on a secret key. A single-letter characterization of the achievable region is derived in the stationary memoryless case. The new model generalizes some other (old and new) models of key agreement. In particular, key generation with an omniscient helper is the special case where the communicator knows all sources, for which we derive a zero-rate one-shot converse for the secret key per bit of communication.
Temporal-Difference Networks
Venue: arXiv cs.LG 2015
Year: 2015

We introduce a generalization of temporal-difference (TD) learning to networks of interrelated predictions. Rather than relating a single prediction to itself at a later time, as in conventional TD methods, a TD network relates each prediction in a set of predictions to other predictions in the set at a later time. TD networks can represent and apply TD learning to a much wider class of predictions than has previously been possible. Using a random-walk example, we show that these networks can be used to learn to predict by a fixed interval, which is not possible with conventional TD methods. Secondly, we show that if the inter-predictive relationships are made conditional on action, then the usual learning-efficiency advantage of TD methods over Monte Carlo (supervised learning) methods becomes particularly pronounced. Thirdly, we demonstrate that TD networks can learn predictive state representations that enable exact solution of a non-Markov problem. A very broad range of inter-predictive temporal relationships can be expressed in these networks. Overall we argue that TD networks represent a substantial extension of the abilities of TD methods and bring us closer to the goal of representing world knowledge in entirely predictive, grounded terms.
Formalizing Preference Utilitarianism in Physical World Models
Venue: arXiv cs.CY 2015
Year: 2015

Most ethical work is done at a low level of formality. This makes practical moral questions inaccessible to formal and natural sciences and can lead to misunderstandings in ethical discussion. In this paper, we use Bayesian inference to introduce a formalization of preference utilitarianism in physical world models, specifically cellular automata. Even though our formalization is not immediately applicable, it is a first step in providing ethics and ultimately the question of how to "make the world better" with a formal basis.
The Impact of Physical Channel on Performance of Subspace-Based Channel Estimation in Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

A subspace method for channel estimation has been recently proposed [1] for tackling the pilot contamination effect, which is regarded by some researchers as a bottleneck in massive MIMO systems. It was shown in [1] that if the power ratio between the desired signal and interference is kept above a certain value, the received signal spectrum splits into signal and interference eigenvalues, namely, the "pilot contamination" effect can be completely eliminated. However, [1] assumes an independently distributed (i.d.) channel, which is actually not much the case in practice. Considering this, a more sensible finite-dimensional physical channel model (i.e., a finite scattering environment, where signals impinge on the base station (BS) from a finite number of angles of arrival (AoA)) is employed in this paper. Via asymptotic spectral analysis, it is demonstrated that, compared with the i.d. channel, the physical channel imposes a penalty in the form of an increased power ratio between the useful signal and the interference. Furthermore, we demonstrate an interesting "antenna saturation" effect, i.e., when the number of the BS antennas approaches infinity, the performance under the physical channel with P AoAs is limited by and nearly the same as the performance under the i.d. channel with P receive antennas.
Theoretical Aspects of a Design Method for Programmable NMR Voters
Venue: arXiv cs.DC 2015
Year: 2015

Almost all dependable systems use some form of redundancy in order to increase fault-tolerance. Very popular are the $N$-Modular Redundant (NMR) systems in which a majority voter chooses the voting output. However, elaborate systems require fault-tolerant voters which further give additional information besides the voting output, e.g., how many module outputs agree. Dynamically defining which set of inputs should be considered for voting is also crucial. Earlier we showed a practical implementation of programmable NMR voters that self-report the voting outcome and do self-checks. Our voter design method uses a binary matrix with specific properties that enable easy scaling of the design regarding the number of voter inputs N. Thus, an automated construction of NMR systems is possible, given the basic module and arbitrary redundancy $N$. In this paper we present the mathematical aspects of the method, i.e., we analyze the properties of the matrix that characterizes the method. We give the characteristic polynomials of the properly and erroneously built matrices in their explicit forms. We further give their eigenvalues and corresponding eigenvectors, which reveal a lot of useful information about the system. At the end, we give relations between the voter outputs and eigenpairs.
Risk Perceptions for Wearable Devices
Venue: arXiv cs.CY 2015
Year: 2015

Wearable devices, or "wearables," bring great benefits but also potential risks that could expose users' activities with- out their awareness or consent. In this paper, we report findings from the first large-scale survey conducted to investigate user security and privacy concerns regarding wearables. We surveyed 1,782 Internet users in order to identify risks that are particularly concerning to them; these risks are inspired by the sensor inputs and applications of popular wearable technologies. During this experiment, our questions controlled for the effects of what data was being accessed and with whom it was being shared. We also investigated how these emergent threats compared to existent mobile threats, how upcoming capabilities and artifacts compared to existing technologies, and how users ranked technical and nontechnical concerns to sketch a concrete and broad view of the wearable device landscape. We hope that this work will inform the design of future user notification, permission management, and access control schemes for wearables.
Convergence of a finite difference scheme to weak solutions of the system of partial differential equation arising in mean field games
Venue: arXiv cs.NA 2015
Year: 2015

Mean field type models describing the limiting behavior of stochastic differential games as the number of players tends to +$\infty$, have been recently introduced by J-M. Lasry and P-L. Lions. Under suitable assumptions, they lead to a system of two coupled partial differential equations, a forward Bellman equation and a backward Fokker-Planck equations. Finite difference schemes for the approximation of such systems have been proposed in previous works. Here, we prove the convergence of these schemes towards a weak solution of the system of partial differential equations.
Honeybees-inspired heuristic algorithms for numerical optimisation
Venue: arXiv cs.NE 2015
Year: 2015

Swarm intelligence is all about developing collective behaviours to solve complex, ill-structured and large-scale problems. Efficiency in collective behaviours depends on how to harmonise the individual contributions so that a complementary collective effort can be achieved to offer a useful solution. The main points in organising the harmony remains as managing the diversification and intensification actions appropriately, where the efficiency of collective behaviours depends on blending these two actions appropriately. In this study, two swarm intelligence algorithms inspired of natural honeybee colonies have been overviewed with many respects and two new revisions and a hybrid version have been studied to improve the efficiencies in solving numerical optimisation problems, which are well-known hard benchmarks. Consequently, the revisions and especially the hybrid algorithm proposed have outperformed the two original bee algorithms in solving these very hard numerical optimisation benchmarks.
Learning of Behavior Trees for Autonomous Agents
Venue: arXiv cs.RO 2015
Year: 2015

Definition of an accurate system model for Automated Planner (AP) is often impractical, especially for real-world problems. Conversely, off-the-shelf planners fail to scale up and are domain dependent. These drawbacks are inherited from conventional transition systems such as Finite State Machines (FSMs) that describes the action-plan execution generated by the AP. On the other hand, Behavior Trees (BTs) represent a valid alternative to FSMs presenting many advantages in terms of modularity, reactiveness, scalability and domain-independence. In this paper, we propose a model-free AP framework using Genetic Programming (GP) to derive an optimal BT for an autonomous agent to achieve a given goal in unknown (but fully observable) environments. We illustrate the proposed framework using experiments conducted with an open source benchmark Mario AI for automated generation of BTs that can play the game character Mario to complete a certain level at various levels of difficulty to include enemies and obstacles.
Opportunistic Scheduling for Full-Duplex Uplink-Downlink Networks
Venue: arXiv cs.IT 2015
Year: 2015

We study opportunistic scheduling and the sum capacity of cellular networks with a full-duplex multi-antenna base station and a large number of single-antenna half-duplex users. Simultaneous uplink and downlink over the same band results in uplink-to-downlink interference, degrading performance. We present a simple opportunistic joint uplink-downlink scheduling algorithm that exploits multiuser diversity and treats interference as noise. We show that in homogeneous networks, our algorithm achieves the same sum capacity as what would have been achieved if there was no uplink-to-downlink interference, asymptotically in the number of users. The algorithm does not require interference CSI at the base station or uplink users. It is also shown that for a simple class of heterogeneous networks without sufficient channel diversity, it is not possible to achieve the corresponding interference-free system capacity. We discuss the potential for using device-to-device side-channels to overcome this limitation in heterogeneous networks.
Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection
Venue: arXiv cs.DM 2015
Year: 2015

Denote by $A$ the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing $\langle A-E\{A\},X\rangle$ over the set of positive semidefinite matrices $X$ with diagonal entries $X_{ii}=1$. We prove that for large (bounded) average degree $d$, the value of this semidefinite program (SDP) is --with high probability-- $2n\sqrt{d} + n\, o(\sqrt{d})+o(n)$. For a random regular graph of degree $d$, we prove that the SDP value is $2n\sqrt{d-1}+o(n)$, matching a spectral upper bound. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is partitioned into subsets of size $n/2$, with edge probability $a/n$ (within group) and $b/n$ (across). We prove that SDP detects the partition with high probability provided $(a-b)^2/(4d)> 1+o_{d}(1)$, with $d= (a+b)/2$. By comparison, the information theoretic threshold for detecting the hidden partition is $(a-b)^2/(4d)> 1$: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: $(i)$ A new `higher-rank' Grothendieck inequality for symmetric matrices; $(ii)$ An interpolation method inspired from statistical physics; $(iii)$ An analysis of the eigenvectors of deformed Gaussian random matrices.
On the Definition of Cyber-Physical Resilience in Power Systems
Venue: arXiv cs.SY 2015
Year: 2015

In recent years, advanced sensors, intelligent automation, communication networks, and information technologies have been integrated into the electric grid to enhance its performance and efficiency. Integrating these new technologies has resulted in more interconnections and interdependencies between the physical and cyber components of the grid. Natural disasters and man-made perturbations have begun to threaten grid integrity more often. Urban infrastructure networks are highly reliant on the electric grid and consequently, the vulnerability of infrastructure networks to electric grid outages is becoming a major global concern. In order to minimize the economic, social, and political impacts of power system outages, the grid must be resilient. The concept of a power system cyber-physical resilience centers around maintaining system states at a stable level in the presence of disturbances. Resilience is a multidimensional property of the electric grid, it requires managing disturbances originating from physical component failures, cyber component malfunctions, and human attacks. In the electric grid community, there is not a clear and universally accepted definition of cyber-physical resilience. This paper focuses on the definition of resilience for the electric grid and reviews key concepts related to system resilience. This paper aims to advance the field not only by adding cyber-physical resilience concepts to power systems vocabulary, but also by proposing a new way of thinking about grid operation with unexpected disturbances and hazards and leveraging distributed energy resources.
Broadcasting a Common Message with Variable-Length Stop-Feedback Codes
Venue: arXiv cs.IT 2015
Year: 2015

We investigate the maximum coding rate achievable over a two-user broadcast channel for the scenario where a common message is transmitted using variable-length stop-feedback codes. Specifically, upon decoding the common message, each decoder sends a stop signal to the encoder, which transmits continuously until it receives both stop signals. For the point-to-point case, Polyanskiy, Poor, and Verdú (2011) recently demonstrated that variable-length coding combined with stop feedback significantly increases the speed at which the maximum coding rate converges to capacity. This speed-up manifests itself in the absence of a square-root penalty in the asymptotic expansion of the maximum coding rate for large blocklengths, a result a.k.a. zero dispersion. In this paper, we show that this speed-up does not necessarily occur for the broadcast channel with common message. Specifically, there exist scenarios for which variable-length stop-feedback codes yield a positive dispersion.
Strong Converse Theorems for Degraded Broadcast Channels with Feedback
Venue: arXiv cs.IT 2015
Year: 2015

We consider the discrete memoryless degraded broadcast channels with feedback. We prove that the error probability of decoding tends to one exponentially for rates outside the capacity region and derive an explicit lower bound of this exponent function. We shall demonstrate that the information spectrum approach is quite useful for investigating this problem.
Finding Tizen security bugs through whole-system static analysis
Venue: arXiv cs.CR 2015
Year: 2015

Tizen is a new Linux-based open source platform for consumer devices including smartphones, televisions, vehicles, and wearables. While Tizen provides kernel-level mandatory policy enforcement, it has a large collection of libraries, implemented in a mix of C and C++, which make their own security checks. In this research, we describe the design and engineering of a static analysis engine which drives a full information flow analysis for apps and a control flow analysis for the full library stack. We implemented these static analyses as extensions to LLVM, requiring us to improve LLVM's native analysis features to get greater precision and scalability, including knotty issues like the coexistence of C++ inheritance with C function pointer use. With our tools, we found several unexpected behaviors in the Tizen system, including paths through the system libraries that did not have inline security checks. We show how our tools can help the Tizen app store to verify important app properties as well as helping the Tizen development process avoid the accidental introduction of subtle vulnerabilities.
Coding against a Limited-view Adversary: The Effect of Causality and Feedback
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of communication over a multi-path network in the presence of a causal adversary. The limited-view causal adversary is able to eavesdrop on a subset of links and also jam on a potentially overlapping subset of links based on the current and past information. To ensure that the communication takes place reliably and secretly, resilient network codes with necessary redundancy are needed. We study two adversarial models - additive and overwrite jamming and we optionally assume passive feedback from decoder to encoder, i.e., the encoder sees everything that the decoder sees. The problem assumes transmissions are in the large alphabet regime. For both jamming models, we find the capacity under four scenarios - reliability without feedback, reliability and secrecy without feedback, reliability with passive feedback, reliability and secrecy with passive feedback. We observe that, in comparison to the non-causal setting, the capacity with a causal adversary is strictly increased for a wide variety of parameter settings and present our intuition through several examples.
Scaling of city attractiveness for foreign visitors through big data of human economical and social media activity
Venue: arXiv cs.SI 2015
Year: 2015

Scientific studies investigating laws and regularities of human behavior are nowadays increasingly relying on the wealth of widely available digital information produced by human social activity. In this paper we leverage big data created by three different aspects of human activity (i.e., bank card transactions, geotagged photographs and tweets) in Spain for quantifying city attractiveness for the foreign visitors. An important finding of this papers is a strong superlinear scaling of city attractiveness with its population size. The observed scaling exponent stays nearly the same for different ways of defining cities and for different data sources, emphasizing the robustness of our finding. Temporal variation of the scaling exponent is also considered in order to reveal seasonal patterns in the attractiveness