title: Study of Self-Organization Model of Multiple Mobile Robot

abstract: A good organization model of multiple mobile robot should be able to improve the efficiency of the system, reduce the complication of robot interactions, and detract the difficulty of computation. From the sociology aspect of topology, structure and organization, this paper studies the multiple mobile robot organization formation and running mechanism in the dynamic, complicated and unknown environment. It presents and describes in detail a Hierarchical- Web Recursive Organization Model (HWROM) and forming algorithm. It defines the robot society leader; robotic team leader and individual robot as the same structure by the united framework and describes the organization model by the recursive structure. The model uses task-oriented and top-down method to dynamically build and maintain structures and organization. It uses market-based techniques to assign task, form teams and allocate resources in dynamic environment. The model holds several characteristics of self-organization, dynamic, conciseness, commonness and robustness.


title: Optimal Point-to-Point Trajectory Tracking of Redundant Manipulators using Generalized Pattern Search

abstract: Optimal point-to-point trajectory planning for planar redundant manipulator is considered in this study. The main objective is to minimize the sum of the position error of the end-effector at each intermediate point along the trajectory so that the end-effector can track the prescribed trajectory accurately. An algorithm combining Genetic Algorithm and Pattern Search as a Generalized Pattern Search GPS is introduced to design the optimal trajectory. To verify the proposed algorithm, simulations for a 3-D-O-F planar manipulator with different end-effector trajectories have been carried out. A comparison between the Genetic Algorithm and the Generalized Pattern Search shows that The GPS gives excellent tracking performance.


title: Robotics Vision-based Heuristic Reasoning for Underwater Target Tracking and Navigation

abstract: This paper presents a robotics vision-based heuristic reasoning system for underwater target tracking and navigation. This system is introduced to improve the level of automation of underwater Remote Operated Vehicles (ROVs) operations. A prototype which combines computer vision with an underwater robotics system is successfully designed and developed to perform target tracking and intelligent navigation. ...


title: New Intelligent Transmission Concept for Hybrid Mobile Robot Speed Control

abstract: This paper presents a new concept of a mobile robot speed control by using two degree of freedom gear transmission. The developed intelligent speed controller utilizes a gear box which comprises of epicyclic gear train with two inputs, one coupled with the engine shaft and another with the shaft of a variable speed dc motor. The net output speed is a combination of the two input speeds and is governed by the transmission ratio of the planetary gear train. This new approach eliminates the use of a torque converter which is otherwise an indispensable part of all available automatic transmissions, thereby reducing the power loss that occurs in the box during the fluid coupling. By gradually varying the speed of the dc motor a stepless transmission has been achieved. The other advantages of the developed controller are pulling over and reversing the vehicle, implemented by intelligent mixing of the dc motor and engine speeds. This approach eliminates traditional braking system in entire vehicle design. The use of two power sources, IC engine and battery driven DC motor, utilizes the modern idea of hybrid vehicles. The new mobile robot speed controller is capable of driving the vehicle even in extreme case of IC engine failure, for example, due to gas depletion.


title: On the Existence of Universally Decodable Matrices

abstract: Universally decodable matrices (UDMs) can be used for coding purposes when transmitting over slow fading channels. These matrices are parameterized by positive integers $L$ and $N$ and a prime power $q$. The main result of this paper is that the simple condition $L \leq q+1$ is both necessary and sufficient for $(L,N,q)$-UDMs to exist. The existence proof is constructive and yields a coding scheme that is equivalent to a class of codes that was proposed by Rosenbloom and Tsfasman. Our work resolves an open problem posed recently in the literature.


title: Design of Rate-Compatible Serially Concatenated Convolutional Codes

abstract: Recently a powerful class of rate-compatible serially concatenated convolutional codes (SCCCs) have been proposed based on minimizing analytical upper bounds on the error probability in the error floor region. Here this class of codes is further investigated by combining analytical upper bounds with extrinsic information transfer charts analysis. Following this approach, we construct a family of rate-compatible SCCCs with good performance in both the error floor and the waterfall regions over a broad range of code rates.


title: Checkbochs: Use Hardware to Check Software

abstract: In this paper, we present a system called Checkbochs, a machine simulator that checks rules about its guest operating system and applications at the hardware level. The properties to be checked can be implemented as `plugins' in the Checkbochs simulator. Some of the properties that were checked using Checkbochs include null-pointer checks, format-string vulnerabilities, user/kernel pointer checks, and race-conditions. On implementing these checks, we were able to uncover previously-unknown bugs in widely used Linux distributions. We also tested our tools on undergraduate coursework, and found numerous bugs.


title: Fast Enumeration of Combinatorial Objects

abstract: The problem of ranking can be described as follows. We have a set of combinatorial objects $S$, such as, say, the k-subsets of n things, and we can imagine that they have been arranged in some list, say lexicographically, and we want to have a fast method for obtaining the rank of a given object in the list. This problem is widely known in Combinatorial Analysis, Computer Science and Information Theory. Ranking is closely connected with the hashing problem, especially with perfect hashing and with generating of random combinatorial objects. In Information Theory the ranking problem is closely connected with so-called enumerative encoding, which may be described as follows: there is a set of words $S$ and an enumerative code has to one-to-one encode every $s \in S$ by a binary word $code(s)$. The length of the $code(s)$ must be the same for all $s \in S$. Clearly, $|code (s)|\geq \log |S|$. (Here and below $\log x=\log_{2}x)$.) The suggested method allows the exponential growth of the speed of encoding and decoding for all combinatorial problems of enumeration which are considered, including the enumeration of permutations, compositions and others.


title: Instanton analysis of Low-Density-Parity-Check codes in the error-floor regime

abstract: In this paper we develop instanton method introduced in [1], [2], [3] to analyze quantitatively performance of Low-Density-Parity-Check (LDPC) codes decoded iteratively in the so-called error-floor regime. We discuss statistical properties of the numerical instanton-amoeba scheme focusing on detailed analysis and comparison of two regular LDPC codes: Tanner's (155, 64, 20) and Margulis' (672, 336, 16) codes. In the regime of moderate values of the signal-to-noise ratio we critically compare results of the instanton-amoeba evaluations against the standard Monte-Carlo calculations of the Frame-Error-Rate.


abstract: In this paper, we present our proposal to Constraint Functional Logic Programming over Finite Domains (CFLP(FD)) with a lazy functional logic programming language which seamlessly embodies finite domain (FD) constraints. This proposal increases the expressiveness and power of constraint logic programming over finite domains (CLP(FD)) by combining functional and relational notation, curried expressions, higher-order functions, patterns, partial applications, non-determinism, lazy evaluation, logical variables, types, domain variables, constraint composition, and finite domain constraints. We describe the syntax of the language, its type discipline, and its declarative and operational semantics. We also describe TOY(FD), an implementation for CFLPFD(FD), and a comparison of our approach with respect to CLP(FD) from a programming point of view, showing the new features we introduce. And, finally, we show a performance analysis which demonstrates that our implementation is competitive with respect to existing CLP(FD) systems and that clearly outperforms the closer approach to CFLP(FD).


title: Fast Frequent Querying with Lazy Control Flow Compilation

abstract: Control flow compilation is a hybrid between classical WAM compilation and meta-call, limited to the compilation of non-recursive clause bodies. This approach is used successfully for the execution of dynamically generated queries in an inductive logic programming setting (ILP). Control flow compilation reduces compilation times up to an order of magnitude, without slowing down execution. A lazy variant of control flow compilation is also presented. By compiling code by need, it removes the overhead of compiling unreached code (a frequent phenomenon in practical ILP settings), and thus reduces the size of the compiled code. Both dynamic compilation approaches have been implemented and were combined with query packs, an efficient ILP execution mechanism. It turns out that locality of data and code is important for performance. The experiments reported in the paper show that lazy control flow compilation is superior in both artificial and real life settings.


title: A Theory of Routing for Large-Scale Wireless Ad-Hoc Networks

abstract: In this work we develop a new theory to analyse the process of routing in large-scale ad-hoc wireless networks. We use a path integral formulation to examine the properties of the paths generated by different routing strategies in these kinds of networks. Using this theoretical framework, we calculate the statistical distribution of the distances between any source to any destination in the network, hence we are able to deduce a length parameter that is unique for each routing strategy. This parameter, defined as the {\it effective radius}, effectively encodes the routing information required by a node. Analysing the aforementioned statistical distribution for different routing strategies, we obtain a threefold result for practical Large-Scale Wireless Ad-Hoc Networks: 1) We obtain the distribution of the lengths of all the paths in a network for any given routing strategy, 2) We are able to identify "good" routing strategies depending on the evolution of its effective radius as the number of nodes, $N$, increases to infinity, 3) For any routing strategy with finite effective radius, we demonstrate that, in a large-scale network, is equivalent to a random routing strategy and that its transport capacity scales as $\Theta(\sqrt{N})$ bit-meters per second, thus retrieving the scaling law that Gupta and Kumar (2000) obtained as the limit for single-route large-scale wireless networks.


title: Joint universal lossy coding and identification of i.i.d. vector sources

abstract: The problem of joint universal source coding and modeling, addressed by Rissanen in the context of lossless codes, is generalized to fixed-rate lossy coding of continuous-alphabet memoryless sources. We show that, for bounded distortion measures, any compactly parametrized family of i.i.d. real vector sources with absolutely continuous marginals (satisfying appropriate smoothness and Vapnik--Chervonenkis learnability conditions) admits a joint scheme for universal lossy block coding and parameter estimation, and give nonasymptotic estimates of convergence rates for distortion redundancies and variational distances between the active source and the estimated source. We also present explicit examples of parametric sources admitting such joint universal compression and modeling schemes.


title: On Universally Decodable Matrices for Space-Time Coding

abstract: The notion of universally decodable matrices (UDMs) was recently introduced by Tavildar and Viswanath while studying slow fading channels. It turns out that the problem of constructing UDMs is tightly connected to the problem of constructing maximum distance separable (MDS) codes. In this paper, we first study the properties of UDMs in general and then we discuss an explicit construction of a class of UDMs, a construction which can be seen as an extension of Reed-Solomon codes. In fact, we show that this extension is, in a sense to be made more precise later on, unique. Moreover, the structure of this class of UDMs allows us to answer some open conjectures by Tavildar, Viswanath, and Doshi in the positive, and it also allows us to formulate an efficient decoding algorithm for this class of UDMs. It turns out that our construction yields a coding scheme that is essentially equivalent to a class of codes that was proposed by Rosenbloom and Tsfasman. Moreover, we point out connections to so-called repeated-root cyclic codes.


title: Learning by Test-infecting Symmetric Ciphers

abstract: We describe a novel way in which students can learn the cipher systems without much supervision. In this work we focus on learning symmetric ciphers by altering them using the agile development approach. Two agile approaches the eXtreme Programming (XP) and the closely related Test-Driven Development (TDD) are mentioned or discussed. To facilitate this development we experiment with an approach that is based on refactoring, with JUnit serves as the automatic testing framework. In this work we exemplify our learning approach by test-infecting the Vernam cipher, an aged but still widely used stream cipher. One can replace the cipher with another symmetric cipher with the same behavior. Software testing is briefly described. Just-in-time introduction to Object-oriented programming (OOP), exemplified by using JavaTM, is advocated. Refactoring exercises, as argued, are kept strategically simple so that they do not become intensive class redesign exercises. The use of free or open-source tools and frameworks is mentioned.


title: IDBE - An Intelligent Dictionary Based Encoding Algorithm for Text Data Compression for High Speed Data Transmission Over Internet

abstract: Compression algorithms reduce the redundancy in data representation to decrease the storage required for that data. Data compression offers an attractive approach to reducing communication costs by using available bandwidth effectively. Over the last decade there has been an unprecedented explosion in the amount of digital data transmitted via the Internet, representing text, images, video, sound, computer programs, etc. With this trend expected to continue, it makes sense to pursue research on developing algorithms that can most effectively use available network bandwidth by maximally compressing data. This research paper is focused on addressing this problem of lossless compression of text files. Lossless compression researchers have developed highly sophisticated approaches, such as Huffman encoding, arithmetic encoding, the Lempel-Ziv family, Dynamic Markov Compression (DMC), Prediction by Partial Matching (PPM), and Burrows-Wheeler Transform (BWT) based algorithms. However, none of these methods has been able to reach the theoretical best-case compression ratio consistently, which suggests that better algorithms may be possible. One approach for trying to attain better compression ratios is to develop new compression algorithms. An alternative approach, however, is to develop intelligent, reversible transformations that can be applied to a source text that improve an existing, or backend, algorithm's ability to compress. The latter strategy has been explored here.


title: Exploring high performance distributed file storage using LDPC codes

abstract: We explore the feasibility of implementing a reliable, high performance, distributed storage system on a commodity computing cluster. Files are distributed across storage nodes using erasure coding with small Low-Density Parity-Check (LDPC) codes which provide high reliability while keeping the storage and performance overhead small. We present performance measurements done on a prototype system comprising 50 nodes which are self organised using a peer-to-peer overlay.


title: SCRUB-PA: A Multi-Level Multi-Dimensional Anonymization Tool for Process Accounting

abstract: In the UNIX/Linux environment the kernel can log every command process created by every user using process accounting. This data has many potential uses, including the investigation of security incidents. However, process accounting data is also sensitive since it contains private user information. Consequently, security system administrators have been hindered from sharing these logs. Given that many interesting security applications could use process accounting data, it would be useful to have a tool that could protect private user information in the logs. For this reason we introduce SCRUB-PA, a tool that uses multi-level multi-dimensional anonymization on process accounting log files in order to provide different levels of privacy protection. It is our goal that SCRUB-PA will promote the sharing of process accounting logs while preserving privacy.


title: On Measure Theoretic definitions of Generalized Information Measures and Maximum Entropy Prescriptions

abstract: Though Shannon entropy of a probability measure $P$, defined as $- \int_{X} \frac{\ud P}{\ud \mu} \ln \frac{\ud P}{\ud\mu} \ud \mu$ on a measure space $(X, \mathfrak{M},\mu)$, does not qualify itself as an information measure (it is not a natural extension of the discrete case), maximum entropy (ME) prescriptions in the measure-theoretic case are consistent with that of discrete case. In this paper, we study the measure-theoretic definitions of generalized information measures and discuss the ME prescriptions. We present two results in this regard: (i) we prove that, as in the case of classical relative-entropy, the measure-theoretic definitions of generalized relative-entropies, R\'{e}nyi and Tsallis, are natural extensions of their respective discrete cases, (ii) we show that, ME prescriptions of measure-theoretic Tsallis entropy are consistent with the discrete case.


title: An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture

abstract: In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which individual bits may be shared by several words. We also show that two variants (generalizations) of the problem can be solved optimally in $\Theta(\lg N)$ time under the comparison based model of computation.


title: Search in Complex Networks : a New Method of Naming

abstract: We suggest a method for routing when the source does not posses full information about the shortest path to the destination. The method is particularly useful for scale-free networks, and exploits its unique characteristics. By assigning new (short) names to nodes (aka labelling) we are able to reduce significantly the memory requirement at the routers, yet we succeed in routing with high probability through paths very close in distance to the shortest ones.


title: Multilevel Coding for Channels with Non-uniform Inputs and Rateless Transmission over the BSC

abstract: We consider coding schemes for channels with non-uniform inputs (NUI), where standard linear block codes can not be applied directly. We show that multilevel coding (MLC) with a set of linear codes and a deterministic mapper can achieve the information rate of the channel with NUI. The mapper, however, does not have to be one-to-one. As an application of the proposed MLC scheme, we present a rateless transmission scheme over the binary symmetric channel (BSC).


title: Randomized Fast Design of Short DNA Words

abstract: We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA computing and DNA self-assembly. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This paper proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide high-probability algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.


title: A Formal Foundation for ODRL

abstract: ODRL is a popular XML-based language for stating the conditions under which resources can be accessed legitimately. The language is described in English and, as a result, agreements written in ODRL are open to interpretation. To address this problem, we propose a formal semantics for a representative fragment of the language. We use this semantics to determine precisely when a permission is implied by a set of ODRL statements and show that answering such questions is a decidable NP-hard problem. Finally, we define a tractable fragment of ODRL that is also fairly expressive.


title: Comments on Beckmann's Uniform Reducts

abstract: Arnold Beckmann defined the uniform reduct of a propositional proof system f to be the set of those bounded arithmetical formulas whose propositional translations have polynomial size f-proofs. We prove that the uniform reduct of f + Extended Frege consists of all true bounded arithmetical formulas iff f + Extended Frege simulates every proof system.


title: Processing of Test Matrices with Guessing Correction

abstract: It is suggested to insert into test matrix 1s for correct responses, 0s for response refusals, and negative corrective elements for incorrect responses. With the classical test theory approach test scores of examinees and items are calculated traditionally as sums of matrix elements, organized in rows and columns. Correlation coefficients are estimated using correction coefficients. In item response theory approach examinee and item logits are estimated using maximum likelihood method and probabilities of all matrix elements.


title: An Algorithm for Constructing All Families of Codes of Arbitrary Requirement in an OCDMA System

abstract: A novel code construction algorithm is presented to find all the possible code families for code reconfiguration in an OCDMA system. The algorithm is developed through searching all the complete subgraphs of a constructed graph. The proposed algorithm is flexible and practical for constructing optical orthogonal codes (OOCs) of arbitrary requirement. Simulation results show that one should choose an appropriate code length in order to obtain sufficient number of code families for code reconfiguration with reasonable cost.


title: Distributed Kernel Regression: An Algorithm for Training Collaboratively

abstract: This paper addresses the problem of distributed learning under communication constraints, motivated by distributed signal processing in wireless sensor networks and data mining with distributed databases. After formalizing a general model for distributed learning, an algorithm for collaboratively training regularized kernel least-squares regression estimators is derived. Noting that the algorithm can be viewed as an application of successive orthogonal projection algorithms, its convergence properties are investigated and the statistical behavior of the estimator is discussed in a simplified theoretical setting.


title: Improved Nearly-MDS Expander Codes

abstract: A construction of expander codes is presented with the following three properties: (i) the codes lie close to the Singleton bound, (ii) they can be encoded in time complexity that is linear in their code length, and (iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace MDS outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for a significantly smaller alphabet size.


title: Communication Over MIMO Broadcast Channels Using Lattice-Basis Reduction

abstract: A simple scheme for communication over MIMO broadcast channels is introduced which adopts the lattice reduction technique to improve the naive channel inversion method. Lattice basis reduction helps us to reduce the average transmitted energy by modifying the region which includes the constellation points. Simulation results show that the proposed scheme performs well, and as compared to the more complex methods (such as the perturbation method) has a negligible loss. Moreover, the proposed method is extended to the case of different rates for different users. The asymptotic behavior of the symbol error rate of the proposed method and the perturbation technique, and also the outage probability for the case of fixed-rate users is analyzed. It is shown that the proposed method, based on LLL lattice reduction, achieves the optimum asymptotic slope of symbol-error-rate (called the precoding diversity). Also, the outage probability for the case of fixed sum-rate is analyzed.


title: LLL Reduction Achieves the Receive Diversity in MIMO Decoding

abstract: Diversity order is an important measure for the performance of communication systems over MIMO fading channels. In this paper, we prove that in MIMO multiple access systems (or MIMO point-to-point systems with V-BLAST transmission), lattice-reduction-aided decoding achieves the maximum receive diversity (which is equal to the number of receive antennas). Also, we prove that the naive lattice decoding (which discards the out-of-region decoded points) achieves the maximum diversity.


title: Stability of Scheduled Multi-access Communication over Quasi-static Flat Fading Channels with Random Coding and Joint Maximum Likelihood Decoding

abstract: We consider stability of scheduled multiaccess message communication with random coding and joint maximum-likehood decoding of messages. The framework we consider here models both the random message arrivals and the subsequent reliable communication by suitably combining techniques from queueing theory and information theory. The number of messages that may be scheduled for simultaneous transmission is limited to a given maximum value, and the channels from transmitters to receiver are quasi-static, flat, and have independent fades. Requests for message transmissions are assumed to arrive according to an i.i.d. arrival process. Then, (i) we derive an outer bound to the region of message arrival rate vectors achievable by the class of stationary scheduling policies, (ii) we show for any message arrival rate vector that satisfies the outerbound, that there exists a stationary state-independent policy that results in a stable system for the corresponding message arrival process, and (iii) in the limit of large message lengths, we show that the stability region of message nat arrival rate vectors has information-theoretic capacity region interpretation.


title: Stability of Scheduled Message Communication over Degraded Broadcast Channels

abstract: We consider scheduled message communication over a discrete memoryless degraded broadcast channel. The framework we consider here models both the random message arrivals and the subsequent reliable communication by suitably combining techniques from queueing theory and information theory. The channel from the transmitter to each of the receivers is quasi-static, flat, and with independent fades across the receivers. Requests for message transmissions are assumed to arrive according to an i.i.d. arrival process. Then, (i) we derive an outer bound to the region of message arrival vectors achievable by the class of stationary scheduling policies, (ii) we show for any message arrival vector that satisfies the outerbound, that there exists a stationary ``state-independent'' policy that results in a stable system for the corresponding message arrival process, and (iii) under two asymptotic regimes, we show that the stability region of nat arrival rate vectors has information-theoretic capacity region interpretation.


title: On the Weight Enumerator and the Maximum Likelihood Performance of Linear Product Codes

abstract: Product codes are widely used in data-storage, optical and wireless applications. Their analytical performance evaluation usually relies on the truncated union bound, which provides a low error rate approximation based on the minimum distance term only. In fact, the complete weight enumerator of most product codes remains unknown. In this paper, concatenated representations are introduced and applied to compute the complete average enumerators of arbitrary product codes over a field Fq. The split weight enumerators of some important constituent codes (Hamming, Reed-Solomon) are studied and used in the analysis. The average binary weight enumerators of Reed Solomon product codes are also derived. Numerical results showing the enumerator behavior are presented. By using the complete enumerators, Poltyrev bounds on the maximum likelihood performance, holding at both high and low error rates, are finally shown and compared against truncated union bounds and simulation results.


title: On timed automata with input-determined guards

abstract: We consider a general notion of timed automata with input-determined guards and show that they admit a robust logical framework along the lines of [D 'Souza03], in terms of a monadic second order logic characterisation and an expressively complete timed temporal logic. We then generalize these automata using the notion of recursive operators introduced by Henzinger, Raskin, and Schobbens, and show that they admit a similar logical framework. These results hold in the ``pointwise'' semantics. We finally use this framework to show that the real-time logic MITL of Alur et al is expressively complete with respect to an MSO corresponding to an appropriate input-determined operator.


title: Compression Scheme for Faster and Secure Data Transmission Over Internet

abstract: Compression algorithms reduce the redundancy in data representation to decrease the storage required for that data. Data compression offers an attractive approach to reducing communication costs by using available bandwidth effectively. Over the last decade there has been an unprecedented explosion in the amount of digital data transmitted via the Internet, representing text, images, video, sound, computer programs, etc. With this trend expected to continue, it makes sense to pursue research on developing algorithms that can most effectively use available network bandwidth by maximally compressing data. It is also important to consider the security aspects of the data being transmitted while compressing it, as most of the text data transmitted over the Internet is very much vulnerable to a multitude of attacks. This paper is focused on addressing this problem of lossless compression of text files with an added security.


title: Energy Efficiency and Delay Quality-of-Service in Wireless Networks

abstract: The energy-delay tradeoffs in wireless networks are studied using a game-theoretic framework. A multi-class multiple-access network is considered in which users choose their transmit powers, and possibly transmission rates, in a distributed manner to maximize their own utilities while satisfying their delay quality-of-service (QoS) requirements. The utility function considered here measures the number of reliable bits transmitted per Joule of energy consumed and is particularly useful for energy-constrained networks. The Nash equilibrium solution for the proposed non-cooperative game is presented and closed-form expressions for the users' utilities at equilibrium are obtained. Based on this, the losses in energy efficiency and network capacity due to presence of delay-sensitive users are quantified. The analysis is extended to the scenario where the QoS requirements include both the average source rate and a bound on the average total delay (including queuing delay). It is shown that the incoming traffic rate and the delay constraint of a user translate into a "size" for the user, which is an indication of the amount of resources consumed by the user. Using this framework, the tradeoffs among throughput, delay, network capacity and energy efficiency are also quantified.


title: Adaptive Linear Programming Decoding

abstract: Detectability of failures of linear programming (LP) decoding and its potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the LP problem. In this paper, we make a first step in studying this method, and show that it can significantly reduce the complexity of the problem, which was originally exponential in the maximum check-node degree. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in the performance.


title: Pseudorandomness and Combinatorial Constructions

abstract: In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science, probabilistic algorithms are sometimes simpler and more efficient than the best known deterministic algorithms for the same problem. Despite this evidence for the power of random choices, the computational theory of pseudorandomness shows that, under certain complexity-theoretic assumptions, every probabilistic algorithm has an efficient deterministic simulation and a large class of applications of the the probabilistic method can be converted into explicit constructions. In this survey paper we describe connections between the conditional ``derandomization'' results of the computational theory of pseudorandomness and unconditional explicit constructions of certain combinatorial objects such as error-correcting codes and ``randomness extractors.''


title: The topology of covert conflict

abstract: Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barabasi famously analysed the static case, and showed that vertex-order attacks are effective against scale-free networks. We extend this work to the dynamic case by developing a framework based on evolutionary game theory to explore the interaction of attack and defence strategies. We show, first, that naive defences don't work against vertex-order attack; second, that defences based on simple redundancy don't work much better, but that defences based on cliques work well; third, that attacks based on centrality work better against clique defences than vertex-order attacks do; and fourth, that defences based on complex strategies such as delegation plus clique resist centrality attacks better than simple clique defences. Our models thus build a bridge between network analysis and evolutionary game theory, and provide a framework for analysing defence and attack in networks where topology matters. They suggest definitions of efficiency of attack and defence, and may even explain the evolution of insurgent organisations from networks of cells to a more virtual leadership that facilitates operations rather than directing them. Finally, we draw some conclusions and present possible directions for future research.


title: Geometric symmetry in the quadratic Fisher discriminant operating on image pixels

abstract: This article examines the design of Quadratic Fisher Discriminants (QFDs) that operate directly on image pixels, when image ensembles are taken to comprise all rotated and reflected versions of distinct sample images. A procedure based on group theory is devised to identify and discard QFD coefficients made redundant by symmetry, for arbitrary sampling lattices. This procedure introduces the concept of a degeneracy matrix. Tensor representations are established for the square lattice point group (8-fold symmetry) and hexagonal lattice point group (12-fold symmetry). The analysis is largely applicable to the symmetrisation of any quadratic filter, and generalises to higher order polynomial (Volterra) filters. Experiments on square lattice sampled synthetic aperture radar (SAR) imagery verify that symmetrisation of QFDs can improve their generalisation and discrimination ability.


title: Google Web APIs - an Instrument for Webometric Analyses?

abstract: This paper introduces Google Web APIs (Google APIs) as an instrument and playground for webometric studies. Several examples of Google APIs implementations are given. Our examples show that this Google Web Service can be used successfully for informetric Internet based studies albeit with some restrictions.


title: The complexity of class polynomial computation via floating point approximations

abstract: We analyse the complexity of computing class polynomials, that are an important ingredient for CM constructions of elliptic curves, via complex floating point approximations of their roots. The heart of the algorithm is the evaluation of modular functions in several arguments. The fastest one of the presented approaches uses a technique devised by Dupont to evaluate modular functions by Newton iterations on an expression involving the arithmetic-geometric mean. It runs in time $O (|D| \log^5 |D| \log \log |D|) = O (|D|^{1 + \epsilon}) = O (h^{2 + \epsilon})$ for any $\epsilon > 0$, where $D$ is the CM discriminant and $h$ is the degree of the class polynomial. Another fast algorithm uses multipoint evaluation techniques known from symbolic computation; its asymptotic complexity is worse by a factor of $\log |D|$. Up to logarithmic factors, this running time matches the size of the constructed polynomials. The estimate also relies on a new result concerning the complexity of enumerating the class group of an imaginary-quadratic order and on a rigorously proven upper bound for the height of class polynomials.


title: The Perceptron Algorithm: Image and Signal Decomposition, Compression, and Analysis by Iterative Gaussian Blurring

abstract: A novel algorithm for tunable compression to within the precision of reproduction targets, or storage, is proposed. The new algorithm is termed the `Perceptron Algorithm', which utilises simple existing concepts in a novel way, has multiple immediate commercial application aspects as well as it opens up a multitude of fronts in computational science and technology. The aims of this paper are to present the concepts underlying the algorithm, observations by its application to some example cases, and the identification of a multitude of potential areas of applications such as: image compression by orders of magnitude, signal compression including sound as well, image analysis in a multilayered detailed analysis, pattern recognition and matching and rapid database searching (e.g. face recognition), motion analysis, biomedical applications e.g. in MRI and CAT scan image analysis and compression, as well as hints on the link of these ideas to the way how biological memory might work leading to new points of view in neural computation. Commercial applications of immediate interest are the compression of images at the source (e.g. photographic equipment, scanners, satellite imaging systems), DVD film compression, pay-per-view downloads acceleration and many others identified in the present paper at its conclusion and future work section.


title: The `Face on Mars': a photographic approach for the search of signs of past civilizations from a macroscopic point of view, factoring long-term erosion in image reconstruction

abstract: This short article presents an alternative view of high resolution imaging from various sources with the aim of the discovery of potential sites of archaeological importance, or sites that exhibit `anomalies' such that they may merit closer inspection and analysis. It is conjectured, and to a certain extent demonstrated here, that it is possible for advanced civilizations to factor in erosion by natural processes into a large scale design so that main features be preserved even with the passage of millions of years. Alternatively viewed, even without such intent embedded in a design left for posterity, it is possible that a gigantic construction may naturally decay in such a way that even cataclysmic (massive) events may leave sufficient information intact with the passage of time, provided one changes the point of view from high resolution images to enhanced blurred renderings of the sites in question.


title: Structure of Optimal Input Covariance Matrices for MIMO Systems with Covariance Feedback under General Correlated Fading

abstract: We describe the structure of optimal Input covariance matrices for single user multiple-input/multiple-output (MIMO) communication system with covariance feedback and for general correlated fading. Our approach is based on the novel concept of right commutant and recovers previously derived results for the Kronecker product models. Conditions are derived which allow a significant simplification of the optimization problem.


title: Fast Lexically Constrained Viterbi Algorithm (FLCVA): Simultaneous Optimization of Speed and Memory

abstract: Lexical constraints on the input of speech and on-line handwriting systems improve the performance of such systems. A significant gain in speed can be achieved by integrating in a digraph structure the different Hidden Markov Models (HMM) corresponding to the words of the relevant lexicon. This integration avoids redundant computations by sharing intermediate results between HMM's corresponding to different words of the lexicon. In this paper, we introduce a token passing method to perform simultaneously the computation of the a posteriori probabilities of all the words of the lexicon. The coding scheme that we introduce for the tokens is optimal in the information theory sense. The tokens use the minimum possible number of bits. Overall, we optimize simultaneously the execution speed and the memory requirement of the recognition systems.


title: Certainty Closure: Reliable Constraint Reasoning with Incomplete or Erroneous Data

abstract: Constraint Programming (CP) has proved an effective paradigm to model and solve difficult combinatorial satisfaction and optimisation problems from disparate domains. Many such problems arising from the commercial world are permeated by data uncertainty. Existing CP approaches that accommodate uncertainty are less suited to uncertainty arising due to incomplete and erroneous data, because they do not build reliable models and solutions guaranteed to address the user's genuine problem as she perceives it. Other fields such as reliable computation offer combinations of models and associated methods to handle these types of uncertain data, but lack an expressive framework characterising the resolution methodology independently of the model. We present a unifying framework that extends the CP formalism in both model and solutions, to tackle ill-defined combinatorial problems with incomplete or erroneous data. The certainty closure framework brings together modelling and solving methodologies from different fields into the CP paradigm to provide reliable and efficient approches for uncertain constraint problems. We demonstrate the applicability of the framework on a case study in network diagnosis. We define resolution forms that give generic templates, and their associated operational semantics, to derive practical solution methods for reliable solutions.


title: Mutual Information Games in Multi-user Channels with Correlated Jamming

abstract: We investigate the behavior of two users and one jammer in an AWGN channel with and without fading when they participate in a non-cooperative zero-sum game, with the channel's input/output mutual information as the objective function. We assume that the jammer can eavesdrop the channel and can use the information obtained to perform correlated jamming. Under various assumptions on the channel characteristics, and the extent of information available at the users and the jammer, we show the existence, or otherwise non-existence of a simultaneously optimal set of strategies for the users and the jammer. In all the cases where the channel is non-fading, we show that the game has a solution, and the optimal strategies are Gaussian signalling for the users and linear jamming for the jammer. In fading channels, we envision each player's strategy as a power allocation function over the channel states, together with the signalling strategies at each channel state. We reduce the game solution to a set of power allocation functions for the players and show that when the jammer is uncorrelated, the game has a solution, but when the jammer is correlated, a set of simultaneously optimal power allocation functions for the users and the jammer does not always exist. In this case, we characterize the max-min user power allocation strategies and the corresponding jammer power allocation strategy.


title: Localization in Wireless Sensor Grids

abstract: This work reports experiences on using radio ranging to position sensors in a grid topology. The implementation is simple, efficient, and could be practically distributed. The paper describes an implementation and experimental result based on RSSI distance estimation. Novel techniques such as fuzzy membership functions and table lookup are used to obtain more accurate result and simplify the computation. An 86% accuracy is achieved in the experiment in spite of inaccurate RSSI distance estimates with errors up to 60%.


title: Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers

abstract: We show that the finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. The method employed also yields a simple proof of a result recently obtained by Y. Kazakov, that the satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME.


title: An Efficient Pseudo-Codeword Search Algorithm for Linear Programming Decoding of LDPC Codes

abstract: In Linear Programming (LP) decoding of a Low-Density-Parity-Check (LDPC) code one minimizes a linear functional, with coefficients related to log-likelihood ratios, over a relaxation of the polytope spanned by the codewords \cite{03FWK}. In order to quantify LP decoding, and thus to describe performance of the error-correction scheme at moderate and large Signal-to-Noise-Ratios (SNR), it is important to study the relaxed polytope to understand better its vertexes, so-called pseudo-codewords, especially those which are neighbors of the zero codeword. In this manuscript we propose a technique to heuristically create a list of these neighbors and their distances. Our pseudo-codeword-search algorithm starts by randomly choosing the initial configuration of the noise. The configuration is modified through a discrete number of steps. Each step consists of two sub-steps. Firstly, one applies an LP decoder to the noise-configuration deriving a pseudo-codeword. Secondly, one finds configuration of the noise equidistant from the pseudo codeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudo-codeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function (frequency spectrum) of the pseudo-codeword effective distance. The effective distance of the coding scheme is approximated by the shortest distance pseudo-codeword in the spectrum. The efficiency of the procedure is demonstrated on examples of the Tanner $[155,64,20]$ code and Margulis $p=7$ and $p=11$ codes (672 and 2640 bits long respectively) operating over an Additive-White-Gaussian-Noise (AWGN) channel.


title: Efficient Query Answering over Conceptual Schemas of Relational Databases : Technical Report

abstract: We develop a query answering system, where at the core of the work there is an idea of query answering by rewriting. For this purpose we extend the DL DL-Lite with the ability to support n-ary relations, obtaining the DL DLR-Lite, which is still polynomial in the size of the data. We devise a flexible way of mapping the conceptual level to the relational level, which provides the users an SQL-like query language over the conceptual schema. The rewriting technique adds value to conventional query answering techniques, allowing to formulate simpler queries, with the ability to infer additional information that was not stated explicitly in the user query. The formalization of the conceptual schema and the developed reasoning technique allow checking for consistency between the database and the conceptual schema, thus improving the trustiness of the information system.


title: Decision Making with Side Information and Unbounded Loss Functions

abstract: We consider the problem of decision-making with side information and unbounded loss functions. Inspired by probably approximately correct learning model, we use a slightly different model that incorporates the notion of side information in a more generic form to make it applicable to a broader class of applications including parameter estimation and system identification. We address sufficient conditions for consistent decision-making with exponential convergence behavior. In this regard, besides a certain condition on the growth function of the class of loss functions, it suffices that the class of loss functions be dominated by a measurable function whose exponential Orlicz expectation is uniformly bounded over the probabilistic model. Decay exponent, decay constant, and sample complexity are discussed. Example applications to method of moments, maximum likelihood estimation, and system identification are illustrated, as well.


title: A unifying framework for seed sensitivity and its application to subset seeds

abstract: We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem -- a set of target alignments, an associated probability distribution, and a seed model -- that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.


title: Finding Cliques of a Graph using Prime Numbers

abstract: This paper proposes a new algorithm for solving maximal cliques for simple undirected graphs using the theory of prime numbers. A novel approach using prime numbers is used to find cliques and ends with a discussion of the algorithm.


title: A Formal Architecture-Centric Model-Driven Approach for the Automatic Generation of Grid Applications

abstract: This paper discusses the concept of model-driven software engineering applied to the Grid application domain. As an extension to this concept, the approach described here, attempts to combine both formal architecture-centric and model-driven paradigms. It is a commonly recognized statement that Grid systems have seldom been designed using formal techniques although from past experience such techniques have shown advantages. This paper advocates a formal engineering approach to Grid system developments in an effort to contribute to the rigorous development of Grids software architectures. This approach addresses quality of service and cross-platform developments by applying the model-driven paradigm to a formal architecture-centric engineering method. This combination benefits from a formal semantic description power in addition to model-based transformations. The result of such a novel combined concept promotes the re-use of design models and facilitates developments in Grid computing.


title: Engineering Conceptual Data Models from Domain Ontologies: A Critical Evaluation

abstract: This paper studies the differences and similarities between domain ontologies and conceptual data models and the role that ontologies can play in establishing conceptual data models during the process of information systems development. A mapping algorithm has been proposed and embedded in a special purpose Transformation Engine to generate a conceptual data model from a given domain ontology. Both quantitative and qualitative methods have been adopted to critically evaluate this new approach. In addition, this paper focuses on evaluating the quality of the generated conceptual data model elements using Bunge-Wand-Weber and OntoClean ontologies. The results of this evaluation indicate that the generated conceptual data model provides a high degree of accuracy in identifying the substantial domain entities along with their attributes and relationships being derived from the consensual semantics of domain knowledge. The results are encouraging and support the potential role that this approach can take part in process of information system development.


title: On The Minimum Mean-Square Estimation Error of the Normalized Sum of Independent Narrowband Waves in the Gaussian Channel

abstract: The minimum mean-square error of the estimation of a signal where observed from the additive white Gaussian noise (WGN) channel's output, is analyzed. It is assumed that the channel input's signal is composed of a (normalized) sum of N narrowband, mutually independent waves. It is shown that if N goes to infinity, then for any fixed signal energy to noise energy ratio (no mater how big) both the causal minimum mean-square error CMMSE and the non-causal minimum mean-square error MMSE converge to the signal energy at a rate which is proportional to 1/N.


title: A Multi-Relational Network to Support the Scholarly Communication Process

abstract: The general pupose of the scholarly communication process is to support the creation and dissemination of ideas within the scientific community. At a finer granularity, there exists multiple stages which, when confronted by a member of the community, have different requirements and therefore different solutions. In order to take a researcher's idea from an initial inspiration to a community resource, the scholarly communication infrastructure may be required to 1) provide a scientist initial seed ideas; 2) form a team of well suited collaborators; 3) located the most appropriate venue to publish the formalized idea; 4) determine the most appropriate peers to review the manuscript; and 5) disseminate the end product to the most interested members of the community. Through the various delinieations of this process, the requirements of each stage are tied soley to the multi-functional resources of the community: its researchers, its journals, and its manuscritps. It is within the collection of these resources and their inherent relationships that the solutions to scholarly communication are to be found. This paper describes an associative network composed of multiple scholarly artifacts that can be used as a medium for supporting the scholarly communication process.


title: Reducibility of Gene Patterns in Ciliates using the Breakpoint Graph

abstract: Gene assembly in ciliates is one of the most involved DNA processings going on in any organism. This process transforms one nucleus (the micronucleus) into another functionally different nucleus (the macronucleus). We continue the development of the theoretical models of gene assembly, and in particular we demonstrate the use of the concept of the breakpoint graph, known from another branch of DNA transformation research. More specifically: (1) we characterize the intermediate gene patterns that can occur during the transformation of a given micronuclear gene pattern to its macronuclear form; (2) we determine the number of applications of the loop recombination operation (the most basic of the three molecular operations that accomplish gene assembly) needed in this transformation; (3) we generalize previous results (and give elegant alternatives for some proofs) concerning characterizations of the micronuclear gene patterns that can be assembled using a specific subset of the three molecular operations.


title: Low density codes achieve the rate-distortion bound

abstract: We propose a new construction for low-density source codes with multiple parameters that can be tuned to optimize the performance of the code. In addition, we introduce a set of analysis techniques for deriving upper bounds for the expected distortion of our construction, as well as more general low-density constructions. We show that (with an optimal encoding algorithm) our codes achieve the rate-distortion bound for a binary symmetric source and Hamming distortion. Our methods also provide rigorous upper bounds on the minimum distortion achievable by previously proposed low-density constructions.


title: Power Control for User Cooperation

abstract: For a fading Gaussian multiple access channel with user cooperation, we obtain the optimal power allocation policies that maximize the rates achievable by block Markov superposition coding. The optimal policies result in a coding scheme that is simpler than the one for a general multiple access channel with generalized feedback. This simpler coding scheme also leads to the possibility of formulating an otherwise non-concave optimization problem as a concave one. Using the channel state information at the transmitters to adapt the powers, we demonstrate significant gains over the achievable rates for existing cooperative systems.


title: Metadata aggregation and "automated digital libraries": A retrospective on the NSDL experience

abstract: Over three years ago, the Core Integration team of the National Science Digital Library (NSDL) implemented a digital library based on metadata aggregation using Dublin Core and OAI-PMH. The initial expectation was that such low-barrier technologies would be relatively easy to automate and administer. While this architectural choice permitted rapid deployment of a production NSDL, our three years of experience have contradicted our original expectations of easy automation and low people cost. We have learned that alleged "low-barrier" standards are often harder to deploy than expected. In this paper we report on this experience and comment on the general cost, the functionality, and the ultimate effectiveness of this architecture.


title: Approximate Linear Time ML Decoding on Tail-Biting Trellises in Two Rounds

abstract: A linear time approximate maximum likelihood decoding algorithm on tail-biting trellises is prsented, that requires exactly two rounds on the trellis. This is an adaptation of an algorithm proposed earlier with the advantage that it reduces the time complexity from O(mlogm) to O(m) where m is the number of nodes in the tail-biting trellis. A necessary condition for the output of the algorithm to differ from the output of the ideal ML decoder is reduced and simulation results on an AWGN channel using tail-biting rrellises for two rate 1/2 convoluational codes with memory 4 and 6 respectively are reported


title: Truly Online Paging with Locality of Reference

abstract: The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model, which attempts to capture the locality of reference. However, the access graph model has a number of troubling aspects. The access graph has to be known in advance to the paging algorithm and the memory required to represent the access graph itself may be very large. In this paper we present truly online strongly competitive paging algorithms in the access graph model that do not have any prior information on the access sequence. We present both deterministic and randomized algorithms. The algorithms need only O(k log n) bits of memory, where k is the number of page slots available and n is the size of the virtual address space. I.e., asymptotically no more memory than needed to store the virtual address translation table. We also observe that our algorithms adapt themselves to temporal changes in the locality of reference. We model temporal changes in the locality of reference by extending the access graph model to the so called extended access graph model, in which many vertices of the graph can correspond to the same virtual page. We define a measure for the rate of change in the locality of reference in G denoted by Delta(G). We then show our algorithms remain strongly competitive as long as Delta(G) >= (1+ epsilon)k, and no truly online algorithm can be strongly competitive on a class of extended access graphs that includes all graphs G with Delta(G) >= k- o(k).


title: On the 3-distortion of a path

abstract: We prove that, when a path of length n is embedded in R^2, the 3-distortion is an Omega(n^{1/2}), and that, when embedded in R^d, the 3-distortion is an O(n^{1/d-1}).


title: Instantaneously Trained Neural Networks

abstract: This paper presents a review of instantaneously trained neural networks (ITNNs). These networks trade learning time for size and, in the basic model, a new hidden node is created for each training sample. Various versions of the corner-classification family of ITNNs, which have found applications in artificial intelligence (AI), are described. Implementation issues are also considered.


title: From Dumb Wireless Sensors to Smart Networks using Network Coding

abstract: The vision of wireless sensor networks is one of a smart collection of tiny, dumb devices. These motes may be individually cheap, unintelligent, imprecise, and unreliable. Yet they are able to derive strength from numbers, rendering the whole to be strong, reliable and robust. Our approach is to adopt a distributed and randomized mindset and rely on in network processing and network coding. Our general abstraction is that nodes should act only locally and independently, and the desired global behavior should arise as a collective property of the network. We summarize our work and present how these ideas can be applied for communication and storage in sensor networks.


title: Scalable Algorithms for Aggregating Disparate Forecasts of Probability

abstract: In this paper, computational aspects of the panel aggregation problem are addressed. Motivated primarily by applications of risk assessment, an algorithm is developed for aggregating large corpora of internally incoherent probability assessments. The algorithm is characterized by a provable performance guarantee, and is demonstrated to be orders of magnitude faster than existing tools when tested on several real-world data-sets. In addition, unexpected connections between research in risk assessment and wireless sensor networks are exposed, as several key ideas are illustrated to be useful in both fields.


title: A Study on the Global Convergence Time Complexity of Estimation of Distribution Algorithms

abstract: The Estimation of Distribution Algorithm is a new class of population based search methods in that a probabilistic model of individuals is estimated based on the high quality individuals and used to generate the new individuals. In this paper we compute 1) some upper bounds on the number of iterations required for global convergence of EDA 2) the exact number of iterations needed for EDA to converge to global optima.


title: Dense Linear Algebra over Finite Fields: the FFLAS and FFPACK packages

abstract: In the past two decades, some major efforts have been made to reduce exact (e.g. integer, rational, polynomial) linear algebra problems to matrix multiplication in order to provide algorithms with optimal asymptotic complexity. To provide efficient implementations of such algorithms one need to be careful with the underlying arithmetic. It is well known that modular techniques such as the Chinese remainder algorithm or the p-adic lifting allow very good practical performance, especially when word size arithmetic are used. Therefore, finite field arithmetic becomes an important core for efficient exact linear algebra libraries. In this paper, we study high performance implementations of basic linear algebra routines over word size prime fields: specially the matrix multiplication; our goal being to provide an exact alternate to the numerical BLAS library. We show that this is made possible by a carefull combination of numerical computations and asymptotically faster algorithms. Our kernel has several symbolic linear algebra applications enabled by diverse matrix multiplication reductions: symbolic triangularization, system solving, determinant and matrix inverse implementations are thus studied.


title: Combining decision procedures for the reals

abstract:
We address the general problem of determining the validity of boolean combinations of equalities and inequalities between real-valued expressions. In particular, we consider methods of establishing such assertions using only restricted forms of distributivity. At the same time, we explore ways in which "local" decision or heuristic procedures for fragments of the theory of the reals can be amalgamated into global ones.

Let Tadd[Q] be the first-order theory of the real numbers in the language of ordered groups, with negation, a constant 1, and function symbols for multiplication by rational constants. Let Tmult[Q] be the analogous theory for the multiplicative structure, and let T[Q] be the union of the two. We show that although T[Q] is undecidable, the universal fragment of T[Q] is decidable. We also show that terms of T[Q]can fruitfully be put in a normal form. We prove analogous results for theories in which Q is replaced, more generally, by suitable subfields F of the reals. Finally, we consider practical methods of establishing quantifier-free validities that approximate our (impractical) decidability results.


title: Strategies of Loop Recombination in Ciliates

abstract: Gene assembly in ciliates is an extremely involved DNA transformation process, which transforms a nucleus, the micronucleus, to another functionally different nucleus, the macronucleus. In this paper we characterize which loop recombination operations (one of the three types of molecular operations that accomplish gene assembly) can possibly be applied in the transformation of a given gene from its micronuclear form to its macronuclear form. We also characterize in which order these loop recombination operations are applicable. This is done in the abstract and more general setting of so-called legal strings.


title: Query-Monotonic Turing Reductions

abstract: We study reductions that limit the extreme adaptivity of Turing reductions. In particular, we study reductions that make a rapid, structured progression through the set to which they are reducing: Each query is strictly longer (shorter) than the previous one. We call these reductions query-increasing (query-decreasing) Turing reductions. We also study query-nonincreasing (query-nondecreasing) Turing reductions. These are Turing reductions in which the sequence of query lengths is nonincreasing (nondecreasing). We ask whether these restrictions in fact limit the power of reductions. We prove that query-increasing and query-decreasing Turing reductions are incomparable with (that is, are neither strictly stronger than nor strictly weaker than) truth-table reductions and are strictly weaker than Turing reductions. In addition, we prove that query-nonincreasing and query-nondecreasing Turing reductions are strictly stronger than truth-table reductions and strictly weaker than Turing reductions. Despite the fact that we prove query-increasing and query-decreasing Turing reductions to in the general case be strictly weaker than Turing reductions, we identify a broad class of sets A for which any set that Turing reduces to A will also reduce to A via both query-increasing and query-decreasing Turing reductions. In particular, this holds for all tight paddable sets, where a set is said to be tight paddable exactly if it is paddable via a function whose output length is bounded tightly both from above and from below in the length of the input. We prove that many natural NP-complete problems such as satisfiability, clique, and vertex cover are tight paddable.


title: Simulating Network Influence Algorithms Using Particle-Swarms: PageRank and PageRank-Priors

abstract: A particle-swarm is a set of indivisible processing elements that traverse a network in order to perform a distributed function. This paper will describe a particular implementation of a particle-swarm that can simulate the behavior of the popular PageRank algorithm in both its {\it global-rank} and {\it relative-rank} incarnations. PageRank is compared against the particle-swarm method on artificially generated scale-free networks of 1,000 nodes constructed using a common gamma value, $\gamma = 2.5$. The running time of the particle-swarm algorithm is $O(|P|+|P|t)$ where $|P|$ is the size of the particle population and $t$ is the number of particle propagation iterations. The particle-swarm method is shown to be useful due to its ease of extension and running time.


title: Watermarking Using Decimal Sequences

abstract: This paper introduces the use of decimal sequences in a code division multiple access (CDMA) based watermarking system to hide information for authentication in black and white images. Matlab version 6.5 was used to implement the algorithms discussed in this paper. The advantage of using d-sequences over PN sequences is that one can choose from a variety of prime numbers which provides a more flexible system.


title: Conjunctive Queries over Trees

abstract: We study the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as ``child'', ``descendant'', and ``following'' as well as unary relations for node labels. We establish a framework for characterizing structures representing trees for which conjunctive queries can be evaluated efficiently. Then we completely chart the tractability frontier of the problem and establish a dichotomy theorem for our axis relations, i.e., we find all subset-maximal sets of axes for which query evaluation is in polynomial time and show that for all other cases, query evaluation is NP-complete. All polynomial-time results are obtained immediately using the proof techniques from our framework. Finally, we study the expressiveness of conjunctive queries over trees and show that for each conjunctive query, there is an equivalent acyclic positive query (i.e., a set of acyclic conjunctive queries), but that in general this query is not of polynomial size.


title: A library of Taylor models for PVS automatic proof checker

abstract: We present in this paper a library to compute with Taylor models, a technique extending interval arithmetic to reduce decorrelation and to solve differential equations. Numerical software usually produces only numerical results. Our library can be used to produce both results and proofs. As seen during the development of Fermat's last theorem reported by Aczel 1996, providing a proof is not sufficient. Our library provides a proof that has been thoroughly scrutinized by a trustworthy and tireless assistant. PVS is an automatic proof assistant that has been fairly developed and used and that has no internal connection with interval arithmetic or Taylor models. We built our library so that PVS validates each result as it is produced. As producing and validating a proof, is and will certainly remain a bigger task than just producing a numerical result our library will never be a replacement to imperative implementations of Taylor models such as Cosy Infinity. Our library should mainly be used to validate small to medium size results that are involved in safety or life critical applications.


title: A Visual Query Language for Complex-Value Databases

abstract: In this paper, a visual language, VCP, for queries on complex-value databases is proposed. The main strength of the new language is that it is purely visual: (i) It has no notion of variable, quantification, partiality, join, pattern matching, regular expression, recursion, or any other construct proper to logical, functional, or other database query languages and (ii) has a very natural, strong, and intuitive design metaphor. The main operation is that of copying and pasting in a schema tree. We show that despite its simplicity, VCP precisely captures complex-value algebra without powerset, or equivalently, monad algebra with union and difference. Thus, its expressive power is precisely that of the language that is usually considered to play the role of relational algebra for complex-value databases.


title: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data

abstract: We provide formal definitions and efficient secure techniques for - turning noisy information into keys usable for any cryptographic application, and, in particular, - reliably and securely authenticating biometric data. Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. We propose two primitives: a "fuzzy extractor" reliably extracts nearly uniform randomness R from its input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in a cryptographic application. A "secure sketch" produces public information about its input w that does not reveal w, and yet allows exact recovery of w given another value that is close to w. Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them. We define the primitives to be both formally secure and versatile, generalizing much prior work. In addition, we provide nearly optimal constructions of both primitives for various measures of ``closeness'' of input data, such as Hamming distance, edit distance, and set difference.


title: Demand Analysis with Partial Predicates

abstract: In order to alleviate the inefficiencies caused by the interaction of the logic and functional sides, integrated languages may take advantage of \emph{demand} information -- i.e. knowing in advance which computations are needed and, to which extent, in a particular context. This work studies \emph{demand analysis} -- which is closely related to \emph{backwards strictness analysis} -- in a semantic framework of \emph{partial predicates}, which in turn are constructive realizations of ideals in a domain. This will allow us to give a concise, unified presentation of demand analysis, to relate it to other analyses based on abstract interpretation or strictness logics, some hints for the implementation, and, more important, to prove the soundness of our analysis based on \emph{demand equations}. There are also some innovative results. One of them is that a set constraint-based analysis has been derived in a stepwise manner using ideas taken from the area of program transformation. The other one is the possibility of using program transformation itself to perform the analysis, specially in those domains of properties where algorithms based on constraint solving are too weak.


title: Efficient Teamwork

abstract: Our goal is to solve both problems of adverse selection and moral hazard for multi-agent projects. In our model, each selected agent can work according to his private "capability tree". This means a process involving hidden actions, hidden chance events and hidden costs in a dynamic manner, and providing contractible consequences which are affecting each other's working process and the outcome of the project. We will construct a mechanism that induces truthful revelation of the agents' capability trees and chance events and to follow the instructions about their hidden decisions. This enables the planner to select the optimal subset of agents and obtain the efficient joint execution. We will construct another mechanism that is collusion-resistant but implements an only approximately efficient outcome. The latter mechanism is widely applicable, and the major application details will be elaborated.


title: Reducing Tile Complexity for Self-Assembly Through Temperature Programming

abstract: We consider the tile self-assembly model and how tile complexity can be eliminated by permitting the temperature of the self-assembly system to be adjusted throughout the assembly process. To do this, we propose novel techniques for designing tile sets that permit an arbitrary length $m$ binary number to be encoded into a sequence of $O(m)$ temperature changes such that the tile set uniquely assembles a supertile that precisely encodes the corresponding binary number. As an application, we show how this provides a general tile set of size O(1) that is capable of uniquely assembling essentially any $n\times n$ square, where the assembled square is determined by a temperature sequence of length $O(\log n)$ that encodes a binary description of $n$. This yields an important decrease in tile complexity from the required $\Omega(\frac{\log n}{\log\log n})$ for almost all $n$ when the temperature of the system is fixed. We further show that for almost all $n$, no tile system can simultaneously achieve both $o(\log n)$ temperature complexity and $o(\frac{\log n}{\log\log n})$ tile complexity, showing that both versions of an optimal square building scheme have been discovered. This work suggests that temperature change can constitute a natural, dynamic method for providing input to self-assembly systems that is potentially superior to the current technique of designing large tile sets with specific inputs hardwired into the tileset.


title: The intuitionistic fragment of computability logic at the propositional level

abstract: This paper presents a soundness and completeness proof for propositional intuitionistic calculus with respect to the semantics of computability logic. The latter interprets formulas as interactive computational problems, formalized as games between a machine and its environment. Intuitionistic implication is understood as algorithmic reduction in the weakest possible -- and hence most natural -- sense, disjunction and conjunction as deterministic-choice combinations of problems (disjunction = machine's choice, conjunction = environment's choice), and "absurd" as a computational problem of universal strength. See http://www.cis.upenn.edu/~giorgi/cl.html for a comprehensive online source on computability logic.


title: Wreath Products in Stream Cipher Design

abstract: The paper develops a novel approach to stream cipher design: Both the state update function and the output function of the corresponding pseudorandom generators are compositions of arithmetic and bitwise logical operations, which are standard instructions of modern microprocessors. Moreover, both the state update function and the output function are being modified dynamically during the encryption. Also, these compositions could be keyed, so the only information available to an attacker is that these functions belong to some exponentially large class. The paper shows that under rather loose conditions the output sequence is uniformly distributed, achieves maximum period length and has high linear complexity and high $\ell$-error linear complexity. Ciphers of this kind are flexible: One could choose a suitable combination of instructions to obtain due performance without affecting the quality of the output sequence. Finally, some evidence is given that a key recovery problem for (reasonably designed) stream ciphers of this kind is intractable up to plausible conjectures.


title: An Optimal Distributed Edge-Biconnectivity Algorithm

abstract: We describe a synchronous distributed algorithm which identifies the edge-biconnected components of a connected network. It requires a leader, and uses messages of size O(log |V|). The main idea is to preorder a BFS spanning tree, and then to efficiently compute least common ancestors so as to mark cycle edges. This algorithm takes O(Diam) time and uses O(|E|) messages. Furthermore, we show that no correct singly-initiated edge-biconnectivity algorithm can beat either bound on any graph by more than a constant factor. We also describe a near-optimal local algorithm for edge-biconnectivity.


title: Game theoretic aspects of distributed spectral coordination with application to DSL networks

abstract: In this paper we use game theoretic techniques to study the value of cooperation in distributed spectrum management problems. We show that the celebrated iterative water-filling algorithm is subject to the prisoner's dilemma and therefore can lead to severe degradation of the achievable rate region in an interference channel environment. We also provide thorough analysis of a simple two bands near-far situation where we are able to provide closed form tight bounds on the rate region of both fixed margin iterative water filling (FM-IWF) and dynamic frequency division multiplexing (DFDM) methods. This is the only case where such analytic expressions are known and all previous studies included only simulated results of the rate region. We then propose an alternative algorithm that alleviates some of the drawbacks of the IWF algorithm in near-far scenarios relevant to DSL access networks. We also provide experimental analysis based on measured DSL channels of both algorithms as well as the centralized optimum spectrum management.


title: On the Asymptotic Performance of Multiple Antenna Channels with Fast Channel Feedback

abstract: In this paper, we analyze the asymptotic performance of multiple antenna channels where the transmitter has either perfect or finite bit channel state information. Using the diversity-multiplexing tradeoff to characterize the system performance, we demonstrate that channel feedback can fundamentally change the system behavior. Even one-bit of information can increase the diversity order of the system compared to the system with no transmitter information. In addition, as the amount of channel information at the transmitter increases, the diversity order for each multiplexing gain increases and goes to infinity for perfect transmitter information. The major reason for diversity order gain is a "location-dependent" temporal power control, which adapts the power control strategy based on the average channel conditions of the channel.


title: Finding total unimodularity in optimization problems solved by linear programs

abstract: A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with the same cost from the fractional solution. Examples are two scheduling problems and the single disk prefetching/caching problem. We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, from which we obtain simple combinatorial algorithms with improved worst case running time.


title: Quasi-Linear Soft Tissue Models Revisited

abstract: Incompressibility, nonlinear deformation under stress and viscoelasticity are the fingerprint of soft tissue mechanical behavior. In order to model soft tissues appropriately, we must pursue to complete these requirements. In this work we revisited different soft tissue quasi-linear model possibilities in trying to achieve for this commitment.


title: Improving the CSIEC Project and Adapting It to the English Teaching and Learning in China

abstract: In this paper after short review of the CSIEC project initialized by us in 2003 we present the continuing development and improvement of the CSIEC project in details, including the design of five new Microsoft agent characters representing different virtual chatting partners and the limitation of simulated dialogs in specific practical scenarios like graduate job application interview, then briefly analyze the actual conditions and features of its application field: web-based English education in China. Finally we introduce our efforts to adapt this system to the requirements of English teaching and learning in China and point out the work next to do.


title: Adaptive Channel Allocation Spectrum Etiquette for Cognitive Radio Networks

abstract: In this work, we propose a game theoretic framework to analyze the behavior of cognitive radios for distributed adaptive channel allocation. We define two different objective functions for the spectrum sharing games, which capture the utility of selfish users and cooperative users, respectively. Based on the utility definition for cooperative users, we show that the channel allocation problem can be formulated as a potential game, and thus converges to a deterministic channel allocation Nash equilibrium point. Alternatively, a no-regret learning implementation is proposed for both scenarios and it is shown to have similar performance with the potential game when cooperation is enforced, but with a higher variability across users. The no-regret learning formulation is particularly useful to accommodate selfish users. Non-cooperative learning games have the advantage of a very low overhead for information exchange in the network. We show that cooperation based spectrum sharing etiquette improves the overall network performance at the expense of an increased overhead required for information exchange.


title: Inter-Block Permuted Turbo Codes

abstract: The structure and size of the interleaver used in a turbo code critically affect the distance spectrum and the covariance property of a component decoder's information input and soft output. This paper introduces a new class of interleavers, the inter-block permutation (IBP) interleavers, that can be build on any existing "good" block-wise interleaver by simply adding an IBP stage. The IBP interleavers reduce the above-mentioned correlation and increase the effective interleaving size. The increased effective interleaving size improves the distance spectrum while the reduced covariance enhances the iterative decoder's performance. Moreover, the structure of the IBP(-interleaved) turbo codes (IBPTC) is naturally fit for high rate applications that necessitate parallel decoding. We present some useful bounds and constraints associated with the IBPTC that can be used as design guidelines. The corresponding codeword weight upper bounds for weight-2 and weight-4 input sequences are derived. Based on some of the design guidelines, we propose a simple IBP algorithm and show that the associated IBPTC yields 0.3 to 1.2 dB performance gain, or equivalently, an IBPTC renders the same performance with a much reduced interleaving delay. The EXIT and covariance behaviors provide another numerical proof of the superiority of the proposed IBPTC.


title: Using Domain Knowledge in Evolutionary System Identification

abstract: Two example of Evolutionary System Identification are presented to highlight the importance of incorporating Domain Knowledge: the discovery of an analytical indentation law in Structural Mechanics using constrained Genetic Programming, and the identification of the repartition of underground velocities in Seismic Prospection. Critical issues for sucessful ESI are discussed in the light of these results.


title: Avoiding the Bloat with Stochastic Grammar-based Genetic Programming

abstract: The application of Genetic Programming to the discovery of empirical laws is often impaired by the huge size of the search space, and consequently by the computer resources needed. In many cases, the extreme demand for memory and CPU is due to the massive growth of non-coding segments, the introns. The paper presents a new program evolution framework which combines distribution-based evolution in the PBIL spirit, with grammar-based genetic programming; the information is stored as a probability distribution on the gra mmar rules, rather than in a population. Experiments on a real-world like problem show that this approach gives a practical solution to the problem of intron growth.


title: Information theory and Thermodynamics

abstract: A communication theory for a transmitter broadcasting to many receivers is presented. In this case energetic considerations cannot be neglected as in Shannon theory. It is shown that, when energy is assigned to the information bit, information theory complies with classical thermodynamic and is part of it. To provide a thermodynamic theory of communication it is necessary to define equilibrium for informatics systems that are not in thermal equilibrium and to calculate temperature, heat, and entropy with accordance to Clausius inequality. It is shown that for a binary file the temperature is proportional to the bit energy and that information is thermodynamic entropy. Equilibrium exists in random files that cannot be compressed. Thermodynamic bounds on the computing power of a physical device, and the maximum information that an antenna can broadcast are calculated.


title: Algorithmic correspondence and completeness in modal logic. I. The core algorithm SQEMA

abstract: Modal formulae express monadic second-order properties on Kripke frames, but in many important cases these have first-order equivalents. Computing such equivalents is important for both logical and computational reasons. On the other hand, canonicity of modal formulae is important, too, because it implies frame-completeness of logics axiomatized with canonical formulae. Computing a first-order equivalent of a modal formula amounts to elimination of second-order quantifiers. Two algorithms have been developed for second-order quantifier elimination: SCAN, based on constraint resolution, and DLS, based on a logical equivalence established by Ackermann. In this paper we introduce a new algorithm, SQEMA, for computing first-order equivalents (using a modal version of Ackermann's lemma) and, moreover, for proving canonicity of modal formulae. Unlike SCAN and DLS, it works directly on modal formulae, thus avoiding Skolemization and the subsequent problem of unskolemization. We present the core algorithm and illustrate it with some examples. We then prove its correctness and the canonicity of all formulae on which the algorithm succeeds. We show that it succeeds not only on all Sahlqvist formulae, but also on the larger class of inductive formulae, introduced in our earlier papers. Thus, we develop a purely algorithmic approach to proving canonical completeness in modal logic and, in particular, establish one of the most general completeness results in modal logic so far.


title: On local symbolic approximation and resolution of ODEs using Implicit Function Theorem

abstract: In this work the implicit function theorem is used for searching local symbolic resolution of differential equations. General results of existence for first order equations are proven and some examples, one relative to cavitation in a fluid, are developed. These examples seem to show that local approximation of non linear differential equations can give useful informations about symbolic form of possible solutions, and in the case a global solution is known, locally the accuracy of approximation can be good.


title: Bulk Scheduling with DIANA Scheduler

abstract: Results from and progress on the development of a Data Intensive and Network Aware (DIANA) Scheduling engine, primarily for data intensive sciences such as physics analysis, are described. Scientific analysis tasks can involve thousands of computing, data handling, and network resources and the size of the input and output files and the amount of overall storage space allocated to a user necessarily can have significant bearing on the scheduling of data intensive applications. If the input or output files must be retrieved from a remote location, then the time required transferring the files must also be taken into consideration when scheduling compute resources for the given application. The central problem in this study is the coordinated management of computation and data at multiple locations and not simply data movement. However, this can be a very costly operation and efficient scheduling can be a challenge if compute and data resources are mapped without network cost. We have implemented an adaptive algorithm within the DIANA Scheduler which takes into account data location and size, network performance and computation capability to make efficient global scheduling decisions. DIANA is a performance-aware as well as an economy-guided Meta Scheduler. It iteratively allocates each job to the site that is likely to produce the best performance as well as optimizing the global queue for any remaining pending jobs. Therefore it is equally suitable whether a single job is being submitted or bulk scheduling is being performed. Results suggest that considerable performance improvements are to be gained by adopting the DIANA scheduling approach.


title: Explaining Constraint Programming

abstract: We discuss here constraint programming (CP) by using a proof-theoretic perspective. To this end we identify three levels of abstraction. Each level sheds light on the essence of CP. In particular, the highest level allows us to bring CP closer to the computation as deduction paradigm. At the middle level we can explain various constraint propagation algorithms. Finally, at the lowest level we can address the issue of automatic generation and optimization of the constraint propagation algorithms.


title: Analysis of Belief Propagation for Non-Linear Problems: The Example of CDMA (or: How to Prove Tanaka's Formula)

abstract: We consider the CDMA (code-division multiple-access) multi-user detection problem for binary signals and additive white gaussian noise. We propose a spreading sequences scheme based on random sparse signatures, and a detection algorithm based on belief propagation (BP) with linear time complexity. In the new scheme, each user conveys its power onto a finite number of chips l, in the large system limit. We analyze the performances of BP detection and prove that they coincide with the ones of optimal (symbol MAP) detection in the l->\infty limit. In the same limit, we prove that the information capacity of the system converges to Tanaka's formula for random `dense' signatures, thus providing the first rigorous justification of this formula. Apart from being computationally convenient, the new scheme allows for optimization in close analogy with irregular low density parity check code ensembles.


title: Approximate Weighted Farthest Neighbors and Minimum Dilation Stars

abstract: We provide an efficient reduction from the problem of querying approximate multiplicatively weighted farthest neighbors in a metric space to the unweighted problem. Combining our techniques with core-sets for approximate unweighted farthest neighbors, we show how to find (1+epsilon)-approximate farthest neighbors in time O(log n) per query in D-dimensional Euclidean space for any constants D and epsilon. As an application, we find an O(n log n) expected time algorithm for choosing the center of a star topology network connecting a given set of points, so as to approximately minimize the maximum dilation between any pair of points.


title: Single-Symbol Maximum Likelihood Decodable Linear STBCs

abstract: Space-Time block codes (STBC) from Orthogonal Designs (OD) and Co-ordinate Interleaved Orthogonal Designs (CIOD) have been attracting wider attention due to their amenability for fast (single-symbol) ML decoding, and full-rate with full-rank over quasi-static fading channels. However, these codes are instances of single-symbol decodable codes and it is natural to ask, if there exist codes other than STBCs form ODs and CIODs that allow single-symbol coding? In this paper, the above question is answered in the affirmative by characterizing all linear STBCs, that allow single-symbol ML decoding (not necessarily full-diversity) over quasi-static fading channels-calling them single-symbol decodable designs (SDD). The class SDD includes ODs and CIODs as proper subclasses. Further, among the SDD, a class of those that offer full-diversity, called Full-rank SDD (FSDD) are characterized and classified.


title: Classifying Signals with Local Classifiers

abstract: This paper deals with the problem of classifying signals. The new method for building so called local classifiers and local features is presented. The method is a combination of the lifting scheme and the support vector machines. Its main aim is to produce effective and yet comprehensible classifiers that would help in understanding processes hidden behind classified signals. To illustrate the method we present the results obtained on an artificial and a real dataset.


title: Finite-State Dimension and Real Arithmetic

abstract: We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+alpha, and q*alpha all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives a new proof of, Wall's 1949 theorem stating that the sum or product of a nonzero rational number and a Borel normal number is always Borel normal.