OpenRaiser/Intern-Atlas huggingface dataset:
Error-Correction of Multidimensional Bursts
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we present several constructions to generate codes for correcting a multidimensional cluster-error. The goal is to correct a cluster-error whose shape can be a box-error, a Lee sphere error, or an error with an arbitrary shape. Our codes have very low redundancy, close to optimal, and large range of parameters of arrays and clusters. Our main results are summarized as follows: 1) A construction of two-dimensional codes capable to correct a rectangular-error with considerably more flexible parameters from previously known constructions. Another advantage of this construction is that it is easily generalized for D dimensions. 2) A novel method based on D colorings of the D-dimensional space for constructing D-dimensional codes correcting D-dimensional cluster-error of various shapes. This method is applied efficiently to correct a D-dimensional cluster error of parameters not covered efficiently by previous onstructions. 3) A transformation of the D-dimensional space into another D-dimensional space such that a D-dimensional Lee sphere is transformed into a shape located in a D-dimensional box of a relatively small size. We use the previous constructions to correct a D-dimensional error whose shape is a D-dimensional Lee sphere. 4) Applying the coloring method to correct more efficiently a two-dimensional error whose shape is a Lee sphere. The D-dimensional case is also discussed. 5) A construction of one-dimensional codes capable to correct a burst-error of length b in which the number of erroneous positions is relatively small compared to b. This construction is generalized for D-dimensional codes. 6) Applying the constructions correcting a Lee sphere error and a cluster-error with small number of erroneous positions, to correct an arbitrary cluster-error.
Lower bounds for the greatest possible number of colors in interval edge colorings of bipartite cylinders and bipartite tori
Venue: arXiv cs.DM 2007
Year: 2007

An interval edge t-coloring of a graph G is a proper edge coloring of G with colors 1,2...,t such that at least one edge of G is colored by color i,i=1,2...,t, and the edges incident with each vertex v are colored by d_{G}(v) consecutive colors, where d_{G}(v) is the degree of the vertex v in G. In this paper interval edge colorings of bipartite cylinders and bipartite tori are investigated.
A Novel and Efficient Bilateral Remote User Authentication Scheme Using Smart Cards
Venue: arXiv cs.CR 2007
Year: 2007

This paper proposes a novel remote user authentication scheme using smart cards which allows both the authentication server (AS) and the user to verify authenticity of each other. Our scheme is efficient enough to resist the known attacks that could be launched against remote user authentication process.
Cyberspace security: How to develop a security strategy
Venue: arXiv cs.OH 2007
Year: 2007

Despite all visible dividers, the Internet is getting us closer and closer, but with a great price. Our security is the price. The international community is fully aware of the urgent need to secure the cyberspace as you see the multiplication of security standards and national schemes interpreting them beyond borders: ISO 15408, ISO 17799, and ISO 27001. Even though some countries, including the Security Big Six (SB6), are equipped with their security books and may feel relatively safe; this remains a wrong sense of security as long as they share their networks with entities of less security. The standards impose security best practices and system specifications for the development of information security management systems. Partners beyond borders have to be secure as this is only possible if all entities connected to the partnership remain secure. Unfortunately, there is no way to verify the continuous security of partners without periodic security auditing and certification, and members who do not comply should be barred from the partnership. This concept also applies to the cyber space or the electronic society. In order to clean our society from cyber crimes and cyber terrorism we need to impose strict security policies and enforce them in a cooperative manner. The paper discusses a country's effort in the development of a national security strategy given its security economic intelligence position, its security readiness, and its adverse exposure.
A mathematical formalism for agent-based modeling
Venue: arXiv cs.MA 2007
Year: 2007

Many complex systems can be modeled as multiagent systems in which the constituent entities (agents) interact with each other. The global dynamics of such a system is determined by the nature of the local interactions among the agents. Since it is difficult to formally analyze complex multiagent systems, they are often studied through computer simulations. While computer simulations can be very useful, results obtained through simulations do not formally validate the observed behavior. Thus, there is a need for a mathematical framework which one can use to represent multiagent systems and formally establish their properties. This work contains a brief exposition of some known mathematical frameworks that can model multiagent systems. The focus is on one such framework, namely that of finite dynamical systems. Both, deterministic and stochastic versions of this framework are discussed. The paper contains a sampling of the mathematical results from the literature to show how finite dynamical systems can be used to carry out a rigorous study of the properties of multiagent systems and it is shown how the framework can also serve as a universal model for computation.
Characterizing and Reasoning about Probabilistic and Non-Probabilistic Expectation
Venue: arXiv cs.AI 2007
Year: 2007

Expectation is a central notion in probability theory. The notion of expectation also makes sense for other notions of uncertainty. We introduce a propositional logic for reasoning about expectation, where the semantics depends on the underlying representation of uncertainty. We give sound and complete axiomatizations for the logic in the case that the underlying representation is (a) probability, (b) sets of probability measures, (c) belief functions, and (d) possibility measures. We show that this logic is more expressive than the corresponding logic for reasoning about likelihood in the case of sets of probability measures, but equi-expressive in the case of probability, belief, and possibility. Finally, we show that satisfiability for these logics is NP-complete, no harder than satisfiability for propositional logic.
Chosen-Plaintext Cryptanalysis of a Clipped-Neural-Network-Based Chaotic Cipher
Venue: arXiv cs.CR 2007
Year: 2007

In ISNN'04, a novel symmetric cipher was proposed, by combining a chaotic signal and a clipped neural network (CNN) for encryption. The present paper analyzes the security of this chaotic cipher against chosen-plaintext attacks, and points out that this cipher can be broken by a chosen-plaintext attack. Experimental analyses are given to support the feasibility of the proposed attack.
Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory
Venue: arXiv cs.CC 2007
Year: 2007

Rabi and Sherman [RS97,RS93] proved that the hardness of factoring is a sufficient condition for there to exist one-way functions (i.e., p-time computable, honest, p-time noninvertible functions; this paper is in the worst-case model, not the average-case model) that are total, commutative, and associative but not strongly noninvertible. In this paper we improve the sufficient condition to ``P does not equal NP.'' More generally, in this paper we completely characterize which types of one-way functions stand or fall together with (plain) one-way functions--equivalently, stand or fall together with P not equaling NP. We look at the four attributes used in Rabi and Sherman's seminal work on algebraic properties of one-way functions (see [RS97,RS93]) and subsequent papers--strongness (of noninvertibility), totality, commutativity, and associativity--and for each attribute, we allow it to be required to hold, required to fail, or ``don't care.'' In this categorization there are 3^4 = 81 potential types of one-way functions. We prove that each of these 81 feature-laden types stand or fall together with the existence of (plain) one-way functions.
A Near Maximum Likelihood Decoding Algorithm for MIMO Systems Based on Semi-Definite Programming
Venue: arXiv cs.IT 2007
Year: 2007

In Multi-Input Multi-Output (MIMO) systems, Maximum-Likelihood (ML) decoding is equivalent to finding the closest lattice point in an N-dimensional complex space. In general, this problem is known to be NP hard. In this paper, we propose a quasi-maximum likelihood algorithm based on Semi-Definite Programming (SDP). We introduce several SDP relaxation models for MIMO systems, with increasing complexity. We use interior-point methods for solving the models and obtain a near-ML performance with polynomial computational complexity. Lattice basis reduction is applied to further reduce the computational complexity of solving these models. The proposed relaxation models are also used for soft output decoding in MIMO systems.
Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy
Venue: arXiv cs.IT 2007
Year: 2007

We present error-correcting codes that achieve the information-theoretically best possible trade-off between the rate and error-correction radius. Specifically, for every $0 < R < 1$ and $\eps> 0$, we present an explicit construction of error-correcting codes of rate $R$ that can be list decoded in polynomial time up to a fraction $(1-R-\eps)$ of {\em worst-case} errors. At least theoretically, this meets one of the central challenges in algorithmic coding theory. Our codes are simple to describe: they are {\em folded Reed-Solomon codes}, which are in fact {\em exactly} Reed-Solomon (RS) codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, and in fact our methods directly yield better decoding algorithms for RS codes when errors occur in {\em phased bursts}. The alphabet size of these folded RS codes is polynomial in the block length. We are able to reduce this to a constant (depending on $\eps$) using ideas concerning ``list recovery'' and expander-based codes from \cite{GI-focs01,GI-ieeejl}. Concatenating the folded RS codes with suitable inner codes also gives us polynomial time constructible binary codes that can be efficiently list decoded up to the Zyablov bound, i.e., up to twice the radius achieved by the standard GMD decoding of concatenated codes.
Matching Subsequences in Trees
Venue: arXiv cs.DS 2007
Year: 2007

Given two rooted, labeled trees $P$ and $T$ the tree path subsequence problem is to determine which paths in $P$ are subsequences of which paths in $T$. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.
Truecluster: robust scalable clustering with model selection
Venue: arXiv cs.AI 2007
Year: 2007

Data-based classification is fundamental to most branches of science. While recent years have brought enormous progress in various areas of statistical computing and clustering, some general challenges in clustering remain: model selection, robustness, and scalability to large datasets. We consider the important problem of deciding on the optimal number of clusters, given an arbitrary definition of space and clusteriness. We show how to construct a cluster information criterion that allows objective model selection. Differing from other approaches, our truecluster method does not require specific assumptions about underlying distributions, dissimilarity definitions or cluster models. Truecluster puts arbitrary clustering algorithms into a generic unified (sampling-based) statistical framework. It is scalable to big datasets and provides robust cluster assignments and case-wise diagnostics. Truecluster will make clustering more objective, allows for automation, and will save time and costs. Free R software is available.
LLL Reduction Achieves the Receive Diversity in MIMO Decoding
Venue: arXiv cs.IT 2007
Year: 2007

Diversity order is an important measure for the performance of communication systems over MIMO fading channels. In this paper, we prove that in MIMO multiple access systems (or MIMO point-to-point systems with V-BLAST transmission), lattice-reduction-aided decoding achieves the maximum receive diversity (which is equal to the number of receive antennas). Also, we prove that the naive lattice decoding (which discards the out-of-region decoded points) achieves the maximum diversity.
A topology visualisation tool for large-scale communications networks
Venue: arXiv cs.NI 2007
Year: 2007

A visualisation tool is presented to facilitate the study on large-scale communications networks. This tool provides a simple and effective way to summarise the topology of a complex network at a coarse level.
Pivotal and Pivotal-discriminative Consequence Relations
Venue: arXiv cs.LO 2007
Year: 2007

In the present paper, we investigate consequence relations that are both paraconsistent and plausible (but still monotonic). More precisely, we put the focus on pivotal consequence relations, i.e. those relations that can be defined by a pivot (in the style of e.g. D. Makinson). A pivot is a fixed subset of valuations which are considered to be the important ones in the absolute sense. We worked with a general notion of valuation that covers e.g. the classical valuations as well as certain kinds of many-valued valuations. In the many-valued cases, pivotal consequence relations are paraconsistant (in addition to be plausible), i.e. they are capable of drawing reasonable conclusions which contain contradictions. We will provide in our general framework syntactic characterizations of several families of pivotal relations. In addition, we will provide, again in our general framework, characterizations of several families of pivotal discriminative consequence relations. The latter are defined exactly as the plain version, but contradictory conclusions are rejected. We will also answer negatively a representation problem that was left open by Makinson. Finally, we will put in evidence a connexion with X-logics from Forget, Risch, and Siegel. The motivations and the framework of the present paper are very close to those of a previous paper of the author which is about preferential consequence relations.
Approximation algorithms for wavelet transform coding of data streams
Venue: arXiv cs.DS 2007
Year: 2007

This paper addresses the problem of finding a B-term wavelet representation of a given discrete function $f \in \real^n$ whose distance from f is minimized. The problem is well understood when we seek to minimize the Euclidean distance between f and its representation. The first known algorithms for finding provably approximate representations minimizing general $\ell_p$ distances (including $\ell_\infty$) under a wide variety of compactly supported wavelet bases are presented in this paper. For the Haar basis, a polynomial time approximation scheme is demonstrated. These algorithms are applicable in the one-pass sublinear-space data stream model of computation. They generalize naturally to multiple dimensions and weighted norms. A universal representation that provides a provable approximation guarantee under all p-norms simultaneously; and the first approximation algorithms for bit-budget versions of the problem, known as adaptive quantization, are also presented. Further, it is shown that the algorithms presented here can be used to select a basis from a tree-structured dictionary of bases and find a B-term representation of the given function that provably approximates its best dictionary-basis representation.
Fuzzy Discrete Event Systems under Fuzzy Observability and a test-algorithm
Venue: arXiv cs.LO 2007
Year: 2007

In order to more effectively cope with the real-world problems of vagueness, impreciseness, and subjectivity, fuzzy discrete event systems (FDESs) were proposed recently. Notably, FDESs have been applied to biomedical control for HIV/AIDS treatment planning and sensory information processing for robotic control. Qiu, Cao and Ying independently developed supervisory control theory of FDESs. We note that the controllability of events in Qiu's work is fuzzy but the observability of events is crisp, and, the observability of events in Cao and Ying's work is also crisp although the controllability is not completely crisp since the controllable events can be disabled with any degrees. Motivated by the necessity to consider the situation that the events may be observed or controlled with some membership degrees, in this paper, we establish the supervisory control theory of FDESs with partial observations, in which both the observability and controllability of events are fuzzy instead. We formalize the notions of fuzzy controllability condition and fuzzy observability condition. And Controllability and Observability Theorem of FDESs is set up in a more generic framework. In particular, we present a detailed computing flow to verify whether the controllability and observability conditions hold. Thus, this result can decide the existence of supervisors. Also, we use this computing method to check the existence of supervisors in the Controllability and Observability Theorem of classical discrete event systems (DESs), which is a new method and different from classical case. A number of examples are elaborated on to illustrate the presented results.
Mining Behavioral Groups in Large Wireless LANs
Venue: arXiv cs.NI 2007
Year: 2007

One vision of future wireless networks is that they will be deeply integrated and embedded in our lives and will involve the use of personalized mobile devices. User behavior in such networks is bound to affect the network performance. It is imperative to study and characterize the fundamental structure of wireless user behavior in order to model, manage, leverage and design efficient mobile networks. It is also important to make such study as realistic as possible, based on extensive measurements collected from existing deployed wireless networks. In this study, using our systematic TRACE approach, we analyze wireless users' behavioral patterns by extensively mining wireless network logs from two major university campuses. We represent the data using location preference vectors, and utilize unsupervised learning (clustering) to classify trends in user behavior using novel similarity metrics. Matrix decomposition techniques are used to identify (and differentiate between) major patterns. While our findings validate intuitive repetitive behavioral trends and user grouping, it is surprising to find the qualitative commonalities of user behaviors from the two universities. We discover multi-modal user behavior for more than 60% of the users, and there are hundreds of distinct groups with unique behavioral patterns in both campuses. The sizes of the major groups follow a power-law distribution. Our methods and findings provide an essential step towards network management and behavior-aware network protocols and applications, to name a few.
A constructive and unifying framework for zero-bit watermarking
Venue: arXiv cs.MM 2007
Year: 2007

In the watermark detection scenario, also known as zero-bit watermarking, a watermark, carrying no hidden message, is inserted in content. The watermark detector checks for the presence of this particular weak signal in content. The article looks at this problem from a classical detection theory point of view, but with side information enabled at the embedding side. This means that the watermark signal is a function of the host content. Our study is twofold. The first step is to design the best embedding function for a given detection function, and the best detection function for a given embedding function. This yields two conditions, which are mixed into one `fundamental' partial differential equation. It appears that many famous watermarking schemes are indeed solution to this `fundamental' equation. This study thus gives birth to a constructive framework unifying solutions, so far perceived as very different.
A field-theory motivated approach to symbolic computer algebra
Venue: arXiv cs.SC 2007
Year: 2007

Field theory is an area in physics with a deceptively compact notation. Although general purpose computer algebra systems, built around generic list-based data structures, can be used to represent and manipulate field-theory expressions, this often leads to cumbersome input formats, unexpected side-effects, or the need for a lot of special-purpose code. This makes a direct translation of problems from paper to computer and back needlessly time-consuming and error-prone. A prototype computer algebra system is presented which features TeX-like input, graph data structures, lists with Young-tableaux symmetries and a multiple-inheritance property system. The usefulness of this approach is illustrated with a number of explicit field-theory problems.
The Many Faces of Rationalizability
Venue: arXiv cs.GT 2007
Year: 2007

The rationalizability concept was introduced in \cite{Ber84} and \cite{Pea84} to assess what can be inferred by rational players in a non-cooperative game in the presence of common knowledge. However, this notion can be defined in a number of ways that differ in seemingly unimportant minor details. We shed light on these differences, explain their impact, and clarify for which games these definitions coincide. Then we apply the same analysis to explain the differences and similarities between various ways the iterated elimination of strictly dominated strategies was defined in the literature. This allows us to clarify the results of \cite{DS02} and \cite{CLL05} and improve upon them. We also consider the extension of these results to strict dominance by a mixed strategy. Our approach is based on a general study of the operators on complete lattices. We allow transfinite iterations of the considered operators and clarify the need for them. The advantage of such a general approach is that a number of results, including order independence for some of the notions of rationalizability and strict dominance, come for free.
A study of fuzzy and many-valued logics in cellular automata
Venue: arXiv cs.LO 2007
Year: 2007

In this paper we provide an analytical study of the theory of multi-valued and fuzzy cellular automata where the fuzziness appears as the result of the application of an underlying multi-valued or continuous logic as opposed to standard logic as used conventionally. Using the disjunctive normal form of any one of the 255 ECA's so defined, we modify the underlying logic structure and redefine the ECA within the framework of this new logic. The idea here is to show that the evolution of space-time diagrams of ECA's under even a probabilistic logic can exhibit non-chaotic behavior. This is looked at specifically for Probabilistic Rule 110, in contrast with Boolean Rule 110 which is known to be capable of universal computation.