title: Conditional Expressions for Blind Deconvolution: Derivative form

abstract:
  We developed novel conditional expressions (CEs) for Lane and Bates' blind
deconvolution. The CEs are given in term of the derivatives of the zero-values
of the z-transform of given images. The CEs make it possible to automatically
detect multiple blur convolved in the given images all at once without
performing any analysis of the zero-sheets of the given images. We illustrate
the multiple blur-detection by the CEs for a model image


title:
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with
  Constant Average Distortion

abstract:
  This paper addresses the basic question of how well can a tree approximate
distances of a metric space or a graph. Given a graph, the problem of
constructing a spanning tree in a graph which strongly preserves distances in
the graph is a fundamental problem in network design. We present scaling
distortion embeddings where the distortion scales as a function of $\epsilon$,
with the guarantee that for each $\epsilon$ the distortion of a fraction
$1-\epsilon$ of all pairs is bounded accordingly. Such a bound implies, in
particular, that the \emph{average distortion} and $\ell_q$-distortions are
small. Specifically, our embeddings have \emph{constant} average distortion and
$O(\sqrt{\log n})$ $\ell_2$-distortion. This follows from the following
results: we prove that any metric space embeds into an ultrametric with scaling
distortion $O(\sqrt{1/\epsilon})$. For the graph setting we prove that any
weighted graph contains a spanning tree with scaling distortion
$O(\sqrt{1/\epsilon})$. These bounds are tight even for embedding in arbitrary
trees.
  For probabilistic embedding into spanning trees we prove a scaling distortion
of $\tilde{O}(\log^2 (1/\epsilon))$, which implies \emph{constant}
$\ell_q$-distortion for every fixed $q<\infty$.


title: Rapport technique du projet OGRE

abstract:
  This repport concerns automatic understanding of (french) iterative
sentences, i.e. sentences where one single verb has to be interpreted by a more
or less regular plurality of events. A linguistic analysis is proposed along an
extension of Reichenbach's theory, several formal representations are
considered and a corpus of 18000 newspaper extracts is described.


title: Domain Wall Displacement Detection Technology Research Report

abstract:
  This article introduce a new data storage method called DWDD(Domain Wall
Displacement Detection) and tell you why it succeed.


title:
A Typed Hybrid Description Logic Programming Language with Polymorphic
  Order-Sorted DL-Typed Unification for Semantic Web Type Systems

abstract:
  In this paper we elaborate on a specific application in the context of hybrid
description logic programs (hybrid DLPs), namely description logic Semantic Web
type systems (DL-types) which are used for term typing of LP rules based on a
polymorphic, order-sorted, hybrid DL-typed unification as procedural semantics
of hybrid DLPs. Using Semantic Web ontologies as type systems facilitates
interchange of domain-independent rules over domain boundaries via dynamically
typing and mapping of explicitly defined type ontologies.


title: Full Text Searching in the Astrophysics Data System

abstract:
  The Smithsonian/NASA Astrophysics Data System (ADS) provides a search system
for the astronomy and physics scholarly literature. All major and many smaller
astronomy journals that were published on paper have been scanned back to
volume 1 and are available through the ADS free of charge. All scanned pages
have been converted to text and can be searched through the ADS Full Text
Search System. In addition, searches can be fanned out to several external
search systems to include the literature published in electronic form. Results
from the different search systems are combined into one results list.
  The ADS Full Text Search System is available at:
http://adsabs.harvard.edu/fulltext_service.html


title: Connectivity in the Astronomy Digital Library

abstract:
  The Astrophysics Data System (ADS) provides an extensive system of links
between the literature and other on-line information. Recently, the journals of
the American Astronomical Society (AAS) and a group of NASA data centers have
collaborated to provide more links between on-line data obtained by space
missions and the on-line journals. Authors can now specify which data sets they
have used in their article. This information is used by the participants to
provide the links between the literature and the data.
  The ADS is available at: http://ads.harvard.edu


title: VPSPACE and a Transfer Theorem over the Reals

abstract:
  We introduce a new class VPSPACE of families of polynomials. Roughly
speaking, a family of polynomials is in VPSPACE if its coefficients can be
computed in polynomial space. Our main theorem is that if (uniform,
constant-free) VPSPACE families can be evaluated efficiently then the class PAR
of decision problems that can be solved in parallel polynomial time over the
real numbers collapses to P. As a result, one must first be able to show that
there are VPSPACE families which are hard to evaluate in order to separate over
the reals P from NP, or even from PAR.


title: One-Pass, One-Hash n-Gram Statistics Estimation

abstract:
  In multimedia, text or bioinformatics databases, applications query sequences
of n consecutive symbols called n-grams. Estimating the number of distinct
n-grams is a view-size estimation problem. While view sizes can be estimated by
sampling under statistical assumptions, we desire an unassuming algorithm with
universally valid accuracy bounds. Most related work has focused on repeatedly
hashing the data, which is prohibitive for large data sources. We prove that a
one-pass one-hash algorithm is sufficient for accurate estimates if the hashing
is sufficiently independent. To reduce costs further, we investigate recursive
random hashing algorithms and show that they are sufficiently independent in
practice. We compare our running times with exact counts using suffix arrays
and show that, while we use hardly any storage, we are an order of magnitude
faster. The approach further is extended to a one-pass/one-hash computation of
n-gram entropy and iceberg counts. The experiments use a large collection of
English text from the Gutenberg Project as well as synthetic data.


title: Creation and use of Citations in the ADS

abstract:
  With over 20 million records, the ADS citation database is regularly used by
researchers and librarians to measure the scientific impact of individuals,
groups, and institutions. In addition to the traditional sources of citations,
the ADS has recently added references extracted from the arXiv e-prints on a
nightly basis. We review the procedures used to harvest and identify the
reference data used in the creation of citations, the policies and procedures
that we follow to avoid double-counting and to eliminate contributions which
may not be scholarly in nature. Finally, we describe how users and institutions
can easily obtain quantitative citation data from the ADS, both interactively
and via web-based programming tools.
  The ADS is available at http://ads.harvard.edu.


title:
On Shift Sequences for Interleaved Construction of Sequence Sets with
  Low Correlation

abstract:
  Construction of signal sets with low correlation property is of interest to
designers of CDMA systems. One of the preferred ways of constructing such sets
is the interleaved construction which uses two sequences a and b with 2-level
autocorrelation and a shift sequence e. The shift sequence has to satisfy
certain conditions for the resulting signal set to have low correlation
properties. This article shows that the conditions reported in literature are
too strong and gives a version which results in more number of shift sequences.
An open problem on the existence of shift sequences for attaining an
interleaved set with maximum correlation value bounded by v+2 is also taken up
and solved.


title: Cooperative Processes for Scientific Workflows

abstract:
  The work described in this paper is a contribution to the problems of
managing in data-intensive scientific applications. First, we discuss
scientific workflows and motivate there use in scientific applications. Then,
we introduce the concept of cooperative processes and describe their
interactions and uses in a flexible cooperative workflow system called
\textit{Bonita}. Finally, we propose an approach to integrate and synthesize
the data exchanged by the mapping of data-intensive science into Bonita, using
a binary approach, and illustrate the endeavors done to enhance the performance
computations within a dynamic environment.


title: Implementing a Unification Algorithm for Protocol Analysis with XOR

abstract:
  In this paper, we propose a unification algorithm for the theory $E$ which
combines unification algorithms for $E\_{\std}$ and $E\_{\ACUN}$ (ACUN
properties, like XOR) but compared to the more general combination methods uses
specific properties of the equational theories for further optimizations. Our
optimizations drastically reduce the number of non-deterministic choices, in
particular those for variable identification and linear orderings. This is
important for reducing both the runtime of the unification algorithm and the
number of unifiers in the complete set of unifiers. We emphasize that obtaining
a ``small'' set of unifiers is essential for the efficiency of the constraint
solving procedure within which the unification algorithm is used. The method is
implemented in the CL-Atse tool for security protocol analysis.


title: Why did the accident happen? A norm-based reasoning approach

abstract:
  In this paper we describe an architecture of a system that answer the
question : Why did the accident happen? from the textual description of an
accident. We present briefly the different parts of the architecture and then
we describe with more detail the semantic part of the system i.e. the part in
which the norm-based reasoning is performed on the explicit knowlege extracted
from the text.


title: Norm Based Causal Reasoning in Textual Corpus

abstract:
  Truth based entailments are not sufficient for a good comprehension of NL. In
fact, it can not deduce implicit information necessary to understand a text. On
the other hand, norm based entailments are able to reach this goal. This idea
was behind the development of Frames (Minsky 75) and Scripts (Schank 77, Schank
79) in the 70's. But these theories are not formalized enough and their
adaptation to new situations is far from being obvious. In this paper, we
present a reasoning system which uses norms in a causal reasoning process in
order to find the cause of an accident from a text describing it.


title: A Quasigroup Based Cryptographic System

abstract:
  This paper presents a quasigroup encryptor that has very good scrambling
properties. We show that the output of the encryptor maximizes the output
entropy and the encrypted output for constant and random inputs is very
similar. The system architecture of the quasigroup encryptor and the
autocorrelation properties of the output sequences are provided.


title:
Raisonnement stratifi\'{e} \`{a} base de normes pour inf\'{e}rer les
  causes dans un corpus textuel

abstract:
  To understand texts written in natural language (LN), we use our knowledge
about the norms of the domain. Norms allow to infer more implicit information
from the text. This kind of information can, in general, be defeasible, but it
remains useful and acceptable while the text do not contradict it explicitly.
In this paper we describe a non-monotonic reasoning system based on the norms
of the car crash domain. The system infers the cause of an accident from its
textual description. The cause of an accident is seen as the most specific norm
which has been violated. The predicates and the rules of the system are
stratified: organized on layers in order to obtain an efficient reasoning.


title:
NectaRSS, an RSS feed ranking system that implicitly learns user
  preferences

abstract:
  In this paper a new RSS feed ranking method called NectaRSS is introduced.
The system recommends information to a user based on his/her past choices. User
preferences are automatically acquired, avoiding explicit feedback, and ranking
is based on those preferences distilled to a user profile. NectaRSS uses the
well-known vector space model for user profiles and new documents, and compares
them using information-retrieval techniques, but introduces a novel method for
user profile creation and adaptation from users' past choices. The efficiency
of the proposed method has been tested by embedding it into an intelligent
aggregator (RSS feed reader), which has been used by different and
heterogeneous users. Besides, this paper proves that the ranking of newsitems
yielded by NectaRSS improves its quality with user's choices, and its
superiority over other algorithms that use a different information
representation method.


title: XString: XML as a String

abstract:
  Extensible markup language (XML) is a technology that has been much hyped, so
that XML has become an industry buzzword. Behind the hype is a powerful
technology for data representation in a platform independent manner. As a text
document, however, XML suffers from being too bloated, and requires an XML
parser to access and manipulate it. XString is an encoding method for XML, in
essence, a markup language's markup language. XString gives the benefit of
compressing XML, and allows for easy manipulation and processing of XML source
as a very long string.


title:
On the Fading Paper Achievable Region of the Fading MIMO Broadcast
  Channel

abstract:
  We consider transmission over the ergodic fading multi-antenna broadcast
(MIMO-BC) channel with partial channel state information at the transmitter and
full information at the receiver. Over the equivalent {\it non}-fading channel,
capacity has recently been shown to be achievable using transmission schemes
that were designed for the ``dirty paper'' channel. We focus on a similar
``fading paper'' model. The evaluation of the fading paper capacity is
difficult to obtain. We confine ourselves to the {\it linear-assignment}
capacity, which we define, and use convex analysis methods to prove that its
maximizing distribution is Gaussian. We compare our fading-paper transmission
to an application of dirty paper coding that ignores the partial state
information and assumes the channel is fixed at the average fade. We show that
a gain is easily achieved by appropriately exploiting the information. We also
consider a cooperative upper bound on the sum-rate capacity as suggested by
Sato. We present a numeric example that indicates that our scheme is capable of
realizing much of this upper bound.


title: Iterative Decoding of Low-Density Parity Check Codes (A Survey)

abstract:
  Much progress has been made on decoding algorithms for error-correcting codes
in the last decade. In this article, we give an introduction to some
fundamental results on iterative, message-passing algorithms for low-density
parity check codes. For certain important stochastic channels, this line of
work has enabled getting very close to Shannon capacity with algorithms that
are extremely efficient (both in theory and practice).


title: Une exp\'{e}rience de s\'{e}mantique inf\'{e}rentielle

abstract:
  We develop a system which must be able to perform the same inferences that a
human reader of an accident report can do and more particularly to determine
the apparent causes of the accident. We describe the general framework in which
we are situated, linguistic and semantic levels of the analysis and the
inference rules used by the system.


title: Network calculus based FDI approach for switched Ethernet architecture

abstract:
  The Networked Control Systems (NCS) are complex systems which integrate
information provided by several domians such as automatic control, computer
science, communication network. The work presented in this paper concerns fault
detection, isolation and compensation of communication network. The proposed
method is based on the classical approach of Fault Detection and Isolation and
Fault Tolerant Control (FDI/FTC) currently used in diagnosis. The modelling of
the network to be supervised is based on both couloured petri nets and network
calculus theory often used to represent and analyse the network behaviour. The
goal is to implement inside network devices algorithms enabling to detect,
isolate and compensate communication faults in an autonomous way.


title: Low Correlation Sequences over the QAM Constellation

abstract:
  This paper presents the first concerted look at low correlation sequence
families over QAM constellations of size M^2=4^m and their potential
applicability as spreading sequences in a CDMA setting.
  Five constructions are presented, and it is shown how such sequence families
have the ability to transport a larger amount of data as well as enable
variable-rate signalling on the reverse link.
  Canonical family CQ has period N, normalized maximum-correlation parameter
theta_max bounded above by A sqrt(N), where 'A' ranges from 1.8 in the 16-QAM
case to 3.0 for large M. In a CDMA setting, each user is enabled to transfer 2m
bits of data per period of the spreading sequence which can be increased to 3m
bits of data by halving the size of the sequence family. The technique used to
construct CQ is easily extended to produce larger sequence families and an
example is provided.
  Selected family SQ has a lower value of theta_max but permits only (m+1)-bit
data modulation. The interleaved 16-QAM sequence family IQ has theta_max <=
sqrt(2) sqrt(N) and supports 3-bit data modulation.
  The remaining two families are over a quadrature-PAM (Q-PAM) subset of size
2M of the M^2-QAM constellation. Family P has a lower value of theta_max in
comparison with Family SQ, while still permitting (m+1)-bit data modulation.
Interleaved family IP, over the 8-ary Q-PAM constellation, permits 3-bit data
modulation and interestingly, achieves the Welch lower bound on theta_max.


title: Covering selfish machines

abstract:
  We consider the machine covering problem for selfish related machines. For a
constant number of machines, m, we show a monotone polynomial time
approximation scheme (PTAS) with running time that is linear in the number of
jobs. It uses a new technique for reducing the number of jobs while remaining
close to the optimal solution. We also present an FPTAS for the classical
machine covering problem (the previous best result was a PTAS) and use this to
give a monotone FPTAS.
  Additionally, we give a monotone approximation algorithm with approximation
ratio \min(m,(2+\eps)s_1/s_m) where \eps>0 can be chosen arbitrarily small and
s_i is the (real) speed of machine i. Finally we give improved results for two
machines.
  Our paper presents the first results for this problem in the context of
selfish machines.


title: LTL with the Freeze Quantifier and Register Automata

abstract:
  A data word is a sequence of pairs of a letter from a finite alphabet and an
element from an infinite set, where the latter can only be compared for
equality. To reason about data words, linear temporal logic is extended by the
freeze quantifier, which stores the element at the current word position into a
register, for equality comparisons deeper in the formula. By translations from
the logic to alternating automata with registers and then to faulty counter
automata whose counters may erroneously increase at any time, and from faulty
and error-free counter automata to the logic, we obtain a complete complexity
table for logical fragments defined by varying the set of temporal operators
and the number of registers. In particular, the logic with future-time
operators and 1 register is decidable but not primitive recursive over finite
data words. Adding past-time operators or 1 more register, or switching to
infinite data words, cause undecidability.


title: Memory and compiler optimizations for low-power and -energy

abstract:
  Embedded systems become more and more widespread, especially autonomous ones,
and clearly tend to be ubiquitous. In such systems, low-power and low-energy
usage get ever more crucial. Furthermore, these issues also become paramount in
(massively) multi-processors systems, either in one machine or more widely in a
grid. The various problems faced pertain to autonomy, power supply
possibilities, thermal dissipation, or even sheer energy cost. Although it has
since long been studied in harware, energy optimization is more recent in
software. In this paper, we thus aim at raising awareness to low-power and
low-energy issues in the language and compilation community. We thus broadly
but briefly survey techniques and solutions to this energy issue, focusing on a
few specific aspects in the context of compiler optimizations and memory
management.


title: Data in the ADS -- Understanding How to Use it Better

abstract:
  The Smithsonian/NASA ADS Abstract Service contains a wealth of data for
astronomers and librarians alike, yet the vast majority of usage consists of
rudimentary searches. Hints on how to obtain more focused search results by
using more of the various capabilities of the ADS are presented, including
searching by affiliation. We also discuss the classification of articles by
content and by referee status.
  The ADS is funded by NASA Grant NNG06GG68G-16613687.


title: Paper to Screen: Processing Historical Scans in the ADS

abstract:
  The NASA Astrophysics Data System in conjunction with the Wolbach Library at
the Harvard-Smithsonian Center for Astrophysics is working on a project to
microfilm historical observatory publications. The microfilm is then scanned
for inclusion in the ADS. The ADS currently contains over 700,000 scanned pages
of volumes of historical literature. Many of these volumes lack clear
pagination or other bibliographic data that are necessary to take advantage of
the searching capabilities of the ADS. This paper will address some of the
interesting challenges that needed to be resolved during the processing of the
Observatory Reports included in the ADS.


title: Pathways: Augmenting interoperability across scholarly repositories

abstract:
  In the emerging eScience environment, repositories of papers, datasets,
software, etc., should be the foundation of a global and natively-digital
scholarly communications system. The current infrastructure falls far short of
this goal. Cross-repository interoperability must be augmented to support the
many workflows and value-chains involved in scholarly communication. This will
not be achieved through the promotion of single repository architecture or
content representation, but instead requires an interoperability framework to
connect the many heterogeneous systems that will exist.
  We present a simple data model and service architecture that augments
repository interoperability to enable scholarly value-chains to be implemented.
We describe an experiment that demonstrates how the proposed infrastructure can
be deployed to implement the workflow involved in the creation of an overlay
journal over several different repository systems (Fedora, aDORe, DSpace and
arXiv).


title: Pipelined Feed-Forward Cyclic Redundancy Check (CRC) Calculation

abstract:
  This paper discusses a method for pipelining the calculation of CRC's, such
as ITU/CCITT CRC32, into a mostly feed-forward architecture. This method allows
several benefits such as independent scaling of circuit frequency and data
throughput. Additionally it allows calculation over packet tails (packet length
not a multiple of CRC input width). Finally it offers the ability to update a
CRC where a subset of data in the packet has changed.


title: A kernel for time series based on global alignments

abstract:
  We propose in this paper a new family of kernels to handle times series,
notably speech data, within the framework of kernel methods which includes
popular algorithms such as the Support Vector Machine. These kernels elaborate
on the well known Dynamic Time Warping (DTW) family of distances by considering
the same set of elementary operations, namely substitutions and repetitions of
tokens, to map a sequence onto another. Associating to each of these operations
a given score, DTW algorithms use dynamic programming techniques to compute an
optimal sequence of operations with high overall score. In this paper we
consider instead the score spanned by all possible alignments, take a smoothed
version of their maximum and derive a kernel out of this formulation. We prove
that this kernel is positive definite under favorable conditions and show how
it can be tuned effectively for practical applications as we report encouraging
results on a speech recognition task.


title: Postinal Determinacy of Games with Infinitely Many Priorities

abstract:
  We study two-player games of infinite duration that are played on finite or
infinite game graphs. A winning strategy for such a game is positional if it
only depends on the current position, and not on the history of the play. A
game is positionally determined if, from each position, one of the two players
has a positional winning strategy.
  The theory of such games is well studied for winning conditions that are
defined in terms of a mapping that assigns to each position a priority from a
finite set. Specifically, in Muller games the winner of a play is determined by
the set of those priorities that have been seen infinitely often; an important
special case are parity games where the least (or greatest) priority occurring
infinitely often determines the winner. It is well-known that parity games are
positionally determined whereas Muller games are determined via finite-memory
strategies.
  In this paper, we extend this theory to the case of games with infinitely
many priorities. Such games arise in several application areas, for instance in
pushdown games with winning conditions depending on stack contents.
  For parity games there are several generalisations to the case of infinitely
many priorities. While max-parity games over omega or min-parity games over
larger ordinals than omega require strategies with infinite memory, we can
prove that min-parity games with priorities in omega are positionally
determined. Indeed, it turns out that the min-parity condition over omega is
the only infinitary Muller condition that guarantees positional determinacy on
all game graphs.


title: Positional Determinacy of Games with Infinitely Many Priorities


title: Optimization of Memory Usage in Tardos's Fingerprinting Codes

abstract:
  It is known that Tardos's collusion-secure probabilistic fingerprinting code
(Tardos code; STOC'03) has length of theoretically minimal order with respect
to the number of colluding users. However, Tardos code uses certain continuous
probability distribution in codeword generation, which creates some problems
for practical use, in particular, it requires large extra memory. A solution
proposed so far is to use some finite probability distributions instead. In
this paper, we determine the optimal finite distribution in order to decrease
extra memory amount. By our result, the extra memory is reduced to 1/32 of the
original, or even becomes needless, in some practical setting. Moreover, the
code length is also reduced, e.g. to about 20.6% of Tardos code asymptotically.
Finally, we address some other practical issues such as approximation errors
which are inevitable in any real implementation.


title:
The Capacity Region of a Class of Discrete Degraded Interference
  Channels

abstract:
  We provide a single-letter characterization for the capacity region of a
class of discrete degraded interference channels (DDICs). The class of DDICs
considered includes the discrete additive degraded interference channel (DADIC)
studied by Benzel. We show that for the class of DDICs studied, encoder
cooperation does not increase the capacity region, and therefore, the capacity
region of the class of DDICs is the same as the capacity region of the
corresponding degraded broadcast channel.


title: Church's thesis is questioned by new calculation paradigm

abstract:
  Church's thesis claims that all effecticely calculable functions are
recursive. A shortcoming of the various definitions of recursive functions lies
in the fact that it is not a matter of a syntactical check to find out if an
entity gives rise to a function. Eight new ideas for a precise setup of
arithmetical logic and its metalanguage give the proper environment for the
construction of a special computer, the ARBACUS computer. Computers do not come
to a necessary halt; it is requested that calculators are constructed on the
basis of computers in a way that they always come to a halt, then all
calculations are effective. The ARBATOR is defined as a calculator with
two-layer-computation. It allows for the calculation of all primitive recursive
functions, but multi-level-arbation also allows for the calculation of other
arbative functions that are not primitive recursive. The new paradigm of
calculation does not have the above mentioned shortcoming. The defenders of
Church's thesis are challenged to show that exotic arbative functions are
recursive and to put forward a recursive function that is not arbative. A
construction with three-tier-multi-level-arbation that includes a
diagonalisation leads to the extravagant yet calculable Snark-function that is
not arbative. As long as it is not shown that all exotic arbative functions and
particularily the Snark-function are arithmetically representable Goedel's
first incompleteness sentence is in limbo.


title:
The Application of Fuzzy Logic to the Construction of the Ranking
  Function of Information Retrieval Systems

abstract:
  The quality of the ranking function is an important factor that determines
the quality of the Information Retrieval system. Each document is assigned a
score by the ranking function; the score indicates the likelihood of relevance
of the document given a query. In the vector space model, the ranking function
is defined by a mathematic expression. We propose a fuzzy logic (FL) approach
to defining the ranking function. FL provides a convenient way of converting
knowledge expressed in a natural language into fuzzy logic rules. The resulting
ranking function could be easily viewed, extended, and verified: * if (tf is
high) and (idf is high) > (relevance is high); * if (overlap is high) >
(relevance is high). By using above FL rules, we are able to achieve
performance approximately equal to the state of the art search engine Apache
Lucene (deltaP10 +0.92%; deltaMAP -0.1%). The fuzzy logic approach allows
combining the logic-based model with the vector model. The resulting model
possesses simplicity and formalism of the logic based model, and the
flexibility and performance of the vector model.


title: Crosstalk-free Conjugate Networks for Optical Multicast Switching

abstract:
  High-speed photonic switching networks can switch optical signals at the rate
of several terabits per second. However, they suffer from an intrinsic
crosstalk problem when two optical signals cross at the same switch element. To
avoid crosstalk, active connections must be node-disjoint in the switching
network. In this paper, we propose a sequence of decomposition and merge
operations, called conjugate transformation, performed on each switch element
to tackle this problem. The network resulting from this transformation is
called conjugate network. By using the numbering-schemes of networks, we prove
that if the route assignments in the original network are link-disjoint, their
corresponding ones in the conjugate network would be node-disjoint. Thus,
traditional nonblocking switching networks can be transformed into
crosstalk-free optical switches in a routine manner. Furthermore, we show that
crosstalk-free multicast switches can also be obtained from existing
nonblocking multicast switches via the same conjugate transformation.


title:
A Computational Model of Spatial Memory Anticipation during Visual
  Search

abstract:
  Some visual search tasks require to memorize the location of stimuli that
have been previously scanned. Considerations about the eye movements raise the
question of how we are able to maintain a coherent memory, despite the frequent
drastically changes in the perception. In this article, we present a
computational model that is able to anticipate the consequences of the eye
movements on the visual perception in order to update a spatial memory


title: A Polynomial Time Algorithm for The Traveling Salesman Problem

abstract:
  The ATSP polytope can be expressed by asymmetric polynomial size linear
program.


title:
Farthest-Point Heuristic based Initialization Methods for K-Modes
  Clustering

abstract:
  The k-modes algorithm has become a popular technique in solving categorical
data clustering problems in different application domains. However, the
algorithm requires random selection of initial points for the clusters.
Different initial points often lead to considerable distinct clustering
results. In this paper we present an experimental study on applying a
farthest-point heuristic based initialization method to k-modes clustering to
improve its performance. Experiments show that new initialization method leads
to better clustering accuracy than random selection initialization method for
k-modes clustering.


title:
M\'{e}canismes de Transmission Multipoint pour R\'{e}seaux Locaux Sans
  Fil IEEE 802.11

abstract:
  Le standard IEEE 802.11 est inefficace pour la transmission multim\'{e}dia en
multipoint. En particulier, les paquets multipoints sont envoy\'{e}s en boucle
ouverte de la m\^{e}me mani\`{e}re que les paquets broadcast. L'absence
d'acquittements rend impossible la mise en oeuvre de m\'{e}canismes de
contr\^{o}le de congestion, de m\'{e}canisme de fiabilisation de la
transmission ainsi que d'algorithmes d'adaptation du d\'{e}bit de transmission
physique. Dans ce rapport, nous proposons de nouveaux m\'{e}canismes de
ransmission multipoint qui se basent sur une approche leader pour renvoyer des
acquittements. Nous nous interessons \`{a} des solutions pratiques qui sont
suceptibles d'\^{e}tre implant\'{e}s dans les cartes r\'{e}seaux sans fil
actuelles et futures et qui restent compatibles avec les stations IEEE 802.11
standards. Nous proposons deux m\'{e}canismes pour adapter le d\'{e}bit de
transmission physique des flots multipoints: un m\'{e}canisme simplifi\'{e}
appel\'{e} LB-ARF et un m\'{e}canisme plus robuste appel\'{e} RRAM. Nos
simulations montrent que pour des environnements statiques, un m\'{e}canisme
aussi simple que LB-ARF suffit pour obtenir de bonnes performances. Le
m\'{e}canisme RRAM est quant \`{a} lui aussi efficace dans des environnements
statiques que lorsque les stations sont mobiles.


title: Spectra of large block matrices

abstract:
  In a frequency selective slow-fading channel in a MIMO system, the channel
matrix is of the form of a block matrix. This paper proposes a method to
calculate the limit of the eigenvalue distribution of block matrices if the
size of the blocks tends to infinity. While it considers random matrices, it
takes an operator-valued free probability approach to achieve this goal. Using
this method, one derives a system of equations, which can be solved numerically
to compute the desired eigenvalue distribution. The paper initially tackles the
problem for square block matrices, then extends the solution to rectangular
block matrices. Finally, it deals with Wishart type block matrices. For two
special cases, the results of our approach are compared with results from
simulations. The first scenario investigates the limit eigenvalue distribution
of block Toeplitz matrices. The second scenario deals with the distribution of
Wishart type block matrices for a frequency selective slow-fading channel in a
MIMO system for two different cases of $n_R=n_T$ and $n_R=2n_T$. Using this
method, one may calculate the capacity and the Signal-to-Interference-and-Noise
Ratio in large MIMO systems.


title:
Streaming Maximum-Minimum Filter Using No More than Three Comparisons
  per Element

abstract:
  The running maximum-minimum (max-min) filter computes the maxima and minima
over running windows of size w. This filter has numerous applications in signal
processing and time series analysis. We present an easy-to-implement online
algorithm requiring no more than 3 comparisons per element, in the worst case.
Comparatively, no algorithm is known to compute the running maximum (or
minimum) filter in 1.5 comparisons per element, in the worst case. Our
algorithm has reduced latency and memory usage.


title: Capacity of the Trapdoor Channel with Feedback

abstract:
  We establish that the feedback capacity of the trapdoor channel is the
logarithm of the golden ratio and provide a simple communication scheme that
achieves capacity. As part of the analysis, we formulate a class of dynamic
programs that characterize capacities of unifilar finite-state channels. The
trapdoor channel is an instance that admits a simple analytic solution.


title:
MV3: A new word based stream cipher using rapid mixing and revolving
  buffers

abstract:
  MV3 is a new word based stream cipher for encrypting long streams of data. A
direct adaptation of a byte based cipher such as RC4 into a 32- or 64-bit word
version will obviously need vast amounts of memory. This scaling issue
necessitates a look for new components and principles, as well as mathematical
analysis to justify their use. Our approach, like RC4's, is based on rapidly
mixing random walks on directed graphs (that is, walks which reach a random
state quickly, from any starting point). We begin with some well understood
walks, and then introduce nonlinearity in their steps in order to improve
security and show long term statistical correlations are negligible. To
minimize the short term correlations, as well as to deter attacks using
equations involving successive outputs, we provide a method for sequencing the
outputs derived from the walk using three revolving buffers. The cipher is fast
-- it runs at a speed of less than 5 cycles per byte on a Pentium IV processor.
A word based cipher needs to output more bits per step, which exposes more
correlations for attacks. Moreover we seek simplicity of construction and
transparent analysis. To meet these requirements, we use a larger state and
claim security corresponding to only a fraction of it. Our design is for an
adequately secure word-based cipher; our very preliminary estimate puts the
security close to exhaustive search for keys of size < 256 bits.


title: Restricted Complexity, General Complexity

abstract:
  Why has the problematic of complexity appeared so late? And why would it be
justified?


title:
The Mathematical Parallels Between Packet Switching and Information
  Transmission

abstract:
  All communication networks comprise of transmission systems and switching
systems, even though they are usually treated as two separate issues.
Communication channels are generally disturbed by noise from various sources.
In circuit switched networks, reliable communication requires the
error-tolerant transmission of bits over noisy channels. In packet switched
networks, however, not only can bits be corrupted with noise, but resources
along connection paths are also subject to contention. Thus, quality of service
(QoS) is determined by buffer delays and packet losses. The theme of this paper
is to show that transmission noise and packet contention actually have similar
characteristics and can be tamed by comparable means to achieve reliable
communication, and a number of analogies between switching and transmission are
identified. The sampling theorem of bandlimited signals provides the
cornerstone of digital communication and signal processing. Recently, the
Birkhoff-von Neumann decomposition of traffic matrices has been widely applied
to packet switches. With respect to the complexity reduction of packet
switching, we show that the decomposition of a doubly stochastic traffic matrix
plays a similar role to that of the sampling theorem in digital transmission.
We conclude that packet switching systems are governed by mathematical laws
that are similar to those of digital transmission systems as envisioned by
Shannon in his seminal 1948 paper, A Mathematical Theory of Communication.


title:
Strong bi-homogeneous B\'{e}zout theorem and its use in effective real
  algebraic geometry

abstract:
  Let f1, ..., fs be a polynomial family in Q[X1,..., Xn] (with s less than n)
of degree bounded by D. Suppose that f1, ..., fs generates a radical ideal, and
defines a smooth algebraic variety V. Consider a projection P. We prove that
the degree of the critical locus of P restricted to V is bounded by
D^s(D-1)^(n-s) times binomial of n and n-s. This result is obtained in two
steps. First the critical points of P restricted to V are characterized as
projections of the solutions of Lagrange's system for which a bi-homogeneous
structure is exhibited. Secondly we prove a bi-homogeneous B\'ezout Theorem,
which bounds the sum of the degrees of the equidimensional components of the
radical of an ideal generated by a bi-homogeneous polynomial family. This
result is improved when f1,..., fs is a regular sequence. Moreover, we use
Lagrange's system to design an algorithm computing at least one point in each
connected component of a smooth real algebraic set. This algorithm generalizes,
to the non equidimensional case, the one of Safey El Din and Schost. The
evaluation of the output size of this algorithm gives new upper bounds on the
first Betti number of a smooth real algebraic set. Finally, we estimate its
arithmetic complexity and prove that in the worst cases it is polynomial in n,
s, D^s(D-1)^(n-s) and the binomial of n and n-s, and the complexity of
evaluation of f1,..., fs.


title:
Finite-Dimensional Bounds on Zm and Binary LDPC Codes with Belief
  Propagation Decoders

abstract:
  This paper focuses on finite-dimensional upper and lower bounds on decodable
thresholds of Zm and binary low-density parity-check (LDPC) codes, assuming
belief propagation decoding on memoryless channels. A concrete framework is
presented, admitting systematic searches for new bounds. Two noise measures are
considered: the Bhattacharyya noise parameter and the soft bit value for a
maximum a posteriori probability (MAP) decoder on the uncoded channel. For Zm
LDPC codes, an iterative m-dimensional bound is derived for
m-ary-input/symmetric-output channels, which gives a sufficient stability
condition for Zm LDPC codes and is complemented by a matched necessary
stability condition introduced herein. Applications to coded modulation and to
codes with non-equiprobable distributed codewords are also discussed.
  For binary codes, two new lower bounds are provided for symmetric channels,
including a two-dimensional iterative bound and a one-dimensional non-iterative
bound, the latter of which is the best known bound that is tight for binary
symmetric channels (BSCs), and is a strict improvement over the bound derived
by the channel degradation argument. By adopting the reverse channel
perspective, upper and lower bounds on the decodable Bhattacharyya noise
parameter are derived for non-symmetric channels, which coincides with the
existing bound for symmetric channels.


title: Towards a Bayesian framework for option pricing

abstract:
  In this paper, we describe a general method for constructing the posterior
distribution of an option price. Our framework takes as inputs the prior
distributions of the parameters of the stochastic process followed by the
underlying, as well as the likelihood function implied by the observed price
history for the underlying. Our work extends that of Karolyi (1993) and
Darsinos and Satchell (2001), but with the crucial difference that the
likelihood function we use for inference is that which is directly implied by
the underlying, rather than imposed in an ad hoc manner via the introduction of
a function representing "measurement error." As such, an important problem
still relevant for our method is that of model risk, and we address this issue
by describing how to perform a Bayesian averaging of parameter inferences based
on the different models considered using our framework.


title: Enumeration Problems Related to Ground Horn Theories

abstract:
  We investigate the enumeration of varieties of boolean theories related to
Horn clauses. We describe a number of combinatorial equivalences among
different characterizations and calculate the number of different theories in
$n$ variables for slightly different characterizations. The method of counting
is via counting models using a satisfiability checker.


title: Extending the Calculus of Constructions with Tarski's fix-point theorem

abstract:
  We propose to use Tarski's least fixpoint theorem as a basis to define
recursive functions in the calculus of inductive constructions. This widens the
class of functions that can be modeled in type-theory based theorem proving
tool to potentially non-terminating functions. This is only possible if we
extend the logical framework by adding the axioms that correspond to classical
logic. We claim that the extended framework makes it possible to reason about
terminating and non-terminating computations and we show that common facilities
of the calculus of inductive construction, like program extraction can be
extended to also handle the new functions.


title: Constructing experimental indicators for Open Access documents

abstract:
  The ongoing paradigm change in the scholarly publication system ('science is
turning to e-science') makes it necessary to construct alternative evaluation
criteria/metrics which appropriately take into account the unique
characteristics of electronic publications and other research output in digital
formats. Today, major parts of scholarly Open Access (OA) publications and the
self-archiving area are not well covered in the traditional citation and
indexing databases. The growing share and importance of freely accessible
research output demands new approaches/metrics for measuring and for evaluating
of these new types of scientific publications. In this paper we propose a
simple quantitative method which establishes indicators by measuring the
access/download pattern of OA documents and other web entities of a single web
server. The experimental indicators (search engine, backlink and direct access
indicator) are constructed based on standard local web usage data. This new
type of web-based indicator is developed to model the specific demand for
better study/evaluation of the accessibility, visibility and interlinking of
open accessible documents. We conclude that e-science will need new stable
e-indicators.


title: Properties of codes in rank metric

abstract:
  We study properties of rank metric and codes in rank metric over finite
fields. We show that in rank metric perfect codes do not exist. We derive an
existence bound that is the equivalent of the Gilbert--Varshamov bound in
Hamming metric. We study the asymptotic behavior of the minimum rank distance
of codes satisfying GV. We derive the probability distribution of minimum rank
distance for random and random $\F{q}$-linear codes. We give an asymptotic
equivalent of their average minimum rank distance and show that random
$\F{q}$-linear codes are on GV bound for rank metric.
  We show that the covering density of optimum codes whose codewords can be
seen as square matrices is lower bounded by a function depending only on the
error-correcting capability of the codes. We show that there are quasi-perfect
codes in rank metric over fields of characteristic 2.


title: Context-sensitive access to e-document corpus

abstract:
  The methodology of context-sensitive access to e-documents considers context
as a problem model based on the knowledge extracted from the application
domain, and presented in the form of application ontology. Efficient access to
an information in the text form is needed. Wiki resources as a modern text
format provides huge number of text in a semi formalized structure. At the
first stage of the methodology, documents are indexed against the ontology
representing macro-situation. The indexing method uses a topic tree as a middle
layer between documents and the application ontology. At the second stage
documents relevant to the current situation (the abstract and operational
contexts) are identified and sorted by degree of relevance. Abstract context is
a problem-oriented ontology-based model. Operational context is an
instantiation of the abstract context with data provided by the information
sources. The following parts of the methodology are described: (i) metrics for
measuring similarity of e-documents to ontology, (ii) a document index storing
results of indexing of e-documents against the ontology; (iii) a method for
identification of relevant e-documents based on semantic similarity measures.
Wikipedia (wiki resource) is used as a corpus of e-documents for approach
evaluation in a case study. Text categorization, the presence of metadata, and
an existence of a lot of articles related to different topics characterize the
corpus.


title: Camera motion estimation through planar deformation determination

abstract:
  In this paper, we propose a global method for estimating the motion of a
camera which films a static scene. Our approach is direct, fast and robust, and
deals with adjacent frames of a sequence. It is based on a quadratic
approximation of the deformation between two images, in the case of a scene
with constant depth in the camera coordinate system. This condition is very
restrictive but we show that provided translation and depth inverse variations
are small enough, the error on optical flow involved by the approximation of
depths by a constant is small. In this context, we propose a new model of
camera motion, that allows to separate the image deformation in a similarity
and a ``purely'' projective application, due to change of optical axis
direction. This model leads to a quadratic approximation of image deformation
that we estimate with an M-estimator; we can immediatly deduce camera motion
parameters.


title: Comparing Typical Opening Move Choices Made by Humans and Chess Engines

abstract:
  The opening book is an important component of a chess engine, and thus
computer chess programmers have been developing automated methods to improve
the quality of their books. For chess, which has a very rich opening theory,
large databases of high-quality games can be used as the basis of an opening
book, from which statistics relating to move choices from given positions can
be collected. In order to find out whether the opening books used by modern
chess engines in machine versus machine competitions are ``comparable'' to
those used by chess players in human versus human competitions, we carried out
analysis on 26 test positions using statistics from two opening books one
compiled from humans' games and the other from machines' games. Our analysis
using several nonparametric measures, shows that, overall, there is a strong
association between humans' and machines' choices of opening moves when using a
book to guide their choices.


title: The Delay-Limited Capacity Region of OFDM Broadcast Channels

abstract:
  In this work, the delay limited capacity (DLC) of orthogonal frequency
division multiplexing (OFDM) systems is investigated. The analysis is organized
into two parts. In the first part, the impact of system parameters on the OFDM
DLC is analyzed in a general setting. The main results are that under weak
assumptions the maximum achievable single user DLC is almost independent of the
distribution of the path attenuations in the low signal-to-noise (SNR) region
but depends strongly on the delay spread. In the high SNR region the roles are
exchanged. Here, the impact of delay spread is negligible while the impact of
the distribution becomes dominant. The relevant asymptotic quantities are
derived without employing simplifying assumptions on the OFDM correlation
structure. Moreover, for both cases it is shown that the DLC is maximized if
the total channel energy is uniformly spread, i.e. the power delay profile is
uniform. It is worth pointing out that since universal bounds are obtained the
results can also be used for other classes of parallel channels with block
fading characteristic. The second part extends the setting to the broadcast
channel and studies the corresponding OFDM DLC BC region. An algorithm for
computing the OFDM BC DLC region is presented. To derive simple but smart
resource allocation strategies, the principle of rate water-filling employing
order statistics is introduced. This yields analytical lower bounds on the OFDM
DLC region based on orthogonal frequency division multiple access (OFDMA) and
ordinal channel state information (CSI). Finally, the schemes are compared to
an algorithm using full CSI.


title:
A type-based termination criterion for dependently-typed higher-order
  rewrite systems

abstract:
  Several authors devised type-based termination criteria for ML-like languages
allowing non-structural recursive calls. We extend these works to general
rewriting and dependent types, hence providing a powerful termination criterion
for the combination of rewriting and beta-reduction in the Calculus of
Constructions.


title: The Calculus of Algebraic Constructions

abstract:
  This paper is concerned with the foundations of the Calculus of Algebraic
Constructions (CAC), an extension of the Calculus of Constructions by inductive
data types. CAC generalizes inductive types equipped with higher-order
primitive recursion, by providing definitions of functions by pattern-matching
which capture recursor definitions for arbitrary non-dependent and
non-polymorphic inductive types satisfying a strictly positivity condition. CAC
also generalizes the first-order framework of abstract data types by providing
dependent types and higher-order rewrite rules.


title: Termination and Confluence of Higher-Order Rewrite Systems

abstract:
  In the last twenty years, several approaches to higher-order rewriting have
been proposed, among which Klop's Combinatory Rewrite Systems (CRSs), Nipkow's
Higher-order Rewrite Systems (HRSs) and Jouannaud and Okada's higher-order
algebraic specification languages, of which only the last one considers typed
terms. The later approach has been extended by Jouannaud, Okada and the present
author into Inductive Data Type Systems (IDTSs). In this paper, we extend IDTSs
with the CRS higher-order pattern-matching mechanism, resulting in simply-typed
CRSs. Then, we show how the termination criterion developed for IDTSs with
first-order pattern-matching, called the General Schema, can be extended so as
to prove the strong normalization of IDTSs with higher-order pattern-matching.
Next, we compare the unified approach with HRSs. We first prove that the
extended General Schema can also be applied to HRSs. Second, we show how
Nipkow's higher-order critical pair analysis technique for proving local
confluence can be applied to IDTSs.


title: Definitions by Rewriting in the Calculus of Constructions

abstract:
  The main novelty of this paper is to consider an extension of the Calculus of
Constructions where predicates can be defined with a general form of rewrite
rules. We prove the strong normalization of the reduction relation generated by
the beta-rule and the user-defined rules under some general syntactic
conditions including confluence. As examples, we show that two important
systems satisfy these conditions: a sub-system of the Calculus of Inductive
Constructions which is the basis of the proof assistant Coq, and the Natural
Deduction Modulo a large class of equational theories.


title: Inductive-data-type Systems

abstract:
  In a previous work ("Abstract Data Type Systems", TCS 173(2), 1997), the last
two authors presented a combined language made of a (strongly normalizing)
algebraic rewrite system and a typed lambda-calculus enriched by
pattern-matching definitions following a certain format, called the "General
Schema", which generalizes the usual recursor definitions for natural numbers
and similar "basic inductive types". This combined language was shown to be
strongly normalizing. The purpose of this paper is to reformulate and extend
the General Schema in order to make it easily extensible, to capture a more
general class of inductive types, called "strictly positive", and to ease the
strong normalization proof of the resulting system. This result provides a
computation model for the combination of an algebraic specification language
based on abstract data types and of a strongly typed functional language with
strictly positive inductive types.


title:
Language, logic and ontology: uncovering the structure of commonsense
  knowledge

abstract:
  The purpose of this paper is twofold: (i) we argue that the structure of
commonsense knowledge must be discovered, rather than invented; and (ii) we
argue that natural language, which is the best known theory of our (shared)
commonsense knowledge, should itself be used as a guide to discovering the
structure of commonsense knowledge. In addition to suggesting a systematic
method to the discovery of the structure of commonsense knowledge, the method
we propose seems to also provide an explanation for a number of phenomena in
natural language, such as metaphor, intensionality, and the semantics of
nominal compounds. Admittedly, our ultimate goal is quite ambitious, and it is
no less than the systematic 'discovery' of a well-typed ontology of commonsense
knowledge, and the subsequent formulation of the long-awaited goal of a meaning
algebra.


title: Type theory and rewriting

abstract:
  We study the properties, in particular termination, of dependent types
systems for lambda calculus and rewriting.


title:
An Isabelle formalization of protocol-independent secrecy with an
  application to e-commerce

abstract:
  A protocol-independent secrecy theorem is established and applied to several
non-trivial protocols. In particular, it is applied to protocols proposed for
protecting the computation results of free-roaming mobile agents doing
comparison shopping. All the results presented here have been formally proved
in Isabelle by building on Larry Paulson's inductive approach. This therefore
provides a library of general theorems that can be applied to other protocols.


title: Inductive types in the Calculus of Algebraic Constructions

abstract:
  In a previous work, we proved that almost all of the Calculus of Inductive
Constructions (CIC), which is the basis of the proof assistant Coq, can be seen
as a Calculus of Algebraic Constructions (CAC), an extension of the Calculus of
Constructions with functions and predicates defined by higher-order rewrite
rules. In this paper, we not only prove that CIC as a whole can be seen as a
CAC, but also that it can be extended with non-free constructors,
pattern-matching on defined symbols, non-strictly positive types and
inductive-recursive types.


title: Rewriting modulo in Deduction modulo

abstract:
  We study the termination of rewriting modulo a set of equations in the
Calculus of Algebraic Constructions, an extension of the Calculus of
Constructions with functions and predicates defined by higher-order rewrite
rules. In a previous work, we defined general syntactic conditions based on the
notion of computable closure for ensuring the termination of the combination of
rewriting and beta-reduction. Here, we show that this result is preserved when
considering rewriting modulo a set of equations if the equivalence classes
generated by these equations are finite, the equations are linear and satisfy
general syntactic conditions also based on the notion of computable closure.
This includes equations like associativity and commutativity, and provides an
original treatment of termination modulo equations.


title: Definitions by rewriting in the Calculus of Constructions

abstract:
  This paper presents general syntactic conditions ensuring the strong
normalization and the logical consistency of the Calculus of Algebraic
Constructions, an extension of the Calculus of Constructions with functions and
predicates defined by higher-order rewrite rules. On the one hand, the Calculus
of Constructions is a powerful type system in which one can formalize the
propositions and natural deduction proofs of higher-order logic. On the other
hand, rewriting is a simple and powerful computation paradigm. The combination
of both allows, among other things, to develop formal proofs with a reduced
size and more automation compared with more traditional proof assistants. The
main novelty is to consider a general form of rewriting at the predicate-level
which generalizes the strong elimination of the Calculus of Inductive
Constructions.


abstract:
  In a previous work, we proved that an important part of the Calculus of
Inductive Constructions (CIC), the basis of the Coq proof assistant, can be
seen as a Calculus of Algebraic Constructions (CAC), an extension of the
Calculus of Constructions with functions and predicates defined by higher-order
rewrite rules. In this paper, we prove that almost all CIC can be seen as a
CAC, and that it can be further extended with non-strictly positive types and
inductive-recursive types together with non-free constructors and
pattern-matching on defined symbols.


title:
Collaborative Decoding of Interleaved Reed-Solomon Codes and
  Concatenated Code Designs

abstract:
  Interleaved Reed-Solomon codes are applied in numerous data processing, data
transmission, and data storage systems. They are generated by interleaving
several codewords of ordinary Reed-Solomon codes. Usually, these codewords are
decoded independently by classical algebraic decoding methods. However, by
collaborative algebraic decoding approaches, such interleaved schemes allow the
correction of error patterns beyond half the minimum distance, provided that
the errors in the received signal occur in bursts. In this work, collaborative
decoding of interleaved Reed-Solomon codes by multi-sequence shift-register
synthesis is considered and analyzed. Based on the framework of interleaved
Reed-Solomon codes, concatenated code designs are investigated, which are
obtained by interleaving several Reed-Solomon codes, and concatenating them
with an inner block code.


title: On Geometric Algebra representation of Binary Spatter Codes

abstract:
  Kanerva's Binary Spatter Codes are reformulated in terms of geometric
algebra. The key ingredient of the construction is the representation of XOR
binding in terms of geometric product.


title:
Peano Count Trees (P-Trees) and Rule Association Mining for Gene
  Expression Profiling of Microarray Data

abstract:
  The greatest challenge in maximizing the use of gene expression data is to
develop new computational tools capable of interconnecting and interpreting the
results from different organisms and experimental settings. We propose an
integrative and comprehensive approach including a super-chip containing data
from microarray experiments collected on different species subjected to hypoxic
and anoxic stress. A data mining technology called Peano count tree (P-trees)
is used to represent genomic data in multidimensions. Each microarray spot is
presented as a pixel with its corresponding red/green intensity feature bands.
Each bad is stored separately in a reorganized 8-separate (bSQ) file format.
Each bSQ is converted to a quadrant base tree structure (P-tree) from which a
superchip is represented as expression P-trees (EP-trees) and repression
P-trees (RP-trees). The use of association rule mining is proposed to derived
to meanigingfully organize signal transduction pathways taking in consideration
evolutionary considerations. We argue that the genetic constitution of an
organism (K) can be represented by the total number of genes belonging to two
groups. The group X constitutes genes (X1,Xn) and they can be represented as 1
or 0 depending on whether the gene was expressed or not. The second group of Y
genes (Y1,Yn) is expressed at different levels. These genes have a very high
repression, high expression, very repressed or highly repressed. However, many
genes of the group Y are specie specific and modulated by the products and
combinations of genes of the group X. In this paper, we introduce the dSQ and
P-tree technology; the biological implications of association rule mining using
X and Y gene groups and some advances in the integration of this information
using the BRAIN architecture.


title:
MIMO Broadcast Channels with Block Diagonalization and Finite Rate
  Feedback

abstract:
  Block diagonalization is a linear precoding technique for the multiple
antenna broadcast (downlink) channel that involves transmission of multiple
data streams to each receiver such that no multi-user interference is
experienced at any of the receivers. This low-complexity scheme operates only a
few dB away from capacity but does require very accurate channel knowledge at
the transmitter, which can be very difficult to obtain in fading scenarios. We
consider a limited feedback system where each receiver knows its channel
perfectly, but the transmitter is only provided with a finite number of channel
feedback bits from each receiver. Using a random vector quantization argument,
we quantify the throughput loss due to imperfect channel knowledge as a
function of the feedback level. The quality of channel knowledge must improve
proportional to the SNR in order to prevent interference-limitations, and we
show that scaling the number of feedback bits linearly with the system SNR is
sufficient to maintain a bounded rate loss. Finally, we investigate a simple
scalar quantization scheme that is seen to achieve the same scaling behavior as
vector quantization.


title: Rapid Prototyping over IEEE 802.11

abstract:
  This paper introduces Prawn, a tool for prototyping communication protocols
over IEEE 802.11 networks. Prawn allows researchers to conduct both functional
assessment and performance evaluation as an inherent part of the protocol
design process. Since Prawn runs on real IEEE 802.11 nodes, prototypes can be
evaluated and adjusted under realistic conditions. Once the prototype has been
extensively tested and thoroughly validated, and its functional design tuned
accordingly, it is then ready for implementation. Prawn facilitates prototype
development by providing: (i) a set of building blocks that implement common
functions needed by a wide range of wireless protocols (e.g., neighbor
discovery, link quality assessment, message transmission and reception), and
(ii) an API that allows protocol designers to access Prawn primitives. We show
through a number of case studies how Prawn supports prototyping as part of
protocol design and, as a result of enabling deployment and testing under
real-world scenarios, how Prawn provides useful feedback on protocol operation
and performance.


title: An Enhanced Covering Lemma for Multiterminal Source Coding

abstract:
  An enhanced covering lemma for a Markov chain is proved in this paper, and
then the distributed source coding problem of correlated general sources with
one average distortion criterion under fixed-length coding is investigated.
Based on the enhanced lemma, a sufficient and necessary condition for
determining the achievability of rate-distortion triples is given.


title: Computable Closed Euclidean Subsets with and without Computable Points

abstract:
  The empty set of course contains no computable point. On the other hand,
surprising results due to Zaslavskii, Tseitin, Kreisel, and Lacombe assert the
existence of NON-empty co-r.e. closed sets devoid of computable points: sets
which are `large' in the sense of positive Lebesgue measure. We observe that a
certain size is in fact necessary: every non-empty co-r.e. closed real set
without computable points has continuum cardinality.
  This leads us to investigate for various classes of computable real subsets
whether they necessarily contain a (not necessarily effectively findable)
computable point.


title:
Semantics of Separation-Logic Typing and Higher-order Frame Rules
  for<br> Algol-like Languages

abstract:
  We show how to give a coherent semantics to programs that are well-specified
in a version of separation logic for a language with higher types: idealized
algol extended with heaps (but with immutable stack variables). In particular,
we provide simple sound rules for deriving higher-order frame rules, allowing
for local reasoning.


title: Theoretical analysis of network cranback protocols performance

abstract:
  Suggested the decision of the network cranback protocols performance
analyzing problem from Eyal Felstine, Reuven Cohen and Ofer Hadar, " Crankback
Prediction in Hierarchical ATM networks", Journal of Network and Systems
Management, Vol. 10, No. 3, September 2002. It show that the false alarm
probability and probability of successful way crossing can be calculated. The
main optimization equations are developed for cranback protocol parameters by
using analytical expressions for statistical protocol characteristics.


title: Estimation of the traffic in the binary channel for data networks

abstract:
  It is impossible to provide an effective utilization of communication
networks without the analysis of the quantitative characteristics of the
traffic in real time. The constant supervision of all channels of the data
practically is impracticable because requires transfer of the significant
additional information on a network and large resources expenses for devices of
the control. Thus, the task on traffic estimation with small expenses in real
time is the urgent.


title:
Share and Disperse: How to Resist Against Aggregator Compromises in
  Sensor Networks

abstract:
  A common approach to overcome the limited nature of sensor networks is to
aggregate data at intermediate nodes. A challenging issue in this context is to
guarantee end-to-end security mainly because sensor networks are extremely
vulnerable to node compromises. In order to secure data aggregation, in this
paper we propose three schemes that rely on multipath routing. The first one
guarantees data confidentiality through secret sharing, while the second and
third ones provide data availability through information dispersal. Based on
qualitative analysis and implementation, we show that, by applying these
schemes, a sensor network can achieve data confidentiality, authenticity, and
protection against denial of service attacks even in the presence of multiple
compromised nodes.


title: Symbolic Simulation-Checking of Dense-Time Systems

abstract:
  Intuitively, an (implementation) automata is simulated by a (specification)
automata if every externally observable transition by the implementation
automata can also be made by the specification automata. In this work, we
present a symbolic algorithm for the simulation-checking of timed automatas. We
first present a simulation-checking procedure that operates on state spaces,
representable with convex polyhedra, of timed automatas. We then present
techniques to represent those intermediate result convex polyhedra with zones
and make the procedure an algorithm. We then discuss how to handle Zeno states
in the implementation automata. Finally, we have endeavored to realize the
algorithm and report the performance of our algorithm in the experiment.


title: The central nature of the Hidden Subgroup problem

abstract:
  We show that several problems that figure prominently in quantum computing,
including Hidden Coset, Hidden Shift, and Orbit Coset, are equivalent or
reducible to Hidden Subgroup for a large variety of groups. We also show that,
over permutation groups, the decision version and search version of Hidden
Subgroup are polynomial-time equivalent. For Hidden Subgroup over dihedral
groups, such an equivalence can be obtained if the order of the group is
smooth. Finally, we give nonadaptive program checkers for Hidden Subgroup and
its decision version.


title:
An Application of the Mobile Transient Internet Architecture to IP
  Mobility and Inter-Operability

abstract:
  We introduce an application of a mobile transient network architecture on top
of the current Internet. This paper is an application extension to a conceptual
mobile network architecture. It attempts to specifically reinforce some of the
powerful notions exposed by the architecture from an application perspective.
Of these notions, we explore the network expansion layer, an overlay of
components and services, that enables a persistent identification network and
other required services. The overlay abstraction introduces several benefits of
which mobility and communication across heterogenous network structures are of
interest to this paper. We present implementations of several components and
protocols including gateways, Agents and the Open Device Access Protocol. Our
present identification network implementation exploits the current
implementation of the Handle System through the use of distributed, global and
persistent identifiers called handles. Handles are used to identify and locate
devices and services abstracting any physical location or network association
from the communicating ends. A communication framework is finally demonstrated
that would allow for mobile devices on the public Internet to have persistent
identifiers and thus be persistently accessible either directly or indirectly.
This application expands IP inter-operability beyond its current boundaries.


title: Vector field visualization with streamlines

abstract:
  We have recently developed an algorithm for vector field visualization with
oriented streamlines, able to depict the flow directions everywhere in a dense
vector field and the sense of the local orientations. The algorithm has useful
applications in the visualization of the director field in nematic liquid
crystals. Here we propose an improvement of the algorithm able to enhance the
visualization of the local magnitude of the field. This new approach of the
algorithm is compared with the same procedure applied to the Line Integral
Convolution (LIC) visualization.


title: Reversible Logic to Cryptographic Hardware: A New Paradigm

abstract:
  Differential Power Analysis (DPA) presents a major challenge to
mathematically-secure cryptographic protocols. Attackers can break the
encryption by measuring the energy consumed in the working digital circuit. To
prevent this type of attack, this paper proposes the use of reversible logic
for designing the ALU of a cryptosystem. Ideally, reversible circuits dissipate
zero energy. Thus, it would be of great significance to apply reversible logic
to designing secure cryptosystems. As far as is known, this is the first
attempt to apply reversible logic to developing secure cryptosystems. In a
prototype of a reversible ALU for a crypto-processor, reversible designs of
adders and Montgomery multipliers are presented. The reversible designs of a
carry propagate adder, four-to-two and five-to-two carry save adders are
presented using a reversible TSG gate. One of the important properties of the
TSG gate is that it can work singly as a reversible full adder. In order to
design the reversible Montgomery multiplier, novel reversible sequential
circuits are also proposed which are integrated with the proposed adders to
design a reversible modulo multiplier. It is intended that this paper will
provide a starting point for developing cryptosystems secure against DPA
attacks.


title:
Combined Integer and Floating Point Multiplication Architecture(CIFM)
  for FPGAs and Its Reversible Logic Implementation

abstract:
  In this paper, the authors propose the idea of a combined integer and
floating point multiplier(CIFM) for FPGAs. The authors propose the replacement
of existing 18x18 dedicated multipliers in FPGAs with dedicated 24x24
multipliers designed with small 4x4 bit multipliers. It is also proposed that
for every dedicated 24x24 bit multiplier block designed with 4x4 bit
multipliers, four redundant 4x4 multiplier should be provided to enforce the
feature of self repairability (to recover from the faults). In the proposed
CIFM reconfigurability at run time is also provided resulting in low power. The
major source of motivation for providing the dedicated 24x24 bit multiplier
stems from the fact that single precision floating point multiplier requires
24x24 bit integer multiplier for mantissa multiplication. A reconfigurable,
self-repairable 24x24 bit multiplier (implemented with 4x4 bit multiply
modules) will ideally suit this purpose, making FPGAs more suitable for integer
as well floating point operations. A dedicated 4x4 bit multiplier is also
proposed in this paper. Moreover, in the recent years, reversible logic has
emerged as a promising technology having its applications in low power CMOS,
quantum computing, nanotechnology, and optical computing. It is not possible to
realize quantum computing without reversible logic. Thus, this paper also paper
provides the reversible logic implementation of the proposed CIFM. The
reversible CIFM designed and proposed here will form the basis of the
completely reversible FPGAs.


title: On the Behavior of Journal Impact Factor Rank-Order Distribution

abstract:
  An empirical law for the rank-order behavior of journal impact factors is
found. Using an extensive data base on impact factors including journals on
Education, Agrosciences, Geosciences, Biosciences and Environ- mental,
Chemical, Computer, Engineering, Material, Mathematical, Medical and Physical
Sciences we have found extremely good fits out- performing other rank-order
models. Some extensions to other areas of knowledge are discussed.


title: Happy endings for flip graphs

abstract:
  We show that the triangulations of a finite point set form a flip graph that
can be embedded isometrically into a hypercube, if and only if the point set
has no empty convex pentagon. Point sets of this type include convex subsets of
lattices, points on two lines, and several other infinite families. As a
consequence, flip distance in such point sets can be computed efficiently.


title: Semantic results for ontic and epistemic change

abstract:
  We give some semantic results for an epistemic logic incorporating dynamic
operators to describe information changing events. Such events include
epistemic changes, where agents become more informed about the non-changing
state of the world, and ontic changes, wherein the world changes. The events
are executed in information states that are modeled as pointed Kripke models.
Our contribution consists of three semantic results. (i) Given two information
states, there is an event transforming one into the other. The linguistic
correspondent to this is that every consistent formula can be made true in
every information state by the execution of an event. (ii) A more technical
result is that: every event corresponds to an event in which the postconditions
formalizing ontic change are assignments to `true' and `false' only (instead of
assignments to arbitrary formulas in the logical language). `Corresponds' means
that execution of either event in a given information state results in
bisimilar information states. (iii) The third, also technical, result is that
every event corresponds to a sequence of events wherein all postconditions are
assignments of a single atom only (instead of simultaneous assignments of more
than one atom).


title: Migrating Multi-page Web Applications to Single-page AJAX Interfaces

abstract:
  Recently, a new web development technique for creating interactive web
applications, dubbed AJAX, has emerged. In this new model, the single-page web
interface is composed of individual components which can be updated/replaced
independently. With the rise of AJAX web applications classical multi-page web
applications are becoming legacy systems. If until a year ago, the concern
revolved around migrating legacy systems to web-based settings, today we have a
new challenge of migrating web applications to single-page AJAX applications.
Gaining an understanding of the navigational model and user interface structure
of the source application is the first step in the migration process. In this
paper, we explore how reverse engineering techniques can help analyze classic
web applications for this purpose. Our approach, using a schema-based
clustering technique, extracts a navigational model of web applications, and
identifies candidate user interface components to be migrated to a single-page
AJAX interface. Additionally, results of a case study, conducted to evaluate
our tool, are presented.


title: Solving planning domains with polytree causal graphs is NP-complete

abstract:
  We show that solving planning domains on binary variables with polytree
causal graph is \NP-complete. This is in contrast to a polynomial-time
algorithm of Domshlak and Brafman that solves these planning domains for
polytree causal graphs of bounded indegree.


title: Partial Evaluation for Program Comprehension

abstract:
  Program comprehension is the most tedious and time consuming task of software
maintenance, an important phase of the software life cycle. This is
particularly true while maintaining scientific application programs that have
been written in Fortran for decades and that are still vital in various domains
even though more modern languages are used to implement their user interfaces.
Very often, programs have evolved as their application domains increase
continually and have become very complex due to extensive modifications. This
generality in programs is implemented by input variables whose value does not
vary in the context of a given application. Thus, it is very interesting for
the maintainer to propagate such information, that is to obtain a simplified
program, which behaves like the initial one when used according to the
restriction. We have adapted partial evaluation for program comprehension. Our
partial evaluator performs mainly two tasks: constant propagation and
statements simplification. It includes an interprocedural alias analysis. As
our aim is program comprehension rather than optimization, there are two main
differences with classical partial evaluation. We do not change the original


title: Reuse of Specification Patterns with the B Method

abstract:
  This paper describes an approach for reusing specification patterns.
Specification patterns are design patterns that are expressed in a formal
specification language. Reusing a specification pattern means instantiating it
or composing it with other specification patterns. Three levels of composition
are defined: juxtaposition, composition with inter-patterns links and
unification. This paper shows through examples how to define specification
patterns in B, how to reuse them directly in B, and also how to reuse the
proofs associated with specification patterns.


title: Characterizing Solution Concepts in Games Using Knowledge-Based Programs

abstract:
  We show how solution concepts in games such as Nash equilibrium, correlated
equilibrium, rationalizability, and sequential equilibrium can be given a
uniform definition in terms of \emph{knowledge-based programs}. Intuitively,
all solution concepts are implementations of two knowledge-based programs, one
appropriate for games represented in normal form, the other for games
represented in extensive form. These knowledge-based programs can be viewed as
embodying rationality. The representation works even if (a) information sets do
not capture an agent's knowledge, (b) uncertainty is not represented by
probability, or (c) the underlying game is not common knowledge.


title: Properties of Codes with the Rank Metric

abstract:
  In this paper, we study properties of rank metric codes in general and
maximum rank distance (MRD) codes in particular. For codes with the rank
metric, we first establish Gilbert and sphere-packing bounds, and then obtain
the asymptotic forms of these two bounds and the Singleton bound. Based on the
asymptotic bounds, we observe that asymptotically Gilbert-Varsharmov bound is
exceeded by MRD codes and sphere-packing bound cannot be attained. We also
establish bounds on the rank covering radius of maximal codes, and show that
all MRD codes are maximal codes and all the MRD codes known so far achieve the
maximum rank covering radius.


title: A Mobile Transient Internet Architecture

abstract:
  This paper describes a new architecture for transient mobile networks
destined to merge existing and future network architectures, communication
implementations and protocol operations by introducing a new paradigm to data
delivery and identification. The main goal of our research is to enable
seamless end-to-end communication between mobile and stationary devices across
multiple networks and through multiple communication environments. The
architecture establishes a set of infrastructure components and protocols that
set the ground for a Persistent Identification Network (PIN). The basis for the
operation of PIN is an identification space consisting of unique location
independent identifiers similar to the ones implemented in the Handle system.
Persistent Identifiers are used to identify and locate Digital Entities which
can include devices, services, users and even traffic. The architecture
establishes a primary connection independent logical structure that can operate
over conventional networks or more advanced peer-to-peer aggregation networks.
Communication is based on routing pools and novel protocols for routing data
across several abstraction levels of the network, regardless of the end-points'
current association and state...


title: Entropy generation in a model of reversible computation

abstract:
  We present a model in which, due to the quantum nature of the signals
controlling the implementation time of successive unitary computational steps,
\emph{physical} irreversibility appears in the execution of a \emph{logically}
reversible computation.


title: Quantum communication is possible with pure state

abstract:
  It is believed that quantum communication is not possible with a pure
ensemble of states because quantum entropy of pure state is zero. This is
indeed possible due to geometric consequence of entanglement.


title: On the Secrecy Capacity of Fading Channels

abstract:
  We consider the secure transmission of information over an ergodic fading
channel in the presence of an eavesdropper. Our eavesdropper can be viewed as
the wireless counterpart of Wyner's wiretapper. The secrecy capacity of such a
system is characterized under the assumption of asymptotically long coherence
intervals. We first consider the full Channel State Information (CSI) case,
where the transmitter has access to the channel gains of the legitimate
receiver and the eavesdropper. The secrecy capacity under this full CSI
assumption serves as an upper bound for the secrecy capacity when only the CSI
of the legitimate receiver is known at the transmitter, which is characterized
next. In each scenario, the perfect secrecy capacity is obtained along with the
optimal power and rate allocation strategies. We then propose a low-complexity
on/off power allocation strategy that achieves near-optimal performance with
only the main channel CSI. More specifically, this scheme is shown to be
asymptotically optimal as the average SNR goes to infinity, and interestingly,
is shown to attain the secrecy capacity under the full CSI assumption.
Remarkably, our results reveal the positive impact of fading on the secrecy
capacity and establish the critical role of rate adaptation, based on the main
channel CSI, in facilitating secure communications over slow fading channels.


title: ARQ Diversity in Fading Random Access Channels

abstract:
  A cross-layer optimization approach is adopted for the design of symmetric
random access wireless systems. Instead of the traditional collision model, a
more realistic physical layer model is considered. Based on this model, an
Incremental Redundancy Automatic Repeat reQuest (IR-ARQ) scheme, tailored to
jointly combat the effects of collisions, multi-path fading, and additive
noise, is developed. The Diversity-Multiplexing-Delay tradeoff (DMDT) of the
proposed scheme is analyzed for fully-loaded queues, and compared with that of
Gallager tree algorithm for collision resolution and the network-assisted
diversity multiple access (NDMA) protocol of Tsatsanis et al.. The fully-loaded
queue model is then replaced by one with random arrivals, under which these
protocols are compared in terms of the stability region, average delay and
diversity gain. Overall, our analytical and numerical results establish the
superiority of the proposed IR-ARQ scheme and reveal some important insights.
For example, it turns out that the performance is optimized, for a given total
throughput, by maximizing the probability that a certain user sends a new
packet and minimizing the transmission rate employed by each user.


title: How To Break Anonymity of the Netflix Prize Dataset

abstract:
  We present a new class of statistical de-anonymization attacks against
high-dimensional micro-data, such as individual preferences, recommendations,
transaction records and so on. Our techniques are robust to perturbation in the
data and tolerate some mistakes in the adversary's background knowledge.
  We apply our de-anonymization methodology to the Netflix Prize dataset, which
contains anonymous movie ratings of 500,000 subscribers of Netflix, the world's
largest online movie rental service. We demonstrate that an adversary who knows
only a little bit about an individual subscriber can easily identify this
subscriber's record in the dataset. Using the Internet Movie Database as the
source of background knowledge, we successfully identified the Netflix records
of known users, uncovering their apparent political preferences and other
potentially sensitive information.


title: On the Error Exponents of ARQ Channels with Deadlines

abstract:
  We consider communication over Automatic Repeat reQuest (ARQ) memoryless
channels with deadlines. In particular, an upper bound L is imposed on the
maximum number of ARQ transmission rounds. In this setup, it is shown that
incremental redundancy ARQ outperforms Forney's memoryless decoding in terms of
the achievable error exponents.


title: Interference Channels with Common Information

abstract:
  In this paper, we consider the discrete memoryless interference channel with
common information, in which two senders need deliver not only private messages
but also certain common messages to their corresponding receivers. We derive an
achievable rate region for such a channel by exploiting a random coding
strategy, namely cascaded superposition coding. We reveal that the derived
achievable rate region generalizes some important existing results for the
interference channels with or without common information. Furthermore, we
specialize to a class of deterministic interference channels with common
information, and show that the derived achievable rate region is indeed the
capacity region for this class of channels.


title: Doppler Spectrum Estimation by Ramanujan Fourier Transforms

abstract:
  The Doppler spectrum estimation of a weather radar signal in a classic way
can be made by two methods, temporal one based in the autocorrelation of the
successful signals, whereas the other one uses the estimation of the power
spectral density PSD by using Fourier transforms. We introduces a new tool of
signal processing based on Ramanujan sums cq(n), adapted to the analysis of
arithmetical sequences with several resonances p/q. These sums are almost
periodic according to time n of resonances and aperiodic according to the order
q of resonances. New results will be supplied by the use of Ramanujan Fourier
Transform (RFT) for the estimation of the Doppler spectrum for the weather
radar signal.


title: Intrusion detection mechanisms for VoIP applications

abstract:
  VoIP applications are emerging today as an important component in business
and communication industry. In this paper, we address the intrusion detection
and prevention in VoIP networks and describe how a conceptual solution based on
the Bayes inference approach can be used to reinforce the existent security
mechanisms. Our approach is based on network monitoring and analyzing of the
VoIP-specific traffic. We give a detailed example on attack detection using the
SIP signaling protocol.


title: Stochastic Formal Methods for Hybrid Systems

abstract:
  We provide a framework to bound the probability that accumulated errors were
never above a given threshold on hybrid systems. Such systems are used for
example to model an aircraft or a nuclear power plant on one side and its
software on the other side. This report contains simple formulas based on
L\'evy's and Markov's inequalities and it presents a formal theory of random
variables with a special focus on producing concrete results. We selected four
very common applications that fit in our framework and cover the common
practices of hybrid systems that evolve for a long time. We compute the number
of bits that remain continuously significant in the first two applications with
a probability of failure around one against a billion, where worst case
analysis considers that no significant bit remains. We are using PVS as such
formal tools force explicit statement of all hypotheses and prevent incorrect
uses of theorems.


title: Local approximate inference algorithms

abstract:
  We present a new local approximation algorithm for computing Maximum a
Posteriori (MAP) and log-partition function for arbitrary exponential family
distribution represented by a finite-valued pair-wise Markov random field
(MRF), say $G$. Our algorithm is based on decomposition of $G$ into {\em
appropriately} chosen small components; then computing estimates locally in
each of these components and then producing a {\em good} global solution. We
show that if the underlying graph $G$ either excludes some finite-sized graph
as its minor (e.g. Planar graph) or has low doubling dimension (e.g. any graph
with {\em geometry}), then our algorithm will produce solution for both
questions within {\em arbitrary accuracy}. We present a message-passing
implementation of our algorithm for MAP computation using self-avoiding walk of
graph. In order to evaluate the computational cost of this implementation, we
derive novel tight bounds on the size of self-avoiding walk tree for arbitrary
graph.
  As a consequence of our algorithmic result, we show that the normalized
log-partition function (also known as free-energy) for a class of {\em regular}
MRFs will converge to a limit, that is computable to an arbitrary accuracy.


title:
On the Performance of Lossless Joint Source-Channel Coding Based on
  Linear Codes

abstract:
  A general lossless joint source-channel coding scheme based on linear codes
is proposed and then analyzed in this paper. It is shown that a linear code
with good joint spectrum can be used to establish limit-approaching joint
source-channel coding schemes for arbitrary sources and channels, where the
joint spectrum of the code is a generalization of the input-output weight
distribution.


title:
CHAC. A MOACO Algorithm for Computation of Bi-Criteria Military Unit
  Path in the Battlefield

abstract:
  In this paper we propose a Multi-Objective Ant Colony Optimization (MOACO)
algorithm called CHAC, which has been designed to solve the problem of finding
the path on a map (corresponding to a simulated battlefield) that minimizes
resources while maximizing safety. CHAC has been tested with two different
state transition rules: an aggregative function that combines the heuristic and
pheromone information of both objectives and a second one that is based on the
dominance concept of multiobjective optimization problems. These rules have
been evaluated in several different situations (maps with different degree of
difficulty), and we have found that they yield better results than a greedy
algorithm (taken as baseline) in addition to a military behaviour that is also
better in the tactical sense. The aggregative function, in general, yields
better results than the one based on dominance.


title: Instant Computing - A New Computation Paradigm

abstract:
  Voltage peaks on a conventional computer's power lines allow for the
well-known dangerous DPA attacks. We show that measurement of a quantum
computer's transient state during a computational step reveals information
about a complete computation of arbitrary length, which can be extracted by
repeated probing, if the computer is suitably programmed. Instant computing, as
we name this mode of operation, recognizes for any total or partial recursive
function arguments lying in the domain of definition and yields their function
value with arbitrary small error probability in probabilistic linear time. This
implies recognition of (not necessarily recursively enumerable) complements of
recursively enumerable sets and the solution of the halting problem. Future
quantum computers are shown to be likely to allow for instant computing, and
some consequences are pointed out.


title: An Achievable Rate Region for the Gaussian Interference Channel

abstract:
  An achievable rate region for the Gaussian interference channel is derived
using Sato's modified frequency division multiplexing idea and a special case
of Han and Kobayashi's rate region (denoted by $\Gmat^\prime$). We show that
the new inner bound includes $\Gmat^\prime$, Sason's rate region $\Dmat$, as
well as the achievable region via TDM/FDM, as its subsets. The advantage of
this improved inner bound over $\Gmat^\prime$ arises due to its inherent
ability to utilize the whole transmit power range on the real line without
violating the power constraint. We also provide analysis to examine the
conditions for the new achievable region to strictly extend $\Gmat^\prime$.


title: DepAnn - An Annotation Tool for Dependency Treebanks

abstract:
  DepAnn is an interactive annotation tool for dependency treebanks, providing
both graphical and text-based annotation interfaces. The tool is aimed for
semi-automatic creation of treebanks. It aids the manual inspection and
correction of automatically created parses, making the annotation process
faster and less error-prone. A novel feature of the tool is that it enables the
user to view outputs from several parsers as the basis for creating the final
tree to be saved to the treebank. DepAnn uses TIGER-XML, an XML-based general
encoding format for both, representing the parser outputs and saving the
annotated treebank. The tool includes an automatic consistency checker for
sentence structures. In addition, the tool enables users to build structures
manually, add comments on the annotations, modify the tagsets, and mark
sentences for further revision.