OpenRaiser/Intern-Atlas huggingface dataset:
N-continuous OFDM: System Optimization and Performance Analysis
Venue: arXiv cs.IT 2013
Year: 2013

N-continuous orthogonal frequency division multiplexing (NC-OFDM) is a promising technique to achieve significant sidelobe suppression of baseband OFDM signals. However, the high complexity limits its application. Based on conventional NC-OFDM, in this paper, a new technique, called time-domain N-continuous OFDM (TD-NC-OFDM), is proposed to transfer the original frequency-domain processing to the time domain, by the linear combination of a novel basis set to smooth the consecutive OFDM symbols and their high-order derivatives. We prove that TD-NC-OFDM is an equivalent to conventional one while consuming much lower complexity. Furthermore, via the time-domain structure, a closed-form spectral expression of NC-OFDM signals is derived and a compact upper bound of sidelobe decaying is derived. This paper also investigates the impact of the TD-NC-OFDM technique on received signal-to-interference-plus-noise ratio (SINR) and provides a closed-form analytical expression. Theoretical analyses and simulation results show that TD-NC-OFDM can prohibitively suppress the sidelobe with much lower complexity.
Compressed Vertical Partitioning for Full-In-Memory RDF Management
Venue: arXiv cs.DB 2013
Year: 2013

The Web of Data has been gaining momentum and this leads to increasingly publish more semi-structured datasets following the RDF model, based on atomic triple units of subject, predicate, and object. Although it is a simple model, compression methods become necessary because datasets are increasingly larger and various scalability issues arise around their organization and storage. This requirement is more restrictive in RDF stores because efficient SPARQL resolution on the compressed RDF datasets is also required. This article introduces a novel RDF indexing technique (called k2-triples) supporting efficient SPARQL resolution in compressed space. k2-triples, uses the predicate to vertically partition the dataset into disjoint subsets of pairs (subject, object), one per predicate. These subsets are represented as binary matrices in which 1-bits mean that the corresponding triple exists in the dataset. This model results in very sparse matrices, which are efficiently compressed using k2-trees. We enhance this model with two compact indexes listing the predicates related to each different subject and object, in order to address the specific weaknesses of vertically partitioned representations. The resulting technique not only achieves by far the most compressed representations, but also the best overall performance for RDF retrieval in our experiments. Our approach uses up to 10 times less space than a state of the art baseline, and outperforms its performance by several order of magnitude on the most basic query patterns. In addition, we optimize traditional join algorithms on k2-triples and define a novel one leveraging its specific features. Our experimental results show that our technique overcomes traditional vertical partitioning for join resolution, reporting the best numbers for joins in which the non-joined nodes are provided, and being competitive in the majority of the cases.
MLI: An API for Distributed Machine Learning
Venue: arXiv cs.LG 2013
Year: 2013

MLI is an Application Programming Interface designed to address the challenges of building Machine Learn- ing algorithms in a distributed setting based on data-centric computing. Its primary goal is to simplify the development of high-performance, scalable, distributed algorithms. Our initial results show that, relative to existing systems, this interface can be used to build distributed implementations of a wide variety of common Machine Learning algorithms with minimal complexity and highly competitive performance and scalability.
Validating Network Value of Influencers by means of Explanations
Venue: arXiv cs.SI 2013
Year: 2013

Recently, there has been significant interest in social influence analysis. One of the central problems in this area is the problem of identifying influencers, such that by convincing these users to perform a certain action (like buying a new product), a large number of other users get influenced to follow the action. The client of such an application is a marketer who would target these influencers for marketing a given new product, say by providing free samples or discounts. It is natural that before committing resources for targeting an influencer the marketer would be interested in validating the influence (or network value) of influencers returned. This requires digging deeper into such analytical questions as: who are their followers, on what actions (or products) they are influential, etc. However, the current approaches to identifying influencers largely work as a black box in this respect. The goal of this paper is to open up the black box, address these questions and provide informative and crisp explanations for validating the network value of influencers. We formulate the problem of providing explanations (called PROXI) as a discrete optimization problem of feature selection. We show that PROXI is not only NP-hard to solve exactly, it is NP-hard to approximate within any reasonable factor. Nevertheless, we show interesting properties of the objective function and develop an intuitive greedy heuristic. We perform detailed experimental analysis on two real world datasets - Twitter and Flixster, and show that our approach is useful in generating concise and insightful explanations of the influence distribution of users and that our greedy algorithm is effective and efficient with respect to several baselines.
Brooks' theorem on powers of graphs
Venue: arXiv cs.DM 2013
Year: 2013

We prove that for $k\geq 3$, the bound given by Brooks' theorem on the chromatic number of $k$-th powers of graphs of maximum degree $Δ\geq 3$ can be lowered by 1, even in the case of online list coloring.
Ship Detection and Segmentation using Image Correlation
Venue: arXiv cs.CV 2013
Year: 2013

There have been intensive research interests in ship detection and segmentation due to high demands on a wide range of civil applications in the last two decades. However, existing approaches, which are mainly based on statistical properties of images, fail to detect smaller ships and boats. Specifically, known techniques are not robust enough in view of inevitable small geometric and photometric changes in images consisting of ships. In this paper a novel approach for ship detection is proposed based on correlation of maritime images. The idea comes from the observation that a fine pattern of the sea surface changes considerably from time to time whereas the ship appearance basically keeps unchanged. We want to examine whether the images have a common unaltered part, a ship in this case. To this end, we developed a method - Focused Correlation (FC) to achieve robustness to geometric distortions of the image content. Various experiments have been conducted to evaluate the effectiveness of the proposed approach.
SymbolicData:SDEval - Benchmarking for Everyone
Venue: arXiv cs.SC 2013
Year: 2013

In this paper we will present SDeval, a software project that contains tools for creating and running benchmarks with a focus on problems in computer algebra. It is built on top of the Symbolic Data project, able to translate problems in the database into executable code for various computer algebra systems. The included tools are designed to be very flexible to use and to extend, such that they can be utilized even in contexts of other communities. With the presentation of SDEval, we will also address particularities of benchmarking in the field of computer algebra. Furthermore, with SDEval, we provide a feasible and automatizable way of reproducing benchmarks published in current research works, which appears to be a difficult task in general due to the customizability of the available programs. We will simultaneously present the current developments in the Symbolic Data project.
Avoiding Shared Clocks in Networks of Timed Automata
Venue: arXiv cs.FL 2013
Year: 2013

Networks of timed automata (NTA) are widely used to model distributed real-time systems. Quite often in the literature, the automata are allowed to share clocks, i.e. transitions of one automaton may be guarded by conditions on the value of clocks reset by another automaton. This is a problem when one considers implementing such model in a distributed architecture, since reading clocks a priori requires communications which are not explicitly described in the model. We focus on the following question: given an NTA A1 || A2 where A2 reads some clocks reset by A1, does there exist an NTA A'1 || A'2 without shared clocks with the same behavior as the initial NTA? For this, we allow the automata to exchange information during synchronizations only, in particular by copying the value of their neighbor's clocks. We discuss a formalization of the problem and define an appropriate behavioural equivalence. Then we give a criterion using the notion of contextual timed transition system, which represents the behavior of A2 when in parallel with A1. Finally, we effectively build A'1 || A'2 when it exists.
Approximation systems for functions in topological and in metric spaces
Venue: arXiv cs.LO 2013
Year: 2013

A notable feature of the TTE approach to computability is the representation of the argument values and the corresponding function values by means of infinitistic names. Two ways to eliminate the using of such names in certain cases are indicated in the paper. The first one is intended for the case of topological spaces with selected indexed denumerable bases. Suppose a partial function is given from one such space into another one whose selected base has a recursively enumerable index set, and suppose that the intersection of base open sets in the first space is computable in the sense of Weihrauch-Grubba. Then the ordinary TTE computability of the function is characterized by the existence of an appropriate recursively enumerable relation between indices of base sets containing the argument value and indices of base sets containing the corresponding function value.This result can be regarded as an improvement of a result of Korovina and Kudinov. The second way is applicable to metric spaces with selected indexed denumerable dense subsets. If a partial function is given from one such space into another one, then, under a semi-computability assumption concerning these spaces, the ordinary TTE computability of the function is characterized by the existence of an appropriate recursively enumerable set of quadruples. Any of them consists of an index of element from the selected dense subset in the first space, a natural number encoding a rational bound for the distance between this element and the argument value, an index of element from the selected dense subset in the second space and a natural number encoding a rational bound for the distance between this element and the function value. One of the examples in the paper indicates that the computability of real functions can be characterized in a simple way by using the first way of elimination of the infinitistic names.
Contextual Hypergraph Modelling for Salient Object Detection
Venue: arXiv cs.CV 2013
Year: 2013

Salient object detection aims to locate objects that capture human attention within images. Previous approaches often pose this as a problem of image contrast analysis. In this work, we model an image as a hypergraph that utilizes a set of hyperedges to capture the contextual properties of image pixels or regions. As a result, the problem of salient object detection becomes one of finding salient vertices and hyperedges in the hypergraph. The main advantage of hypergraph modeling is that it takes into account each pixel's (or region's) affinity with its neighborhood as well as its separation from image background. Furthermore, we propose an alternative approach based on center-versus-surround contextual contrast analysis, which performs salient object detection by optimizing a cost-sensitive support vector machine (SVM) objective function. Experimental results on four challenging datasets demonstrate the effectiveness of the proposed approaches against the state-of-the-art approaches to salient object detection.
The Cryptanalysis of Lee's Chaotic Maps-Based Authentication and Key Agreement Scheme using Smart card for Telecare Medicine Information Systems
Venue: arXiv cs.CR 2013
Year: 2013

The Telecare medicine information system (TMIS) is developed to provide Telecare services to the remote user. A user can access remote medical servers using internet without moving from his place. Although remote user and server exchange their messages/data via public networks. An adversary is considered to be enough powerful that he may have full control over the public network. This makes these Telecare services vulnerable to attacks. To ensure secure communication between the user and server many password based authentication schemes have been proposed. In 2013, Hao et al. presented chaotic maps-based password authentication scheme for TMIS. Recently, Lee identified that Hao et al.'s scheme fails to satisfy key agreement property, such that a malicious server can predetermine the session key. Lee also presented an efficient chaotic map-based password authentication and key agreement scheme using Smart cards for TMIS. In this article, we briefly review Lee's scheme and demonstrates the weakness of Lee's scheme. The study shows that the Lee's scheme inefficiency of password change phase causes denial of service attack and login phase results extra computation and communication overhead.
On The Limits Of Perfect Security For Steganographic System
Venue: arXiv cs.CR 2013
Year: 2013

Until now the discussion on perfect security for steganographic systems has remained confined within the realm of mathematicians and information theory experts whose concise and symbolic representation of their philosophies, postulates, and inference thereafter has made it hard for the naïve academics to have an insight of the concepts. This paper is an endeavor not only to appraise on the limitations of one of such pioneer comprehensions but also to illustrate a pitfall in another scheme that asserts on having perfect security without the use of public or secret key. Goals set are accomplished through contrasting test results of a steganographic scheme that exploits English words with corresponding acronyms for hiding bits of secret information in chat - a preferred way to exchange messages these days. The misapprehension about perfect security and reign in characteristic of stego key in bit embedding process are unfolded respectively by launching elementary chosen-message and chosen-cover attack, and through proposed enhancement of target scheme.
RBAC Architecture Design Issues in Institutions Collaborative Environment
Venue: arXiv cs.SE 2013
Year: 2013

Institutional collaborative systems focus on providing the fast, and secure connections to students, teaching and non-teaching staff members. Access control is more important in these types of systems because different kind of users access the system on different levels. So a proper architecture must be there for these kinds of systems, for providing an efficient and secure system. As lot of work was done in RBAC like for grouping, securing the system, ease of use, and for enterprise etc but no one apply all these concepts as a whole on institution level. So, this paper will be a step towards administrative load sharing, securing the system, and ease of use.
Optimal Transmit Filters for ISI Channels under Channel Shortening Detection
Venue: arXiv cs.IT 2013
Year: 2013

We consider channels affected by intersymbol interference with reduced-complexity, mutual information optimized, channel-shortening detection. For such settings, we optimize the transmit filter, taking into consideration the reduced receiver complexity constraint. As figure of merit, we consider the achievable information rate of the entire system and with functional analysis, we establish a general form of the optimal transmit filter, which can then be optimized by standard numerical methods. As a corollary to our main result, we obtain some insight of the behavior of the standard waterfilling algorithm for intersymbol interference channels. With only some minor changes, the general form we derive can be applied to multiple-input multiple-output channels with intersymbol interference. To illuminate the practical use of our results, we provide applications of our theoretical results by deriving the optimal shaping pulse of a linear modulation transmitted over a bandlimited additive white Gaussian noise channel which has possible applications in the faster-than-Nyquist/time packing technique.
Cultural Evolution as Distributed Computation
Venue: arXiv cs.MA 2013
Year: 2013

The speed and transformative power of human cultural evolution is evident from the change it has wrought on our planet. This chapter proposes a human computation program aimed at (1) distinguishing algorithmic from non-algorithmic components of cultural evolution, (2) computationally modeling the algorithmic components, and amassing human solutions to the non-algorithmic (generally, creative) components, and (3) combining them to develop human-machine hybrids with previously unforeseen computational power that can be used to solve real problems. Drawing on recent insights into the origins of evolutionary processes from biology and complexity theory, human minds are modeled as self-organizing, interacting, autopoietic networks that evolve through a Lamarckian (non-Darwinian) process of communal exchange. Existing computational models as well as directions for future research are discussed.
Utility-based Decision-making in Distributed Systems Modelling
Venue: arXiv cs.LO 2013
Year: 2013

We consider a calculus of resources and processes as a basis for modelling decision-making in multi-agent systems. The calculus represents the regulation of agents' choices using utility functions that take account of context. Associated with the calculus is a (Hennessy Milner-style) context sensitive modal logic of state. As an application, we show how a notion of `trust domain' can be defined for multi-agent systems.
The Shape of Reactive Coordination Tasks
Venue: arXiv cs.LO 2013
Year: 2013

This paper studies the interaction between knowledge, time and coordination in systems in which timing information is available. Necessary conditions are given for the causal structure in coordination problems consisting of orchestrating a set of actions in a manner that satisfies a variety of temporal ordering assumptions. Results are obtained in two main steps: A specification of coordination is shown to require epistemic properties, and the causal structure required to obtain these properties is characterised via "knowledge gain" theorems. A new causal structure called a centibroom structure is presented, generalising previous causal structures for this model. It is shown to capture coordination tasks in which a sequence of clusters of events is performed in linear order, while within each cluster all actions must take place simultaneously. This form of coordination is shown to require the agents to gain a nested common knowledge of particular facts, which in turn requires a centibroom. Altogether, the results presented provide a broad view of the causal shape underlying partially ordered coordinated actions. This, in turn, provides insight into and can enable the design of efficient solutions to the coordination tasks in question.
Defeasible Modalities
Venue: arXiv cs.LO 2013
Year: 2013

Nonmonotonic logics are usually characterized by the presence of some notion of 'conditional' that fails monotonicity. Research on nonmonotonic logics is therefore largely concerned with the defeasibility of argument forms and the associated normality (or abnormality) of its constituents. In contrast, defeasible modes of inference aim to formalize the defeasible aspects of modal notions such as actions, obligations and knowledge. In this work we enrich the standard possible worlds semantics with a preference ordering on worlds in Kripke models. The resulting family of modal logics allow for the elegant expression of defeasible modalities. We also propose a tableau calculus which is sound and complete with respect to our preferential semantics.
Bounded rationality in a dynamic alternate game
Venue: arXiv cs.GT 2013
Year: 2013

From the standpoint of game theory, dominoes is a game that has not received much attention (specially the variety known as draw). It is usually thought that this game is already solved, given general results in game theory. However, the determination of equilibria is not feasible for the general case because of the well known problem of node explosion in the tree expressing the game. We propose a new model based in limited forecast as a kind of bounded rationality for dynamic alternate games.
Estimating Channel Parameters from the Syndrome of a Linear Code
Venue: arXiv cs.IT 2013
Year: 2013

In this letter, we analyse the properties of a maximum likelihood channel estimator based on the syndrome of a linear code. For the two examples of a binary symmetric channel and a binary input additive white Gaussian noise channel, we derive expressions for the bias and the mean squared error and compare them to the Cramér-Rao bound. The analytical expressions show the relationship between the estimator properties and the parameters of the linear code, i.e., the number of check nodes and the check node degree.
PDL as a Multi-Agent Strategy Logic
Venue: arXiv cs.GT 2013
Year: 2013

Propositional Dynamic Logic or PDL was invented as a logic for reasoning about regular programming constructs. We propose a new perspective on PDL as a multi-agent strategic logic (MASL). This logic for strategic reasoning has group strategies as first class citizens, and brings game logic closer to standard modal logic. We demonstrate that MASL can express key notions of game theory, social choice theory and voting theory in a natural way, we give a sound and complete proof system for MASL, and we show that MASL encodes coalition logic. Next, we extend the language to epistemic multi-agent strategic logic (EMASL), we give examples of what it can express, we propose to use it for posing new questions in epistemic social choice theory, and we give a calculus for reasoning about a natural class of epistemic game models. We end by listing avenues for future research and by tracing connections to a number of other logics for reasoning about strategies.
Facebook and the Epistemic Logic of Friendship
Venue: arXiv cs.LO 2013
Year: 2013

This paper presents a two-dimensional modal logic for reasoning about the changing patterns of knowledge and social relationships in networks organised on the basis of a symmetric 'friendship' relation, providing a precise language for exploring 'logic in the community' [11]. Agents are placed in the model, allowing us to express such indexical facts as 'I am your friend' and 'You, my friends, are in danger'. The technical framework for this work is general dynamic dynamic logic (GDDL) [4], which provides a general method for extending modal logics with dynamic operators for reasoning about a wide range of model-transformations, starting with those definable in propositional dynamic logic (PDL) and extended to allow for the more subtle operators involved in, for example, private communication, as represented in dynamic epistemic logic (DEL) and related systems. We provide a hands-on introduction to GDDL, introducing elements of the formalism as we go, but leave the reader to consult [4] for technical details. Instead, the purpose of this paper is to investigate a number of conceptual issues that arise when considering communication between agents in such networks, both from one agent to another, and broadcasts to socially-defined groups of agents, such as the group of my friends.