OpenRaiser/Intern-Atlas huggingface dataset:
Complementary cooperation, minimal winning coalitions, and power indices
Venue: arXiv cs.GT 2012
Year: 2012

We introduce a new simple game, which is referred to as the complementary weighted multiple majority game (C-WMMG for short). C-WMMG models a basic cooperation rule, the complementary cooperation rule, and can be taken as a sister model of the famous weighted majority game (WMG for short). In this paper, we concentrate on the two dimensional C-WMMG. An interesting property of this case is that there are at most $n+1$ minimal winning coalitions (MWC for short), and they can be enumerated in time $O(n\log n)$, where $n$ is the number of players. This property guarantees that the two dimensional C-WMMG is more handleable than WMG. In particular, we prove that the main power indices, i.e. the Shapley-Shubik index, the Penrose-Banzhaf index, the Holler-Packel index, and the Deegan-Packel index, are all polynomially computable. To make a comparison with WMG, we know that it may have exponentially many MWCs, and none of the four power indices is polynomially computable (unless P=NP). Still for the two dimensional case, we show that local monotonicity holds for all of the four power indices. In WMG, this property is possessed by the Shapley-Shubik index and the Penrose-Banzhaf index, but not by the Holler-Packel index or the Deegan-Packel index. Since our model fits very well the cooperation and competition in team sports, we hope that it can be potentially applied in measuring the values of players in team sports, say help people give more objective ranking of NBA players and select MVPs, and consequently bring new insights into contest theory and the more general field of sports economics. It may also provide some interesting enlightenments into the design of non-additive voting mechanisms. Last but not least, the threshold version of C-WMMG is a generalization of WMG, and natural variants of it are closely related with the famous airport game and the stable marriage/roommates problem.
A Linear Vertex Kernel for Maximum Internal Spanning Tree
Venue: arXiv cs.DS 2012
Year: 2012

We present a polynomial time algorithm that for any graph G and integer k >= 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G' on at most 3k vertices and an integer k' such that G has a spanning tree with at least k internal vertices if and only if G' has a spanning tree with at least k' internal vertices. In other words, we show that the Maximum Internal Spanning Tree problem parameterized by the number of internal vertices k, has a 3k-vertex kernel. Our result is based on an innovative application of a classical min-max result about hypertrees in hypergraphs which states that "a hypergraph H contains a hypertree if and only if H is partition connected."
Geometry of the Welch Bounds
Venue: arXiv cs.IT 2012
Year: 2012

A geometric perspective involving Grammian and frame operators is used to derive the entire family of Welch bounds. This perspective unifies a number of observations that have been made regarding tightness of the bounds and their connections to symmetric k-tensors, tight frames, homogeneous polynomials, and t-designs. In particular. a connection has been drawn between sampling of homogeneous polynomials and frames of symmetric k-tensors. It is also shown that tightness of the bounds requires tight frames. The lack of tight frames in symmetric k-tensors in many cases, however, leads to consideration of sets that come as close as possible to attaining the bounds. The geometric derivation is then extended in the setting of generalized or continuous frames. The Welch bounds for finite sets and countably infinite sets become special cases of this general setting.
On disjoint matchings in cubic graphs: maximum 2- and 3-edge-colorable subgraphs
Venue: arXiv cs.DM 2012
Year: 2012

We show that any $2-$factor of a cubic graph can be extended to a maximum $3-$edge-colorable subgraph. We also show that the sum of sizes of maximum $2-$ and $3-$edge-colorable subgraphs of a cubic graph is at least twice of its number of vertices. Finally, for a cubic graph $G$, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let $H$ be the largest matching among such pairs. Let $M$ be a maximum matching of $G$. We show that 9/8 is a tight upper bound for $|M|/|H|$.
Randomness Efficient Steganography
Venue: arXiv cs.CR 2012
Year: 2012

Steganographic protocols enable one to embed covert messages into inconspicuous data over a public communication channel in such a way that no one, aside from the sender and the intended receiver, can even detect the presence of the secret message. In this paper, we provide a new provably-secure, private-key steganographic encryption protocol secure in the framework of Hopper et al. We first present a "one-time stegosystem" that allows two parties to transmit messages of length at most that of the shared key with information-theoretic security guarantees. The employment of a pseudorandom generator (PRG) permits secure transmission of longer messages in the same way that such a generator allows the use of one-time pad encryption for messages longer than the key in symmetric encryption. The advantage of our construction, compared to all previous work is randomness efficiency: in the information theoretic setting our protocol embeds a message of length n bits using a shared secret key of length (1+o(1))n bits while achieving security 2^{-n/log^{O(1)}n}; simply put this gives a rate of key over message that is 1 as n tends to infinity (the previous best result achieved a constant rate greater than 1 regardless of the security offered). In this sense, our protocol is the first truly randomness efficient steganographic system. Furthermore, in our protocol, we can permit a portion of the shared secret key to be public while retaining precisely n private key bits. In this setting, by separating the public and the private randomness of the shared key, we achieve security of 2^{-n}. Our result comes as an effect of the application of randomness extractors to stegosystem design. To the best of our knowledge this is the first time extractors have been applied in steganography.
Performance of Joint Spectrum Sensing and MAC Algorithms for Multichannel Opportunistic Spectrum Access Ad Hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

We present an analytical framework to assess the link layer throughput of multichannel Opportunistic Spectrum Access (OSA) ad hoc networks. Specifically, we focus on analyzing various combinations of collaborative spectrum sensing and Medium Access Control (MAC) protocol abstractions. We decompose collaborative spectrum sensing into layers, parametrize each layer, classify existing solutions, and propose a new protocol called Truncated Time Division Multiple Access (TTDMA) that supports efficient distribution of sensing results in "k out of N" fusion rule. In case of multichannel MAC protocols we evaluate two main approaches of control channel design with (i) dedicated and (ii) hopping channel. We propose to augment these protocols with options of handling secondary user (SU) connections preempted by primary user (PU) by (i) connection buffering until PU departure and (ii) connection switching to a vacant PU channel. By comparing and optimizing different design combinations we show that (i) it is generally better to buffer preempted SU connections than to switch them to PU vacant channels and (ii) TTDMA is a promising design option for collaborative spectrum sensing process when k does not change over time.
Instruction sequence processing operators
Venue: arXiv cs.LO 2012
Year: 2012

Instruction sequence is a key concept in practice, but it has as yet not come prominently into the picture in theoretical circles. This paper concerns instruction sequences, the behaviours produced by them under execution, the interaction between these behaviours and components of the execution environment, and two issues relating to computability theory. Positioning Turing's result regarding the undecidability of the halting problem as a result about programs rather than machines, and taking instruction sequences as programs, we analyse the autosolvability requirement that a program of a certain kind must solve the halting problem for all programs of that kind. We present novel results concerning this autosolvability requirement. The analysis is streamlined by using the notion of a functional unit, which is an abstract state-based model of a machine. In the case where the behaviours exhibited by a component of an execution environment can be viewed as the behaviours of a machine in its different states, the behaviours concerned are completely determined by a functional unit. The above-mentioned analysis involves functional units whose possible states represent the possible contents of the tapes of Turing machines with a particular tape alphabet. We also investigate functional units whose possible states are the natural numbers. This investigation yields a novel computability result, viz. the existence of a universal computable functional unit for natural numbers.
Sequential anomaly detection in the presence of noise and limited feedback
Venue: arXiv cs.LG 2012
Year: 2012

This paper describes a methodology for detecting anomalies from sequentially observed and potentially noisy data. The proposed approach consists of two main elements: (1) {\em filtering}, or assigning a belief or likelihood to each successive measurement based upon our ability to predict it from previous noisy observations, and (2) {\em hedging}, or flagging potential anomalies by comparing the current belief against a time-varying and data-adaptive threshold. The threshold is adjusted based on the available feedback from an end user. Our algorithms, which combine universal prediction with recent work on online convex programming, do not require computing posterior distributions given all current observations and involve simple primal-dual parameter updates. At the heart of the proposed approach lie exponential-family models which can be used in a wide variety of contexts and applications, and which yield methods that achieve sublinear per-round regret against both static and slowly varying product distributions with marginals drawn from the same exponential family. Moreover, the regret against static distributions coincides with the minimax value of the corresponding online strongly convex game. We also prove bounds on the number of mistakes made during the hedging step relative to the best offline choice of the threshold with access to all estimated beliefs and feedback signals. We validate the theory on synthetic data drawn from a time-varying distribution over binary vectors of high dimensionality, as well as on the Enron email dataset.
Automated languages phylogeny from Levenshtein distance
Venue: arXiv cs.CL 2012
Year: 2012

Languages evolve over time in a process in which reproduction, mutation and extinction are all possible, similar to what happens to living organisms. Using this similarity it is possible, in principle, to build family trees which show the degree of relatedness between languages. The method used by modern glottochronology, developed by Swadesh in the 1950s, measures distances from the percentage of words with a common historical origin. The weak point of this method is that subjective judgment plays a relevant role. Recently we proposed an automated method that avoids the subjectivity, whose results can be replicated by studies that use the same database and that doesn't require a specific linguistic knowledge. Moreover, the method allows a quick comparison of a large number of languages. We applied our method to the Indo-European and Austronesian families, considering in both cases, fifty different languages. The resulting trees are similar to those of previous studies, but with some important differences in the position of few languages and subgroups. We believe that these differences carry new information on the structure of the tree and on the phylogenetic relationships within families.
The Multivariate Resultant is NP-hard in any Characteristic
Venue: arXiv cs.CC 2012
Year: 2012

The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of n homogeneous equations in n variables is satisfiable (the resultant is a polynomial in the system's coefficients which vanishes if and only if the system is satisfiable). In this paper we present several NP-hardness results for testing whether a multivariate resultant vanishes, or equivalently for deciding whether a square system of homogeneous equations is satisfiable. Our main result is that testing the resultant for zero is NP-hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). We also observe that in characteristic zero, this problem is in the Arthur-Merlin class AM if the generalized Riemann hypothesis holds true. In positive characteristic, the best upper bound remains PSPACE.
Windtalking Computers: Frequency Normalization, Binary Coding Systems and Encryption
Venue: arXiv cs.CR 2012
Year: 2012

This paper discusses the application of known techniques, knowledge and technology in a novel way for encryption. Two distinct and separate methods are presented. Method 1: Alter the symbol set of the language by adding additional redundant symbols for frequent symbols. This will reduce the high frequency of more commonly used symbols. Hence, frequency analysis upon ciphertext will not be possible. Hence, decryption will be possible. Method 2: Computers use binary base 2. Most encryption systems use ciphering to convert data to ciphertext. The author presents the theory and several possible implementations of a method for computers analogous to speaking another language. This is done by using a binary base other than base 2. Ex. Fibonacci, Phi or Prime. In addition, steganography may be used for creating alternate binary bases. This kind of encryption significantly increases the complexity of decryption. First the binary base must be known. Only then, can decryption begin. This kind of encryption also breaks the transitivity of plaintext-codebook-binary; the correlation of letters-ASCII-base2. With this transitivity broken, decryption is logically impossible. Coupled with encrypting the plaintext, binary encryption makes decryption uncrackable. It may produce false positives--information theoretic secure, and requires much more computing power to resolve than is currently used in brute force decryption. Hence, the assertion that these combination of methods are computationally secure--impervious to brute force. The proposed system has a drawback. It is not as compressed as a base2. (Similar to adding random padding to the encryption.) However, this is acceptable, since the goal is very strong encryption: Both methods are not decryptable by method uncrackable - by conventional, statistical means.
Games on Social Networks: On a Problem Posed by Goyal
Venue: arXiv cs.GT 2012
Year: 2012

Within the context of games on networks S. Goyal (Goya (2007), pg. 39) posed the following problem. Under any arbitrary but fixed topology, does there exist at least one pure Nash equilibrium that exhibits a positive relation between the cardinality of a player's set of neighbors and its utility payoff? In this paper we present a class of topologies/games in which pure Nash equilibria with the above property do not exist.
Regularized Modified BPDN for Noisy Sparse Reconstruction with Partial Erroneous Support and Signal Value Knowledge
Venue: arXiv cs.IT 2012
Year: 2012

We study the problem of sparse reconstruction from noisy undersampled measurements when the following two things are available. (1) We are given partial, and partly erroneous, knowledge of the signal's support, denoted by $T$. (2) We are also given an erroneous estimate of the signal values on $T$, denoted by $(\hatμ)_T$. In practice, both these may be available from available prior knowledge. Alternatively, in recursive reconstruction applications, like real-time dynamic MRI, one can use the support estimate and the signal value estimate from the previous time instant as $T$ and $(\hatμ)_T$. In this work, we introduce regularized modified-BPDN (reg-mod-BPDN) and obtain computable bounds on its reconstruction error. Reg-mod-BPDN tries to find the signal that is sparsest outside the set $T$, while being "close enough" to $(\hatμ)_T$ on $T$ and while satisfying the data constraint. Corresponding results for modified-BPDN and BPDN follow as direct corollaries. A second key contribution is an approach to obtain computable error bounds that hold without any sufficient conditions. This makes it easy to compare the bounds for the various approaches. Empirical reconstruction error comparisons with many existing approaches are also provided.
Finding and counting vertex-colored subtrees
Venue: arXiv cs.CC 2012
Year: 2012

The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. in the context of biological networks. The problem is to decide if a vertex-colored graph has a connected subgraph whose colors equal a given multiset of colors $M$. It is a graph pattern-matching problem variant, where the structure of the occurrence of the pattern is not of interest but the only requirement is the connectedness. Using an algebraic framework recently introduced by Koutis et al., we obtain new FPT algorithms for Graph Motif and variants, with improved running times. We also obtain results on the counting versions of this problem, proving that the counting problem is FPT if M is a set, but becomes W[1]-hard if M is a multiset with two colors. Finally, we present an experimental evaluation of this approach on real datasets, showing that its performance compares favorably with existing software.
SSMS - A Secure SMS Messaging Protocol for the M-payment Systems
Venue: arXiv cs.CR 2012
Year: 2012

The GSM network with the greatest worldwide number of users, succumbs to several security vulnerabilities. The short message service (SMS) is one of its superior and well-tried services with a global availability in the GSM networks. The main contribution of this paper is to introduce a new secure application layer protocol, called SSMS, to efficiently embed the desired security attributes in the SMS messages to be used as a secure bearer in the m-payment systems. SSMS efficiently embeds the confidentiality, integrity, authentication, and non-repudiation in the SMS messages. It provides an elliptic curve-based public key solution that uses public keys for the secret key establishment of a symmetric encryption. It also provides the attributes of public verification and forward secrecy. It efficiently makes the SMS messaging suitable for the m-payment applications where the security is the great concern.
Message-Passing Algorithms: Reparameterizations and Splittings
Venue: arXiv cs.IT 2012
Year: 2012

The max-product algorithm, a local message-passing scheme that attempts to compute the most probable assignment (MAP) of a given probability distribution, has been successfully employed as a method of approximate inference for applications arising in coding theory, computer vision, and machine learning. However, the max-product algorithm is not guaranteed to converge to the MAP assignment, and if it does, is not guaranteed to recover the MAP assignment. Alternative convergent message-passing schemes have been proposed to overcome these difficulties. This work provides a systematic study of such message-passing algorithms that extends the known results by exhibiting new sufficient conditions for convergence to local and/or global optima, providing a combinatorial characterization of these optima based on graph covers, and describing a new convergent and correct message-passing algorithm whose derivation unifies many of the known convergent message-passing algorithms. While convergent and correct message-passing algorithms represent a step forward in the analysis of max-product style message-passing algorithms, the conditions needed to guarantee convergence to a global optimum can be too restrictive in both theory and practice. This limitation of convergent and correct message-passing schemes is characterized by graph covers and illustrated by example.
Formalization and Validation of Safety-Critical Requirements
Venue: arXiv cs.SE 2012
Year: 2012

The validation of requirements is a fundamental step in the development process of safety-critical systems. In safety critical applications such as aerospace, avionics and railways, the use of formal methods is of paramount importance both for requirements and for design validation. Nevertheless, while for the verification of the design, many formal techniques have been conceived and applied, the research on formal methods for requirements validation is not yet mature. The main obstacles are that, on the one hand, the correctness of requirements is not formally defined; on the other hand that the formalization and the validation of the requirements usually demands a strong involvement of domain experts. We report on a methodology and a series of techniques that we developed for the formalization and validation of high-level requirements for safety-critical applications. The main ingredients are a very expressive formal language and automatic satisfiability procedures. The language combines first-order, temporal, and hybrid logic. The satisfiability procedures are based on model checking and satisfiability modulo theory. We applied this technology within an industrial project to the validation of railways requirements.
Quantum codes from codes over Gaussian integers with respect to the Mannheim metric
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, some nonbinary quantum codes using classical codes over Gaussian integers are obtained. Also, some of our quantum codes are better than or comparable with those known before, (for instance [[8; 2; 5]]4+i).
Formal Relationships Between Geometrical and Classical Models for Concurrency
Venue: arXiv cs.DC 2012
Year: 2012

A wide variety of models for concurrent programs has been proposed during the past decades, each one focusing on various aspects of computations: trace equivalence, causality between events, conflicts and schedules due to resource accesses, etc. More recently, models with a geometrical flavor have been introduced, based on the notion of cubical set. These models are very rich and expressive since they can represent commutation between any bunch of events, thus generalizing the principle of true concurrency. While they seem to be very promising - because they make possible the use of techniques from algebraic topology in order to study concurrent computations - they have not yet been precisely related to the previous models, and the purpose of this paper is to fill this gap. In particular, we describe an adjunction between Petri nets and cubical sets which extends the previously known adjunction between Petri nets and asynchronous transition systems by Nielsen and Winskel.
An Elliptic Curve-based Signcryption Scheme with Forward Secrecy
Venue: arXiv cs.CR 2012
Year: 2012

An elliptic curve-based signcryption scheme is introduced in this paper that effectively combines the functionalities of digital signature and encryption, and decreases the computational costs and communication overheads in comparison with the traditional signature-then-encryption schemes. It simultaneously provides the attributes of message confidentiality, authentication, integrity, unforgeability, non-repudiation, public verifiability, and forward secrecy of message confidentiality. Since it is based on elliptic curves and can use any fast and secure symmetric algorithm for encrypting messages, it has great advantages to be used for security establishments in store-and-forward applications and when dealing with resource-constrained devices.