OpenRaiser/Intern-Atlas huggingface dataset:
An Efficient Scheme for Sensitive Message Transmission using Blind Signcryption
Venue: arXiv cs.CR 2005
Year: 2005

Blind signature schemes enable a useful protocol that guarantee the anonymity of the participants while Signcryption offers authentication of message and confidentiality of messages at the same time and more efficiently. In this paper, we present a blind signcryption scheme that combines the functionality of blind signature and signcryption. This blind Signcryption is useful for applications that are based on anonymity untracebility and unlinkability.
Wikis in Tuple Spaces
Venue: arXiv cs.DC 2005
Year: 2005

We consider storing the pages of a wiki in a tuple space and the effects this might have on the wiki experience. In particular, wiki pages are stored in tuples with a few identifying values such as title, author, revision date, content, etc. and pages are retrieved by sending the tuple space templates, such as one that gives the title but nothing else, leaving the tuple space to resolve to a single tuple. We use a tuple space wiki to avoid deadlocks, infinite loops, and wasted efforts when page edit contention arises and examine how a tuple space wiki changes the wiki experience.
k-core decomposition: a tool for the visualization of large scale networks
Venue: arXiv cs.NI 2005
Year: 2005

We use the k-core decomposition to visualize large scale complex networks in two dimensions. This decomposition, based on a recursive pruning of the least connected vertices, allows to disentangle the hierarchical structure of networks by progressively focusing on their central cores. By using this strategy we develop a general visualization algorithm that can be used to compare the structural properties of various networks and highlight their hierarchical structure. The low computational complexity of the algorithm, O(n+e), where 'n' is the size of the network, and 'e' is the number of edges, makes it suitable for the visualization of very large sparse networks. We apply the proposed visualization tool to several real and synthetic graphs, showing its utility in finding specific structural fingerprints of computer generated and real world networks.
Tight Lower Bounds for Query Processing on Streaming and External Memory Data
Venue: arXiv cs.DB 2005
Year: 2005

We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is sufficiently small, e.g., polylogarithmic in the size of the input). We also show that neither joins nor sorting are feasible if the product of the number $r(n)$ of scans of the external memory and the size $s(n)$ of the internal memory buffers is sufficiently small, e.g., of size $o(\sqrt[5]{n})$. We also establish tight bounds for the complexity of XPath evaluation and filtering.
Defragmenting the Module Layout of a Partially Reconfigurable Device
Venue: arXiv cs.AR 2005
Year: 2005

Modern generations of field-programmable gate arrays (FPGAs) allow for partial reconfiguration. In an online context, where the sequence of modules to be loaded on the FPGA is unknown beforehand, repeated insertion and deletion of modules leads to progressive fragmentation of the available space, making defragmentation an important issue. We address this problem by propose an online and an offline component for the defragmentation of the available space. We consider defragmenting the module layout on a reconfigurable device. This corresponds to solving a two-dimensional strip packing problem. Problems of this type are NP-hard in the strong sense, and previous algorithmic results are rather limited. Based on a graph-theoretic characterization of feasible packings, we develop a method that can solve two-dimensional defragmentation instances of practical size to optimality. Our approach is validated for a set of benchmark instances.
Parametric Verification of a Group Membership Algorithm
Venue: arXiv cs.LO 2005
Year: 2005

We address the problem of verifying clique avoidance in the TTP protocol. TTP allows several stations embedded in a car to communicate. It has many mechanisms to ensure robustness to faults. In particular, it has an algorithm that allows a station to recognize itself as faulty and leave the communication. This algorithm must satisfy the crucial 'non-clique' property: it is impossible to have two or more disjoint groups of stations communicating exclusively with stations in their own group. In this paper, we propose an automatic verification method for an arbitrary number of stations $N$ and a given number of faults $k$. We give an abstraction that allows to model the algorithm by means of unbounded (parametric) counter automata. We have checked the non-clique property on this model in the case of one fault, using the ALV tool as well as the LASH tool.
General Recursion via Coinductive Types
Venue: arXiv cs.LO 2005
Year: 2005

A fertile field of research in theoretical computer science investigates the representation of general recursive functions in intensional type theories. Among the most successful approaches are: the use of wellfounded relations, implementation of operational semantics, formalization of domain theory, and inductive definition of domain predicates. Here, a different solution is proposed: exploiting coinductive types to model infinite computations. To every type A we associate a type of partial elements Partial(A), coinductively generated by two constructors: the first, return(a) just returns an element a:A; the second, step(x), adds a computation step to a recursive element x:Partial(A). We show how this simple device is sufficient to formalize all recursive functions between two given types. It allows the definition of fixed points of finitary, that is, continuous, operators. We will compare this approach to different ones from the literature. Finally, we mention that the formalization, with appropriate structural maps, defines a strong monad.
Asynchronous pseudo-systems
Venue: arXiv cs.OH 2005
Year: 2005

The paper introduces the concept of asynchronous pseudo-system. Its purpose is to correct/generalize/continue the study of the asynchronous systems (the models of the asynchronous circuits) that has been started in [1], [2].
Wavelet Time Shift Properties Integration with Support Vector Machines
Venue: arXiv cs.IR 2005
Year: 2005

This paper presents a short evaluation about the integration of information derived from wavelet non-linear-time-invariant (non-LTI) projection properties using Support Vector Machines (SVM). These properties may give additional information for a classifier trying to detect known patterns hidden by noise. In the experiments we present a simple electromagnetic pulsed signal recognition scheme, where some improvement is achieved with respect to previous work. SVMs are used as a tool for information integration, exploiting some unique properties not easily found in neural networks.
The Partition Weight Enumerator of MDS Codes and its Applications
Venue: arXiv cs.IT 2005
Year: 2005

A closed form formula of the partition weight enumerator of maximum distance separable (MDS) codes is derived for an arbitrary number of partitions. Using this result, some properties of MDS codes are discussed. The results are extended for the average binary image of MDS codes in finite fields of characteristic two. As an application, we study the multiuser error probability of Reed Solomon codes.
On the existence and characterization of the maxent distribution under general moment inequality constraints
Venue: arXiv cs.IT 2005
Year: 2005

A broad set of sufficient conditions that guarantees the existence of the maximum entropy (maxent) distribution consistent with specified bounds on certain generalized moments is derived. Most results in the literature are either focused on the minimum cross-entropy distribution or apply only to distributions with a bounded-volume support or address only equality constraints. The results of this work hold for general moment inequality constraints for probability distributions with possibly unbounded support, and the technical conditions are explicitly on the underlying generalized moment functions. An analytical characterization of the maxent distribution is also derived using results from the theory of constrained optimization in infinite-dimensional normed linear spaces. Several auxiliary results of independent interest pertaining to certain properties of convex coercive functions are also presented.
Cryptanalysis of Key Issuing Protocols in ID-based Cryptosystems
Venue: arXiv cs.CR 2005
Year: 2005

To remove key escrow problem and avoid the need of secure channel in ID based cryptosystem Lee et al. proposed a secure key issuing protocol. However we show that it suffers from impersonation, insider attacks and incompetency of the key privacy authorities. We also cryptanalyze Sui et al.'s separable and anonymous key issuing protocol.
Database Reformulation with Integrity Constraints (extended abstract)
Venue: arXiv cs.DB 2005
Year: 2005

In this paper we study the problem of reducing the evaluation costs of queries on finite databases in presence of integrity constraints, by designing and materializing views. Given a database schema, a set of queries defined on the schema, a set of integrity constraints, and a storage limit, to find a solution to this problem means to find a set of views that satisfies the storage limit, provides equivalent rewritings of the queries under the constraints (this requirement is weaker than equivalence in the absence of constraints), and reduces the total costs of evaluating the queries. This problem, database reformulation, is important for many applications, including data warehousing and query optimization. We give complexity results and algorithms for database reformulation in presence of constraints, for conjunctive queries, views, and rewritings and for several types of constraints, including functional and inclusion dependencies. To obtain better complexity results, we introduce an unchase technique, which reduces the problem of query equivalence under constraints to equivalence in the absence of constraints without increasing query size.
A Unified Framework for Tree Search Decoding : Rediscovering the Sequential Decoder
Venue: arXiv cs.IT 2005
Year: 2005

We consider receiver design for coded transmission over linear Gaussian channels. We restrict ourselves to the class of lattice codes and formulate the joint detection and decoding problem as a closest lattice point search (CLPS). Here, a tree search framework for solving the CLPS is adopted. In our framework, the CLPS algorithm decomposes into the preprocessing and tree search stages. The role of the preprocessing stage is to expose the tree structure in a form {\em matched} to the search stage. We argue that the minimum mean square error decision feedback (MMSE-DFE) frontend is instrumental for solving the joint detection and decoding problem in a single search stage. It is further shown that MMSE-DFE filtering allows for using lattice reduction methods to reduce complexity, at the expense of a marginal performance loss, and solving under-determined linear systems. For the search stage, we present a generic method, based on the branch and bound (BB) algorithm, and show that it encompasses all existing sphere decoders as special cases. The proposed generic algorithm further allows for an interesting classification of tree search decoders, sheds more light on the structural properties of all known sphere decoders, and inspires the design of more efficient decoders. In particular, an efficient decoding algorithm that resembles the well known Fano sequential decoder is identified. The excellent performance-complexity tradeoff achieved by the proposed MMSE-Fano decoder is established via simulation results and analytical arguments in several MIMO and ISI scenarios.
A Taxonomy of Data Grids for Distributed Data Sharing, Management and Processing
Venue: arXiv cs.DC 2005
Year: 2005

Data Grids have been adopted as the platform for scientific communities that need to share, access, transport, process and manage large data collections distributed worldwide. They combine high-end computing technologies with high-performance networking and wide-area storage management techniques. In this paper, we discuss the key concepts behind Data Grids and compare them with other data sharing and distribution paradigms such as content delivery networks, peer-to-peer networks and distributed databases. We then provide comprehensive taxonomies that cover various aspects of architecture, data transportation, data replication and resource allocation and scheduling. Finally, we map the proposed taxonomy to various Data Grid systems not only to validate the taxonomy but also to identify areas for future exploration. Through this taxonomy, we aim to categorise existing systems to better understand their goals and their methodology. This would help evaluate their applicability for solving similar problems. This taxonomy also provides a "gap analysis" of this area through which researchers can potentially identify new issues for investigation. Finally, we hope that the proposed taxonomy and mapping also helps to provide an easy way for new practitioners to understand this complex area of research.
Tradeoff Between Source and Channel Coding for Erasure Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we investigate the optimal tradeoff between source and channel coding for channels with bit or packet erasure. Upper and Lower bounds on the optimal channel coding rate are computed to achieve minimal end-to-end distortion. The bounds are calculated based on a combination of sphere packing, straight line and expurgated error exponents and also high rate vector quantization theory. By modeling a packet erasure channel in terms of an equivalent bit erasure channel, we obtain bounds on the packet size for a specified limit on the distortion.
Antenna array geometry and coding performance
Venue: arXiv cs.IT 2005
Year: 2005

This paper provides details about experiments in realistic, urban, and frequency flat channels with space-time coding that specifically examines the impact of the number of receive antennas and the design criteria for code selection on the performance. Also the performance characteristics are examined of the coded modulations in the presence of finite size array geometries. This paper gives some insight into which of the theories are most useful in realistic deployments.
Competitive on-line learning with a convex loss function
Venue: arXiv cs.LG 2005
Year: 2005

We consider the problem of sequential decision making under uncertainty in which the loss caused by a decision depends on the following binary observation. In competitive on-line learning, the goal is to design decision algorithms that are almost as good as the best decision rules in a wide benchmark class, without making any assumptions about the way the observations are generated. However, standard algorithms in this area can only deal with finite-dimensional (often countable) benchmark classes. In this paper we give similar results for decision rules ranging over an arbitrary reproducing kernel Hilbert space. For example, it is shown that for a wide class of loss functions (including the standard square, absolute, and log loss functions) the average loss of the master algorithm, over the first $N$ observations, does not exceed the average loss of the best decision rule with a bounded norm plus $O(N^{-1/2})$. Our proof technique is very different from the standard ones and is based on recent results about defensive forecasting. Given the probabilities produced by a defensive forecasting algorithm, which are known to be well calibrated and to have good resolution in the long run, we use the expected loss minimization principle to find a suitable decision.
Decision Feedback Based Scheme for Slepian-Wolf Coding of sources with Hidden Markov Correlation
Venue: arXiv cs.IT 2005
Year: 2005

We consider the problem of compression of two memoryless binary sources, the correlation between which is defined by a Hidden Markov Model (HMM). We propose a Decision Feedback (DF) based scheme which when used with low density parity check codes results in compression close to the Slepian Wolf limits.
Dictionaries merger for text expansion in question answering
Venue: arXiv cs.DL 2005
Year: 2005

This paper presents an original way to add new data in a reference dictionary from several other lexical resources, without loosing any consistence. This operation is carried in order to get lexical information classified by the sense of the entry. This classification makes it possible to enrich utterances (in QA: the queries) following the meaning, and to reduce noise. An analysis of the experienced problems shows the interest of this method, and insists on the points that have to be tackled.
Enriching a Text by Semantic Disambiguation for Information Extraction
Venue: arXiv cs.IR 2005
Year: 2005

External linguistic resources have been used for a very long time in information extraction. These methods enrich a document with data that are semantically equivalent, in order to improve recall. For instance, some of these methods use synonym dictionaries. These dictionaries enrich a sentence with words that have a similar meaning. However, these methods present some serious drawbacks, since words are usually synonyms only in restricted contexts. The method we propose here consists of using word sense disambiguation rules (WSD) to restrict the selection of synonyms to only these that match a specific syntactico-semantic context. We show how WSD rules are built and how information extraction techniques can benefit from the application of these rules.
About one 3-parameter Model of Testing
Venue: arXiv cs.LG 2005
Year: 2005

This article offers a 3-parameter model of testing, with 1) the difference between the ability level of the examinee and item difficulty; 2) the examinee discrimination and 3) the item discrimination as model parameters.
Signal transmission on lossy lines as a dissipative quantum state propagation
Venue: arXiv cs.NI 2005
Year: 2005

The transmission of electric signals on a coupled line with distributed RLC-parameters is considered as a propagation of a dissipative quasi particle. A calculation technique is developed, alternative to the one, accepted for lumped lines. The relativistic wave equation for the transient response is deduced following the common Ohm-low-type considerations. The exact expressions for the Green function, for information transfer velocity and for time delay are obtained on this base. The fundamental restrictions on the measurement accuracy of the time delay are pointed out. The obtained results are naturally generalized for the multilevel networks of the arbitrary dimension.
Redundancy in Logic II: 2CNF and Horn Propositional Formulae
Venue: arXiv cs.AI 2005
Year: 2005

We report complexity results about redundancy of formulae in 2CNF form. We first consider the problem of checking redundancy and show some algorithms that are slightly better than the trivial one. We then analyze problems related to finding irredundant equivalent subsets (I.E.S.) of a given set. The concept of cyclicity proved to be relevant to the complexity of these problems. Some results about Horn formulae are also shown.
Three lines proof of the lower bound for the matrix rigidity
Venue: arXiv cs.CC 2005
Year: 2005

The rigidity of a matrix describes the minimal number of entries one has to change to reduce matrix's rank to r. We give very simple combinatorial proof of the lower bound for the rigidity of Sylvester (special case of Hadamard) matrix that matches the best known result by de Wolf(2005) for Hadamard matrices proved by quantum information theoretical arguments.
Large System Decentralized Detection Performance Under Communication Constraints
Venue: arXiv cs.IT 2005
Year: 2005

The problem of decentralized detection in a sensor network subjected to a total average power constraint and all nodes sharing a common bandwidth is investigated. The bandwidth constraint is taken into account by assuming non-orthogonal communication between sensors and the data fusion center via direct-sequence code-division multiple-access (DS-CDMA). In the case of large sensor systems and random spreading, the asymptotic decentralized detection performance is derived assuming independent and identically distributed (iid) sensor observations via random matrix theory. The results show that, even under both power and bandwidth constraints, it is better to combine many not-so-good local decisions rather than relying on one (or a few) very-good local decisions.
On Maximum Contention-Free Interleavers and Permutation Polynomials over Integer Rings
Venue: arXiv cs.IT 2005
Year: 2005

An interleaver is a critical component for the channel coding performance of turbo codes. Algebraic constructions are of particular interest because they admit analytical designs and simple, practical hardware implementation. Contention-free interleavers have been recently shown to be suitable for parallel decoding of turbo codes. In this correspondence, it is shown that permutation polynomials generate maximum contention-free interleavers, i.e., every factor of the interleaver length becomes a possible degree of parallel processing of the decoder. Further, it is shown by computer simulations that turbo codes using these interleavers perform very well for the 3rd Generation Partnership Project (3GPP) standard.
A Flexible Thread Scheduler for Hierarchical Multiprocessor Machines
Venue: arXiv cs.DC 2005
Year: 2005

With the current trend of multiprocessor machines towards more and more hierarchical architectures, exploiting the full computational power requires careful distribution of execution threads and data so as to limit expensive remote memory accesses. Existing multi-threaded libraries provide only limited facilities to let applications express distribution indications, so that programmers end up with explicitly distributing tasks according to the underlying architecture, which is difficult and not portable. In this article, we present: (1) a model for dynamically expressing the structure of the computation; (2) a scheduler interpreting this model so as to make judicious hierarchical distribution decisions; (3) an implementation within the Marcel user-level thread library. We experimented our proposal on a scientific application running on a ccNUMA Bull NovaScale with 16 Intel Itanium II processors; results show a 30% gain compared to a classical scheduler, and are similar to what a handmade scheduler achieves in a non-portable way.
Efficient Multiclass Implementations of L1-Regularized Maximum Entropy
Venue: arXiv cs.LG 2005
Year: 2005

This paper discusses the application of L1-regularized maximum entropy modeling or SL1-Max [9] to multiclass categorization problems. A new modification to the SL1-Max fast sequential learning algorithm is proposed to handle conditional distributions. Furthermore, unlike most previous studies, the present research goes beyond a single type of conditional distribution. It describes and compares a variety of modeling assumptions about the class distribution (independent or exclusive) and various types of joint or conditional distributions. It results in a new methodology for combining binary regularized classifiers to achieve multiclass categorization. In this context, Maximum Entropy can be considered as a generic and efficient regularized classification tool that matches or outperforms the state-of-the art represented by AdaBoost and SVMs.