title: Equality of complexity classes P and NP: Linear programming formulation of the quadratic assignment problem

abstract: In this paper, we present a polynomial-sized linear programming formulation of the Quadratic Assignment Problem (QAP). The proposed linear program is a network flow-based model. Hence, it provides for the solution of the QAP in polynomial time. Computational testing and results are discussed.


title: The traveling salesman problem: A Linear programming formulation

abstract: In this paper, we present a polynomial-sized linear programming formulation of the Traveling Salesman Problem (TSP). The proposed linear program is a network flow-based model. Numerical implementation issues and results are discussed. (The exposition and proofs are much more detailed in an edition which I wrote in collaboration with Dr. M.H. Karwan in 2012-2014 . That edition is available at http://users.business.uconn.edu/mdiaby/P=NPProofPapers/tspPaper.pdf)


title: New Quasi-Cyclic Codes from Simplex Codes

abstract: As a generalization of cyclic codes, quasi-cyclic (QC) codes contain many good linear codes. But quasi-cyclic codes studied so far are mainly limited to one generator (1-generator) QC codes. In this correspondence, 2-generator and 3-generator QC codes are studied, and many good, new QC codes are constructed from simplex codes. Some new binary QC codes or related codes, that improve the bounds on maximum minimum distance for binary linear codes are constructed. They are 5-generator QC [93, 17, 34] and [254, 23, 102] codes, and related [96, 17, 36], [256, 23, 104] codes.


title: A Massive Local Rules Search Approach to the Classification Problem

abstract: An approach to the classification problem of machine learning, based on building local classification rules, is developed. The local rules are considered as projections of the global classification rules to the event we want to classify. A massive global optimization algorithm is used for optimization of quality criterion. The algorithm, which has polynomial complexity in typical case, is used to find all high--quality local rules. The other distinctive feature of the algorithm is the integration of attributes levels selection (for ordered attributes) with rules searching and original conflicting rules resolution strategy. The algorithm is practical; it was tested on a number of data sets from UCI repository, and a comparison with the other predicting techniques is presented.


title: On the freeze quantifier in Constraint LTL: decidability and complexity

abstract: Constraint LTL, a generalisation of LTL over Presburger constraints, is often used as a formal language to specify the behavior of operational models with constraints. The freeze quantifier can be part of the language, as in some real-time logics, but this variable-binding mechanism is quite general and ubiquitous in many logical languages (first-order temporal logics, hybrid logics, logics for sequence diagrams, navigation logics, logics with lambda-abstraction etc.). We show that Constraint LTL over the simple domain (N,=) augmented with the freeze quantifier is undecidable which is a surprising result in view of the poor language for constraints (only equality tests). Many versions of freeze-free Constraint LTL are decidable over domains with qualitative predicates and our undecidability result actually establishes Sigma_1^1-completeness. On the positive side, we provide complexity results when the domain is finite (EXPSPACE-completeness) or when the formulae are flat in a sense introduced in the paper. Our undecidability results are sharp (i.e. with restrictions on the number of variables) and all our complexity characterisations ensure completeness with respect to some complexity class (mainly PSPACE and EXPSPACE).


title: Finding heaviest H-subgraphs in real weighted graphs, with applications

abstract: For a graph G with real weights assigned to the vertices (edges), the MAX H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if one exists. The all-pairs MAX H-SUBGRAPH problem is to find for every pair of vertices u,v, a maximum H-subgraph containing both u and v, if one exists. Our main results are new strongly polynomial algorithms for the all-pairs MAX H-SUBGRAPH problem for vertex weighted graphs. We also give improved algorithms for the MAX-H SUBGRAPH problem for edge weighted graphs, and various related problems, including computing the first k most significant bits of the distance product of two matrices. Some of our algorithms are based, in part, on fast matrix multiplication.


title: An effective edge--directed frequency filter for removal of aliasing in upsampled images

abstract: Raster images can have a range of various distortions connected to their raster structure. Upsampling them might in effect substantially yield the raster structure of the original image, known as aliasing. The upsampling itself may introduce aliasing into the upsampled image as well. The presented method attempts to remove the aliasing using frequency filters based on the discrete fast Fourier transform, and applied directionally in certain regions placed along the edges in the image. As opposed to some anisotropic smoothing methods, the presented algorithm aims to selectively reduce only the aliasing, preserving the sharpness of image details. The method can be used as a post--processing filter along with various upsampling algorithms. It was experimentally shown that the method can improve the visual quality of the upsampled images.


title: Scheduling for Stable and Reliable Communication over Multiaccess Channels and Degraded Broadcast Channels

abstract: Information-theoretic arguments focus on modeling the reliability of information transmission, assuming availability of infinite data at sources, thus ignoring randomness in message generation times at the respective sources. However, in information transport networks, not only is reliable transmission important, but also stability, i.e., finiteness of mean delay incurred by messages from the time of generation to the time of successful reception. Usually, delay analysis is done separately using queueing-theoretic arguments, whereas reliable information transmission is studied using information theory. In this thesis, we investigate these two important aspects of data communication jointly by suitably combining models from these two fields. In particular, we model scheduled communication of messages, that arrive in a random process, (i) over multiaccess channels, with either independent decoding or joint decoding, and (ii) over degraded broadcast channels. The scheduling policies proposed permit up to a certain maximum number of messages for simultaneous transmission. In the first part of the thesis, we develop a multi-class discrete-time processor-sharing queueing model, and then investigate the stability of this queue. In particular, we model the queue by a discrete-time Markov chain defined on a countable state space, and then establish (i) a sufficient condition for $c$-regularity of the chain, and hence positive recurrence and finiteness of stationary mean of the function $c$ of the state, and (ii) a sufficient condition for transience of the chain. These stability results form the basis for the conclusions drawn in the thesis.


title: Baire Categories on Small Complexity Classes and Meager-Comeager Laws

abstract: We introduce two resource-bounded Baire category notions on small complexity classes such as P, SUBEXP, and PSPACE and on probabilistic classes such as BPP, which differ on how the corresponding finite extension strategies are computed. We give an alternative characterization of small sets via resource-bounded Banach-Mazur games. As an application of the first notion, we show that for almost every language A (i.e. all except a meager class) computable in subexponential time, P(A)=BPP(A). We also show that almost all languages in PSPACE do not have small nonuniform complexity. We then switch to the second Baire category notion (called locally-computable), and show that the class SPARSE is meager in P. We show that in contrast to the resource-bounded measure case, meager-comeager laws can be obtained for many standard complexity classes, relative to locally-computable Baire category on BPP and PSPACE. Another topic where locally-computable Baire categories differ from resource-bounded measure is regarding weak-completeness: we show that there is no weak-completeness notion in P based on locally-computable Baire categories, i.e. every P-weakly-complete set is complete for P. We also prove that the class of complete sets for P under Turing-logspace reductions is meager in P, if P is not equal to DSPACE(log n), and that the same holds unconditionally for quasi-poly time. Finally we observe that locally-computable Baire categories are incomparable with all existing resource-bounded measure notions on small complexity classes, which might explain why those two settings seem to differ so fundamentally.


title: Combining typing and size constraints for checking the termination of higher-order conditional rewrite systems

abstract: In a previous work, the first author extended to higher-order rewriting and dependent types the use of size annotations in types, a termination proof technique called type or size based termination and initially developed for ML-like programs. Here, we go one step further by considering conditional rewriting and explicit quantifications and constraints on size annotations. This allows to describe more precisely how the size of the output of a function depends on the size of its inputs. Hence, we can check the termination of more functions. We first give a general type-checking algorithm based on constraint solving. Then, we give a termination criterion with constraints in Presburger arithmetic. To our knowledge, this is the first termination criterion for higher-order conditional rewriting taking into account the conditions in termination.


title: A simple stability condition for RED using TCP mean-field modeling

abstract: Congestion on the Internet is an old problem but still a subject of intensive research. The TCP protocol with its AIMD (Additive Increase and Multiplicative Decrease) behavior hides very challenging problems; one of them is to understand the interaction between a large number of users with delayed feedback. This article will focus on two modeling issues of TCP which appeared to be important to tackle concrete scenarios when implementing the model proposed in [Baccelli McDonald Reynier 02] firstly the modeling of the maximum TCP window size: this maximum can be reached quickly in many practical cases; secondly the delay structure: the usual Little-like formula behaves really poorly when queuing delays are variable, and may change dramatically the evolution of the predicted queue size, which makes it useless to study drop-tail or RED (Random Early Detection) mechanisms. Within proposed TCP modeling improvements, we are enabled to look at a concrete example where RED should be used in FIFO routers instead of letting the default drop-tail happen. We study mathematically fixed points of the window size distribution and local stability of RED. An interesting case is when RED operates at the limit when the congestion starts, it avoids unwanted loss of bandwidth and delay variations.


title: Residual Finite Tree Automata

abstract: Tree automata based algorithms are essential in many fields in computer science such as verification, specification, program analysis. They become also essential for databases with the development of standards such as XML. In this paper, we define new classes of non deterministic tree automata, namely residual finite tree automata (RFTA). In the bottom-up case, we obtain a new characterization of regular tree languages. In the top-down case, we obtain a subclass of regular tree languages which contains the class of languages recognized by deterministic top-down tree automata. RFTA also come with the property of existence of canonical non deterministic tree automata.


title: ANAP: Anonymous Authentication Protocol in Mobile Ad hoc Networks

abstract: The pervasiveness of wireless communication recently gave mobile ad hoc networks (MANET) a significant researchers' attention, due to its innate capabilities of instant communication in many time and mission critical applications. However, its natural advantages of networking in civilian and military environments make them vulnerable to security threats. Support for an anonymity in MANET is an orthogonal to security critical challenge we faced in this paper. We propose a new anonymous authentication protocol for mobile ad hoc networks enhanced with a distributed reputation system. The main its objective is to provide mechanisms concealing a real identity of communicating nodes with an ability of resist to known attacks. The distributed reputation system is incorporated for a trust management and malicious behavior detection in the network. The end-to-end anonymous authentication is conducted in three-pass handshake based on an asymmetric and symmetric key cryptography. After successfully finished authentication phase secure and multiple anonymous data channels are established. The anonymity is guarantied by randomly chosen pseudonyms owned by a user. Nodes of the network are publicly identified and are independent of users' pseudonyms. In this paper we presented an example of the protocol implementation.


title: On some winning strategies for the Iterated Prisoner's Dilemma or Mr. Nice Guy and the Cosa Nostra

abstract: We submitted two kinds of strategies to the iterated prisoner's dilemma (IPD) competitions organized by Graham Kendall, Paul Darwen and Xin Yao in 2004 and 2005. Our strategies performed exceedingly well in both years. One type is an intelligent and optimistic enhanced version of the well known TitForTat strategy which we named OmegaTitForTat. It recognizes common behaviour patterns and detects and recovers from repairable mutual defect deadlock situations, otherwise behaving much like TitForTat. The second type consists of a set of strategies working together as a team. These group strategies have one distinguished individual Godfather strategy that plays OmegaTitForTat against non-members while heavily profiting from the behaviour of the other members of his group, the Hitman. The Hitman willingly let themselves being abused by their Godfather while themselves lowering the scores of all other players as much as possible, thus further maximizing the performance of their Godfather in relation to other participants. The study of collusion in the simplified framework of the iterated prisoner's dilemma allows us to draw parallels to many common aspects of reality both in Nature as well as Human Society, and therefore further extends the scope of the iterated prisoner's dilemma as a metaphor for the study of cooperative behaviour in a new and natural direction. We further provide evidence that it will be unavoidable that such group strategies will dominate all future iterated prisoner's dilemma competitions as they can be stealthy camouflaged as non-group strategies with arbitrary subtlety. Moreover, we show that the general problem of recognizing stealth colluding strategies is undecidable in the theoretical sense.


title: Bilayer Low-Density Parity-Check Codes for Decode-and-Forward in Relay Channels

abstract: This paper describes an efficient implementation of binning for the relay channel using low-density parity-check (LDPC) codes. We devise bilayer LDPC codes to approach the theoretically promised rate of the decode-and-forward relaying strategy by incorporating relay-generated information bits in specially designed bilayer graphical code structures. While conventional LDPC codes are sensitively tuned to operate efficiently at a certain channel parameter, the proposed bilayer LDPC codes are capable of working at two different channel parameters and two different rates: that at the relay and at the destination. To analyze the performance of bilayer LDPC codes, bilayer density evolution is devised as an extension of the standard density evolution algorithm. Based on bilayer density evolution, a design methodology is developed for the bilayer codes in which the degree distribution is iteratively improved using linear programming. Further, in order to approach the theoretical decode-and-forward rate for a wide range of channel parameters, this paper proposes two different forms bilayer codes, the bilayer-expurgated and bilayer-lengthened codes. It is demonstrated that a properly designed bilayer LDPC code can achieve an asymptotic infinite-length threshold within 0.24 dB gap to the Shannon limits of two different channels simultaneously for a wide range of channel parameters. By practical code construction, finite-length bilayer codes are shown to be able to approach within a 0.6 dB gap to the theoretical decode-and-forward rate of the relay channel at a block length of $10^5$ and a bit-error probability (BER) of $10^{-4}$. Finally, it is demonstrated that a generalized version of the proposed bilayer code construction is applicable to relay networks with multiple relays.


title: Improving Term Extraction with Terminological Resources

abstract: Studies of different term extractors on a corpus of the biomedical domain revealed decreasing performances when applied to highly technical texts. The difficulty or impossibility of customising them to new domains is an additional limitation. In this paper, we propose to use external terminologies to influence generic linguistic data in order to augment the quality of the extraction. The tool we implemented exploits testified terms at different steps of the process: chunking, parsing and extraction of term candidates. Experiments reported here show that, using this method, more term candidates can be acquired with a higher level of reliability. We further describe the extraction process involving endogenous disambiguation implemented in the term extractor YaTeA.


title: Fast algorithms for computing isogenies between elliptic curves

abstract: We survey algorithms for computing isogenies between elliptic curves defined over a field of characteristic either 0 or a large prime. We introduce a new algorithm that computes an isogeny of degree $\ell$ ($\ell$ different from the characteristic) in time quasi-linear with respect to $\ell$. This is based in particular on fast algorithms for power series expansion of the Weierstrass $\wp$-function and related functions.


title: Non uniform (hyper/multi)coherence spaces

abstract: In (hyper)coherence semantics, proofs/terms are cliques in (hyper)graphs. Intuitively, vertices represent results of computations and the edge relation witnesses the ability of being assembled into a same piece of data or a same (strongly) stable function, at arrow types. In (hyper)coherence semantics, the argument of a (strongly) stable functional is always a (strongly) stable function. As a consequence, comparatively to the relational semantics, where there is no edge relation, some vertices are missing. Recovering these vertices is essential for the purpose of reconstructing proofs/terms from their interpretations. It shall also be useful for the comparison with other semantics, like game semantics. In [BE01], Bucciarelli and Ehrhard introduced a so called non uniform coherence space semantics where no vertex is missing. By constructing the co-free exponential we set a new version of this last semantics, together with non uniform versions of hypercoherences and multicoherences, a new semantics where an edge is a finite multiset. Thanks to the co-free construction, these non uniform semantics are deterministic in the sense that the intersection of a clique and of an anti-clique contains at most one vertex, a result of interaction, and extensionally collapse onto the corresponding uniform semantics.


title: Dichotomies and Duality in First-order Model Checking Problems

abstract: We study the complexity of the model checking problem, for fixed model A, over certain fragments L of first-order logic. These are sometimes known as the expression complexities of L. We obtain various complexity classification theorems for these logics L as each ranges over models A, in the spirit of the dichotomy conjecture for the Constraint Satisfaction Problem -- which itself may be seen as the model checking problem for existential conjunctive positive first-order logic.


title: Novel Reversible TSG Gate and Its Application for Designing Components of Primitive Reversible/Quantum ALU

abstract: In recent years, reversible logic has emerged as a promising computing paradigm having application 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 utilizes a new 4 * 4 reversible gate called TSG gate to build the components of a primitive reversible/quantum ALU. The most significant aspect of the TSG gate is that it can work singly as a reversible full adder, that is reversible full adder can now be implemented with a single gate only. A Novel reversible 4:2 compressor is also designed from the TSG gate which is later used to design a novel 8x8 reversible Wallace tree multiplier. It is proved that the adder, 4:2 compressor and multiplier architectures designed using the TSG gate are better than their counterparts available in literature, in terms of number of reversible gates and garbage outputs. This is perhaps, the first attempt to design a reversible 4:2 compressor and a reversible Wallace tree multiplier as far as existing literature and our knowledge is concerned. Thus, this paper provides an initial threshold to build more complex systems which can execute complicated operations using reversible logic.


title: Linux, Open Source and Unicode

abstract: The paper is taken out.


title: A XML Schema Definition based Universal User Interface

abstract: The article is taken out for change of contents.


title: Rarest First and Choke Algorithms Are Enough

abstract: The performance of peer-to-peer file replication comes from its piece and peer selection strategies. Two such strategies have been introduced by the BitTorrent protocol: the rarest first and choke algorithms. Whereas it is commonly admitted that BitTorrent performs well, recent studies have proposed the replacement of the rarest first and choke algorithms in order to improve efficiency and fairness. In this paper, we use results from real experiments to advocate that the replacement of the rarest first and choke algorithms cannot be justified in the context of peer-to-peer file replication in the Internet. We instrumented a BitTorrent client and ran experiments on real torrents with different characteristics. Our experimental evaluation is peer oriented, instead of tracker oriented, which allows us to get detailed information on all exchanged messages and protocol events. We go beyond the mere observation of the good efficiency of both algorithms. We show that the rarest first algorithm guarantees close to ideal diversity of the pieces among peers. In particular, on our experiments, replacing the rarest first algorithm with source or network coding solutions cannot be justified. We also show that the choke algorithm in its latest version fosters reciprocation and is robust to free riders. In particular, the choke algorithm is fair and its replacement with a bit level tit-for-tat solution is not appropriate. Finally, we identify new areas of improvements for efficient peer-to-peer file replication protocols.


title: A Case for Peering of Content Delivery Networks

abstract: The proliferation of Content Delivery Networks (CDN) reveals that existing content networks are owned and operated by individual companies. As a consequence, closed delivery networks are evolved which do not cooperate with other CDNs and in practice, islands of CDNs are formed. Moreover, the logical separation between contents and services in this context results in two content networking domains. But present trends in content networks and content networking capabilities give rise to the interest in interconnecting content networks. Finding ways for distinct content networks to coordinate and cooperate with other content networks is necessary for better overall service. In addition to that, meeting the QoS requirements of users according to the negotiated Service Level Agreements between the user and the content network is a burning issue in this perspective. In this article, we present an open, scalable and Service-Oriented Architecture based system to assist the creation of open Content and Service Delivery Networks (CSDN) that scale and support sharing of resources with other CSDNs.


title: VLSI Implementation of RSA Encryption System Using Ancient Indian Vedic Mathematics

abstract: This paper proposes the hardware implementation of RSA encryption/decryption algorithm using the algorithms of Ancient Indian Vedic Mathematics that have been modified to improve performance. The recently proposed hierarchical overlay multiplier architecture is used in the RSA circuitry for multiplication operation. The most significant aspect of the paper is the development of a division architecture based on Straight Division algorithm of Ancient Indian Vedic Mathematics and embedding it in RSA encryption/decryption circuitry for improved efficiency. The coding is done in Verilog HDL and the FPGA synthesis is done using Xilinx Spartan library. The results show that RSA circuitry implemented using Vedic division and multiplication is efficient in terms of area/speed compared to its implementation using conventional multiplication and division architectures


title: Reversible Programmable Logic Array (RPLA) using Fredkin & Feynman Gates for Industrial Electronics and Applications

abstract: In recent years, reversible logic has emerged as a promising computing paradigm having application in low power CMOS, quantum computing, nanotechnology, and optical computing. The classical set of gates such as AND, OR, and EXOR are not reversible. In this paper, the authors have proposed reversible programmable logic array (RPLA) architecture using reversible Fredkin and Feynman gates. The proposed RPLA has n inputs and m outputs and can realize m functions of n variables. In order to demonstrate the design of RPLA, a 3 input RPLA is designed which can perform any 28 functions using the combination of 8 min terms (23). Furthermore, the application of the designed 3 input RPLA is shown by implementing the full adder and full subtractor functions through it.


title: Space Division Multiple Access with a Sum Feedback Rate Constraint

abstract: On a multi-antenna broadcast channel, simultaneous transmission to multiple users by joint beamforming and scheduling is capable of achieving high throughput, which grows double logarithmically with the number of users. The sum rate for channel state information (CSI) feedback, however, increases linearly with the number of users, reducing the effective uplink capacity. To address this problem, a novel space division multiple access (SDMA) design is proposed, where the sum feedback rate is upper-bounded by a constant. This design consists of algorithms for CSI quantization, threshold based CSI feedback, and joint beamforming and scheduling. The key feature of the proposed approach is the use of feedback thresholds to select feedback users with large channel gains and small CSI quantization errors such that the sum feedback rate constraint is satisfied. Despite this constraint, the proposed SDMA design is shown to achieve a sum capacity growth rate close to the optimal one. Moreover, the feedback overflow probability for this design is found to decrease exponentially with the difference between the allowable and the average sum feedback rates. Numerical results show that the proposed SDMA design is capable of attaining higher sum capacities than existing ones, even though the sum feedback rate is bounded.


title: Approximation Algorithms for the Bipartite Multi-cut Problem

abstract: We introduce the {\it Bipartite Multi-cut} problem. This is a generalization of the {\it st-Min-cut} problem, is similar to the {\it Multi-cut} problem (except for more stringent requirements) and also turns out to be an immediate generalization of the {\it Min UnCut} problem. We prove that this problem is {\bf NP}-hard and then present LP and SDP based approximation algorithms. While the LP algorithm is based on the Garg-Vazirani-Yannakakis algorithm for {\it Multi-cut}, the SDP algorithm uses the {\it Structure Theorem} of $\ell_2^2$ Metrics.


title: CR-precis: A deterministic summary structure for update data streams

abstract: We present the \crprecis structure, that is a general-purpose, deterministic and sub-linear data structure for summarizing \emph{update} data streams. The \crprecis structure yields the \emph{first deterministic sub-linear space/time algorithms for update streams} for answering a variety of fundamental stream queries, such as, (a) point queries, (b) range queries, (c) finding approximate frequent items, (d) finding approximate quantiles, (e) finding approximate hierarchical heavy hitters, (f) estimating inner-products, (g) near-optimal $B$-bucket histograms, etc..


title: Choosing Colors for Geometric Graphs via Color Space Embeddings

abstract: Graph drawing research traditionally focuses on producing geometric embeddings of graphs satisfying various aesthetic constraints. After the geometric embedding is specified, there is an additional step that is often overlooked or ignored: assigning display colors to the graph's vertices. We study the additional aesthetic criterion of assigning distinct colors to vertices of a geometric graph so that the colors assigned to adjacent vertices are as different from one another as possible. We formulate this as a problem involving perceptual metrics in color space and we develop algorithms for solving this problem by embedding the graph in color space. We also present an application of this work to a distributed load-balancing visualization problem.


title: Social Decision Making with Multi-Relational Networks and Grammar-Based Particle Swarms

abstract: Social decision support systems are able to aggregate the local perspectives of a diverse group of individuals into a global social decision. This paper presents a multi-relational network ontology and grammar-based particle swarm algorithm capable of aggregating the decisions of millions of individuals. This framework supports a diverse problem space and a broad range of vote aggregation algorithms. These algorithms account for individual expertise and representation across different domains of the group problem space. Individuals are able to pose and categorize problems, generate potential solutions, choose trusted representatives, and vote for particular solutions. Ultimately, via a social decision making algorithm, the system aggregates all the individual votes into a single collective decision.


title: Rational Secret Sharing and Multiparty Computation: Extended Abstract

abstract: We consider the problems of secret sharing and multiparty computation, assuming that agents prefer to get the secret (resp., function value) to not getting it, and secondarily, prefer that as few as possible of the other agents get it. We show that, under these assumptions, neither secret sharing nor multiparty function computation is possible using a mechanism that has a fixed running time. However, we show that both are possible using randomized mechanisms with constant expected running time.


title: Reduced Area Low Power High Throughput BCD Adders 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. Firstly, this paper proposes novel two transistor AND and OR gates. The proposed AND gate has no power supply, thus it can be referred as the Powerless AND gate. Similarly, the proposed two transistor OR gate has no ground and can be referred as Groundless OR. Secondly for IEEE 754r format, two novel BCD adders called carry skip and carry look-ahead BCD adders are also proposed in this paper. In order to design the carry look-ahead BCD adder, a novel 4 bit carry look-ahead adder called NCLA is proposed which forms the basic building block of the proposed carry look-ahead BCD adder. Finally, the proposed two transistors AND and OR gates are used to provide the optimized small area low power high throughput circuitries of the proposed BCD adders.


title: (HO)RPO Revisited

abstract: The notion of computability closure has been introduced for proving the termination of the combination of higher-order rewriting and beta-reduction. It is also used for strengthening the higher-order recursive path ordering. In the present paper, we study in more details the relations between the computability closure and the (higher-order) recursive path ordering. We show that the first-order recursive path ordering is equal to an ordering naturally defined from the computability closure. In the higher-order case, we get an ordering containing the higher-order recursive path ordering whose well-foundedness relies on the correctness of the computability closure. This provides a simple way to extend the higher-order recursive path ordering to richer type systems.


title: On Performance of Event-to-Sink Transport in Transmit-Only Sensor Networks

abstract: We consider a hybrid wireless sensor network with regular and transmit-only sensors. The transmit-only sensors do not have receiver circuit, hence are cheaper and less energy consuming, but their transmissions cannot be coordinated. Regular sensors, also called cluster-heads, are responsible for receiving information from transmit-only sensors and forwarding it to sinks. The main goal of such a hybrid network is to reduce the cost of deployment while achieving some performance constraints (minimum coverage, sensing rate, etc). In this paper we are interested in the communication between transmit-only sensors and cluster-heads. We develop a detailed analytical model of the physical and MAC layer using tools from queuing theory and stochastic geometry. (The MAC model, that we call Erlang's loss model with interference, might be of independent interest as adequate for any non-slotted; i.e., unsynchronized, wireless communication channel.) We give an explicit formula for the frequency of successful packet reception by a cluster-head, given sensors' locations. We further define packet admission policies at a cluster-head, and we calculate the optimal policies for different performance criteria. Finally we show that the proposed hybrid network, using the optimal policies, can achieve substantial cost savings as compared to conventional architectures.


title: Higher-Order Termination: from Kruskal to Computability

abstract: Termination is a major question in both logic and computer science. In logic, termination is at the heart of proof theory where it is usually called strong normalization (of cut elimination). In computer science, termination has always been an important issue for showing programs correct. In the early days of logic, strong normalization was usually shown by assigning ordinals to expressions in such a way that eliminating a cut would yield an expression with a smaller ordinal. In the early days of verification, computer scientists used similar ideas, interpreting the arguments of a program call by a natural number, such as their size. Showing the size of the arguments to decrease for each recursive call gives a termination proof of the program, which is however rather weak since it can only yield quite small ordinals. In the sixties, Tait invented a new method for showing cut elimination of natural deduction, based on a predicate over the set of terms, such that the membership of an expression to the predicate implied the strong normalization property for that expression. The predicate being defined by induction on types, or even as a fixpoint, this method could yield much larger ordinals. Later generalized by Girard under the name of reducibility or computability candidates, it showed very effective in proving the strong normalization property of typed lambda-calculi...


title: Elgot Algebras

abstract: Denotational semantics can be based on algebras with additional structure (order, metric, etc.) which makes it possible to interpret recursive specifications. It was the idea of Elgot to base denotational semantics on iterative theories instead, i.e., theories in which abstract recursive specifications are required to have unique solutions. Later Bloom and Esik studied iteration theories and iteration algebras in which a specified solution has to obey certain axioms. We propose so-called Elgot algebras as a convenient structure for semantics in the present paper. An Elgot algebra is an algebra with a specified solution for every system of flat recursive equations. That specification satisfies two simple and well motivated axioms: functoriality (stating that solutions are stable under renaming of recursion variables) and compositionality (stating how to perform simultaneous recursion). These two axioms stem canonically from Elgot's iterative theories: We prove that the category of Elgot algebras is the Eilenberg-Moore category of the monad given by a free iterative theory.


title: Primitive operations for the construction and reorganization of minimally persistent formations

abstract: In this paper, we study the construction and transformation of two-dimensional persistent graphs. Persistence is a generalization to directed graphs of the undirected notion of rigidity. In the context of moving autonomous agent formations, persistence characterizes the efficacy of a directed structure of unilateral distances constraints seeking to preserve a formation shape. Analogously to the powerful results about Henneberg sequences in minimal rigidity theory, we propose different types of directed graph operations allowing one to sequentially build any minimally persistent graph (i.e. persistent graph with a minimal number of edges for a given number of vertices), each intermediate graph being also minimally persistent. We also consider the more generic problem of obtaining one minimally persistent graph from another, which corresponds to the on-line reorganization of an autonomous agent formation. We prove that we can obtain any minimally persistent formation from any other one by a sequence of elementary local operations such that minimal persistence is preserved throughout the reorganization process.


title: On Divergence-Power Inequalities

abstract: Expressions for (EPI Shannon type) Divergence-Power Inequalities (DPI) in two cases (time-discrete and band-limited time-continuous) of stationary random processes are given. The new expressions connect the divergence rate of the sum of independent processes, the individual divergence rate of each process, and their power spectral densities. All divergences are between a process and a Gaussian process with same second order statistics, and are assumed to be finite. A new proof of the Shannon entropy-power inequality EPI, based on the relationship between divergence and causal minimum mean-square error (CMMSE) in Gaussian channels with large signal-to-noise ratio, is also shown.


title: Challenging the principle of compositionality in interpreting natural language texts

abstract: The paper aims at emphasizing that, even relaxed, the hypothesis of compositionality has to face many problems when used for interpreting natural language texts. Rather than fixing these problems within the compositional framework, we believe that a more radical change is necessary, and propose another approach.


title: The role of time in considering collections

abstract: The paper concerns the understanding of plurals in the framework of Artificial Intelligence and emphasizes the role of time. The construction of collection(s) and their evolution across time is often crucial and has to be accounted for. The paper contrasts a "de dicto" collection where the collection can be considered as persisting over these situations even if its members change with a "de re" collection whose composition does not vary through time. It expresses different criteria of choice between the two interpretations (de re and de dicto) depending on the context of enunciation.


title: Metric entropy in competitive on-line prediction

abstract: Competitive on-line prediction (also known as universal prediction of individual sequences) is a strand of learning theory avoiding making any stochastic assumptions about the way the observations are generated. The predictor's goal is to compete with a benchmark class of prediction rules, which is often a proper Banach function space. Metric entropy provides a unifying framework for competitive on-line prediction: the numerous known upper bounds on the metric entropy of various compact sets in function spaces readily imply bounds on the performance of on-line prediction strategies. This paper discusses strengths and limitations of the direct approach to competitive on-line prediction via metric entropy, including comparisons to other approaches.


title: Exhausting Error-Prone Patterns in LDPC Codes

abstract: It is proved in this work that exhaustively determining bad patterns in arbitrary, finite low-density parity-check (LDPC) codes, including stopping sets for binary erasure channels (BECs) and trapping sets (also known as near-codewords) for general memoryless symmetric channels, is an NP-complete problem, and efficient algorithms are provided for codes of practical short lengths n~=500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of size <=13 and the trapping sets of size <=11 can be efficiently exhaustively determined for the first time, and the resulting exhaustive list is of great importance for code analysis and finite code optimization. The featured tree-based narrowing search distinguishes this algorithm from existing ones for which inexhaustive methods are employed. One important byproduct is a pair of upper bounds on the bit-error rate (BER) & frame-error rate (FER) iterative decoding performance of arbitrary codes over BECs that can be evaluated for any value of the erasure probability, including both the waterfall and the error floor regions. The tightness of these upper bounds and the exhaustion capability of the proposed algorithm are proved when combining an optimal leaf-finding module with the tree-based search. These upper bounds also provide a worst-case-performance guarantee which is crucial to optimizing LDPC codes for extremely low error rate applications, e.g., optical/satellite communications. Extensive numerical experiments are conducted that include both randomly and algebraically constructed LDPC codes, the results of which demonstrate the superior efficiency of the exhaustion algorithm and its significant value for finite length code optimization.


title: Topology Control and Network Lifetime in Three-Dimensional Wireless Sensor Networks

abstract: Coverage and connectivity issues of three-dimensional (3D) networks are addressed in [2], but that work assumes that a node can be placed at any arbitrary location. In this work, we drop that assumption and rather assume that nodes are uniformly and densely deployed in a 3D space. We want to devise a mechanism that keeps some nodes active and puts other nodes into sleep so that the number of active nodes at a time is minimized (and thus network life time is maximized), while maintaining full coverage and connectivity. One simple way to do that is to partition the 3D space into cells, and only one node in each cell remains active at a time. Our results show that the number of active nodes can be minimized if the shape of each cell is a truncated octahedron. It requires the sensing range to be at least 0.542326 times the transmission radius. This value is 0.5, 0.53452 and 0.5 for cube, hexagonal prism, and rhombic dodecahedron, respectively. However, at a time the number of active nodes for cube, hexagonal prism and rhombic dodecahedron model is respectively 2.372239, 1.82615 and 1.49468 times of that of truncated octahedron model. So clearly truncated octahedron model has the highest network lifetime. We also provide a distributed topology control algorithm that can be used by each sensor node to determine its cell id using a constant number of local arithmetic operations provided that the sensor node knows its location. We also validate our results by simulation.


title: On the logical definability of certain graph and poset languages

abstract: We show that it is equivalent, for certain sets of finite graphs, to be definable in CMS (counting monadic second-order logic, a natural extension of monadic second-order logic), and to be recognizable in an algebraic framework induced by the notion of modular decomposition of a finite graph. More precisely, we consider the set $F\_\infty$ of composition operations on graphs which occur in the modular decomposition of finite graphs. If $F$ is a subset of $F\_{\infty}$, we say that a graph is an $\calF$-graph if it can be decomposed using only operations in $F$. A set of $F$-graphs is recognizable if it is a union of classes in a finite-index equivalence relation which is preserved by the operations in $F$. We show that if $F$ is finite and its elements enjoy only a limited amount of commutativity -- a property which we call weak rigidity, then recognizability is equivalent to CMS-definability. This requirement is weak enough to be satisfied whenever all $F$-graphs are posets, that is, transitive dags. In particular, our result generalizes Kuske's recent result on series-parallel poset languages.


title: Scanning and Sequential Decision Making for Multi-Dimensional Data - Part I: the Noiseless Case

abstract: We investigate the problem of scanning and prediction ("scandiction", for short) of multidimensional data arrays. This problem arises in several aspects of image and video processing, such as predictive coding, for example, where an image is compressed by coding the error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and whether there exist specific scandiction schemes which are universal in some sense. Specifically, we investigate the following problems: First, modeling the data array as a random field, we wish to examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution was known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a non-optimal scanning order is used, yet accompanied by an optimal predictor, and derive bounds on the excess loss compared to optimal scanning and prediction. This paper is the first part of a two-part paper on sequential decision making for multi-dimensional data. It deals with clean, noiseless data arrays. The second part deals with noisy data arrays, namely, with the case where the decision maker observes only a noisy version of the data, yet it is judged with respect to the original, clean data.


title: Exact Spectral Analysis of Single-h and Multi-h CPM Signals through PAM decomposition and Matrix Series Evaluation

abstract: In this paper we address the problem of closed-form spectral evaluation of CPM. We show that the multi-h CPM signal can be conveniently generated by a PTI SM. The output is governed by a Markov chain with the unusual peculiarity of being cyclostationary and reducible; this holds also in the single-h context. Judicious reinterpretation of the result leads to a formalization through a stationary and irreducible Markov chain, whose spectral evaluation is known in closed-form from the literature. Two are the major outcomes of this paper. First, unlike the literature, we obtain a PSD in true closed-form. Second, we give novel insights into the CPM format.


title: Multilingual person name recognition and transliteration

abstract: We present an exploratory tool that extracts person names from multilingual news collections, matches name variants referring to the same person, and infers relationships between people based on the co-occurrence of their names in related news. A novel feature is the matching of name variants across languages and writing systems, including names written with the Greek, Cyrillic and Arabic writing system. Due to our highly multilingual setting, we use an internal standard representation for name representation and matching, instead of adopting the traditional bilingual approach to transliteration. This work is part of the news analysis system NewsExplorer that clusters an average of 25,000 news articles per day to detect related news within the same and across different languages.


title: Undecidability of the unification and admissibility problems for modal and description logics

abstract: We show that the unification problem `is there a substitution instance of a given formula that is provable in a given logic?' is undecidable for basic modal logics K and K4 extended with the universal modality. It follows that the admissibility problem for inference rules is undecidable for these logics as well. These are the first examples of standard decidable modal logics for which the unification and admissibility problems are undecidable. We also prove undecidability of the unification and admissibility problems for K and K4 with at least two modal operators and nominals (instead of the universal modality), thereby showing that these problems are undecidable for basic hybrid logics. Recently, unification has been introduced as an important reasoning service for description logics. The undecidability proof for K with nominals can be used to show the undecidability of unification for boolean description logics with nominals (such as ALCO and SHIQO). The undecidability proof for K with the universal modality can be used to show that the unification problem relative to role boxes is undecidable for Boolean description logic with transitive roles, inverse roles, and role hierarchies (such as SHI and SHIQ).


title: Navigating multilingual news collections using automatically extracted information

abstract: We are presenting a text analysis tool set that allows analysts in various fields to sieve through large collections of multilingual news items quickly and to find information that is of relevance to them. For a given document collection, the tool set automatically clusters the texts into groups of similar articles, extracts names of places, people and organisations, lists the user-defined specialist terms found, links clusters and entities, and generates hyperlinks. Through its daily news analysis operating on thousands of articles per day, the tool also learns relationships between people and other entities. The fully functional prototype system allows users to explore and navigate multilingual document collections across languages and time.


title: High Data-Rate Single-Symbol ML Decodable Distributed STBCs for Cooperative Networks

abstract: High data-rate Distributed Orthogonal Space-Time Block Codes (DOSTBCs) which achieve the single-symbol decodability and full diversity order are proposed in this paper. An upper bound of the data-rate of the DOSTBC is derived and it is approximately twice larger than that of the conventional repetition-based cooperative strategy. In order to facilitate the systematic constructions of the DOSTBCs achieving the upper bound of the data-rate, some special DOSTBCs, which have diagonal noise covariance matrices at the destination terminal, are investigated. These codes are referred to as the row-monomial DOSTBCs. An upper bound of the data-rate of the row-monomial DOSTBC is derived and it is equal to or slightly smaller than that of the DOSTBC. Lastly, the systematic construction methods of the row-monomial DOSTBCs achieving the upper bound of the data-rate are presented.


title: Coding for Additive White Noise Channels with Feedback Corrupted by Uniform Quantization or Bounded Noise

abstract: We present simple coding strategies, which are variants of the Schalkwijk-Kailath scheme, for communicating reliably over additive white noise channels in the presence of corrupted feedback. More specifically, we consider a framework comprising an additive white forward channel and a backward link which is used for feedback. We consider two types of corruption mechanisms in the backward link. The first is quantization noise, i.e., the encoder receives the quantized values of the past outputs of the forward channel. The quantization is uniform, memoryless and time invariant (that is, symbol-by-symbol scalar quantization), with bounded quantization error. The second corruption mechanism is an arbitrarily distributed additive bounded noise in the backward link. Here we allow symbol-by-symbol encoding at the input to the backward channel. We propose simple explicit schemes that guarantee positive information rate, in bits per channel use, with positive error exponent. If the forward channel is additive white Gaussian then our schemes achieve capacity, in the limit of diminishing amplitude of the noise components at the backward link, while guaranteeing that the probability of error converges to zero as a doubly exponential function of the block length. Furthermore, if the forward channel is additive white Gaussian and the backward link consists of an additive bounded noise channel, with signal-to-noise ratio (SNR) constrained symbol-by-symbol encoding, then our schemes are also capacity-achieving in the limit of high SNR.


title: Matrix Games, Linear Programming, and Linear Approximation

abstract: The following four classes of computational problems are equivalent: solving matrix games, solving linear programs, best $l^{\infty}$ linear approximation, best $l^1$ linear approximation.


title: Concurrently Non-Malleable Zero Knowledge in the Authenticated Public-Key Model

abstract: We consider a type of zero-knowledge protocols that are of interest for their practical applications within networks like the Internet: efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks. In an effort to reduce the setup assumptions required for efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks, we consider a model, which we call the Authenticated Public-Key (APK) model. The APK model seems to significantly reduce the setup assumptions made by the CRS model (as no trusted party or honest execution of a centralized algorithm are required), and can be seen as a slightly stronger variation of the Bare Public-Key (BPK) model from \cite{CGGM,MR}, and a weaker variation of the registered public-key model used in \cite{BCNP}. We then define and study man-in-the-middle attacks in the APK model. Our main result is a constant-round concurrent non-malleable zero-knowledge argument of knowledge for any polynomial-time relation (associated to a language in $\mathcal{NP}$), under the (minimal) assumption of the existence of a one-way function family. Furthermore,We show time-efficient instantiations of our protocol based on known number-theoretic assumptions. We also note a negative result with respect to further reducing the setup assumptions of our protocol to those in the (unauthenticated) BPK model, by showing that concurrently non-malleable zero-knowledge arguments of knowledge in the BPK model are only possible for trivial languages.


title: The JRC-Acquis: A multilingual aligned parallel corpus with 20+ languages

abstract: We present a new, unique and freely available parallel corpus containing European Union (EU) documents of mostly legal nature. It is available in all 20 official EUanguages, with additional documents being available in the languages of the EU candidate countries. The corpus consists of almost 8,000 documents per language, with an average size of nearly 9 million words per language. Pair-wise paragraph alignment information produced by two different aligners (Vanilla and HunAlign) is available for all 190+ language pair combinations. Most texts have been manually classified according to the EUROVOC subject domains so that the collection can also be used to train and test multi-label classification algorithms and keyword-assignment software. The corpus is encoded in XML, according to the Text Encoding Initiative Guidelines. Due to the large number of parallel texts in many languages, the JRC-Acquis is particularly suitable to carry out all types of cross-language research, as well as to test and benchmark text analysis software across different languages (for instance for alignment, sentence splitting and term extraction).


title: Automatic annotation of multilingual text collections with a conceptual thesaurus

abstract: Automatic annotation of documents with controlled vocabulary terms (descriptors) from a conceptual thesaurus is not only useful for document indexing and retrieval. The mapping of texts onto the same thesaurus furthermore allows to establish links between similar documents. This is also a substantial requirement of the Semantic Web. This paper presents an almost language-independent system that maps documents written in different languages onto the same multilingual conceptual thesaurus, EUROVOC. Conceptual thesauri differ from Natural Language Thesauri in that they consist of relatively small controlled lists of words or phrases with a rather abstract meaning. To automatically identify which thesaurus descriptors describe the contents of a document best, we developed a statistical, associative system that is trained on texts that have previously been indexed manually. In addition to describing the large number of empirically optimised parameters of the fully functional application, we present the performance of the software according to a human evaluation by professional indexers.


title: Automatic Identification of Document Translations in Large Multilingual Document Collections

abstract: Texts and their translations are a rich linguistic resource that can be used to train and test statistics-based Machine Translation systems and many other applications. In this paper, we present a working system that can identify translations and other very similar documents among a large number of candidates, by representing the document contents with a vector of thesaurus terms from a multilingual thesaurus, and by then measuring the semantic similarity between the vectors. Tests on different text types have shown that the system can detect translations with over 96% precision in a large search space of 820 documents or more. The system was tuned to ignore language-specific similarities and to give similar documents in a second language the same similarity score as equivalent documents in the same language. The application can also be used to detect cross-lingual document plagiarism.


title: Cross-lingual keyword assignment

abstract: This paper presents a language-independent approach to controlled vocabulary keyword assignment using the EUROVOC thesaurus. Due to the multilingual nature of EUROVOC, the keywords for a document written in one language can be displayed in all eleven official European Union languages. The mapping of documents written in different languages to the same multilingual thesaurus furthermore allows cross-language document comparison. The assignment of the controlled vocabulary thesaurus descriptors is achieved by applying a statistical method that uses a collection of manually indexed documents to identify, for each thesaurus descriptor, a large number of lemmas that are statistically associated to the descriptor. These associated words are then used during the assignment procedure to identify a ranked list of those EUROVOC terms that are most likely to be good keywords for a given document. The paper also describes the challenges of this task and discusses the achieved results of the fully functional prototype.


title: Nominal Logic Programming

abstract: Nominal logic is an extension of first-order logic which provides a simple foundation for formalizing and reasoning about abstract syntax modulo consistent renaming of bound names (that is, alpha-equivalence). This article investigates logic programming based on nominal logic. We describe some typical nominal logic programs, and develop the model-theoretic, proof-theoretic, and operational semantics of such programs. Besides being of interest for ensuring the correct behavior of implementations, these results provide a rigorous foundation for techniques for analysis and reasoning about nominal logic programs, as we illustrate via examples.


title: Extending an Information Extraction tool set to Central and Eastern European languages

abstract: In a highly multilingual and multicultural environment such as in the European Commission with soon over twenty official languages, there is an urgent need for text analysis tools that use minimal linguistic knowledge so that they can be adapted to many languages without much human effort. We are presenting two such Information Extraction tools that have already been adapted to various Western and Eastern European languages: one for the recognition of date expressions in text, and one for the detection of geographical place names and the visualisation of the results in geographical maps. An evaluation of the performance has produced very satisfying results.


title: Exploiting multilingual nomenclatures and language-independent text features as an interlingua for cross-lingual text analysis applications

abstract: We are proposing a simple, but efficient basic approach for a number of multilingual and cross-lingual language technology applications that are not limited to the usual two or three languages, but that can be applied with relatively little effort to larger sets of languages. The approach consists of using existing multilingual linguistic resources such as thesauri, nomenclatures and gazetteers, as well as exploiting the existence of additional more or less language-independent text items such as dates, currency expressions, numbers, names and cognates. Mapping texts onto the multilingual resources and identifying word token links between texts in different languages are basic ingredients for applications such as cross-lingual document similarity calculation, multilingual clustering and categorisation, cross-lingual document retrieval, and tools to provide cross-lingual information access.


title: Geocoding multilingual texts: Recognition, disambiguation and visualisation

abstract: We are presenting a method to recognise geographical references in free text. Our tool must work on various languages with a minimum of language-dependent resources, except a gazetteer. The main difficulty is to disambiguate these place names by distinguishing places from persons and by selecting the most likely place out of a list of homographic place names world-wide. The system uses a number of language-independent clues and heuristics to disambiguate place name homographs. The final aim is to index texts with the countries and cities they mention and to automatically visualise this information on geographical maps using various tools.


title: Building and displaying name relations using automatic unsupervised analysis of newspaper articles

abstract: We present a tool that, from automatically recognised names, tries to infer inter-person relations in order to present associated people on maps. Based on an in-house Named Entity Recognition tool, applied on clusters of an average of 15,000 news articles per day, in 15 different languages, we build a knowledge base that allows extracting statistical co-occurrences of persons and visualising them on a per-person page or in various graphs.


title: A tool set for the quick and efficient exploration of large document collections

abstract: We are presenting a set of multilingual text analysis tools that can help analysts in any field to explore large document collections quickly in order to determine whether the documents contain information of interest, and to find the relevant text passages. The automatic tool, which currently exists as a fully functional prototype, is expected to be particularly useful when users repeatedly have to sieve through large collections of documents such as those downloaded automatically from the internet. The proposed system takes a whole document collection as input. It first carries out some automatic analysis tasks (named entity recognition, geo-coding, clustering, term extraction), annotates the texts with the generated meta-information and stores the meta-information in a database. The system then generates a zoomable and hyperlinked geographic map enhanced with information on entities and terms found. When the system is used on a regular basis, it builds up a historical database that contains information on which names have been mentioned together with which other names or places, and users can query this database to retrieve information extracted in the past.


title: The heterogeneity of inter-contact time distributions: its importance for routing in delay tolerant networks

abstract: Prior work on routing in delay tolerant networks (DTNs) has commonly made the assumption that each pair of nodes shares the same inter-contact time distribution as every other pair. The main argument in this paper is that researchers should also be looking at heterogeneous inter-contact time distributions. We demonstrate the presence of such heterogeneity in the often-used Dartmouth Wi-Fi data set. We also show that DTN routing can benefit from knowing these distributions. We first introduce a new stochastic model focusing on the inter-contact time distributions between all pairs of nodes, which we validate on real connectivity patterns. We then analytically derive the mean delivery time for a bundle of information traversing the network for simple single copy routing schemes. The purpose is to examine the theoretic impact of heterogeneous inter-contact time distributions. Finally, we show that we can exploit this user diversity to improve routing performance.


title: Coverage and Connectivity in Three-Dimensional Networks

abstract: Most wireless terrestrial networks are designed based on the assumption that the nodes are deployed on a two-dimensional (2D) plane. However, this 2D assumption is not valid in underwater, atmospheric, or space communications. In fact, recent interest in underwater acoustic ad hoc and sensor networks hints at the need to understand how to design networks in 3D. Unfortunately, the design of 3D networks is surprisingly more difficult than the design of 2D networks. For example, proofs of Kelvin's conjecture and Kepler's conjecture required centuries of research to achieve breakthroughs, whereas their 2D counterparts are trivial to solve. In this paper, we consider the coverage and connectivity issues of 3D networks, where the goal is to find a node placement strategy with 100% sensing coverage of a 3D space, while minimizing the number of nodes required for surveillance. Our results indicate that the use of the Voronoi tessellation of 3D space to create truncated octahedral cells results in the best strategy. In this truncated octahedron placement strategy, the transmission range must be at least 1.7889 times the sensing range in order to maintain connectivity among nodes. If the transmission range is between 1.4142 and 1.7889 times the sensing range, then a hexagonal prism placement strategy or a rhombic dodecahedron placement strategy should be used. Although the required number of nodes in the hexagonal prism and the rhombic dodecahedron placement strategies is the same, this number is 43.25% higher than the number of nodes required by the truncated octahedron placement strategy. We verify by simulation that our placement strategies indeed guarantee ubiquitous coverage. We believe that our approach and our results presented in this paper could be used for extending the processes of 2D network design to 3D networks.


title: Exploring Computer Science Concepts with a Ready-made Computer Game Framework

abstract: Leveraging the prevailing interest in computer games among college students, both for entertainment and as a possible career path, is a major reason for the increasing prevalence of computer game design courses in computer science curricula. Because implementing a computer game requires strong programming skills, game design courses are most often restricted to more advanced computer science students. This paper reports on a ready-made game design and experimentation framework, implemented in Java, that makes game programming more widely accessible. This framework, called Labyrinth, enables students at all programming skill levels to participate in computer game design. We describe the architecture of the framework, and discuss programming projects suitable for a wide variety of computer science courses, from capstone to non-major.


title: A kernel method for canonical correlation analysis

abstract: Canonical correlation analysis is a technique to extract common features from a pair of multivariate data. In complex situations, however, it does not extract useful features because of its linearity. On the other hand, kernel method used in support vector machine is an efficient approach to improve such a linear method. In this paper, we investigate the effectiveness of applying kernel method to canonical correlation analysis.


title: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

abstract: Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions of Boolean satisfiability problems and establish various dichotomies in Schaefer's framework. On the structural side, we obtain dichotomies for the kinds of subgraphs of the hypercube that can be induced by the solutions of Boolean formulas, as well as for the diameter of the connected components of the solution space. On the computational side, we establish dichotomy theorems for the complexity of the connectivity and st-connectivity questions for the graph of solutions of Boolean formulas. Our results assert that the intractable side of the computational dichotomies is PSPACE-complete, while the tractable side - which includes but is not limited to all problems with polynomial time algorithms for satisfiability - is in P for the st-connectivity question, and in coNP for the connectivity question. The diameter of components can be exponential for the PSPACE-complete cases, whereas in all other cases it is linear; thus, small diameter and tractability of the connectivity problems are remarkably aligned. The crux of our results is an expressibility theorem showing that in the tractable cases, the subgraphs induced by the solution space possess certain good structural properties, whereas in the intractable cases, the subgraphs can be arbitrary.


title: Optimal power allocation for downlink cooperative cellular networks

abstract: This paper has been withdrawn by the author


title: A Non-anchored Unified Naming System for Ad Hoc Computing Environments

abstract: A ubiquitous computing environment consists of many resources that need to be identified by users and applications. Users and developers require some way to identify resources by human readable names. In addition, ubiquitous computing environments impose additional requirements such as the ability to work well with ad hoc situations and the provision of names that depend on context. The Non-anchored Unified Naming (NUN) system was designed to satisfy these requirements. It is based on relative naming among resources and provides the ability to name arbitrary types of resources. By having resources themselves take part in naming, resources are able to able contribute their specialized knowledge into the name resolution process, making context-dependent mapping of names to resources possible. The ease of which new resource types can be added makes it simple to incorporate new types of contextual information within names. In this paper, we describe the naming system and evaluate its use.


title: On factorization and solution of multidimensional linear partial differential equations

abstract: We describe a method of obtaining closed-form complete solutions of certain second-order linear partial differential equations with more than two independent variables. This method generalizes the classical method of Laplace transformations of second-order hyperbolic equations in the plane and is based on an idea given by Ulisse Dini in 1902.


title: Asymptotic Spectral Distribution of Crosscorrelation Matrix in Asynchronous CDMA

abstract: Asymptotic spectral distribution (ASD) of the crosscorrelation matrix is investigated for a random spreading short/long-code asynchronous direct sequence-code division multiple access (DS-CDMA) system. The discrete-time decision statistics are obtained as the output samples of a bank of symbol matched filters of all users. The crosscorrelation matrix is studied when the number of symbols transmitted by each user tends to infinity. Two levels of asynchronism are considered. One is symbol-asynchronous but chip-synchronous, and the other is chip-asynchronous. The existence of a nonrandom ASD is proved by moment convergence theorem, where the focus is on the derivation of asymptotic eigenvalue moments (AEM) of the crosscorrelation matrix. A combinatorics approach based on noncrossing partition of set partition theory is adopted for AEM computation. The spectral efficiency and the minimum mean-square-error (MMSE) achievable by a linear receiver of asynchronous CDMA are plotted by AEM using a numerical method.


title: On Intentional Attacks and Protections in Complex Communication Networks

abstract: Being motivated by recent developments in the theory of complex networks, we examine the robustness of communication networks under intentional attack that takes down network nodes in a decreasing order of their nodal degrees. In this paper, we study two different effects that have been largely missed in the existing results: (i) some communication networks, like Internet, are too large for anyone to have global information of their topologies, which makes the accurate intentional attack practically impossible; and (ii) most attacks in communication networks are propagated from one node to its neighborhood node(s), utilizing local network-topology information only. We show that incomplete global information has different impacts to the intentional attack in different circumstances, while local information-based attacks can be actually highly efficient. Such insights would be helpful for the future developments of efficient network attack/protection schemes.


title: A Continuum Theory for Unstructured Mesh Generation in Two Dimensions

abstract: A continuum description of unstructured meshes in two dimensions, both for planar and curved surface domains, is proposed. The meshes described are those which, in the limit of an increasingly finer mesh (smaller cells), and away from irregular vertices, have ideally-shaped cells (squares or equilateral triangles), and can therefore be completely described by two local properties: local cell size and local edge directions. The connection between the two properties is derived by defining a Riemannian manifold whose geodesics trace the edges of the mesh. A function $\phi$, proportional to the logarithm of the cell size, is shown to obey the Poisson equation, with localized charges corresponding to irregular vertices. The problem of finding a suitable manifold for a given domain is thus shown to exactly reduce to an Inverse Poisson problem on $\phi$, of finding a distribution of localized charges adhering to the conditions derived for boundary alignment. Possible applications to mesh generation are discussed.


title: Modern Statistics by Kriging

abstract: We present statistics (S-statistics) based only on random variable (not random value) with a mean squared error of mean estimation as a concept of error.


title: Solution of a Problem of Barendregt on Sensible lambda-Theories

abstract: H is the theory extending β-conversion by identifying all closed unsolvables. Hω is the closure of this theory under the ω-rule (and β-conversion). A long-standing conjecture of H. Barendregt states that the provable equations of Hω form Π11-complete set. Here we prove that conjecture.


title: Recurrence relations and fast algorithms

abstract: We construct fast algorithms for evaluating transforms associated with families of functions which satisfy recurrence relations. These include algorithms both for computing the coefficients in linear combinations of the functions, given the values of these linear combinations at certain points, and, vice versa, for evaluating such linear combinations at those points, given the coefficients in the linear combinations; such procedures are also known as analysis and synthesis of series of certain special functions. The algorithms of the present paper are efficient in the sense that their computational costs are proportional to n (ln n) (ln(1/epsilon))^3, where n is the amount of input and output data, and epsilon is the precision of computations. Stated somewhat more precisely, we find a positive real number C such that, for any positive integer n > 10, the algorithms require at most C n (ln n) (ln(1/epsilon))^3 floating-point operations and words of memory to evaluate at n appropriately chosen points any linear combination of n special functions, given the coefficients in the linear combination, where epsilon is the precision of computations.


title: Classifying extrema using intervals

abstract: We present a straightforward and verified method of deciding whether the n-dimensional point x (n>=1), such that \nabla f(x)=0, is the local minimizer, maximizer or just a saddle point of a real-valued function f. The method scales linearly with dimensionality of the problem and never produces false results.


title: k-Colorability of P5-free graphs

abstract: A polynomial time algorithm that determines for a fixed integer k whether or not a P5-free graph can be k-colored is presented in this paper. If such a coloring exists, the algorithm will produce a valid k-coloring.


title: Non-photorealistic image rendering with a labyrinthine tiling

abstract: The paper describes a new image processing for a non-photorealistic rendering. The algorithm is based on a random generation of gray tones and competing statistical requirements. The gray tone value of each pixel in the starting image is replaced selecting among randomly generated tone values, according to the statistics of nearest-neighbor and next-nearest-neighbor pixels. Two competing conditions for replacing the tone values - one position on the local mean value the other on the local variance - produce a peculiar pattern on the image. This pattern has a labyrinthine tiling aspect. For certain subjects, the pattern enhances the look of the image.


title: Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts

abstract: We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes. We present a time-space trade-off that leads to algorithms improving the previously known complexities for both problems. In particular, we significantly improve the space bounds, which in practical applications are likely to be a bottleneck.


title: About the Capacity of Flat and Self-Organized Ad Hoc and Hybrid Networks

abstract: Ad hoc networking specific challenges foster a strong research effort on efficient protocols design. Routing protocols based on a self-organized structure have been studied principally for the robustness and the scalability they provide. On the other hand, self-organization schemes may decrease the network capacity since they concentrate the traffic on privileged links. This paper presents four models for evaluating the capacity of a routing schemes on 802.11 like networks. Our approach consists in modeling the radio resource sharing principles of 802.11 like MAC protocols as a set of linear constraints. We have implemented two models of fairness. The first one assumes that nodes have a fair access to the channel, while the second one assumes that on the radio links. We then develop a pessimistic and an optimistic scenarii of spatial re-utilization of the medium, yielding a lower bound and an upper bound on the network capacity for each fairness case. Our models are independent of the routing protocols and provide therefore a relevant framework for their comparison. We apply our models to a comparative analysis of the well-known shortest path base flat routing protocol OLSR against two main self-organized structure approaches, VSR, and Wu & Li's protocols. This study concludes on the relevance of self-organized approaches from the network capacity point of view.


title: A comparative analysis of the geometrical surface texture of a real and virtual model of a tooth flank of a cylindrical gear

abstract: The paper presents the methodology of modelling tooth flanks of cylindrical gears in the Cad environment. The modelling consists in a computer simulation of gear generation. A model of tooth flanks is an envelope curve of a family of envelopes that originate from the rolling motion of a solid tool model in relation to a solid model of the cylindrical gear. The surface stereometry and topography of the tooth flanks, hobbed and chiselled by Fellows method, are compared to their numerical models. Metrological measurements of the real gears were carried out using a coordinated measuring machine and a two - and a three-dimensional profilometer. A computer simulation of the gear generation was performed in the Mechanical Desktop environment.


title: Deriving the Normalized Min-Sum Algorithm from Cooperative Optimization

abstract: The normalized min-sum algorithm can achieve near-optimal performance at decoding LDPC codes. However, it is a critical question to understand the mathematical principle underlying the algorithm. Traditionally, people thought that the normalized min-sum algorithm is a good approximation to the sum-product algorithm, the best known algorithm for decoding LDPC codes and Turbo codes. This paper offers an alternative approach to understand the normalized min-sum algorithm. The algorithm is derived directly from cooperative optimization, a newly discovered general method for global/combinatorial optimization. This approach provides us another theoretical basis for the algorithm and offers new insights on its power and limitation. It also gives us a general framework for designing new decoding algorithms.


title: Fast Min-Sum Algorithms for Decoding of LDPC over GF(q)

abstract: In this paper, we present a fast min-sum algorithm for decoding LDPC codes over GF(q). Our algorithm is different from the one presented by David Declercq and Marc Fossorier in ISIT 05 only at the way of speeding up the horizontal scan in the min-sum algorithm. The Declercq and Fossorier's algorithm speeds up the computation by reducing the number of configurations, while our algorithm uses the dynamic programming instead. Compared with the configuration reduction algorithm, the dynamic programming one is simpler at the design stage because it has less parameters to tune. Furthermore, it does not have the performance degradation problem caused by the configuration reduction because it searches the whole configuration space efficiently through dynamic programming. Both algorithms have the same level of complexity and use simple operations which are suitable for hardware implementations.


title: Single-Scan Min-Sum Algorithms for Fast Decoding of LDPC Codes

abstract: Many implementations for decoding LDPC codes are based on the (normalized/offset) min-sum algorithm due to its satisfactory performance and simplicity in operations. Usually, each iteration of the min-sum algorithm contains two scans, the horizontal scan and the vertical scan. This paper presents a single-scan version of the min-sum algorithm to speed up the decoding process. It can also reduce memory usage or wiring because it only needs the addressing from check nodes to variable nodes while the original min-sum algorithm requires that addressing plus the addressing from variable nodes to check nodes. To cut down memory usage or wiring further, another version of the single-scan min-sum algorithm is presented where the messages of the algorithm are represented by single bit values instead of using fixed point ones. The software implementation has shown that the single-scan min-sum algorithm is more than twice as fast as the original min-sum algorithm.


title: Using shifted conjugacy in braid-based cryptography

abstract: Conjugacy is not the only possible primitive for designing braid-based protocols. To illustrate this principle, we describe a Fiat--Shamir-style authentication protocol that be can be implemented using any binary operation that satisfies the left self-distributive law. Conjugation is an example of such an operation, but there are other examples, in particular the shifted conjugation on Artin's braid group B\_oo, and the finite Laver tables. In both cases, the underlying structures have a high combinatorial complexity, and they lead to difficult problems.


title: Analysis of Equality Relationships for Imperative Programs

abstract: In this article, we discuss a flow--sensitive analysis of equality relationships for imperative programs. We describe its semantic domains, general purpose operations over abstract computational states (term evaluation and identification, semantic completion, widening operator, etc.) and semantic transformers corresponding to program constructs. We summarize our experiences from the last few years concerning this analysis and give attention to applications of analysis of automatically generated code. Among other illustrating examples, we consider a program for which the analysis diverges without a widening operator and results of analyzing residual programs produced by some automatic partial evaluator. An example of analysis of a program generated by this evaluator is given.


title: PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption

abstract: We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. Here the task is to construct a hypothesis mixture of Gaussians that is statistically indistinguishable from the actual mixture generating the data; specifically, the KL-divergence should be at most epsilon. In this scenario, we give a poly(n/epsilon)-time algorithm that learns the class of mixtures of any constant number of axis-aligned Gaussians in n-dimensional Euclidean space. Our algorithm makes no assumptions about the separation between the means of the Gaussians, nor does it have any dependence on the minimum mixing weight. This is in contrast to learning results known in the ``clustering'' model, where such assumptions are unavoidable. Our algorithm relies on the method of moments, and a subalgorithm developed in previous work by the authors (FOCS 2005) for a discrete mixture-learning problem.


title: An Improved Sphere-Packing Bound Targeting Codes of Short to Moderate Block Lengths and Applications

abstract: This paper derives an improved sphere-packing (ISP) bound targeting codes of short to moderate block lengths. We first review the 1967 sphere-packing (SP67) bound for discrete memoryless channels, and a recent improvement by Valembois and Fossorier. These concepts are used for the derivation of a new lower bound on the decoding error probability (referred to as the ISP bound) which is uniformly tighter than the SP67 bound and its recent improved version. Under a mild condition, the ISP bound is applicable to general memoryless channels, and some of its applications are exemplified. Its tightness is studied by comparing it with bounds on the ML decoding error probability. It is exemplified that the ISP bound suggests an interesting alternative to the 1959 sphere-packing (SP59) bound of Shannon for the Gaussian channel, especially for digital modulations of high spectral efficiency.


title: Free Choice Petri Nets without frozen tokens and Bipolar Synchronization Systems

abstract: Bipolar synchronization systems (BP-systems) constitute a class of coloured Petri nets, well suited for modeling the control flow of discrete, dynamical systems. Every BP-system has an underlying ordinary Petri net, which is a T-system. Moreover, it has a second ordinary net attached, which is a free-choice system. We prove that a BP-system is live and safe if the T-system and the free-choice system are live and safe and if the free-choice system has no frozen tokens. This result is the converse of a theorem of Genrich and Thiagarajan and proves an elder conjecture. The proof compares the different Petri nets by Petri net morphisms and makes use of the classical theory of free-choice systems


title: Finite-State Dimension and Lossy Decompressors

abstract: This paper examines information-theoretic questions regarding the difficulty of compressing data versus the difficulty of decompressing data and the role that information loss plays in this interaction. Finite-state compression and decompression are shown to be of equivalent difficulty, even when the decompressors are allowed to be lossy. Inspired by Kolmogorov complexity, this paper defines the optimal *decompression *ratio achievable on an infinite sequence by finite-state decompressors (that is, finite-state transducers outputting the sequence in question). It is shown that the optimal compression ratio achievable on a sequence S by any *information lossless* finite state compressor, known as the finite-state dimension of S, is equal to the optimal decompression ratio achievable on S by any finite-state decompressor. This result implies a new decompression characterization of finite-state dimension in terms of lossy finite-state transducers.


title: Traveing Salesperson Problems for a double integrator

abstract: In this paper we propose some novel path planning strategies for a double integrator with bounded velocity and bounded control inputs. First, we study the following version of the Traveling Salesperson Problem (TSP): given a set of points in $\real^d$, find the fastest tour over the point set for a double integrator. We first give asymptotic bounds on the time taken to complete such a tour in the worst-case. Then, we study a stochastic version of the TSP for double integrator where the points are randomly sampled from a uniform distribution in a compact environment in $\real^2$ and $\real^3$. We propose novel algorithms that perform within a constant factor of the optimal strategy with high probability. Lastly, we study a dynamic TSP: given a stochastic process that generates targets, is there a policy which guarantees that the number of unvisited targets does not diverge over time? If such stable policies exist, what is the minimum wait for a target? We propose novel stabilizing receding-horizon algorithms whose performances are within a constant factor from the optimum with high probability, in $\real^2$ as well as $\real^3$. We also argue that these algorithms give identical performances for a particular nonholonomic vehicle, Dubins vehicle.


title: Reducing the Makespan in Hierarchical Reliable Multicast Tree

abstract: In hierarchical reliable multicast environment, makespan is the time that is required to fully and successfully transmit a packet from the sender to all receivers. Low makespan is vital for achieving high throughput with a TCP-like window based sending scheme. In hierarchical reliable multicast methods, the number of repair servers and their locations influence the makespan. In this paper we propose a new method to decide the locations of repair servers that can reduce the makespan in hierarchical reliable multicast networks. Our method has a formulation based on mixed integer programming to analyze the makespan minimization problem. A notable aspect of the formulation is that heterogeneous links and packet losses are taken into account in the formulation. Three different heuristics are presented to find the locations of repair servers in reasonable time in the formulation. Through simulations, three heuristics are carefully analyzed and compared on networks with different sizes. We also evaluate our proposals on PGM (Pragmatic General Multicast) reliable multicast protocol using ns-2 simulation. The results show that the our best heuristic is close to the lower bound by a factor of 2.3 in terms of makespan and by a factor of 5.5 in terms of the number of repair servers.


title: Coding for Parallel Channels: Gallager Bounds and Applications to Repeat-Accumulate Codes

abstract: This paper is focused on the performance analysis of binary linear block codes (or ensembles) whose transmission takes place over independent and memoryless parallel channels. New upper bounds on the maximum-likelihood (ML) decoding error probability are derived. The framework of the second version of the Duman and Salehi (DS2) bounds is generalized to the case of parallel channels, along with the derivation of optimized tilting measures. The connection between the generalized DS2 and the 1961 Gallager bounds, known previously for a single channel, is revisited for the case of parallel channels. The new bounds are used to obtain improved inner bounds on the attainable channel regions under ML decoding. These improved bounds are applied to ensembles of turbo-like codes, focusing on repeat-accumulate codes and their recent variations.


title: Total Variation Minimization and Graph Cuts for Moving Objects Segmentation

abstract: In this paper, we are interested in the application to video segmentation of the discrete shape optimization problem involving the shape weighted perimeter and an additional term depending on a parameter. Based on recent works and in particular the one of Darbon and Sigelle, we justify the equivalence of the shape optimization problem and a weighted total variation regularization. For solving this problem, we adapt the projection algorithm proposed recently for solving the basic TV regularization problem. Another solution to the shape optimization investigated here is the graph cut technique. Both methods have the advantage to lead to a global minimum. Since we can distinguish moving objects from static elements of a scene by analyzing norm of the optical flow vectors, we choose the optical flow norm as initial data. In order to have the contour as close as possible to an edge in the image, we use a classical edge detector function as the weight of the weighted total variation. This model has been used in one of our former works. We also apply the same methods to a video segmentation model used by Jehan-Besson, Barlaud and Aubert. In this case, only standard perimeter is incorporated in the shape functional. We also propose another way for finding moving objects by using an a contrario detection of objects on the image obtained by solving the Rudin-Osher-Fatemi Total Variation regularization problem.We can notice the segmentation can be associated to a level set in the former methods.


title: Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios

abstract: For large clause-to-variable ratio, typical K-SAT instances drawn from the uniform distribution have no solution. We argue, based on statistical mechanics calculations using the replica and cavity methods, that rare satisfiable instances from the uniform distribution are very similar to typical instances drawn from the so-called planted distribution, where instances are chosen uniformly between the ones that admit a given solution. It then follows, from a recent article by Feige, Mossel and Vilenchik, that these rare instances can be easily recognized (in O(log N) time and with probability close to 1) by a simple message-passing algorithm.


title: Using groups for investigating rewrite systems

abstract: We describe several technical tools that prove to be efficient for investigating the rewrite systems associated with a family of algebraic laws, and might be useful for more general rewrite systems. These tools consist in introducing a monoid of partial operators, listing the monoid relations expressing the possible local confluence of the rewrite system, then introducing the group presented by these relations, and finally replacing the initial rewrite system with a internal process entirely sitting in the latter group. When the approach can be completed, one typically obtains a practical method for constructing algebras satisfying prescribed laws and for solving the associated word problem.


title: Minimum-weight Cycle Covers and Their Approximability

abstract: A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise a polynomial-time approximation algorithm that achieves a constant approximation ratio for all sets L. On the other hand, we prove that the problem cannot be approximated within a factor of 2-eps for certain sets L. For directed graphs, we present a polynomial-time approximation algorithm that achieves an approximation ratio of O(n), where $n$ is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated within a factor of o(n). To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.