OpenRaiser/Intern-Atlas huggingface dataset:
Construction of Short Protocol Sequences with Worst-Case Throughput Guarantee
Venue: arXiv cs.IT 2010
Year: 2010

Protocol sequences are used in channel access for the multiple-access collision channel without feedback. A new construction of protocol sequences with a guarantee of worst-case system throughput is proposed. The construction is based on Chinese remainder theorem. The Hamming crosscorrelation is proved to be concentrated around the mean. The sequence period is much shorter than existing protocol sequences with the same throughput performance. The new construction reduces the complexity in implementation and also shortens the waiting time until a packet can be sent successfully.
A Data Cleansing Method for Clustering Large-scale Transaction Databases
Venue: arXiv cs.DB 2010
Year: 2010

In this paper, we emphasize the need for data cleansing when clustering large-scale transaction databases and propose a new data cleansing method that improves clustering quality and performance. We evaluate our data cleansing method through a series of experiments. As a result, the clustering quality and performance were significantly improved by up to 165% and 330%, respectively.
Logical methods of object recognition on satellite images using spatial constraints
Venue: arXiv cs.CV 2010
Year: 2010

A logical approach to object recognition on image is proposed. The main idea of the approach is to perform the object recognition as a logical inference on a set of rules describing an object shape.
On the Capacity of Compound State-Dependent Channels with States Known at the Transmitter
Venue: arXiv cs.IT 2010
Year: 2010

This paper investigates the capacity of compound state-dependent channels with non-causal state information available at only the transmitter. A new lower bound on the capacity of this class of channels is derived. This bound is shown to be tight for the special case of compound channels with stochastic degraded components, yielding the full characterization of the capacity. Specific results are derived for the compound Gaussian Dirty-Paper (GDP) channel. This model consists of an additive white Gaussian noise (AWGN) channel corrupted by an additive Gaussian interfering signal, known at the transmitter only, where the input and the state signals are affected by fading coefficients whose realizations are unknown at the transmitter. Our bounds are shown to be tight for specific cases. Applications of these results arise in a variety of wireless scenarios as multicast channels, cognitive radio and problems with interference cancellation.
Reed Muller Sensing Matrices and the LASSO
Venue: arXiv cs.IT 2010
Year: 2010

We construct two families of deterministic sensing matrices where the columns are obtained by exponentiating codewords in the quaternary Delsarte-Goethals code $DG(m,r)$. This method of construction results in sensing matrices with low coherence and spectral norm. The first family, which we call Delsarte-Goethals frames, are $2^m$ - dimensional tight frames with redundancy $2^{rm}$. The second family, which we call Delsarte-Goethals sieves, are obtained by subsampling the column vectors in a Delsarte-Goethals frame. Different rows of a Delsarte-Goethals sieve may not be orthogonal, and we present an effective algorithm for identifying all pairs of non-orthogonal rows. The pairs turn out to be duplicate measurements and eliminating them leads to a tight frame. Experimental results suggest that all $DG(m,r)$ sieves with $m\leq 15$ and $r\geq2$ are tight-frames; there are no duplicate rows. For both families of sensing matrices, we measure accuracy of reconstruction (statistical 0-1 loss) and complexity (average reconstruction time) as a function of the sparsity level $k$. Our results show that DG frames and sieves outperform random Gaussian matrices in terms of noiseless and noisy signal recovery using the LASSO.
The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)
Venue: arXiv cs.DS 2010
Year: 2010

One of the driving problems in the CSP area is the Dichotomy Conjecture, formulated in 1993 by Feder and Vardi [STOC'93], stating that for any fixed relational structure G the Constraint Satisfaction Problem CSP(G) is either NP--complete or polynomial time solvable. A large amount of research has gone into checking various specific cases of this conjecture. One such variant which attracted a lot of attention in the recent years is the LIST MATRIX PARTITION problem. In 2004 Cameron et al. [SODA'04] classified almost all LIST MATRIX PARTITION variants for matrices of size at most four. The only case which resisted the classification became known as the STUBBORN PROBLEM. In this paper we show a result which enables us to finish the classification - thus solving a problem which resisted attacks for the last six years. Our approach is based on a combinatorial problem known to be at least as hard as the STUBBORN PROBLEM - the 3-COMPATIBLE COLOURING problem. In this problem we are given a complete graph with each edge assigned one of 3 possible colours and we want to assign one of those 3 colours to each vertex in such a way that no edge has the same colour as both of its endpoints. The tractability of the 3-COMPATIBLE COLOURING problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [SODA'05] - a quasipolynomial algorithm with a n^O(log n / log log n) time complexity. In this paper we present a polynomial-time algorithm for the 3-COMPATIBLE COLOURING problem and consequently we prove a dichotomy for the k-COMPATIBLE COLOURING problem.
The Two-User Deterministic Interference Channel with Rate-Limited Feedback
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we study the effect of rate-limited feedback on the sum-rate capacity of the deterministic interference channel. We characterize the sum-rate capacity of this channel in the symmetric case and show that having feedback links can increase the sum-rate capacity by at most the rate of the available feedback. Our proof includes a novel upper-bound on the sum-rate capacity and a set of new achievability strategies.
The Application of a Dendritic Cell Algorithm to a Robotic Classifier
Venue: arXiv cs.AI 2010
Year: 2010

The dendritic cell algorithm is an immune-inspired technique for processing time-dependant data. Here we propose it as a possible solution for a robotic classification problem. The dendritic cell algorithm is implemented on a real robot and an investigation is performed into the effects of varying the migration threshold median for the cell population. The algorithm performs well on a classification task with very little tuning. Ways of extending the implementation to allow it to be used as a classifier within the field of robotic security are suggested.
On the Rationality of Escalation
Venue: arXiv cs.GT 2010
Year: 2010

Escalation is a typical feature of infinite games. Therefore tools conceived for studying infinite mathematical structures, namely those deriving from coinduction are essential. Here we use coinduction, or backward coinduction (to show its connection with the same concept for finite games) to study carefully and formally the infinite games especially those called dollar auctions, which are considered as the paradigm of escalation. Unlike what is commonly admitted, we show that, provided one assumes that the other agent will always stop, bidding is rational, because it results in a subgame perfect equilibrium. We show that this is not the only rational strategy profile (the only subgame perfect equilibrium). Indeed if an agent stops and will stop at every step, we claim that he is rational as well, if one admits that his opponent will never stop, because this corresponds to a subgame perfect equilibrium. Amazingly, in the infinite dollar auction game, the behavior in which both agents stop at each step is not a Nash equilibrium, hence is not a subgame perfect equilibrium, hence is not rational.
On Application of the Local Search and the Genetic Algorithms Techniques to Some Combinatorial Optimization Problems
Venue: arXiv cs.NE 2010
Year: 2010

In this paper the approach to solving several combinatorial optimization problems using the local search and the genetic algorithm techniques is proposed. Initially this approach was developed in purpose to overcome some difficulties inhibiting the application of above mentioned techniques to the problems of the Questionnaire Theory. But when the algorithms were developed it became clear that them could be successfully applied also to the Minimum Set Cover, the 0-1-Knapsack and probably to other combinatorial optimization problems.
Isometric Embeddings in Imaging and Vision: Facts and Fiction
Venue: arXiv cs.CV 2010
Year: 2010

We explore the practicability of Nash's Embedding Theorem in vision and imaging sciences. In particular, we investigate the relevance of a result of Burago and Zalgaller regarding the existence of isometric embeddings of polyhedral surfaces in $\mathbb{R}^3$ and we show that their proof does not extended directly to higher dimensions.
Graphic Symbol Recognition using Graph Based Signature and Bayesian Network Classifier
Venue: arXiv cs.CV 2010
Year: 2010

We present a new approach for recognition of complex graphic symbols in technical documents. Graphic symbol recognition is a well known challenge in the field of document image analysis and is at heart of most graphic recognition systems. Our method uses structural approach for symbol representation and statistical classifier for symbol recognition. In our system we represent symbols by their graph based signatures: a graphic symbol is vectorized and is converted to an attributed relational graph, which is used for computing a feature vector for the symbol. This signature corresponds to geometry and topology of the symbol. We learn a Bayesian network to encode joint probability distribution of symbol signatures and use it in a supervised learning scenario for graphic symbol recognition. We have evaluated our method on synthetically deformed and degraded images of pre-segmented 2D architectural and electronic symbols from GREC databases and have obtained encouraging recognition rates.
On Distance Properties of Quasi-Cyclic Protograph-Based LDPC Codes
Venue: arXiv cs.IT 2010
Year: 2010

Recent work has shown that properly designed protograph-based LDPC codes may have minimum distance linearly increasing with block length. This notion rests on ensemble arguments over all possible expansions of the base protograph. When implementation complexity is considered, the expansion is typically chosen to be quite orderly. For example, protograph expansion by cyclically shifting connections creates a quasi-cyclic (QC) code. Other recent work has provided upper bounds on the minimum distance of QC codes. In this paper, these bounds are expanded upon to cover puncturing and tightened in several specific cases. We then evaluate our upper bounds for the most prominent protograph code thus far, one proposed for deep-space usage in the CCSDS experimental standard, the code known as AR4JA.
Strong Secrecy for Erasure Wiretap Channels
Venue: arXiv cs.IT 2010
Year: 2010

We show that duals of certain low-density parity-check (LDPC) codes, when used in a standard coset coding scheme, provide strong secrecy over the binary erasure wiretap channel (BEWC). This result hinges on a stopping set analysis of ensembles of LDPC codes with block length $n$ and girth $\geq 2k$, for some $k \geq 2$. We show that if the minimum left degree of the ensemble is $l_\mathrm{min}$, the expected probability of block error is $\calO(\frac{1}{n^{\lceil l_\mathrm{min} k /2 \rceil - k}})$ when the erasure probability $ε< ε_\mathrm{ef}$, where $ε_\mathrm{ef}$ depends on the degree distribution of the ensemble. As long as $l_\mathrm{min} > 2$ and $k > 2$, the dual of this LDPC code provides strong secrecy over a BEWC of erasure probability greater than $1 - ε_\mathrm{ef}$.
Optimal ordering of transmissions for computing Boolean threhold functions
Venue: arXiv cs.IT 2010
Year: 2010

We address a sequential decision problem that arises in the computation of symmetric Boolean functions of distributed data. We consider a collocated network, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and we wish to compute a given Boolean function of these measurements. We suppose that the measurements are independent and Bernoulli distributed. Thus, the problem of optimal computation becomes the problem of optimally ordering node's transmissions so as to minimize the total expected number of bits. We solve the ordering problem for the class of Boolean threshold functions. The optimal ordering is dynamic, i.e., it could potentially depend on the values of previously transmitted bits. Further, it depends only on the ordering of the marginal probabilites, but not on their exact values. This provides an elegant structure for the optimal strategy. For the case where each node has a block of measurements, the problem is significantly harder, and we conjecture the optimal strategy.
Secret Sharing Based on a Hard-on-Average Problem
Venue: arXiv cs.CR 2010
Year: 2010

The main goal of this work is to propose the design of secret sharing schemes based on hard-on-average problems. It includes the description of a new multiparty protocol whose main application is key management in networks. Its unconditionally perfect security relies on a discrete mathematics problem classiffied as DistNP-Complete under the average-case analysis, the so-called Distributional Matrix Representability Problem. Thanks to the use of the search version of the mentioned decision problem, the security of the proposed scheme is guaranteed. Although several secret sharing schemes connected with combinatorial structures may be found in the bibliography, the main contribution of this work is the proposal of a new secret sharing scheme based on a hard-on-average problem, which allows to enlarge the set of tools for designing more secure cryptographic applications.
A Rational Approach to Cryptographic Protocols
Venue: arXiv cs.CR 2010
Year: 2010

This work initiates an analysis of several cryptographic protocols from a rational point of view using a game-theoretical approach, which allows us to represent not only the protocols but also possible misbehaviours of parties. Concretely, several concepts of two-person games and of two-party cryptographic protocols are here combined in order to model the latters as the formers. One of the main advantages of analysing a cryptographic protocol in the game-theory setting is the possibility of describing improved and stronger cryptographic solutions because possible adversarial behaviours may be taken into account directly. With those tools, protocols can be studied in a malicious model in order to find equilibrium conditions that make possible to protect honest parties against all possible strategies of adversaries.
Personnalisation de Systèmes OLAP Annotés
Venue: arXiv cs.DB 2010
Year: 2010

This paper deals with personalization of annotated OLAP systems. Data constellation is extended to support annotations and user preferences. Annotations reflect the decision-maker experience whereas user preferences enable users to focus on the most interesting data. User preferences allow annotated contextual recommendations helping the decision-maker during his/her multidimensional navigations.
Algèbre OLAP et langage graphique
Venue: arXiv cs.DB 2010
Year: 2010

This article deals with OLAP systems based on multidimensional model. The conceptual model we provide, represents data through a constellation (multi-facts) composed of several multi-hierarchy dimensions. In this model, data are displayed through multidimensional tables. We define a query algebra handling these tables. This user oriented algebra is composed of a closure core of OLAP operators as soon as advanced operators dedicated to complex analysis. Finally, we specify a graphical OLAP language based on this algebra. This language facilitates analyses of decision makers.
Towards Conceptual Multidimensional Design in Decision Support Systems
Venue: arXiv cs.DB 2010
Year: 2010

Multidimensional databases support efficiently on-line analytical processing (OLAP). In this paper, we depict a model dedicated to multidimensional databases. The approach we present designs decisional information through a constellation of facts and dimensions. Each dimension is possibly shared between several facts and it is organised according to multiple hierarchies. In addition, we define a comprehensive query algebra regrouping the more popular multidimensional operations in current commercial systems and research approaches. We introduce new operators dedicated to a constellation. Finally, we describe a prototype that allows managers to query constellations of facts, dimensions and multiple hierarchies.
Software Requirements Specification of the IUfA's UUIS -- a Team 1 COMP5541-W10 Project Approach
Venue: arXiv cs.SE 2010
Year: 2010

Unified University Inventory System (UUIS), is an inventory system created for the Imaginary University of Arctica (IUfA) to facilitate its inventory management, of all the faculties in one system. Team 1 elucidates the functions of the system and the characteristics of the users who have access to these functions. It shows the access restrictions to different functionalities of the system provided to users, who are the staff and students of the University. Team 1, also, emphasises on the necessary steps required to prevent the security of the system and its data.
Software Design Document, Testing, and Deployment and Configuration Management of the UUIS - a Team 1 COMP5541-W10 Project Approach
Venue: arXiv cs.SE 2010
Year: 2010

The document presents a detailed description of the designs for the implementation of the Unified University Inventory System for the Imaginary University of Arctica. The document, through numerous diagrams and UI samples, gives the structure of the system and the functions of its modules. It also gives test cases and reports that support the system's architecture and design.
Informal Concepts in Machines
Venue: arXiv cs.AI 2010
Year: 2010

This paper constructively proves the existence of an effective procedure generating a computable (total) function that is not contained in any given effectively enumerable set of such functions. The proof implies the existence of machines that process informal concepts such as computable (total) functions beyond the limits of any given Turing machine or formal system, that is, these machines can, in a certain sense, "compute" function values beyond these limits. We call these machines creative. We argue that any "intelligent" machine should be capable of processing informal concepts such as computable (total) functions, that is, it should be creative. Finally, we introduce hypotheses on creative machines which were developed on the basis of theoretical investigations and experiments with computer programs. The hypotheses say that machine intelligence is the execution of a self-developing procedure starting from any universal programming language and any input.
Security Through Entertainment: Experiences Using a Memory Game for Secure Device Pairing
Venue: arXiv cs.CR 2010
Year: 2010

The secure "pairing" of wireless devices based on auxiliary or out-of-band (OOB) communication, such as audio, visual, or tactile channels, is a well-established research direction. However, prior work shows that this approach to pairing can be prone to human errors of different forms that may directly or indirectly translate into man-in-the-middle attacks. To address this problem, we propose a general direction of the use of computer games for pairing. Since games are a popular means of entertainment, our hypothesis is that they may serve as an incentive to users and make the pairing process enjoyable for them, thus improving the usability, as well as the security, of the pairing process. We consider an emerging use case of pairing whereby two different users are involved, each in possession of his or her own device (e.g., Alice and Bob pairing their smartphones for social interactions). We develop "Alice Says," a pairing game based on a popular memory game called Simon (Says), and discuss the underlying design challenges. We also present a preliminary evaluation of Alice Says via a usability study and demonstrate its feasibility in terms of usability and security. Our results indicate that overall Alice Says was deemed as a fun and an enjoyable way to pair devices, confirming our hypothesis. However, contrary to our intuition, the relatively slower speed of Alice Says pairing was found to be a cause of concern and prompts the need for the design of faster pairing games. We put forth several ways in which this issue can be ameliorated. In addition, we also discuss several other security problems which are lacking optimal solutions and suggest ideas on how entertainment can be used to improve the current state of the art solutions that have been developed to address them.
Software Design Document, Testing, Deployment and Configuration Management of the UUIS--a Team 2 COMP5541-W10 Project Approach
Venue: arXiv cs.SE 2010
Year: 2010

The Software Design Document of UUIS describes the prototype design details of the system architecture, database layer, deployment and configuration details as well as test cases produced while working the design and implementation of the prototype. The requirements specification of UUIS are detailed in arXiv:1005.0783.
Empowered by Wireless Communication: Self-Organizing Traffic Collectives
Venue: arXiv cs.NI 2010
Year: 2010

In recent years, tremendous progress has been made in understanding the dynamics of vehicle traffic flow and traffic congestion by interpreting traffic as a multi-particle system. This helps to explain the onset and persistence of many undesired phenomena, e.g., traffic jams. It also reflects the apparent helplessness of drivers in traffic, who feel like passive particles that are pushed around by exterior forces; one of the crucial aspects is the inability to communicate and coordinate with other traffic participants. We present distributed methods for solving these fundamental problems, employing modern wireless, ad-hoc, multi-hop networks. The underlying idea is to use these capabilities as the basis for self-organizing methods for coordinating data collection and processing, recognizing traffic phenomena, and changing their structure by coordinated behavior. The overall objective is a multi-level approach that reaches from protocols for local wireless communication, data dissemination, pattern recognition, over hierarchical structuring and coordinated behavior, all the way to large-scale traffic regulation. In this article we describe three types of results: (i) self-organizing and distributed methods for maintaining and collecting data (using our concept of Hovering Data Clouds); (ii) adaptive data dissemination for traffic information systems; (iii) methods for self-recognition of traffic jams. We conclude by describing higher-level aspects of our work.
Outage rates and outage durations of opportunistic relaying systems
Venue: arXiv cs.IT 2010
Year: 2010

Opportunistic relaying is a simple yet efficient cooperation scheme that achieves full diversity and preserves the spectral efficiency among the spatially distributed stations. However, the stations' mobility causes temporal correlation of the system's capacity outage events, which gives rise to its important second-order outage statistical parameters, such as the average outage rate (AOR) and the average outage duration (AOD). This letter presents exact analytical expressions for the AOR and the AOD of an opportunistic relaying system, which employs a mobile source and a mobile destination (without a direct path), and an arbitrary number of (fixed-gain amplify-and-forward or decode-and-forward) mobile relays in Rayleigh fading environment.