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

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


title: Matrix Games, Linear Programming, and Linear Approximation

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


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

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


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

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


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

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


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

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


title: Cross-lingual keyword assignment

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


title: Nominal Logic Programming

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


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

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


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

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


title:
Geocoding multilingual texts: Recognition, disambiguation and
  visualisation

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


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

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


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

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


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

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


title: Coverage and Connectivity in Three-Dimensional Networks

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


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

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


title: A kernel method for canonical correlation analysis

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


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

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


title: Optimal power allocation for downlink cooperative cellular networks

abstract: This paper has been withdrawn by the author


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

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


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

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


title:
Asymptotic Spectral Distribution of Crosscorrelation Matrix in
  Asynchronous CDMA

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


title: On Intentional Attacks and Protections in Complex Communication Networks

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


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

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


title: Modern Statistics by Kriging

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


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

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


title: Recurrence relations and fast algorithms

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


title: Classifying extrema using intervals

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


title: k-Colorability of P5-free graphs

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


title: Non-photorealistic image rendering with a labyrinthine tiling

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


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

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


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

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


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

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


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

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


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

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


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

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


title: Using shifted conjugacy in braid-based cryptography

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


title: Analysis of Equality Relationships for Imperative Programs

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


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

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


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

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


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

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


title: Finite-State Dimension and Lossy Decompressors

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


title: Traveing Salesperson Problems for a double integrator

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


title: Reducing the Makespan in Hierarchical Reliable Multicast Tree

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


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

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


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

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


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

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


title: Using groups for investigating rewrite systems

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


title: Minimum-weight Cycle Covers and Their Approximability

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


title: On Verifying Complex Properties using Symbolic Shape Analysis

abstract:
  One of the main challenges in the verification of software systems is the
analysis of unbounded data structures with dynamic memory allocation, such as
linked data structures and arrays. We describe Bohne, a new analysis for
verifying data structures. Bohne verifies data structure operations and shows
that 1) the operations preserve data structure invariants and 2) the operations
satisfy their specifications expressed in terms of changes to the set of
objects stored in the data structure. During the analysis, Bohne infers loop
invariants in the form of disjunctions of universally quantified Boolean
combinations of formulas. To synthesize loop invariants of this form, Bohne
uses a combination of decision procedures for Monadic Second-Order Logic over
trees, SMT-LIB decision procedures (currently CVC Lite), and an automated
reasoner within the Isabelle interactive theorem prover. This architecture
shows that synthesized loop invariants can serve as a useful communication
mechanism between different decision procedures. Using Bohne, we have verified
operations on data structures such as linked lists with iterators and back
pointers, trees with and without parent pointers, two-level skip lists, array
data structures, and sorted lists. We have deployed Bohne in the Hob and Jahob
data structure analysis systems, enabling us to combine Bohne with analyses of
data structure clients and apply it in the context of larger programs. This
report describes the Bohne algorithm as well as techniques that Bohne uses to
reduce the ammount of annotations and the running time of the analysis.


title: Binomial multichannel algorithm

abstract:
  The binomial multichannel algorithm is proposed. Some its properties are
discussed.


title: Throughput Optimal Distributed Control of Stochastic Wireless Networks

abstract:
  The Maximum Differential Backlog (MDB) control policy of Tassiulas and
Ephremides has been shown to adaptively maximize the stable throughput of
multi-hop wireless networks with random traffic arrivals and queueing. The
practical implementation of the MDB policy in wireless networks with mutually
interfering links, however, requires the development of distributed
optimization algorithms. Within the context of CDMA-based multi-hop wireless
networks, we develop a set of node-based scaled gradient projection power
control algorithms which solves the MDB optimization problem in a distributed
manner using low communication overhead. As these algorithms require time to
converge to a neighborhood of the optimum, the optimal rates determined by the
MDB policy can only be found iteratively over time. For this, we show that the
iterative MDB policy with convergence time remains throughput optimal.


title: A multipurpose Hopf deformation of the Algebra of Feynman-like Diagrams

abstract:
  We construct a three parameter deformation of the Hopf algebra
$\mathbf{LDIAG}$. This new algebra is a true Hopf deformation which reduces to
$\mathbf{LDIAG}$ on one hand and to $\mathbf{MQSym}$ on the other, relating
$\mathbf{LDIAG}$ to other Hopf algebras of interest in contemporary physics.
Further, its product law reproduces that of the algebra of polyzeta functions.


title: Generalized Majority-Minority Operations are Tractable

abstract:
  Generalized majority-minority (GMM) operations are introduced as a common
generalization of near unanimity operations and Mal'tsev operations on finite
sets. We show that every instance of the constraint satisfaction problem (CSP),
where all constraint relations are invariant under a (fixed) GMM operation, is
solvable in polynomial time. This constitutes one of the largest tractable
cases of the CSP.


title: The recognizability of sets of graphs is a robust property

abstract:
  Once the set of finite graphs is equipped with an algebra structure (arising
from the definition of operations that generalize the concatenation of words),
one can define the notion of a recognizable set of graphs in terms of finite
congruences. Applications to the construction of efficient algorithms and to
the theory of context-free sets of graphs follow naturally. The class of
recognizable sets depends on the signature of graph operations. We consider
three signatures related respectively to Hyperedge Replacement (HR)
context-free graph grammars, to Vertex Replacement (VR) context-free graph
grammars, and to modular decompositions of graphs. We compare the corresponding
classes of recognizable sets. We show that they are robust in the sense that
many variants of each signature (where in particular operations are defined by
quantifier-free formulas, a quite flexible framework) yield the same notions of
recognizability. We prove that for graphs without large complete bipartite
subgraphs, HR-recognizability and VR-recognizability coincide. The same
combinatorial condition equates HR-context-free and VR-context-free sets of
graphs. Inasmuch as possible, results are formulated in the more general
framework of relational structures.


title: Algebraic recognizability of languages

abstract:
  Recognizable languages of finite words are part of every computer science
cursus, and they are routinely described as a cornerstone for applications and
for theory. We would like to briefly explore why that is, and how this
word-related notion extends to more complex models, such as those developed for
modeling distributed or timed behaviors.


title:
A State-Based Regression Formulation for Domains with Sensing
  Actions<br> and Incomplete Information

abstract:
  We present a state-based regression function for planning domains where an
agent does not have complete information and may have sensing actions. We
consider binary domains and employ a three-valued characterization of domains
with sensing actions to define the regression function. We prove the soundness
and completeness of our regression formulation with respect to the definition
of progression. More specifically, we show that (i) a plan obtained through
regression for a planning problem is indeed a progression solution of that
planning problem, and that (ii) for each plan found through progression, using
regression one obtains that plan or an equivalent one.


title: A Richer Understanding of the Complexity of Election Systems

abstract:
  We provide an overview of some recent progress on the complexity of election
systems. The issues studied include the complexity of the winner, manipulation,
bribery, and control problems.


title: Algebraic recognizability of regular tree languages

abstract:
  We propose a new algebraic framework to discuss and classify recognizable
tree languages, and to characterize interesting classes of such languages. Our
algebraic tool, called preclones, encompasses the classical notion of syntactic
Sigma-algebra or minimal tree automaton, but adds new expressivity to it. The
main result in this paper is a variety theorem \`{a} la Eilenberg, but we also
discuss important examples of logically defined classes of recognizable tree
languages, whose characterization and decidability was established in recent
papers (by Benedikt and S\'{e}goufin, and by Bojanczyk and Walukiewicz) and can
be naturally formulated in terms of pseudovarieties of preclones. Finally, this
paper constitutes the foundation for another paper by the same authors, where
first-order definable tree languages receive an algebraic characterization.


title:
A VFRoe scheme for 1D shallow water flows : wetting and drying
  simulation

abstract:
  A finite-volume method for the one-dimensional shallow-water equations
including topographic source terms is presented. Exploiting an original idea by
Leroux, the system of partial-differential equations is completed by a trivial
equation for the bathymetry. By applying a change of variable, the system is
given a celerity-speed formulation, and linearized. As a result, an approximate
Riemann solver preserving the positivity of the celerity can be constructed,
permitting wetting and drying flow simulations to be performed. Finally, the
simulation of numerical test cases is presented.


title: Measuring Fundamental Properties of Real-World Complex Networks

abstract:
  Complex networks, modeled as large graphs, received much attention during
these last years. However, data on such networks is only available through
intricate measurement procedures. Until recently, most studies assumed that
these procedures eventually lead to samples large enough to be representative
of the whole, at least concerning some key properties. This has crucial impact
on network modeling and simulation, which rely on these properties.
  Recent contributions proved that this approach may be misleading, but no
solution has been proposed. We provide here the first practical way to
distinguish between cases where it is indeed misleading, and cases where the
observed properties may be trusted. It consists in studying how the properties
of interest evolve when the sample grows, and in particular whether they reach
a steady state or not.
  In order to illustrate this method and to demonstrate its relevance, we apply
it to data-sets on complex network measurements that are representative of the
ones commonly used. The obtained results show that the method fulfills its
goals very well. We moreover identify some properties which seem easier to
evaluate in practice, thus opening interesting perspectives.


title:
Theory and Practice of Triangle Problems in Very Large (Sparse
  (Power-Law)) Graphs

abstract:
  Finding, counting and/or listing triangles (three vertices with three edges)
in large graphs are natural fundamental problems, which received recently much
attention because of their importance in complex network analysis. We provide
here a detailed state of the art on these problems, in a unified way. We note
that, until now, authors paid surprisingly little attention to space
complexity, despite its both fundamental and practical interest. We give the
space complexities of known algorithms and discuss their implications. Then we
propose improvements of a known algorithm, as well as a new algorithm, which
are time optimal for triangle listing and beats previous algorithms concerning
space complexity. They have the additional advantage of performing better on
power-law graphs, which we also study. We finally show with an experimental
study that these two algorithms perform very well in practice, allowing to
handle cases that were previously out of reach.


title: Constructing LDPC Codes by 2-Lifts

abstract:
  We propose a new low-density parity-check code construction scheme based on
2-lifts. The proposed codes have an advantage of admitting efficient hardware
implementations. With the motivation of designing codes with low error floors,
we present an analysis of the low-weight stopping set distributions of the
proposed codes. Based on this analysis, we propose design criteria for
designing codes with low error floors. Numerical results show that the
resulting codes have low error probabilities over binary erasure channels.


title: Duality of Fix-Points for Distributive Lattices

abstract:
  We present a novel algorithm for calculating fix-points. The algorithm
calculates fix-points of an endo-function f on a distributive lattice, by
performing reachability computation a graph derived from the dual of f; this is
in comparison to traditional algorithms that are based on iterated application
of f until a fix-point is reached.


title:
Verification, Validation and Integrity of Distributed and Interchanged
  Rule Based Policies and Contracts in the Semantic Web

abstract:
  Rule-based policy and contract systems have rarely been studied in terms of
their software engineering properties. This is a serious omission, because in
rule-based policy or contract representation languages rules are being used as
a declarative programming language to formalize real-world decision logic and
create IS production systems upon. This paper adopts an SE methodology from
extreme programming, namely test driven development, and discusses how it can
be adapted to verification, validation and integrity testing (V&V&I) of policy
and contract specifications. Since, the test-driven approach focuses on the
behavioral aspects and the drawn conclusions instead of the structure of the
rule base and the causes of faults, it is independent of the complexity of the
rule language and the system under test and thus much easier to use and
understand for the rule engineer and the user.


title: Rule-based Knowledge Representation for Service Level Agreement

abstract:
  Automated management and monitoring of service contracts like Service Level
Agreements (SLAs) or higher-level policies is vital for efficient and reliable
distributed service-oriented architectures (SOA) with high quality of ser-vice
(QoS) levels. IT service provider need to manage, execute and maintain
thousands of SLAs for different customers and different types of services,
which needs new levels of flexibility and automation not available with the
current technol-ogy. I propose a novel rule-based knowledge representation (KR)
for SLA rules and a respective rule-based service level management (RBSLM)
framework. My rule-based approach based on logic programming provides several
advantages including automated rule chaining allowing for compact knowledge
representation and high levels of automation as well as flexibility to adapt to
rapidly changing business requirements. Therewith, I address an urgent need
service-oriented busi-nesses do have nowadays which is to dynamically change
their business and contractual logic in order to adapt to rapidly changing
business environments and to overcome the restricting nature of slow change
cycles.


title:
Approximating Rate-Distortion Graphs of Individual Data: Experiments in
  Lossy Compression and Denoising

abstract:
  Classical rate-distortion theory requires knowledge of an elusive source
distribution. Instead, we analyze rate-distortion properties of individual
objects using the recently developed algorithmic rate-distortion theory. The
latter is based on the noncomputable notion of Kolmogorov complexity. To apply
the theory we approximate the Kolmogorov complexity by standard data
compression techniques, and perform a number of experiments with lossy
compression and denoising of objects from different domains. We also introduce
a natural generalization to lossy compression with side information. To
maintain full generality we need to address a difficult searching problem.
While our solutions are therefore not time efficient, we do observe good
denoising and compression performance.


title:
Multi-Antenna Cooperative Wireless Systems: A Diversity-Multiplexing
  Tradeoff Perspective

abstract:
  We consider a general multiple antenna network with multiple sources,
multiple destinations and multiple relays in terms of the
diversity-multiplexing tradeoff (DMT). We examine several subcases of this most
general problem taking into account the processing capability of the relays
(half-duplex or full-duplex), and the network geometry (clustered or
non-clustered). We first study the multiple antenna relay channel with a
full-duplex relay to understand the effect of increased degrees of freedom in
the direct link. We find DMT upper bounds and investigate the achievable
performance of decode-and-forward (DF), and compress-and-forward (CF)
protocols. Our results suggest that while DF is DMT optimal when all terminals
have one antenna each, it may not maintain its good performance when the
degrees of freedom in the direct link is increased, whereas CF continues to
perform optimally. We also study the multiple antenna relay channel with a
half-duplex relay. We show that the half-duplex DMT behavior can significantly
be different from the full-duplex case. We find that CF is DMT optimal for
half-duplex relaying as well, and is the first protocol known to achieve the
half-duplex relay DMT. We next study the multiple-access relay channel (MARC)
DMT. Finally, we investigate a system with a single source-destination pair and
multiple relays, each node with a single antenna, and show that even under the
idealistic assumption of full-duplex relays and a clustered network, this
virtual multi-input multi-output (MIMO) system can never fully mimic a real
MIMO DMT. For cooperative systems with multiple sources and multiple
destinations the same limitation remains to be in effect.


title: Optimal Design of Multiple Description Lattice Vector Quantizers

abstract:
  In the design of multiple description lattice vector quantizers (MDLVQ),
index assignment plays a critical role. In addition, one also needs to choose
the Voronoi cell size of the central lattice v, the sublattice index N, and the
number of side descriptions K to minimize the expected MDLVQ distortion, given
the total entropy rate of all side descriptions Rt and description loss
probability p. In this paper we propose a linear-time MDLVQ index assignment
algorithm for any K >= 2 balanced descriptions in any dimensions, based on a
new construction of so-called K-fraction lattice. The algorithm is greedy in
nature but is proven to be asymptotically (N -> infinity) optimal for any K >=
2 balanced descriptions in any dimensions, given Rt and p. The result is
stronger when K = 2: the optimality holds for finite N as well, under some mild
conditions. For K > 2, a local adjustment algorithm is developed to augment the
greedy index assignment, and conjectured to be optimal for finite N.
  Our algorithmic study also leads to better understanding of v, N and K in
optimal MDLVQ design. For K = 2 we derive, for the first time, a
non-asymptotical closed form expression of the expected distortion of optimal
MDLVQ in p, Rt, N. For K > 2, we tighten the current asymptotic formula of the
expected distortion, relating the optimal values of N and K to p and Rt more
precisely.


title: The Three Gap Theorem (Steinhauss Conjecture)

abstract:
  We deal with the distribution of N points placed consecutively around the
circle by a fixed angle of a. From the proof of Tony van Ravenstein, we propose
a detailed proof of the Steinhaus conjecture whose result is the following: the
N points partition the circle into gaps of at most three different lengths. We
study the mathematical notions required for the proof of this theorem revealed
during a formal proof carried out in Coq.


title: Problem Evolution: A new approach to problem solving systems

abstract:
  In this paper we present a novel tool to evaluate problem solving systems.
Instead of using a system to solve a problem, we suggest using the problem to
evaluate the system. By finding a numerical representation of a problem's
complexity, one can implement genetic algorithm to search for the most complex
problem the given system can solve. This allows a comparison between different
systems that solve the same set of problems. In this paper we implement this
approach on pattern recognition neural networks to try and find the most
complex pattern a given configuration can solve. The complexity of the pattern
is calculated using linguistic complexity. The results demonstrate the power of
the problem evolution approach in ranking different neural network
configurations according to their pattern recognition abilities. Future
research and implementations of this technique are also discussed.


title: E-prints and Journal Articles in Astronomy: a Productive Co-existence

abstract:
  Are the e-prints (electronic preprints) from the arXiv repository being used
instead of the journal articles? In this paper we show that the e-prints have
not undermined the usage of journal papers in the astrophysics community. As
soon as the journal article is published, the astronomical community prefers to
read the journal article and the use of e-prints through the NASA Astrophysics
Data System drops to zero. This suggests that the majority of astronomers have
access to institutional subscriptions and that they choose to read the journal
article when given the choice. Within the NASA Astrophysics Data System they
are given this choice, because the e-print and the journal article are treated
equally, since both are just one click away. In other words, the e-prints have
not undermined journal use in the astrophysics community and thus currently do
not pose a financial threat to the publishers. We present readership data for
the arXiv category "astro-ph" and the 4 core journals in astronomy
(Astrophysical Journal, Astronomical Journal, Monthly Notices of the Royal
Astronomical Society and Astronomy & Astrophysics). Furthermore, we show that
the half-life (the point where the use of an article drops to half the use of a
newly published article) for an e-print is shorter than for a journal paper.
  The ADS is funded by NASA Grant NNG06GG68G. arXiv receives funding from NSF
award #0404553


title: On Bus Graph Realizability

abstract:
  In this paper, we consider the following graph embedding problem: Given a
bipartite graph G = (V1; V2;E), where the maximum degree of vertices in V2 is
4, can G be embedded on a two dimensional grid such that each vertex in V1 is
drawn as a line segment along a grid line, each vertex in V2 is drawn as a
point at a grid point, and each edge e = (u; v) for some u 2 V1 and v 2 V2 is
drawn as a line segment connecting u and v, perpendicular to the line segment
for u? We show that this problem is NP-complete, and sketch how our proof
techniques can be used to show the hardness of several other related problems.


title: Max-Cut and Max-Bisection are NP-hard on unit disk graphs

abstract:
  We prove that the Max-Cut and Max-Bisection problems are NP-hard on unit disk
graphs. We also show that $\lambda$-precision graphs are planar for $\lambda$ >
1 / \sqrt{2}$.


title:
One approach to the digital visualization of hedgehogs in holomorphic
  dynamics

abstract:
  In the field of holomorphic dynamics in one complex variable, hedgehog is the
local invariant set arising about a Cremer point and endowed with a very
complicate shape as well as relating to very weak numerical conditions. We give
a solution to the open problem of its digital visualization, featuring either a
time saving approach and a far-reaching insight.


title: A Predicative Harmonization of the Time and Provable Hierarchies

abstract:
  A decidable transfinite hierarchy is defined by assigning ordinals to the
programs of an imperative language. It singles out: the classes TIMEF(n^c) and
TIMEF(n_c); the finite Grzegorczyk classes at and above the elementary level,
and the \Sigma_k-IND fragments of PA. Limited operators, diagonalization, and
majorization functions are not used.


title:
A Fast Block Matching Algorithm for Video Motion Estimation Based on
  Particle Swarm Optimization and Motion Prejudgment

abstract:
  In this paper, we propose a fast 2-D block-based motion estimation algorithm
called Particle Swarm Optimization - Zero-motion Prejudgment(PSO-ZMP) which
consists of three sequential routines: 1)Zero-motion prejudgment. The routine
aims at finding static macroblocks(MB) which do not need to perform remaining
search thus reduces the computational cost; 2)Predictive image coding and 3)PSO
matching routine. Simulation results obtained show that the proposed PSO-ZMP
algorithm achieves over 10 times of computation less than Diamond Search(DS)
and 5 times less than the recent proposed Adaptive Rood Pattern
Searching(ARPS). Meanwhile the PSNR performances using PSO-ZMP are very close
to that using DS and ARPS in some less-motioned sequences. While in some
sequences containing dense and complex motion contents, the PSNR performances
of PSO-ZMP are several dB lower than that using DS and ARPS but in an
acceptable degree.


title: Semantic Description of Parameters in Web Service Annotations

abstract:
  A modification of OWL-S regarding parameter description is proposed. It is
strictly based on Description Logic. In addition to class description of
parameters it also allows the modelling of relations between parameters and the
precise description of the size of data to be supplied to a service. In
particular, it solves two major issues identified within current proposals for
a Semantic Web Service annotation standard.


title:
An application-oriented terminology evaluation: the case of back-of-the
  book indexes

abstract:
  This paper addresses the problem of computational terminology evaluation not
per se but in a specific application context. This paper describes the
evaluation procedure that has been used to assess the validity of our overall
indexing approach and the quality of the IndDoc indexing tool. Even if
user-oriented extended evaluation is irreplaceable, we argue that early
evaluations are possible and they are useful for development guidance.


title: Using NLP to build the hypertextuel network of a back-of-the-book index

abstract:
  Relying on the idea that back-of-the-book indexes are traditional devices for
navigation through large documents, we have developed a method to build a
hypertextual network that helps the navigation in a document. Building such an
hypertextual network requires selecting a list of descriptors, identifying the
relevant text segments to associate with each descriptor and finally ranking
the descriptors and reference segments by relevance order. We propose a
specific document segmentation method and a relevance measure for information
ranking. The algorithms are tested on 4 corpora (of different types and
domains) without human intervention or any semantic knowledge.


title:
Event-based Information Extraction for the biomedical domain: the
  Caderige project

abstract:
  This paper gives an overview of the Caderige project. This project involves
teams from different areas (biology, machine learning, natural language
processing) in order to develop high-level analysis tools for extracting
structured information from biological bibliographical databases, especially
Medline. The paper gives an overview of the approach and compares it to the
state of the art.


title: The ALVIS Format for Linguistically Annotated Documents

abstract:
  The paper describes the ALVIS annotation format designed for the indexing of
large collections of documents in topic-specific search engines. This paper is
exemplified on the biological domain and on MedLine abstracts, as developing a
specialized search engine for biologists is one of the ALVIS case studies. The
ALVIS principle for linguistic annotations is based on existing works and
standard propositions. We made the choice of stand-off annotations rather than
inserted mark-up. Annotations are encoded as XML elements which form the
linguistic subsection of the document record.


title: Ontologies and Information Extraction

abstract:
  This report argues that, even in the simplest cases, IE is an ontology-driven
process. It is not a mere text filtering method based on simple pattern
matching and keywords, because the extracted pieces of texts are interpreted
with respect to a predefined partial domain model. This report shows that
depending on the nature and the depth of the interpretation to be done for
extracting the information, more or less knowledge must be involved. This
report is mainly illustrated in biology, a domain in which there are critical
needs for content-based exploration of the scientific literature and which
becomes a major application domain for IE.


title: MDL Denoising Revisited

abstract:
  We refine and extend an earlier MDL denoising criterion for wavelet-based
denoising. We start by showing that the denoising problem can be reformulated
as a clustering problem, where the goal is to obtain separate clusters for
informative and non-informative wavelet coefficients, respectively. This
suggests two refinements, adding a code-length for the model index, and
extending the model in order to account for subband-dependent coefficient
distributions. A third refinement is derivation of soft thresholding inspired
by predictive universal coding with weighted mixtures. We propose a practical
method incorporating all three refinements, which is shown to achieve good
performance and robustness in denoising both artificial and natural signals.


title: The Capacity of Channels with Feedback

abstract:
  We introduce a general framework for treating channels with memory and
feedback. First, we generalize Massey's concept of directed information and use
it to characterize the feedback capacity of general channels. Second, we
present coding results for Markov channels. This requires determining
appropriate sufficient statistics at the encoder and decoder. Third, a dynamic
programming framework for computing the capacity of Markov channels is
presented. Fourth, it is shown that the average cost optimality equation (ACOE)
can be viewed as an implicit single-letter characterization of the capacity.
Fifth, scenarios with simple sufficient statistics are described.


title: Motion Primitives for Robotic Flight Control

abstract:
  We introduce a simple framework for learning aggressive maneuvers in flight
control of UAVs. Having inspired from biological environment, dynamic movement
primitives are analyzed and extended using nonlinear contraction theory.
Accordingly, primitives of an observed movement are stably combined and
concatenated. We demonstrate our results experimentally on the Quanser
Helicopter, in which we first imitate aggressive maneuvers and then use them as
primitives to achieve new maneuvers that can fly over an obstacle.


title: Polygon Convexity: A Minimal O(n) Test

abstract:
  An O(n) test for polygon convexity is stated and proved. It is also proved
that the test is minimal in a certain exact sense.


title: Modular self-organization

abstract:
  The aim of this paper is to provide a sound framework for addressing a
difficult problem: the automatic construction of an autonomous agent's modular
architecture. We combine results from two apparently uncorrelated domains:
Autonomous planning through Markov Decision Processes and a General Data
Clustering Approach using a kernel-like method. Our fundamental idea is that
the former is a good framework for addressing autonomy whereas the latter
allows to tackle self-organizing problems.


title:
ECA-LP / ECA-RuleML: A Homogeneous Event-Condition-Action Logic
  Programming Language

abstract:
  Event-driven reactive functionalities are an urgent need in nowadays
distributed service-oriented applications and (Semantic) Web-based
environments. An important problem to be addressed is how to correctly and
efficiently capture and process the event-based behavioral, reactive logic
represented as ECA rules in combination with other conditional decision logic
which is represented as derivation rules. In this paper we elaborate on a
homogeneous integration approach which combines derivation rules, reaction
rules (ECA rules) and other rule types such as integrity constraint into the
general framework of logic programming. The developed ECA-LP language provides
expressive features such as ID-based updates with support for external and
self-updates of the intensional and extensional knowledge, transac-tions
including integrity testing and an event algebra to define and process complex
events and actions based on a novel interval-based Event Calculus variant.


title:
The Management and Integration of Biomedical Knowledge: Application in
  the Health-e-Child Project (Position Paper)

abstract:
  The Health-e-Child project aims to develop an integrated healthcare platform
for European paediatrics. In order to achieve a comprehensive view of childrens
health, a complex integration of biomedical data, information, and knowledge is
necessary. Ontologies will be used to formally define this domain knowledge and
will form the basis for the medical knowledge management system. This paper
introduces an innovative methodology for the vertical integration of biomedical
knowledge. This approach will be largely clinician-centered and will enable the
definition of ontology fragments, connections between them (semantic bridges)
and enriched ontology fragments (views). The strategy for the specification and
capture of fragments, bridges and views is outlined with preliminary examples
demonstrated in the collection of biomedical information from hospital
databases, biomedical ontologies, and biomedical public databases.


title: A Semidefinite Relaxation for Air Traffic Flow Scheduling

abstract:
  We first formulate the problem of optimally scheduling air traffic low with
sector capacity constraints as a mixed integer linear program. We then use
semidefinite relaxation techniques to form a convex relaxation of that problem.
Finally, we present a randomization algorithm to further improve the quality of
the solution. Because of the specific structure of the air traffic flow
problem, the relaxation has a single semidefinite constraint of size dn where d
is the maximum delay and n the number of flights.


title: A Combinatorial Family of Near Regular LDPC Codes

abstract:
  An elementary combinatorial Tanner graph construction for a family of
near-regular low density parity check codes achieving high girth is presented.
The construction allows flexibility in the choice of design parameters like
rate, average degree, girth and block length of the code and yields an
asymptotic family. The complexity of constructing codes in the family grows
only quadratically with the block length.


title: Identifying Crosscutting Concerns Using Fan-in Analysis

abstract:
  Aspect mining is a reverse engineering process that aims at finding
crosscutting concerns in existing systems. This paper proposes an aspect mining
approach based on determining methods that are called from many different
places, and hence have a high fan-in, which can be seen as a symptom of
crosscutting functionality. The approach is semi-automatic, and consists of
three steps: metric calculation, method filtering, and call site analysis.
Carrying out these steps is an interactive process supported by an Eclipse
plug-in called FINT. Fan-in analysis has been applied to three open source Java
systems, totaling around 200,000 lines of code. The most interesting concerns
identified are discussed in detail, which includes several concerns not
previously discussed in the aspect-oriented literature. The results show that a
significant number of crosscutting concerns can be recognized using fan-in
analysis, and each of the three steps can be supported by tools.


title: Pseudo-Codeword Performance Analysis for LDPC Convolutional Codes

abstract:
  Message-passing iterative decoders for low-density parity-check (LDPC) block
codes are known to be subject to decoding failures due to so-called
pseudo-codewords. These failures can cause the large signal-to-noise ratio
performance of message-passing iterative decoding to be worse than that
predicted by the maximum-likelihood decoding union bound. In this paper we
address the pseudo-codeword problem from the convolutional-code perspective. In
particular, we compare the performance of LDPC convolutional codes with that of
their ``wrapped'' quasi-cyclic block versions and we show that the minimum
pseudo-weight of an LDPC convolutional code is at least as large as the minimum
pseudo-weight of an underlying quasi-cyclic code. This result, which parallels
a well-known relationship between the minimum Hamming weight of convolutional
codes and the minimum Hamming weight of their quasi-cyclic counterparts, is due
to the fact that every pseudo-codeword in the convolutional code induces a
pseudo-codeword in the block code with pseudo-weight no larger than that of the
convolutional code's pseudo-codeword. This difference in the weight spectra
leads to improved performance at low-to-moderate signal-to-noise ratios for the
convolutional code, a conclusion supported by simulation results.


title:
Dynamic Spectrum Access: Signal Processing, Networking, and Regulatory
  Policy

abstract:
  In this article, we first provide a taxonomy of dynamic spectrum access. We
then focus on opportunistic spectrum access, the overlay approach under the
hierarchical access model of dynamic spectrum access. we aim to provide an
overview of challenges and recent developments in both technological and
regulatory aspects of opportunistic spectrum access.


title:
Modelling and Simulation of Scheduling Policies Implemented in Ethernet
  Switch by Using Coloured Petri Nets

abstract:
  The objective of this paper is to propose models enabling to study the
behaviour of Ethernet switch for Networked Control Systems. Two scheduler
policies are analyzed: the static priority and the WRR (Weighted Round Robin).
The modelling work is based on Coloured Petri Nets. A temporal validation step
based on the simulation of these modelling, shows that the obtained results are
near to the expected behaviour of these scheduler policies.


title:
Control compensation based on upper bound delay in networked control
  systems

abstract:
  Recent interest in networked control systems (NCS) has instigated research in
both communication networks and control. Analysis of NCSs has usually been
performed from either the network or the control point of view, but not many
papers exist where the analysis of both is done in the same context. In this
paper an overall analysis of the networked control system is presented. First,
the procedure of obtaining the upper bound delay value for packet transmission
in the switched Ethernet network is presented. Next, the obtained delay
estimate is utilised in delay compensation for improving the Quality of
Performance (QoP) of the control systems. The presented upper bound delay
algorithm applies ideas from network calculus theory. For the improvement of
QoP, two delay compensation strategies, the Smith predictor based and the
robust control based delay compensation strategies, are presented and compared.


title:
Use of upper bound delay estimate in stability analysis and robust
  control compensation in networked control systems

abstract:
  Recent interest in networked control systems (NCS) has instigated research in
various areas of both communication networks and control. The analysis of NCS
has often been performed either from the network, or the control point of view
and not many papers exist were the analysis of both is done in the same
context. Here a simple overall analysis is presented. In the paper the
procedure of obtaining the upper bound delay value in the switched Ethernet
network is proposed and the obtained delay estimate is used in stability
analysis of the feedback loop and in the control compensation. The upper bound
delay algorithm is based on the network calculus theory, the stability analysis
uses the small gain theorem, and control compensating strategy is based on
Smith predictor, where however the upper bound delay is utilised in obtaining
the delay estimate.


title: Mining Generalized Graph Patterns based on User Examples

abstract:
  There has been a lot of recent interest in mining patterns from graphs.
Often, the exact structure of the patterns of interest is not known. This
happens, for example, when molecular structures are mined to discover fragments
useful as features in chemical compound classification task, or when web sites
are mined to discover sets of web pages representing logical documents. Such
patterns are often generated from a few small subgraphs (cores), according to
certain generalization rules (GRs). We call such patterns "generalized
patterns"(GPs). While being structurally different, GPs often perform the same
function in the network. Previously proposed approaches to mining GPs either
assumed that the cores and the GRs are given, or that all interesting GPs are
frequent. These are strong assumptions, which often do not hold in practical
applications. In this paper, we propose an approach to mining GPs that is free
from the above assumptions. Given a small number of GPs selected by the user,
our algorithm discovers all GPs similar to the user examples. First, a machine
learning-style approach is used to find the cores. Second, generalizations of
the cores in the graph are computed to identify GPs. Evaluation on synthetic
data, generated using real cores and GRs from biological and web domains,
demonstrates effectiveness of our approach.


title:
Loop Calculus Helps to Improve Belief Propagation and Linear Programming
  Decodings of Low-Density-Parity-Check Codes

abstract:
  We illustrate the utility of the recently developed loop calculus for
improving the Belief Propagation (BP) algorithm. If the algorithm that
minimizes the Bethe free energy fails we modify the free energy by accounting
for a critical loop in a graphical representation of the code. The
log-likelihood specific critical loop is found by means of the loop calculus.
The general method is tested using an example of the Linear Programming (LP)
decoding, that can be viewed as a special limit of the BP decoding. Considering
the (155,64,20) code that performs over Additive-White-Gaussian-Noise channel
we show that the loop calculus improves the LP decoding and corrects all
previously found dangerous configurations of log-likelihoods related to
pseudo-codewords with low effective distance, thus reducing the code's
error-floor.

categories: cs.IT cond-mat.dis-nn cond-mat.stat-mech math.IT


title:
Detection of Markov Random Fields on Two-Dimensional Intersymbol
  Interference Channels

abstract:
  We present a novel iterative algorithm for detection of binary Markov random
fields (MRFs) corrupted by two-dimensional (2D) intersymbol interference (ISI)
and additive white Gaussian noise (AWGN). We assume a first-order binary MRF as
a simple model for correlated images. We assume a 2D digital storage channel,
where the MRF is interleaved before being written and then read by a 2D
transducer; such channels occur in recently proposed optical disk storage
systems. The detection algorithm is a concatenation of two
soft-input/soft-output (SISO) detectors: an iterative row-column soft-decision
feedback (IRCSDF) ISI detector, and a MRF detector. The MRF detector is a SISO
version of the stochastic relaxation algorithm by Geman and Geman in IEEE
Trans. Pattern Anal. and Mach. Intell., Nov. 1984. On the 2 x 2 averaging-mask
ISI channel, at a bit error rate (BER) of 10^{-5}, the concatenated algorithm
achieves SNR savings of between 0.5 and 2.0 dB over the IRCSDF detector alone;
the savings increase as the MRFs become more correlated, or as the SNR
decreases. The algorithm is also fairly robust to mismatches between the
assumed and actual MRF parameters.


title: Entangled Graphs

abstract:
  In this paper we prove a separability criterion for mixed states in $\mathbb
C^p\otimes\mathbb C^q$. We also show that the density matrix of a graph with
only one entangled edge is entangled.


title: Sensor Scheduling for Optimal Observability Using Estimation Entropy

abstract:
  We consider sensor scheduling as the optimal observability problem for
partially observable Markov decision processes (POMDP). This model fits to the
cases where a Markov process is observed by a single sensor which needs to be
dynamically adjusted or by a set of sensors which are selected one at a time in
a way that maximizes the information acquisition from the process. Similar to
conventional POMDP problems, in this model the control action is based on all
past measurements; however here this action is not for the control of state
process, which is autonomous, but it is for influencing the measurement of that
process. This POMDP is a controlled version of the hidden Markov process, and
we show that its optimal observability problem can be formulated as an average
cost Markov decision process (MDP) scheduling problem. In this problem, a
policy is a rule for selecting sensors or adjusting the measuring device based
on the measurement history. Given a policy, we can evaluate the estimation
entropy for the joint state-measurement processes which inversely measures the
observability of state process for that policy. Considering estimation entropy
as the cost of a policy, we show that the problem of finding optimal policy is
equivalent to an average cost MDP scheduling problem where the cost function is
the entropy function over the belief space. This allows the application of the
policy iteration algorithm for finding the policy achieving minimum estimation
entropy, thus optimum observability.


title: A Fast Image Encryption Scheme based on Chaotic Standard Map

abstract:
  In recent years, a variety of effective chaos-based image encryption schemes
have been proposed. The typical structure of these schemes has the permutation
and the diffusion stages performed alternatively. The confusion and diffusion
effect is solely contributed by the permutation and the diffusion stage,
respectively. As a result, more overall rounds than necessary are required to
achieve a certain level of security. In this paper, we suggest to introduce
certain diffusion effect in the confusion stage by simple sequential
add-and-shift operations. The purpose is to reduce the workload of the
time-consuming diffusion part so that fewer overall rounds and hence a shorter
encryption time is needed. Simulation results show that at a similar
performance level, the proposed cryptosystem needs less than one-third the
encryption time of an existing cryptosystem. The effective acceleration of the
encryption speed is thus achieved.


title: Duality for Several Families of Evaluation Codes

abstract:
  We consider generalizations of Reed-Muller codes, toric codes, and codes from
certain plane curves, such as those defined by norm and trace functions on
finite fields. In each case we are interested in codes defined by evaluating
arbitrary subsets of monomials, and in identifying when the dual codes are also
obtained by evaluating monomials. We then move to the context of order domain
theory, in which the subsets of monomials can be chosen to optimize decoding
performance using the Berlekamp-Massey-Sakata algorithm with majority voting.
We show that for the codes under consideration these subsets are well-behaved
and the dual codes are also defined by monomials.


title: Redundancies of Correction-Capability-Optimized Reed-Muller Codes

abstract:
  This article is focused on some variations of Reed-Muller codes that yield
improvements to the rate for a prescribed decoding performance under the
Berlekamp-Massey-Sakata algorithm with majority voting. Explicit formulas for
the redundancies of the new codes are given.


title:
The Order Bound on the Minimum Distance of the One-Point Codes
  Associated to a Garcia-Stichtenoth Tower of Function Fields

abstract:
  Garcia and Stichtenoth discovered two towers of function fields that meet the
Drinfeld-Vl\u{a}du\c{t} bound on the ratio of the number of points to the
genus. For one of these towers, Garcia, Pellikaan and Torres derived a
recursive description of the Weierstrass semigroups associated to a tower of
points on the associated curves. In this article, a non-recursive description
of the semigroups is given and from this the enumeration of each of the
semigroups is derived as well as its inverse. This enables us to find an
explicit formula for the order (Feng-Rao) bound on the minimum distance of the
associated one-point codes.


title:
On Semigroups Generated by Two Consecutive Integers and Improved
  Hermitian Codes

abstract:
  Analysis of the Berlekamp-Massey-Sakata algorithm for decoding one-point
codes leads to two methods for improving code rate. One method, due to Feng and
Rao, removes parity checks that may be recovered by their majority voting
algorithm. The second method is to design the code to correct only those error
vectors of a given weight that are also geometrically generic. In this work,
formulae are given for the redundancies of Hermitian codes optimized with
respect to these criteria as well as the formula for the order bound on the
minimum distance. The results proceed from an analysis of numerical semigroups
generated by two consecutive integers. The formula for the redundancy of
optimal Hermitian codes correcting a given number of errors answers an open
question stated by Pellikaan and Torres in 1999.


title: Labeling Schemes with Queries

abstract:
  We study the question of ``how robust are the known lower bounds of labeling
schemes when one increases the number of consulted labels''. Let $f$ be a
function on pairs of vertices. An $f$-labeling scheme for a family of graphs
$\cF$ labels the vertices of all graphs in $\cF$ such that for every graph
$G\in\cF$ and every two vertices $u,v\in G$, the value $f(u,v)$ can be inferred
by merely inspecting the labels of $u$ and $v$.
  This paper introduces a natural generalization: the notion of $f$-labeling
schemes with queries, in which the value $f(u,v)$ can be inferred by inspecting
not only the labels of $u$ and $v$ but possibly the labels of some additional
vertices. We show that inspecting the label of a single additional vertex (one
{\em query}) enables us to reduce the label size of many labeling schemes
significantly.


title: Conditional Expressions for Blind Deconvolution: Multi-point form

abstract:
  We present conditional expression (CE) for finding blurs convolved in given
images. The CE is given in terms of the zero-values of the blurs evaluated at
multi-point. The CE can detect multiple blur all at once. We illustrate the
multiple blur-detection by using a test image.


title: Simple method to eliminate blur based on Lane and Bates algorithm

abstract:
  A simple search method for finding a blur convolved in a given image is
presented. The method can be easily extended to a large blur. The method has
been experimentally tested with a model blurred image.


title: Private Approximate Heavy Hitters

abstract:
  We consider the problem of private computation of approximate Heavy Hitters.
Alice and Bob each hold a vector and, in the vector sum, they want to find the
B largest values along with their indices. While the exact problem requires
linear communication, protocols in the literature solve this problem
approximately using polynomial computation time, polylogarithmic communication,
and constantly many rounds. We show how to solve the problem privately with
comparable cost, in the sense that nothing is learned by Alice and Bob beyond
what is implied by their input, the ideal top-B output, and goodness of
approximation (equivalently, the Euclidean norm of the vector sum). We give
lower bounds showing that the Euclidean norm must leak by any efficient
algorithm.


title:
Updates in Answer Set Programming: An Approach Based on Basic Structural
  Properties

abstract:
  We have studied the update operator defined for update sequences by Eiter et
al. without tautologies and we have observed that it satisfies an interesting
property This property, which we call Weak Independence of Syntax (WIS), is
similar to one of the postulates proposed by Alchourron, Gardenfors, and
Makinson (AGM); only that in this case it applies to nonmonotonic logic. In
addition, we consider other five additional basic properties about update
programs and we show that the operator of Eiter et al. satisfies them. This
work continues the analysis of the AGM postulates under a refined view that
considers nelson logic as a monotonic logic which allows us to expand our
understanding of answer sets. Moreover, nelson logic helped us to derive an
alternative definition of the operator defined by Eiter et al. avoiding the use
of unnecessary extra atoms.


title: Practical Entropy-Compressed Rank/Select Dictionary

abstract:
  Rank/Select dictionaries are data structures for an ordered set $S \subset
\{0,1,...,n-1\}$ to compute $\rank(x,S)$ (the number of elements in $S$ which
are no greater than $x$), and $\select(i,S)$ (the $i$-th smallest element in
$S$), which are the fundamental components of \emph{succinct data structures}
of strings, trees, graphs, etc. In those data structures, however, only
asymptotic behavior has been considered and their performance for real data is
not satisfactory. In this paper, we propose novel four Rank/Select
dictionaries, esp, recrank, vcode and sdarray, each of which is small if the
number of elements in $S$ is small, and indeed close to $nH_0(S)$ ($H_0(S) \leq
1$ is the zero-th order \textit{empirical entropy} of $S$) in practice, and its
query time is superior to the previous ones. Experimental results reveal the
characteristics of our data structures and also show that these data structures
are superior to existing implementations in both size and query time.