title: Applying and Combining Three Different Aspect Mining Techniques

abstract:
  Understanding a software system at source-code level requires understanding
the different concerns that it addresses, which in turn requires a way to
identify these concerns in the source code. Whereas some concerns are
explicitly represented by program entities (like classes, methods and
variables) and thus are easy to identify, crosscutting concerns are not
captured by a single program entity but are scattered over many program
entities and are tangled with the other concerns. Because of their crosscutting
nature, such crosscutting concerns are difficult to identify, and reduce the
understandability of the system as a whole.
  In this paper, we report on a combined experiment in which we try to identify
crosscutting concerns in the JHotDraw framework automatically. We first apply
three independently developed aspect mining techniques to JHotDraw and evaluate
and compare their results. Based on this analysis, we present three interesting
combinations of these three techniques, and show how these combinations provide
a more complete coverage of the detected concerns as compared to the original
techniques individually. Our results are a first step towards improving the
understandability of a system that contains crosscutting concerns, and can be
used as a basis for refactoring the identified crosscutting concerns into
aspects.


title: Theory of sexes by Geodakian as it is advanced by Iskrin

abstract:
  In 1960s V.Geodakian proposed a theory that explains sexes as a mechanism for
evolutionary adaptation of the species to changing environmental conditions. In
2001 V.Iskrin refined and augmented the concepts of Geodakian and gave a new
and interesting explanation to several phenomena which involve sex, and sex
ratio, including the war-years phenomena. He also introduced a new concept of
the "catastrophic sex ratio." This note is an attempt to digest technical
aspects of the new ideas by Iskrin.


title: 3-facial colouring of plane graphs

abstract:
  A plane graph is l-facially k-colourable if its vertices can be coloured with
k colours such that any two distinct vertices on a facial segment of length at
most l are coloured differently. We prove that every plane graph is 3-facially
11-colourable. As a consequence, we derive that every 2-connected plane graph
with maximum face-size at most 7 is cyclically 11-colourable. These two bounds
are for one off from those that are proposed by the (3l+1)-Conjecture and the
Cyclic Conjecture.


title:
Almost Periodicity, Finite Automata Mappings and Related Effectiveness
  Issues

abstract:
  The paper studies different variants of almost periodicity notion. We
introduce the class of eventually strongly almost periodic sequences where some
suffix is strongly almost periodic (=uniformly recurrent). The class of almost
periodic sequences includes the class of eventually strongly almost periodic
sequences, and we prove this inclusion to be strict. We prove that the class of
eventually strongly almost periodic sequences is closed under finite automata
mappings and finite transducers. Moreover, an effective form of this result is
presented. Finally we consider some algorithmic questions concerning almost
periodicity.


title: ITs, a structure sensitive information theory

abstract:
  Broadly speaking Information theory (IT) assumes no structure of the
underlying states. But what about contexts where states do have a clear
structure - how should IT cope with such situations? And if such coping is at
all possible then - how should structure be expressed so that it can be coped
with? A possible answer to these questions is presented here. Noting that IT
can cope well with a structure expressed as an accurate clustering (by shifting
to the implied reduced alphabet), a generalization is suggested in which
structure is expressed as a measure on reduced alphabets. Given such structure
an extension of IT is presented where the reduced alphabets are treated
simultaneously. This structure-sensitive IT, called ITs, extends traditional IT
in the sense that: a)there are structure-sensitive analogs to the notions of
traditional IT and b)translating a theorem in IT by replacing its notions with
their structure-sensitive counterparts, yields a (provable) theorem of ITs.
Seemingly paradoxically, ITs extends IT but it's completely within the
framework of IT. The richness of the suggested structures is demonstrated by
two disparate families studied in more detail: the family of hierarchical
structures and the family of linear structures. The formal findings extend the
scope of cases to which a rigorous application of IT can be applied (with
implications on quantization, for example). The implications on the foundations
of IT are that the assumption regarding no underlying structure of states is
not mandatory and that there is a framework for expressing such underlying
structure.


title: A simple generalization of El-Gamal cryptosystem to non-abelian groups

abstract:
  In this paper we study the MOR cryptosystem. We use the group of
unitriangular matrices over a finite field as the non-abelian group in the MOR
cryptosystem. We show that a cryptosystem similar to the El-Gamal cryptosystem
over finite fields can be built using the proposed groups and a set of
automorphisms of these groups. We also show that the security of this proposed
MOR cryptosystem is equivalent to the El-Gamal cryptosystem over finite fields.


title: A Flexible Structured-based Representation for XML Document Mining

abstract:
  This paper reports on the INRIA group's approach to XML mining while
participating in the INEX XML Mining track 2005. We use a flexible
representation of XML documents that allows taking into account the structure
only or both the structure and content. Our approach consists of representing
XML documents by a set of their sub-paths, defined according to some criteria
(length, root beginning, leaf ending). By considering those sub-paths as words,
we can use standard methods for vocabulary reduction, and simple clustering
methods such as K-means that scale well. We actually use an implementation of
the clustering algorithm known as "dynamic clouds" that can work with distinct
groups of independent variables put in separate variables. This is useful in
our model since embedded sub-paths are not independent: we split potentially
dependant paths into separate variables, resulting in each of them containing
independant paths. Experiments with the INEX collections show good results for
the structure-only collections, but our approach could not scale well for large
structure-and-content collections.


title: Database Querying under Changing Preferences

abstract:
  We present here a formal foundation for an iterative and incremental approach
to constructing and evaluating preference queries. Our main focus is on query
modification: a query transformation approach which works by revising the
preference relation in the query. We provide a detailed analysis of the cases
where the order-theoretic properties of the preference relation are preserved
by the revision. We consider a number of different revision operators: union,
prioritized and Pareto composition. We also formulate algebraic laws that
enable incremental evaluation of preference queries. Finally, we consider two
variations of the basic framework: finite restrictions of preference relations
and weak-order extensions of strict partial order preference relations.


title: Strong Consistency of the Good-Turing Estimator

abstract:
  We consider the problem of estimating the total probability of all symbols
that appear with a given frequency in a string of i.i.d. random variables with
unknown distribution. We focus on the regime in which the block length is large
yet no symbol appears frequently in the string. This is accomplished by
allowing the distribution to change with the block length. Under a natural
convergence assumption on the sequence of underlying distributions, we show
that the total probabilities converge to a deterministic limit, which we
characterize. We then show that the Good-Turing total probability estimator is
strongly consistent.


title: The uncovering of hidden structures by Latent Semantic Analysis

abstract:
  Latent Semantic Analysis (LSA) is a well known method for information
retrieval. It has also been applied as a model of cognitive processing and
word-meaning acquisition. This dual importance of LSA derives from its capacity
to modulate the meaning of words by contexts, dealing successfully with
polysemy and synonymy. The underlying reasons that make the method work are not
clear enough. We propose that the method works because it detects an underlying
block structure (the blocks corresponding to topics) in the term by document
matrix. In real cases this block structure is hidden because of perturbations.
We propose that the correct explanation for LSA must be searched in the
structure of singular vectors rather than in the profile of singular values.
Using Perron-Frobenius theory we show that the presence of disjoint blocks of
documents is marked by sign-homogeneous entries in the vectors corresponding to
the documents of one block and zeros elsewhere. In the case of nearly disjoint
blocks, perturbation theory shows that if the perturbations are small the zeros
in the leading vectors are replaced by small numbers (pseudo-zeros). Since the
singular values of each block might be very different in magnitude, their order
does not mirror the order of blocks. When the norms of the blocks are similar,
LSA works fine, but we propose that when the topics have different sizes, the
usual procedure of selecting the first k singular triplets (k being the number
of blocks) should be replaced by a method that selects the perturbed Perron
vectors for each block.


title: An Analysis of Arithmetic Constraints on Integer Intervals

abstract:
  Arithmetic constraints on integer intervals are supported in many constraint
programming systems. We study here a number of approaches to implement
constraint propagation for these constraints. To describe them we introduce
integer interval arithmetic. Each approach is explained using appropriate proof
rules that reduce the variable domains. We compare these approaches using a set
of benchmarks. For the most promising approach we provide results that
characterize the effect of constraint propagation. This is a full version of
our earlier paper, cs.PL/0403016.


title: Performance of STBC MC-CDMA systems over outdoor realistic MIMO channels

abstract:
  The paper deals with orthogonal space-time block coded MC-CDMA systems in
outdoor realistic downlink scenarios with up to two transmit and receive
antennas. Assuming no channel state information at the transmitter, we compare
several linear single-user detection and spreading schemes, with or without
channel coding, achieving a spectral efficiency of 1-2 bits/s/Hz. The different
results obtained demonstrate that spatial diversity significantly improves the
performance of MC-CDMA systems, and allows different chip-mapping without
notably decreasing performance. Moreover, the global system exhibits a good
trade-off between complexity at mobile stations and performance. Then,
Alamouti's STBC MC-CDMA schemes derive full benefit from the frequency and
spatial diversities and can be considered as a very realistic and promising
candidate for the air interface downlink of the 4/sup th/ generation mobile
radio systems.


title: Feynman Checkerboard as a Model of Discrete Space-Time

abstract:
  In 1965, Feynman wrote of using a lattice containing one dimension of space
and one dimension of time to derive aspects of quantum mechanics. Instead of
summing the behavior of all possible paths as he did, this paper will consider
the motion of single particles within this discrete Space-Time lattice,
sometimes called Feynman's Checkerboard. This empirical approach yielded
several predicted emergent properties for a discrete Space-Time lattice, one of
which is novel and testable.


title: Modelling the Probability Density of Markov Sources

abstract:
  This paper introduces an objective function that seeks to minimise the
average total number of bits required to encode the joint state of all of the
layers of a Markov source. This type of encoder may be applied to the problem
of optimising the bottom-up (recognition model) and top-down (generative model)
connections in a multilayer neural network, and it unifies several previous
results on the optimisation of multilayer neural networks.


title: Iterative Decoding Performance Bounds for LDPC Codes on Noisy Channels

abstract:
  The asymptotic iterative decoding performances of low-density parity-check
(LDPC) codes using min-sum (MS) and sum-product (SP) decoding algorithms on
memoryless binary-input output-symmetric (MBIOS) channels are analyzed in this
paper. For MS decoding, the analysis is done by upper bounding the bit error
probability of the root bit of a tree code by the sequence error probability of
a subcode of the tree code assuming the transmission of the all-zero codeword.
The result is a recursive upper bound on the bit error probability after each
iteration. For SP decoding, we derive a recursively determined lower bound on
the bit error probability after each iteration. This recursive lower bound
recovers the density evolution equation of LDPC codes on the binary erasure
channel (BEC) with inequalities satisfied with equalities. A significant
implication of this result is that the performance of LDPC codes under SP
decoding on the BEC is an upper bound of the performance on all MBIOS channels
with the same uncoded bit error probability. All results hold for the more
general multi-edge type LDPC codes.


title: Slepian-Wolf Code Design via Source-Channel Correspondence

abstract:
  We consider Slepian-Wolf code design based on LDPC (low-density parity-check)
coset codes for memoryless source-side information pairs. A density evolution
formula, equipped with a concentration theorem, is derived for Slepian- Wolf
coding based on LDPC coset codes. As a consequence, an intimate connection
between Slepian-Wolf coding and channel coding is established. Specifically we
show that, under density evolution, design of binary LDPC coset codes for
Slepian-Wolf coding of an arbitrary memoryless source-side information pair
reduces to design of binary LDPC codes for binary-input output-symmetric
channels without loss of optimality. With this connection, many classic results
in channel coding can be easily translated into the Slepian-Wolf setting.


title: Ten Incredibly Dangerous Software Ideas

abstract:
  This is a rough draft synopsis of a book presently in preparation. This book
provides a systematic critique of the software industry. This critique is
accomplished using classical methods in practical design science.


title: Sharp threshold for hamiltonicity of random geometric graphs

abstract:
  We show for an arbitrary $\ell_p$ norm that the property that a random
geometric graph $\mathcal G(n,r)$ contains a Hamiltonian cycle exhibits a sharp
threshold at $r=r(n)=\sqrt{\frac{\log n}{\alpha_p n}}$, where $\alpha_p$ is the
area of the unit disk in the $\ell_p$ norm. The proof is constructive and
yields a linear time algorithm for finding a Hamiltonian cycle of $\RG$ a.a.s.,
provided $r=r(n)\ge\sqrt{\frac{\log n}{(\alpha_p -\epsilon)n}}$ for some fixed
$\epsilon > 0$.


title:
Results on Parity-Check Matrices with Optimal Stopping and/or Dead-End
  Set Enumerators

abstract:
  The performance of iterative decoding techniques for linear block codes
correcting erasures depends very much on the sizes of the stopping sets
associated with the underlying Tanner graph, or, equivalently, the parity-check
matrix representing the code. In this paper, we introduce the notion of
dead-end sets to explicitly demonstrate this dependency. The choice of the
parity-check matrix entails a trade-off between performance and complexity. We
give bounds on the complexity of iterative decoders achieving optimal
performance in terms of the sizes of the underlying parity-check matrices.
Further, we fully characterize codes for which the optimal stopping set
enumerator equals the weight enumerator.


title: The evolution of navigable small-world networks

abstract:
  Small-world networks, which combine randomized and structured elements, are
seen as prevalent in nature. Several random graph models have been given for
small-world networks, with one of the most fruitful, introduced by Jon
Kleinberg, showing in which type of graphs it is possible to route, or
navigate, between vertices with very little knowledge of the graph itself.
Kleinberg's model is static, with random edges added to a fixed grid. In this
paper we introduce, analyze and test a randomized algorithm which successively
rewires a graph with every application. The resulting process gives a model for
the evolution of small-world networks with properties similar to those studied
by Kleinberg.


title: Path-independent load balancing with unreliable machines

abstract:
  We consider algorithms for load balancing on unreliable machines. The
objective is to optimize the two criteria of minimizing the makespan and
minimizing job reassignments in response to machine failures. We assume that
the set of jobs is known in advance but that the pattern of machine failures is
unpredictable. Motivated by the requirements of BGP routing, we consider
path-independent algorithms, with the property that the job assignment is
completely determined by the subset of available machines and not the previous
history of the assignments. We examine first the question of performance
measurement of path-independent load-balancing algorithms, giving the measure
of makespan and the normalized measure of reassignments cost. We then describe
two classes of algorithms for optimizing these measures against an oblivious
adversary for identical machines. The first, based on independent random
assignments, gives expected reassignment costs within a factor of 2 of optimal
and gives a makespan within a factor of O(log m/log log m) of optimal with high
probability, for unknown job sizes. The second, in which jobs are first grouped
into bins and at most one bin is assigned to each machine, gives
constant-factor ratios on both reassignment cost and makespan, for known job
sizes. Several open problems are discussed.


title:
A general computation rule for lossy summaries/messages with examples
  from equalization

abstract:
  Elaborating on prior work by Minka, we formulate a general computation rule
for lossy messages. An important special case (with many applications in
communications) is the conversion of "soft-bit" messages to Gaussian messages.
By this method, the performance of a Kalman equalizer is improved, both for
uncoded and coded transmission.


title:
A Quasi-Optimal Leader Election Algorithm in Radio Networks with
  Log-Logarithmic Awake Time Slots

abstract:
  Radio networks (RN) are distributed systems (\textit{ad hoc networks})
consisting in $n \ge 2$ radio stations. Assuming the number $n$ unknown, two
distinct models of RN without collision detection (\textit{no-CD}) are
addressed: the model with \textit{weak no-CD} RN and the one with
\textit{strong no-CD} RN. We design and analyze two distributed leader election
protocols, each one running in each of the above two (no-CD RN) models,
respectively. Both randomized protocols are shown to elect a leader within
$\BO(\log{(n)})$ expected time, with no station being awake for more than
$\BO(\log{\log{(n)}})$ time slots (such algorithms are said to be
\textit{energy-efficient}). Therefore, a new class of efficient algorithms is
set up that matchthe $\Omega(\log{(n)})$ time lower-bound established by
Kushilevitz and Mansour.


title:
A Coding Theorem Characterizing Renyi's Entropy through
  Variable-to-Fixed Length Codes

abstract: This paper has been withdrawn


title:
Towards a General Theory of Simultaneous Diophantine Approximation of
  Formal Power Series: Multidimensional Linear Complexity

abstract:
  We model the development of the linear complexity of multisequences by a
stochastic infinite state machine, the Battery-Discharge-Model, BDM. The states
s in S of the BDM have asymptotic probabilities or mass Pr(s)=1/(P(q,M)
q^K(s)), where K(s) in N_0 is the class of the state s, and P(q,M)=\sum_(K
in\N0) P_M(K)q^(-K)=\prod_(i=1..M) q^i/(q^i-1) is the generating function of
the number of partitions into at most M parts. We have (for each timestep
modulo M+1) just P_M(K) states of class K \.
  We obtain a closed formula for the asymptotic probability for the linear
complexity deviation d(n) := L(n)-\lceil n\cdot M/(M+1)\rceil with
Pr(d)=O(q^(-|d|(M+1))), for M in N, for d in Z. The precise formula is given in
the text. It has been verified numerically for M=1..8, and is conjectured to
hold for all M in N.
  From the asymptotic growth (proven for all M in N), we infer the Law of the
Logarithm for the linear complexity deviation, -liminf_{n\to\infty} d_a(n) /
log n = 1 /((M+1)log q) = limsup_{n\to\infty} d_a(n) / log n, which immediately
yields L_a(n)/n \to M/(M+1) with measure one, for all M in N, a result recently
shown already by Niederreiter and Wang. Keywords: Linear complexity, linear
complexity deviation, multisequence, Battery Discharge Model, isometry.


title:
A distributed approximation algorithm for the minimum degree minimum
  weight spanning trees

abstract:
  Fischer has shown how to compute a minimum weight spanning tree of degree at
most $b \Delta^* + \lceil \log\_b n\rceil$ in time $O(n^{4 + 1/\ln b})$ for any
constant $b > 1$, where $\Delta^*$ is the value of an optimal solution and $n$
is the number of nodes in the network. In this paper, we propose a distributed
version of Fischer's algorithm that requires messages and time complexity
$O(n^{2 + 1/\ln b})$, and O(n) space per node.


title: Asymptotic Analysis of a Leader Election Algorithm

abstract:
  Itai and Rodeh showed that, on the average, the communication of a leader
election algorithm takes no more than $LN$ bits, where $L \simeq 2.441716$ and
$N$ denotes the size of the ring. We give a precise asymptotic analysis of the
average number of rounds M(n) required by the algorithm, proving for example
that $\dis M(\infty) := \lim\_{n\to \infty} M(n) = 2.441715879...$, where $n$
is the number of starting candidates in the election. Accurate asymptotic
expressions of the second moment $M^{(2)}(n)$ of the discrete random variable
at hand, its probability distribution, and the generalization to all moments
are given. Corresponding asymptotic expansions $(n\to \infty)$ are provided for
sufficiently large $j$, where $j$ counts the number of rounds. Our numerical
results show that all computations perfectly fit the observed values. Finally,
we investigate the generalization to probability $t/n$, where $t$ is a non
negative real parameter. The real function $\dis M(\infty,t) := \lim\_{n\to
\infty} M(n,t)$ is shown to admit \textit{one unique minimum} $M(\infty,t^{*})$
on the real segment $(0,2)$. Furthermore, the variations of $M(\infty,t)$ on
thewhole real line are also studied in detail.


title: Planar Graphs: Logical Complexity and Parallel Isomorphism Tests

abstract:
  We prove that every triconnected planar graph is definable by a first order
sentence that uses at most 15 variables and has quantifier depth at most
$11\log_2 n+43$. As a consequence, a canonic form of such graphs is computable
in $AC^1$ by the 14-dimensional Weisfeiler-Lehman algorithm. This provides
another way to show that the planar graph isomorphism is solvable in $AC^1$.


title:
Quasi-Optimal Leader Election Algorithms in Radio Networks with
  Loglogarithmic Awake Time Slots

abstract:
  A radio network (RN) is a distributed system consisting of $n$ radio
stations. We design and analyze two distributed leader election protocols in RN
where the number $n$ of radio stations is unknown. The first algorithm runs
under the assumption of {\it limited collision detection}, while the second
assumes that {\it no collision detection} is available. By ``limited collision
detection'', we mean that if exactly one station sends (broadcasts) a message,
then all stations (including the transmitter) that are listening at this moment
receive the sent message. By contrast, the second no-collision-detection
algorithm assumes that a station cannot simultaneously send and listen signals.
Moreover, both protocols allow the stations to keep asleep as long as possible,
thus minimizing their awake time slots (such algorithms are called {\it
energy-efficient}). Both randomized protocols in RN areshown to elect a leader
in $O(\log{(n)})$ expected time, with no station being awake for more than
$O(\log{\log{(n)}})$ time slots. Therefore, a new class of efficient algorithms
is set up that match the $\Omega(\log{(n)})$ time lower-bound established by
Kushilevitz and Mansour.


title:
Resettable Zero Knowledge in the Bare Public-Key Model under Standard
  Assumption

abstract:
  In this paper we resolve an open problem regarding resettable zero knowledge
in the bare public-key (BPK for short) model: Does there exist constant round
resettable zero knowledge argument with concurrent soundness for $\mathcal{NP}$
in BPK model without assuming \emph{sub-exponential hardness}? We give a
positive answer to this question by presenting such a protocol for any language
in $\mathcal{NP}$ in the bare public-key model assuming only
collision-resistant hash functions against \emph{polynomial-time} adversaries.


title: Combinatorial laplacians and positivity under partial transpose

abstract:
  Density matrices of graphs are combinatorial laplacians normalized to have
trace one (Braunstein \emph{et al.} \emph{Phys. Rev. A,} \textbf{73}:1, 012320
(2006)). If the vertices of a graph are arranged as an array, then its density
matrix carries a block structure with respect to which properties such as
separability can be considered. We prove that the so-called degree-criterion,
which was conjectured to be necessary and sufficient for separability of
density matrices of graphs, is equivalent to the PPT-criterion. As such it is
not sufficient for testing the separability of density matrices of graphs (we
provide an explicit example). Nonetheless, we prove the sufficiency when one of
the array dimensions has length two (for an alternative proof see Wu,
\emph{Phys. Lett. A}\textbf{351} (2006), no. 1-2, 18--22).
  Finally we derive a rational upper bound on the concurrence of density
matrices of graphs and show that this bound is exact for graphs on four
vertices.


title:
The Minimal Cost Algorithm for Off-Line Diagnosability of Discrete Event
  Systems

abstract:
  The failure diagnosis for {\it discrete event systems} (DESs) has been given
considerable attention in recent years. Both on-line and off-line diagnostics
in the framework of DESs was first considered by Lin Feng in 1994, and
particularly an algorithm for diagnosability of DESs was presented. Motivated
by some existing problems to be overcome in previous work, in this paper, we
investigate the minimal cost algorithm for diagnosability of DESs.
  More specifically: (i) we give a generic method for judging a system's
off-line diagnosability, and the complexity of this algorithm is
polynomial-time; (ii) and in particular, we present an algorithm of how to
search for the minimal set in all observable event sets, whereas the previous
algorithm may find {\it non-minimal} one.


title:
Retouched Bloom Filters: Allowing Networked Applications to Flexibly
  Trade Off False Positives Against False Negatives

abstract:
  Where distributed agents must share voluminous set membership information,
Bloom filters provide a compact, though lossy, way for them to do so. Numerous
recent networking papers have examined the trade-offs between the bandwidth
consumed by the transmission of Bloom filters, and the error rate, which takes
the form of false positives, and which rises the more the filters are
compressed. In this paper, we introduce the retouched Bloom filter (RBF), an
extension that makes the Bloom filter more flexible by permitting the removal
of selected false positives at the expense of generating random false
negatives. We analytically show that RBFs created through a random process
maintain an overall error rate, expressed as a combination of the false
positive rate and the false negative rate, that is equal to the false positive
rate of the corresponding Bloom filters. We further provide some simple
heuristics and improved algorithms that decrease the false positive rate more
than than the corresponding increase in the false negative rate, when creating
RBFs. Finally, we demonstrate the advantages of an RBF over a Bloom filter in a
distributed network topology measurement application, where information about
large stop sets must be shared among route tracing monitors.


title: Set-Theoretic Preliminaries for Computer Scientists

abstract:
  The basics of set theory are usually copied, directly or indirectly, by
computer scientists from introductions to mathematical texts. Often
mathematicians are content with special cases when the general case is of no
mathematical interest. But sometimes what is of no mathematical interest is of
great practical interest in computer science. For example, non-binary relations
in mathematics tend to have numerical indexes and tend to be unsorted. In the
theory and practice of relational databases both these simplifications are
unwarranted. In response to this situation we present here an alternative to
the ``set-theoretic preliminaries'' usually found in computer science texts.
This paper separates binary relations from the kind of relations that are
needed in relational databases. Its treatment of functions supports both
computer science in general and the kind of relations needed in databases. As a
sample application this paper shows how the mathematical theory of relations
naturally leads to the relational data model and how the operations on
relations are by themselves already a powerful vehicle for queries.


title: PALS: Efficient Or-Parallelism on Beowulf Clusters

abstract:
  This paper describes the development of the PALS system, an implementation of
Prolog capable of efficiently exploiting or-parallelism on distributed-memory
platforms--specifically Beowulf clusters. PALS makes use of a novel technique,
called incremental stack-splitting. The technique proposed builds on the
stack-splitting approach, previously described by the authors and
experimentally validated on shared-memory systems, which in turn is an
evolution of the stack-copying method used in a variety of parallel logic and
constraint systems--e.g., MUSE, YAP, and Penny. The PALS system is the first
distributed or-parallel implementation of Prolog based on the stack-splitting
method ever realized. The results presented confirm the superiority of this
method as a simple yet effective technique to transition from shared-memory to
distributed-memory systems. PALS extends stack-splitting by combining it with
incremental copying; the paper provides a description of the implementation of
PALS, including details of how distributed scheduling is handled. We also
investigate methodologies to effectively support order-sensitive predicates
(e.g., side-effects) in the context of the stack-splitting scheme. Experimental
results obtained from running PALS on both Shared Memory and Beowulf systems
are presented and analyzed.


title:
Methods for Partitioning Data to Improve Parallel Execution Time for
  Sorting on Heterogeneous Clusters

abstract:
  The aim of the paper is to introduce general techniques in order to optimize
the parallel execution time of sorting on a distributed architectures with
processors of various speeds. Such an application requires a partitioning step.
For uniformly related processors (processors speeds are related by a constant
factor), we develop a constant time technique for mastering processor load and
execution time in an heterogeneous environment and also a technique to deal
with unknown cost functions. For non uniformly related processors, we use a
technique based on dynamic programming. Most of the time, the solutions are in
O(p) (p is the number of processors), independent of the problem size n.
Consequently, there is a small overhead regarding the problem we deal with but
it is inherently limited by the knowing of time complexity of the portion of
code following the partitioning.


title:
Towards a classical proof of exponential lower bound for 2-probe smooth
  codes

abstract:
  Let C: {0,1}^n -> {0,1}^m be a code encoding an n-bit string into an m-bit
string. Such a code is called a (q, c, e) smooth code if there exists a
decoding algorithm which while decoding any bit of the input, makes at most q
probes on the code word and the probability that it looks at any location is at
most c/m. The error made by the decoding algorithm is at most e. Smooth codes
were introduced by Katz and Trevisan in connection with Locally decodable
codes.
  For 2-probe smooth codes Kerenedis and de Wolf have shown exponential in n
lower bound on m in case c and e are constants. Their lower bound proof went
through quantum arguments and interestingly there is no completely classical
argument as yet for the same (albeit completely classical !) statement.
  We do not match the bounds shown by Kerenedis and de Wolf but however show
the following. Let C: {0,1}^n -> {0,1}^m be a (2,c,e) smooth code and if e <=
c^2/8n^2, then m >= 2^(n/320c^2 - 1)$. We hope that the arguments and
techniques used in this paper extend (or are helpful in making similar other
arguments), to match the bounds shown using quantum arguments. More so,
hopefully they extend to show bounds for codes with greater number of probes
where quantum arguments unfortunately do not yield good bounds (even for
3-probe codes).


title: Analysis of CDMA systems that are characterized by eigenvalue spectrum

abstract:
  An approach by which to analyze the performance of the code division multiple
access (CDMA) scheme, which is a core technology used in modern wireless
communication systems, is provided. The approach characterizes the objective
system by the eigenvalue spectrum of a cross-correlation matrix composed of
signature sequences used in CDMA communication, which enables us to handle a
wider class of CDMA systems beyond the basic model reported by Tanaka. The
utility of the novel scheme is shown by analyzing a system in which the
generation of signature sequences is designed for enhancing the orthogonality.


title: Use of UML and Model Transformations for Workflow Process Definitions

abstract:
  Currently many different modeling languages are used for workflow definitions
in BPM systems. Authors of this paper analyze the two most popular graphical
languages, with highest possibility of wide practical usage - UML Activity
diagrams (AD) and Business Process Modeling Notation (BPMN). The necessary in
practice workflow aspects are briefly discussed, and on this basis a natural AD
profile is proposed, which covers all of them. A functionally equivalent BPMN
subset is also selected. The semantics of both languages in the context of
process execution (namely, mapping to BPEL) is also analyzed in the paper. By
analyzing AD and BPMN metamodels, authors conclude that an exact transformation
from AD to BPMN is not trivial even for the selected subset, though these
languages are considered to be similar. Authors show how this transformation
could be defined in the MOLA transformation language.


title: Improved online hypercube packing

abstract:
  In this paper, we study online multidimensional bin packing problem when all
items are hypercubes.
  Based on the techniques in one dimensional bin packing algorithm Super
Harmonic by Seiden, we give a framework for online hypercube packing problem
and obtain new upper bounds of asymptotic competitive ratios.
  For square packing, we get an upper bound of 2.1439, which is better than
2.24437.
  For cube packing, we also give a new upper bound 2.6852 which is better than
2.9421 by Epstein and van Stee.


title: Strip Packing vs. Bin Packing

abstract:
  In this paper we establish a general algorithmic framework between bin
packing and strip packing, with which we achieve the same asymptotic bounds by
applying bin packing algorithms to strip packing. More precisely we obtain the
following results: (1) Any offline bin packing algorithm can be applied to
strip packing maintaining the same asymptotic worst-case ratio. Thus using FFD
(MFFD) as a subroutine, we get a practical (simple and fast) algorithm for
strip packing with an upper bound 11/9 (71/60). A simple AFPTAS for strip
packing immediately follows. (2) A class of Harmonic-based algorithms for bin
packing can be applied to online strip packing maintaining the same asymptotic
competitive ratio. It implies online strip packing admits an upper bound of
1.58889 on the asymptotic competitive ratio, which is very close to the lower
bound 1.5401 and significantly improves the previously best bound of 1.6910 and
affirmatively answers an open question posed by Csirik et. al.


title: PAC Classification based on PAC Estimates of Label Class Distributions

abstract:
  A standard approach in pattern classification is to estimate the
distributions of the label classes, and then to apply the Bayes classifier to
the estimates of the distributions in order to classify unlabeled examples. As
one might expect, the better our estimates of the label class distributions,
the better the resulting classifier will be. In this paper we make this
observation precise by identifying risk bounds of a classifier in terms of the
quality of the estimates of the label class distributions. We show how PAC
learnability relates to estimates of the distributions that have a PAC
guarantee on their $L_1$ distance from the true distribution, and we bound the
increase in negative log likelihood risk in terms of PAC bounds on the
KL-divergence. We give an inefficient but general-purpose smoothing method for
converting an estimated distribution that is good under the $L_1$ metric into a
distribution that is good under the KL-divergence.


title:
Evaluation de Techniques de Traitement des Refus\'{e}s pour l'Octroi de
  Cr\'{e}dit

abstract:
  We present the problem of "Reject Inference" for credit acceptance. Because
of the current legal framework (Basel II), credit institutions need to
industrialize their processes for credit acceptance, including Reject
Inference. We present here a methodology to compare various techniques of
Reject Inference and show that it is necessary, in the absence of real
theoretical results, to be able to produce and compare models adapted to
available data (selection of "best" model conditionnaly on data). We describe
some simulations run on a small data set to illustrate the approach and some
strategies for choosing the control group, which is the only valid approach to
Reject Inference.


title: Secure Component Deployment in the OSGi(tm) Release 4 Platform

abstract:
  Last years have seen a dramatic increase in the use of component platforms,
not only in classical application servers, but also more and more in the domain
of Embedded Systems. The OSGi(tm) platform is one of these platforms dedicated
to lightweight execution environments, and one of the most prominent. However,
new platforms also imply new security flaws, and a lack of both knowledge and
tools for protecting the exposed systems. This technical report aims at
fostering the understanding of security mechanisms in component deployment. It
focuses on securing the deployment of components. It presents the cryptographic
mechanisms necessary for signing OSGi(tm) bundles, as well as the detailed
process of bundle signature and validation. We also present the SFelix
platform, which is a secure extension to Felix OSGi(tm) framework
implementation. It includes our implementation of the bundle signature process,
as specified by OSGi(tm) Release 4 Security Layer. Moreover, a tool for signing
and publishing bundles, SFelix JarSigner, has been developed to conveniently
integrate bundle signature in the bundle deployment process.


title: Interactive Hatching and Stippling by Example

abstract:
  We describe a system that lets a designer interactively draw patterns of
strokes in the picture plane, then guide the synthesis of similar patterns over
new picture regions. Synthesis is based on an initial user-assisted analysis
phase in which the system recognizes distinct types of strokes (hatching and
stippling) and organizes them according to perceptual grouping criteria. The
synthesized strokes are produced by combining properties (eg. length,
orientation, parallelism, proximity) of the stroke groups extracted from the
input examples. We illustrate our technique with a drawing application that
allows the control of attributes and scale-dependent reproduction of the
synthesized patterns.


title:
Raisonner avec des diagrammes : perspectives cognitives et
  computationnelles

abstract:
  Diagrammatic, analogical or iconic representations are often contrasted with
linguistic or logical representations, in which the shape of the symbols is
arbitrary. The aim of this paper is to make a case for the usefulness of
diagrams in inferential knowledge representation systems. Although commonly
used, diagrams have for a long time suffered from the reputation of being only
a heuristic tool or a mere support for intuition. The first part of this paper
is an historical background paying tribute to the logicians, psychologists and
computer scientists who put an end to this formal prejudice against diagrams.
The second part is a discussion of their characteristics as opposed to those of
linguistic forms. The last part is aimed at reviving the interest for
heterogeneous representation systems including both linguistic and diagrammatic
representations.


title: Dealing with Metonymic Readings of Named Entities

abstract:
  The aim of this paper is to propose a method for tagging named entities (NE),
using natural language processing techniques. Beyond their literal meaning,
named entities are frequently subject to metonymy. We show the limits of
current NE type hierarchies and detail a new proposal aiming at dynamically
capturing the semantics of entities in context. This model can analyze complex
linguistic phenomena like metonymy, which are known to be difficult for natural
language processing but crucial for most applications. We present an
implementation and some test using the French ESTER corpus and give significant
results.


title: Linguistically Grounded Models of Language Change

abstract:
  Questions related to the evolution of language have recently known an
impressive increase of interest (Briscoe, 2002). This short paper aims at
questioning the scientific status of these models and their relations to
attested data. We show that one cannot directly model non-linguistic factors
(exogenous factors) even if they play a crucial role in language evolution. We
then examine the relation between linguistic models and attested language data,
as well as their contribution to cognitive linguistics.


title: Elementary Proof of a Theorem of Jean Ville

abstract:
  Considerable thought has been devoted to an adequate definition of the class
of infinite, random binary sequences (the sort of sequence that almost
certainly arises from flipping a fair coin indefinitely). The first
mathematical exploration of this problem was due to R. Von Mises, and based on
his concept of a "selection function." A decisive objection to Von Mises' idea
was formulated in a theorem offered by Jean Ville in 1939. It shows that some
sequences admitted by Von Mises as "random" in fact manifest a certain kind of
systematicity. Ville's proof is challenging, and an alternative approach has
appeared only in condensed form. We attempt to provide an expanded version of
the latter, alternative argument.


title:
Boundary cliques, clique trees and perfect sequences of maximal cliques
  of a chordal graph

abstract:
  We characterize clique trees of a chordal graph in their relation to
simplicial vertices and perfect sequences of maximal cliques. We investigate
boundary cliques defined by Shibata and clarify their relation to endpoints of
clique trees. Next we define a symmetric binary relation between the set of
clique trees and the set of perfect sequences of maximal cliques. We describe
the relation as a bipartite graph and prove that the bipartite graph is always
connected. Lastly we consider to characterize chordal graphs from the aspect of
non-uniqueness of clique trees.


title: Reasoning with Intervals on Granules

abstract:
  The formalizations of periods of time inside a linear model of Time are
usually based on the notion of intervals, that may contain or may not their
endpoints. This is not enought when the periods are written in terms of coarse
granularities with respect to the event taken into account. For instance, how
to express the inter-war period in terms of a {\em years} interval? This paper
presents a new type of intervals, neither open, nor closed or open-closed and
the extension of operations on intervals of this new type, in order to reduce
the gap between the discourse related to temporal relationship and its
translation into a discretized model of Time.


title: The Average Size of Giant Components Between the Double-Jump

abstract:
  We study the sizes of connected components according to their excesses during
a random graph process built with $n$ vertices. The considered model is the
continuous one defined in Janson 2000. An ${\ell}$-component is a connected
component with ${\ell}$ edges more than vertices. $\ell$ is also called the
\textit{excess} of such component. As our main result, we show that when $\ell$
and ${n \over \ell}$ are both large, the expected number of vertices that ever
belong to an $\ell$-component is about ${12}^{1/3} {\ell}^{1/3} n^{2/3}$. We
also obtain limit theorems for the number of creations of $\ell$-components.


title: Craig's Interpolation Theorem formalised and mechanised in Isabelle/HOL

abstract:
  We formalise and mechanise a construtive, proof theoretic proof of Craig's
Interpolation Theorem in Isabelle/HOL. We give all the definitions and lemma
statements both formally and informally. We also transcribe informally the
formal proofs. We detail the main features of our mechanisation, such as the
formalisation of binding for first order formulae. We also give some
applications of Craig's Interpolation Theorem.


title: Creation and Growth of Components in a Random Hypergraph Process

abstract:
  Denote by an $\ell$-component a connected $b$-uniform hypergraph with $k$
edges and $k(b-1) - \ell$ vertices. We prove that the expected number of
creations of $\ell$-component during a random hypergraph process tends to 1 as
$\ell$ and $b$ tend to $\infty$ with the total number of vertices $n$ such that
$\ell = o(\sqrt[3]{\frac{n}{b}})$. Under the same conditions, we also show that
the expected number of vertices that ever belong to an $\ell$-component is
approximately $12^{1/3} (b-1)^{1/3} \ell^{1/3} n^{2/3}$. As an immediate
consequence, it follows that with high probability the largest $\ell$-component
during the process is of size $O((b-1)^{1/3} \ell^{1/3} n^{2/3})$. Our results
give insight about the size of giant components inside the phase transition of
random hypergraphs.


title: Circle Formation of Weak Mobile Robots

abstract:
  In this paper we prove the conjecture of D\'{e}fago & Konagaya. Furthermore,
we describe a deterministic protocol for forming a regular n-gon in finite
time.


title:
On Some Peculiarities of Dynamic Switch between Component
  Implementations in an Autonomic Computing System

abstract:
  Behavior of the delta algorithm of autonomic switch between two component
implementations is considered on several examples of a client-server systems
involving, in particular, periodic change of intensities of requests for the
component. It is shown that in the cases of some specific combinations of
elementary requests costs, the number of clients in the system, the number of
requests per unit of time, and the cost of switch between the implementations,
the algorithm may reveal behavior that is rather far from the desired. A
sufficient criterion of a success of the algorithm is proposed based on the
analysis of the accumulated implementations costs difference as a function of
time. Suggestions are pointed out of practical evaluation of the algorithm
functioning regarding the observations made in this paper.


title:
Get out the vote: Determining support or opposition from Congressional
  floor-debate transcripts

abstract:
  We investigate whether one can determine from the transcripts of U.S.
Congressional floor debates whether the speeches represent support of or
opposition to proposed legislation. To address this problem, we exploit the
fact that these speeches occur as part of a discussion; this allows us to use
sources of information regarding relationships between discourse segments, such
as whether a given utterance indicates agreement with the opinion expressed by
another. We find that the incorporation of such information yields substantial
improvements over classifying speeches in isolation.


title: Prioritizing Software Inspection Results using Static Profiling

abstract:
  Static software checking tools are useful as an additional automated software
inspection step that can easily be integrated in the development cycle and
assist in creating secure, reliable and high quality code. However, an often
quoted disadvantage of these tools is that they generate an overly large number
of warnings, including many false positives due to the approximate analysis
techniques. This information overload effectively limits their usefulness.
  In this paper we present ELAN, a technique that helps the user prioritize the
information generated by a software inspection tool, based on a demand-driven
computation of the likelihood that execution reaches the locations for which
warnings are reported. This analysis is orthogonal to other prioritization
techniques known from literature, such as severity levels and statistical
analysis to reduce false positives. We evaluate feasibility of our technique
using a number of case studies and assess the quality of our predictions by
comparing them to actual values obtained by dynamic profiling.


title: How to Find Good Finite-Length Codes: From Art Towards Science

abstract:
  We explain how to optimize finite-length LDPC codes for transmission over the
binary erasure channel. Our approach relies on an analytic approximation of the
erasure probability. This is in turn based on a finite-length scaling result to
model large scale erasures and a union bound involving minimal stopping sets to
take into account small error events. We show that the performances of
optimized ensembles as observed in simulations are well described by our
approximation. Although we only address the case of transmission over the
binary erasure channel, our method should be applicable to a more general
setting.


title: Decomposable Theories

abstract:
  We present in this paper a general algorithm for solving first-order formulas
in particular theories called "decomposable theories". First of all, using
special quantifiers, we give a formal characterization of decomposable theories
and show some of their properties. Then, we present a general algorithm for
solving first-order formulas in any decomposable theory "T". The algorithm is
given in the form of five rewriting rules. It transforms a first-order formula
"P", which can possibly contain free variables, into a conjunction "Q" of
solved formulas easily transformable into a Boolean combination of
existentially quantified conjunctions of atomic formulas. In particular, if "P"
has no free variables then "Q" is either the formula "true" or "false". The
correctness of our algorithm proves the completeness of the decomposable
theories.
  Finally, we show that the theory "Tr" of finite or infinite trees is a
decomposable theory and give some benchmarks realized by an implementation of
our algorithm, solving formulas on two-partner games in "Tr" with more than 160
nested alternated quantifiers.


title: Generalized h-index for Disclosing Latent Facts in Citation Networks

abstract:
  What is the value of a scientist and its impact upon the scientific thinking?
How can we measure the prestige of a journal or of a conference? The evaluation
of the scientific work of a scientist and the estimation of the quality of a
journal or conference has long attracted significant interest, due to the
benefits from obtaining an unbiased and fair criterion. Although it appears to
be simple, defining a quality metric is not an easy task. To overcome the
disadvantages of the present metrics used for ranking scientists and journals,
J.E. Hirsch proposed a pioneering metric, the now famous h-index. In this
article, we demonstrate several inefficiencies of this index and develop a pair
of generalizations and effective variants of it to deal with scientist ranking
and with publication forum ranking. The new citation indices are able to
disclose trendsetters in scientific research, as well as researchers that
constantly shape their field with their influential work, no matter how old
they are. We exhibit the effectiveness and the benefits of the new indices to
unfold the full potential of the h-index, with extensive experimental results
obtained from DBLP, a widely known on-line digital library.


title: Competing with stationary prediction strategies

abstract:
  In this paper we introduce the class of stationary prediction strategies and
construct a prediction algorithm that asymptotically performs as well as the
best continuous stationary strategy. We make mild compactness assumptions but
no stochastic assumptions about the environment. In particular, no assumption
of stationarity is made about the environment, and the stationarity of the
considered strategies only means that they do not depend explicitly on time; we
argue that it is natural to consider only stationary strategies even for highly
non-stationary environments.


title: Computation of the Weight Distribution of CRC Codes

abstract:
  In this article, we illustrate an algorithm for the computation of the weight
distribution of CRC codes. The recursive structure of CRC codes will give us an
iterative way to compute the weight distribution of their dual codes starting
from just some ``representative'' words. Thanks to MacWilliams Theorem, the
computation of the weight distribution of dual codes can be easily brought back
to that of CRC codes. This algorithm is a good alternative to the standard
algorithm that involves listing every word of the code.


title:
The B-Exponential Map: A Generalization of the Logistic Map, and Its
  Applications In Generating Pseudo-random Numbers

abstract:
  A 1-dimensional generalization of the well known Logistic Map is proposed.
The proposed family of maps is referred to as the B-Exponential Map. The
dynamics of this map are analyzed and found to have interesting properties. In
particular, the B-Exponential Map exhibits robust chaos for all real values of
the parameter B >= e^(-4). We then propose a pseudo-random number generator
based on the B-Exponential Map by chaotically hopping between different
trajectories for different values of B. We call this BEACH (B-Exponential
All-Chaotic Map Hopping) pseudo-random number generator. BEACH successfully
passes stringent statistical randomness tests such as ENT, NIST and Diehard. An
implementation of BEACH is also outlined.


title: Citation as a Representation Process

abstract:
  The presented work proposes a novel approach to model the citation rate. The
paper begins with a brief introduction into informetrics studies and highlights
drawbacks of the contemporary approaches to modeling the citation process as a
product of social interactions. An alternative modeling framework based on
results obtained in cognitive psychology is then introduced and applied in an
experiment to investigate properties of the citation process, as they are
revealed by a large collection of citation statistics. Major research findings
are discussed, and a summary is given.


title: Islands for SAT

abstract:
  In this note we introduce the notion of islands for restricting local search.
We show how we can construct islands for CNF SAT problems, and how much search
space can be eliminated by restricting search to the island.


title: Effect of Interface Style in Peer Review Comments for UML Designs

abstract:
  This paper presents our evaluation of using a Tablet-PC to provide
peer-review comments in the first year Computer Science course. Our exploration
consisted of an evaluation of how students write comments on other students'
assignments using three different methods: pen and paper, a Tablet-PC, and a
desktop computer. Our ultimate goal is to explore the effect that interface
style (Tablet vs. Desktop) has on the quality and quantity of the comments
provided.


title: Counting good truth assignments of random k-SAT formulae

abstract:
  We present a deterministic approximation algorithm to compute logarithm of
the number of `good' truth assignments for a random k-satisfiability (k-SAT)
formula in polynomial time (by `good' we mean that violate a small fraction of
clauses). The relative error is bounded above by an arbitrarily small constant
epsilon with high probability as long as the clause density (ratio of clauses
to variables) alpha<alpha_{u}(k) = 2k^{-1}\log k(1+o(1)). The algorithm is
based on computation of marginal distribution via belief propagation and use of
an interpolation procedure. This scheme substitutes the traditional one based
on approximation of marginal probabilities via MCMC, in conjunction with
self-reduction, which is not easy to extend to the present problem.
  We derive 2k^{-1}\log k (1+o(1)) as threshold for uniqueness of the Gibbs
distribution on satisfying assignment of random infinite tree k-SAT formulae to
establish our results, which is of interest in its own right.


title: On Construction of the (24,12,8) Golay Codes

abstract:
  Two product array codes are used to construct the (24, 12, 8) binary Golay
code through the direct sum operation. This construction provides a systematic
way to find proper (8, 4, 4) linear block component codes for generating the
Golay code, and it generates and extends previously existing methods that use a
similar construction framework. The code constructed is simple to decode.


title: On entropy for mixtures of discrete and continuous variables

abstract:
  Let $X$ be a discrete random variable with support $S$ and $f : S \to
S^\prime$ be a bijection. Then it is well-known that the entropy of $X$ is the
same as the entropy of $f(X)$. This entropy preservation property has been
well-utilized to establish non-trivial properties of discrete stochastic
processes, e.g. queuing process \cite{prg03}. Entropy as well as entropy
preservation is well-defined only in the context of purely discrete or
continuous random variables. However for a mixture of discrete and continuous
random variables, which arise in many interesting situations, the notions of
entropy and entropy preservation have not been well understood.
  In this paper, we extend the notion of entropy in a natural manner for a
mixed-pair random variable, a pair of random variables with one discrete and
the other continuous. Our extensions are consistent with the existing
definitions of entropy in the sense that there exist natural injections from
discrete or continuous random variables into mixed-pair random variables such
that their entropy remains the same. This extension of entropy allows us to
obtain sufficient conditions for entropy preservation in mixtures of discrete
and continuous random variables under bijections.
  The extended definition of entropy leads to an entropy rate for continuous
time Markov chains. As an application, we recover a known probabilistic result
related to Poisson process. We strongly believe that the frame-work developed
in this paper can be useful in establishing probabilistic properties of complex
processes, such as load balancing systems, queuing network, caching algorithms.


title: Capacity of Cooperative Fusion in the Presence of Byzantine Sensors

abstract:
  The problem of cooperative fusion in the presence of Byzantine sensors is
considered. An information theoretic formulation is used to characterize the
Shannon capacity of sensor fusion. It is shown that when less than half of the
sensors are Byzantine, the effect of Byzantine attack can be entirely
mitigated, and the fusion capacity is identical to that when all sensors are
honest. But when at least half of the sensors are Byzantine, they can
completely defeat the sensor fusion so that no information can be transmitted
reliably. A capacity achieving transmit-then-verify strategy is proposed for
the case that less than half of the sensors are Byzantine, and its error
probability and coding rate is analyzed by using a Markov decision process
modeling of the transmission protocol.


title:
Fault-Tolerant Real-Time Streaming with FEC thanks to Capillary
  Multi-Path Routing

abstract:
  Erasure resilient FEC codes in off-line packetized streaming rely on time
diversity. This requires unrestricted buffering time at the receiver. In
real-time streaming the playback buffering time must be very short. Path
diversity is an orthogonal strategy. However, the large number of long paths
increases the number of underlying links and consecutively the overall link
failure rate. This may increase the overall requirement in redundant FEC
packets for combating the link failures. We introduce the Redundancy Overall
Requirement (ROR) metric, a routing coefficient specifying the total number of
FEC packets required for compensation of all underlying link failures. We
present a capillary routing algorithm for constructing layer by layer steadily
diversifying multi-path routing patterns. By measuring the ROR coefficients of
a dozen of routing layers on hundreds of network samples, we show that the
number of required FEC packets decreases substantially when the path diversity
is increased by the capillary routing construction algorithm.


title: Complex Lattice Reduction Algorithm for Low-Complexity MIMO Detection

abstract:
  Recently, lattice-reduction-aided detectors have been proposed for
multiple-input multiple-output (MIMO) systems to give performance with full
diversity like maximum likelihood receiver, and yet with complexity similar to
linear receivers. However, these lattice-reduction-aided detectors are based on
the traditional LLL reduction algorithm that was originally introduced for
reducing real lattice bases, in spite of the fact that the channel matrices are
inherently complex-valued. In this paper, we introduce the complex LLL
algorithm for direct application to reduce the basis of a complex lattice which
is naturally defined by a complex-valued channel matrix. We prove that complex
LLL reduction-aided detection can also achieve full diversity. Our analysis
reveals that the new complex LLL algorithm can achieve a reduction in
complexity of nearly 50% over the traditional LLL algorithm, and this is
confirmed by simulation. It is noteworthy that the complex LLL algorithm
aforementioned has nearly the same bit-error-rate performance as the
traditional LLL algorithm.


title: Length-based cryptanalysis: The case of Thompson's Group

abstract:
  The length-based approach is a heuristic for solving randomly generated
equations in groups which possess a reasonably behaved length function. We
describe several improvements of the previously suggested length-based
algorithms, that make them applicable to Thompson's group with significant
success rates. In particular, this shows that the Shpilrain-Ushakov public key
cryptosystem based on Thompson's group is insecure, and suggests that no
practical public key cryptosystem based on this group can be secure.


title: New Model of Internet Topology Using k-shell Decomposition

abstract:
  We introduce and use k-shell decomposition to investigate the topology of the
Internet at the AS level. Our analysis separates the Internet into three
sub-components: (a) a nucleus which is a small (~100 nodes) very well connected
globally distributed subgraph; (b) a fractal sub-component that is able to
connect the bulk of the Internet without congesting the nucleus, with self
similar properties and critical exponents; and (c) dendrite-like structures,
usually isolated nodes that are connected to the rest of the network through
the nucleus only. This unique decomposition is robust, and provides insight
into the underlying structure of the Internet and its functional consequences.
Our approach is general and useful also when studying other complex networks.


title:
Syst\`{e}me de repr\'{e}sentation d'aide au besoin dans le domaine
  architectural

abstract:
  The image is a very important mean of communication in the field of
architectural who intervenes in the various phases of the design of a project.
It can be regarded as a tool of decision-making aid. The study of our research
aims at to see the contribution of the Economic Intelligence in the resolution
of a decisional problem of the various partners (Architect, Contractor,
Customer) in the architectural field, in order to make strategic decisions
within the framework of the realization or design of an architectural work. The
economic Intelligence allows the taking into account of the real needs for the
user-decision makers, so that their waiting are considered at the first stage
of a search for information and not in the final stage of the development of
the tool in the evaluation of this last.


title: Well quasi-orders and the shuffle closure of finite sets

abstract:
  Given a set I of word, the set of all words obtained by the shuffle of
(copies of) words of I is naturally provided with a partial order. In [FS05],
the authors have opened the problem of the characterization of the finite sets
I such that the order is a well quasi-order . In this paper we give an answer
in the case when I consists of a single word w.


title:
Mathematical Modelling of the Thermal Accumulation in Hot Water Solar
  Systems

abstract:
  Mathematical modelling and defining useful recommendations for construction
and regimes of exploitation for hot water solar installation with thermal
stratification is the main purpose of this work. A special experimental solar
module for hot water was build and equipped with sufficient measure apparatus.
The main concept of investigation is to optimise the stratified regime of
thermal accumulation and constructive parameters of heat exchange equipment
(heat serpentine in tank). Accumulation and heat exchange processes were
investigated by theoretical end experimental means. Special mathematical model
was composed to simulate the energy transfer in stratified tank. Computer
program was developed to solve mathematical equations for thermal accumulation
and energy exchange. Extensive numerical and experimental tests were carried
out. A good correspondence between theoretical and experimental data was
arrived. Keywords: Mathematical modelling, accumulation


title: About Norms and Causes

abstract:
  Knowing the norms of a domain is crucial, but there exist no repository of
norms. We propose a method to extract them from texts: texts generally do not
describe a norm, but rather how a state-of-affairs differs from it. Answers
concerning the cause of the state-of-affairs described often reveal the
implicit norm. We apply this idea to the domain of driving, and validate it by
designing algorithms that identify, in a text, the "basic" norms to which it
refers implicitly.


title:
Using Pseudo-Stochastic Rational Languages in Probabilistic Grammatical
  Inference

abstract:
  In probabilistic grammatical inference, a usual goal is to infer a good
approximation of an unknown distribution P called a stochastic language. The
estimate of P stands in some class of probabilistic models such as
probabilistic automata (PA). In this paper, we focus on probabilistic models
based on multiplicity automata (MA). The stochastic languages generated by MA
are called rational stochastic languages; they strictly include stochastic
languages generated by PA; they also admit a very concise canonical
representation. Despite the fact that this class is not recursively enumerable,
it is efficiently identifiable in the limit by using the algorithm DEES,
introduced by the authors in a previous paper. However, the identification is
not proper and before the convergence of the algorithm, DEES can produce MA
that do not define stochastic languages. Nevertheless, it is possible to use
these MA to define stochastic languages. We show that they belong to a broader
class of rational series, that we call pseudo-stochastic rational languages.
The aim of this paper is twofold. First we provide a theoretical study of
pseudo-stochastic rational languages, the languages output by DEES, showing for
example that this class is decidable within polynomial time. Second, we have
carried out a lot of experiments in order to compare DEES to classical
inference algorithms such as ALERGIA and MDI. They show that DEES outperforms
them in most cases.


title: Representing Knowledge about Norms

abstract:
  Norms are essential to extend inference: inferences based on norms are far
richer than those based on logical implications. In the recent decades, much
effort has been devoted to reason on a domain, once its norms are represented.
How to extract and express those norms has received far less attention.
Extraction is difficult: as the readers are supposed to know them, the norms of
a domain are seldom made explicit. For one thing, extracting norms requires a
language to represent them, and this is the topic of this paper. We apply this
language to represent norms in the domain of driving, and show that it is
adequate to reason on the causes of accidents, as described by car-crash
reports.


title:
Un filtre temporel cr\'edibiliste pour la reconnaissance d'actions
  humaines dans les vid\'eos

abstract:
  In the context of human action recognition in video sequences, a temporal
belief filter is presented. It allows to cope with human action disparity and
low quality videos. The whole system of action recognition is based on the
Transferable Belief Model (TBM) proposed by P. Smets. The TBM allows to
explicitly model the doubt between actions. Furthermore, the TBM emphasizes the
conflict which is exploited for action recognition. The filtering performance
is assessed on real video sequences acquired by a moving camera and under
several unknown view angles.


Using Answer Set Programming in an Inference-Based approach to Natural
  Language Semantics


title:
Superregular Matrices and the Construction of Convolutional Codes having
  a Maximum Distance Profile

abstract:
  Superregular matrices are a class of lower triangular Toeplitz matrices that
arise in the context of constructing convolutional codes having a maximum
distance profile. These matrices are characterized by the property that no
submatrix has a zero determinant unless it is trivially zero due to the lower
triangular structure. In this paper, we discuss how superregular matrices may
be used to construct codes having a maximum distance profile. We also introduce
group actions that preserve the superregularity property and present an upper
bound on the minimum size a finite field must have in order that a superregular
matrix of a given size can exist over that field.


title: Neural Networks with Complex and Quaternion Inputs

abstract:
  This article investigates Kak neural networks, which can be instantaneously
trained, for complex and quaternion inputs. The performance of the basic
algorithm has been analyzed and shown how it provides a plausible model of
human perception and understanding of images. The motivation for studying
quaternion inputs is their use in representing spatial rotations that find
applications in computer graphics, robotics, global navigation, computer vision
and the spatial orientation of instruments. The problem of efficient mapping of
data in quaternion neural networks is examined. Some problems that need to be
addressed before quaternion neural networks find applications are identified.


title:
Finite element method for thermal analysis of concentrating solar
  receivers

abstract:
  Application of finite element method and heat conductivity transfer model for
calculation of temperature distribution in receiver for dish-Stirling
concentrating solar system is described. The method yields discretized
equations that are entirely local to the elements and provides complete
geometric flexibility. A computer program solving the finite element method
problem is created and great number of numerical experiments is carried out.
Illustrative numerical results are given for an array of triangular elements in
receiver for dish-Stirling system.


title: Representing graphs as the intersection of axis-parallel cubes

abstract:
  A unit cube in $k$ dimensional space (or \emph{$k$-cube} in short) is defined
as the Cartesian product $R_1\times R_2\times...\times R_k$ where $R_i$(for
$1\leq i\leq k$) is a closed interval of the form $[a_i,a_i+1]$ on the real
line. A $k$-cube representation of a graph $G$ is a mapping of the vertices of
$G$ to $k$-cubes such that two vertices in $G$ are adjacent if and only if
their corresponding $k$-cubes have a non-empty intersection. The
\emph{cubicity} of $G$, denoted as $\cubi(G)$, is the minimum $k$ such that $G$
has a $k$-cube representation. Roberts \cite{Roberts} showed that for any graph
$G$ on $n$ vertices, $\cubi(G)\leq 2n/3$. Many NP-complete graph problems have
polynomial time deterministic algorithms or have good approximation ratios in
graphs of low cubicity. In most of these algorithms, computing a low
dimensional cube representation of the given graph is usually the first step.
  We present an efficient algorithm to compute the $k$-cube representation of
$G$ with maximum degree $\Delta$ in $O(\Delta \ln b)$ dimensions where $b$ is
the bandwidth of $G$. Bandwidth of $G$ is at most $n$ and can be much lower.
The algorithm takes as input a bandwidth ordering of the vertices in $G$.
Though computing the bandwidth ordering of vertices for a graph is NP-hard,
there are heuristics that perform very well in practice. Even theoretically,
there is an $O(\log^4 n)$ approximation algorithm for computing the bandwidth
ordering of a graph using which our algorithm can produce a $k$-cube
representation of any given graph in $k=O(\Delta(\ln b + \ln\ln n))$
dimensions. Both the bounds on cubicity are shown to be tight upto a factor of
$O(\log\log n)$.


title: An Elegant Argument that P is not NP

abstract:
  In this note, we present an elegant argument that P is not NP by
demonstrating that the Meet-in-the-Middle algorithm must have the fastest
running-time of all deterministic and exact algorithms which solve the
SUBSET-SUM problem on a classical computer.


title: Upright-Quad Drawing of st-Planar Learning Spaces

abstract:
  We consider graph drawing algorithms for learning spaces, a type of
st-oriented partial cube derived from antimatroids and used to model states of
knowledge of students. We show how to draw any st-planar learning space so all
internal faces are convex quadrilaterals with the bottom side horizontal and
the left side vertical, with one minimal and one maximal vertex. Conversely,
every such drawing represents an st-planar learning space. We also describe
connections between these graphs and arrangements of translates of a quadrant.


title: Gallager's Exponent for MIMO Channels: A Reliability-Rate Tradeoff

abstract:
  In this paper, we derive Gallager's random coding error exponent for
multiple-input multiple-output (MIMO) channels, assuming no channel-state
information (CSI) at the transmitter and perfect CSI at the receiver. This
measure gives insight into a fundamental tradeoff between the communication
reliability and information rate of MIMO channels, enabling to determine the
required codeword length to achieve a prescribed error probability at a given
rate below the channel capacity. We quantify the effects of the number of
antennas, channel coherence time, and spatial fading correlation on the MIMO
exponent. In addition, general formulae for the ergodic capacity and the cutoff
rate in the presence of spatial correlation are deduced from the exponent
expressions. These formulae are applicable to arbitrary structures of transmit
and receive correlation, encompassing all the previously known results as
special cases of our expressions.


title:
Logical settings for concept learning from incomplete examples in First
  Order Logic

abstract:
  We investigate here concept learning from incomplete examples. Our first
purpose is to discuss to what extent logical learning settings have to be
modified in order to cope with data incompleteness. More precisely we are
interested in extending the learning from interpretations setting introduced by
L. De Raedt that extends to relational representations the classical
propositional (or attribute-value) concept learning from examples framework. We
are inspired here by ideas presented by H. Hirsh in a work extending the
Version space inductive paradigm to incomplete data. H. Hirsh proposes to
slightly modify the notion of solution when dealing with incomplete examples: a
solution has to be a hypothesis compatible with all pieces of information
concerning the examples. We identify two main classes of incompleteness. First,
uncertainty deals with our state of knowledge concerning an example. Second,
generalization (or abstraction) deals with what part of the description of the
example is sufficient for the learning purpose. These two main sources of
incompleteness can be mixed up when only part of the useful information is
known. We discuss a general learning setting, referred to as "learning from
possibilities" that formalizes these ideas, then we present a more specific
learning setting, referred to as "assumption-based learning" that cope with
examples which uncertainty can be reduced when considering contextual
information outside of the proper description of the examples. Assumption-based
learning is illustrated on a recent work concerning the prediction of a
consensus secondary structure common to a set of RNA sequences.


title:
Dynamic Packet Aggregation to Solve Performance Anomaly in 802.11
  Wireless Networks

abstract:
  In the widely used 802.11 standard, the so called performance anomaly is a
well known issue. Several works have tried to solve this problem by introducing
mechanisms such as packet fragmentation, backoff adaptation, or packet
aggregation during a fixed time interval. In this paper, we propose a novel
approach solving the performance anomaly problem by packet aggregation using a
dynamic time interval, which depends on the busy time of the wireless medium.
Our solution differs from other proposition in the literature because of this
dynamic time interval, which allows increasing fairness, reactivity, and in
some cases efficiency. In this article, we emphasize the performance evaluation
of our proposal.


title: List decoding of noisy Reed-Muller-like codes

abstract:
  First- and second-order Reed-Muller (RM(1) and RM(2), respectively) codes are
two fundamental error-correcting codes which arise in communication as well as
in probabilistically-checkable proofs and learning. In this paper, we take the
first steps toward extending the quick randomized decoding tools of RM(1) into
the realm of quadratic binary and, equivalently, Z_4 codes. Our main
algorithmic result is an extension of the RM(1) techniques from Goldreich-Levin
and Kushilevitz-Mansour algorithms to the Hankel code, a code between RM(1) and
RM(2). That is, given signal s of length N, we find a list that is a superset
of all Hankel codewords phi with dot product to s at least (1/sqrt(k)) times
the norm of s, in time polynomial in k and log(N). We also give a new and
simple formulation of a known Kerdock code as a subcode of the Hankel code. As
a corollary, we can list-decode Kerdock, too. Also, we get a quick algorithm
for finding a sparse Kerdock approximation. That is, for k small compared with
1/sqrt{N} and for epsilon > 0, we find, in time polynomial in (k
log(N)/epsilon), a k-Kerdock-term approximation s~ to s with Euclidean error at
most the factor (1+epsilon+O(k^2/sqrt{N})) times that of the best such
approximation.


title: Degrees of Freedom Region for the MIMO X Channel

abstract:
  We provide achievability as well as converse results for the degrees of
freedom region of a MIMO $X$ channel, i.e., a system with two transmitters, two
receivers, each equipped with multiple antennas, where independent messages
need to be conveyed over fixed channels from each transmitter to each receiver.
With M=1 antennas at each node, we find that the total (sum rate) degrees of
freedom are bounded above and below as $1 \leq\eta_X^\star \leq {4/3}$. If
$M>1$ and channel matrices are non-degenerate then the precise degrees of
freedom $\eta_X^\star = {4/3}M$. Simple zero forcing without dirty paper
encoding or successive decoding, suffices to achieve the ${4/3}M$ degrees of
freedom. With equal number of antennas at all nodes, we explore the increase in
degrees of freedom when some of the messages are made available to a
transmitter or receiver in the manner of cognitive radio. With a cognitive
transmitter we show that the number of degrees of freedom $\eta = {3/2}M$ (for
$M>1$) on the MIMO $X$ channel. The same degrees of freedom are obtained on the
MIMO $X$ channel with a cognitive receiver as well. In contrast to the $X$
channel result, we show that for the MIMO \emph{interference} channel, the
degrees of freedom are not increased even if both the transmitter and the
receiver of one user know the other user's message. However, the interference
channel can achieve the full $2M$ degrees of freedom if \emph{each} user has
either a cognitive transmitter or a cognitive receiver. Lastly, if the channels
vary with time/frequency then the $X$ channel with single antennas $(M=1)$ at
all nodes has exactly 4/3 degrees of freedom with no shared messages and
exactly 3/2 degrees of freedom with a cognitive transmitter or a cognitive
receiver.


title: New Upper Bounds on The Approximability of 3D Strip Packing

abstract:
  In this paper, we study the 3D strip packing problem in which we are given a
list of 3-dimensional boxes and required to pack all of them into a
3-dimensional strip with length 1 and width 1 and unlimited height to minimize
the height used. Our results are below: i) we give an approximation algorithm
with asymptotic worst-case ratio 1.69103, which improves the previous best
bound of $2+\epsilon$ by Jansen and Solis-Oba of SODA 2006; ii) we also present
an asymptotic PTAS for the case in which all items have {\em square} bases.


title: Deriving Escape Analysis by Abstract Interpretation: Proofs of results

abstract:
  Escape analysis of object-oriented languages approximates the set of objects
which do not escape from a given context. If we take a method as context, the
non-escaping objects can be allocated on its activation stack; if we take a
thread, Java synchronisation locks on such objects are not needed. In this
paper, we formalise a basic escape domain e as an abstract interpretation of
concrete states, which we then refine into an abstract domain er which is more
concrete than e and, hence, leads to a more precise escape analysis than e. We
provide optimality results for both e and er, in the form of Galois insertions
from the concrete to the abstract domains and of optimal abstract operations.
The Galois insertion property is obtained by restricting the abstract domains
to those elements which do not contain garbage, by using an abstract garbage
collector. Our implementation of er is hence an implementation of a formally
correct escape analyser, able to detect the stack allocatable creation points
of Java (bytecode) applications.
  This report contains the proofs of results of a paper with the same title and
authors and to be published in the Journal "Higher-Order Symbolic Computation".


title:
Multiaccess Channels with State Known to Some Encoders and Independent
  Messages

abstract:
  We consider a state-dependent multiaccess channel (MAC) with state
non-causally known to some encoders. We derive an inner bound for the capacity
region in the general discrete memoryless case and specialize to a binary
noiseless case. In the case of maximum entropy channel state, we obtain the
capacity region for binary noiseless MAC with one informed encoder by deriving
a non-trivial outer bound for this case. For a Gaussian state-dependent MAC
with one encoder being informed of the channel state, we present an inner bound
by applying a slightly generalized dirty paper coding (GDPC) at the informed
encoder that allows for partial state cancellation, and a trivial outer bound
by providing channel state to the decoder also. The uninformed encoders benefit
from the state cancellation in terms of achievable rates, however, appears that
GDPC cannot completely eliminate the effect of the channel state on the
achievable rate region, in contrast to the case of all encoders being informed.
In the case of infinite state variance, we analyze how the uninformed encoder
benefits from the informed encoder's actions using the inner bound and also
provide a non-trivial outer bound for this case which is better than the
trivial outer bound.


title: Ideas by Statistical Mechanics (ISM)

abstract:
  Ideas by Statistical Mechanics (ISM) is a generic program to model evolution
and propagation of ideas/patterns throughout populations subjected to
endogenous and exogenous interactions. The program is based on the author's
work in Statistical Mechanics of Neocortical Interactions (SMNI), and uses the
author's Adaptive Simulated Annealing (ASA) code for optimizations of training
sets, as well as for importance-sampling to apply the author's copula financial
risk-management codes, Trading in Risk Dimensions (TRD), for assessments of
risk and uncertainty. This product can be used for decision support for
projects ranging from diplomatic, information, military, and economic (DIME)
factors of propagation/evolution of ideas, to commercial sales, trading
indicators across sectors of financial markets, advertising and political
campaigns, etc. A statistical mechanical model of neocortical interactions,
developed by the author and tested successfully in describing short-term memory
and EEG indicators, is the proposed model. Parameters with a given subset of
macrocolumns will be fit using ASA to patterns representing ideas. Parameters
of external and inter-regional interactions will be determined that promote or
inhibit the spread of these ideas. Tools of financial risk management,
developed by the author to process correlated multivariate systems with
differing non-Gaussian distributions using modern copula analysis,
importance-sampled using ASA, will enable bona fide correlations and
uncertainties of success and failure to be calculated. Marginal distributions
will be evolved to determine their expected duration and stability using
algorithms developed by the author, i.e., PATHTREE and PATHINT codes.


title:
Reducing the Computation of Linear Complexities of Periodic Sequences
  over $GF(p^m)$

abstract:
  The linear complexity of a periodic sequence over $GF(p^m)$ plays an
important role in cryptography and communication [12]. In this correspondence,
we prove a result which reduces the computation of the linear complexity and
minimal connection polynomial of a period $un$ sequence over $GF(p^m)$ to the
computation of the linear complexities and minimal connection polynomials of
$u$ period $n$ sequences. The conditions $u|p^m-1$ and
  $\gcd(n,p^m-1)=1$ are required for the result to hold. Some applications of
this reduction in fast algorithms to determine the linear complexities and
minimal connection polynomials of sequences over $GF(p^m)$ are presented.


title:
Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric,
  Diagonally Dominant Linear Systems

abstract:
  We present a randomized algorithm that, on input a symmetric, weakly
diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b,
produces a y such that $\norm{y - \pinv{A} b}_{A} \leq \epsilon \norm{\pinv{A}
b}_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon)),$ for some constant
c. By applying this algorithm inside the inverse power method, we compute
approximate Fiedler vectors in a similar amount of time. The algorithm applies
subgraph preconditioners in a recursive fashion. These preconditioners improve
upon the subgraph preconditioners first introduced by Vaidya (1990).
  For any symmetric, weakly diagonally-dominant matrix A with non-positive
off-diagonal entries and $k \geq 1$, we construct in time $O (m \log^{c} n)$ a
preconditioner B of A with at most $2 (n - 1) + O ((m/k) \log^{39} n)$ nonzero
off-diagonal entries such that the finite generalized condition number
$\kappa_{f} (A,B)$ is at most k, for some other constant c.
  In the special case when the nonzero structure of the matrix is planar the
corresponding linear system solver runs in expected time $ O (n \log^{2} n + n
\log n \ \log \log n \ \log (1/\epsilon))$.
  We hope that our introduction of algorithms of low asymptotic complexity will
lead to the development of algorithms that are also fast in practice.


title:
The Complexity of Quantified Constraint Satisfaction: Collapsibility,
  Sink Algebras, and the Three-Element Case

abstract:
  The constraint satisfaction probem (CSP) is a well-acknowledged framework in
which many combinatorial search problems can be naturally formulated. The CSP
may be viewed as the problem of deciding the truth of a logical sentence
consisting of a conjunction of constraints, in front of which all variables are
existentially quantified. The quantified constraint satisfaction problem (QCSP)
is the generalization of the CSP where universal quantification is permitted in
addition to existential quantification. The general intractability of these
problems has motivated research studying the complexity of these problems under
a restricted constraint language, which is a set of relations that can be used
to express constraints.
  This paper introduces collapsibility, a technique for deriving positive
complexity results on the QCSP. In particular, this technique allows one to
show that, for a particular constraint language, the QCSP reduces to the CSP.
We show that collapsibility applies to three known tractable cases of the QCSP
that were originally studied using disparate proof techniques in different
decades: Quantified 2-SAT (Aspvall, Plass, and Tarjan 1979), Quantified
Horn-SAT (Karpinski, Kleine B\"{u}ning, and Schmitt 1987), and Quantified
Affine-SAT (Creignou, Khanna, and Sudan 2001). This reconciles and reveals
common structure among these cases, which are describable by constraint
languages over a two-element domain. In addition to unifying these known
tractable cases, we study constraint languages over domains of larger size.


title: Linear Predictive Coding as an Estimator of Volatility

abstract:
  In this paper, we present a method of estimating the volatility of a signal
that displays stochastic noise (such as a risky asset traded on an open market)
utilizing Linear Predictive Coding. The main purpose is to associate volatility
with a series of statistical properties that can lead us, through further
investigation, toward a better understanding of structural volatility as well
as to improve the quality of our current estimates.


title: Properties of subspace subcodes of optimum codes in rank metric

abstract:
  Maximum rank distance codes denoted MRD-codes are the equivalent in rank
metric of MDS-codes. Given any integer $q$ power of a prime and any integer $n$
there is a family of MRD-codes of length $n$ over $\FF{q^n}$ having
polynomial-time decoding algorithms. These codes can be seen as the analogs of
Reed-Solomon codes (hereafter denoted RS-codes) for rank metric. In this paper
their subspace subcodes are characterized. It is shown that hey are equivalent
to MRD-codes constructed in the same way but with smaller parameters. A
specific polynomial-time decoding algorithm is designed. Moreover, it is shown
that the direct sum of subspace subcodes is equivalent to the direct product of
MRD-codes with smaller parameters. This implies that the decoding procedure can
correct errors of higher rank than the error-correcting capability. Finally it
is shown that, for given parameters, subfield subcodes are completely
characterized by elements of the general linear group ${GL}_n(\FF{q})$ of
non-singular $q$-ary matrices of size $n$.


title: Complexity and Applications of Edge-Induced Vertex-Cuts

abstract:
  Motivated by hypergraph decomposition algorithms, we introduce the notion of
edge-induced vertex-cuts and compare it with the well-known notions of
edge-cuts and vertex-cuts. We investigate the complexity of computing minimum
edge-induced vertex-cuts and demonstrate the usefulness of our notion by
applications in network reliability and constraint satisfaction.


title: A Theory of Probabilistic Boosting, Decision Trees and Matryoshki

abstract:
  We present a theory of boosting probabilistic classifiers. We place ourselves
in the situation of a user who only provides a stopping parameter and a
probabilistic weak learner/classifier and compare three types of boosting
algorithms: probabilistic Adaboost, decision tree, and tree of trees of ... of
trees, which we call matryoshka. "Nested tree," "embedded tree" and "recursive
tree" are also appropriate names for this algorithm, which is one of our
contributions. Our other contribution is the theoretical analysis of the
algorithms, in which we give training error bounds. This analysis suggests that
the matryoshka leverages probabilistic weak classifiers more efficiently than
simple decision trees.


title:
UCLog+ : A Security Data Management System for Correlating Alerts,
  Incidents, and Raw Data From Remote Logs

abstract:
  Source data for computer network security analysis takes different forms
(alerts, incidents, logs) and each source may be voluminous. Due to the
challenge this presents for data management, this has often lead to security
stovepipe operations which focus primarily on a small number of data sources
for analysis with little or no automated correlation between data sources
(although correlation may be done manually). We seek to address this systemic
problem.
  In previous work we developed a unified correlated logging system (UCLog)
that automatically processes alerts from different devices. We take this work
one step further by presenting the architecture and applications of UCLog+
which adds the new capability to correlate between alerts and incidents and raw
data located on remote logs. UCLog+ can be used for forensic analysis including
queries and report generation but more importantly it can be used for
near-real-time situational awareness of attack patterns in progress. The
system, implemented with open source tools, can also be a repository for secure
information sharing by different organizations.


title: Improving convergence of Belief Propagation decoding

abstract:
  The decoding of Low-Density Parity-Check codes by the Belief Propagation (BP)
algorithm is revisited. We check the iterative algorithm for its convergence to
a codeword (termination), we run Monte Carlo simulations to find the
probability distribution function of the termination time, n_it. Tested on an
example [155, 64, 20] code, this termination curve shows a maximum and an
extended algebraic tail at the highest values of n_it. Aiming to reduce the
tail of the termination curve we consider a family of iterative algorithms
modifying the standard BP by means of a simple relaxation. The relaxation
parameter controls the convergence of the modified BP algorithm to a minimum of
the Bethe free energy. The improvement is experimentally demonstrated for
Additive-White-Gaussian-Noise channel in some range of the signal-to-noise
ratios. We also discuss the trade-off between the relaxation parameter of the
improved iterative scheme and the number of iterations.


title: Trees with Convex Faces and Optimal Angles

abstract:
  We consider drawings of trees in which all edges incident to leaves can be
extended to infinite rays without crossing, partitioning the plane into
infinite convex polygons. Among all such drawings we seek the one maximizing
the angular resolution of the drawing. We find linear time algorithms for
solving this problem, both for plane trees and for trees without a fixed
embedding. In any such drawing, the edge lengths may be set independently of
the angles, without crossing; we describe multiple strategies for setting these
lengths.


title: Revising Type-2 Computation and Degrees of Discontinuity

abstract:
  By the sometimes so-called MAIN THEOREM of Recursive Analysis, every
computable real function is necessarily continuous. Weihrauch and Zheng
(TCS'2000), Brattka (MLQ'2005), and Ziegler (ToCS'2006) have considered
different relaxed notions of computability to cover also discontinuous
functions. The present work compares and unifies these approaches. This is
based on the concept of the JUMP of a representation: both a TTE-counterpart to
the well known recursion-theoretic jump on Kleene's Arithmetical Hierarchy of
hypercomputation: and a formalization of revising computation in the sense of
Shoenfield.
  We also consider Markov and Banach/Mazur oracle-computation of discontinuous
fu nctions and characterize the computational power of Type-2 nondeterminism to
coincide with the first level of the Analytical Hierarchy.


title: Polynomial-time algorithm for vertex k-colorability of P_5-free graphs

abstract:
  We give the first polynomial-time algorithm for coloring vertices of P_5-free
graphs with k colors. This settles an open problem and generalizes several
previously known results.


title: Program Spectra Analysis in Embedded Software: A Case Study

abstract:
  Because of constraints imposed by the market, embedded software in consumer
electronics is almost inevitably shipped with faults and the goal is just to
reduce the inherent unreliability to an acceptable level before a product has
to be released. Automatic fault diagnosis is a valuable tool to capture
software faults without extra effort spent on testing. Apart from a debugging
aid at design and integration time, fault diagnosis can help analyzing problems
during operation, which allows for more accurate system recovery. In this paper
we discuss perspectives and limitations for applying a particular fault
diagnosis technique, namely the analysis of program spectra, in the area of
embedded software in consumer electronics devices. We illustrate these by our
first experience with a test case from industry.