title: ScotGrid: A Prototype Tier 2 Centre

abstract: ScotGrid is a prototype regional computing centre formed as a collaboration between the universities of Durham, Edinburgh and Glasgow as part of the UK's national particle physics grid, GridPP. We outline the resources available at the three core sites and our optimisation efforts for our user communities. We discuss the work which has been conducted in extending the centre to embrace new projects both from particle physics and new user communities and explain our methodology for doing this.


title: Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time

abstract: We study the problem of preemptive scheduling of n equal-length jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time. Recently, Brucker and Kravchenko proved that the optimal schedule can be computed in polynomial time by solving a linear program with O(n^3) variables and constraints, followed by some substantial post-processing (where n is the number of jobs.) In this note we describe a simple linear program with only O(mn) variables and constraints. Our linear program produces directly the optimal schedule and does not require any post-processing.


title: Partitioning Regular Polygons into Circular Pieces II:Nonconvex Partitions

abstract: We explore optimal circular nonconvex partitions of regular k-gons. The circularity of a polygon is measured by its aspect ratio: the ratio of the radii of the smallest circumscribing circle to the largest inscribed disk. An optimal circular partition minimizes the maximum ratio over all pieces in the partition. We show that the equilateral triangle has an optimal 4-piece nonconvex partition, the square an optimal 13-piece nonconvex partition, and the pentagon has an optimal nonconvex partition with more than 20 thousand pieces. For hexagons and beyond, we provide a general algorithm that approaches optimality, but does not achieve it.


title: Complexity of Self-Assembled Shapes

abstract: The connection between self-assembly and computation suggests that a shape can be considered the output of a self-assembly ``program,'' a set of tiles that fit together to create a shape. It seems plausible that the size of the smallest self-assembly program that builds a shape and the shape's descriptional (Kolmogorov) complexity should be related. We show that when using a notion of a shape that is independent of scale, this is indeed so: in the Tile Assembly Model, the minimal number of distinct tile types necessary to self-assemble a shape, at some scale, can be bounded both above and below in terms of the shape's Kolmogorov complexity. As part of the proof of the main result, we sketch a general method for converting a program outputting a shape as a list of locations into a set of tile types that self-assembles into a scaled up version of that shape. Our result implies, somewhat counter-intuitively, that self-assembly of a scaled-up version of a shape often requires fewer tile types. Furthermore, the independence of scale in self-assembly theory appears to play the same crucial role as the independence of running time in the theory of computability. This leads to an elegant formulation of languages of shapes generated by self-assembly. Considering functions from integers to shapes, we show that the running-time complexity, with respect to Turing machines, is polynomially equivalent to the scale complexity of the same function implemented via self-assembly by a finite set of tile types. Our results also hold for shapes defined by Wang tiling -- where there is no sense of a self-assembly process -- except that here time complexity must be measured with respect to non-deterministic Turing machines.


title: The Computational Power of Benenson Automata

abstract: The development of autonomous molecular computers capable of making independent decisions in vivo regarding local drug administration may revolutionize medical science. Recently Benenson at el (2004) have envisioned one form such a ``smart drug'' may take by implementing an in vitro scheme, in which a long DNA state molecule is cut repeatedly by a restriction enzyme in a manner dependent upon the presence of particular short DNA ``rule molecules.'' To analyze the potential of their scheme in terms of the kinds of computations it can perform, we study an abstraction assuming that a certain class of restriction enzymes is available and reactions occur without error. We also discuss how our molecular algorithms could perform with known restriction enzymes. By exhibiting a way to simulate arbitrary circuits, we show that these ``Benenson automata'' are capable of computing arbitrary Boolean functions. Further, we show that they are able to compute efficiently exactly those functions computable by log-depth circuits. Computationally, we formalize a new variant of limited width branching programs with a molecular implementation.


title: The Google Similarity Distance

abstract: Words and phrases acquire meaning from the way they are used in society, from their relative semantics to other words and phrases. For computers the equivalent of `society' is `database,' and the equivalent of `use' is `way to search the database.' We present a new theory of similarity between words and phrases based on information distance and Kolmogorov complexity. To fix thoughts we use the world-wide-web as database, and Google as search engine. The method is also applicable to other search engines and databases. This theory is then applied to construct a method to automatically extract similarity, the Google similarity distance, of words and phrases from the world-wide-web using Google page counts. The world-wide-web is the largest database on earth, and the context information entered by millions of independent users averages out to provide automatic semantics of useful quality. We give applications in hierarchical clustering, classification, and language translation. We give examples to distinguish between colors and numbers, cluster names of paintings by 17th century Dutch masters and names of books by English novelists, the ability to understand emergencies, and primes, and we demonstrate the ability to do a simple automatic English-Spanish translation. Finally, we use the WordNet database as an objective baseline against which to judge the performance of our method. We conduct a massive randomized trial in binary classification using support vector machines to learn categories based on our Google distance, resulting in an a mean agreement of 87% with the expert crafted WordNet categories.


title: An unbreakable cryptosystem

abstract: The remarkably long-standing problem of cryptography is to generate completely secure key. It is widely believed that the task cannot be achieved within classical cryptography. However, there is no proof in support of this belief. We present an incredibly simple classical cryptosystem which can generate completely secure key.


title: Formal Test Purposes and The Validity of Test Cases

abstract: We give a formalization of the notion of test purpose based on (suitably restricted) Message Sequence Charts. We define the validity of test cases with respect to such a formal test purpose and provide a simple decision procedure for validity.


title: The Inverse Method Implements the Automata Approach for Modal Satisfiability

abstract: Tableaux-based decision procedures for satisfiability of modal and description logics behave quite well in practice, but it is sometimes hard to obtain exact worst-case complexity results using these approaches, especially for EXPTIME-complete logics. In contrast, automata-based approaches often yield algorithms for which optimal worst-case complexity can easily be proved. However, the algorithms obtained this way are usually not only worst-case, but also best-case exponential: they first construct an automaton that is always exponential in the size of the input, and then apply the (polynomial) emptiness test to this large automaton. To overcome this problem, one must try to construct the automaton "on-the-fly" while performing the emptiness test. In this paper we will show that Voronkov's inverse method for the modal logic K can be seen as an on-the-fly realization of the emptiness test done by the automata approach for K. The benefits of this result are two-fold. First, it shows that Voronkov's implementation of the inverse method, which behaves quite well in practice, is an optimized on-the-fly implementation of the automata-based satisfiability procedure for K. Second, it can be used to give a simpler proof of the fact that Voronkov's optimizations do not destroy completeness of the procedure. We will also show that the inverse method can easily be extended to handle global axioms, and that the correspondence to the automata approach still holds in this setting. In particular, the inverse method yields an EXPTIME-algorithm for satisfiability in K w.r.t. global axioms.


title: Quantum Interactive Proofs with Competing Provers

abstract: This paper studies quantum refereed games, which are quantum interactive proof systems with two competing provers: one that tries to convince the verifier to accept and the other that tries to convince the verifier to reject. We prove that every language having an ordinary quantum interactive proof system also has a quantum refereed game in which the verifier exchanges just one round of messages with each prover. A key part of our proof is the fact that there exists a single quantum measurement that reliably distinguishes between mixed states chosen arbitrarily from disjoint convex sets having large minimal trace distance from one another. We also show how to reduce the probability of error for some classes of quantum refereed games.


title: Chosen-Plaintext Cryptanalysis of a Clipped-Neural-Network-Based Chaotic Cipher

abstract: 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.


title: Negotiating over Bundles and Prices Using Aggregate Knowledge

abstract: Combining two or more items and selling them as one good, a practice called bundling, can be a very effective strategy for reducing the costs of producing, marketing, and selling goods. In this paper, we consider a form of multi-issue negotiation where a shop negotiates both the contents and the price of bundles of goods with his customers. We present some key insights about, as well as a technique for, locating mutually beneficial alternatives to the bundle currently under negotiation. The essence of our approach lies in combining historical sales data, condensed into aggregate knowledge, with current data about the ongoing negotiation process, to exploit these insights. In particular, when negotiating a given bundle of goods with a customer, the shop analyzes the sequence of the customer's offers to determine the progress in the negotiation process. In addition, it uses aggregate knowledge concerning customers' valuations of goods in general. We show how the shop can use these two sources of data to locate promising alternatives to the current bundle. When the current negotiation's progress slows down, the shop may suggest the most promising of those alternatives and, depending on the customer's response, continue negotiating about the alternative bundle, or propose another alternative. Extensive computer simulation experiments show that our approach increases the speed with which deals are reached, as well as the number and quality of the deals reached, as compared to a benchmark. In addition, we show that the performance of our system is robust to a variety of changes in the negotiation strategies employed by the customers.


title: On the existence of stable models of non-stratified logic programs

abstract: This paper introduces a fundamental result, which is relevant for Answer Set programming, and planning. For the first time since the definition of the stable model semantics, the class of logic programs for which a stable model exists is given a syntactic characterization. This condition may have a practical importance both for defining new algorithms for checking consistency and computing answer sets, and for improving the existing systems. The approach of this paper is to introduce a new canonical form (to which any logic program can be reduced to), to focus the attention on cyclic dependencies. The technical result is then given in terms of programs in canonical form (canonical programs), without loss of generality. The result is based on identifying the cycles contained in the program, showing that stable models of the overall program are composed of stable models of suitable sub-programs, corresponding to the cycles, and on defining the Cycle Graph. Each vertex of this graph corresponds to one cycle, and each edge corresponds to onehandle, which is a literal containing an atom that, occurring in both cycles, actually determines a connection between them. In fact, the truth value of the handle in the cycle where it appears as the head of a rule, influences the truth value of the atoms of the cycle(s) where it occurs in the body. We can therefore introduce the concept of a handle path, connecting different cycles. If for every odd cycle we can find a handle path with certain properties, then the existence of stable model is guaranteed.


title: Online Learning of Aggregate Knowledge about Non-linear Preferences Applied to Negotiating Prices and Bundles

abstract: In this paper, we consider a form of multi-issue negotiation where a shop negotiates both the contents and the price of bundles of goods with his customers. We present some key insights about, as well as a procedure for, locating mutually beneficial alternatives to the bundle currently under negotiation. The essence of our approach lies in combining aggregate (anonymous) knowledge of customer preferences with current data about the ongoing negotiation process. The developed procedure either works with already obtained aggregate knowledge or, in the absence of such knowledge, learns the relevant information online. We conduct computer experiments with simulated customers that have_nonlinear_ preferences. We show how, for various types of customers, with distinct negotiation heuristics, our procedure (with and without the necessary aggregate knowledge) increases the speed with which deals are reached, as well as the number and the Pareto efficiency of the deals reached compared to a benchmark.


title: A Monte Carlo algorithm for efficient large matrix inversion

abstract: This paper introduces a new Monte Carlo algorithm to invert large matrices. It is based on simultaneous coupled draws from two random vectors whose covariance is the required inverse. It can be considered a generalization of a previously reported algorithm for hermitian matrices inversion based in only one draw. The use of two draws allows the inversion on non-hermitian matrices. Both the conditions for convergence and the rate of convergence are similar to the Gauss-Seidel algorithm. Results on two examples are presented, a real non-symmetric matrix related to quantitative genetics and a complex non-hermitian matrix relevant for physicists. Compared with other Monte Carlo algorithms it reveals a large reduction of the processing time showing eight times faster processing in the examples studied.


title: Mutual Information and Minimum Mean-square Error in Gaussian Channels

abstract: This paper deals with arbitrarily distributed finite-power input signals observed through an additive Gaussian noise channel. It shows a new formula that connects the input-output mutual information and the minimum mean-square error (MMSE) achievable by optimal estimation of the input given the output. That is, the derivative of the mutual information (nats) with respect to the signal-to-noise ratio (SNR) is equal to half the MMSE, regardless of the input statistics. This relationship holds for both scalar and vector signals, as well as for discrete-time and continuous-time noncausal MMSE estimation. This fundamental information-theoretic result has an unexpected consequence in continuous-time nonlinear estimation: For any input signal with finite power, the causal filtering MMSE achieved at SNR is equal to the average value of the noncausal smoothing MMSE achieved with a channel whose signal-to-noise ratio is chosen uniformly distributed between 0 and SNR.


title: Global minimization of a quadratic functional: neural network approach

abstract: The problem of finding out the global minimum of a multiextremal functional is discussed. One frequently faces with such a functional in various applications. We propose a procedure, which depends on the dimensionality of the problem polynomially. In our approach we use the eigenvalues and eigenvectors of the connection matrix.


title: Q-valued neural network as a system of fast identification and pattern recognition

abstract: An effective neural network algorithm of the perceptron type is proposed. The algorithm allows us to identify strongly distorted input vector reliably. It is shown that its reliability and processing speed are orders of magnitude higher than that of full connected neural networks. The processing speed of our algorithm exceeds the one of the stack fast-access retrieval algorithm that is modified for working when there are noises in the input channel.


title: On the asymptotic accuracy of the union bound

abstract: A new lower bound on the error probability of maximum likelihood decoding of a binary code on a binary symmetric channel was proved in Barg and McGregor (2004, cs.IT/0407011). It was observed in that paper that this bound leads to a new region of code rates in which the random coding exponent is asymptotically tight, giving a new region in which the reliability of the BSC is known exactly. The present paper explains the relation of these results to the union bound on the error probability.


title: Source Coding With Encoder Side Information

abstract: We introduce the idea of distortion side information, which does not directly depend on the source but instead affects the distortion measure. We show that such distortion side information is not only useful at the encoder, but that under certain conditions, knowing it at only the encoder is as good as knowing it at both encoder and decoder, and knowing it at only the decoder is useless. Thus distortion side information is a natural complement to the signal side information studied by Wyner and Ziv, which depends on the source but does not involve the distortion measure. Furthermore, when both types of side information are present, we characterize the penalty for deviating from the configuration of encoder-only distortion side information and decoder-only signal side information, which in many cases is as good as full side information knowledge.


title: Source-Channel Diversity for Parallel Channels

abstract: We consider transmitting a source across a pair of independent, non-ergodic channels with random states (e.g., slow fading channels) so as to minimize the average distortion. The general problem is unsolved. Hence, we focus on comparing two commonly used source and channel encoding systems which correspond to exploiting diversity either at the physical layer through parallel channel coding or at the application layer through multiple description source coding. For on-off channel models, source coding diversity offers better performance. For channels with a continuous range of reception quality, we show the reverse is true. Specifically, we introduce a new figure of merit called the distortion exponent which measures how fast the average distortion decays with SNR. For continuous-state models such as additive white Gaussian noise channels with multiplicative Rayleigh fading, optimal channel coding diversity at the physical layer is more efficient than source coding diversity at the application layer in that the former achieves a better distortion exponent. Finally, we consider a third decoding architecture: multiple description encoding with a joint source-channel decoding. We show that this architecture achieves the same distortion exponent as systems with optimal channel coding diversity for continuous-state channels, and maintains the the advantages of multiple description systems for on-off channels. Thus, the multiple description system with joint decoding achieves the best performance, from among the three architectures considered, on both continuous-state and on-off channels.


title: State of the Art, Evaluation and Recommendations regarding "Document Processing and Visualization Techniques"

abstract: Several Networks of Excellence have been set up in the framework of the European FP5 research program. Among these Networks of Excellence, the NEMIS project focuses on the field of Text Mining. Within this field, document processing and visualization was identified as one of the key topics and the WG1 working group was created in the NEMIS project, to carry out a detailed survey of techniques associated with the text mining process and to identify the relevant research topics in related research areas. In this document we present the results of this comprehensive survey. The report includes a description of the current state-of-the-art and practice, a roadmap for follow-up research in the identified areas, and recommendations for anticipated technological development in the domain of text mining.


title: Reductions in Distributed Computing Part I: Consensus and Atomic Commitment Tasks

abstract: We introduce several notions of reduction in distributed computing, and investigate reduction properties of two fundamental agreement tasks, namely Consensus and Atomic Commitment. We first propose the notion of reduction "a la Karp'', an analog for distributed computing of the classical Karp reduction. We then define a weaker reduction which is the analog of Cook reduction. These two reductions are called K-reduction and C-reduction, respectively. We also introduce the notion of C*-reduction which has no counterpart in classical (namely, non distributed) systems, and which naturally arises when dealing with symmetric tasks. We establish various reducibility and irreducibility theorems with respect to these three reductions. Our main result is an incomparability statement for Consensus and Atomic Commitment tasks: we show that they are incomparable with respect to the C-reduction, except when the resiliency degree is 1, in which case Atomic Commitment is strictly harder than Consensus. A side consequence of these results is that our notion of C-reduction is strictly weaker than the one of K-reduction, even for unsolvable tasks.


title: Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks

abstract: We extend the results of Part I by considering a new class of agreement tasks, the so-called k-Threshold Agreement tasks (previously introduced by Charron-Bost and Le Fessant). These tasks naturally interpolate between Atomic Commitment and Consensus. Moreover, they constitute a valuable tool to derive irreducibility results between Consensus tasks only. In particular, they allow us to show that (A) for a fixed set of processes, the higher the resiliency degree is, the harder the Consensus task is, and (B) for a fixed resiliency degree, the smaller the set of processes is, the harder the Consensus task is. The proofs of these results lead us to consider new oracle-based reductions, involving a weaker variant of the C-reduction introduced in Part I. We also discuss the relationship between our results and previous ones relating f-resiliency and wait-freedom.


title: Thematic Annotation: extracting concepts out of documents

abstract: Contrarily to standard approaches to topic annotation, the technique used in this work does not centrally rely on some sort of -- possibly statistical -- keyword extraction. In fact, the proposed annotation algorithm uses a large scale semantic database -- the EDR Electronic Dictionary -- that provides a concept hierarchy based on hyponym and hypernym relations. This concept hierarchy is used to generate a synthetic representation of the document by aggregating the words present in topically homogeneous document segments into a set of concepts best preserving the document's content. This new extraction technique uses an unexplored approach to topic selection. Instead of using semantic similarity measures based on a semantic resource, the later is processed to extract the part of the conceptual hierarchy relevant to the document content. Then this conceptual hierarchy is searched to extract the most relevant set of concepts to represent the topics discussed in the document. Notice that this algorithm is able to extract generic concepts that are not directly present in the document.


title: Power Aware Routing for Sensor Databases

abstract: Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensor network databases like TinyDB are the dominant architectures to extract and manage data in such networks. Since sensors have significant power constraints (battery life), and high communication costs, design of energy efficient communication algorithms is of great importance. The data flow in a sensor database is very different from data flow in an ordinary network and poses novel challenges in designing efficient routing algorithms. In this work we explore the problem of energy efficient routing for various different types of database queries and show that in general, this problem is NP-complete. We give a constant factor approximation algorithm for one class of query, and for other queries give heuristic algorithms. We evaluate the efficiency of the proposed algorithms by simulation and demonstrate their near optimal performance for various network sizes.


title: CDTP Chain Distributed Transfer Protocol

abstract: The rapid growth of the internet in general and of bandwidth capacity at internet clients in particular poses increasing computation and bandwidth demands on internet servers. Internet access technologies like ADSL [DSL], Cable Modem and Wireless modem allow internet clients to access the internet with orders of magnitude more bandwidth than using traditional modems. We present CDTP a distributed transfer protocol that allows clients to cooperate and therefore remove the strain from the internet server thus achieving much better performance than traditional transfer protocols (e.g. FTP [FTP]). The CDTP server and client tools are presented also as well as results of experiments. Finally a bandwidth measurement technique is presented. CDTP tools use this technique to differentiate between slow and fast clients.


title: An estimate of accuracy for interpolant numerical solutions of a PDE problem

abstract: In this paper we present an estimate of accuracy for a piecewise polynomial approximation of a classical numerical solution to a non linear differential problem. We suppose the numerical solution U is computed using a grid with a small linear step and interval time Tu, while the polynomial approximation V is an interpolation of the values of a numerical solution on a less fine grid and interval time Tv << Tu. The estimate shows that the interpolant solution V can be, under suitable hypotheses, a good approximation and in general its computational cost is much lower of the cost of the fine numerical solution. We present two possible applications to linear case and periodic case.


title: A Distributed Economics-based Infrastructure for Utility Computing

abstract: Existing attempts at utility computing revolve around two approaches. The first consists of proprietary solutions involving renting time on dedicated utility computing machines. The second requires the use of heavy, monolithic applications that are difficult to deploy, maintain, and use. We propose a distributed, community-oriented approach to utility computing. Our approach provides an infrastructure built on Web Services in which modular components are combined to create a seemingly simple, yet powerful system. The community-oriented nature generates an economic environment which results in fair transactions between consumers and providers of computing cycles while simultaneously encouraging improvements in the infrastructure of the computational grid itself.


title: A Survey of Distributed Intrusion Detection Approaches

abstract: Distributed intrustion detection systems detect attacks on computer systems by analyzing data aggregated from distributed sources. The distributed nature of the data sources allows patterns in the data to be seen that might not be detectable if each of the sources were examined individually. This paper describes the various approaches that have been developed to share and analyze data in such systems, and discusses some issues that must be addressed before fully decentralized distributed intrusion detection systems can be made viable.


title: A Survey of Fault-Tolerance and Fault-Recovery Techniques in Parallel Systems

abstract: Supercomputing systems today often come in the form of large numbers of commodity systems linked together into a computing cluster. These systems, like any distributed system, can have large numbers of independent hardware components cooperating or collaborating on a computation. Unfortunately, any of this vast number of components can fail at any time, resulting in potentially erroneous output. In order to improve the robustness of supercomputing applications in the presence of failures, many techniques have been developed to provide resilience to these kinds of system faults. This survey provides an overview of these various fault-tolerance techniques.


title: Implementation of Motzkin-Burger algorithm in Maple

abstract: Subject of this paper is an implementation of a well-known Motzkin-Burger algorithm, which solves the problem of finding the full set of solutions of a system of linear homogeneous inequalities. There exist a number of implementations of this algorithm, but there was no one in Maple, to the best of the author's knowledge.


title: Advances towards a General-Purpose Societal-Scale Human-Collective Problem-Solving Engine

abstract: Human collective intelligence has proved itself as an important factor in a society's ability to accomplish large-scale behavioral feats. As societies have grown in population-size, individuals have seen a decrease in their ability to activeily participate in the problem-solving processes of the group. Representative decision-making structures have been used as a modern solution to society's inadequate information-processing infrastructure. With computer and network technologies being further embedded within the fabric of society, the implementation of a general-purpose societal-scale human-collective problem-solving engine is envisioned as a means of furthering the collective-intelligence potential of society. This paper provides both a novel framework for creating collective intelligence systems and a method for implementing a representative and expertise system based on social-network theory.


title: Portfolio selection using neural networks

abstract: In this paper we apply a heuristic method based on artificial neural networks in order to trace out the efficient frontier associated to the portfolio selection problem. We consider a generalization of the standard Markowitz mean-variance model which includes cardinality and bounding constraints. These constraints ensure the investment in a given number of different assets and limit the amount of capital to be invested in each asset. We present some experimental results obtained with the neural network heuristic and we compare them to those obtained with three previous heuristic methods.


title: Formal Languages and Algorithms for Similarity based Retrieval from Sequence Databases

abstract: The paper considers various formalisms based on Automata, Temporal Logic and Regular Expressions for specifying queries over sequences. Unlike traditional binary semantics, the paper presents a similarity based semantics for thse formalisms. More specifically, a distance measure in the range [0,1] is associated with a sequence, query pair denoting how closely the sequence satisfies the query. These measures are defined using a spectrum of normed vector distance measures. Various distance measures based on the syntax and the traditional semantics of the query are presented. Efficient algorithms for computing these distance measure are presented. These algorithms can be employed for retrieval of sequence from a database that closely satisfy a given.


title: A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions

abstract: We propose a new refinement algorithm to generate size-optimal quality-guaranteed Delaunay triangulations in the plane. The algorithm takes $O(n \log n + m)$ time, where $n$ is the input size and $m$ is the output size. This is the first time-optimal Delaunay refinement algorithm.


title: Multipartite Secret Correlations and Bound Information

abstract: We consider the problem of secret key extraction when $n$ honest parties and an eavesdropper share correlated information. We present a family of probability distributions and give the full characterization of its distillation properties. This formalism allows us to design a rich variety of cryptographic scenarios. In particular, we provide examples of multipartite probability distributions containing non-distillable secret correlations, also known as bound information.


title: On The Liniar Time Complexity of Finite Languages

abstract: The present paper presents and proves a proposition concerning the time complexity of finite languages. It is shown herein, that for any finite language (a language for which the set of words composing it is finite) there is a Turing machine that computes the language in such a way that for any input of length k the machine stops in, at most, k + 1 steps.


title: A Cryptographic Study of Some Digital Signature Schemes

abstract: In this thesis, we propose some directed signature schemes. In addition, we have discussed their applications in different situations. In this thesis, we would like to discuss the security aspects during the design process of the proposed directed digital signature schemes. The security of the most digital signature schemes widely use in practice is based on the two difficult problems, viz; the problem of factoring integers (The RSA scheme) and the problem of finding discrete logarithms over finite fields (The ElGamal scheme). The proposed works in this thesis is divided into seven chapters.


title: A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm

abstract: A simple and natural Gao algorithm for decoding algebraic codes is described. Its relation to the Welch-Berlekamp and Euclidean algorithms is given.


title: Fedora: An Architecture for Complex Objects and their Relationships

abstract: The Fedora architecture is an extensible framework for the storage, management, and dissemination of complex objects and the relationships among them. Fedora accommodates the aggregation of local and distributed content into digital objects and the association of services with objects. This al-lows an object to have several accessible representations, some of them dy-namically produced. The architecture includes a generic RDF-based relation-ship model that represents relationships among objects and their components. Queries against these relationships are supported by an RDF triple store. The architecture is implemented as a web service, with all aspects of the complex object architecture and related management functions exposed through REST and SOAP interfaces. The implementation is available as open-source soft-ware, providing the foundation for a variety of end-user applications for digital libraries, archives, institutional repositories, and learning object systems.


title: On the security of the Yen-Guo's domino signal encryption algorithm (DSEA)

abstract: Recently, a new domino signal encryption algorithm (DSEA) was proposed for digital signal transmission, especially for digital images and videos. This paper analyzes the security of DSEA, and points out the following weaknesses: 1) its security against the brute-force attack was overestimated; 2) it is not sufficiently secure against ciphertext-only attacks, and only one ciphertext is enough to get some information about the plaintext and to break the value of a sub-key; 3) it is insecure against known/chosen-plaintext attacks, in the sense that the secret key can be recovered from a number of continuous bytes of only one known/chosen plaintext and the corresponding ciphertext. Experimental results are given to show the performance of the proposed attacks, and some countermeasures are discussed to improve DSEA.


title: On the Design of Perceptual MPEG-Video Encryption Algorithms

abstract: In this paper, some existing perceptual encryption algorithms of MPEG videos are reviewed and some problems, especially security defects of two recently proposed MPEG-video perceptual encryption schemes, are pointed out. Then, a simpler and more effective design is suggested, which selectively encrypts fixed-length codewords (FLC) in MPEG-video bitstreams under the control of three perceptibility factors. The proposed design is actually an encryption configuration that can work with any stream cipher or block cipher. Compared with the previously-proposed schemes, the new design provides more useful features, such as strict size-preservation, on-the-fly encryption and multiple perceptibility, which make it possible to support more applications with different requirements. In addition, four different measures are suggested to provide better security against known/chosen-plaintext attacks.


title: Application of Generating Functions and Partial Differential Equations in Coding Theory

abstract: In this work we have considered formal power series and partial differential equations, and their relationship with Coding Theory. We have obtained the nature of solutions for the partial differential equations for Cycle Poisson Case. The coefficients for this case have been simulated, and the high tendency of growth is shown. In the light of Complex Analysis, the Hadamard Multiplication's Theorem is presented as a new approach to divide the power sums relating to the error probability, each part of which can be analyzed later.


title: On the weight distribution of convolutional codes

abstract: Detailed information about the weight distribution of a convolutional code is given by the adjacency matrix of the state diagram associated with a controller canonical form of the code. We will show that this matrix is an invariant of the code. Moreover, it will be proven that codes with the same adjacency matrix have the same dimension and the same Forney indices and finally that for one-dimensional binary convolutional codes the adjacency matrix determines the code uniquely up to monomial equivalence.


title: Public Key Cryptography based on Semigroup Actions

abstract: A generalization of the original Diffie-Hellman key exchange in $(\Z/p\Z)^*$ found a new depth when Miller and Koblitz suggested that such a protocol could be used with the group over an elliptic curve. In this paper, we propose a further vast generalization where abelian semigroups act on finite sets. We define a Diffie-Hellman key exchange in this setting and we illustrate how to build interesting semigroup actions using finite (simple) semirings. The practicality of the proposed extensions rely on the orbit sizes of the semigroup actions and at this point it is an open question how to compute the sizes of these orbits in general and also if there exists a square root attack in general. In Section 2 a concrete practical semigroup action built from simple semirings is presented. It will require further research to analyse this system.


title: Combining Independent Modules in Lexical Multiple-Choice Problems

abstract: Existing statistical approaches to natural language problems are very coarse approximations to the true complexity of language processing. As such, no single technique will be best for all problem instances. Many researchers are examining ensemble methods that combine the output of multiple modules to create more accurate solutions. This paper examines three merging rules for combining probability distributions: the familiar mixture rule, the logarithmic rule, and a novel product rule. These rules were applied with state-of-the-art results to two problems used to assess human mastery of lexical semantics -- synonym questions and analogy questions. All three merging rules result in ensembles that are more accurate than any of their component modules. The differences among the three rules are not statistically significant, but it is suggestive that the popular mixture rule is not the best rule for either of the two problems.


title: Clustering SPIRES with EqRank

abstract: SPIRES is the largest database of scientific papers in the subject field of high energy and nuclear physics. It contains information on the citation graph of more than half a million of papers (vertexes of the citation graph). We outline the EqRank algorithm designed to cluster vertexes of directed graphs, and present the results of EqRank application to the SPIRES citation graph. The hierarchical clustering of SPIRES yielded by EqRank is used to set up a web service, which is also outlined.


title: Enhancing Histograms by Tree-Like Bucket Indices

abstract: Histograms are used to summarize the contents of relations into a number of buckets for the estimation of query result sizes. Several techniques (e.g., MaxDiff and V-Optimal) have been proposed in the past for determining bucket boundaries which provide accurate estimations. However, while search strategies for optimal bucket boundaries are rather sophisticated, no much attention has been paid for estimating queries inside buckets and all of the above techniques adopt naive methods for such an estimation. This paper focuses on the problem of improving the estimation inside a bucket once its boundaries have been fixed. The proposed technique is based on the addition, to each bucket, of 32-bit additional information (organized into a 4-level tree index), storing approximate cumulative frequencies at 7 internal intervals of the bucket. Both theoretical analysis and experimental results show that, among a number of alternative ways to organize the additional information, the 4-level tree index provides the best frequency estimation inside a bucket. The index is later added to two well-known histograms, MaxDiff and V-Optimal, obtaining the non-obvious result that despite the spatial cost of 4LT which reduces the number of allowed buckets once the storage space has been fixed, the original methods are strongly improved in terms of accuracy.


title: Large-scale lattice Boltzmann simulations of complex fluids: advances through the advent of computational grids

abstract: During the last two years the RealityGrid project has allowed us to be one of the few scientific groups involved in the development of computational grids. Since smoothly working production grids are not yet available, we have been able to substantially influence the direction of software development and grid deployment within the project. In this paper we review our results from large scale three-dimensional lattice Boltzmann simulations performed over the last two years. We describe how the proactive use of computational steering and advanced job migration and visualization techniques enabled us to do our scientific work more efficiently. The projects reported on in this paper are studies of complex fluid flows under shear or in porous media, as well as large-scale parameter searches, and studies of the self-organisation of liquid cubic mesophases. Movies are available at http://www.ica1.uni-stuttgart.de/~jens/pub/05/05-PhilTransReview.html

categories: cs.DC cond-mat.other cond-mat.soft physics.flu-dyn


title: Algebraic Properties for Selector Functions

abstract: The nondeterministic advice complexity of the P-selective sets is known to be exactly linear. Regarding the deterministic advice complexity of the P-selective sets--i.e., the amount of Karp--Lipton advice needed for polynomial-time machines to recognize them in general--the best current upper bound is quadratic [Ko, 1983] and the best current lower bound is linear [Hemaspaandra and Torenvliet, 1996]. We prove that every associatively P-selective set is commutatively, associatively P-selective. Using this, we establish an algebraic sufficient condition for the P-selective sets to have a linear upper bound (which thus would match the existing lower bound) on their deterministic advice complexity: If all P-selective sets are associatively P-selective then the deterministic advice complexity of the P-selective sets is linear. The weakest previously known sufficient condition was P=NP. We also establish related results for algebraic properties of, and advice complexity of, the nondeterministically selective sets.


abstract: Existing quantum key distribution schemes need the support of classical authentication scheme to ensure security. This is a conceptual drawback of quantum cryptography. It is pointed out that quantum cryptosystem does not need any support of classical cryptosystem to ensure security. No-cloning principal can alone provide security in communication. Even no-cloning principle itself can help to authenticate each bit of information. It implies that quantum password need not to be a secret password.


title: Effectively Open Real Functions

abstract: A function f is continuous iff the PRE-image f^{-1}[V] of any open set V is open again. Dual to this topological property, f is called OPEN iff the IMAGE f[U] of any open set U is open again. Several classical Open Mapping Theorems in Analysis provide a variety of sufficient conditions for openness. By the Main Theorem of Recursive Analysis, computable real functions are necessarily continuous. In fact they admit a well-known characterization in terms of the mapping V+->f^{-1}[V] being EFFECTIVE: Given a list of open rational balls exhausting V, a Turing Machine can generate a corresponding list for f^{-1}[V]. Analogously, EFFECTIVE OPENNESS requires the mapping U+->f[U] on open real subsets to be effective. By effectivizing classical Open Mapping Theorems as well as from application of Tarski's Quantifier Elimination, the present work reveals several rich classes of functions to be effectively open.


title: A Logic for Non-Monotone Inductive Definitions

abstract: Well-known principles of induction include monotone induction and different sorts of non-monotone induction such as inflationary induction, induction over well-founded sets and iterated induction. In this work, we define a logic formalizing induction over well-founded sets and monotone and iterated induction. Just as the principle of positive induction has been formalized in FO(LFP), and the principle of inflationary induction has been formalized in FO(IFP), this paper formalizes the principle of iterated induction in a new logic for Non-Monotone Inductive Definitions (ID-logic). The semantics of the logic is strongly influenced by the well-founded semantics of logic programming. Our main result concerns the modularity properties of inductive definitions in ID-logic. Specifically, we formulate conditions under which a simultaneous definition $\D$ of several relations is logically equivalent to a conjunction of smaller definitions $\D_1 \land ... \land \D_n$ with disjoint sets of defined predicates. The difficulty of the result comes from the fact that predicates $P_i$ and $P_j$ defined in $\D_i$ and $\D_j$, respectively, may be mutually connected by simultaneous induction. Since logic programming and abductive logic programming under well-founded semantics are proper fragments of our logic, our modularity results are applicable there as well.


title: On the Sensitivity of Cyclically-Invariant Boolean Functions

abstract: In this paper we construct a cyclically invariant Boolean function whose sensitivity is $\Theta(n^{1/3})$. This result answers two previously published questions. Tur\'an (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity $\Omega(\sqrt{n})$. Kenyon and Kutin (2004) asked whether for a ``nice'' function the product of 0-sensitivity and 1-sensitivity is $\Omega(n)$. Our function answers both questions in the negative. We also prove that for minterm-transitive functions (a natural class of Boolean functions including our example) the sensitivity is $\Omega(n^{1/3})$. Hence for this class of functions sensitivity and block sensitivity are polynomially related.


title: Enforcing Bulk Mail Classification

abstract: Spam costs US corporations upwards of $8.9 billion a year, and comprises as much as 40% of all email received. Solutions exist to reduce the amount of spam seen by end users, but cannot withstand sophisticated attacks. Worse yet, many will occasionally misclassify and silently drop legitimate email. Spammers take advantage of the near-zero cost of sending email to flood the network, knowing that success even a tiny fraction of the time means a profit. End users, however, have proven unwilling to pay money to send email to friends and family. We show that it is feasible to extend the existing mail system to reduce the amount of unwanted email, without misclassifying email, and without charging well-behaved users. We require that bulk email senders accurately classify each email message they send as an advertisement with an area of interest or else be charged a small negative incentive per message delivered. Recipients are able to filter out email outside their scope of interest, while senders are able to focus their sendings to the appropriate audience.


title: An Empirical Study of MDL Model Selection with Infinite Parametric Complexity

abstract: Parametric complexity is a central concept in MDL model selection. In practice it often turns out to be infinite, even for quite simple models such as the Poisson and Geometric families. In such cases, MDL model selection as based on NML and Bayesian inference based on Jeffreys' prior can not be used. Several ways to resolve this problem have been proposed. We conduct experiments to compare and evaluate their behaviour on small sample sizes. We find interestingly poor behaviour for the plug-in predictive code; a restricted NML model performs quite well but it is questionable if the results validate its theoretical motivation. The Bayesian model with the improper Jeffreys' prior is the most dependable.


title: Estimating Range Queries using Aggregate Data with Integrity Constraints: a Probabilistic Approach

abstract: The problem of recovering (count and sum) range queries over multidimensional data only on the basis of aggregate information on such data is addressed. This problem can be formalized as follows. Suppose that a transformation T producing a summary from a multidimensional data set is used. Now, given a data set D, a summary S=T(D) and a range query r on D, the problem consists of studying r by modelling it as a random variable defined over the sample space of all the data sets D' such that T(D) = S. The study of such a random variable, done by the definition of its probability distribution and the computation of its mean value and variance, represents a well-founded, theoretical probabilistic approach for estimating the query only on the basis of the available information (that is the summary S) without assumptions on original data.


title: Generalized Laplace transformations and integration of hyperbolic systems of linear partial differential equations

abstract: We give a new procedure for generalized factorization and construction of the complete solution of strictly hyperbolic linear partial differential equations or strictly hyperbolic systems of such equations in the plane. This procedure generalizes the classical theory of Laplace transformations of second-order equations in the plane.


title: From truth to computability II

abstract: Computability logic is a formal theory of computational tasks and resources. Formulas in it represent interactive computational problems, and "truth" is understood as algorithmic solvability. Interactive computational problems, in turn, are defined as a certain sort games between a machine and its environment, with logical operators standing for operations on such games. Within the ambitious program of finding axiomatizations for incrementally rich fragments of this semantically introduced logic, the earlier article "From truth to computability I" proved soundness and completeness for system CL3, whose language has the so called parallel connectives (including negation), choice connectives, choice quantifiers, and blind quantifiers. The present paper extends that result to the significantly more expressive system CL4 with the same collection of logical operators. What makes CL4 expressive is the presence of two sorts of atoms in its language: elementary atoms, representing elementary computational problems (i.e. predicates, i.e. problems of zero degree of interactivity), and general atoms, representing arbitrary computational problems. CL4 conservatively extends CL3, with the latter being nothing but the general-atom-free fragment of the former. Removing the blind (classical) group of quantifiers from the language of CL4 is shown to yield a decidable logic despite the fact that the latter is still first-order. A comprehensive online source on computability logic can be found at http://www.cis.upenn.edu/~giorgi/cl.html


title: On Partially Additive Kleene Algebras

abstract: We define the notion of a partially additive Kleene algebra, which is a Kleene algebra where the + operation need only be partially defined. These structures formalize a number of examples that cannot be handled directly by Kleene algebras. We relate partially additive Kleene algebras to existing algebraic structures, by exhibiting categorical connections with Kleene algebras, partially additive categories, and closed semirings.


title: Playful, streamlike computation

abstract: We offer a short tour into the interactive interpretation of sequential programs. We emphasize streamlike computation -- that is, computation of successive bits of information upon request. The core of the approach surveyed here dates back to the work of Berry and the author on sequential algorithms on concrete data structures in the late seventies, culminating in the design of the programming language CDS, in which the semantics of programs of any type can be explored interactively. Around one decade later, two major insights of Cartwright and Felleisen on one hand, and of Lamarche on the other hand gave new, decisive impulses to the study of sequentiality. Cartwright and Felleisen observed that sequential algorithms give a direct semantics to control operators like \"call-cc\" and proposed to include explicit errors both in the syntax and in the semantics of the language PCF. Lamarche (unpublished) connected sequential algorithms to linear logic and games. The successful program of games semantics has spanned over the nineties until now, starting with syntax-independent characterizations of the term model of PCF by Abramsky, Jagadeesan, and Malacaria on one hand, and by Hyland and Ong on the other hand.


title: Symmetry and interactivity in Programming

abstract: We recall some of the early occurrences of the notions of interactivity and symmetry in the operational and denotational semantics of programming languages. We suggest some connections with ludics.


title: Introduction to linear logic and ludics, part I

abstract: This two-parts paper offers a survey of linear logic and ludics, which were introduced by Girard in 1986 and 2001, respectively. Both theories revisit mathematical logic from first principles, with inspiration from and applications to computer science. The present part I covers an introduction to the connectives and proof rules of linear logic, to its decidability properties, and to its models. Part II will deal with proof nets, a graph-like representation of proofs which is one of the major innovations of linear logic, and will present an introduction to ludics.


title: Enabling Agents to Dynamically Select Protocols for Interactions

abstract: in this paper we describe a method which allows agents to dynamically select protocols and roles when they need to execute collaborative tasks


title: Oligopolistic Competition in an Evolutionary Environment: a Computer Simulation

abstract: The following notes contain a computer simulation concerning effective competition in an evolutionary environment. The scope is to underline the existence of a side effect pertaining to the competitive processes: the tendency toward an excess of supply by producers which operate in a strongly competitive situation. A set of four oligopolistic firms will be employed in the formal reconstruction. The simulation will operate following the Edmond Malinvaud "short side" approach, as far as the price adjustment is concerned, and the sequential Hicksian "weeks" structure with regard of the temporal characterization. The content of the present paper ought to be considered as a development of the writing: Michele Tucci, Evolution and Gravitation: a Computer Simulation of a Non-Walrasian Equilibrium Model, published with the E-print Archives at arXiv.com (section: Computer Science, registration number: cs.CY/0209017). In such a paper there can be found some preliminary considerations regarding the comparison between the evolutionary and the gravitational paradigms and the evaluation of approaches belonging to rival schools of economic thought.


title: Data Tastes Better Seasoned: Introducing the ASH Family of Hashing Algorithms

abstract: Over the recent months it has become clear that the current generation of cryptographic hashing algorithms are insufficient to meet future needs. The ASH family of algorithms provides modifications to the existing SHA-2 family. These modifications are designed with two main goals: 1) Providing increased collision resistance. 2) Increasing mitigation of security risks post-collision. The unique public/private sections and salt/pepper design elements provide increased flexibility for a broad range of applications. The ASH family is a new generation of cryptographic hashing algorithms.


title: Introduction to linear logic and ludics, part II

abstract: This paper is the second part of an introduction to linear logic and ludics, both due to Girard. It is devoted to proof nets, in the limited, yet central, framework of multiplicative linear logic and to ludics, which has been recently developped in an aim of further unveiling the fundamental interactive nature of computation and logic. We hope to offer a few computer science insights into this new theory.


title: Split-2 Bisimilarity has a Finite Axiomatization over CCS with<br> Hennessy's Merge

abstract: This note shows that split-2 bisimulation equivalence (also known as timed equivalence) affords a finite equational axiomatization over the process algebra obtained by adding an auxiliary operation proposed by Hennessy in 1981 to the recursion, relabelling and restriction free fragment of Milner's Calculus of Communicating Systems. Thus the addition of a single binary operation, viz. Hennessy's merge, is sufficient for the finite equational axiomatization of parallel composition modulo this non-interleaving equivalence. This result is in sharp contrast to a theorem previously obtained by the same authors to the effect that the same language is not finitely based modulo bisimulation equivalence.


title: Two Iterative Algorithms for Solving Systems of Simultaneous Linear Algebraic Equations with Real Matrices of Coefficients

abstract: The paper describes two iterative algorithms for solving general systems of M simultaneous linear algebraic equations (SLAE) with real matrices of coefficients. The system can be determined, underdetermined, and overdetermined. Linearly dependent equations are also allowed. Both algorithms use the method of Lagrange multipliers to transform the original SLAE into a positively determined function F of real original variables X(i) (i=1,...,N) and Lagrange multipliers Lambda(i) (i=1,...,M). Function F is differentiated with respect to variables X(i) and the obtained relationships are used to express F in terms of Lagrange multipliers Lambda(i). The obtained function is minimized with respect to variables Lambda(i) with the help of one of two the following minimization techniques: (1) relaxation method or (2) method of conjugate gradients by Fletcher and Reeves. Numerical examples are given.


title: Maintaining Consistency of Data on the Web

abstract: Increasingly more data is becoming available on the Web, estimates speaking of 1 billion documents in 2002. Most of the documents are Web pages whose data is considered to be in XML format, expecting it to eventually replace HTML. A common problem in designing and maintaining a Web site is that data on a Web page often replicates or derives from other data, the so-called base data, that is usually not contained in the deriving or replicating page. Consequently, replicas and derivations become inconsistent upon modifying base data in a Web page or a relational database. For example, after assigning a thesis to a student and modifying the Web page that describes it in detail, the thesis is still incorrectly contained in the list of offered thesis, missing in the list of ongoing thesis, and missing in the advisor's teaching record. The thesis presents a solution by proposing a combined approach that provides for maintaining consistency of data in Web pages that (i) replicate data in relational databases, or (ii) replicate or derive from data in Web pages. Upon modifying base data, the modification is immediately pushed to affected Web pages. There, maintenance is performed incrementally by only modifying the affected part of the page instead of re-generating the whole page from scratch.


title: Proving Correctness and Completeness of Normal Programs - a Declarative Approach

abstract: We advocate a declarative approach to proving properties of logic programs. Total correctness can be separated into correctness, completeness and clean termination; the latter includes non-floundering. Only clean termination depends on the operational semantics, in particular on the selection rule. We show how to deal with correctness and completeness in a declarative way, treating programs only from the logical point of view. Specifications used in this approach are interpretations (or theories). We point out that specifications for correctness may differ from those for completeness, as usually there are answers which are neither considered erroneous nor required to be computed. We present proof methods for correctness and completeness for definite programs and generalize them to normal programs. For normal programs we use the 3-valued completion semantics; this is a standard semantics corresponding to negation as finite failure. The proof methods employ solely the classical 2-valued logic. We use a 2-valued characterization of the 3-valued completion semantics which may be of separate interest. The presented methods are compared with an approach based on operational semantics. We also employ the ideas of this work to generalize a known method of proving termination of normal programs.


title: Augmented Segmentation and Visualization for Presentation Videos

abstract: We investigate methods of segmenting, visualizing, and indexing presentation videos by separately considering audio and visual data. The audio track is segmented by speaker, and augmented with key phrases which are extracted using an Automatic Speech Recognizer (ASR). The video track is segmented by visual dissimilarities and augmented by representative key frames. An interactive user interface combines a visual representation of audio, video, text, and key frames, and allows the user to navigate a presentation video. We also explore clustering and labeling of speaker data and present preliminary results.


title: Improved Approximation Algorithms for Geometric Set Cover

abstract: Given a collection S of subsets of some set U, and M a subset of U, the set cover problem is to find the smallest subcollection C of S such that M is a subset of the union of the sets in C. While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually U = R^d. Extending prior results, we show that approximation algorithms with provable performance exist, under a certain general condition: that for a random subset R of S and function f(), there is a decomposition of the portion of U not covered by R into an expected f(|R|) regions, each region of a particular simple form. We show that under this condition, a cover of size O(f(|C|)) can be found. Our proof involves the generalization of shallow cuttings to more general geometric situations. We obtain constant-factor approximation algorithms for covering by unit cubes in R^3, for guarding a one-dimensional terrain, and for covering by similar-sized fat triangles in R^2. We also obtain improved approximation guarantees for fat triangles, of arbitrary size, and for a class of fat objects.


title: Thermodynamics of used punched tape: A weak and a strong equivalence principle

abstract: We study the repeated use of a monotonic recording medium--such as punched tape or photographic plate--where marks can be added at any time but never erased. (For practical purposes, also the electromagnetic "ether" falls into this class.) Our emphasis is on the case where the successive users act independently and selfishly, but not maliciously; typically, the "first user" would be a blind natural process tending to degrade the recording medium, and the "second user" a human trying to make the most of whatever capacity is left. To what extent is a length of used tape "equivalent"--for information transmission purposes--to a shorter length of virgin tape? Can we characterize a piece of used tape by an appropriate "effective length" and forget all other details? We identify two equivalence principles. The weak principle is exact, but only holds for a sequence of infinitesimal usage increments. The strong principle holds for any amount of incremental usage, but is only approximate; nonetheless, it is quite accurate even in the worst case and is virtually exact over most of the range--becoming exact in the limit of heavily used tape. The fact that strong equivalence does not hold exactly, but then it does almost exactly, comes as a bit of a surprise.


title: Impact of Channel Estimation Errors on Multiuser Detection via the Replica Method

abstract: For practical wireless DS-CDMA systems, channel estimation is imperfect due to noise and interference. In this paper, the impact of channel estimation errors on multiuser detection (MUD) is analyzed under the framework of the replica method. System performance is obtained in the large system limit for optimal MUD, linear MUD and turbo MUD, and is validated by numerical results for finite systems.


title: Low Complexity Joint Iterative Equalization and Multiuser Detection in Dispersive DS-CDMA Channels

abstract: Communications in dispersive direct-sequence code-division multiple-access (DS-CDMA) channels suffer from intersymbol and multiple-access interference, which can significantly impair performance. Joint maximum \textit{a posteriori} probability (MAP) equalization and multiuser detection with error control decoding can be used to mitigate this interference and to achieve the optimal bit error rate. Unfortunately, such optimal detection typically requires prohibitive computational complexity. This problem is addressed in this paper through the development of a reduced state trellis search detection algorithm, based on decision feedback from channel decoders. The performance of this algorithm is analyzed in the large-system limit. This analysis and simulations show that this low-complexity algorithm can obtain near-optimal performance under moderate signal-to-noise ratio and attains larger system load capacity than parallel interference cancellation.


title: Performance Evaluation of Impulse Radio UWB Systems with Pulse-Based Polarity Randomization

abstract: In this paper, the performance of a binary phase shift keyed random time-hopping impulse radio system with pulse-based polarity randomization is analyzed. Transmission over frequency-selective channels is considered and the effects of inter-frame interference and multiple access interference on the performance of a generic Rake receiver are investigated for both synchronous and asynchronous systems. Closed form (approximate) expressions for the probability of error that are valid for various Rake combining schemes are derived. The asynchronous system is modelled as a chip-synchronous system with uniformly distributed timing jitter for the transmitted pulses of interfering users. This model allows the analytical technique developed for the synchronous case to be extended to the asynchronous case. An approximate closed-form expression for the probability of bit error, expressed in terms of the autocorrelation function of the transmitted pulse, is derived for the asynchronous case. Then, transmission over an additive white Gaussian noise channel is studied as a special case, and the effects of multiple-access interference is investigated for both synchronous and asynchronous systems. The analysis shows that the chip-synchronous assumption can result in over-estimating the error probability, and the degree of over-estimation mainly depends on the autocorrelation function of the ultra-wideband pulse and the signal-to-interference-plus-noise-ratio of the system. Simulations studies support the approximate analysis.


title: Energy-Efficient Joint Estimation in Sensor Networks: Analog vs. Digital

abstract: Sensor networks in which energy is a limited resource so that energy consumption must be minimized for the intended application are considered. In this context, an energy-efficient method for the joint estimation of an unknown analog source under a given distortion constraint is proposed. The approach is purely analog, in which each sensor simply amplifies and forwards the noise-corrupted analog bservation to the fusion center for joint estimation. The total transmission power across all the sensor nodes is minimized while satisfying a distortion requirement on the joint estimate. The energy efficiency of this analog approach is compared with previously proposed digital approaches with and without coding. It is shown in our simulation that the analog approach is more energy-efficient than the digital system without coding, and in some cases outperforms the digital system with optimal coding.


title: On the Capacity of Multiple Antenna Systems in Rician Fading

abstract: The effect of Rician-ness on the capacity of multiple antenna systems is investigated under the assumption that channel state information (CSI) is available only at the receiver. The average-power-constrained capacity of such systems is considered under two different assumptions on the knowledge about the fading available at the transmitter: the case in which the transmitter has no knowledge of fading at all, and the case in which the transmitter has knowledge of the distribution of the fading process but not the instantaneous CSI. The exact capacity is given for the former case while capacity bounds are derived for the latter case. A new signalling scheme is also proposed for the latter case and it is shown that by exploiting the knowledge of Rician-ness at the transmitter via this signalling scheme, significant capacity gain can be achieved. The derived capacity bounds are evaluated explicitly to provide numerical results in some representative situations.


title: Stochastic Differential Games in a Non-Markovian Setting

abstract: Stochastic differential games are considered in a non-Markovian setting. Typically, in stochastic differential games the modulating process of the diffusion equation describing the state flow is taken to be Markovian. Then Nash equilibria or other types of solution such as Pareto equilibria are constructed using Hamilton-Jacobi-Bellman (HJB) equations. But in a non-Markovian setting the HJB method is not applicable. To examine the non-Markovian case, this paper considers the situation in which the modulating process is a fractional Brownian motion. Fractional noise calculus is used for such models to find the Nash equilibria explicitly. Although fractional Brownian motion is taken as the modulating process because of its versatility in modeling in the fields of finance and networks, the approach in this paper has the merit of being applicable to more general Gaussian stochastic differential games with only slight conceptual modifications. This work has applications in finance to stock price modeling which incorporates the effect of institutional investors, and to stochastic differential portfolio games in markets in which the stock prices follow diffusions modulated with fractional Brownian motion.


title: Relational Algebra as non-Distributive Lattice

abstract: We reduce the set of classic relational algebra operators to two binary operations: natural join and generalized union. We further demonstrate that this set of operators is relationally complete and honors lattice axioms.


title: Arbitrage in Fractal Modulated Markets When the Volatility is Stochastic

abstract: In this paper an arbitrage strategy is constructed for the modified Black-Scholes model driven by fractional Brownian motion or by a time changed fractional Brownian motion, when the volatility is stochastic. This latter property allows the heavy tailedness of the log returns of the stock prices to be also accounted for in addition to the long range dependence introduced by the fractional Brownian motion. Work has been done previously on this problem for the case with constant `volatility' and without a time change; here these results are extended to the case of stochastic volatility models when the modulator is fractional Brownian motion or a time change of it. (Volatility in fractional Black-Scholes models does not carry the same meaning as in the classic Black-Scholes framework, which is made clear in the text.) Since fractional Brownian motion is not a semi-martingale, the Black-Scholes differential equation is not well-defined sense for arbitrary predictable volatility processes. However, it is shown here that any almost surely continuous and adapted process having zero quadratic variation can act as an integrator over functions of the integrator and over the family of continuous adapted semi-martingales. Moreover it is shown that the integral also has zero quadratic variation, and therefore that the integral itself can be an integrator. This property of the integral is crucial in developing the arbitrage strategy. Since fractional Brownian motion and a time change of fractional Brownian motion have zero quadratic variation, these results are applicable to these cases in particular. The appropriateness of fractional Brownian motion as a means of modeling stock price returns is discussed as well.


title: Consistency Problems for Jump-Diffusion Models

abstract: In this paper consistency problems for multi-factor jump-diffusion models, where the jump parts follow multivariate point processes are examined. First the gap between jump-diffusion models and generalized Heath-Jarrow-Morton (HJM) models is bridged. By applying the drift condition for a generalized arbitrage-free HJM model, the consistency condition for jump-diffusion models is derived. Then we consider a case in which the forward rate curve has a separable structure, and obtain a specific version of the general consistency condition. In particular, a necessary and sufficient condition for a jump-diffusion model to be affine is provided. Finally the Nelson-Siegel type of forward curve structures is discussed. It is demonstrated that under regularity condition, there exists no jump-diffusion model consistent with the Nelson-Siegel curves.


title: A Large Deviations Approach to Sensor Scheduling for Detection of Correlated Random Fields

abstract: The problem of scheduling sensor transmissions for the detection of correlated random fields using spatially deployed sensors is considered. Using the large deviations principle, a closed-form expression for the error exponent of the miss probability is given as a function of the sensor spacing and signal-to-noise ratio (SNR). It is shown that the error exponent has a distinct characteristic: at high SNR, the error exponent is monotonically increasing with respect to sensor spacing, while at low SNR there is an optimal spacing for scheduled sensors.


title: Concavity of the auxiliary function appearing in quantum reliability function an classical-quantum channels

abstract: Concavity of the auxiliary function which appears in the random coding exponent as the lower bound of the quantum reliability function for general quantum states is proven for s between 0 and 1.


title: Estimation of the Number of Sources in Unbalanced Arrays via Information Theoretic Criteria

abstract: Estimating the number of sources impinging on an array of sensors is a well known and well investigated problem. A common approach for solving this problem is to use an information theoretic criterion, such as Minimum Description Length (MDL) or the Akaike Information Criterion (AIC). The MDL estimator is known to be a consistent estimator, robust against deviations from the Gaussian assumption, and non-robust against deviations from the point source and/or temporally or spatially white additive noise assumptions. Over the years several alternative estimation algorithms have been proposed and tested. Usually, these algorithms are shown, using computer simulations, to have improved performance over the MDL estimator, and to be robust against deviations from the assumed spatial model. Nevertheless, these robust algorithms have high computational complexity, requiring several multi-dimensional searches. In this paper, motivated by real life problems, a systematic approach toward the problem of robust estimation of the number of sources using information theoretic criteria is taken. An MDL type estimator that is robust against deviation from assumption of equal noise level across the array is studied. The consistency of this estimator, even when deviations from the equal noise level assumption occur, is proven. A novel low-complexity implementation method avoiding the need for multi-dimensional searches is presented as well, making this estimator a favorable choice for practical applications.


title: Under-approximation of the Greatest Fixpoint in Real-Time System Verification

abstract: Techniques for the efficient successive under-approximation of the greatest fixpoint in TCTL formulas can be useful in fast refutation of inevitability properties and vacuity checking. We first give an integrated algorithmic framework for both under and over-approximate model-checking. We design the {\em NZF (Non-Zeno Fairness) predicate}, with a greatest fixpoint formulation, as a unified framework for the evaluation of formulas like $\exists\pfrr\eta_1$, $\exists\pfrr\pevt\eta_1$, and $\exists\pevt\pfrr\eta_1$. We then prove the correctness of a new formulation for the characterization of the NZF predicate based on zone search and the least fixpoint evaluation. The new formulation then leads to the design of an evaluation algorithm, with the capability of successive under-approximation, for $\exists\pfrr\eta_1$, $\exists\pfrr\pevt\eta_1$, and $\exists\pevt\pfrr\eta_1$. We then present techniques to efficiently search for the zones and to speed up the under-approximate evaluation of those three formulas. Our experiments show that the techniques have significantly enhanced the verification performance against several benchmarks over exact model-checking.


title: Under-approximation of the Greatest Fixpoints in Real-Time System Verification


title: Optimal and Suboptimal Finger Selection Algorithms for MMSE Rake Receivers in Impulse Radio Ultra-Wideband Systems

abstract: Convex relaxations of the optimal finger selection algorithm are proposed for a minimum mean square error (MMSE) Rake receiver in an impulse radio ultra-wideband system. First, the optimal finger selection problem is formulated as an integer programming problem with a non-convex objective function. Then, the objective function is approximated by a convex function and the integer programming problem is solved by means of constraint relaxation techniques. The proposed algorithms are suboptimal due to the approximate objective function and the constraint relaxation steps. However, they can be used in conjunction with the conventional finger selection algorithm, which is suboptimal on its own since it ignores the correlation between multipath components, to obtain performances reasonably close to that of the optimal scheme that cannot be implemented in practice due to its complexity. The proposed algorithms leverage convexity of the optimization problem formulations, which is the watershed between `easy' and `difficult' optimization problems.


title: On The Tradeoff Between Two Types of Processing Gain

abstract: One of the features characterizing almost every multiple access (MA) communication system is the processing gain. Through the use of spreading sequences, the processing gain of Random CDMA systems (RCDMA), is devoted to both bandwidth expansion and orthogonalization of the signals transmitted by different users. Another type of multiple access system is Impulse Radio (IR). In many aspects, IR systems are similar to time division multiple access (TDMA) systems, and the processing gain of IR systems represents the ratio between the actual transmission time and the total time between two consecutive ransmissions (on-plus-off to on ratio). While CDMA systems, which constantly excite the channel, rely on spreading sequences to orthogonalize the signals transmitted by different users, IR systems transmit a series of short pulses and the orthogonalization between the signals transmitted by different users is achieved by the fact that most of the pulses do not collide with each other at the receiver. In this paper, a general class of MA communication systems that use both types of processing gain is presented, and both IR and RCDMA systems are demonstrated to be two special cases of this more general class of systems. The bit error rate (BER) of several receivers as a function of the ratio between the two types of processing gain is analyzed and compared under the constraint that the total processing gain of the system is large and fixed. It is demonstrated that in non inter-symbol interference (ISI) channels there is no tradeoff between the two types of processing gain. However, in ISI channels a tradeoff between the two types of processing gain exists. In addition, the sub-optimality of RCDMA systems in frequency selective channels is established.


title: Bandit Problems with Side Observations

abstract: An extension of the traditional two-armed bandit problem is considered, in which the decision maker has access to some side information before deciding which arm to pull. At each time t, before making a selection, the decision maker is able to observe a random variable X_t that provides some information on the rewards to be obtained. The focus is on finding uniformly good rules (that minimize the growth rate of the inferior sampling time) and on quantifying how much the additional information helps. Various settings are considered and for each setting, lower bounds on the achievable inferior sampling time are developed and asymptotically optimal adaptive schemes achieving these lower bounds are constructed.


title: A Non-Cooperative Power Control Game for Multi-Carrier CDMA Systems

abstract: In this work, a non-cooperative power control game for multi-carrier CDMA systems is proposed. In the proposed game, each user needs to decide how much power to transmit over each carrier to maximize its overall utility. The utility function considered here measures the number of reliable bits transmitted per joule of energy consumed. It is shown that the user's utility is maximized when the user transmits only on the carrier with the best "effective channel". The existence and uniqueness of Nash equilibrium for the proposed game are investigated and the properties of equilibrium are studied. Also, an iterative and distributed algorithm for reaching the equilibrium (if it exists) is presented. It is shown that the proposed approach results in a significant improvement in the total utility achieved at equilibrium compared to the case in which each user maximizes its utility over each carrier independently.


title: Harmonic Analysis

abstract: This paper describes a method of calculating the transforms, currently obtained via Fourier and reverse Fourier transforms. The method allows calculating efficiently the transforms of a signal having an arbitrary dimension of the digital representation by reducing the transform to a vector-to-circulant matrix multiplying. There is a connection between harmonic equations in rectangular and polar coordinate systems. The connection established here and used to create a very robust iterative algorithm for a conformal mapping calculation. There is also suggested a new ratio (and an efficient way of computing it) of two oscillative signals.


title: The Noncoherent Rician Fading Channel -- Part I : Structure of the Capacity-Achieving Input

abstract: Transmission of information over a discrete-time memoryless Rician fading channel is considered where neither the receiver nor the transmitter knows the fading coefficients. First the structure of the capacity-achieving input signals is investigated when the input is constrained to have limited peakedness by imposing either a fourth moment or a peak constraint. When the input is subject to second and fourth moment limitations, it is shown that the capacity-achieving input amplitude distribution is discrete with a finite number of mass points in the low-power regime. A similar discrete structure for the optimal amplitude is proven over the entire SNR range when there is only a peak power constraint. The Rician fading with phase-noise channel model, where there is phase uncertainty in the specular component, is analyzed. For this model it is shown that, with only an average power constraint, the capacity-achieving input amplitude is discrete with a finite number of levels. For the classical average power limited Rician fading channel, it is proven that the optimal input amplitude distribution has bounded support.


title: The Noncoherent Rician Fading Channel -- Part II : Spectral Efficiency in the Low-Power Regime

abstract: Transmission of information over a discrete-time memoryless Rician fading channel is considered where neither the receiver nor the transmitter knows the fading coefficients. The spectral-efficiency/bit-energy tradeoff in the low-power regime is examined when the input has limited peakedness. It is shown that if a fourth moment input constraint is imposed or the input peak-to-average power ratio is limited, then in contrast to the behavior observed in average power limited channels, the minimum bit energy is not always achieved at zero spectral efficiency. The low-power performance is also characterized when there is a fixed peak limit that does not vary with the average power. A new signaling scheme that overlays phase-shift keying on on-off keying is proposed and shown to be optimally efficient in the low-power regime.


title: Learning to automatically detect features for mobile robots using second-order Hidden Markov Models

abstract: In this paper, we propose a new method based on Hidden Markov Models to interpret temporal sequences of sensor data from mobile robots to automatically detect features. Hidden Markov Models have been used for a long time in pattern recognition, especially in speech recognition. Their main advantages over other methods (such as neural networks) are their ability to model noisy temporal signals of variable length. We show in this paper that this approach is well suited for interpretation of temporal sequences of mobile-robot sensor data. We present two distinct experiments and results: the first one in an indoor environment where a mobile robot learns to detect features like open doors or T-intersections, the second one in an outdoor environment where a different mobile robot has to identify situations like climbing a hill or crossing a rock.


title: A Statistical Theory of Chord under Churn

abstract: Most earlier studies of Distributed Hash Tables (DHTs) under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation-based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different 'types' and the implications this will have for the functioning of DHTs in general.


title: Extending Design by Contract for Aspect-Oriented Programming

abstract: Design by Contract (DbC) and runtime enforcement of program assertions enables the construction of more robust software. It also enables the assignment of blame in error reporting. Unfortunately, there is no support for runtime contract enforcement and blame assignment for Aspect-Oriented Programming (AOP). Extending DbC to also cover aspects brings forward a plethora of issues related to the correct order of assertion validation. We show that there is no generally correct execution sequence of object assertions and aspect assertions. A further classification of aspects as agnostic, obedient, or rebellious defines the order of assertion validation that needs to be followed. We describe the application of this classification in a prototyped DbC tool for AOP named Cona, where aspects are used for implementing contracts, and contracts are used for enforcing assertions on aspects.


title: Capacity Regions and Optimal Power Allocation for Groupwise Multiuser Detection

abstract: In this paper, optimal power allocation and capacity regions are derived for GSIC (groupwise successive interference cancellation) systems operating in multipath fading channels, under imperfect channel estimation conditions. It is shown that the impact of channel estimation errors on the system capacity is two-fold: it affects the receivers' performance within a group of users, as well as the cancellation performance (through cancellation errors). An iterative power allocation algorithm is derived, based on which it can be shown that the total required received power is minimized when the groups are ordered according to their cancellation errors, and the first detected group has the smallest cancellation error. Performace/complexity tradeoff issues are also discussed by directly comparing the system capacity for different implementations: GSIC with linear minimum-mean-square error (LMMSE) receivers within the detection groups, GSIC with matched filter receivers, multicode LMMSE systems, and simple all matched filter receivers systems.


title: Inferring knowledge from a large semantic network

abstract: In this paper, we present a rich semantic network based on a differential analysis. We then detail implemented measures that take into account common and differential features between words. In a last section, we describe some industrial applications.


title: Optimal Union-Find in Constraint Handling Rules

abstract: Constraint Handling Rules (CHR) is a committed-choice rule-based language that was originally intended for writing constraint solvers. In this paper we show that it is also possible to write the classic union-find algorithm and variants in CHR. The programs neither compromise in declarativeness nor efficiency. We study the time complexity of our programs: they match the almost-linear complexity of the best known imperative implementations. This fact is illustrated with experimental results.


title: Efficient Computation of the Characteristic Polynomial

abstract: This article deals with the computation of the characteristic polynomial of dense matrices over small finite fields and over the integers. We first present two algorithms for the finite fields: one is based on Krylov iterates and Gaussian elimination. We compare it to an improvement of the second algorithm of Keller-Gehrig. Then we show that a generalization of Keller-Gehrig's third algorithm could improve both complexity and computational time. We use these results as a basis for the computation of the characteristic polynomial of integer matrices. We first use early termination and Chinese remaindering for dense matrices. Then a probabilistic approach, based on integer minimal polynomial and Hensel factorization, is particularly well suited to sparse and/or structured matrices.


title: Simple extractors via constructions of cryptographic pseudo-random generators

abstract: Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-random generators from one-way permutations (the Blum-Micali-Yao approach) can be used for building extractors as well. Using this new technique we build extractors that do not use designs and polynomial-based error-correcting codes and that are very simple and efficient. For example, one extractor produces each output bit separately in $O(\log^2 n)$ time. These extractors work for weak sources with min entropy $\lambda n$, for arbitrary constant $\lambda > 0$, have seed length $O(\log^2 n)$, and their output length is $\approx n^{\lambda/3}$.


title: Geometric Complexity III: on deciding positivity of Littlewood-Richardson coefficients

abstract: We point out that the remarkable Knutson and Tao Saturation Theorem and polynomial time algorithms for LP have together an important and immediate consequence in Geometric Complexity Theory. The problem of deciding positivity of Littlewood-Richardson coefficients for GLn(C) belongs to P. Furthermore, the algorithm is strongly polynomial. The main goal of this article is to explain the significance of this result in the context of Geometric Complexity Theory. Furthermore, it is also conjectured that an analogous result holds for arbitrary symmetrizable Kac-Moody algebras.


title: Ontology-Based Users & Requests Clustering in Customer Service Management System

abstract: Customer Service Management is one of major business activities to better serve company customers through the introduction of reliable processes and procedures. Today this kind of activities is implemented through e-services to directly involve customers into business processes. Traditionally Customer Service Management involves application of data mining techniques to discover usage patterns from the company knowledge memory. Hence grouping of customers/requests to clusters is one of major technique to improve the level of company customization. The goal of this paper is to present an efficient for implementation approach for clustering users and their requests. The approach uses ontology as knowledge representation model to improve the semantic interoperability between units of the company and customers. Some fragments of the approach tested in an industrial company are also presented in the paper.


title: Multi-document Biography Summarization

abstract: In this paper we describe a biography summarization system using sentence classification and ideas from information retrieval. Although the individual techniques are not new, assembling and applying them to generate multi-document biographies is new. Our system was evaluated in DUC2004. It is among the top performers in task 5-short summaries focused by person questions.


title: Data Mining for Actionable Knowledge: A Survey

abstract: The data mining process consists of a series of steps ranging from data cleaning, data selection and transformation, to pattern evaluation and visualization. One of the central problems in data mining is to make the mined patterns or knowledge actionable. Here, the term actionable refers to the mined patterns suggest concrete and profitable actions to the decision-maker. That is, the user can do something to bring direct benefits (increase in profits, reduction in cost, improvement in efficiency, etc.) to the organization's advantage. However, there has been written no comprehensive survey available on this topic. The goal of this paper is to fill the void. In this paper, we first present two frameworks for mining actionable knowledge that are inexplicitly adopted by existing research methods. Then we try to situate some of the research on this topic from two different viewpoints: 1) data mining tasks and 2) adopted framework. Finally, we specify issues that are either not addressed or insufficiently studied yet and conclude the paper.


title: An Information Network Overlay Architecture for the NSDL

abstract: We describe the underlying data model and implementation of a new architecture for the National Science Digital Library (NSDL) by the Core Integration Team (CI). The architecture is based on the notion of an information network overlay. This network, implemented as a graph of digital objects in a Fedora repository, allows the representation of multiple information entities and their relationships. The architecture provides the framework for contextualization and reuse of resources, which we argue is essential for the utility of the NSDL as a tool for teaching and learning.