title:
Two Iterative Algorithms for Solving Systems of Simultaneous Linear
  Algebraic Equations with Real Matrices of Coefficients

abstract:
  The paper describes two iterative algorithms for solving general systems of M
simultaneous linear algebraic equations (SLAE) with real matrices of
coefficients. The system can be determined, underdetermined, and
overdetermined. Linearly dependent equations are also allowed. Both algorithms
use the method of Lagrange multipliers to transform the original SLAE into a
positively determined function F of real original variables X(i) (i=1,...,N)
and Lagrange multipliers Lambda(i) (i=1,...,M). Function F is differentiated
with respect to variables X(i) and the obtained relationships are used to
express F in terms of Lagrange multipliers Lambda(i). The obtained function is
minimized with respect to variables Lambda(i) with the help of one of two the
following minimization techniques: (1) relaxation method or (2) method of
conjugate gradients by Fletcher and Reeves. Numerical examples are given.


title: Maintaining Consistency of Data on the Web

abstract:
  Increasingly more data is becoming available on the Web, estimates speaking
of 1 billion documents in 2002. Most of the documents are Web pages whose data
is considered to be in XML format, expecting it to eventually replace HTML.
  A common problem in designing and maintaining a Web site is that data on a
Web page often replicates or derives from other data, the so-called base data,
that is usually not contained in the deriving or replicating page.
Consequently, replicas and derivations become inconsistent upon modifying base
data in a Web page or a relational database. For example, after assigning a
thesis to a student and modifying the Web page that describes it in detail, the
thesis is still incorrectly contained in the list of offered thesis, missing in
the list of ongoing thesis, and missing in the advisor's teaching record.
  The thesis presents a solution by proposing a combined approach that provides
for maintaining consistency of data in Web pages that (i) replicate data in
relational databases, or (ii) replicate or derive from data in Web pages. Upon
modifying base data, the modification is immediately pushed to affected Web
pages. There, maintenance is performed incrementally by only modifying the
affected part of the page instead of re-generating the whole page from scratch.


title:
Proving Correctness and Completeness of Normal Programs - a Declarative
  Approach

abstract:
  We advocate a declarative approach to proving properties of logic programs.
Total correctness can be separated into correctness, completeness and clean
termination; the latter includes non-floundering. Only clean termination
depends on the operational semantics, in particular on the selection rule. We
show how to deal with correctness and completeness in a declarative way,
treating programs only from the logical point of view. Specifications used in
this approach are interpretations (or theories). We point out that
specifications for correctness may differ from those for completeness, as
usually there are answers which are neither considered erroneous nor required
to be computed.
  We present proof methods for correctness and completeness for definite
programs and generalize them to normal programs. For normal programs we use the
3-valued completion semantics; this is a standard semantics corresponding to
negation as finite failure. The proof methods employ solely the classical
2-valued logic. We use a 2-valued characterization of the 3-valued completion
semantics which may be of separate interest. The presented methods are compared
with an approach based on operational semantics. We also employ the ideas of
this work to generalize a known method of proving termination of normal
programs.


title: Augmented Segmentation and Visualization for Presentation Videos

abstract:
  We investigate methods of segmenting, visualizing, and indexing presentation
videos by separately considering audio and visual data. The audio track is
segmented by speaker, and augmented with key phrases which are extracted using
an Automatic Speech Recognizer (ASR). The video track is segmented by visual
dissimilarities and augmented by representative key frames. An interactive user
interface combines a visual representation of audio, video, text, and key
frames, and allows the user to navigate a presentation video. We also explore
clustering and labeling of speaker data and present preliminary results.


title: Improved Approximation Algorithms for Geometric Set Cover

abstract:
  Given a collection S of subsets of some set U, and M a subset of U, the set
cover problem is to find the smallest subcollection C of S such that M is a
subset of the union of the sets in C. While the general problem is NP-hard to
solve, even approximately, here we consider some geometric special cases, where
usually U = R^d. Extending prior results, we show that approximation algorithms
with provable performance exist, under a certain general condition: that for a
random subset R of S and function f(), there is a decomposition of the portion
of U not covered by R into an expected f(|R|) regions, each region of a
particular simple form. We show that under this condition, a cover of size
O(f(|C|)) can be found. Our proof involves the generalization of shallow
cuttings to more general geometric situations. We obtain constant-factor
approximation algorithms for covering by unit cubes in R^3, for guarding a
one-dimensional terrain, and for covering by similar-sized fat triangles in
R^2. We also obtain improved approximation guarantees for fat triangles, of
arbitrary size, and for a class of fat objects.


title:
Thermodynamics of used punched tape: A weak and a strong equivalence
  principle

abstract:
  We study the repeated use of a monotonic recording medium--such as punched
tape or photographic plate--where marks can be added at any time but never
erased. (For practical purposes, also the electromagnetic "ether" falls into
this class.) Our emphasis is on the case where the successive users act
independently and selfishly, but not maliciously; typically, the "first user"
would be a blind natural process tending to degrade the recording medium, and
the "second user" a human trying to make the most of whatever capacity is left.
  To what extent is a length of used tape "equivalent"--for information
transmission purposes--to a shorter length of virgin tape? Can we characterize
a piece of used tape by an appropriate "effective length" and forget all other
details? We identify two equivalence principles. The weak principle is exact,
but only holds for a sequence of infinitesimal usage increments. The strong
principle holds for any amount of incremental usage, but is only approximate;
nonetheless, it is quite accurate even in the worst case and is virtually exact
over most of the range--becoming exact in the limit of heavily used tape.
  The fact that strong equivalence does not hold exactly, but then it does
almost exactly, comes as a bit of a surprise.


title:
Impact of Channel Estimation Errors on Multiuser Detection via the
  Replica Method

abstract:
  For practical wireless DS-CDMA systems, channel estimation is imperfect due
to noise and interference. In this paper, the impact of channel estimation
errors on multiuser detection (MUD) is analyzed under the framework of the
replica method. System performance is obtained in the large system limit for
optimal MUD, linear MUD and turbo MUD, and is validated by numerical results
for finite systems.


title:
Low Complexity Joint Iterative Equalization and Multiuser Detection in
  Dispersive DS-CDMA Channels

abstract:
  Communications in dispersive direct-sequence code-division multiple-access
(DS-CDMA) channels suffer from intersymbol and multiple-access interference,
which can significantly impair performance. Joint maximum \textit{a posteriori}
probability (MAP) equalization and multiuser detection with error control
decoding can be used to mitigate this interference and to achieve the optimal
bit error rate. Unfortunately, such optimal detection typically requires
prohibitive computational complexity. This problem is addressed in this paper
through the development of a reduced state trellis search detection algorithm,
based on decision feedback from channel decoders. The performance of this
algorithm is analyzed in the large-system limit. This analysis and simulations
show that this low-complexity algorithm can obtain near-optimal performance
under moderate signal-to-noise ratio and attains larger system load capacity
than parallel interference cancellation.


title:
Performance Evaluation of Impulse Radio UWB Systems with Pulse-Based
  Polarity Randomization

abstract:
  In this paper, the performance of a binary phase shift keyed random
time-hopping impulse radio system with pulse-based polarity randomization is
analyzed. Transmission over frequency-selective channels is considered and the
effects of inter-frame interference and multiple access interference on the
performance of a generic Rake receiver are investigated for both synchronous
and asynchronous systems. Closed form (approximate) expressions for the
probability of error that are valid for various Rake combining schemes are
derived. The asynchronous system is modelled as a chip-synchronous system with
uniformly distributed timing jitter for the transmitted pulses of interfering
users. This model allows the analytical technique developed for the synchronous
case to be extended to the asynchronous case. An approximate closed-form
expression for the probability of bit error, expressed in terms of the
autocorrelation function of the transmitted pulse, is derived for the
asynchronous case. Then, transmission over an additive white Gaussian noise
channel is studied as a special case, and the effects of multiple-access
interference is investigated for both synchronous and asynchronous systems. The
analysis shows that the chip-synchronous assumption can result in
over-estimating the error probability, and the degree of over-estimation mainly
depends on the autocorrelation function of the ultra-wideband pulse and the
signal-to-interference-plus-noise-ratio of the system. Simulations studies
support the approximate analysis.


title: Energy-Efficient Joint Estimation in Sensor Networks: Analog vs. Digital

abstract:
  Sensor networks in which energy is a limited resource so that energy
consumption must be minimized for the intended application are considered. In
this context, an energy-efficient method for the joint estimation of an unknown
analog source under a given distortion constraint is proposed. The approach is
purely analog, in which each sensor simply amplifies and forwards the
noise-corrupted analog bservation to the fusion center for joint estimation.
The total transmission power across all the sensor nodes is minimized while
satisfying a distortion requirement on the joint estimate. The energy
efficiency of this analog approach is compared with previously proposed digital
approaches with and without coding. It is shown in our simulation that the
analog approach is more energy-efficient than the digital system without
coding, and in some cases outperforms the digital system with optimal coding.


title: On the Capacity of Multiple Antenna Systems in Rician Fading

abstract:
  The effect of Rician-ness on the capacity of multiple antenna systems is
investigated under the assumption that channel state information (CSI) is
available only at the receiver. The average-power-constrained capacity of such
systems is considered under two different assumptions on the knowledge about
the fading available at the transmitter: the case in which the transmitter has
no knowledge of fading at all, and the case in which the transmitter has
knowledge of the distribution of the fading process but not the instantaneous
CSI. The exact capacity is given for the former case while capacity bounds are
derived for the latter case. A new signalling scheme is also proposed for the
latter case and it is shown that by exploiting the knowledge of Rician-ness at
the transmitter via this signalling scheme, significant capacity gain can be
achieved. The derived capacity bounds are evaluated explicitly to provide
numerical results in some representative situations.


title: Stochastic Differential Games in a Non-Markovian Setting

abstract:
  Stochastic differential games are considered in a non-Markovian setting.
Typically, in stochastic differential games the modulating process of the
diffusion equation describing the state flow is taken to be Markovian. Then
Nash equilibria or other types of solution such as Pareto equilibria are
constructed using Hamilton-Jacobi-Bellman (HJB) equations. But in a
non-Markovian setting the HJB method is not applicable. To examine the
non-Markovian case, this paper considers the situation in which the modulating
process is a fractional Brownian motion. Fractional noise calculus is used for
such models to find the Nash equilibria explicitly. Although fractional
Brownian motion is taken as the modulating process because of its versatility
in modeling in the fields of finance and networks, the approach in this paper
has the merit of being applicable to more general Gaussian stochastic
differential games with only slight conceptual modifications. This work has
applications in finance to stock price modeling which incorporates the effect
of institutional investors, and to stochastic differential portfolio games in
markets in which the stock prices follow diffusions modulated with fractional
Brownian motion.


title: Relational Algebra as non-Distributive Lattice

abstract:
  We reduce the set of classic relational algebra operators to two binary
operations: natural join and generalized union. We further demonstrate that
this set of operators is relationally complete and honors lattice axioms.


title: Arbitrage in Fractal Modulated Markets When the Volatility is Stochastic

abstract:
  In this paper an arbitrage strategy is constructed for the modified
Black-Scholes model driven by fractional Brownian motion or by a time changed
fractional Brownian motion, when the volatility is stochastic. This latter
property allows the heavy tailedness of the log returns of the stock prices to
be also accounted for in addition to the long range dependence introduced by
the fractional Brownian motion. Work has been done previously on this problem
for the case with constant `volatility' and without a time change; here these
results are extended to the case of stochastic volatility models when the
modulator is fractional Brownian motion or a time change of it. (Volatility in
fractional Black-Scholes models does not carry the same meaning as in the
classic Black-Scholes framework, which is made clear in the text.)
  Since fractional Brownian motion is not a semi-martingale, the Black-Scholes
differential equation is not well-defined sense for arbitrary predictable
volatility processes. However, it is shown here that any almost surely
continuous and adapted process having zero quadratic variation can act as an
integrator over functions of the integrator and over the family of continuous
adapted semi-martingales. Moreover it is shown that the integral also has zero
quadratic variation, and therefore that the integral itself can be an
integrator. This property of the integral is crucial in developing the
arbitrage strategy. Since fractional Brownian motion and a time change of
fractional Brownian motion have zero quadratic variation, these results are
applicable to these cases in particular. The appropriateness of fractional
Brownian motion as a means of modeling stock price returns is discussed as
well.


title: Consistency Problems for Jump-Diffusion Models

abstract:
  In this paper consistency problems for multi-factor jump-diffusion models,
where the jump parts follow multivariate point processes are examined. First
the gap between jump-diffusion models and generalized Heath-Jarrow-Morton (HJM)
models is bridged. By applying the drift condition for a generalized
arbitrage-free HJM model, the consistency condition for jump-diffusion models
is derived. Then we consider a case in which the forward rate curve has a
separable structure, and obtain a specific version of the general consistency
condition. In particular, a necessary and sufficient condition for a
jump-diffusion model to be affine is provided. Finally the Nelson-Siegel type
of forward curve structures is discussed. It is demonstrated that under
regularity condition, there exists no jump-diffusion model consistent with the
Nelson-Siegel curves.


title:
A Large Deviations Approach to Sensor Scheduling for Detection of
  Correlated Random Fields

abstract:
  The problem of scheduling sensor transmissions for the detection of
correlated random fields using spatially deployed sensors is considered. Using
the large deviations principle, a closed-form expression for the error exponent
of the miss probability is given as a function of the sensor spacing and
signal-to-noise ratio (SNR). It is shown that the error exponent has a distinct
characteristic: at high SNR, the error exponent is monotonically increasing
with respect to sensor spacing, while at low SNR there is an optimal spacing
for scheduled sensors.


title:
Concavity of the auxiliary function appearing in quantum reliability
  function an classical-quantum channels

abstract:
  Concavity of the auxiliary function which appears in the random coding
exponent as the lower bound of the quantum reliability function for general
quantum states is proven for s between 0 and 1.


title:
Estimation of the Number of Sources in Unbalanced Arrays via Information
  Theoretic Criteria

abstract:
  Estimating the number of sources impinging on an array of sensors is a well
known and well investigated problem. A common approach for solving this problem
is to use an information theoretic criterion, such as Minimum Description
Length (MDL) or the Akaike Information Criterion (AIC). The MDL estimator is
known to be a consistent estimator, robust against deviations from the Gaussian
assumption, and non-robust against deviations from the point source and/or
temporally or spatially white additive noise assumptions. Over the years
several alternative estimation algorithms have been proposed and tested.
Usually, these algorithms are shown, using computer simulations, to have
improved performance over the MDL estimator, and to be robust against
deviations from the assumed spatial model. Nevertheless, these robust
algorithms have high computational complexity, requiring several
multi-dimensional searches.
  In this paper, motivated by real life problems, a systematic approach toward
the problem of robust estimation of the number of sources using information
theoretic criteria is taken. An MDL type estimator that is robust against
deviation from assumption of equal noise level across the array is studied. The
consistency of this estimator, even when deviations from the equal noise level
assumption occur, is proven. A novel low-complexity implementation method
avoiding the need for multi-dimensional searches is presented as well, making
this estimator a favorable choice for practical applications.


title:
Under-approximation of the Greatest Fixpoint in Real-Time System
  Verification

abstract:
  Techniques for the efficient successive under-approximation of the greatest
fixpoint in TCTL formulas can be useful in fast refutation of inevitability
properties and vacuity checking. We first give an integrated algorithmic
framework for both under and over-approximate model-checking. We design the
{\em NZF (Non-Zeno Fairness) predicate}, with a greatest fixpoint formulation,
as a unified framework for the evaluation of formulas like
$\exists\pfrr\eta_1$, $\exists\pfrr\pevt\eta_1$, and $\exists\pevt\pfrr\eta_1$.
We then prove the correctness of a new formulation for the characterization of
the NZF predicate based on zone search and the least fixpoint evaluation. The
new formulation then leads to the design of an evaluation algorithm, with the
capability of successive under-approximation, for $\exists\pfrr\eta_1$,
$\exists\pfrr\pevt\eta_1$, and $\exists\pevt\pfrr\eta_1$. We then present
techniques to efficiently search for the zones and to speed up the
under-approximate evaluation of those three formulas. Our experiments show that
the techniques have significantly enhanced the verification performance against
several benchmarks over exact model-checking.


title:
Under-approximation of the Greatest Fixpoints in Real-Time System
  Verification


title:
Optimal and Suboptimal Finger Selection Algorithms for MMSE Rake
  Receivers in Impulse Radio Ultra-Wideband Systems

abstract:
  Convex relaxations of the optimal finger selection algorithm are proposed for
a minimum mean square error (MMSE) Rake receiver in an impulse radio
ultra-wideband system. First, the optimal finger selection problem is
formulated as an integer programming problem with a non-convex objective
function. Then, the objective function is approximated by a convex function and
the integer programming problem is solved by means of constraint relaxation
techniques. The proposed algorithms are suboptimal due to the approximate
objective function and the constraint relaxation steps. However, they can be
used in conjunction with the conventional finger selection algorithm, which is
suboptimal on its own since it ignores the correlation between multipath
components, to obtain performances reasonably close to that of the optimal
scheme that cannot be implemented in practice due to its complexity. The
proposed algorithms leverage convexity of the optimization problem
formulations, which is the watershed between `easy' and `difficult'
optimization problems.


title: On The Tradeoff Between Two Types of Processing Gain

abstract:
  One of the features characterizing almost every multiple access (MA)
communication system is the processing gain. Through the use of spreading
sequences, the processing gain of Random CDMA systems (RCDMA), is devoted to
both bandwidth expansion and orthogonalization of the signals transmitted by
different users. Another type of multiple access system is Impulse Radio (IR).
In many aspects, IR systems are similar to time division multiple access (TDMA)
systems, and the processing gain of IR systems represents the ratio between the
actual transmission time and the total time between two consecutive
ransmissions (on-plus-off to on ratio). While CDMA systems, which constantly
excite the channel, rely on spreading sequences to orthogonalize the signals
transmitted by different users, IR systems transmit a series of short pulses
and the orthogonalization between the signals transmitted by different users is
achieved by the fact that most of the pulses do not collide with each other at
the receiver.
  In this paper, a general class of MA communication systems that use both
types of processing gain is presented, and both IR and RCDMA systems are
demonstrated to be two special cases of this more general class of systems. The
bit error rate (BER) of several receivers as a function of the ratio between
the two types of processing gain is analyzed and compared under the constraint
that the total processing gain of the system is large and fixed. It is
demonstrated that in non inter-symbol interference (ISI) channels there is no
tradeoff between the two types of processing gain. However, in ISI channels a
tradeoff between the two types of processing gain exists. In addition, the
sub-optimality of RCDMA systems in frequency selective channels is established.


title: Bandit Problems with Side Observations

abstract:
  An extension of the traditional two-armed bandit problem is considered, in
which the decision maker has access to some side information before deciding
which arm to pull. At each time t, before making a selection, the decision
maker is able to observe a random variable X_t that provides some information
on the rewards to be obtained. The focus is on finding uniformly good rules
(that minimize the growth rate of the inferior sampling time) and on
quantifying how much the additional information helps. Various settings are
considered and for each setting, lower bounds on the achievable inferior
sampling time are developed and asymptotically optimal adaptive schemes
achieving these lower bounds are constructed.


title: A Non-Cooperative Power Control Game for Multi-Carrier CDMA Systems

abstract:
  In this work, a non-cooperative power control game for multi-carrier CDMA
systems is proposed. In the proposed game, each user needs to decide how much
power to transmit over each carrier to maximize its overall utility. The
utility function considered here measures the number of reliable bits
transmitted per joule of energy consumed. It is shown that the user's utility
is maximized when the user transmits only on the carrier with the best
"effective channel". The existence and uniqueness of Nash equilibrium for the
proposed game are investigated and the properties of equilibrium are studied.
Also, an iterative and distributed algorithm for reaching the equilibrium (if
it exists) is presented. It is shown that the proposed approach results in a
significant improvement in the total utility achieved at equilibrium compared
to the case in which each user maximizes its utility over each carrier
independently.


title: Harmonic Analysis

abstract:
  This paper describes a method of calculating the transforms, currently
obtained via Fourier and reverse Fourier transforms. The method allows
calculating efficiently the transforms of a signal having an arbitrary
dimension of the digital representation by reducing the transform to a
vector-to-circulant matrix multiplying. There is a connection between harmonic
equations in rectangular and polar coordinate systems. The connection
established here and used to create a very robust iterative algorithm for a
conformal mapping calculation. There is also suggested a new ratio (and an
efficient way of computing it) of two oscillative signals.


title:
The Noncoherent Rician Fading Channel -- Part I : Structure of the
  Capacity-Achieving Input

abstract:
  Transmission of information over a discrete-time memoryless Rician fading
channel is considered where neither the receiver nor the transmitter knows the
fading coefficients. First the structure of the capacity-achieving input
signals is investigated when the input is constrained to have limited
peakedness by imposing either a fourth moment or a peak constraint. When the
input is subject to second and fourth moment limitations, it is shown that the
capacity-achieving input amplitude distribution is discrete with a finite
number of mass points in the low-power regime. A similar discrete structure for
the optimal amplitude is proven over the entire SNR range when there is only a
peak power constraint. The Rician fading with phase-noise channel model, where
there is phase uncertainty in the specular component, is analyzed. For this
model it is shown that, with only an average power constraint, the
capacity-achieving input amplitude is discrete with a finite number of levels.
For the classical average power limited Rician fading channel, it is proven
that the optimal input amplitude distribution has bounded support.


title:
The Noncoherent Rician Fading Channel -- Part II : Spectral Efficiency
  in the Low-Power Regime

abstract:
  Transmission of information over a discrete-time memoryless Rician fading
channel is considered where neither the receiver nor the transmitter knows the
fading coefficients. The spectral-efficiency/bit-energy tradeoff in the
low-power regime is examined when the input has limited peakedness. It is shown
that if a fourth moment input constraint is imposed or the input
peak-to-average power ratio is limited, then in contrast to the behavior
observed in average power limited channels, the minimum bit energy is not
always achieved at zero spectral efficiency. The low-power performance is also
characterized when there is a fixed peak limit that does not vary with the
average power. A new signaling scheme that overlays phase-shift keying on
on-off keying is proposed and shown to be optimally efficient in the low-power
regime.


title:
Learning to automatically detect features for mobile robots using
  second-order Hidden Markov Models

abstract:
  In this paper, we propose a new method based on Hidden Markov Models to
interpret temporal sequences of sensor data from mobile robots to automatically
detect features. Hidden Markov Models have been used for a long time in pattern
recognition, especially in speech recognition. Their main advantages over other
methods (such as neural networks) are their ability to model noisy temporal
signals of variable length. We show in this paper that this approach is well
suited for interpretation of temporal sequences of mobile-robot sensor data. We
present two distinct experiments and results: the first one in an indoor
environment where a mobile robot learns to detect features like open doors or
T-intersections, the second one in an outdoor environment where a different
mobile robot has to identify situations like climbing a hill or crossing a
rock.


title: A Statistical Theory of Chord under Churn

abstract:
  Most earlier studies of Distributed Hash Tables (DHTs) under churn have
either depended on simulations as the primary investigation tool, or on
establishing bounds for DHTs to function. In this paper, we present a complete
analytical study of churn using a master-equation-based approach, used
traditionally in non-equilibrium statistical mechanics to describe steady-state
or transient phenomena. Simulations are used to verify all theoretical
predictions. We demonstrate the application of our methodology to the Chord
system. For any rate of churn and stabilization rates, and any system size, we
accurately predict the fraction of failed or incorrect successor and finger
pointers and show how we can use these quantities to predict the performance
and consistency of lookups under churn. We also discuss briefly how churn may
actually be of different 'types' and the implications this will have for the
functioning of DHTs in general.


title: Extending Design by Contract for Aspect-Oriented Programming

abstract:
  Design by Contract (DbC) and runtime enforcement of program assertions
enables the construction of more robust software. It also enables the
assignment of blame in error reporting. Unfortunately, there is no support for
runtime contract enforcement and blame assignment for Aspect-Oriented
Programming (AOP). Extending DbC to also cover aspects brings forward a
plethora of issues related to the correct order of assertion validation. We
show that there is no generally correct execution sequence of object assertions
and aspect assertions. A further classification of aspects as agnostic,
obedient, or rebellious defines the order of assertion validation that needs to
be followed. We describe the application of this classification in a prototyped
DbC tool for AOP named Cona, where aspects are used for implementing contracts,
and contracts are used for enforcing assertions on aspects.


title:
Capacity Regions and Optimal Power Allocation for Groupwise Multiuser
  Detection

abstract:
  In this paper, optimal power allocation and capacity regions are derived for
GSIC (groupwise successive interference cancellation) systems operating in
multipath fading channels, under imperfect channel estimation conditions. It is
shown that the impact of channel estimation errors on the system capacity is
two-fold: it affects the receivers' performance within a group of users, as
well as the cancellation performance (through cancellation errors). An
iterative power allocation algorithm is derived, based on which it can be shown
that the total required received power is minimized when the groups are ordered
according to their cancellation errors, and the first detected group has the
smallest cancellation error.
  Performace/complexity tradeoff issues are also discussed by directly
comparing the system capacity for different implementations: GSIC with linear
minimum-mean-square error (LMMSE) receivers within the detection groups, GSIC
with matched filter receivers, multicode LMMSE systems, and simple all matched
filter receivers systems.


title: Inferring knowledge from a large semantic network

abstract:
  In this paper, we present a rich semantic network based on a differential
analysis. We then detail implemented measures that take into account common and
differential features between words. In a last section, we describe some
industrial applications.


title: Optimal Union-Find in Constraint Handling Rules

abstract:
  Constraint Handling Rules (CHR) is a committed-choice rule-based language
that was originally intended for writing constraint solvers. In this paper we
show that it is also possible to write the classic union-find algorithm and
variants in CHR. The programs neither compromise in declarativeness nor
efficiency. We study the time complexity of our programs: they match the
almost-linear complexity of the best known imperative implementations. This
fact is illustrated with experimental results.


title: Efficient Computation of the Characteristic Polynomial

abstract:
  This article deals with the computation of the characteristic polynomial of
dense matrices over small finite fields and over the integers. We first present
two algorithms for the finite fields: one is based on Krylov iterates and
Gaussian elimination. We compare it to an improvement of the second algorithm
of Keller-Gehrig. Then we show that a generalization of Keller-Gehrig's third
algorithm could improve both complexity and computational time. We use these
results as a basis for the computation of the characteristic polynomial of
integer matrices. We first use early termination and Chinese remaindering for
dense matrices. Then a probabilistic approach, based on integer minimal
polynomial and Hensel factorization, is particularly well suited to sparse
and/or structured matrices.


title:
Simple extractors via constructions of cryptographic pseudo-random
  generators

abstract:
  Trevisan has shown that constructions of pseudo-random generators from hard
functions (the Nisan-Wigderson approach) also produce extractors. We show that
constructions of pseudo-random generators from one-way permutations (the
Blum-Micali-Yao approach) can be used for building extractors as well. Using
this new technique we build extractors that do not use designs and
polynomial-based error-correcting codes and that are very simple and efficient.
For example, one extractor produces each output bit separately in $O(\log^2 n)$
time. These extractors work for weak sources with min entropy $\lambda n$, for
arbitrary constant $\lambda > 0$, have seed length $O(\log^2 n)$, and their
output length is $\approx n^{\lambda/3}$.


title:
Geometric Complexity III: on deciding positivity of
  Littlewood-Richardson coefficients

abstract:
  We point out that the remarkable Knutson and Tao Saturation Theorem and
polynomial time algorithms for LP have together an important and immediate
consequence in Geometric Complexity Theory. The problem of deciding positivity
of Littlewood-Richardson coefficients for GLn(C) belongs to P. Furthermore, the
algorithm is strongly polynomial.
  The main goal of this article is to explain the significance of this result
in the context of Geometric Complexity Theory. Furthermore, it is also
conjectured that an analogous result holds for arbitrary symmetrizable
Kac-Moody algebras.


title:
Ontology-Based Users & Requests Clustering in Customer Service
  Management System

abstract:
  Customer Service Management is one of major business activities to better
serve company customers through the introduction of reliable processes and
procedures. Today this kind of activities is implemented through e-services to
directly involve customers into business processes. Traditionally Customer
Service Management involves application of data mining techniques to discover
usage patterns from the company knowledge memory. Hence grouping of
customers/requests to clusters is one of major technique to improve the level
of company customization. The goal of this paper is to present an efficient for
implementation approach for clustering users and their requests. The approach
uses ontology as knowledge representation model to improve the semantic
interoperability between units of the company and customers. Some fragments of
the approach tested in an industrial company are also presented in the paper.


title: Multi-document Biography Summarization

abstract:
  In this paper we describe a biography summarization system using sentence
classification and ideas from information retrieval. Although the individual
techniques are not new, assembling and applying them to generate multi-document
biographies is new. Our system was evaluated in DUC2004. It is among the top
performers in task 5-short summaries focused by person questions.


title: Data Mining for Actionable Knowledge: A Survey

abstract:
  The data mining process consists of a series of steps ranging from data
cleaning, data selection and transformation, to pattern evaluation and
visualization. One of the central problems in data mining is to make the mined
patterns or knowledge actionable. Here, the term actionable refers to the mined
patterns suggest concrete and profitable actions to the decision-maker. That
is, the user can do something to bring direct benefits (increase in profits,
reduction in cost, improvement in efficiency, etc.) to the organization's
advantage. However, there has been written no comprehensive survey available on
this topic. The goal of this paper is to fill the void.
  In this paper, we first present two frameworks for mining actionable
knowledge that are inexplicitly adopted by existing research methods. Then we
try to situate some of the research on this topic from two different
viewpoints: 1) data mining tasks and 2) adopted framework. Finally, we specify
issues that are either not addressed or insufficiently studied yet and conclude
the paper.


title: An Information Network Overlay Architecture for the NSDL

abstract:
  We describe the underlying data model and implementation of a new
architecture for the National Science Digital Library (NSDL) by the Core
Integration Team (CI). The architecture is based on the notion of an
information network overlay. This network, implemented as a graph of digital
objects in a Fedora repository, allows the representation of multiple
information entities and their relationships. The architecture provides the
framework for contextualization and reuse of resources, which we argue is
essential for the utility of the NSDL as a tool for teaching and learning.


title:
A Tree Search Method for Iterative Decoding of Underdetermined Multiuser
  Systems

abstract:
  Application of the turbo principle to multiuser decoding results in an
exchange of probability distributions between two sets of constraints. Firstly,
constraints imposed by the multiple-access channel, and secondly, individual
constraints imposed by each users' error control code. A-posteriori probability
computation for the first set of constraints is prohibitively complex for all
but a small number of users. Several lower complexity approaches have been
proposed in the literature. One class of methods is based on linear filtering
(e.g. LMMSE). A more recent approach is to compute approximations to the
posterior probabilities by marginalising over a subset of sequences (list
detection). Most of the list detection methods are restricted to non-singular
systems. In this paper, we introduce a transformation that permits application
of standard tree-search methods to underdetermined systems. We find that the
resulting tree-search based receiver outperforms existing methods.


title: A Group-Theoretic Approach to the WSSUS Pulse Design Problem

abstract:
  We consider the pulse design problem in multicarrier transmission where the
pulse shapes are adapted to the second order statistics of the WSSUS channel.
Even though the problem has been addressed by many authors analytical insights
are rather limited. First we show that the problem is equivalent to the pure
state channel fidelity in quantum information theory. Next we present a new
approach where the original optimization functional is related to an eigenvalue
problem for a pseudo differential operator by utilizing unitary representations
of the Weyl--Heisenberg group.A local approximation of the operator for
underspread channels is derived which implicitly covers the concepts of pulse
scaling and optimal phase space displacement. The problem is reformulated as a
differential equation and the optimal pulses occur as eigenstates of the
harmonic oscillator Hamiltonian. Furthermore this operator--algebraic approach
is extended to provide exact solutions for different classes of scattering
environments.


title: Orchestrating Metadata Enhancement Services: Introducing Lenny

abstract:
  Harvested metadata often suffers from uneven quality to the point that
utility is compromised. Although some aggregators have developed methods for
evaluating and repairing specific metadata problems, it has been unclear how
these methods might be scaled into services that can be used within an
automated production environment. The National Science Digital Library (NSDL),
as part of its work with INFOMINE, has developed a model of ser-vice
interaction that enables loosely-coupled third party services to provide
metadata enhancements to a central repository, with interactions orchestrated
by a centralized software application.


title:
Towards Automated Integration of Guess and Check Programs in Answer Set
  Programming: A Meta-Interpreter and Applications

abstract:
  Answer set programming (ASP) with disjunction offers a powerful tool for
declaratively representing and solving hard problems. Many NP-complete problems
can be encoded in the answer set semantics of logic programs in a very concise
and intuitive way, where the encoding reflects the typical "guess and check"
nature of NP problems: The property is encoded in a way such that polynomial
size certificates for it correspond to stable models of a program. However, the
problem-solving capacity of full disjunctive logic programs (DLPs) is beyond
NP, and captures a class of problems at the second level of the polynomial
hierarchy. While these problems also have a clear "guess and check" structure,
finding an encoding in a DLP reflecting this structure may sometimes be a
non-obvious task, in particular if the "check" itself is a coNP-complete
problem; usually, such problems are solved by interleaving separate guess and
check programs, where the check is expressed by inconsistency of the check
program. In this paper, we present general transformations of head-cycle free
(extended) disjunctive logic programs into stratified and positive (extended)
disjunctive logic programs based on meta-interpretation techniques. The answer
sets of the original and the transformed program are in simple correspondence,
and, moreover, inconsistency of the original program is indicated by a
designated answer set of the transformed program. Our transformations
facilitate the integration of separate "guess" and "check" programs, which are
often easy to obtain, automatically into a single disjunctive logic program.
Our results complement recent results on meta-interpretation in ASP, and extend
methods and techniques for a declarative "guess and check" problem solving
paradigm through ASP.


title: Space Frequency Codes from Spherical Codes

abstract:
  A new design method for high rate, fully diverse ('spherical') space
frequency codes for MIMO-OFDM systems is proposed, which works for arbitrary
numbers of antennas and subcarriers. The construction exploits a differential
geometric connection between spherical codes and space time codes. The former
are well studied e.g. in the context of optimal sequence design in CDMA
systems, while the latter serve as basic building blocks for space frequency
codes. In addition a decoding algorithm with moderate complexity is presented.
This is achieved by a lattice based construction of spherical codes, which
permits lattice decoding algorithms and thus offers a substantial reduction of
complexity.


title: Clever Search: A WordNet Based Wrapper for Internet Search Engines

abstract:
  This paper presents an approach to enhance search engines with information
about word senses available in WordNet. The approach exploits information about
the conceptual relations within the lexical-semantic net. In the wrapper for
search engines presented, WordNet information is used to specify user's request
or to classify the results of a publicly available web search engine, like
google, yahoo, etc.


title:
Faults and Improvements of an Enhanced Remote User Authentication Scheme
  Using Smart Cards

abstract:
  In 2000, Hwang and Li proposed a remote user authentication scheme using
smart cards to solve the problems of Lamport scheme. Later, Chan- Chang, Shen-
Lin- Hwang and then Chang-Hwang pointed out some attacks on Hwang –
Li’s scheme. In 2003, Shen, Lin and Hwang also proposed a modified scheme
to remove these attacks. In the same year, Leung-Cheng-Fong-Chan showed that
modified scheme proposed by Shen-Lin-Hwang is still insecure. In 2004, Awasthi
and Lal enhanced Shen-Lin-Hwang’s scheme to overcome its security
pitfalls. This paper analyses that the user U/smart card does not provide
complete information for the execution and proper running of the login phase of
the Awasthi- Lal’s scheme. Furthermore, this paper also modifies the
Awasthi- Lal’s scheme for the proper functioning.


title: Information estimations and analysis of structures

abstract:
  In this paper have written the results of the information analysis of
structures. The obtained information estimation (IE) are based on an entropy
measure of C. Shannon. Obtained IE is univalent both for the non-isomorphic and
for the isomorphic graphs, algorithmically, it is asymptotically steady and has
vector character. IE can be used for the solution of the problems ranking of
structures by the preference, the evaluation of the structurization of subject
area, the solution of the problems of structural optimization. Information
estimations and method of the information analysis of structures it can be used
in many fields of knowledge (Electrical Systems and Circuit, Image recognition,
Computer technology, Databases and Bases of knowledge, Organic chemistry,
Biology and others) and it can be base for the structure calculus.


title: Issues in Exploiting GermaNet as a Resource in Real Applications

abstract:
  This paper reports about experiments with GermaNet as a resource within
domain specific document analysis. The main question to be answered is: How is
the coverage of GermaNet in a specific domain? We report about results of a
field test of GermaNet for analyses of autopsy protocols and present a sketch
about the integration of GermaNet inside XDOC. Our remarks will contribute to a
GermaNet user's wish list.


title: Stochastic Iterative Decoders

abstract:
  This paper presents a stochastic algorithm for iterative error control
decoding. We show that the stochastic decoding algorithm is an approximation of
the sum-product algorithm. When the code's factor graph is a tree, as with
trellises, the algorithm approaches maximum a-posteriori decoding. We also
demonstrate a stochastic approximations to the alternative update rule known as
successive relaxation. Stochastic decoders have very simple digital
implementations which have almost no RAM requirements. We present example
stochastic decoders for a trellis-based Hamming code, and for a Block Turbo
code constructed from Hamming codes.


title:
A complexity-regularized quantization approach to nonlinear
  dimensionality reduction

abstract:
  We consider the problem of nonlinear dimensionality reduction: given a
training set of high-dimensional data whose ``intrinsic'' low dimension is
assumed known, find a feature extraction map to low-dimensional space, a
reconstruction map back to high-dimensional space, and a geometric description
of the dimension-reduced data as a smooth manifold. We introduce a
complexity-regularized quantization approach for fitting a Gaussian mixture
model to the training set via a Lloyd algorithm. Complexity regularization
controls the trade-off between adaptation to the local shape of the underlying
manifold and global geometric consistency. The resulting mixture model is used
to design the feature extraction and reconstruction maps and to define a
Riemannian metric on the low-dimensional data. We also sketch a proof of
consistency of our scheme for the purposes of estimating the unknown underlying
pdf of high-dimensional data.


title: Multi-Vehicle Cooperative Control Using Mixed Integer Linear Programming

abstract:
  We present methods to synthesize cooperative strategies for multi-vehicle
control problems using mixed integer linear programming. Complex multi-vehicle
control problems are expressed as mixed logical dynamical systems. Optimal
strategies for these systems are then solved for using mixed integer linear
programming. We motivate the methods on problems derived from an adversarial
game between two teams of robots called RoboFlag. We assume the strategy for
one team is fixed and governed by state machines. The strategy for the other
team is generated using our methods. Finally, we perform an average case
computational complexity study on our approach.


title: Transforming Business Rules Into Natural Language Text

abstract:
  The aim of the project presented in this paper is to design a system for an
NLG architecture, which supports the documentation process of eBusiness models.
A major task is to enrich the formal description of an eBusiness model with
additional information needed in an NLG task.


title: Corpus based Enrichment of GermaNet Verb Frames

abstract:
  Lexical semantic resources, like WordNet, are often used in real applications
of natural language document processing. For example, we integrated GermaNet in
our document suite XDOC of processing of German forensic autopsy protocols. In
addition to the hypernymy and synonymy relation, we want to adapt GermaNet's
verb frames for our analysis. In this paper we outline an approach for the
domain related enrichment of GermaNet verb frames by corpus based syntactic and
co-occurred data analyses of real documents.


title: Context Related Derivation of Word Senses

abstract:
  Real applications of natural language document processing are very often
confronted with domain specific lexical gaps during the analysis of documents
of a new domain. This paper describes an approach for the derivation of domain
specific concepts for the extension of an existing ontology. As resources we
need an initial ontology and a partially processed corpus of a domain. We
exploit the specific characteristic of the sublanguage in the corpus. Our
approach is based on syntactical structures (noun phrases) and compound
analyses to extract information required for the extension of GermaNet's
lexical resources.


title: Transforming and Enriching Documents for the Semantic Web

abstract:
  We suggest to employ techniques from Natural Language Processing (NLP) and
Knowledge Representation (KR) to transform existing documents into documents
amenable for the Semantic Web. Semantic Web documents have at least part of
their semantics and pragmatics marked up explicitly in both a machine
processable as well as human readable manner. XML and its related standards
(XSLT, RDF, Topic Maps etc.) are the unifying platform for the tools and
methodologies developed for different application scenarios.


title: Some Extensions of Gallager's Method to General Sources and Channels

abstract:
  The Gallager bound is well known in the area of channel coding. However, most
discussions about it mainly focus on its applications to memoryless channels.
We show in this paper that the bounds obtained by Gallager's method are very
tight even for general sources and channels that are defined in the
information-spectrum theory. Our method is mainly based on the estimations of
error exponents in those bounds, and by these estimations we proved the direct
part of the Slepian-Wolf theorem and channel coding theorem for general sources
and channels.


title: Directed Threshold Multi – Signature Scheme without SDC

abstract:
  In this paper, we propose a Directed threshold multisignature scheme without
SDC. This signature scheme is applicable when the message is sensitive to the
signature receiver; and the signatures are generated by the cooperation of a
number of people from a given group of senders. In this scheme, any malicious
set of signers cannot impersonate any other set of signers to forge the
signatures. In case of forgery, it is possible to trace the signing set.


title: Shawn: A new approach to simulating wireless sensor networks

abstract:
  We consider the simulation of wireless sensor networks (WSN) using a new
approach. We present Shawn, an open-source discrete-event simulator that has
considerable differences to all other existing simulators. Shawn is very
powerful in simulating large scale networks with an abstract point of view. It
is, to the best of our knowledge, the first simulator to support generic
high-level algorithms as well as distributed protocols on exactly the same
underlying networks.


title: Asymptotic Log-loss of Prequential Maximum Likelihood Codes

abstract:
  We analyze the Dawid-Rissanen prequential maximum likelihood codes relative
to one-parameter exponential family models M. If data are i.i.d. according to
an (essentially) arbitrary P, then the redundancy grows at rate c/2 ln n. We
show that c=v1/v2, where v1 is the variance of P, and v2 is the variance of the
distribution m* in M that is closest to P in KL divergence. This shows that
prequential codes behave quite differently from other important universal codes
such as the 2-part MDL, Shtarkov and Bayes codes, for which c=1. This behavior
is undesirable in an MDL model selection setting.


title: Model-Checking Problems as a Basis for Parameterized Intractability

abstract:
  Most parameterized complexity classes are defined in terms of a parameterized
version of the Boolean satisfiability problem (the so-called weighted
satisfiability problem). For example, Downey and Fellow's W-hierarchy is of
this form. But there are also classes, for example, the A-hierarchy, that are
more naturally characterised in terms of model-checking problems for certain
fragments of first-order logic.
  Downey, Fellows, and Regan were the first to establish a connection between
the two formalisms by giving a characterisation of the W-hierarchy in terms of
first-order model-checking problems. We improve their result and then prove a
similar correspondence between weighted satisfiability and model-checking
problems for the A-hierarchy and the W^*-hierarchy. Thus we obtain very uniform
characterisations of many of the most important parameterized complexity
classes in both formalisms.
  Our results can be used to give new, simple proofs of some of the core
results of structural parameterized complexity theory.


title: Neural network ensembles: Evaluation of aggregation algorithms

abstract:
  Ensembles of artificial neural networks show improved generalization
capabilities that outperform those of single networks. However, for aggregation
to be effective, the individual networks must be as accurate and diverse as
possible. An important problem is, then, how to tune the aggregate members in
order to have an optimal compromise between these two conflicting conditions.
We present here an extensive evaluation of several algorithms for ensemble
construction, including new proposals and comparing them with standard methods
in the literature. We also discuss a potential problem with sequential
aggregation algorithms: the non-frequent but damaging selection through their
heuristics of particularly bad ensemble members. We introduce modified
algorithms that cope with this problem by allowing individual weighting of
aggregate members. Our algorithms and their weighted modifications are
favorably tested against other methods in the literature, producing a sensible
improvement in performance on most of the standard statistical databases used
as benchmarks.


title: Identification of complex systems in the basis of wavelets

abstract:
  In this paper is proposed the method of the identification of complex dynamic
systems. Method can be used for the identification of linear and nonlinear
complex dynamic systems for the determined or stochastic signals at the inputs
and the outputs. It is proposed to use a basis of wavelets for obtaining the
impulse transient function (ITF) of system. ITF is considered in the form of
surface in the 3D space. Are given the results of experiments on the
identification of systems in the basis of wavelets.


title: Scientific Data Management in the Coming Decade

abstract:
  This is a thought piece on data-intensive science requirements for databases
and science centers. It argues that peta-scale datasets will be housed by
science centers that provide substantial storage and processing for scientists
who access the data via smart notebooks. Next-generation science instruments
and simulations will generate these peta-scale datasets. The need to publish
and share data and the need for generic analysis and visualization tools will
finally create a convergence on common metadata standards. Database systems
will be judged by their support of these metadata standards and by their
ability to manage and access peta-scale datasets. The procedural
stream-of-bytes-file-centric approach to data analysis is both too cumbersome
and too serial for such large datasets. Non-procedural query and analysis of
schematized self-describing data is both easier to use and allows much more
parallelism.


title:
Performance Considerations for Gigabyte per Second Transcontinental
  Disk-to-Disk File Transfers

abstract:
  Moving data from CERN to Pasadena at a gigabyte per second using the next
generation Internet requires good networking and good disk IO. Ten Gbps
Ethernet and OC192 links are in place, so now it is simply a matter of
programming. This report describes our preliminary work and measurements in
configuring the disk subsystem for this effort. Using 24 SATA disks at each
endpoint we are able to locally read and write an NTFS volume is striped across
24 disks at 1.2 GBps. A 32-disk stripe delivers 1.7 GBps. Experiments on higher
performance and higher-capacity systems deliver up to 3.5 GBps.


title: TerraServer SAN-Cluster Architecture and Operations Experience

abstract:
  Microsoft TerraServer displays aerial, satellite, and to-pographic images of
the earth in a SQL database available via the Internet. It is one of the most
popular online at-lases, presenting seventeen terabytes of image data from the
United States Geological Survey (USGS). Initially de-ployed in 1998, the system
demonstrated the scalability of PC hardware and software - Windows and SQL
Server - on a single, mainframe-class processor. In September 2000, the
back-end database application was migrated to 4-node active/passive cluster
connected to an 18 terabyte Storage Area Network (SAN). The new configuration
was designed to achieve 99.99% availability for the back-end application. This
paper describes the hardware and software components of the TerraServer Cluster
and SAN, and describes our experience in configuring and operating this system
for three years. Not surprisingly, the hardware and architecture delivered
better than four-9's of availability, but operations mistakes delivered
three-9's.


title:
Where the Rubber Meets the Sky: Bridging the Gap between Databases and
  Science

abstract:
  Scientists in all domains face a data avalanche - both from better
instruments and from improved simulations. We believe that computer science
tools and computer scientists are in a position to help all the sciences by
building tools and developing techniques to manage, analyze, and visualize
peta-scale scientific information. This article is summarizes our experiences
over the last seven years trying to bridge the gap between database technology
and the needs of the astronomy community in building the World-Wide Telescope.


title: Sequential File Programming Patterns and Performance with .NET

abstract:
  Programming patterns for sequential file access in the .NET Framework are
described and the performance is measured. The default behavior provides
excellent performance on a single disk - 50 MBps both reading and writing.
Using large request sizes and doing file pre-allocation when possible have
quantifiable benefits. When one considers disk arrays, .NET unbuffered IO
delivers 800 MBps on a 16-disk array, but buffered IO delivers about 12% of
that performance. Consequently, high-performance file and database utilities
are still forced to use unbuffered IO for maximum sequential performance. The
report is accompanied by downloadable source code that demonstrates the
concepts and code that was used to obtain these measurements.


title: Amazons is PSPACE-complete

abstract:
  Amazons is a board game which combines elements of Chess and Go. It has
become popular in recent years, and has served as a useful platform for both
game-theoretic study and AI games research. Buro showed that simple Amazons
endgames are NP-equivalent, leaving the complexity of the general case as an
open problem.
  We settle this problem, by showing that deciding the outcome of an n x n
Amazons position is PSPACE-hard. We give a reduction from one of the
PSPACE-complete two-player formula games described by Schaefer. Since the
number of moves in an Amazons game is polynomially bounded (unlike Chess and
Go), Amazons is in PSPACE. It is thus on a par with other two-player,
bounded-move, perfect-information games such as Hex, Othello, and Kayles. Our
construction also provides an alternate proof that simple Amazons endgames are
NP-equivalent.
  Our reduction uses a number of amazons polynomial in the input formula
length; a remaining open problem is the complexity of Amazons when only a
constant number of amazons is used.


title: On the asymptotic behavior of some Algorithms

abstract:
  A simple approach is presented to study the asymptotic behavior of some
algorithms with an underlying tree structure. It is shown that some asymptotic
oscillating behaviors can be precisely analyzed without resorting to complex
analysis techniques as it is usually done in this context. A new explicit
representation of periodic functions involved is obtained at the same time.


title: Can Computer Algebra be Liberated from its Algebraic Yoke ?

abstract:
  So far, the scope of computer algebra has been needlessly restricted to exact
algebraic methods. Its possible extension to approximate analytical methods is
discussed. The entangled roles of functional analysis and symbolic programming,
especially the functional and transformational paradigms, are put forward. In
the future, algebraic algorithms could constitute the core of extended symbolic
manipulation systems including primitives for symbolic approximations.


title: Stability Analysis for Regularized Least Squares Regression

abstract:
  We discuss stability for a class of learning algorithms with respect to noisy
labels. The algorithms we consider are for regression, and they involve the
minimization of regularized risk functionals, such as L(f) := 1/N sum_i
(f(x_i)-y_i)^2+ lambda ||f||_H^2. We shall call the algorithm `stable' if, when
y_i is a noisy version of f*(x_i) for some function f* in H, the output of the
algorithm converges to f* as the regularization term and noise simultaneously
vanish. We consider two flavors of this problem, one where a data set of N
points remains fixed, and the other where N -> infinity. For the case where N
-> infinity, we give conditions for convergence to f_E (the function which is
the expectation of y(x) for each x), as lambda -> 0. For the fixed N case, we
describe the limiting 'non-noisy', 'non-regularized' function f*, and give
conditions for convergence. In the process, we develop a set of tools for
dealing with functionals such as L(f), which are applicable to many other
problems in learning theory.


title: Estimating mutual information and multi--information in large networks

abstract:
  We address the practical problems of estimating the information relations
that characterize large networks. Building on methods developed for analysis of
the neural code, we show that reliable estimates of mutual information can be
obtained with manageable computational effort. The same methods allow
estimation of higher order, multi--information terms. These ideas are
illustrated by analyses of gene expression, financial markets, and consumer
preferences. In each case, information theoretic measures correlate with
independent, intuitive measures of the underlying structures in the system.


title: When Database Systems Meet the Grid

abstract:
  We illustrate the benefits of combining database systems and Grid
technologies for data-intensive applications. Using a cluster of SQL servers,
we reimplemented an existing Grid application that finds galaxy clusters in a
large astronomical database. The SQL implementation runs an order of magnitude
faster than the earlier Tcl-C-file-based implementation. We discuss why and how
Grid applications can take advantage of database systems.


title:
A Price-Anticipating Resource Allocation Mechanism for Distributed
  Shared Clusters

abstract:
  In this paper we formulate the fixed budget resource allocation game to
understand the performance of a distributed market-based resource allocation
system. Multiple users decide how to distribute their budget (bids) among
multiple machines according to their individual preferences to maximize their
individual utility. We look at both the efficiency and the fairness of the
allocation at the equilibrium, where fairness is evaluated through the measures
of utility uniformity and envy-freeness. We show analytically and through
simulations that despite being highly decentralized, such a system converges
quickly to an equilibrium and unlike the social optimum that achieves high
efficiency but poor fairness, the proposed allocation scheme achieves a nice
balance of high degrees of efficiency and fairness at the equilibrium.


title: Population Sizing for Genetic Programming Based Upon Decision Making

abstract:
  This paper derives a population sizing relationship for genetic programming
(GP). Following the population-sizing derivation for genetic algorithms in
Goldberg, Deb, and Clark (1992), it considers building block decision making as
a key facet. The analysis yields a GP-unique relationship because it has to
account for bloat and for the fact that GP solutions often use subsolution
multiple times. The population-sizing relationship depends upon tree size,
solution complexity, problem difficulty and building block expression
probability. The relationship is used to analyze and empirically investigate
population sizing for three model GP problems named ORDER, ON-OFF and LOUD.
These problems exhibit bloat to differing extents and differ in whether their
solutions require the use of a building block multiple times.


title:
Oiling the Wheels of Change: The Role of Adaptive Automatic Problem
  Decomposition in Non--Stationary Environments

abstract:
  Genetic algorithms (GAs) that solve hard problems quickly, reliably and
accurately are called competent GAs. When the fitness landscape of a problem
changes overtime, the problem is called non--stationary, dynamic or
time--variant problem. This paper investigates the use of competent GAs for
optimizing non--stationary optimization problems. More specifically, we use an
information theoretic approach based on the minimum description length
principle to adaptively identify regularities and substructures that can be
exploited to respond quickly to changes in the environment. We also develop a
special type of problems with bounded difficulties to test non--stationary
optimization problems. The results provide new insights into non-stationary
optimization problems and show that a search algorithm which automatically
identifies and exploits possible decompositions is more robust and responds
quickly to changes than a simple genetic algorithm.


title: Sub-Structural Niching in Non-Stationary Environments

abstract:
  Niching enables a genetic algorithm (GA) to maintain diversity in a
population. It is particularly useful when the problem has multiple optima
where the aim is to find all or as many as possible of these optima. When the
fitness landscape of a problem changes overtime, the problem is called
non--stationary, dynamic or time--variant problem. In these problems, niching
can maintain useful solutions to respond quickly, reliably and accurately to a
change in the environment. In this paper, we present a niching method that
works on the problem substructures rather than the whole solution, therefore it
has less space complexity than previously known niching mechanisms. We show
that the method is responding accurately when environmental changes occur.


title: Sub-structural Niching in Estimation of Distribution Algorithms

abstract:
  We propose a sub-structural niching method that fully exploits the problem
decomposition capability of linkage-learning methods such as the estimation of
distribution algorithms and concentrate on maintaining diversity at the
sub-structural level. The proposed method consists of three key components: (1)
Problem decomposition and sub-structure identification, (2) sub-structure
fitness estimation, and (3) sub-structural niche preservation. The
sub-structural niching method is compared to restricted tournament selection
(RTS)--a niching method used in hierarchical Bayesian optimization
algorithm--with special emphasis on sustained preservation of multiple global
solutions of a class of boundedly-difficult, additively-separable multimodal
problems. The results show that sub-structural niching successfully maintains
multiple global optima over large number of generations and does so with
significantly less population than RTS. Additionally, the market share of each
of the niche is much closer to the expected level in sub-structural niching
when compared to RTS.


title: Idempotents, Mattson-Solomon Polynomials and Binary LDPC codes

abstract:
  We show how to construct an algorithm to search for binary idempotents which
may be used to construct binary LDPC codes. The algorithm, which allows control
of the key properties of sparseness, code rate and minimum distance, is
constructed in the Mattson-Solomon domain. Some of the new codes, found by
using this technique, are displayed.


title: EPspectra: A Formal Toolkit for Developing DSP Software Applications

abstract:
  The software approach to developing Digital Signal Processing (DSP)
applications brings some great features such as flexibility, re-usability of
resources and easy upgrading of applications. However, it requires long and
tedious tests and verification phases because of the increasing complexity of
the software. This implies the need of a software programming environment
capable of putting together DSP modules and providing facilities to debug,
verify and validate the code. The objective of the work is to provide such
facilities as simulation and verification for developing DSP software
applications. This led us to develop an extension toolkit, Epspectra, built
upon Pspectra, one of the first toolkits available to design basic software
radio applications on standard PC workstations. In this paper, we first present
Epspectra, an Esterel-based extension of Pspectra that makes the design and
implementation of portable DSP applications easier. It allows drastic reduction
of testing and verification time while requiring relatively little expertise in
formal verification methods. Second, we demonstrate the use of Epspectra,
taking as an example the radio interface part of a GSM base station. We also
present the verification procedures for the three safety properties of the
implementation programs which have complex control-paths. These have to obey
strict scheduling rules. In addition, Epspectra achieves the verification of
the targeted application since the same model is used for the executable code
generation and for the formal verification.


title: Quantum mechanics can provide unbiased result

abstract:
  Getting an unbiased result is a remarkably long standing problem of
collective observation/measurement. It is pointed out that quantum coin tossing
can generate unbiased result defeating dishonesty.


title: Markets are Dead, Long Live Markets

abstract:
  Researchers have long proposed using economic approaches to resource
allocation in computer systems. However, few of these proposals became
operational, let alone commercial. Questions persist about the economic
approach regarding its assumptions, value, applicability, and relevance to
system design. The goal of this paper is to answer these questions. We find
that market-based resource allocation is useful, and more importantly, that
mechanism design and system design should be integrated to produce systems that
are both economically and computationally efficient.


title: aDORe: a modular, standards-based Digital Object Repository

abstract:
  This paper describes the aDORe repository architecture, designed and
implemented for ingesting, storing, and accessing a vast collection of Digital
Objects at the Research Library of the Los Alamos National Laboratory. The
aDORe architecture is highly modular and standards-based. In the architecture,
the MPEG-21 Digital Item Declaration Language is used as the XML-based format
to represent Digital Objects that can consist of multiple datastreams as Open
Archival Information System Archival Information Packages (OAIS AIPs).Through
an ingestion process, these OAIS AIPs are stored in a multitude of autonomous
repositories. A Repository Index keeps track of the creation and location of
all the autonomous repositories, whereas an Identifier Locator registers in
which autonomous repository a given Digital Object or OAIS AIP resides. A
front-end to the complete environment, the OAI-PMH Federator, is introduced for
requesting OAIS Dissemination Information Packages (OAIS DIPs). These OAIS DIPs
can be the stored OAIS AIPs themselves, or transformations thereof. This
front-end allows OAI-PMH harvesters to recurrently and selectively collect
batches of OAIS DIPs from aDORe, and hence to create multiple, parallel
services using the collected objects. Another front-end, the OpenURL Resolver,
is introduced for requesting OAIS Result Sets. An OAIS Result Set is a
dissemination of an individual Digital Object or of its constituent
datastreams. Both front-ends make use of an MPEG-21 Digital Item Processing
Engine to apply services to OAIS AIPs, Digital Objects, or constituent
datastreams that were specified in a dissemination request.


title:
Scalability of Genetic Programming and Probabilistic Incremental Program
  Evolution

abstract:
  This paper discusses scalability of standard genetic programming (GP) and the
probabilistic incremental program evolution (PIPE). To investigate the need for
both effective mixing and linkage learning, two test problems are considered:
ORDER problem, which is rather easy for any recombination-based GP, and TRAP or
the deceptive trap problem, which requires the algorithm to learn interactions
among subsets of terminals. The scalability results show that both GP and PIPE
scale up polynomially with problem size on the simple ORDER problem, but they
both scale up exponentially on the deceptive problem. This indicates that while
standard recombination is sufficient when no interactions need to be
considered, for some problems linkage learning is necessary. These results are
in agreement with the lessons learned in the domain of binary-string genetic
algorithms (GAs). Furthermore, the paper investigates the effects of
introducing utnnecessary and irrelevant primitives on the performance of GP and
PIPE.


title: Fixed Type Theorems

abstract: This submission has been withdrawn at the request of the author.


title: Logic Column 11: The Finite and the Infinite in Temporal Logic

abstract:
  This article examines the interpretation of the LTL temporal operators over
finite and infinite sequences. This is used as the basis for deriving a sound
and complete axiomatization for Caret, a recent temporal logic for reasoning
about programs with nested procedure calls and returns.


title: On Dynamic Range Reporting in One Dimension

abstract:
  We consider the problem of maintaining a dynamic set of integers and
answering queries of the form: report a point (equivalently, all points) in a
given interval. Range searching is a natural and fundamental variant of integer
search, and can be solved using predecessor search. However, for a RAM with
w-bit words, we show how to perform updates in O(lg w) time and answer queries
in O(lglg w) time. The update time is identical to the van Emde Boas structure,
but the query time is exponentially faster. Existing lower bounds show that
achieving our query time for predecessor search requires doubly-exponentially
slower updates. We present some arguments supporting the conjecture that our
solution is optimal.
  Our solution is based on a new and interesting recursion idea which is "more
extreme" that the van Emde Boas recursion. Whereas van Emde Boas uses a simple
recursion (repeated halving) on each path in a trie, we use a nontrivial, van
Emde Boas-like recursion on every such path. Despite this, our algorithm is
quite clean when seen from the right angle. To achieve linear space for our
data structure, we solve a problem which is of independent interest. We develop
the first scheme for dynamic perfect hashing requiring sublinear space. This
gives a dynamic Bloomier filter (an approximate storage scheme for sparse
vectors) which uses low space. We strengthen previous lower bounds to show that
these results are optimal.


title: Pseudo-Codewords of Cycle Codes via Zeta Functions

abstract:
  Cycle codes are a special case of low-density parity-check (LDPC) codes and
as such can be decoded using an iterative message-passing decoding algorithm on
the associated Tanner graph. The existence of pseudo-codewords is known to
cause the decoding algorithm to fail in certain instances. In this paper, we
draw a connection between pseudo-codewords of cycle codes and the so-called
edge zeta function of the associated normal graph and show how the Newton
polyhedron of the zeta function equals the fundamental cone of the code, which
plays a crucial role in characterizing the performance of iterative decoding
algorithms.


title: Multiobjective hBOA, Clustering, and Scalability

abstract:
  This paper describes a scalable algorithm for solving multiobjective
decomposable problems by combining the hierarchical Bayesian optimization
algorithm (hBOA) with the nondominated sorting genetic algorithm (NSGA-II) and
clustering in the objective space. It is first argued that for good
scalability, clustering or some other form of niching in the objective space is
necessary and the size of each niche should be approximately equal.
Multiobjective hBOA (mohBOA) is then described that combines hBOA, NSGA-II and
clustering in the objective space. The algorithm mohBOA differs from the
multiobjective variants of BOA and hBOA proposed in the past by including
clustering in the objective space and allocating an approximately equally sized
portion of the population to each cluster. The algorithm mohBOA is shown to
scale up well on a number of problems on which standard multiobjective
evolutionary algorithms perform poorly.


title:
Near Maximum-Likelihood Performance of Some New Cyclic Codes Constructed
  in the Finite-Field Transform Domain

abstract:
  It is shown that some well-known and some new cyclic codes with orthogonal
parity-check equations can be constructed in the finite-field transform domain.
It is also shown that, for some binary linear cyclic codes, the performance of
the iterative decoder can be improved by substituting some of the dual code
codewords in the parity-check matrix with other dual code codewords formed from
linear combinations. This technique can bring the performance of a code closer
to its maximum-likelihood performance, which can be derived from the erroneous
decoded codeword whose euclidean distance with the respect to the received
block is smaller than that of the correct codeword. For (63,37), (93,47) and
(105,53) cyclic codes, the maximum-likelihood performance is realised with this
technique.


title: Improved Iterative Decoding for Perpendicular Magnetic Recording

abstract:
  An algorithm of improving the performance of iterative decoding on
perpendicular magnetic recording is presented. This algorithm follows on the
authors' previous works on the parallel and serial concatenated turbo codes and
low-density parity-check codes. The application of this algorithm with
signal-to-noise ratio mismatch technique shows promising results in the
presence of media noise. We also show that, compare to the standard iterative
decoding algorithm, an improvement of within one order of magnitude can be
achieved.


title: GF(2^m) Low-Density Parity-Check Codes Derived from Cyclotomic Cosets

abstract:
  Based on the ideas of cyclotomic cosets, idempotents and Mattson-Solomon
polynomials, we present a new method to construct GF(2^m), where m>0 cyclic
low-density parity-check codes. The construction method produces the dual code
idempotent which is used to define the parity-check matrix of the low-density
parity-check code. An interesting feature of this construction method is the
ability to increment the code dimension by adding more idempotents and so
steadily decrease the sparseness of the parity-check matrix. We show that the
constructed codes can achieve performance very close to the
sphere-packing-bound constrained for binary transmission.


title: The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs

abstract:
  In this paper we examine the classes of graphs whose $K_n$-complements are
trees and quasi-threshold graphs and derive formulas for their number of
spanning trees; for a subgraph $H$ of $K_n$, the $K_n$-complement of $H$ is the
graph $K_n-H$ which is obtained from $K_n$ by removing the edges of $H$. Our
proofs are based on the complement spanning-tree matrix theorem, which
expresses the number of spanning trees of a graph as a function of the
determinant of a matrix that can be easily constructed from the adjacency
relation of the graph. Our results generalize previous results and extend the
family of graphs of the form $K_n-H$ admitting formulas for the number of their
spanning trees.


title: Efficient Parallel Simulations of Asynchronous Cellular Arrays

abstract:
  A definition for a class of asynchronous cellular arrays is proposed. An
example of such asynchrony would be independent Poisson arrivals of cell
iterations. The Ising model in the continuous time formulation of Glauber falls
into this class. Also proposed are efficient parallel algorithms for simulating
these asynchronous cellular arrays. In the algorithms, one or several cells are
assigned to a processing element (PE), local times for different PEs can be
different. Although the standard serial algorithm by Metropolis, Rosenbluth,
Rosenbluth, Teller, and Teller can simulate such arrays, it is usually believed
to be without an efficient parallel counterpart. However, the proposed parallel
algorithms contradict this belief proving to be both efficient and able to
perform the same task as the standard algorithm. The results of experiments
with the new algorithms are encouraging: the speed-up is greater than 16 using
25 PEs on a shared memory MIMD bus computer, and greater than 1900 using 2**14
PEs on a SIMD computer. The algorithm by Bortz, Kalos, and Lebowitz can be
incorporated in the proposed parallel algorithms, further contributing to
speed-up. [In this paper I invented the update-cites-of-local-time-minima
parallel simulation scheme. Now the scheme is becoming popular. Many misprints
of the original 1987 Complex Systems publication are corrected here.-B.L.]


title:
Testing Systems of Concurrent Black-boxes--an Automata-Theoretic and
  Decompositional Approach

abstract:
  The global testing problem studied in this paper is to seek a definite answer
to whether a system of concurrent black-boxes has an observable behavior in a
given finite (but could be huge) set "Bad". We introduce a novel approach to
solve the problem that does not require integration testing. Instead, in our
approach, the global testing problem is reduced to testing individual
black-boxes in the system one by one in some given order. Using an
automata-theoretic approach, test sequences for each individual black-box are
generated from the system's description as well as the test results of
black-boxes prior to this black-box in the given order. In contrast to the
conventional compositional/modular verification/testing approaches, our
approach is essentially decompositional.
  Also, our technique is complete, sound, and can be carried out automatically.
Our experiment results show that the total number of tests needed to solve the
global testing problem is substantially small even for an extremely large
"Bad".


title: Logarithmic Lower Bounds in the Cell-Probe Model

abstract:
  We develop a new technique for proving cell-probe lower bounds on dynamic
data structures. This technique enables us to prove an amortized randomized
Omega(lg n) lower bound per operation for several data structural problems on n
elements, including partial sums, dynamic connectivity among disjoint paths (or
a forest or a graph), and several other dynamic graph problems (by simple
reductions). Such a lower bound breaks a long-standing barrier of Omega(lg n /
lglg n) for any dynamic language membership problem. It also establishes the
optimality of several existing data structures, such as Sleator and Tarjan's
dynamic trees. We also prove the first Omega(log_B n) lower bound in the
external-memory model without assumptions on the data structure (such as the
comparison model). Our lower bounds also give a query-update trade-off curve
matched, e.g., by several data structures for dynamic connectivity in graphs.
We also prove matching upper and lower bounds for partial sums when
parameterized by the word size and the maximum additive change in an update.


title:
Unified Large System Analysis of MMSE and Adaptive Least Squares
  Receivers for a class of Random Matrix Channels

abstract:
  We present a unified large system analysis of linear receivers for a class of
random matrix channels. The technique unifies the analysis of both the
minimum-mean-squared-error (MMSE) receiver and the adaptive least-squares (ALS)
receiver, and also uses a common approach for both random i.i.d. and random
orthogonal precoding. We derive expressions for the asymptotic
signal-to-interference-plus-noise (SINR) of the MMSE receiver, and both the
transient and steady-state SINR of the ALS receiver, trained using either
i.i.d. data sequences or orthogonal training sequences. The results are in
terms of key system parameters, and allow for arbitrary distributions of the
power of each of the data streams and the eigenvalues of the channel
correlation matrix. In the case of the ALS receiver, we allow a diagonal
loading constant and an arbitrary data windowing function. For i.i.d. training
sequences and no diagonal loading, we give a fundamental relationship between
the transient/steady-state SINR of the ALS and the MMSE receivers. We
demonstrate that for a particular ratio of receive to transmit dimensions and
window shape, all channels which have the same MMSE SINR have an identical
transient ALS SINR response. We demonstrate several applications of the
results, including an optimization of information throughput with respect to
training sequence length in coded block transmission.


title:
Compatible Triangulations and Point Partitions by Series-Triangular
  Graphs

abstract:
  We introduce series-triangular graph embeddings and show how to partition
point sets with them. This result is then used to improve the upper bound on
the number of Steiner points needed to obtain compatible triangulations of
point sets. The problem is generalized to finding compatible triangulations for
more than two point sets and we show that such triangulations can be
constructed with only a linear number of Steiner points added to each point
set.


title:
The complexity of computing the Hilbert polynomial of smooth
  equidimensional complex projective varieties

abstract:
  We continue the study of counting complexity begun in [Buergisser, Cucker 04]
and [Buergisser, Cucker, Lotz 05] by proving upper and lower bounds on the
complexity of computing the Hilbert polynomial of a homogeneous ideal. We show
that the problem of computing the Hilbert polynomial of a smooth
equidimensional complex projective variety can be reduced in polynomial time to
the problem of counting the number of complex common zeros of a finite set of
multivariate polynomials. Moreover, we prove that the more general problem of
computing the Hilbert polynomial of a homogeneous ideal is polynomial space
hard. This implies polynomial space lower bounds for both the problems of
computing the rank and the Euler characteristic of cohomology groups of
coherent sheaves on projective space, improving the #P-lower bound of Bach (JSC
1999).


title: Adaptive grids as parametrized scale-free networks

abstract:
  In this paper we present a possible model of adaptive grids for numerical
resolution of differential problems, using physical or geometrical properties,
as viscosity or velocity gradient of a moving fluid. The relation between the
values of grid step and these entities is based on the mathematical scheme
offered by the model of scale-free networks, due to Barabasi, so that the step
can be connected to the other variables by a constitutive relation. Some
examples and an application are discussed, showing that this approach can be
further developed for treatment of more complex situations.

categories: cs.NA math-ph math.AP math.MP physics.flu-dyn


title:
Proof obligations for specification and refinement of liveness
  properties under weak fairness

abstract:
  In this report, we present a formal model of fair iteration of events for B
event systems. The model is used to justify proof obligations for basic
liveness properties and preservation under refinement of general liveness
properties. The model of fair iteration of events uses the dovetail operator,
an operator proposed by Broy and Nelson to model fair choice. The proofs are
mainly founded in fixpoint calculations of fair iteration of events and weakest
precondition calculus.


title: The succinctness of first-order logic on linear orders

abstract:
  Succinctness is a natural measure for comparing the strength of different
logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all
properties that can be expressed in L_2 can be expressed in L_1 by formulas of
(approximately) the same size, but some properties can be expressed in L_1 by
(significantly) smaller formulas.
  We study the succinctness of logics on linear orders. Our first theorem is
concerned with the finite variable fragments of first-order logic. We prove
that:
  (i) Up to a polynomial factor, the 2- and the 3-variable fragments of
first-order logic on linear orders have the same succinctness. (ii) The
4-variable fragment is exponentially more succinct than the 3-variable
fragment. Our second main result compares the succinctness of first-order logic
on linear orders with that of monadic second-order logic. We prove that the
fragment of monadic second-order logic that has the same expressiveness as
first-order logic on linear orders is non-elementarily more succinct than
first-order logic.


title: An Automated Analysis of the Security of Quantum Key Distribution

abstract:
  This paper discusses the use of computer-aided verification as a practical
means for analysing quantum information systems; specifically, the BB84
protocol for quantum key distribution is examined using this method. This
protocol has been shown to be unconditionally secure against all attacks in an
information-theoretic setting, but the relevant security proof requires a
thorough understanding of the formalism of quantum mechanics and is not easily
adaptable to practical scenarios. Our approach is based on probabilistic
model-checking; we have used the PRISM model-checker to show that, as the
number of qubits transmitted in BB84 is increased, the equivocation of the
eavesdropper with respect to the channel decreases exponentially. We have also
shown that the probability of detecting the presence of an eavesdropper
increases exponentially with the number of qubits. The results presented here
are a testament to the effectiveness of the model-checking approach for systems
where analytical solutions may not be possible or plausible.


title: Generalised Bent Criteria for Boolean Functions (I)

abstract:
  Generalisations of the bent property of a boolean function are presented, by
proposing spectral analysis with respect to a well-chosen set of local unitary
transforms. Quadratic boolean functions are related to simple graphs and it is
shown that the orbit generated by successive Local Complementations on a graph
can be found within the transform spectra under investigation. The flat spectra
of a quadratic boolean function are related to modified versions of its
associated adjacency matrix.


title: Generalised Bent Criteria for Boolean Functions (II)

abstract:
  In the first part of this paper [16], some results on how to compute the flat
spectra of Boolean constructions w.r.t. the transforms {I,H}^n, {H,N}^n and
{I,H,N}^n were presented, and the relevance of Local Complementation to the
quadratic case was indicated. In this second part, the results are applied to
develop recursive formulae for the numbers of flat spectra of some structural
quadratics. Observations are made as to the generalised Bent properties of
boolean functions of algebraic degree greater than two, and the number of flat
spectra w.r.t. {I,H,N}^n are computed for some of them.


title: A Semantic Grid-based E-Learning Framework (SELF)

abstract:
  E-learning can be loosely defined as a wide set of applications and
processes, which uses available electronic media (and tools) to deliver
vocational education and training. With its increasing recognition as an
ubiquitous mode of instruction and interaction in the academic as well as
corporate world, the need for a scaleable and realistic model is becoming
important. In this paper we introduce SELF; a Semantic grid-based E-Learning
Framework. SELF aims to identify the key-enablers in a practical grid-based
E-learning environment and to minimize technological reworking by proposing a
well-defined interaction plan among currently available tools and technologies.
We define a dichotomy with E-learning specific application layers on top and
semantic grid-based support layers underneath. We also map the latest open and
freeware technologies with various components in SELF.


title: Log Analysis Case Study Using LoGS

abstract:
  A very useful technique a network administrator can use to identify
problematic network behavior is careful analysis of logs of incoming and
outgoing network flows. The challenge one faces when attempting to undertake
this course of action, though, is that large networks tend to generate an
extremely large quantity of network traffic in a very short period of time,
resulting in very large traffic logs which must be analyzed post-generation
with an eye for contextual information which may reveal symptoms of problematic
traffic. A better technique is to perform real-time log analysis using a
real-time context-generating tool such as LoGS.


title:
A low-cost time-hopping impulse radio system for high data rate
  transmission

abstract:
  We present an efficient, low-cost implementation of time-hopping impulse
radio that fulfills the spectral mask mandated by the FCC and is suitable for
high-data-rate, short-range communications. Key features are: (i) all-baseband
implementation that obviates the need for passband components, (ii) symbol-rate
(not chip rate) sampling, A/D conversion, and digital signal processing, (iii)
fast acquisition due to novel search algorithms, (iv) spectral shaping that can
be adapted to accommodate different spectrum regulations and interference
environments. Computer simulations show that this system can provide 110Mbit/s
at 7-10m distance, as well as higher data rates at shorter distances under FCC
emissions limits. Due to the spreading concept of time-hopping impulse radio,
the system can sustain multiple simultaneous users, and can suppress narrowband
interference effectively.


title: Improved Tag Set Design and Multiplexing Algorithms for Universal Arrays

abstract:
  In this paper we address two optimization problems arising in the design of
genomic assays based on universal tag arrays. First, we address the universal
array tag set design problem. For this problem, we extend previous formulations
to incorporate antitag-to-antitag hybridization constraints in addition to
constraints on antitag-to-tag hybridization specificity, establish a
constructive upper bound on the maximum number of tags satisfying the extended
constraints, and propose a simple greedy tag selection algorithm. Second, we
give methods for improving the multiplexing rate in large-scale genomic assays
by combining primer selection with tag assignment. Experimental results on
simulated data show that this integrated optimization leads to reductions of up
to 50% in the number of required arrays.


title: On quasi-cyclic interleavers for parallel turbo codes

abstract:
  We present an interleaving scheme that yields quasi-cyclic turbo codes. We
prove that randomly chosen members of this family yield with probability almost
1 turbo codes with asymptotically optimum minimum distance, i.e. growing as a
logarithm of the interleaver size. These interleavers are also very practical
in terms of memory requirements and their decoding error probabilities for
small block lengths compare favorably with previous interleaving schemes.