OpenRaiser/Intern-Atlas huggingface dataset:
A new authentication protocol for revocable anonymity in ad-hoc networks
Venue: arXiv cs.CR 2005
Year: 2005

This paper describes a new protocol for authentication in ad-hoc networks. The protocol has been designed to meet specialized requirements of ad-hoc networks, such as lack of direct communication between nodes or requirements for revocable anonymity. At the same time, a ad-hoc authentication protocol must be resistant to spoofing, eavesdropping and playback, and man-in-the-middle attacks. The article analyzes existing authentication methods based on the Public Key Infrastructure, and finds that they have several drawbacks in ad-hoc networks. Therefore, a new authentication protocol, basing on established cryptographic primitives (Merkle's puzzles and zero-knowledge proofs) is proposed. The protocol is studied for a model ad-hoc chat application that provides private conversations.
On Interleaving Techniques for MIMO Channels and Limitations of Bit Interleaved Coded Modulation
Venue: arXiv cs.IT 2005
Year: 2005

It is shown that while the mutual information curves for coded modulation (CM) and bit interleaved coded modulation (BICM) overlap in the case of a single input single output channel, the same is not true in multiple input multiple output (MIMO) channels. A method for mitigating fading in the presence of multiple transmit antennas, named coordinate interleaving (CI), is presented as a generalization of component interleaving for a single transmit antenna. The extent of any advantages of CI over BICM, relative to CM, is analyzed from a mutual information perspective; the analysis is based on an equivalent parallel channel model for CI. Several expressions for mutual information in the presence of CI and multiple transmit and receive antennas are derived. Results show that CI gives higher mutual information compared to that of BICM if proper signal mappings are used. Effects like constellation rotation in the presence of CI are also considered and illustrated; it is shown that constellation rotation can increase the constrained capacity.
Vector Gaussian Multiple Description with Individual and Central Receivers
Venue: arXiv cs.IT 2005
Year: 2005

L multiple descriptions of a vector Gaussian source for individual and central receivers are investigated. The sum rate of the descriptions with covariance distortion measure constraints, in a positive semidefinite ordering, is exactly characterized. For two descriptions, the entire rate region is characterized. Jointly Gaussian descriptions are optimal in achieving the limiting rates. The key component of the solution is a novel information-theoretic inequality that is used to lower bound the achievable multiple description rates.
MathPSfrag: Creating Publication-Quality Labels in Mathematica Plots
Venue: arXiv cs.GR 2005
Year: 2005

This article introduces a Mathematica package providing a graphics export function that automatically replaces Mathematica expressions in a graphic by the corresponding LaTeX constructs and positions them correctly. It thus facilitates the creation of publication-quality Enscapulated PostScript (EPS) graphics.
A simple effective method for curvatures estimation on triangular meshes
Venue: arXiv cs.CG 2005
Year: 2005

To definite and compute differential invariants, like curvatures, for triangular meshes (or polyhedral surfaces) is a key problem in CAGD and the computer vision. The Gaussian curvature and the mean curvature are determined by the differential of the Gauss map of the underlying surface. The Gauss map assigns to each point in the surface the unit normal vector of the tangent plane to the surface at this point. We follow the ideas developed in Chen and Wu \cite{Chen2}(2004) and Wu, Chen and Chi\cite{Wu}(2005) to describe a new and simple approach to estimate the differential of the Gauss map and curvatures from the viewpoint of the gradient and the centroid weights. This will give us a much better estimation of curvatures than Taubin's algorithm \cite{Taubin} (1995).
ParFORM: recent development
Venue: arXiv cs.SC 2005
Year: 2005

We report on the status of our project of parallelization of the symbolic manipulation program FORM. We have now parallel versions of FORM running on Cluster- or SMP-architectures. These versions can be used to run arbitrary FORM programs in parallel.
Analysis of Stochastic Service Guarantees in Communication Networks: A Basic Calculus
Venue: arXiv cs.PF 2005
Year: 2005

A basic calculus is presented for stochastic service guarantee analysis in communication networks. Central to the calculus are two definitions, maximum-(virtual)-backlog-centric (m.b.c) stochastic arrival curve and stochastic service curve, which respectively generalize arrival curve and service curve in the deterministic network calculus framework. With m.b.c stochastic arrival curve and stochastic service curve, various basic results are derived under the (min, +) algebra for the general case analysis, which are crucial to the development of stochastic network calculus. These results include (i) superposition of flows, (ii) concatenation of servers, (iii) output characterization, (iv) per-flow service under aggregation, and (v) stochastic backlog and delay guarantees. In addition, to perform independent case analysis, stochastic strict server is defined, which uses an ideal service process and an impairment process to characterize a server. The concept of stochastic strict server not only allows us to improve the basic results (i) -- (v) under the independent case, but also provides a convenient way to find the stochastic service curve of a serve. Moreover, an approach is introduced to find the m.b.c stochastic arrival curve of a flow and the stochastic service curve of a server.
The Impact of Social Networks on Multi-Agent Recommender Systems
Venue: arXiv cs.LG 2005
Year: 2005

Awerbuch et al.'s approach to distributed recommender systems (DRSs) is to have agents sample products at random while randomly querying one another for the best item they have found; we improve upon this by adding a communication network. Agents can only communicate with their immediate neighbors in the network, but neighboring agents may or may not represent users with common interests. We define two network structures: in the ``mailing-list model,'' agents representing similar users form cliques, while in the ``word-of-mouth model'' the agents are distributed randomly in a scale-free network (SFN). In both models, agents tell their neighbors about satisfactory products as they are found. In the word-of-mouth model, knowledge of items propagates only through interested agents, and the SFN parameters affect the system's performance. We include a summary of our new results on the character and parameters of random subgraphs of SFNs, in particular SFNs with power-law degree distributions down to minimum degree 1. These networks are not as resilient as Cohen et al. originally suggested. In the case of the widely-cited ``Internet resilience'' result, high failure rates actually lead to the orphaning of half of the surviving nodes after 60% of the network has failed and the complete disintegration of the network at 90%. We show that given an appropriate network, the communication network reduces the number of sampled items, the number of messages sent, and the amount of ``spam.'' We conclude that in many cases DRSs will be useful for sharing information in a multi-agent learning system.
A Decision Theoretic Framework for Real-Time Communication
Venue: arXiv cs.IT 2005
Year: 2005

We consider a communication system in which the outputs of a Markov source are encoded and decoded in \emph{real-time} by a finite memory receiver, and the distortion measure does not tolerate delays. The objective is to choose designs, i.e. real-time encoding, decoding and memory update strategies that minimize a total expected distortion measure. This is a dynamic team problem with non-classical information structure [Witsenhausen:1971]. We use the structural results of [Teneketzis:2004] to develop a sequential decomposition for the finite and infinite horizon problems. Thus, we obtain a systematic methodology for the determination of jointly optimal encoding decoding and memory update strategies for real-time point-to-point communication systems.
Various Solutions to the Firing Squad Synchronization Problems
Venue: arXiv cs.DS 2005
Year: 2005

We present different classes of solutions to the Firing Squad Synchronization Problem on networks of different shapes. The nodes are finite state processors that work at unison discrete steps. The networks considered are the line, the ring and the square. For all of these models we have considered one and two-way communication modes and also constrained the quantity of information that adjacent processors can exchange each step. We are given a particular time expressed as a function of the number of nodes of the network, $f(n)$ and present synchronization algorithms in time $n^2$, $n \log n$, $n\sqrt n$, $2^n$. The solutions are presented as {\em signals} that are used as building blocks to compose new solutions for all times expressed by polynomials with nonnegative coefficients.
Pathwords: a user-friendly schema for common passwords management
Venue: arXiv cs.CR 2005
Year: 2005

Many computer-based authentication schemata are based on pass- words. Logging on a computer, reading email, accessing content on a web server are all examples of applications where the identification of the user is usually accomplished matching the data provided by the user with data known by the application. Such a widespread approach relies on some assumptions, whose satisfaction is of foremost importance to guarantee the robustness of the solution. Some of these assumptions, like having a "secure" chan- nel to transmit data, or having sound algorithms to check the correct- ness of the data, are not addressed by this paper. We will focus on two simple issues: the problem of using adequate passwords and the problem of managing passwords. The proposed solution, the pathword, is a method that guarantees: 1 that the passwords generated with the help of a pathword are adequate (i.e. that they are not easy to guess), 2 that managing pathwords is more user friendly than managing passwords and that pathwords are less amenable to problems typical of passwords.
The consistency principle for a digitization procedure. An algorithm for building normal digital spaces of continuous n-dimensional objects
Venue: arXiv cs.CV 2005
Year: 2005

This paper considers conditions, which allow to preserve important topological and geometric properties in the process of digitization. For this purpose, we introduce a triplet {C,M,D} consisting of a continuous object C, an intermediate model M, which is a collection of subregions whose union is C, a digital model D, which is the intersection graph of M, and apply the consistency principle and criteria of similarity to M in order to make its mathematical structure consistent with the natural structure of D. Specifically, this paper introduces a locally centered lump collection of subregions and shows that for any locally centered lump cover of an n-dimensional continuous manifold, the digital model of the manifold is a digital normal n-dimensional space. In addition, we give examples of locally centered lump tilings of two-manifolds. We propose an algorithm for constructing normal digital models of continuous objects.
Proving that P is not equal to NP and that P is not equal to the intersection of NP and co-NP
Venue: arXiv cs.CC 2005
Year: 2005

The open question, P=NP?, was presented by Cook (1971). In this paper, a proof that P is not equal to NP is presented. In addition, it is shown that P is not equal to the intersection of NP and co-NP. Finally, the exact inclusion relationships between the classes P, NP and co-NP are presented.
Energy-Efficient Resource Allocation in Time Division Multiple-Access over Fading Channels
Venue: arXiv cs.IT 2005
Year: 2005

We investigate energy-efficiency issues and resource allocation policies for time division multi-access (TDMA) over fading channels in the power-limited regime. Supposing that the channels are frequency-flat block-fading and transmitters have full or quantized channel state information (CSI), we first minimize power under a weighted sum-rate constraint and show that the optimal rate and time allocation policies can be obtained by water-filling over realizations of convex envelopes of the minima for cost-reward functions. We then address a related minimization under individual rate constraints and derive the optimal allocation policies via greedy water-filling. Using water-filling across frequencies and fading states, we also extend our results to frequency-selective channels. Our approaches not only provide fundamental power limits when each user can support an infinite number of capacity-achieving codebooks, but also yield guidelines for practical designs where users can only support a finite number of adaptive modulation and coding (AMC) modes with prescribed symbol error probabilities, and also for systems where only discrete-time allocations are allowed.
Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity
Venue: arXiv cs.CC 2005
Year: 2005

This paper is motivated by questions such as P vs. NP and other questions in Boolean complexity theory. We describe an approach to attacking such questions with cohomology, and we show that using Grothendieck topologies and other ideas from the Grothendieck school gives new hope for such an attack. We focus on circuit depth complexity, and consider only finite topological spaces or Grothendieck topologies based on finite categories; as such, we do not use algebraic geometry or manifolds. Given two sheaves on a Grothendieck topology, their "cohomological complexity" is the sum of the dimensions of their Ext groups. We seek to model the depth complexity of Boolean functions by the cohomological complexity of sheaves on a Grothendieck topology. We propose that the logical AND of two Boolean functions will have its corresponding cohomological complexity bounded in terms of those of the two functions using ``virtual zero extensions.'' We propose that the logical negation of a function will have its corresponding cohomological complexity equal to that of the original function using duality theory. We explain these approaches and show that they are stable under pullbacks and base change. It is the subject of ongoing work to achieve AND and negation bounds simultaneously in a way that yields an interesting depth lower bound.
A Practical Approach to Joint Network-Source Coding
Venue: arXiv cs.IT 2005
Year: 2005

We are interested in how to best communicate a real valued source to a number of destinations (sinks) over a network with capacity constraints in a collective fidelity metric over all the sinks, a problem which we call joint network-source coding. It is demonstrated that multiple description codes along with proper diversity routing provide a powerful solution to joint network-source coding. A systematic optimization approach is proposed. It consists of optimizing the network routing given a multiple description code and designing optimal multiple description code for the corresponding optimized routes.
Uncertainty Principles for Signal Concentrations
Venue: arXiv cs.IT 2005
Year: 2005

Uncertainty principles for concentration of signals into truncated subspaces are considered. The ``classic'' uncertainty principle is explored as a special case of a more general operator framework. The time-bandwidth concentration problem is shown as a similar special case. A spatial concentration of radio signals example is provided, and it is shown that an uncertainty principle exists for concentration of single-frequency signals for regions in space. We show that the uncertainty is related to the volumes of the spatial regions.
A Software Framework for Vehicle-Infrastructure Cooperative Applications
Venue: arXiv cs.IR 2005
Year: 2005

A growing category of vehicle-infrastructure cooperative (VIC) applications requires telematics software components distributed between an infrastructure-based management center and a number of vehicles. This article presents an approach based on a software framework, focusing on a Telematic Management System (TMS), a component suite aimed to run inside an infrastructure-based operations center, in some cases interacting with legacy systems like Advanced Traffic Management Systems or Vehicle Relationship Management. The TMS framework provides support for modular, flexible, prototyping and implementation of VIC applications. This work has received the support of the European Commission in the context of the projects REACT and CyberCars.
An algorithm for the k-error linear complexity of a sequence with period 2pn over GF(q)
Venue: arXiv cs.CR 2005
Year: 2005

The union cost is used, so that an efficient algorithm for computing the k-error linear complexity of a sequence with period 2pn over GF(q) is presented, where p and q are odd primes, and q is a primitive root of modulo p2.
Preference Learning in Terminology Extraction: A ROC-based approach
Venue: arXiv cs.LG 2005
Year: 2005

A key data preparation step in Text Mining, Term Extraction selects the terms, or collocation of words, attached to specific concepts. In this paper, the task of extracting relevant collocations is achieved through a supervised learning algorithm, exploiting a few collocations manually labelled as relevant/irrelevant. The candidate terms are described along 13 standard statistical criteria measures. From these examples, an evolutionary learning algorithm termed Roger, based on the optimization of the Area under the ROC curve criterion, extracts an order on the candidate terms. The robustness of the approach is demonstrated on two real-world domain applications, considering different domains (biology and human resources) and different languages (English and French).
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
Venue: arXiv cs.CC 2005
Year: 2005

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one of Lutz and Mayordomo's "Twelve Problems in Resource-Bounded Measure" (1999).
Complex Random Vectors and ICA Models: Identifiability, Uniqueness and Separability
Venue: arXiv cs.IT 2005
Year: 2005

In this paper the conditions for identifiability, separability and uniqueness of linear complex valued independent component analysis (ICA) models are established. These results extend the well-known conditions for solving real-valued ICA problems to complex-valued models. Relevant properties of complex random vectors are described in order to extend the Darmois-Skitovich theorem for complex-valued models. This theorem is used to construct a proof of a theorem for each of the above ICA model concepts. Both circular and noncircular complex random vectors are covered. Examples clarifying the above concepts are presented.
On the Asymptotic Weight and Stopping Set Distribution of Regular LDPC Ensembles
Venue: arXiv cs.IT 2005
Year: 2005

We estimate the variance of weight and stopping set distribution of regular LDPC ensembles. Using this estimate and the second moment method we obtain bounds on the probability that a randomly chosen code from regular LDPC ensemble has its weight distribution and stopping set distribution close to respective ensemble averages. We are able to show that a large fraction of total number of codes have their weight and stopping set distribution close to the average.
Dynamic Web File Format Transformations with Grace
Venue: arXiv cs.DL 2005
Year: 2005

Web accessible content stored in obscure, unpopular or obsolete formats represents a significant problem for digital preservation. The file formats that encode web content represent the implicit and explicit choices of web site maintainers at a particular point in time. Older file formats that have fallen out of favor are obviously a problem, but so are new file formats that have not yet been fully supported by browsers. Often browsers use plug-in software for displaying old and new formats, but plug-ins can be difficult to find, install and replicate across all environments that one may use. We introduce Grace, an http proxy server that transparently converts browser-incompatible and obsolete web content into web content that a browser is able to display without the use of plug-ins. Grace is configurable on a per user basis and can be expanded to provide an array of conversion services. We illustrate how the Grace prototype transforms several image formats (XBM, PNG with various alpha channels, and JPEG 2000) so they are viewable in Internet Explorer.
Computations with one and two real algebraic numbers
Venue: arXiv cs.SC 2005
Year: 2005

We present algorithmic and complexity results concerning computations with one and two real algebraic numbers, as well as real solving of univariate polynomials and bivariate polynomial systems with integer coefficients using Sturm-Habicht sequences. Our main results, in the univariate case, concern the problems of real root isolation (Th. 19) and simultaneous inequalities (Cor.26) and in the bivariate, the problems of system real solving (Th.42), sign evaluation (Th. 37) and simultaneous inequalities (Cor. 43).
Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes
Venue: arXiv cs.IT 2005
Year: 2005

The goal of the present paper is the derivation of a framework for the finite-length analysis of message-passing iterative decoding of low-density parity-check codes. To this end we introduce the concept of graph-cover decoding. Whereas in maximum-likelihood decoding all codewords in a code are competing to be the best explanation of the received vector, under graph-cover decoding all codewords in all finite covers of a Tanner graph representation of the code are competing to be the best explanation. We are interested in graph-cover decoding because it is a theoretical tool that can be used to show connections between linear programming decoding and message-passing iterative decoding. Namely, on the one hand it turns out that graph-cover decoding is essentially equivalent to linear programming decoding. On the other hand, because iterative, locally operating decoding algorithms like message-passing iterative decoding cannot distinguish the underlying Tanner graph from any covering graph, graph-cover decoding can serve as a model to explain the behavior of message-passing iterative decoding. Understanding the behavior of graph-cover decoding is tantamount to understanding the so-called fundamental polytope. Therefore, we give some characterizations of this polytope and explain its relation to earlier concepts that were introduced to understand the behavior of message-passing iterative decoding for finite-length codes.
EqRank: Theme Evolution in Citation Graphs
Venue: arXiv cs.DS 2005
Year: 2005

Time evolution of the classification scheme generated by the EqRank algorithm is studied with hep-th citation graph as an example. Intuitive expectations about evolution of an adequate classification scheme for a growing set of objects are formulated. Evolution compliant with these expectations is called natural. It is demonstrated that EqRank yields a naturally evolving classification scheme. We conclude that EqRank can be used as a means to detect new scientific themes, and to track their development.