OpenRaiser/Intern-Atlas huggingface dataset:
Maximum-rate, Minimum-Decoding-Complexity STBCs from Clifford Algebras
Venue: arXiv cs.IT 2007
Year: 2007

It is well known that Space-Time Block Codes (STBCs) from orthogonal designs (ODs) are single-symbol decodable/symbol-by-symbol decodable (SSD) and are obtainable from unitary matrix representations of Clifford algebras. However, SSD codes are obtainable from designs that are not orthogonal also. Recently, two such classes of SSD codes have been studied: (i) Coordinate Interleaved Orthogonal Designs (CIODs) and (ii) Minimum-Decoding-Complexity (MDC) STBCs from Quasi-ODs (QODs). Codes from ODs, CIODs and MDC-QODs are mutually non-intersecting classes of codes. The class of CIODs have {\it non-unitary weight matrices} when written as a Linear Dispersion Code (LDC) proposed by Hassibi and Hochwald, whereas several known SSD codes including CODs have {\it unitary weight matrices}. In this paper, we obtain SSD codes with unitary weight matrices (that are not CODs) called Clifford Unitary Weight SSDs (CUW-SSDs) from matrix representations of Clifford algebras. A main result of this paper is the derivation of an achievable upper bound on the rate of any unitary weight SSD code as $\frac{a}{2^{a-1}}$ for $2^a$ antennas which is larger than that of the CODs which is $\frac{a+1}{2^a}$. It is shown that several known classes of SSD codes are CUW-SSD codes and CUW-SSD codes meet this upper bound. Also, for the codes of this paper conditions on the signal sets which ensure full-diversity and expressions for the coding gain are presented. A large class of SSD codes with non-unitary weight matrices are obtained which include CIODs as a proper subclass.
Reducing semantic complexity in distributed Digital Libraries: treatment of term vagueness and document re-ranking
Venue: arXiv cs.DL 2007
Year: 2007

The purpose of the paper is to propose models to reduce the semantic complexity in heterogeneous DLs. The aim is to introduce value-added services (treatment of term vagueness and document re-ranking) that gain a certain quality in DLs if they are combined with heterogeneity components established in the project "Competence Center Modeling and Treatment of Semantic Heterogeneity". Empirical observations show that freely formulated user terms and terms from controlled vocabularies are often not the same or match just by coincidence. Therefore, a value-added service will be developed which rephrases the natural language searcher terms into suggestions from the controlled vocabulary, the Search Term Recommender (STR). Two methods, which are derived from scientometrics and network analysis, will be implemented with the objective to re-rank result sets by the following structural properties: the ranking of the results by core journals (so-called Bradfordizing) and ranking by centrality of authors in co-authorship networks.
Interval Edge Colourings of Complete Graphs and n-cubes
Venue: arXiv cs.DM 2007
Year: 2007

For complete graphs and n-cubes bounds are found for the possible number of colours in an interval edge colourings.
Maximum-Likelihood Priority-First Search Decodable Codes for Combined Channel Estimation and Error Protection
Venue: arXiv cs.IT 2007
Year: 2007

The code that combines channel estimation and error protection has received general attention recently, and has been considered a promising methodology to compensate multi-path fading effect. It has been shown by simulations that such code design can considerably improve the system performance over the conventional design with separate channel estimation and error protection modules under the same code rate. Nevertheless, the major obstacle that prevents from the practice of the codes is that the existing codes are mostly searched by computers, and hence exhibit no good structure for efficient decoding. Hence, the time-consuming exhaustive search becomes the only decoding choice, and the decoding complexity increases dramatically with the codeword length. In this paper, by optimizing the signal-tonoise ratio, we found a systematic construction for the codes for combined channel estimation and error protection, and confirmed its equivalence in performance to the computer-searched codes by simulations. Moreover, the structural codes that we construct by rules can now be maximum-likelihoodly decodable in terms of a newly derived recursive metric for use of the priority-first search decoding algorithm. Thus,the decoding complexity reduces significantly when compared with that of the exhaustive decoder. The extension code design for fast-fading channels is also presented. Simulations conclude that our constructed extension code is robust in performance even if the coherent period is shorter than the codeword length.
Towards Persistence-Based Reconstruction in Euclidean Spaces
Venue: arXiv cs.CG 2007
Year: 2007

Manifold reconstruction has been extensively studied for the last decade or so, especially in two and three dimensions. Recently, significant improvements were made in higher dimensions, leading to new methods to reconstruct large classes of compact subsets of Euclidean space $\R^d$. However, the complexities of these methods scale up exponentially with d, which makes them impractical in medium or high dimensions, even for handling low-dimensional submanifolds. In this paper, we introduce a novel approach that stands in-between classical reconstruction and topological estimation, and whose complexity scales up with the intrinsic dimension of the data. Specifically, when the data points are sufficiently densely sampled from a smooth $m$-submanifold of $\R^d$, our method retrieves the homology of the submanifold in time at most $c(m)n^5$, where $n$ is the size of the input and $c(m)$ is a constant depending solely on $m$. It can also provably well handle a wide range of compact subsets of $\R^d$, though with worse complexities. Along the way to proving the correctness of our algorithm, we obtain new results on Čech, Rips, and witness complex filtrations in Euclidean spaces.
Single-Exclusion Number and the Stopping Redundancy of MDS Codes
Venue: arXiv cs.IT 2007
Year: 2007

For a linear block code C, its stopping redundancy is defined as the smallest number of check nodes in a Tanner graph for C, such that there exist no stopping sets of size smaller than the minimum distance of C. Schwartz and Vardy conjectured that the stopping redundancy of an MDS code should only depend on its length and minimum distance. We define the (n,t)-single-exclusion number, S(n,t) as the smallest number of t-subsets of an n-set, such that for each i-subset of the n-set, i=1,...,t+1, there exists a t-subset that contains all but one element of the i-subset. New upper bounds on the single-exclusion number are obtained via probabilistic methods, recurrent inequalities, as well as explicit constructions. The new bounds are used to better understand the stopping redundancy of MDS codes. In particular, it is shown that for [n,k=n-d+1,d] MDS codes, as n goes to infinity, the stopping redundancy is asymptotic to S(n,d-2), if d=o(\sqrt{n}), or if k=o(\sqrt{n}) and k goes to infinity, thus giving partial confirmation of the Schwartz-Vardy conjecture in the asymptotic sense.
Phase transition and computational complexity in a stochastic prime number generator
Venue: arXiv cs.CC 2007
Year: 2007

We introduce a prime number generator in the form of a stochastic algorithm. The character of such algorithm gives rise to a continuous phase transition which distinguishes a phase where the algorithm is able to reduce the whole system of numbers into primes and a phase where the system reaches a frozen state with low prime density. In this paper we firstly pretend to give a broad characterization of this phase transition, both in terms of analytical and numerical analysis. Critical exponents are calculated, and data collapse is provided. Further on we redefine the model as a search problem, fitting it in the hallmark of computational complexity theory. We suggest that the system belongs to the class NP. The computational cost is maximal around the threshold, as common in many algorithmic phase transitions, revealing the presence of an easy-hard-easy pattern. We finally relate the nature of the phase transition to an average-case classification of the problem.
On the Capacity and Energy Efficiency of Training-Based Transmissions over Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, the capacity and energy efficiency of training-based communication schemes employed for transmission over a-priori unknown Rayleigh block fading channels are studied. In these schemes, periodically transmitted training symbols are used at the receiver to obtain the minimum mean-square-error (MMSE) estimate of the channel fading coefficients. Initially, the case in which the product of the estimate error and transmitted signal is assumed to be Gaussian noise is considered. In this case, it is shown that bit energy requirements grow without bound as the signal-to-noise ratio (SNR) goes to zero, and the minimum bit energy is achieved at a nonzero SNR value below which one should not operate. The effect of the block length on both the minimum bit energy and the SNR value at which the minimum is achieved is investigated. Flash training and transmission schemes are analyzed and shown to improve the energy efficiency in the low-SNR regime. In the second part of the paper, the capacity and energy efficiency of training-based schemes are investigated when the channel input is subject to peak power constraints. The capacity-achieving input structure is characterized and the magnitude distribution of the optimal input is shown to be discrete with a finite number of mass points. The capacity, bit energy requirements, and optimal resource allocation strategies are obtained through numerical analysis. The bit energy is again shown to grow without bound as SNR decreases to zero due to the presence of peakedness constraints. The improvements in energy efficiency when on-off keying with fixed peak power and vanishing duty cycle is employed are studied. Comparisons of the performances of training-based and noncoherent transmission schemes are provided.
Graph kernels between point clouds
Venue: arXiv cs.LG 2007
Year: 2007

Point clouds are sets of points in two or three dimensions. Most kernel methods for learning on sets of points have not yet dealt with the specific geometrical invariances and practical constraints associated with point clouds in computer vision and graphics. In this paper, we present extensions of graph kernels for point clouds, which allow to use kernel methods for such ob jects as shapes, line drawings, or any three-dimensional point clouds. In order to design rich and numerically efficient kernels with as few free parameters as possible, we use kernels between covariance matrices and their factorizations on graphical models. We derive polynomial time dynamic programming recursions and present applications to recognition of handwritten digits and Chinese characters from few training examples.
A Partition-Based Relaxation For Steiner Trees
Venue: arXiv cs.DS 2007
Year: 2007

The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G=(V,E), a set of terminals R, and non-negative costs c_e for all edges e in E. Any tree that contains all terminals is called a Steiner tree; the goal is to find a minimum-cost Steiner tree. The nodes V R are called Steiner nodes. The best approximation algorithm known for the Steiner tree problem is due to Robins and Zelikovsky (SIAM J. Discrete Math, 2005); their greedy algorithm achieves a performance guarantee of 1+(ln 3)/2 ~ 1.55. The best known linear (LP)-based algorithm, on the other hand, is due to Goemans and Bertsimas (Math. Programming, 1993) and achieves an approximation ratio of 2-2/|R|. In this paper we establish a link between greedy and LP-based approaches by showing that Robins and Zelikovsky's algorithm has a natural primal-dual interpretation with respect to a novel partition-based linear programming relaxation. We also exhibit surprising connections between the new formulation and existing LPs and we show that the new LP is stronger than the bidirected cut formulation. An instance is b-quasi-bipartite if each connected component of G R has at most b vertices. We show that Robins' and Zelikovsky's algorithm has an approximation ratio better than 1+(ln 3)/2 for such instances, and we prove that the integrality gap of our LP is between 8/7 and (2b+1)/(b+1).
Framework and Resources for Natural Language Parser Evaluation
Venue: arXiv cs.CL 2007
Year: 2007

Because of the wide variety of contemporary practices used in the automatic syntactic parsing of natural languages, it has become necessary to analyze and evaluate the strengths and weaknesses of different approaches. This research is all the more necessary because there are currently no genre- and domain-independent parsers that are able to analyze unrestricted text with 100% preciseness (I use this term to refer to the correctness of analyses assigned by a parser). All these factors create a need for methods and resources that can be used to evaluate and compare parsing systems. This research describes: (1) A theoretical analysis of current achievements in parsing and parser evaluation. (2) A framework (called FEPa) that can be used to carry out practical parser evaluations and comparisons. (3) A set of new evaluation resources: FiEval is a Finnish treebank under construction, and MGTS and RobSet are parser evaluation resources in English. (4) The results of experiments in which the developed evaluation framework and the two resources for English were used for evaluating a set of selected parsers.
Cryptanalysis of an Image Encryption Scheme Based on a Compound Chaotic Sequence
Venue: arXiv cs.CR 2007
Year: 2007

Recently, an image encryption scheme based on a compound chaotic sequence was proposed. In this paper, the security of the scheme is studied and the following problems are found: (1) a differential chosen-plaintext attack can break the scheme with only three chosen plain-images; (2) there is a number of weak keys and some equivalent keys for encryption; (3) the scheme is not sensitive to the changes of plain-images; and (4) the compound chaotic sequence does not work as a good random number resource.
On Distributed Computation in Noisy Random Planar Networks
Venue: arXiv cs.IT 2007
Year: 2007

We consider distributed computation of functions of distributed data in random planar networks with noisy wireless links. We present a new algorithm for computation of the maximum value which is order optimal in the number of transmissions and computation time.We also adapt the histogram computation algorithm of Ying et al to make the histogram computation time optimal.
TRUST-TECH based Methods for Optimization and Learning
Venue: arXiv cs.AI 2007
Year: 2007

Many problems that arise in machine learning domain deal with nonlinearity and quite often demand users to obtain global optimal solutions rather than local optimal ones. Optimization problems are inherent in machine learning algorithms and hence many methods in machine learning were inherited from the optimization literature. Popularly known as the initialization problem, the ideal set of parameters required will significantly depend on the given initialization values. The recently developed TRUST-TECH (TRansformation Under STability-reTaining Equilibria CHaracterization) methodology systematically explores the subspace of the parameters to obtain a complete set of local optimal solutions. In this thesis work, we propose TRUST-TECH based methods for solving several optimization and machine learning problems. Two stages namely, the local stage and the neighborhood-search stage, are repeated alternatively in the solution space to achieve improvements in the quality of the solutions. Our methods were tested on both synthetic and real datasets and the advantages of using this novel framework are clearly manifested. This framework not only reduces the sensitivity to initialization, but also allows the flexibility for the practitioners to use various global and local methods that work well for a particular problem of interest. Other hierarchical stochastic algorithms like evolutionary algorithms and smoothing algorithms are also studied and frameworks for combining these methods with TRUST-TECH have been proposed and evaluated on several test systems.
On the Throughput of Secure Hybrid-ARQ Protocols for Gaussian Block-Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

The focus of this paper is an information-theoretic study of retransmission protocols for reliable packet communication under a secrecy constraint. The hybrid automatic retransmission request (HARQ) protocol is revisited for a block-fading wire-tap channel, in which two legitimate users communicate over a block-fading channel in the presence of a passive eavesdropper who intercepts the transmissions through an independent block-fading channel. In this model, the transmitter obtains a 1-bit ACK/NACK feedback from the legitimate receiver via an error-free public channel. Both reliability and confidentiality of secure HARQ protocols are studied by the joint consideration of channel coding, secrecy coding, and retransmission protocols. In particular, the error and secrecy performance of repetition time diversity (RTD) and incremental redundancy (INR) protocols are investigated based on good Wyner code sequences, which ensure that the confidential message is decoded successfully by the legitimate receiver and is kept in total ignorance by the eavesdropper for a given set of channel realizations. This paper first illustrates that there exists a good rate-compatible Wyner code family which ensures a secure INR protocol. Next, two types of outage probabilities, connection outage and secrecy outage probabilities are defined in order to characterize the tradeoff between the reliability of the legitimate communication link and the confidentiality with respect to the eavesdropper's link. For a given connection/secrecy outage probability pair, an achievable throughput of secure HARQ protocols is derived for block-fading channels. Finally, both asymptotic analysis and numerical computations demonstrate the benefits of HARQ protocols to throughput and secrecy.
Secure Clustering in DSN with Key Predistribution and WCDS
Venue: arXiv cs.NI 2007
Year: 2007

This paper proposes an efficient approach of secure clustering in distributed sensor networks. The clusters or groups in the network are formed based on offline rank assignment and predistribution of secret keys. Our approach uses the concept of weakly connected dominating set (WCDS) to reduce the number of cluster-heads in the network. The formation of clusters in the network is secured as the secret keys are distributed and used in an efficient way to resist the inclusion of any hostile entity in the clusters. Along with the description of our approach, we present an analysis and comparison of our approach with other schemes. We also mention the limitations of our approach considering the practical implementation of the sensor networks.
An Improved Timestamp-Based Password Authentication Scheme Using Smart Cards
Venue: arXiv cs.CR 2007
Year: 2007

With the recent proliferation of distributed systems and networking, remote authentication has become a crucial task in many networking applications. Various schemes have been proposed so far for the two-party remote authentication; however, some of them have been proved to be insecure. In this paper, we propose an efficient timestamp-based password authentication scheme using smart cards. We show various types of forgery attacks against a previously proposed timestamp-based password authentication scheme and improve that scheme to ensure robust security for the remote authentication process, keeping all the advantages that were present in that scheme. Our scheme successfully defends the attacks that could be launched against other related previous schemes. We present a detailed cryptanalysis of previously proposed Shen et. al scheme and an analysis of the improved scheme to show its improvements and efficiency.
Indirect Object Representation and Access by Means of Concepts
Venue: arXiv cs.PL 2007
Year: 2007

The paper describes a mechanism for indirect object representation and access (ORA) in programming languages. The mechanism is based on using a new programming construct which is referred to as concept. Concept consists of one object class and one reference class both having their fields and methods. The object class is the conventional class as defined in OOP with instances passed by reference. Instances of the reference class are passed by value and are intended to represent objects. The reference classes are used to describe how objects have to be represented and accessed by providing custom format for their identifiers and custom access procedures. Such an approach to programming where concepts are used instead of classes is referred to as concept-oriented programming. It generalizes OOP and its main advantage is that it allows the programmer to describe not only the functionality of target objects but also intermediate functions which are executed behind the scenes as an object is being accessed.
Efficient Solving of Quantified Inequality Constraints over the Real Numbers
Venue: arXiv cs.LO 2007
Year: 2007

Let a quantified inequality constraint over the reals be a formula in the first-order predicate language over the structure of the real numbers, where the allowed predicate symbols are $\leq$ and $<$. Solving such constraints is an undecidable problem when allowing function symbols such $\sin$ or $\cos$. In the paper we give an algorithm that terminates with a solution for all, except for very special, pathological inputs. We ensure the practical efficiency of this algorithm by employing constraint programming techniques.
Applications of LDPC Codes to the Wiretap Channel
Venue: arXiv cs.IT 2007
Year: 2007

With the advent of quantum key distribution (QKD) systems, perfect (i.e. information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical error-correcting codes for both error correction (for the honest parties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model that corresponds to such a setting is the wire tap channel introduced by Wyner in 1975. In this paper, we study fundamental limits and coding methods for wire tap channels. We provide an alternative view of the proof for secrecy capacity of wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide security at rates below secrecy capacity. For the special case of a noiseless main channel and binary erasure channel, we consider encoder and decoder design for codes achieving secrecy on the wiretap channel; we show that it is possible to construct linear-time decodable secrecy codes based on LDPC codes that achieve secrecy.