OpenRaiser/Intern-Atlas huggingface dataset:
Convolutional-Code-Specific CRC Code Design
Venue: arXiv cs.IT 2015
Year: 2015

Cyclic redundancy check (CRC) codes check if a codeword is correctly received. This paper presents an algorithm to design CRC codes that are optimized for the code-specific error behavior of a specified feedforward convolutional code. The algorithm utilizes two distinct approaches to computing undetected error probability of a CRC code used with a specific convolutional code. The first approach enumerates the error patterns of the convolutional code and tests if each of them is detectable. The second approach reduces complexity significantly by exploiting the equivalence of the undetected error probability to the frame error rate of an equivalent catastrophic convolutional code. The error events of the equivalent convolutional code are exactly the undetectable errors for the original concatenation of CRC and convolutional codes. This simplifies the computation because error patterns do not need to be individually checked for detectability. As an example, we optimize CRC codes for a commonly used 64-state convolutional code for information length k=1024 demonstrating significant reduction in undetected error probability compared to the existing CRC codes with the same degrees. For a fixed target undetected error probability, the optimized CRC codes typically require 2 fewer bits.
The Majority Illusion in Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

Social behaviors are often contagious, spreading through a population as individuals imitate the decisions and choices of others. A variety of global phenomena, from innovation adoption to the emergence of social norms and political movements, arise as a result of people following a simple local rule, such as copy what others are doing. However, individuals often lack global knowledge of the behaviors of others and must estimate them from the observations of their friends' behaviors. In some cases, the structure of the underlying social network can dramatically skew an individual's local observations, making a behavior appear far more common locally than it is globally. We trace the origins of this phenomenon, which we call "the majority illusion," to the friendship paradox in social networks. As a result of this paradox, a behavior that is globally rare may be systematically overrepresented in the local neighborhoods of many people, i.e., among their friends. Thus, the "majority illusion" may facilitate the spread of social contagions in networks and also explain why systematic biases in social perceptions, for example, of risky behavior, arise. Using synthetic and real-world networks, we explore how the "majority illusion" depends on network structure and develop a statistical model to calculate its magnitude in a network.
N-Version Obfuscation: Impeding Software Tampering Replication with Program Diversity
Venue: arXiv cs.CR 2015
Year: 2015

Tamper-resistance is a fundamental software security research area. Many approaches have been proposed to thwart specific procedures of tampering, e.g., obfuscation and self-checksumming. However, to our best knowledge, none of them can achieve theoretically tamper-resistance. Our idea is to impede the replication of tampering via program diversification, and thus increasing the complexity to break the whole software system. To this end, we propose to deliver same featured, but functionally nonequivalent software copies to different machines. We formally define the problem as N-version obfuscation, and provide a viable means to solve the problem. Our evaluation result shows that the time required for breaking a software system is linearly increased with the number of software versions, which is O(n) complexity.
Relative Select
Venue: arXiv cs.DS 2015
Year: 2015

Motivated by the problem of storing coloured de Bruijn graphs, we show how, if we can already support fast select queries on one string, then we can store a little extra information and support fairly fast select queries on a similar string.
The Attack as Strong Negation, Part I
Venue: arXiv cs.LO 2015
Year: 2015

We add strong negation $N$ to classical logic and interpret the attack relation of "$x$ attacks $y$" in argumentation as $(x\to Ny)$. We write a corresponding object level (using $N$ only) classical theory for each argumentation network and show that the classical models of this theory correspond exactly to the complete extensions of the argumentation network. We show by example how this approach simplifies the study of abstract argumentation networks. We compare with other translations of abstract argumentation networks into logic, such as classical predicate logic or modal logics, or logic programming, and we also compare with Abstract Dialectical Frameworks.
BREW: A Breakable Web Application for IT-Security Classroom Use
Venue: arXiv cs.CY 2015
Year: 2015

This paper presents BREW (Breakable Web Application), a tool for teaching IT Security. BREWs main teaching targets are identification and exploitation of vulnerabilities, using technologies and methodologies for software auditing and testing, and bug detection, fixation, and writing of secure code. Main advantages of BREW include that it is easy to apply in practice, it is a perfect tool to create and retain motivation, it corresponds to the demands of the psychology of learning, and it can be used for a heterogeneous group of students. BREW has been success- fully used for teaching IT Security in Germany as well as on an Erasmus Project with international student groups.
Power Allocation Schemes for Multicell Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the sum-rate gains brought by power allocation strategies in multicell massive multipleinput multiple-output systems, assuming time-division duplex transmission. For both uplink and downlink, we derive tractable expressions for the achievable rate with zero-forcing receivers and precoders respectively. To avoid high complexity joint optimization across the network, we propose a scheduling mechanism for power allocation, where in a single time slot, only cells that do not interfere with each other adjust their transmit powers. Based on this, corresponding transmit power allocation strategies are derived, aimed at maximizing the sum rate per-cell. These schemes are shown to bring considerable gains over equal power allocation for practical antenna configurations (e.g., up to a few hundred). However, with fixed number of users (N), these gains diminish as M turns to infinity, and equal power allocation becomes optimal. A different conclusion is drawn for the case where both M and N grow large together, in which case: (i) improved rates are achieved as M grows with fixed M/N ratio, and (ii) the relative gains over the equal power allocation diminish as M/N grows. Moreover, we also provide applicable values of M/N under an acceptable power allocation gain threshold, which can be used as to determine when the proposed power allocation schemes yield appreciable gains, and when they do not. From the network point of view, the proposed scheduling approach can achieve almost the same performance as the joint power allocation after one scheduling round, with much reduced complexity.
Exact Asymptotics for the Random Coding Error Probability
Venue: arXiv cs.IT 2015
Year: 2015

Error probabilities of random codes for memoryless channels are considered in this paper. In the area of communication systems, admissible error probability is very small and it is sometimes more important to discuss the relative gap between the achievable error probability and its bound than to discuss the absolute gap. Scarlett et al. derived a good upper bound of a random coding union bound based on the technique of saddlepoint approximation but it is not proved that the relative gap of their bound converges to zero. This paper derives a new bound on the achievable error probability in this viewpoint for a class of memoryless channels. The derived bound is strictly smaller than that by Scarlett et al. and its relative gap with the random coding error probability (not a union bound) vanishes as the block length increases for a fixed coding rate.
Connectivity in Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

The value of a social network is generally determined by its size and the connectivity of its nodes. But since some of the nodes may be fake ones and others that are dormant, the question of validating the node counts by statistical tests becomes important. In this paper we propose the use of the Benford's distribution to check on the trustworthiness of the connectivity statistics. Our experiments using statistics of both symmetric and asymmetric networks show that when the accumulation processes are random, the convergence to Benford's law is significantly better, and therefore this fact can be used to distinguish between processes which are randomly generated and those with internal dependencies.
Spatial Self-Interference Isolation for In-Band Full-Duplex Wireless: A Degrees-of-Freedom Analysis
Venue: arXiv cs.IT 2015
Year: 2015

The challenge to in-band full-duplex wireless communication is managing self-interference. Many designs have employed spatial isolation mechanisms, such as shielding or multi-antenna beamforming, to isolate the self-interference wave from the receiver. Such spatial isolation methods are effective, but by confining the transmit and receive signals to a subset of the available space, the full spatial resources of the channel be under-utilized, expending a cost that may nullify the net benefit of operating in full-duplex mode. In this paper we leverage an antenna-theory-based channel model to analyze the spatial degrees of freedom available to a full-duplex capable base station, and observe that whether or not spatial isolation out-performs time-division (i.e. half-duplex) depends heavily on the geometric distribution of scatterers. Unless the angular spread of the objects that scatter to the intended users is overlapped by the spread of objects that backscatter to the base station, then spatial isolation outperforms time division, otherwise time division may be optimal.
Virtual Networks and Poverty Analysis in Senegal
Venue: arXiv cs.CY 2015
Year: 2015

Do today's communication technologies hold potential to alleviate poverty? The mobile phone's accessibility and use allows us with an unprecedented volume of data on social interactions, mobility and more. Can this data help us better understand, characterize and alleviate poverty in one of the poorest nations in the world. Our study is an attempt in this direction. We discuss two concepts, which are both interconnected and immensely useful for securing the important link between mobile accessibility and poverty. First, we use the cellular-communications data to construct virtual connectivity maps for Senegal, which are then correlated with the poverty indicators to learn a model. Our model predicts poverty index at any spatial resolution. Thus, we generate Poverty Maps for Senegal at an unprecedented finer resolution. Such maps are essential for understanding what characterizes poverty in a certain region, and how it differentiates from other regions, for targeted responses for the demographic of the population that is most needy. An interesting fact, that is empirically proved by our methodology, is that a large portion of all communication, and economic activity in Senegal is concentrated in Dakar, leaving many other regions marginalized. Second, we study how user behavioral statistics, gathered from cellular-communications, correlate with the poverty indicators. Can this relationship be learnt as a model to generate poverty maps at a finer resolution? Surprisingly, this relationship can give us an alternate poverty map, that is solely based on the user behavior. Since poverty is a complex phenomenon, poverty maps showcasing multiple perspectives, such as ours, provide policymakers with better insights for effective responses for poverty eradication.
Self-optimizing load balancing with backhaul-constrained radio access networks
Venue: arXiv cs.NI 2015
Year: 2015

Self-Organizing Network (SON) technology aims at autonomously deploying, optimizing and repairing the Radio Access Networks (RAN). SON algorithms typically use Key Performance Indicators (KPIs) from the RAN. It is shown that in certain cases, it is essential to take into account the impact of the backhaul state in the design of the SON algorithm. We revisit the Base Station (BS) load definition taking into account the backhaul state. We provide an analytical formula for the load along with a simple estimator for both elastic and guaranteed bit-rate (GBR) traffic. We incorporate the proposed load estimator in a self-optimized load balancing algorithm. Simulation results for a backhaul constrained heterogeneous network illustrate how the correct load definition can guarantee a proper operation of the SON algorithm.
Enigma: Decentralized Computation Platform with Guaranteed Privacy
Venue: arXiv cs.CR 2015
Year: 2015

A peer-to-peer network, enabling different parties to jointly store and run computations on data while keeping the data completely private. Enigma's computational model is based on a highly optimized version of secure multi-party computation, guaranteed by a verifiable secret-sharing scheme. For storage, we use a modified distributed hashtable for holding secret-shared data. An external blockchain is utilized as the controller of the network, manages access control, identities and serves as a tamper-proof log of events. Security deposits and fees incentivize operation, correctness and fairness of the system. Similar to Bitcoin, Enigma removes the need for a trusted third party, enabling autonomous control of personal data. For the first time, users are able to share their data with cryptographic guarantees regarding their privacy.
Strategic decentralization in binary choice composite congestion games
Venue: arXiv cs.GT 2015
Year: 2015

This paper studies strategic decentralization in binary choice composite network congestion games. A player decentralizes if she lets some autonomous agents to decide respectively how to send different parts of her stock from the origin to the destination. This paper shows that, with convex, strictly increasing and differentiable arc cost functions, an atomic splittable player always has an optimal unilateral decentralization strategy. Besides, unilateral decentralization gives her the same advantage as being the leader in a Stackelberg congestion game. Finally, unilateral decentralization of an atomic player has a negative impact on the social cost and on the costs of the other players at the equilibrium of the congestion game.
The Relative Power of Composite Loop Agreement Tasks
Venue: arXiv cs.DC 2015
Year: 2015

Loop agreement is a family of wait-free tasks that includes set agreement and simplex agreement, and was used to prove the undecidability of wait-free solvability of distributed tasks by read/write memory. Herlihy and Rajsbaum defined the algebraic signature of a loop agreement task, which consists of a group and a distinguished element. They used the algebraic signature to characterize the relative power of loop agreement tasks. In particular, they showed that one task implements another exactly when there is a homomorphism between their respective signatures sending one distinguished element to the other. In this paper, we extend the previous result by defining the composition of multiple loop agreement tasks to create a new one with the same combined power. We generalize the original algebraic characterization of relative power to compositions of tasks. In this way, we can think of loop agreement tasks in terms of their basic building blocks. We also investigate a category-theoretic perspective of loop agreement by defining a category of loops, showing that the algebraic signature is a functor, and proving that our definition of task composition is the "correct" one, in a categorical sense.
Automatic Generation of Minimal Cut Sets
Venue: arXiv cs.LO 2015
Year: 2015

A cut set is a collection of component failure modes that could lead to a system failure. Cut Set Analysis (CSA) is applied to critical systems to identify and rank system vulnerabilities at design time. Model checking tools have been used to automate the generation of minimal cut sets but are generally based on checking reachability of system failure states. This paper describes a new approach to CSA using a Linear Temporal Logic (LTL) model checker called BT Analyser that supports the generation of multiple counterexamples. The approach enables a broader class of system failures to be analysed, by generalising from failure state formulae to failure behaviours expressed in LTL. The traditional approach to CSA using model checking requires the model or system failure to be modified, usually by hand, to eliminate already-discovered cut sets, and the model checker to be rerun, at each step. By contrast, the new approach works incrementally and fully automatically, thereby removing the tedious and error-prone manual process and resulting in significantly reduced computation time. This in turn enables larger models to be checked. Two different strategies for using BT Analyser for CSA are presented. There is generally no single best strategy for model checking: their relative efficiency depends on the model and property being analysed. Comparative results are given for the A320 hydraulics case study in the Behavior Tree modelling language.
Long-Term Stability Analysis of Power Systems with Wind Power Based on Stochastic Differential Equations: Model Development and Foundations
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, the variable wind power is incorporated into the dynamic model for long-term stability analysis. A theory-based method is proposed for power systems with wind power to conduct long-term stability analysis, which is able to provide accurate stability assessments with fast simulation speed. Particularly, the theoretical foundation for the proposed approximation approach is presented. The accuracy and efficiency of the method are illustrated by several numerical examples.
From Independence to Expansion and Back Again
Venue: arXiv cs.DS 2015
Year: 2015

We consider the following fundamental problems: (1) Constructing $k$-independent hash functions with a space-time tradeoff close to Siegel's lower bound. (2) Constructing representations of unbalanced expander graphs having small size and allowing fast computation of the neighbor function. It is not hard to show that these problems are intimately connected in the sense that a good solution to one of them leads to a good solution to the other one. In this paper we exploit this connection to present efficient, recursive constructions of $k$-independent hash functions (and hence expanders with a small representation). While the previously most efficient construction (Thorup, FOCS 2013) needed time quasipolynomial in Siegel's lower bound, our time bound is just a logarithmic factor from the lower bound.
On Equivalences, Metrics, and Polynomial Time (Long Version)
Venue: arXiv cs.LO 2015
Year: 2015

Interactive behaviors are ubiquitous in modern cryptography, but are also present in $λ$-calculi, in the form of higher-order constructions. Traditionally, however, typed $λ$-calculi simply do not fit well into cryptography, being both deterministic and too powerful as for the complexity of functions they can express. We study interaction in a $λ$-calculus for probabilistic polynomial time computable functions. In particular, we show how notions of context equivalence and context metric can both be characterized by way of traces when defined on linear contexts. We then give evidence on how this can be turned into a proof methodology for computational indistinguishability, a key notion in modern cryptography. We also hint at what happens if a more general notion of a context is used.
Strategies for fostering Knowledge Management Programs in Public Organizations
Venue: arXiv cs.CY 2015
Year: 2015

Knowledge Management (KM) is an approach to achieving strategic objectives by visualizing, sharing, and using intangible resources of an organization and its stakeholders. There are many studies that analyze specific factors for the successful implementation of KM programs, and the evaluation of such factors is considered a strategic tool for Public Organizations (POs) for efficiently directing the implementation of a KM program. Nevertheless, there are cultural problems such as weak trust, bad collaboration; technological problems as KM systems difficult to use, nor interconnected or interoperable; and strategic problems as political changes, not inter-administration continuity or lack of political willingness. In this research we provide an overview of the key factors for facilitating the implementation of KM programs. To this end, we conducted a Systematic Literature Review (SLR) of success factors to create a KM program for POs. Analyzing the twenty related studies we summarize benefits and quality attributes of KM. Moreover, we obtained from an ongoing project evaluation results of the KM factors ranked cultural, technological and strategic. The results show that the Mexican POs have strategic and technological issues such as: a misalignment between knowledge management and organizational goals, it seems that POs are barely reusing their knowledge to execute their daily activities or to take decisions, and is not possible to know who and how a knowledge asset has been used. Finally, according to the gaps and difficulties of the SLR, we provide strategies to successfully implement KM programs in Mexico.
Stochastic Geometry Modeling of Cellular Networks: Analysis, Simulation and Experimental Validation
Venue: arXiv cs.IT 2015
Year: 2015

Due to the increasing heterogeneity and deployment density of emerging cellular networks, new flexible and scalable approaches for their modeling, simulation, analysis and optimization are needed. Recently, a new approach has been proposed: it is based on the theory of point processes and it leverages tools from stochastic geometry for tractable system-level modeling, performance evaluation and optimization. In this paper, we investigate the accuracy of this emerging abstraction for modeling cellular networks, by explicitly taking realistic base station locations, building footprints, spatial blockages and antenna radiation patterns into account. More specifically, the base station locations and the building footprints are taken from two publicly available databases from the United Kingdom. Our study confirms that the abstraction model based on stochastic geometry is capable of accurately modeling the communication performance of cellular networks in dense urban environments.
Technical Report: Image Captioning with Semantically Similar Images
Venue: arXiv cs.CV 2015
Year: 2015

This report presents our submission to the MS COCO Captioning Challenge 2015. The method uses Convolutional Neural Network activations as an embedding to find semantically similar images. From these images, the most typical caption is selected based on unigram frequencies. Although the method received low scores with automated evaluation metrics and in human assessed average correctness, it is competitive in the ratio of captions which pass the Turing test and which are assessed as better or equal to human captions.
Short Note on Costs of Floating Point Operations on current x86-64 Architectures: Denormals, Overflow, Underflow, and Division by Zero
Venue: arXiv cs.PF 2015
Year: 2015

Simple floating point operations like addition or multiplication on normalized floating point values can be computed by current AMD and Intel processors in three to five cycles. This is different for denormalized numbers, which appear when an underflow occurs and the value can no longer be represented as a normalized floating-point value. Here the costs are about two magnitudes higher.