title: On the Information Rate of MIMO Systems with Finite Rate Channel State Feedback Using Beamforming and Power On/Off Strategy

abstract: It is well known that Multiple-Input Multiple-Output (MIMO) systems have high spectral efficiency, especially when channel state information at the transmitter (CSIT) is available. When CSIT is obtained by feedback, it is practical to assume that the channel state feedback rate is finite and the CSIT is not perfect. For such a system, we consider beamforming and power on/off strategy for its simplicity and near optimality, where power on/off means that a beamforming vector (beam) is either turned on with a constant power or turned off. The main contribution of this paper is to accurately evaluate the information rate as a function of the channel state feedback rate. Name a beam turned on as an on-beam and the minimum number of the transmit and receive antennas as the dimension of a MIMO system. We prove that the ratio of the optimal number of on-beams and the system dimension converges to a constant for a given signal-to-noise ratio (SNR) when the numbers of transmit and receive antennas approach infinity simultaneously and when beamforming is perfect. Asymptotic formulas are derived to evaluate this ratio and the corresponding information rate per dimension. The asymptotic results can be accurately applied to finite dimensional systems and suggest a power on/off strategy with a constant number of on-beams. For this suboptimal strategy, we take a novel approach to introduce power efficiency factor, which is a function of the feedback rate, to quantify the effect of imperfect beamforming. By combining power efficiency factor and the asymptotic formulas for perfect beamforming case, the information rate of the power on/off strategy with a constant number of on-beams is accurately characterized.


title: Locally Adaptive Block Thresholding Method with Continuity Constraint

abstract: We present an algorithm that enables one to perform locally adaptive block thresholding, while maintaining image continuity. Images are divided into sub-images based some standard image attributes and thresholding technique is employed over the sub-images. The present algorithm makes use of the thresholds of neighboring sub-images to calculate a range of values. The image continuity is taken care by choosing the threshold of the sub-image under consideration to lie within the above range. After examining the average range values for various sub-image sizes of a variety of images, it was found that the range of acceptable threshold values is substantially high, justifying our assumption of exploiting the freedom of range for bringing out local details.


title: The NoN Approach to Autonomic Face Recognition

abstract: A method of autonomic face recognition based on the biologically plausible network of networks (NoN) model of information processing is presented. The NoN model is based on locally parallel and globally coordinated transformations in which the neurons or computational units form distributed networks, which themselves link to form larger networks. This models the structures in the cerebral cortex described by Mountcastle and the architecture based on that proposed for information processing by Sutton. In the proposed implementation, face images are processed by a nested family of locally operating networks along with a hierarchically superior network that classifies the information from each of the local networks. The results of the experiments yielded a maximum of 98.5% recognition accuracy and an average of 97.4% recognition accuracy on a benchmark database.


title: Time-Space Trade-Offs for Predecessor Search

abstract: We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an explicit problem which breaks this communication complexity barrier. In addition, our bounds give the first separation between polynomial and near linear space. Such a separation is inherently impossible by communication complexity. Using our lower bound technique and new upper bound constructions, we obtain tight bounds for searching predecessors among a static set of integers. Given a set Y of n integers of l bits each, the goal is to efficiently find predecessor(x) = max{y in Y | y <= x}, by representing Y on a RAM using space S. In external memory, it follows that the optimal strategy is to use either standard B-trees, or a RAM algorithm ignoring the larger block size. In the important case of l = c*lg n, for c>1 (i.e. polynomial universes), and near linear space (such as S = n*poly(lg n)), the optimal search time is Theta(lg l). Thus, our lower bound implies the surprising conclusion that van Emde Boas' classic data structure from [FOCS'75] is optimal in this case. Note that for space n^{1+eps}, a running time of O(lg l / lglg l) was given by Beame and Fich [STOC'99].


title: First Steps in Relational Lattice

abstract: Relational lattice reduces the set of six classic relational algebra operators to two binary lattice operations: natural join and inner union. We give an introduction to this theory with emphasis on formal algebraic laws. New results include Spight distributivity criteria and its applications to query transformations.


title: Information and Errors in Quantum Teleportation

abstract: This article considers the question of the teleportation protocol from an engineering perspective. The protocol ideally requires an authority that ensures that the two communicating parties have a perfectly entangled pair of particles available to them. But this cannot be unconditionally established to the satisfaction of the parties due to the fact that an unknown quantum state cannot be copied. This supports the view that quantum information cannot be treated on the same basis as classical information.


title: Trusted Certificates in Quantum Cryptography

abstract: This paper analyzes the performance of Kak's three stage quantum cryptographic protocol based on public key cryptography against a man-in-the-middle attack. A method for protecting against such an attack is presented using certificates distributed by a trusted third party.


title: The Quantum Separability Problem for Gaussian States

abstract: Determining whether a quantum state is separable or entangled is a problem of fundamental importance in quantum information science. This is a brief review in which we consider the problem for states in infinite dimensional Hilbert spaces. We show how the problem becomes tractable for a class of Gaussian states.


title: Homogeneity vs. Adjacency: generalising some graph decomposition algorithms

abstract: In this paper, a new general decomposition theory inspired from modular graph decomposition is presented. Our main result shows that, within this general theory, most of the nice algorithmic tools developed for modular decomposition are still efficient. This theory not only unifies the usual modular decomposition generalisations such as modular decomposition of directed graphs or decomposition of 2-structures, but also star cutsets and bimodular decomposition. Our general framework provides a decomposition algorithm which improves the best known algorithms for bimodular decomposition.


title: State Space Realizations and Monomial Equivalence for Convolutional Codes

abstract: We will study convolutional codes with the help of state space realizations. It will be shown that two such minimal realizations belong to the same code if and only if they are equivalent under the full state feedback group. This result will be used in order to prove that two codes with positive Forney indices are monomially equivalent if and only if they share the same adjacency matrix. The adjacency matrix counts in a detailed way the weights of all possible outputs and thus contains full information about the weights of the codewords in the given code.


title: Multiple serial episode matching

abstract: In a previous paper we generalized the Knuth-Morris-Pratt (KMP) pattern matching algorithm and defined a non-conventional kind of RAM, the MP--RAMs (RAMS equipped with extra operations), and designed an O(n) on-line algorithm for solving the serial episode matching problem on MP--RAMs when there is only one single episode. We here give two extensions of this algorithm to the case when we search for several patterns simultaneously and compare them. More preciseley, given $q+1$ strings (a text $t$ of length $n$ and $q$ patterns $m\_1,...,m\_q$) and a natural number $w$, the {\em multiple serial episode matching problem} consists in finding the number of size $w$ windows of text $t$ which contain patterns $m\_1,...,m\_q$ as subsequences, i.e. for each $m\_i$, if $m\_i=p\_1,..., p\_k$, the letters $p\_1,..., p\_k$ occur in the window, in the same order as in $m\_i$, but not necessarily consecutively (they may be interleaved with other letters).} The main contribution is an algorithm solving this problem on-line in time $O(nq)$.


title: Transitive trust in mobile scenarios

abstract: Horizontal integration of access technologies to networks and services should be accompanied by some kind of convergence of authentication technologies. The missing link for the federation of user identities across the technological boundaries separating authentication methods can be provided by trusted computing platforms. The concept of establishing transitive trust by trusted computing enables the desired crossdomain authentication functionality. The focus of target application scenarios lies in the realm of mobile networks and devices.


title: Evaluation of interval extension of the power function by graph decomposition

abstract: The subject of our talk is the correct evaluation of interval extension of the function specified by the expression x^y without any constraints on the values of x and y. The core of our approach is a decomposition of the graph of x^y into a small number of parts which can be transformed into subsets of the graph of x^y for non-negative bases x. Because of this fact, evaluation of interval extension of x^y, without any constraints on x and y, is not much harder than evaluation of interval extension of x^y for non-negative bases x.


title: Automatic generation of simplified weakest preconditions for integrity constraint verification

abstract: Given a constraint $c$ assumed to hold on a database $B$ and an update $u$ to be performed on $B$, we address the following question: will $c$ still hold after $u$ is performed? When $B$ is a relational database, we define a confluent terminating rewriting system which, starting from $c$ and $u$, automatically derives a simplified weakest precondition $wp(c,u)$ such that, whenever $B$ satisfies $wp(c,u)$, then the updated database $u(B)$ will satisfy $c$, and moreover $wp(c,u)$ is simplified in the sense that its computation depends only upon the instances of $c$ that may be modified by the update. We then extend the definition of a simplified $wp(c,u)$ to the case of deductive databases; we prove it using fixpoint induction.


title: Testing Graph Isomorphism in Parallel by Playing a Game

abstract: Our starting point is the observation that if graphs in a class C have low descriptive complexity in first order logic, then the isomorphism problem for C is solvable by a fast parallel algorithm (essentially, by a simple combinatorial algorithm known as the multidimensional Weisfeiler-Lehman algorithm). Using this approach, we prove that isomorphism of graphs of bounded treewidth is testable in TC1, answering an open question posed by Chandrasekharan. Furthermore, we obtain an AC1 algorithm for testing isomorphism of rotation systems (combinatorial specifications of graph embeddings). The AC1 upper bound was known before, but the fact that this bound can be achieved by the simple Weisfeiler-Lehman algorithm is new. Combined with other known results, it also yields a new AC1 isomorphism algorithm for planar graphs.


title: Improved Watermarking Scheme Using Decimal Sequences

abstract: This paper presents watermarking algorithms using d-sequences so that the peak signal to noise ratio (PSNR) is maximized and the distortion introduced in the image due to the embedding is minimized. By exploiting the cross correlation property of decimal sequences, the concept of embedding more than one watermark in the same cover image is investigated.


title: Does the arXiv lead to higher citations and reduced publisher downloads for mathematics articles?

abstract: An analysis of 2,765 articles published in four math journals from 1997 to 2005 indicate that articles deposited in the arXiv received 35% more citations on average than non-deposited articles (an advantage of about 1.1 citations per article), and that this difference was most pronounced for highly-cited articles. Open Access, Early View, and Quality Differential were examined as three non-exclusive postulates for explaining the citation advantage. There was little support for a universal Open Access explanation, and no empirical support for Early View. There was some inferential support for a Quality Differential brought about by more highly-citable articles being deposited in the arXiv. In spite of their citation advantage, arXiv-deposited articles received 23% fewer downloads from the publisher's website (about 10 fewer downloads per article) in all but the most recent two years after publication. The data suggest that arXiv and the publisher's website may be fulfilling distinct functional needs of the reader.


title: Guard Placement For Wireless Localization

abstract: Motivated by secure wireless networking, we consider the problem of placing fixed localizers that enable mobile communication devices to prove they belong to a secure region that is defined by the interior of a polygon. Each localizer views an infinite wedge of the plane, and a device can prove membership in the secure region if it is inside the wedges for a set of localizers whose common intersection contains no points outside the polygon. This model leads to a broad class of new art gallery type problems, for which we provide upper and lower bounds.


title: Convergence of Min-Sum Message Passing for Quadratic Optimization

abstract: We establish the convergence of the min-sum message passing algorithm for minimization of a broad class of quadratic objective functions: those that admit a convex decomposition. Our results also apply to the equivalent problem of the convergence of Gaussian belief propagation.


title: Derivatives of Entropy Rate in Special Families of Hidden Markov Chains

abstract: Consider a hidden Markov chain obtained as the observation process of an ordinary Markov chain corrupted by noise. Zuk, et. al. [13], [14] showed how, in principle, one can explicitly compute the derivatives of the entropy rate of at extreme values of the noise. Namely, they showed that the derivatives of standard upper approximations to the entropy rate actually stabilize at an explicit finite time. We generalize this result to a natural class of hidden Markov chains called ``Black Holes.'' We also discuss in depth special cases of binary Markov chains observed in binary symmetric noise, and give an abstract formula for the first derivative in terms of a measure on the simplex due to Blackwell.


title: An Improved Exact Algorithm for the Domatic Number Problem

abstract: The 3-domatic number problem asks whether a given graph can be partitioned intothree dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695^n (up to polynomial factors). This result improves the previous bound of 2.8805^n, which is due to Fomin, Grandoni, Pyatkin, and Stepanov. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta(G) by a randomized algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta(G) >= 5. Our new randomized algorithm employs Schoening's approach to constraint satisfaction problems.


title: Quasi-Orthogonal STBC With Minimum Decoding Complexity

abstract: In this paper, we consider a quasi-orthogonal (QO) space-time block code (STBC) with minimum decoding complexity (MDC-QO-STBC). We formulate its algebraic structure and propose a systematic method for its construction. We show that a maximum-likelihood (ML) decoder for this MDC-QOSTBC, for any number of transmit antennas, only requires the joint detection of two real symbols. Assuming the use of a square or rectangular quadratic-amplitude modulation (QAM) or multiple phase-shift keying (MPSK) modulation for this MDC-QOSTBC, we also obtain the optimum constellation rotation angle, in order to achieve full diversity and optimum coding gain. We show that the maximum achievable code rate of these MDC-QOSTBC is 1 for three and four antennas and 3/4 for five to eight antennas. We also show that the proposed MDC-QOSTBC has several desirable properties, such as a more even power distribution among antennas and better scalability in adjusting the number of transmit antennas, compared with the coordinate interleaved orthogonal design (CIOD) and asymmetric CIOD (ACIOD) codes. For the case of an odd number of transmit antennas, MDC-QO-STBC also has better decoding performance than CIOD.


title: Implementation and Deployment of a Distributed Network Topology Discovery Algorithm

abstract: In the past few years, the network measurement community has been interested in the problem of internet topology discovery using a large number (hundreds or thousands) of measurement monitors. The standard way to obtain information about the internet topology is to use the traceroute tool from a small number of monitors. Recent papers have made the case that increasing the number of monitors will give a more accurate view of the topology. However, scaling up the number of monitors is not a trivial process. Duplication of effort close to the monitors wastes time by reexploring well-known parts of the network, and close to destinations might appear to be a distributed denial-of-service (DDoS) attack as the probes converge from a set of sources towards a given destination. In prior work, authors of this report proposed Doubletree, an algorithm for cooperative topology discovery, that reduces the load on the network, i.e., router IP interfaces and end-hosts, while discovering almost as many nodes and links as standard approaches based on traceroute. This report presents our open-source and freely downloadable implementation of Doubletree in a tool we call traceroute@home. We describe the deployment and validation of traceroute@home on the PlanetLab testbed and we report on the lessons learned from this experience. We discuss how traceroute@home can be developed further and discuss ideas for future improvements.


title: Unary Primitive Recursive Functions

abstract: In this article, we study some new characterizations of primitive recursive functions based on restricted forms of primitive recursion, improving the pioneering work of R. M. Robinson and M. D. Gladstone in this area. We reduce certain recursion schemes (mixed/pure iteration without parameters) and we characterize one-argument primitive recursive functions as the closure under substitution and iteration of certain optimal sets.


title: Guessing under source uncertainty

abstract: This paper considers the problem of guessing the realization of a finite alphabet source when some side information is provided. The only knowledge the guesser has about the source and the correlated side information is that the joint source is one among a family. A notion of redundancy is first defined and a new divergence quantity that measures this redundancy is identified. This divergence quantity shares the Pythagorean property with the Kullback-Leibler divergence. Good guessing strategies that minimize the supremum redundancy (over the family) are then identified. The min-sup value measures the richness of the uncertainty set. The min-sup redundancies for two examples - the families of discrete memoryless sources and finite-state arbitrarily varying sources - are then determined.


title: MIMO Broadcast Channels with Finite Rate Feedback

abstract: Multiple transmit antennas in a downlink channel can provide tremendous capacity (i.e. multiplexing) gains, even when receivers have only single antennas. However, receiver and transmitter channel state information is generally required. In this paper, a system where each receiver has perfect channel knowledge, but the transmitter only receives quantized information regarding the channel instantiation is analyzed. The well known zero forcing transmission technique is considered, and simple expressions for the throughput degradation due to finite rate feedback are derived. A key finding is that the feedback rate per mobile must be increased linearly with the SNR (in dB) in order to achieve the full multiplexing gain, which is in sharp contrast to point-to-point MIMO systems in which it is not necessary to increase the feedback rate as a function of the SNR.


title: A Feedback Reduction Technique for MIMO Broadcast Channels

abstract: A multiple antenna broadcast channel with perfect channel state information at the receivers is considered. If each receiver quantizes its channel knowledge to a finite number of bits which are fed back to the transmitter, the large capacity benefits of the downlink channel can be realized. However, the required number of feedback bits per mobile must be scaled with both the number of transmit antennas and the system SNR, and thus can be quite large in even moderately sized systems. It is shown that a small number of antennas can be used at each receiver to improve the quality of the channel estimate provided to the transmitter. As a result, the required feedback rate per mobile can be significantly decreased.


title: Implementing the Three-Stage Quantum Cryptography Protocol

abstract: We present simple implementations of Kak's three-stage quantum cryptography protocol. The case where the transformation is applied to more than one qubit at the same time is also considered.


title: Universal Lossless Compression with Unknown Alphabets - The Average Case

abstract: Universal compression of patterns of sequences generated by independently identically distributed (i.i.d.) sources with unknown, possibly large, alphabets is investigated. A pattern is a sequence of indices that contains all consecutive indices in increasing order of first occurrence. If the alphabet of a source that generated a sequence is unknown, the inevitable cost of coding the unknown alphabet symbols can be exploited to create the pattern of the sequence. This pattern can in turn be compressed by itself. It is shown that if the alphabet size $k$ is essentially small, then the average minimax and maximin redundancies as well as the redundancy of every code for almost every source, when compressing a pattern, consist of at least 0.5 log(n/k^3) bits per each unknown probability parameter, and if all alphabet letters are likely to occur, there exist codes whose redundancy is at most 0.5 log(n/k^2) bits per each unknown probability parameter, where n is the length of the data sequences. Otherwise, if the alphabet is large, these redundancies are essentially at least O(n^{-2/3}) bits per symbol, and there exist codes that achieve redundancy of essentially O(n^{-1/2}) bits per symbol. Two sub-optimal low-complexity sequential algorithms for compression of patterns are presented and their description lengths analyzed, also pointing out that the pattern average universal description length can decrease below the underlying i.i.d.\ entropy for large enough alphabets.


title: The neighbor-scattering number can be computed in polynomial time for interval graphs

abstract: Neighbor-scattering number is a useful measure for graph vulnerability. For some special kinds of graphs, explicit formulas are given for this number. However, for general graphs it is shown that to compute this number is NP-complete. In this paper, we prove that for interval graphs this number can be computed in polynomial time.


title: Predicting the Path of an Open System

abstract: The expected path of an open system,which is a big Poincare system,has been found in this paper.This path has been obtained from the actual and from the expected droop of the open system.The actual droop has been reconstructed from the variations in the power and in the frequency of the open system.The expected droop has been found as a function of rotation from the expected potential energy of the open system under synchronization of that system.


title: An Explicit Solution to Post's Problem over the Reals

abstract: In the BCSS model of real number computations we prove a concrete and explicit semi-decidable language to be undecidable yet not reducible from (and thus strictly easier than) the real Halting Language. This solution to Post's Problem over the reals significantly differs from its classical, discrete variant where advanced diagonalization techniques are only known to yield the existence of such intermediate Turing degrees. Strengthening the above result, we construct (that is, obtain again explicitly) as well an uncountable number of incomparable semi-decidable Turing degrees below the real Halting problem in the BCSS model. Finally we show the same to hold for the linear BCSS model, that is over (R,+,-,<) rather than (R,+,-,*,/,<).


title: Distributed Transmit Beamforming using Feedback Control

abstract: A simple feedback control algorithm is presented for distributed beamforming in a wireless network. A network of wireless sensors that seek to cooperatively transmit a common message signal to a Base Station (BS) is considered. In this case, it is well-known that substantial energy efficiencies are possible by using distributed beamforming. The feedback algorithm is shown to achieve the carrier phase coherence required for beamforming in a scalable and distributed manner. In the proposed algorithm, each sensor independently makes a random adjustment to its carrier phase. Assuming that the BS is able to broadcast one bit of feedback each timeslot about the change in received signal to noise ratio (SNR), the sensors are able to keep the favorable phase adjustments and discard the unfavorable ones, asymptotically achieving perfect phase coherence. A novel analytical model is derived that accurately predicts the convergence rate. The analytical model is used to optimize the algorithm for fast convergence and to establish the scalability of the algorithm.


title: VXA: A Virtual Architecture for Durable Compressed Archives

abstract: Data compression algorithms change frequently, and obsolete decoders do not always run on new hardware and operating systems, threatening the long-term usability of content archived using those algorithms. Re-encoding content into new formats is cumbersome, and highly undesirable when lossy compression is involved. Processor architectures, in contrast, have remained comparatively stable over recent decades. VXA, an archival storage system designed around this observation, archives executable decoders along with the encoded content it stores. VXA decoders run in a specialized virtual machine that implements an OS-independent execution environment based on the standard x86 architecture. The VXA virtual machine strictly limits access to host system services, making decoders safe to run even if an archive contains malicious code. VXA's adoption of a "native" processor architecture instead of type-safe language technology allows reuse of existing "hand-optimized" decoders in C and assembly language, and permits decoders access to performance-enhancing architecture features such as vector processing instructions. The performance cost of VXA's virtualization is typically less than 15% compared with the same decoders running natively. The storage cost of archived decoders, typically 30-130KB each, can be amortized across many archived files sharing the same compression method.


title: Peer-to-Peer Communication Across Network Address Translators

abstract: Network Address Translation (NAT) causes well-known difficulties for peer-to-peer (P2P) communication, since the peers involved may not be reachable at any globally valid IP address. Several NAT traversal techniques are known, but their documentation is slim, and data about their robustness or relative merits is slimmer. This paper documents and analyzes one of the simplest but most robust and practical NAT traversal techniques, commonly known as "hole punching." Hole punching is moderately well-understood for UDP communication, but we show how it can be reliably used to set up peer-to-peer TCP streams as well. After gathering data on the reliability of this technique on a wide variety of deployed NATs, we find that about 82% of the NATs tested support hole punching for UDP, and about 64% support hole punching for TCP streams. As NAT vendors become increasingly conscious of the needs of important P2P applications such as Voice over IP and online gaming protocols, support for hole punching is likely to increase in the future.


title: Unmanaged Internet Protocol: Taming the Edge Network Management Crisis

abstract: Though appropriate for core Internet infrastructure, the Internet Protocol is unsuited to routing within and between emerging ad-hoc edge networks due to its dependence on hierarchical, administratively assigned addresses. Existing ad-hoc routing protocols address the management problem but do not scale to Internet-wide networks. The promise of ubiquitous network computing cannot be fulfilled until we develop an Unmanaged Internet Protocol (UIP), a scalable routing protocol that manages itself automatically. UIP must route within and between constantly changing edge networks potentially containing millions or billions of nodes, and must still function within edge networks disconnected from the main Internet, all without imposing the administrative burden of hierarchical address assignment. Such a protocol appears challenging but feasible. We propose an architecture based on self-certifying, cryptographic node identities and a routing algorithm adapted from distributed hash tables.


title: User-Relative Names for Globally Connected Personal Devices

abstract: Nontechnical users who own increasingly ubiquitous network-enabled personal devices such as laptops, digital cameras, and smart phones need a simple, intuitive, and secure way to share information and services between their devices. User Information Architecture, or UIA, is a novel naming and peer-to-peer connectivity architecture addressing this need. Users assign UIA names by "introducing" devices to each other on a common local-area network, but these names remain securely bound to their target as devices migrate. Multiple devices owned by the same user, once introduced, automatically merge their namespaces to form a distributed "personal cluster" that the owner can access or modify from any of his devices. Instead of requiring users to allocate globally unique names from a central authority, UIA enables users to assign their own "user-relative" names both to their own devices and to other users. With UIA, for example, Alice can always access her iPod from any of her own personal devices at any location via the name "ipod", and her friend Bob can access her iPod via a relative name like "ipod.Alice".


title: Packrat Parsing: Simple, Powerful, Lazy, Linear Time

abstract: Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language. A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time. Any language defined by an LL(k) or LR(k) grammar can be recognized by a packrat parser, in addition to many languages that conventional linear-time algorithms do not support. This additional power simplifies the handling of common syntactic idioms such as the widespread but troublesome longest-match rule, enables the use of sophisticated disambiguation strategies such as syntactic and semantic predicates, provides better grammar composition properties, and allows lexical analysis to be integrated seamlessly into parsing. Yet despite its power, packrat parsing shares the same simplicity and elegance as recursive descent parsing; in fact converting a backtracking recursive descent parser into a linear-time packrat parser often involves only a fairly straightforward structural change. This paper describes packrat parsing informally with emphasis on its use in practical applications, and explores its advantages and disadvantages with respect to the more conventional alternatives.


title: Consensus Propagation

abstract: We propose consensus propagation, an asynchronous distributed protocol for averaging numbers across a network. We establish convergence, characterize the convergence rate for regular graphs, and demonstrate that the protocol exhibits better scaling properties than pairwise averaging, an alternative that has received much recent attention. Consensus propagation can be viewed as a special case of belief propagation, and our results contribute to the belief propagation literature. In particular, beyond singly-connected graphs, there are very few classes of relevant problems for which belief propagation is known to converge.


title: A compositional Semantics for CHR

abstract: Constraint Handling Rules (CHR) are a committed-choice declarative language which has been designed for writing constraint solvers. A CHR program consists of multi-headed guarded rules which allow one to rewrite constraints into simpler ones until a solved form is reached. CHR has received a considerable attention, both from the practical and from the theoretical side. Nevertheless, due the use of multi-headed clauses, there are several aspects of the CHR semantics which have not been clarified yet. In particular, no compositional semantics for CHR has been defined so far. In this paper we introduce a fix-point semantics which characterizes the input/output behavior of a CHR program and which is and-compositional, that is, which allows to retrieve the semantics of a conjunctive query from the semantics of its components. Such a semantics can be used as a basis to define incremental and modular analysis and verification tools.


title: Yet Another Efficient Unification Algorithm

abstract: The unification algorithm is at the core of the logic programming paradigm, the first unification algorithm being developed by Robinson [5]. More efficient algorithms were developed later [3] and I introduce here yet another efficient unification algorithm centered on a specific data structure, called the Unification Table.


title: Application of Support Vector Regression to Interpolation of Sparse Shock Physics Data Sets

abstract: Shock physics experiments are often complicated and expensive. As a result, researchers are unable to conduct as many experiments as they would like - leading to sparse data sets. In this paper, Support Vector Machines for regression are applied to velocimetry data sets for shock damaged and melted tin metal. Some success at interpolating between data sets is achieved. Implications for future work are discussed.


title: Solving Sparse Integer Linear Systems

abstract: We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with structured blocks. It achieves a sub-cubic complexity in terms of machine operations subject to a conjecture on the effectiveness of certain sparse projections. A LinBox-based implementation of this algorithm is demonstrated, and emphasizes the practical benefits of this new method over the previous state of the art.


title: Entropy-optimal Generalized Token Bucket Regulator

abstract: We derive the maximum entropy of a flow (information utility) which conforms to traffic constraints imposed by a generalized token bucket regulator, by taking into account the covert information present in the randomness of packet lengths. Under equality constraints of aggregate tokens and aggregate bucket depth, a generalized token bucket regulator can achieve higher information utility than a standard token bucket regulator. The optimal generalized token bucket regulator has a near-uniform bucket depth sequence and a decreasing token increment sequence.


title: Random 3CNF formulas elude the Lovasz theta function

abstract: Let $\phi$ be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisfiable. It is an open question whether there is an efficient refutation algorithm that for most such formulas proves that they are not satisfiable. A possible approach to refute a formula $\phi$ is: first, translate it into a graph $G_{\phi}$ using a generic reduction from 3-SAT to max-IS, then bound the maximum independent set of $G_{\phi}$ using the Lovasz $\vartheta$ function. If the $\vartheta$ function returns a value $< m$, this is a certificate for the unsatisfiability of $\phi$. We show that for random formulas with $m < n^{3/2 -o(1)}$ clauses, the above approach fails, i.e. the $\vartheta$ function is likely to return a value of m.


title: Access Control for Hierarchical Joint-Tenancy

abstract: Basic role based access control [RBAC] provides a mechanism for segregating access privileges based upon a user's hierarchical roles within an organization. This model doesn't scale well when there is tight integration of multiple hierarchies. In a case where there is joint-tenancy and a requirement for different levels of disclosure based upon a user's hierarchy, or in our case, organization or company, basic RBAC requires these hierarchies to be effectively merged. Specific roles that effectively represent both the user's organizations and roles must be translated to fit within the merged hierarchy to be used to control access. Essentially, users from multiple organizations are served from a single role base with roles designed to constrain their access as needed. Our work proposes, through parameterized roles and privileges, a means for accurately representing both users' roles within their respective hierarchies for providing access to controlled objects. Using this method will reduce the amount of complexity required in terms of the number of roles and privileges. The resulting set of roles, privileges, and objects will make modeling and visualizing the access role hierarchy significantly simplified. This paper will give some background on role based access control, parameterized roles and privileges, and then focus on how RBAC with parameterized roles and privileges can be leveraged as an access control solution for the problems presented by joint tenancy.


title: Matching Edges in Images ; Application to Face Recognition

abstract: This communication describes a representation of images as a set of edges characterized by their position and orientation. This representation allows the comparison of two images and the computation of their similarity. The first step in this computation of similarity is the seach of a geometrical basis of the two dimensional space where the two images are represented simultaneously after transformation of one of them. Presently, this simultaneous representation takes into account a shift and a scaling ; it may be extended to rotations or other global geometrical transformations. An elementary probabilistic computation shows that a sufficient but not excessive number of trials (a few tens) ensures that the exhibition of this common basis is guaranteed in spite of possible errors in the detection of edges. When this first step is performed, the search of similarity between the two images reduces to counting the coincidence of edges in the two images. The approach may be applied to many problems of pattern matching ; it was checked on face recognition.


title: IP over P2P: Enabling Self-configuring Virtual IP Networks for Grid Computing

abstract: Peer-to-peer (P2P) networks have mostly focused on task oriented networking, where networks are constructed for single applications, i.e. file-sharing, DNS caching, etc. In this work, we introduce IPOP, a system for creating virtual IP networks on top of a P2P overlay. IPOP enables seamless access to Grid resources spanning multiple domains by aggregating them into a virtual IP network that is completely isolated from the physical network. The virtual IP network provided by IPOP supports deployment of existing IP-based protocols over a robust, self-configuring P2P overlay. We present implementation details as well as experimental measurement results taken from LAN, WAN, and Planet-Lab tests.


title: Novel BCD Adders and Their Reversible Logic Implementation for IEEE 754r Format

abstract: IEEE 754r is the ongoing revision to the IEEE 754 floating point standard and a major enhancement to the standard is the addition of decimal format. This paper proposes two novel BCD adders called carry skip and carry look-ahead BCD adders respectively. Furthermore, in the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nanotechnology, and optical computing. It is not possible to realize quantum computing without reversible logic. Thus, this paper also paper provides the reversible logic implementation of the conventional BCD adder as the well as the proposed Carry Skip BCD adder using a recently proposed TSG gate. Furthermore, a new reversible gate called TS-3 is also being proposed and it has been shown that the proposed reversible logic implementation of the BCD Adders is much better compared to recently proposed one, in terms of number of reversible gates used and garbage outputs produced. The reversible BCD circuits designed and proposed here form the basis of the decimal ALU of a primitive quantum CPU.


title: Convex Separation from Optimization via Heuristics

abstract: Let $K$ be a full-dimensional convex subset of $\mathbb{R}^n$. We describe a new polynomial-time Turing reduction from the weak separation problem for $K$ to the weak optimization problem for $K$ that is based on a geometric heuristic. We compare our reduction, which relies on analytic centers, with the standard, more general reduction.


title: Topological Grammars for Data Approximation

abstract: A method of {\it topological grammars} is proposed for multidimensional data approximation. For data with complex topology we define a {\it principal cubic complex} of low dimension and given complexity that gives the best approximation for the dataset. This complex is a generalization of linear and non-linear principal manifolds and includes them as particular cases. The problem of optimal principal complex construction is transformed into a series of minimization problems for quadratic functionals. These quadratic functionals have a physically transparent interpretation in terms of elastic energy. For the energy computation, the whole complex is represented as a system of nodes and springs. Topologically, the principal complex is a product of one-dimensional continuums (represented by graphs), and the grammars describe how these continuums transform during the process of optimal complex construction. This factorization of the whole process onto one-dimensional transformations using minimization of quadratic energy functionals allow us to construct efficient algorithms.


title: A New Reversible TSG Gate and Its Application For Designing Efficient Adder Circuits

abstract: In the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nanotechnology, and optical computing. The classical set of gates such as AND, OR, and EXOR are not reversible. This paper proposes a new 4 * 4 reversible gate called TSG gate. The proposed gate is used to design efficient adder units. The most significant aspect of the proposed gate is that it can work singly as a reversible full adder i.e reversible full adder can now be implemented with a single gate only. The proposed gate is then used to design reversible ripple carry and carry skip adders. It is demonstrated that the adder architectures designed using the proposed gate are much better and optimized, compared to their existing counterparts in literature; in terms of number of reversible gates and garbage outputs. Thus, this paper provides the initial threshold to building of more complex system which can execute more complicated operations using reversible logic.


title: An Extension to DNA Based Fredkin Gate Circuits: Design of Reversible Sequential Circuits using Fredkin Gates

abstract: In recent years, reversible logic has emerged as a promising computing paradigm having its applications in low power computing, quantum computing, nanotechnology, optical computing and DNA computing. The classical set of gates such as AND, OR, and EXOR are not reversible. Recently, it has been shown how to encode information in DNA and use DNA amplification to implement Fredkin gates. Furthermore, in the past Fredkin gates have been constructed using DNA, whose outputs are used as inputs for other Fredkin gates. Thus, it can be concluded that arbitrary circuits of Fredkin gates can be constructed using DNA. This paper provides the initial threshold to building of more complex system having reversible sequential circuits and which can execute more complicated operations. The novelty of the paper is the reversible designs of sequential circuits using Fredkin gate. Since, Fredkin gate has already been realized using DNA, it is expected that this work will initiate the building of complex systems using DNA. The reversible circuits designed here are highly optimized in terms of number of gates and garbage outputs. The modularization approach that is synthesizing small circuits and thereafter using them to construct bigger circuits is used for designing the optimal reversible sequential circuits.


title: About the domino problem in the hyperbolic plane from an algorithmic point of view

abstract: In this paper, we prove that the general problem of tiling the hyperbolic plane with \`a la Wang tiles is undecidable.


title: On the Capacity Achieving Transmit Covariance Matrices of MIMO Correlated Rician Channels: A Large System Approach

abstract: We determine the capacity-achieving input covariance matrices for coherent block-fading correlated MIMO Rician channels. In contrast with the Rayleigh and uncorrelated Rician cases, no closed-form expressions for the eigenvectors of the optimum input covariance matrix are available. Both the eigenvectors and eigenvalues have to be evaluated by using numerical techniques. As the corresponding optimization algorithms are not very attractive, we evaluate the limit of the average mutual information when the number of transmit and receive antennas converge to infinity at the same rate. If the channel is semi-correlated, we propose an attractive optimization algorithm of the large system approximant, and establish some convergence results. Simulation results show that our approach provide reliable results even for a quite moderate number of transmit and receive antennas.


title: A Turbo Coding System for High Speed Communications

abstract: Conventional turbo codes (CTCs) usually employ a block-oriented interleaving so that each block is separately encoded and decoded. As interleaving and de-interleaving are performed within a block, the message-passing process associated with an iterative decoder is limited to proceed within the corresponding range. This paper presents a new turbo coding scheme that uses a special interleaver structure and a multiple-round early termination test involving both sign check and a CRC code. The new interleaver structure is naturally suited for high speed parallel processing and the resulting coding system offers new design options and tradeoffs that are not available to CTCs. In particular, it becomes possible for the decoder to employ an efficient inter-block collaborative decoding algorithm, passing the information obtained from termination test proved blocks to other unproved blocks. It also becomes important to have a proper decoding schedule. The combined effect is improved performance and reduction in the average decoding delay (whence the required computing power). A memory (storage) management mechanism is included as a critical part of the decoder so as to provide additional design tradeoff between performance and memory size. It is shown that the latter has a modular-like effect in that additional memory units render enhanced performance due not only to less forced early terminations but to possible increases of the interleaving depth. Depending on the decoding schedule, the degree of parallelism and other decoding resources available, the proposed scheme admits a variety of decoder architectures that meet a large range of throughput and performance demands.


title: On Reduced Complexity Soft-Output MIMO ML detection

abstract: In multiple-input multiple-output (MIMO) fading channels maximum likelihood (ML) detection is desirable to achieve high performance, but its complexity grows exponentially with the spectral efficiency. The current state of the art in MIMO detection is list decoding and lattice decoding. This paper proposes a new class of lattice detectors that combines some of the principles of both list and lattice decoding, thus resulting in an efficient parallelizable implementation and near optimal soft-ouput ML performance. The novel detector is called layered orthogonal lattice detector (LORD), because it adopts a new lattice formulation and relies on a channel orthogonalization process. It should be noted that the algorithm achieves optimal hard-output ML performance in case of two transmit antennas. For two transmit antennas max-log bit soft-output information can be generated and for greater than two antennas approximate max-log detection is achieved. Simulation results show that LORD, in MIMO system employing orthogonal frequency division multiplexing (OFDM) and bit interleaved coded modulation (BICM) is able to achieve very high signal-to-noise ratio (SNR) gains compared to practical soft-output detectors such as minimum-mean square error (MMSE), in either linear or nonlinear iterative scheme. Besides, the performance comparison with hard-output decoded algebraic space time codes shows the fundamental importance of soft-output generation capability for practical wireless applications.


title: On Pinsker's Type Inequalities and Csiszar's f-divergences. Part I: Second and Fourth-Order Inequalities

abstract: We study conditions on $f$ under which an $f$-divergence $D_f$ will satisfy $D_f \geq c_f V^2$ or $D_f \geq c_{2,f} V^2 + c_{4,f} V^4$, where $V$ denotes variational distance and the coefficients $c_f$, $c_{2,f}$ and $c_{4,f}$ are {\em best possible}. As a consequence, we obtain lower bounds in terms of $V$ for many well known distance and divergence measures. For instance, let $D_{(\alpha)} (P,Q) = [\alpha (\alpha-1)]^{-1} [\int q^{\alpha} p^{1-\alpha} d \mu -1]$ and ${\cal I}_\alpha (P,Q) = (\alpha -1)^{-1} \log [\int p^\alpha q^{1-\alpha} d \mu]$ be respectively the {\em relative information of type} ($1-\alpha$) and {\em R\'{e}nyi's information gain of order} $\alpha$. We show that $D_{(\alpha)} \geq {1/2} V^2 + {1/72} (\alpha+1)(2-\alpha) V^4$ whenever $-1 \leq \alpha \leq 2$, $\alpha \not= 0,1$ and that ${\cal I}_{\alpha} = \frac{\alpha}{2} V^2 + {1/36} \alpha (1 + 5 \alpha - 5 \alpha^2) V^4$ for $0 < \alpha < 1$. Pinsker's inequality $D \geq {1/2} V^2$ and its extension $D \geq {1/2} V^2 + {1/36} V^4$ are special cases of each one of these.


title: A SIMO Fiber Aided Wireless Network Architecture

abstract: The concept of a fiber aided wireless network architecture (FAWNA) is introduced in [Ray et al., Allerton Conference 2005], which allows high-speed mobile connectivity by leveraging the speed of optical networks. In this paper, we consider a single-input, multiple-output (SIMO) FAWNA, which consists of a SIMO wireless channel and an optical fiber channel, connected through wireless-optical interfaces. We propose a scheme where the received wireless signal at each interface is quantized and sent over the fiber. Though our architecture is similar to that of the classical CEO problem, our problem is different from it. We show that the capacity of our scheme approaches the capacity of the architecture, exponentially with fiber capacity. We also show that for a given fiber capacity, there is an optimal operating wireless bandwidth and an optimal number of wireless-optical interfaces. The wireless-optical interfaces of our scheme have low complexity and do not require knowledge of the transmitter code book. They are also extendable to FAWNAs with large number of transmitters and interfaces and, offer adaptability to variable rates, changing channel conditions and node positions.


title: Benchmark Problems for Constraint Solving

abstract: Constraint Programming is roughly a new software technology introduced by Jaffar and Lassez in 1987 for description and effective solving of large, particularly combinatorial, problems especially in areas of planning and scheduling. In the following we define three problems for constraint solving from the domain of electrical networks; based on them we define 43 related problems. For the defined set of problems we benchmarked five systems: ILOG OPL, AMPL, GAMS, Mathematica and UniCalc. As expected some of the systems performed very well for some problems while others performed very well on others.


title: Efficient Compression of Prolog Programs

abstract: We propose a special-purpose class of compression algorithms for efficient compression of Prolog programs. It is a dictionary-based compression method, specially designed for the compression of Prolog code, and therefore we name it PCA (Prolog Compression Algorithm). According to the experimental results this method provides better compression than state-of-the-art general-purpose compression algorithms. Since the algorithm works with Prolog syntactic entities (e.g. atoms, terms, etc.) the implementation of a Prolog prototype is straightforward and very easy to use in any Prolog application that needs compression. Although the algorithm is designed for Prolog programs, the idea can be easily applied for the compression of programs written in other (logic) languages.


title: Prolog Server Pages

abstract: Prolog Server Pages (PSP) is a scripting language, based on Prolog, than can be embedded in HTML documents. To run PSP applications one needs a web server, a web browser and a PSP interpreter. The code is executed, by the interpreter, on the server-side (web server) and the output (together with the html code in witch the PSP code is embedded) is sent to the client-side (browser). The current implementation supports Apache Web Server. We implemented an Apache web server module that handles PSP files, and sends the result (an html document) to the client. PSP supports both GET and POST http requests. It also provides methods for working with http cookies.


title: Enhanced Prolog Remote Predicate Call Protocol

abstract: Following the ideas of the Remote Procedure Call model, we have developed a logic programming counterpart, naturally called Prolog Remote Predicate Call (Prolog RPC). The Prolog RPC protocol facilitates the integration of Prolog code in multi-language applications as well as the development of distributed intelligent applications. One use of the protocol's most important uses could be the development of distributed applications that use Prolog at least partially to achieve their goals. Most notably the Distributed Artificial Intelligence (DAI) applications that are suitable for logic programming can profit from the use of the protocol. After proving its usefulness, we went further, developing a new version of the protocol, making it more reliable and extending its functionality. Because it has a new syntax and the new set of commands, we call this version Enhanced Prolog Remote Procedure Call. This paper describes the new features and modifications this second version introduced.


title: Bargaining over the interference channel

abstract: In this paper we analyze the interference channel as a conflict situation. This viewpoint implies that certain points in the rate region are unreasonable to one of the players. Therefore these points cannot be considered achievable based on game theoretic considerations. We then propose to use Nash bargaining solution as a tool that provides preferred points on the boundary of the game theoretic rate region. We provide analysis for the 2x2 intereference channel using the FDM achievable rate region. We also outline how to generalize our results to other achievable rate regions for the interference channel as well as the multiple access channel. Keywords: Spectrum optimization, distributed coordination, game theory, interference channel, multiple access channel.


title: Verification of Ptime reducibility for system F terms via Dual Light Affine Logic

abstract: In a previous work we introduced Dual Light Affine Logic (DLAL) ([BaillotTerui04]) as a variant of Light Linear Logic suitable for guaranteeing complexity properties on lambda-calculus terms: all typable terms can be evaluated in polynomial time and all Ptime functions can be represented. In the present work we address the problem of typing lambda-terms in second-order DLAL. For that we give a procedure which, starting with a term typed in system F, finds all possible ways to decorate it into a DLAL typed term. We show that our procedure can be run in time polynomial in the size of the original Church typed system F term.


title: A unifying framework for seed sensitivity and its application to subset seeds (Extended abstract)

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: Estimating seed sensitivity on homogeneous alignments

abstract: We address the problem of estimating the sensitivity of seed-based similarity search algorithms. In contrast to approaches based on Markov models [18, 6, 3, 4, 10], we study the estimation based on homogeneous alignments. We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies. We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.


title: Towards an information-theoretically safe cryptographic protocol

abstract: We introduce what --if some kind of group action exists-- is a truly (information theoretically) safe cryptographic communication system: a protocol which provides \emph{zero} information to any passive adversary having full access to the channel.


title: Minimizing Symmetric Set Functions Faster

abstract: We describe a combinatorial algorithm which, given a monotone and consistent symmetric set function d on a finite set V in the sense of Rizzi, constructs a non trivial set S minimizing d(S,V-S). This includes the possibility for the minimization of symmetric submodular functions. The presented algorithm requires at most as much time as the one described by Rizzi, but depending on the function d, it may allow several improvements.


title: Encoding of Functions of Correlated Sources

abstract: This submission is being withdrawn due to serious errors in the achievability proofs. The reviewers of the journal I had submitted to had found errors back in 2006. I had forgotten about this paper until I saw the CFP for a JSAC issue on in-network computation. http://www.jsac.ucsd.edu/Calls/in-networkcomputationcfp.pdf.


title: Asymptotic Learnability of Reinforcement Problems with Arbitrary Dependence

abstract: We address the problem of reinforcement learning in which observations may exhibit an arbitrary form of stochastic dependence on past observations and actions. The task for an agent is to attain the best possible asymptotic reward where the true generating environment is unknown but belongs to a known countable family of environments. We find some sufficient conditions on the class of environments under which an agent exists which attains the best asymptotic reward for any environment in the class. We analyze how tight these conditions are and how they relate to different probabilistic assumptions known in reinforcement learning and related fields, such as Markov Decision Processes and mixing conditions.


title: Remote-control and clustering of physical computations using the XML-RPC protocol and the open-Mosix system

abstract: The applications of the remote control of physical simulations performed in clustered computers running under an open-Mosix system are presented. Results from the simulation of a 2-dimensional ferromagnetic system of spins in the Ising scheme are provided. Basic parameters of a simulated hysteresis loop like coercivity and exchange bias due to pinning of ferromagnetic spins are given. The paper describes in physicists terminology a cost effective solution which utilizes an XML-RPC protocol (Extensible Markup Language - Remote Procedure Calling) and standard C++ and Python languages.


title: A General Framework for Scalability and Performance Analysis of DHT Routing Systems

abstract: In recent years, many DHT-based P2P systems have been proposed, analyzed, and certain deployments have reached a global scale with nearly one million nodes. One is thus faced with the question of which particular DHT system to choose, and whether some are inherently more robust and scalable. Toward developing such a comparative framework, we present the reachable component method (RCM) for analyzing the performance of different DHT routing systems subject to random failures. We apply RCM to five DHT systems and obtain analytical expressions that characterize their routability as a continuous function of system size and node failure probability. An important consequence is that in the large-network limit, the routability of certain DHT systems go to zero for any non-zero probability of node failure. These DHT routing algorithms are therefore unscalable, while some others, including Kademlia, which powers the popular eDonkey P2P system, are found to be scalable.


title: Mathematical Modeling of Aerodynamic Space -to - Surface Flight with Trajectory for Avoid Intercepting Process

abstract: Modeling has been created for a Space-to-Surface system defined for an optimal trajectory for targeting in terminal phase with avoids an intercepting process. The modeling includes models for simulation atmosphere, speed of sound, aerodynamic flight and navigation by an infrared system. The modeling and simulation includes statistical analysis of the modeling results.


title: Using SMART for Customized Monitoring of Windows Services

abstract: We focus on examining and working with an important category of computer software called Services, which are provided as a part of newer Microsoft Windows operating systems. A typical Windows user transparently utilizes many of these services but is frequently unaware of their existence. Since some services have the potential to create significant problems when they are executing, it is important for a system administrator to identify which services are running on the network, the types of processing done by each service, and any interrelationships among the various services. This information can then be used to improve the overall integrity of both the individual computer where a questionable service is running and in aggregate an entire network of computers. NCSA has developed an application called SMART (Services Monitoring And Reporting Tool) that can be used to identify and display all services currently running in the network. A commercial program called Hyena remotely monitors the services on all computers attached to the network and exports this information to SMART. SMART produces various outputs that the system administrator can analyze and then determine appropriate actions to take. In particular, SMART provides a color coordinated user interface to quickly identify and classify both potentially hazardous services and also unknown services.


title: Implementation of float-float operators on graphics hardware

abstract: The Graphic Processing Unit (GPU) has evolved into a powerful and flexible processor. The latest graphic processors provide fully programmable vertex and pixel processing units that support vector operations up to single floating-point precision. This computational power is now being used for general-purpose computations. However, some applications require higher precision than single precision. This paper describes the emulation of a 44-bit floating-point number format and its corresponding operations. An implementation is presented along with performance and accuracy results.


title: Fourier Analysis and Holographic Representations of 1D and 2D Signals

abstract: In this paper, we focus on Fourier analysis and holographic transforms for signal representation. For instance, in the case of image processing, the holographic representation has the property that an arbitrary portion of the transformed image enables reconstruction of the whole image with details missing. We focus on holographic representation defined through the Fourier Transforms. Thus, We firstly review some results in Fourier transform and Fourier series. Next, we review the Discrete Holographic Fourier Transform (DHFT) for image representation. Then, we describe the contributions of our work. We show a simple scheme for progressive transmission based on the DHFT. Next, we propose the Continuous Holographic Fourier Transform (CHFT) and discuss some theoretical aspects of it for 1D signals. Finally, some testes are presented in the experimental results


title: Affine functions and series with co-inductive real numbers

abstract: We extend the work of A. Ciaffaglione and P. Di Gianantonio on mechanical verification of algorithms for exact computation on real numbers, using infinite streams of digits implemented as co-inductive types. Four aspects are studied: the first aspect concerns the proof that digit streams can be related to the axiomatized real numbers that are already axiomatized in the proof system (axiomatized, but with no fixed representation). The second aspect re-visits the definition of an addition function, looking at techniques to let the proof search mechanism perform the effective construction of an algorithm that is correct by construction. The third aspect concerns the definition of a function to compute affine formulas with positive rational coefficients. This should be understood as a testbed to describe a technique to combine co-recursion and recursion to obtain a model for an algorithm that appears at first sight to be outside the expressive power allowed by the proof system. The fourth aspect concerns the definition of a function to compute series, with an application on the series that is used to compute Euler's number e. All these experiments should be reproducible in any proof system that supports co-inductive types, co-recursion and general forms of terminating recursion, but we performed with the Coq system [12, 3, 14].


title: Coq in a Hurry

abstract: These notes provide a quick introduction to the Coq system and show how it can be used to define logical concepts and functions and reason about them. It is designed as a tutorial, so that readers can quickly start their own experiments, learning only a few of the capabilities of the system. A much more comprehensive study is provided in [1], which also provides an extensive collection of exercises to train on.


title: CoInduction in Coq

abstract: We describe the basic notions of co-induction as they are available in the coq system. As an application, we describe arithmetic properties for simple representations of real numbers.


title: Approximation Algorithms for K-Modes Clustering

abstract: In this paper, we study clustering with respect to the k-modes objective function, a natural formulation of clustering for categorical data. One of the main contributions of this paper is to establish the connection between k-modes and k-median, i.e., the optimum of k-median is at most twice the optimum of k-modes for the same categorical data clustering problem. Based on this observation, we derive a deterministic algorithm that achieves an approximation factor of 2. Furthermore, we prove that the distance measure in k-modes defines a metric. Hence, we are able to extend existing approximation algorithms for metric k-median to k-modes. Empirical results verify the superiority of our method.


title: minimUML: A Minimalist Approach to UML Diagraming for Early Computer Science Education

abstract: The Unified Modeling Language (UML) is commonly used in introductory Computer Science to teach basic object-oriented design. However, there appears to be a lack of suitable software to support this task. Many of the available programs that support UML focus on developing code and not on enhancing learning. Those that were designed for educational use sometimes have poor interfaces or are missing common and important features, such as multiple selection and undo/redo. There is a need for software that is tailored to an instructional environment and has all the useful and needed functionality for that specific task. This is the purpose of minimUML. minimUML provides a minimum amount of UML, just what is commonly used in beginning programming classes, while providing a simple, usable interface. In particular, minimUML was designed to support abstract design while supplying features for exploratory learning and error avoidance. In addition, it allows for the annotation of diagrams, through text or freeform drawings, so students can receive feedback on their work. minimUML was developed with the goal of supporting ease of use, supporting novice students, and a requirement of no prior-training for its use.


title: Complexity of Monadic inf-datalog. Application to temporal logic

abstract: In [11] we defined Inf-Datalog and characterized the fragments of Monadic inf-Datalog that have the same expressive power as Modal Logic (resp. $CTL$, alternation-free Modal $\mu$-calculus and Modal $\mu$-calculus). We study here the time and space complexity of evaluation of Monadic inf-Datalog programs on finite models. We deduce a new unified proof that model checking has 1. linear data and program complexities (both in time and space) for $CTL$ and alternation-free Modal $\mu$-calculus, and 2. linear-space (data and program) complexities, linear-time program complexity and polynomial-time data complexity for $L\mu\_k$ (Modal $\mu$-calculus with fixed alternation-depth at most $k$).}


title: Towards the Optimal Amplify-and-Forward Cooperative Diversity Scheme

abstract: In a slow fading channel, how to find a cooperative diversity scheme that achieves the transmit diversity bound is still an open problem. In fact, all previously proposed amplify-and-forward (AF) and decode-and-forward (DF) schemes do not improve with the number of relays in terms of the diversity multiplexing tradeoff (DMT) for multiplexing gains r higher than 0.5. In this work, we study the class of slotted amplify-and-forward (SAF) schemes. We first establish an upper bound on the DMT for any SAF scheme with an arbitrary number of relays N and number of slots M. Then, we propose a sequential SAF scheme that can exploit the potential diversity gain in the high multiplexing gain regime. More precisely, in certain conditions, the sequential SAF scheme achieves the proposed DMT upper bound which tends to the transmit diversity bound when M goes to infinity. In particular, for the two-relay case, the three-slot sequential SAF scheme achieves the proposed upper bound and outperforms the two-relay non-orthorgonal amplify-and-forward (NAF) scheme of Azarian et al. for multiplexing gains r < 2/3. Numerical results reveal a significant gain of our scheme over the previously proposed AF schemes, especially in high spectral efficiency and large network size regime.


title: Diversity-Multiplexing Tradeoff of Double Scattering MIMO Channels

abstract: It is well known that the presence of double scattering degrades the performance of a MIMO channel, in terms of both the multiplexing gain and the diversity gain. In this paper, a closed-form expression of the diversity-multiplexing tradeoff (DMT) of double scattering MIMO channels is obtained. It is shown that, for a channel with nT transmit antennas, nR receive antennas and nS scatterers, the DMT only depends on the ordered version of the triple (nT,nS,nR), for arbitrary nT, nS and nR. The condition under which the double scattering channel has the same DMT as the single scattering channel is also established.


title: If a tree casts a shadow is it telling the time?

abstract: Physical processes are computations only when we use them to externalize thought. Computation is the performance of one or more fixed processes within a contingent environment. We reformulate the Church-Turing thesis so that it applies to programs rather than to computability. When suitably formulated agent-based computing in an open, multi-scalar environment represents the current consensus view of how we interact with the world. But we don't know how to formulate multi-scalar environments.


title: Open at the Top; Open at the Bottom; and Continually (but Slowly) Evolving

abstract: Systems of systems differ from traditional systems in that they are open at the top, open at the bottom, and continually (but slowly) evolving. "Open at the top" means that there is no pre-defined top level application. New applications may be created at any time. "Open at the bottom" means that the system primitives are defined functionally rather than concretely. This allows the implementation of these primitives to be modified as technology changes. "Continually (but slowly) evolving" means that the system's functionality is stable enough to be useful but is understood to be subject to modification. Systems with these properties tend to be environments within which other systems operate--and hence are systems of systems. It is also important to understand the larger environment within which a system of systems exists.


title: Complex Systems + Systems Engineering = Complex Systems Engineeri

abstract: One may define a complex system as a system in which phenomena emerge as a consequence of multiscale interaction among the system's components and their environments. The field of Complex Systems is the study of such systems--usually naturally occurring, either bio-logical or social. Systems Engineering may be understood to include the conceptualising and building of systems that consist of a large number of concurrently operating and interacting components--usually including both human and non-human elements. It has become increasingly apparent that the kinds of systems that systems engineers build have many of the same multiscale characteristics as those of naturally occurring complex systems. In other words, systems engineering is the engineering of complex systems. This paper and the associated panel will explore some of the connections between the fields of complex systems and systems engineering.


title: On Cosets of the Generalized First-Order Reed-Muller Code with Low PMEPR

abstract: Golay sequences are well suited for the use as codewords in orthogonal frequency-division multiplexing (OFDM), since their peak-to-mean envelope power ratio (PMEPR) in q-ary phase-shift keying (PSK) modulation is at most 2. It is known that a family of polyphase Golay sequences of length 2^m organizes in m!/2 cosets of a q-ary generalization of the first-order Reed-Muller code, RM_q(1,m). In this paper a more general construction technique for cosets of RM_q(1,m) with low PMEPR is established. These cosets contain so-called near-complementary sequences. The application of this theory is then illustrated by providing some construction examples. First, it is shown that the m!/2 cosets of RM_q(1,m) comprised of Golay sequences just arise as a special case. Second, further families of cosets of RM_q(1,m) with maximum PMEPR between 2 and 4 are presented, showing that some previously unexplained phenomena can now be understood within a unified framework. A lower bound on the PMEPR of cosets of RM_q(1,m) is proved as well, and it is demonstrated that the upper bound on the PMEPR is tight in many cases. Finally it is shown that all upper bounds on the PMEPR of cosets of RM_q(1,m) also hold for the peak-to-average power ratio (PAPR) under the Walsh-Hadamard transform.


title: A Business Goal Driven Approach for Understanding and Specifying Information Security Requirements

abstract: In this paper we present an approach for specifying and prioritizing information security requirements in organizations. It is important to prioritize security requirements since hundred per cent security is not achievable and the limited resources available should be directed to satisfy the most important ones. We propose to link explicitly security requirements with the organization's business vision, i.e. to provide business rationale for security requirements. The rationale is then used as a basis for comparing the importance of different security requirements. A conceptual framework is presented, where the relationships between business vision, critical impact factors and valuable assets (together with their security requirements) are shown.


title: Digital watermarking in the singular vector domain

abstract: Many current watermarking algorithms insert data in the spatial or transform domains like the discrete cosine, the discrete Fourier, and the discrete wavelet transforms. In this paper, we present a data-hiding algorithm that exploits the singular value decomposition (SVD) representation of the data. We compute the SVD of the host image and the watermark and embed the watermark in the singular vectors of the host image. The proposed method leads to an imperceptible scheme for digital images, both in grey scale and color and is quite robust against attacks like noise and JPEG compression.


title: Error Rate Analysis for Coded Multicarrier Systems over Quasi-Static Fading Channels

abstract: This paper presents two methods for approximating the performance of coded multicarrier systems operating over frequency-selective, quasi-static fading channels with non-ideal interleaving. The first method is based on approximating the performance of the system over each realization of the channel, and is suitable for obtaining the outage performance of this type of system. The second method is based on knowledge of the correlation matrix of the frequency-domain channel gains and can be used to directly obtain the average performance. Both of the methods are applicable for convolutionally-coded interleaved systems employing Quadrature Amplitude Modulation (QAM). As examples, both methods are used to study the performance of the Multiband Orthogonal Frequency Division Multiplexing (OFDM) proposal for high data-rate Ultra-Wideband (UWB) communication.


title: Graphics Turing Test

abstract: We define a Graphics Turing Test to measure graphics performance in a similar manner to the definition of the traditional Turing Test. To pass the test one needs to reach a computational scale, the Graphics Turing Scale, for which Computer Generated Imagery becomes comparatively indistinguishable from real images while also being interactive. We derive an estimate for this computational scale which, although large, is within reach of todays supercomputers. We consider advantages and disadvantages of various computer systems designed to pass the Graphics Turing Test. Finally we discuss commercial applications from the creation of such a system, in particular Interactive Cinema.


title: Theoretical Properties of Projection Based Multilayer Perceptrons with Functional Inputs

abstract: Many real world data are sampled functions. As shown by Functional Data Analysis (FDA) methods, spectra, time series, images, gesture recognition data, etc. can be processed more efficiently if their functional nature is taken into account during the data analysis process. This is done by extending standard data analysis methods so that they can apply to functional inputs. A general way to achieve this goal is to compute projections of the functional data onto a finite dimensional sub-space of the functional space. The coordinates of the data on a basis of this sub-space provide standard vector representations of the functions. The obtained vectors can be processed by any standard method. In our previous work, this general approach has been used to define projection based Multilayer Perceptrons (MLPs) with functional inputs. We study in this paper important theoretical properties of the proposed model. We show in particular that MLPs with functional inputs are universal approximators: they can approximate to arbitrary accuracy any continuous mapping from a compact sub-space of a functional space to R. Moreover, we provide a consistency result that shows that any mapping from a functional space to R can be learned thanks to examples by a projection based MLP: the generalization mean square error of the MLP decreases to the smallest possible mean square error on the data when the number of examples goes to infinity.


title: Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics

abstract: Consistent Query Answering (CQA) is the problem of computing from a database the answers to a query that are consistent with respect to certain integrity constraints that the database, as a whole, may fail to satisfy. Consistent answers have been characterized as those that are invariant under certain minimal forms of restoration of the database consistency. We investigate algorithmic and complexity theoretic issues of CQA under database repairs that minimally depart -wrt the cardinality of the symmetric difference- from the original database. We obtain first tight complexity bounds. We also address the problem of incremental complexity of CQA, that naturally occurs when an originally consistent database becomes inconsistent after the execution of a sequence of update operations. Tight bounds on incremental complexity are provided for various semantics under denial constraints. Fixed parameter tractability is also investigated in this dynamic context, where the size of the update sequence becomes the relevant parameter.


title: Hypercomputing the Mandelbrot Set?

abstract: The Mandelbrot set is an extremely well-known mathematical object that can be described in a quite simple way but has very interesting and non-trivial properties. This paper surveys some results that are known concerning the (non-)computability of the set. It considers two models of decidability over the reals (which have been treated much more thoroughly and technically by Hertling (2005), Blum, Shub and Smale, Brattka (2003) and Weihrauch (1999 and 2003) among others), two over the computable reals (the Russian school and hypercomputation) and a model over the rationals.


title: The Poincare conjecture for digital spaces. Properties of digital n-dimensional disks and spheres

abstract: Motivated by the Poincare conjecture, we study properties of digital n-dimensional spheres and disks, which are digital models of their continuous counterparts. We introduce homeomorphic transformations of digital manifolds, which retain the connectedness, the dimension, the Euler characteristics and the homology groups of manifolds. We find conditions where an n-dimensional digital manifold is the n-dimensional digital sphere and discuss the link between continuous closed n-manifolds and their digital models.


title: Multiterminal Source Coding with Two Encoders--I: A Computable Outer Bound

abstract: In this first part, a computable outer bound is proved for the multiterminal source coding problem, for a setup with two encoders, discrete memoryless sources, and bounded distortion measures.


title: Sparse Matrix Implementation in Octave

abstract: There are many classes of mathematical problems which give rise to matrices, where a large number of the elements are zero. In this case it makes sense to have a special matrix type to handle this class of problems where only the non-zero elements of the matrix are stored. Not only does this reduce the amount of memory to store the matrix, but it also means that operations on this type of matrix can take advantage of the a-priori knowledge of the positions of the non-zero elements to accelerate their calculations. A matrix type that stores only the non-zero elements is generally called sparse. Until recently Octave has lacked a full implementation of sparse matrices. This article address the implementation of sparse matrices within Octave, including their storage, creation, fundamental algorithms used, their implementations and the basic operations and functions implemented for sparse matrices. Mathematical issues such as the return types of sparse operations, matrix fill-in and reordering for sparse matrix factorization is discussed in the context of a real example. Benchmarking of Octave's implementation of sparse operations compared to their equivalent in Matlab are given and their implications discussed. Results are presented for multiplication and linear algebra operations for various matrix orders and densities. Furthermore, the use of Octave's sparse matrix implementation is demonstrated using a real example of a finite element model (FEM) problem. Finally, the method of using sparse matrices with Octave's oct-files is discussed. The means of creating, using and returning sparse matrices within oct-files is discussed as well as the differences between Octave's Sparse and Array classes.


title: On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures

abstract: We study the notion of limit sets of cellular automata associated with probability measures (mu-limit sets). This notion was introduced by P. Kurka and A. Maass. It is a refinement of the classical notion of omega-limit sets dealing with the typical long term behavior of cellular automata. It focuses on the words whose probability of appearance does not tend to 0 as time tends to infinity (the persistent words). In this paper, we give a characterisation of the persistent language for non sensible cellular automata associated with Bernouilli measures. We also study the computational complexity of these languages. We show that the persistent language can be non-recursive. But our main result is that the set of quasi-nilpotent cellular automata (those with a single configuration in their mu-limit set) is neither recursively enumerable nor co-recursively enumerable.


title: Minimum-Cost Coverage of Point Sets by Disks

abstract: We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t_j) and radii (r_j) that cover a given set of demand points Y in the plane at the smallest possible cost. We consider cost functions of the form sum_j f(r_j), where f(r)=r^alpha is the cost of transmission to radius r. Special cases arise for alpha=1 (sum of radii) and alpha=2 (total area); power consumption models in wireless network design often use an exponent alpha>2. Different scenarios arise according to possible restrictions on the transmission centers t_j, which may be constrained to belong to a given discrete set or to lie on a line, etc. We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points t_j on a given line in order to cover demand points Y in the plane; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in the plane and any fixed alpha>1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.


title: Can an Organism Adapt Itself to Unforeseen Circumstances?

abstract: A model of an organism as an autonomous intelligent system has been proposed. This model was used to analyze learning of an organism in various environmental conditions. Processes of learning were divided into two types: strong and weak processes taking place in the absence and the presence of aprioristic information about an object respectively. Weak learning is synonymous to adaptation when aprioristic programs already available in a system (an organism) are started. It was shown that strong learning is impossible for both an organism and any autonomous intelligent system. It was shown also that the knowledge base of an organism cannot be updated. Therefore, all behavior programs of an organism are congenital. A model of a conditioned reflex as a series of consecutive measurements of environmental parameters has been advanced. Repeated measurements are necessary in this case to reduce the error during decision making.


title: Nearly optimal exploration-exploitation decision thresholds

abstract: While in general trading off exploration and exploitation in reinforcement learning is hard, under some formulations relatively simple solutions exist. In this paper, we first derive upper bounds for the utility of selecting different actions in the multi-armed bandit setting. Unlike the common statistical upper confidence bounds, these explicitly link the planning horizon, uncertainty and the need for exploration explicit. The resulting algorithm can be seen as a generalisation of the classical Thompson sampling algorithm. We experimentally test these algorithms, as well as $\epsilon$-greedy and the value of perfect information heuristics. Finally, we also introduce the idea of bagging for reinforcement learning. By employing a version of online bootstrapping, we can efficiently sample from an approximate posterior distribution.


title: Semi-Supervised Learning -- A Statistical Physics Approach

abstract: We present a novel approach to semi-supervised learning which is based on statistical physics. Most of the former work in the field of semi-supervised learning classifies the points by minimizing a certain energy function, which corresponds to a minimal k-way cut solution. In contrast to these methods, we estimate the distribution of classifications, instead of the sole minimal k-way cut, which yields more accurate and robust results. Our approach may be applied to all energy functions used for semi-supervised learning. The method is based on sampling using a Multicanonical Markov chain Monte-Carlo algorithm, and has a straightforward probabilistic interpretation, which allows for soft assignments of points to classes, and also to cope with yet unseen class types. The suggested approach is demonstrated on a toy data set and on two real-life data sets of gene expression.


title: The Aryabhata Algorithm Using Least Absolute Remainders

abstract: This paper presents an introduction to the Aryabhata algorithm for finding multiplicative inverses and solving linear congruences, both of which have applications in cryptography. We do so by the use of the least absolute remainders. The exposition of the Aryabhata algorithm provided here can have performance that could exceed what was described recently by Rao and Yang.


title: On Covering a Graph Optimally with Induced Subgraphs

abstract: We consider the problem of covering a graph with a given number of induced subgraphs so that the maximum number of vertices in each subgraph is minimized. We prove NP-completeness of the problem, prove lower bounds, and give approximation algorithms for certain graph classes.


title: Towards Analog Reverse Time Computation

abstract: We report the consequences of a destabilization process on a simulated General Purpose Analog Computer. This new technology overcomes problems linked with serial ambiguity, and provides an analog bias to encode algorithms whose complexity is over polynomial. We also implicitly demonstrate how countermesures of the Stochastic Aperture Degeneracy could efficiently reach higher computational classes, and would open a road towards Analog Reverse Time Computation.


title: Revealing the Autonomous System Taxonomy: The Machine Learning Approach

abstract: Although the Internet AS-level topology has been extensively studied over the past few years, little is known about the details of the AS taxonomy. An AS "node" can represent a wide variety of organizations, e.g., large ISP, or small private business, university, with vastly different network characteristics, external connectivity patterns, network growth tendencies, and other properties that we can hardly neglect while working on veracious Internet representations in simulation environments. In this paper, we introduce a radically new approach based on machine learning techniques to map all the ASes in the Internet into a natural AS taxonomy. We successfully classify 95.3% of ASes with expected accuracy of 78.1%. We release to the community the AS-level topology dataset augmented with: 1) the AS taxonomy information and 2) the set of AS attributes we used to classify ASes. We believe that this dataset will serve as an invaluable addition to further understanding of the structure and evolution of the Internet.


title: On Conditional Branches in Optimal Search Trees

abstract: Algorithms for efficiently finding optimal alphabetic decision trees -- such as the Hu-Tucker algorithm -- are well established and commonly used. However, such algorithms generally assume that the cost per decision is uniform and thus independent of the outcome of the decision. The few algorithms without this assumption instead use one cost if the decision outcome is ``less than'' and another cost otherwise. In practice, neither assumption is accurate for software optimized for today's microprocessors. Such software generally has one cost for the more likely decision outcome and a greater cost -- often far greater -- for the less likely decision outcome. This problem and generalizations thereof are thus applicable to hard coding static decision tree instances in software, e.g., for optimizing program bottlenecks or for compiling switch statements. An O(n^3)-time O(n^2)-space dynamic programming algorithm can solve this optimal binary decision tree problem, and this approach has many generalizations that optimize for the behavior of processors with predictive branch capabilities, both static and dynamic. Solutions to this formulation are often faster in practice than ``optimal'' decision trees as formulated in the literature. Different search paradigms can sometimes yield even better performance.


title: AS Relationships: Inference and Validation

abstract: Research on performance, robustness, and evolution of the global Internet is fundamentally handicapped without accurate and thorough knowledge of the nature and structure of the contractual relationships between Autonomous Systems (ASs). In this work we introduce novel heuristics for inferring AS relationships. Our heuristics improve upon previous works in several technical aspects, which we outline in detail and demonstrate with several examples. Seeking to increase the value and reliability of our inference results, we then focus on validation of inferred AS relationships. We perform a survey with ASs' network administrators to collect information on the actual connectivity and policies of the surveyed ASs. Based on the survey results, we find that our new AS relationship inference techniques achieve high levels of accuracy: we correctly infer 96.5% customer to provider (c2p), 82.8% peer to peer (p2p), and 90.3% sibling to sibling (s2s) relationships. We then cross-compare the reported AS connectivity with the AS connectivity data contained in BGP tables. We find that BGP tables miss up to 86.2% of the true adjacencies of the surveyed ASs. The majority of the missing links are of the p2p type, which highlights the limitations of present measuring techniques to capture links of this type. Finally, to make our results easily accessible and practically useful for the community, we open an AS relationship repository where we archive, on a weekly basis, and make publicly available the complete Internet AS-level topology annotated with AS relationship information for every pair of AS neighbors.


title: Cryptographic Pseudo-Random Sequences from the Chaotic Henon Map

abstract: A scheme for pseudo-random binary sequence generation based on the two-dimensional discrete-time Henon map is proposed. Properties of the proposed sequences pertaining to linear complexity, linear complexity profile, correlation and auto-correlation are investigated. All these properties of the sequences suggest a strong resemblance to random sequences. Results of statistical testing of the sequences are found encouraging. An attempt is made to estimate the keyspace size if the proposed scheme is used for cryptographic applications. The keyspace size is found to be large and is dependent on the precision of the computing platform used.


title: The Case for Modeling Security, Privacy, Usability and Reliability (SPUR) in Automotive Software

abstract: Over the past five years, there has been considerable growth and established value in the practice of modeling automotive software requirements. Much of this growth has been centered on requirements of software associated with the established functional areas of an automobile, such as those associated with powertrain, chassis, body, safety and infotainment. This paper makes a case for modeling four additional attributes that are increasingly important as vehicles become information conduits: security, privacy, usability, and reliability. These four attributes are important in creating specifications for embedded in-vehicle automotive software.