title:
Linear-Codes-Based Lossless Joint Source-Channel Coding for
  Multiple-Access Channels

abstract:
  A general lossless joint source-channel coding (JSCC) scheme based on linear
codes and random interleavers for multiple-access channels (MACs) is presented
and then analyzed in this paper. By the information-spectrum approach and the
code-spectrum approach, it is shown that a linear code with a good joint
spectrum can be used to establish limit-approaching lossless JSCC schemes for
correlated general sources and general MACs, where the joint spectrum is a
generalization of the input-output weight distribution. Some properties of
linear codes with good joint spectra are investigated. A formula on the
"distance" property of linear codes with good joint spectra is derived, based
on which, it is further proved that, the rate of any systematic codes with good
joint spectra cannot be larger than the reciprocal of the corresponding
alphabet cardinality, and any sparse generator matrices cannot yield linear
codes with good joint spectra. The problem of designing arbitrary rate coding
schemes is also discussed. A novel idea called "generalized puncturing" is
proposed, which makes it possible that one good low-rate linear code is enough
for the design of coding schemes with multiple rates. Finally, various coding
problems of MACs are reviewed in a unified framework established by the
code-spectrum approach, under which, criteria and candidates of good linear
codes in terms of spectrum requirements for such problems are clearly
presented.


title: P is not equal to NP

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


title: Next Generation Language Resources using GRID

abstract:
  This paper presents a case study concerning the challenges and requirements
posed by next generation language resources, realized as an overall model of
open, distributed and collaborative language infrastructure. If a sort of "new
paradigm" is required, we think that the emerging and still evolving technology
connected to Grid computing is a very interesting and suitable one for a
concrete realization of this vision. Given the current limitations of Grid
computing, it is very important to test the new environment on basic language
analysis tools, in order to get the feeling of what are the potentialities and
possible limitations connected to its use in NLP. For this reason, we have done
some experiments on a module of Linguistic Miner, i.e. the extraction of
linguistic patterns from restricted domain corpora.


title:
Comparison between Networked Control System behaviour based on CAN and
  Switched Ethernet networks

abstract:
  The distributed control systems are more and more used in many industrial
applications. These systems are often referred as "Networked control systems".
The goal of this paper is to show the network influence on feedback control
systems. Two networks are considered: Switched Ethernet network and CAN
fieldbus. The first one represents the non deterministic network and second one
represents the deterministic one. Several scenarii are studied to analyse the
stability of system according to different network parameters (packets losses,
congestion and frame priority). The Truetime simulator is used in this work.


title: A Novel Bayesian Classifier using Copula Functions

abstract:
  A useful method for representing Bayesian classifiers is through
\emph{discriminant functions}. Here, using copula functions, we propose a new
model for discriminants. This model provides a rich and generalized class of
decision boundaries. These decision boundaries significantly boost the
classification accuracy especially for high dimensional feature spaces. We
strengthen our analysis through simulation results.


title:
Collaborative design : managing task interdependencies and multiple
  perspectives

abstract:
  This paper focuses on two characteristics of collaborative design with
respect to cooperative work: the importance of work interdependencies linked to
the nature of design problems; and the fundamental function of design
cooperative work arrangement which is the confrontation and combination of
perspectives. These two intrinsic characteristics of the design work stress
specific cooperative processes: coordination processes in order to manage task
interdependencies, establishment of common ground and negotiation mechanisms in
order to manage the integration of multiple perspectives in design.


title: Viewpoints in co-design: a field study in concurrent engineering

abstract:
  We present a field study aimed at analysing the use of viewpoints in
co-design meetings. A viewpoint is a representation characterised by a certain
combination of constraints. Three types of viewpoints are distinguished:
prescribed viewpoint, discipline-specific viewpoint and integrated viewpoint.
The contribution of our work consists in characterising the viewpoints of
various stakeholders involved in co-design ("design office" disciplines, and
production and maintenance disciplines), the dynamics of viewpoints
confrontation and the cooperative modes that enable these different viewpoints
to be integrated.


title:
Changing our view on design evaluation meetings methodology: a study of
  software technical review meetings

abstract:
  By contrast to design meetings, design evaluation meetings (DEMs) have
generally been considered as situations in which, according to DEMs
methodologies, design activities are quite marginal. In a study of DEMs in
software development, i.e. in technical review meetings following a particular
review methodology, we showed: (i) the occurrence of design activities as part
of an argumentation process; (ii) the relative importance of cognitive
synchronisation as a prerequisite for evaluation; (iii) the important role
played in evaluation by argumentation that makes explicit the underlying design
rationale (DR). On the basis of our results, we discuss the potential for using
DR methodologies in this kind of meetings.


title:
Assessing the cognitive consequences of the object-oriented approach: a
  survey of empirical research on object-oriented design by individuals and
  teams

abstract:
  This paper presents a state-of-art review of empirical research on
object-oriented (OO) design. Many claims about the cognitive benefits of the OO
paradigm have been made by its advocates. These claims concern the ease of
designing and reusing software at the individual level as well as the benefits
of this paradigm at the team level. Since these claims are cognitive in nature,
its seems important to assess them empirically. After a brief presentation of
the main concepts of the OO paradigm, the claims about the superiority of OO
design are outlined. The core of this paper consists of a review of empirical
studies of OOD. We first discuss results concerning OOD by individuals. On the
basis of empirical work, we (1) analyse the design activity of novice OO
designers, (2) compare OO design with procedural design and, (3) discuss a
typology of problems relevant for the OO approach. Then we assess the claims
about naturalness and ease of OO design. The next part discusses results on OO
software reuse. On the basis of empirical work, we (1) compare reuse in the OO
versus procedural paradigm, (2) discuss the potential for OO software reuse and
(3) analyse reuse activity in the OO paradigm. Then we assess claims on
reusability. The final part reviews empirical work on OO design by teams. We
present results on communication, coordination, knowledge dissemination and
interactions with clients. Then we assess claims about OOD at the software
design team level. In a general conclusion, we discuss the limitations of these
studies and give some directions for future research.


title: Zig-zag and Replacement Product Graphs and LDPC Codes

abstract:
  The performance of codes defined from graphs depends on the expansion
property of the underlying graph in a crucial way. Graph products, such as the
zig-zag product and replacement product provide new infinite families of
constant degree expander graphs. The paper investigates the use of zig-zag and
replacement product graphs for the construction of codes on graphs. A
modification of the zig-zag product is also introduced, which can operate on
two unbalanced biregular bipartite graphs.


title:
D-MG Tradeoff and Optimal Codes for a Class of AF and DF Cooperative
  Communication Protocols

abstract:
  We consider cooperative relay communication in a fading channel environment
under the Orthogonal Amplify and Forward (OAF) and Orthogonal and
Non-Orthogonal Selection Decode and Forward (OSDF and NSDF) protocols. For all
these protocols, we compute the Diversity-Multiplexing Gain Tradeoff (DMT). We
construct DMT optimal codes for the protocols which are sphere decodable and,
in certain cases, incur minimum possible delay. Our results establish that the
DMT of the OAF protocol is identical to the DMT of the Non-Orthogonal Amplify
and Forward (NAF) protocol. Two variants of the NSDF protocol are considered:
fixed-NSDF and variable-NSDF protocol. In the variable-NSDF protocol, the
fraction of time duration for which the source alone transmits is allowed to
vary with the rate of communication. Among the class of static
amplify-and-forward and decode-and-forward protocols, the variable-NSDF
protocol is shown to have the best known DMT for any number of relays apart
from the two-relay case. When there are two relays, the variable-NSDF protocol
is shown to improve on the DMT of the best previously-known protocol for higher
values of the multiplexing gain. Our results also establish that the fixed-NSDF
protocol has a better DMT than the NAF protocol for any number of relays.
Finally, we present a DMT optimal code construction for the NAF protocol.


title: Bounding the Bias of Tree-Like Sampling in IP Topologies

abstract:
  It is widely believed that the Internet's AS-graph degree distribution obeys
a power-law form. Most of the evidence showing the power-law distribution is
based on BGP data. However, it was recently argued that since BGP collects data
in a tree-like fashion, it only produces a sample of the degree distribution,
and this sample may be biased. This argument was backed by simulation data and
mathematical analysis, which demonstrated that under certain conditions a tree
sampling procedure can produce an artificail power-law in the degree
distribution. Thus, although the observed degree distribution of the AS-graph
follows a power-law, this phenomenon may be an artifact of the sampling
process. In this work we provide some evidence to the contrary. We show, by
analysis and simulation, that when the underlying graph degree distribution
obeys a power-law with an exponent larger than 2, a tree-like sampling process
produces a negligible bias in the sampled degree distribution. Furthermore,
recent data collected from the DIMES project, which is not based on BGP
sampling, indicates that the underlying AS-graph indeed obeys a power-law
degree distribution with an exponent larger than 2. By combining this empirical
data with our analysis, we conclude that the bias in the degree distribution
calculated from BGP data is negligible.


title:
Articulation entre \'{e}laboration de solutions et argumentation
  polyphonique

abstract:
  In this paper, we propose an analytical framework that aims to bring out the
nature of participants' contributions to co-design meetings, in a way that
synthesises content and function dimensions, together with the dimension of
dialogicality. We term the resulting global vision of contribution, the
"interactive profile".


title:
Cognitive Effort in Collective Software Design: Methodological
  Perspectives in Cognitive Ergonomics

abstract:
  Empirical software engineering is concerned with measuring, or estimating,
both the effort put into the software process and the quality of its product.
We defend the idea that measuring process effort and product quality and
establishing a relation between the two cannot be performed without a model of
cognitive and collective activities involved in software design, and without
measurement of these activities. This is the object of our field, i.e.
Cognitive Ergonomics of design. After a brief presentation of its theoretical
and methodological foundations, we will discuss a cognitive approach to design
activities and its potential to provide new directions in ESE. Then we will
present and discuss an illustration of the methodological directions we have
proposed for the analysis and measurement of cognitive activities in the
context of collective software design. The two situations analysed are
technical review meetings, and Request For Comments-like procedures in Open
Source Software design.


title:
Complementary Sets, Generalized Reed-Muller Codes, and Power Control for
  OFDM

abstract:
  The use of error-correcting codes for tight control of the peak-to-mean
envelope power ratio (PMEPR) in orthogonal frequency-division multiplexing
(OFDM) transmission is considered in this correspondence. By generalizing a
result by Paterson, it is shown that each q-phase (q is even) sequence of
length 2^m lies in a complementary set of size 2^{k+1}, where k is a
nonnegative integer that can be easily determined from the generalized Boolean
function associated with the sequence. For small k this result provides a
reasonably tight bound for the PMEPR of q-phase sequences of length 2^m. A new
2^h-ary generalization of the classical Reed-Muller code is then used together
with the result on complementary sets to derive flexible OFDM coding schemes
with low PMEPR. These codes include the codes developed by Davis and Jedwab as
a special case. In certain situations the codes in the present correspondence
are similar to Paterson's code constructions and often outperform them.


title: On the Peak-to-Mean Envelope Power Ratio of Phase-Shifted Binary Codes

abstract:
  The peak-to-mean envelope power ratio (PMEPR) of a code employed in
orthogonal frequency-division multiplexing (OFDM) systems can be reduced by
permuting its coordinates and by rotating each coordinate by a fixed phase
shift. Motivated by some previous designs of phase shifts using suboptimal
methods, the following question is considered in this paper. For a given binary
code, how much PMEPR reduction can be achieved when the phase shifts are taken
from a 2^h-ary phase-shift keying (2^h-PSK) constellation? A lower bound on the
achievable PMEPR is established, which is related to the covering radius of the
binary code. Generally speaking, the achievable region of the PMEPR shrinks as
the covering radius of the binary code decreases. The bound is then applied to
some well understood codes, including nonredundant BPSK signaling, BCH codes
and their duals, Reed-Muller codes, and convolutional codes. It is demonstrated
that most (presumably not optimal) phase-shift designs from the literature
attain or approach our bound.


title: Quaternary Constant-Amplitude Codes for Multicode CDMA

abstract:
  A constant-amplitude code is a code that reduces the peak-to-average power
ratio (PAPR) in multicode code-division multiple access (MC-CDMA) systems to
the favorable value 1. In this paper quaternary constant-amplitude codes (codes
over Z_4) of length 2^m with error-correction capabilities are studied. These
codes exist for every positive integer m, while binary constant-amplitude codes
cannot exist if m is odd. Every word of such a code corresponds to a function
from the binary m-tuples to Z_4 having the bent property, i.e., its Fourier
transform has magnitudes 2^{m/2}. Several constructions of such functions are
presented, which are exploited in connection with algebraic codes over Z_4 (in
particular quaternary Reed-Muller, Kerdock, and Delsarte-Goethals codes) to
construct families of quaternary constant-amplitude codes. Mappings from binary
to quaternary constant-amplitude codes are presented as well.


title:
On Measuring the Impact of Human Actions in the Machine Learning of a
  Board Game's Playing Policies

abstract:
  We investigate systematically the impact of human intervention in the
training of computer players in a strategy board game. In that game, computer
players utilise reinforcement learning with neural networks for evolving their
playing strategies and demonstrate a slow learning speed. Human intervention
can significantly enhance learning performance, but carry-ing it out
systematically seems to be more of a problem of an integrated game development
environment as opposed to automatic evolutionary learning.


title:
Player co-modelling in a strategy board game: discovering how to play
  fast

abstract:
  In this paper we experiment with a 2-player strategy board game where playing
models are evolved using reinforcement learning and neural networks. The models
are evolved to speed up automatic game development based on human involvement
at varying levels of sophistication and density when compared to fully
autonomous playing. The experimental results suggest a clear and measurable
association between the ability to win games and the ability to do that fast,
while at the same time demonstrating that there is a minimum level of human
involvement beyond which no learning really occurs.


title:
Partially ordered distributed computations on asynchronous
  point-to-point networks

abstract:
  Asynchronous executions of a distributed algorithm differ from each other due
to the nondeterminism in the order in which the messages exchanged are handled.
In many situations of interest, the asynchronous executions induced by
restricting nondeterminism are more efficient, in an application-specific
sense, than the others. In this work, we define partially ordered executions of
a distributed algorithm as the executions satisfying some restricted orders of
their actions in two different frameworks, those of the so-called event- and
pulse-driven computations. The aim of these restrictions is to characterize
asynchronous executions that are likely to be more efficient for some important
classes of applications. Also, an asynchronous algorithm that ensures the
occurrence of partially ordered executions is given for each case. Two of the
applications that we believe may benefit from the restricted nondeterminism are
backtrack search, in the event-driven case, and iterative algorithms for
systems of linear equations, in the pulse-driven case.


title: Lossless fitness inheritance in genetic algorithms for decision trees

abstract:
  When genetic algorithms are used to evolve decision trees, key tree quality
parameters can be recursively computed and re-used across generations of
partially similar decision trees. Simply storing instance indices at leaves is
enough for fitness to be piecewise computed in a lossless fashion. We show the
derivation of the (substantial) expected speed-up on two bounding case problems
and trace the attractive property of lossless fitness inheritance to the
divide-and-conquer nature of decision trees. The theoretical results are
supported by experimental evidence.


title: Polynomial Time Symmetry and Isomorphism Testing for Connected Graphs

abstract:
  We use the concept of a Kirchhoff resistor network (alternatively random walk
on a network) to probe connected graphs and produce symmetry revealing
canonical labelings of the graph(s) nodes and edges.


title:
Reuse of designs: Desperately seeking an interdisciplinary cognitive
  approach

abstract:
  This text analyses the papers accepted for the workshop "Reuse of designs: an
interdisciplinary cognitive approach". Several dimensions and questions
considered as important (by the authors and/or by us) are addressed: What about
the "interdisciplinary cognitive" character of the approaches adopted by the
authors? Is design indeed a domain where the use of CBR is particularly
suitable? Are there important distinctions between CBR and other approaches?
Which types of knowledge -other than cases- is being, or might be, used in CBR
systems? With respect to cases: are there different "types" of case and
different types of case use? which formats are adopted for their
representation? do cases have "components"? how are cases organised in the case
memory? Concerning their retrieval: which types of index are used? on which
types of relation is retrieval based? how does one retrieve only a selected
number of cases, i.e., how does one retrieve only the "best" cases? which
processes and strategies are used, by the system and by its user? Finally, some
important aspects of CBR system development are shortly discussed: should CBR
systems be assistance or autonomous systems? how can case knowledge be
"acquired"? what about the empirical evaluation of CBR systems? The conclusion
points out some lacking points: not much attention is paid to the user, and few
papers have indeed adopted an interdisciplinary cognitive approach.


title: Predicate Abstraction via Symbolic Decision Procedures

abstract:
  We present a new approach for performing predicate abstraction based on
symbolic decision procedures. Intuitively, a symbolic decision procedure for a
theory takes a set of predicates in the theory and symbolically executes a
decision procedure on all the subsets over the set of predicates. The result of
the symbolic decision procedure is a shared expression (represented by a
directed acyclic graph) that implicitly represents the answer to a predicate
abstraction query.
  We present symbolic decision procedures for the logic of Equality and
Uninterpreted Functions (EUF) and Difference logic (DIFF) and show that these
procedures run in pseudo-polynomial (rather than exponential) time. We then
provide a method to construct symbolic decision procedures for simple mixed
theories (including the two theories mentioned above) using an extension of the
Nelson-Oppen combination method. We present preliminary evaluation of our
Procedure on predicate abstraction benchmarks from device driver verification
in SLAM.


title:
Object-Oriented Program Comprehension: Effect of Expertise, Task and
  Phase

abstract:
  The goal of our study is to evaluate the effect on program comprehension of
three factors that have not previously been studied in a single experiment.
These factors are programmer expertise (expert vs. novice), programming task
(documentation vs. reuse), and the development of understanding over time
(phase 1 vs. phase 2). This study is carried out in the context of the mental
model approach to comprehension based on van Dijk and Kintsch's model (1983).
One key aspect of this model is the distinction between two kinds of
representation the reader might construct from a text: 1) the textbase, which
refers to what is said in the text and how it is said, and 2) the situation
model, which represents the situation referred to by the text. We have
evaluated the effect of the three factors mentioned above on the development of
both the textbase (or program model) and the situation model in object-oriented
program comprehension. We found a four-way interaction of expertise, phase,
task and type of model. For the documentation group we found that experts and
novices differ in the elaboration of their situation model but not their
program model. There was no interaction of expertise with phase and type of
model in the documentation group. For the reuse group, there was a three-way
interaction between phase, expertise and type of model. For the novice reuse
group, the effect of the phase was to increase the construction of the
situation model but not the program model. With respect to the task, our
results show that novices do not spontaneously construct a strong situation
model but are able to do so if the task demands it.


title:
Quantitative Measurements of the Influence of Participant Roles during
  Peer Review Meetings

abstract:
  Peer review meetings (PRMs) are formal meetings during which peers
systematically analyze artifacts to improve their quality and report on
non-conformities. This paper presents an approach based on protocol analysis
for quantifying the influence of participant roles during PRMs. Three views are
used to characterize the seven defined participant roles. The project view
defines three roles supervisor, procedure expert and developer. The meeting
view defines two roles: author and reviewer, and the task view defines the
roles reflecting direct and indirect interest in the artifact under review. The
analysis, based on log-linear modeling, shows that review activities have
different patterns, depending on their focus: form or content. The influence of
each role is analyzed with respect to this focus. Interpretation of the
quantitative data leads to the suggestion that PRMs could be improved by
creating three different types of reviews, each of which collects together
specific roles: form review, cognitive synchronization review and content
review.


title:
Evocation and elaboration of solutions: Different types of
  problem-solving actions. An empirical study on the design of an aerospace
  artifact

abstract:
  An observational study was conducted on a professional designer working on a
design project in aerospace industry. The protocol data were analyzed in order
to gain insight into the actions the designer used for the development of a
solution to the corresponding problem. Different processes are described: from
the "simple" evocation of a solution existing in memory, to the elaboration of
a "new" solution out of mnesic entities without any clear link to the current
problem. Control is addressed in so far as it concerns the priority among the
different types of development processes: the progression from evocation of a
"standard" solution to elaboration of a "new" solution is supposed to
correspond to the resulting order, that is, the one in which the designer's
activity proceeds. Short discussions of * the double status of "problem" and
"solution," * the problem/solution knowledge units in memory and their access,
and * the different abstraction levels on which problem and solution
representations are developed, are illustrated by the results.


title:
High SNR Analysis for MIMO Broadcast Channels: Dirty Paper Coding vs.
  Linear Precoding

abstract:
  We study the MIMO broadcast channel and compare the achievable throughput for
the optimal strategy of dirty paper coding to that achieved with sub-optimal
and lower complexity linear precoding (e.g., zero-forcing and block
diagonalization) transmission. Both strategies utilize all available spatial
dimensions and therefore have the same multiplexing gain, but an absolute
difference in terms of throughput does exist. The sum rate difference between
the two strategies is analytically computed at asymptotically high SNR, and it
is seen that this asymptotic statistic provides an accurate characterization at
even moderate SNR levels. Furthermore, the difference is not affected by
asymmetric channel behavior when each user a has different average SNR.
Weighted sum rate maximization is also considered, and a similar quantification
of the throughput difference between the two strategies is performed. In the
process, it is shown that allocating user powers in direct proportion to user
weights asymptotically maximizes weighted sum rate. For multiple antenna users,
uniform power allocation across the receive antennas is applied after
distributing power proportional to the user weight.


title:
Design Strategies and Knowledge in Object-Oriented Programming: Effects
  of Experience

abstract:
  An empirical study was conducted to analyse design strategies and knowledge
used in object-oriented software design. Eight professional programmers
experienced with procedural programming languages and either experienced or not
experienced in object-oriented design strategies related to two central aspects
of the object-oriented paradigm: (1) associating actions, i.e., execution
steps, of a complex plan to different objects and revising a complex plan, and
(2) defining simple plans at different levels in the class hierarchy. As
regards the development of complex plans elements attached to different
objects, our results show that, for beginners in OOP, the description of
objects and the description of actions are not always integrated in an early
design phase, particularly for the declarative problem whereas, for the
programmers experienced in OOP, the description of objects and the description
of actions tend to be integrated in their first drafts of solutions whichever
the problem type. The analysis of design strategies reveal the use of different
knowledge according to subjects' language experience: (1) schemas related to
procedural languages; actions are organized in an execution order, or (2)
schemas related to object-oriented languages; actions and objects are
integrated, and actions are organised around objects.


title:
Users' participation to the design process in an Open Source Software
  online community

abstract:
  The objective of this research is to analyse the ways members of open-source
software communities participate in design. In particular we focus on how users
of an Open Source (OS) programming language (Python) participate in adding new
functionalities to the language. Indeed, in the OS communities, users are
highly skilled in computer sciences; they do not correspond to the common
representation of end-users and can potentially participate to the design
process. Our study characterizes the Python galaxy and analyses a formal
process to introduce new functionalities to the language called Python
Enhancement Proposal (PEP) from the idea of language evolution to the PEP
implementation. The analysis of a particular pushed-by-users PEP from one
application domain community (financial), shows: that the design process is
distributed and specialized between online and physical interactions spaces;
and there are some cross participants between users and developers communities
which may reveal boundary spanners roles.


title:
Articulation entre composantes verbale et graphico-gestuelle de
  l'interaction dans des r\'{e}unions de conception architecturale

abstract:
  This study is focused on the role of external representations, e.g.,
skteches, in collaborative architectural design. In particular, we analyse (1)
the use of graphico-gestural modalities and, (2) the articulation modes between
graphico-gestural and verbal modalities in design interaction. We have
elaborated a first classification which distinguishes between two modes of
articulation, articulation in integrated activities versus articulation in
parallel activities.


title:
Estimation of Bit and Frame Error Rates of Low-Density Parity-Check
  Codes on Binary Symmetric Channels

abstract:
  A method for estimating the performance of low-density parity-check (LDPC)
codes decoded by hard-decision iterative decoding algorithms on binary
symmetric channels (BSC) is proposed. Based on the enumeration of the smallest
weight error patterns that can not be all corrected by the decoder, this method
estimates both the frame error rate (FER) and the bit error rate (BER) of a
given LDPC code with very good precision for all crossover probabilities of
practical interest. Through a number of examples, we show that the proposed
method can be effectively applied to both regular and irregular LDPC codes and
to a variety of hard-decision iterative decoding algorithms. Compared with the
conventional Monte Carlo simulation, the proposed method has a much smaller
computational complexity, particularly for lower error rates.


title: Geographic Gossip on Geometric Random Graphs via Affine Combinations

abstract:
  In recent times, a considerable amount of work has been devoted to the
development and analysis of gossip algorithms in Geometric Random Graphs. In a
recently introduced model termed "Geographic Gossip," each node is aware of its
position but possesses no further information. Traditionally, gossip protocols
have always used convex linear combinations to achieve averaging. We develop a
new protocol for Geographic Gossip, in which counter-intuitively, we use {\it
non-convex affine combinations} as updates in addition to convex combinations
to accelerate the averaging process. The dependence of the number of
transmissions used by our algorithm on the number of sensors $n$ is $n
\exp(O(\log \log n)^2) = n^{1 + o(1)}$. For the previous algorithm, this
dependence was $\tilde{O}(n^{1.5})$. The exponent 1+ o(1) of our algorithm is
asymptotically optimal. Our algorithm involves a hierarchical structure of
$\log \log n$ depth and is not completely decentralized. However, the extent of
control exercised by a sensor on another is restricted to switching the other
on or off.


title: Economy-based Content Replication for Peering Content Delivery Networks

abstract:
  Existing Content Delivery Networks (CDNs) exhibit the nature of closed
delivery networks which do not cooperate with other CDNs and in practice,
islands of CDNs are formed. The logical separation between contents and
services in this context results in two content networking domains. In addition
to that, meeting the Quality of Service requirements of users according to
negotiated Service Level Agreement is crucial for a CDN. Present trends in
content networks and content networking capabilities give rise to the interest
in interconnecting content networks. Hence, in this paper, we present an open,
scalable, and Service-Oriented Architecture (SOA)-based system that assist the
creation of open Content and Service Delivery Networks (CSDNs), which scale and
supports sharing of resources through peering with other CSDNs. To encourage
resource sharing and peering arrangements between different CDN providers at
global level, we propose using market-based models by introducing an
economy-based strategy for content replication.


title: Going Stupid with EcoLab

abstract:
  In 2005, Railsback et al. proposed a very simple model ({\em Stupid
  Model}) that could be implemented within a couple of hours, and later
extended to demonstrate the use of common ABM platform functionality. They
provided implementations of the model in several agent based modelling
platforms, and compared the platforms for ease of implementation of this simple
model, and performance. In this paper, I implement Railsback et al's Stupid
Model in the EcoLab simulation platform, a C++ based modelling platform,
demonstrating that it is a feasible platform for these sorts of models, and
compare the performance of the implementation with Repast, Mason and Swarm
versions.


title: On the intersection of additive perfect codes

abstract:
  The intersection problem for additive (extended and non-extended) perfect
codes, i.e. which are the possibilities for the number of codewords in the
intersection of two additive codes C1 and C2 of the same length, is
investigated. Lower and upper bounds for the intersection number are computed
and, for any value between these bounds, codes which have this given
intersection value are constructed. For all these codes the abelian group
structure of the intersection is characterized. The parameters of this abelian
group structure corresponding to the intersection codes are computed and lower
and upper bounds for these parameters are established. Finally, constructions
of codes the intersection of which fits any parameters between these bounds are
given.


title:
Memory of past designs: distinctive roles in individual and collective
  design

abstract:
  Empirical studies on design have emphasised the role of memory of past
solutions. Design involves the use of generic knowledge as well as episodic
knowledge about past designs for analogous problems : in this way, it involves
the reuse of past designs. We analyse this mechanism of reuse from a
socio-cognitive viewpoint. According to a purely cognitive approach, reuse
involves cognitive mechanisms linked to the problem solving activity itself.
Our socio-cognitive approach accounts for these phenomena as well as reuse
mechanisms linked to cooperation, in particular coordination, and
confrontation/integration of viewpoints.


title: Confrontation of viewpoints in a concurrent engineering process

abstract:
  We present an empirical study aimed at analysing the use of viewpoints in an
industrial Concurrent Engineering context. Our focus is on the viewpoints
expressed in the argumentative process taking place in evaluation meetings. Our
results show that arguments enabling a viewpoint or proposal to be defended are
often characterized by the use of constraints. One result involved the way in
which the proposals for solutions are assessed during these meetings. We have
revealed the existence of specific assessment modes in these meetings as well
as their combination. Then, we show that, even if some constraints are
apparently identically used by the different specialists involved in meetings,
various meanings and weightings are associated with these constraints by these
different specialists.


title:
Mental Representations Constructed by Experts and Novices in
  Object-Oriented Program Comprehension

abstract:
  Previous studies on program comprehension were carried out largely in the
context of procedural languages. Our purpose is to develop and evaluate a
cognitive model of object-oriented (OO) program understanding. Our model is
based on the van Dijk and Kintsch's model of text understanding (1983). One key
aspect of this theoretical approach is the distinction between two kinds of
representation the reader might construct from a text: the textbase and the
situation model. On the basis of results of an experiment we have conducted, we
evaluate the cognitive validity of this distinction in OO program
understanding. We examine how the construction of these two representations is
differentially affected by the programmer's expertise and how they evolve
differentially over time.


title:
On Finite Memory Universal Data Compression and Classification of
  Individual Sequences

abstract:
  Consider the case where consecutive blocks of N letters of a semi-infinite
individual sequence X over a finite-alphabet are being compressed into binary
sequences by some one-to-one mapping. No a-priori information about X is
available at the encoder, which must therefore adopt a universal
data-compression algorithm. It is known that if the universal LZ77 data
compression algorithm is successively applied to N-blocks then the best
error-free compression for the particular individual sequence X is achieved, as
$N$ tends to infinity. The best possible compression that may be achieved by
any universal data compression algorithm for finite N-blocks is discussed. It
is demonstrated that context tree coding essentially achieves it. Next,
consider a device called classifier (or discriminator) that observes an
individual training sequence X. The classifier's task is to examine individual
test sequences of length N and decide whether the test N-sequence has the same
features as those that are captured by the training sequence X, or is
sufficiently different, according to some appropriatecriterion. Here again, it
is demonstrated that a particular universal context classifier with a
storage-space complexity that is linear in N, is essentially optimal. This may
contribute a theoretical "individual sequence" justification for the
Probabilistic Suffix Tree (PST) approach in learning theory and in
computational biology.


title: Analysing viewpoints in design through the argumentation process

abstract:
  We present an empirical study aimed at analysing the use of viewpoints in an
industrial Concurrent Engineering context. Our focus is on the viewpoints
expressed in the argumentative process taking place in evaluation meetings. Our
results show that arguments enabling a viewpoint or proposal to be defended are
often characterized by the use of constraints. Firstly, we show that, even if
some constraints are apparently identically used by the different specialists
involved in meetings, various meanings and weightings are associated with these
constraints by these different specialists. Secondly, we show that the implicit
or explicit nature of constraints depends on several interlocutive factors.
Thirdly, we show that an argument often covers not only one constraint but a
network of constraints. The type of combination reflects viewpoints which have
specific status in the meeting. Then, we will propose a first model of the
dynamics of viewpoints confrontation/integration.


title:
Multimodality and parallelism in design interaction: co-designers'
  alignment and coalitions

abstract:
  This paper presents an analysis of various forms of articulation between
graphico-gestural and verbal modalities in parallel interactions between
designers in a collaborative design situation. Based on our methodological
framework, we illustrate several forms of multimodal articulations, that is,
integrated and non-integrated, through extracts from a corpus on an
architectural design meeting. These modes reveal alignment or disalignment
between designers, with respect to the focus of their activities. They also
show different forms of coalition.


title: Both Generic Design and Different Forms of Designing

abstract:
  This paper defends an augmented cognitively oriented "generic-design
hypothesis": There are both significant similarities between the design
activities implemented in different situations and crucial differences between
these and other cognitive activities; yet, characteristics of a design
situation (i.e., related to the designers, the artefact, and other task
variables influencing these two) introduce specificities in the corresponding
design activities and cognitive structures that are used. We thus combine the
generic-design hypothesis with that of different "forms" of designing. In this
paper, outlining a number of directions that need further elaboration, we
propose a series of candidate dimensions underlying such forms of design.


title:
Reusing processes and documenting processes: toward an integrated
  framework

abstract:
  This paper presents a cognitive typology of reuse processes, and a cognitive
typology of documenting processes. Empirical studies on design with reuse and
on software documenting provide evidence for a generalized cognitive model.
First, these studies emphasize the cyclical nature of design: cycles of
planning, writing and revising occur. Second, natural language documentation
follows the hierarchy of cognitive entities manipulated during design.
Similarly software reuse involves exploiting various types of knowledge
depending on the phase of design in which reuse is involved. We suggest that
these observations can be explained based on cognitive models of text
processing: the van Dijk and Kintsch (1983) model of text comprehension, and
the Hayes and Flower (1980) model of text production. Based on our generalized
cognitive model, we suggest a framework for documenting reusable components.


title: On the Maximum Sum-rate Capacity of Cognitive Multiple Access Channel

abstract:
  We consider the communication scenario where multiple cognitive users wish to
communicate to the same receiver, in the presence of primary transmission. The
cognitive transmitters are assumed to have the side information about the
primary transmission. The capacity region of cognitive users is formulated
under the constraint that the capacity of primary transmission is not changed
as if no cognitive users exist. Moreover, the maximum sum-rate point of the
capacity region is characterized, by optimally allocating the power of each
cognitive user to transmit its own information.


title: Registers

abstract:
  Entry in: Encyclopedia of Algorithms, Ming-Yang Kao, Ed., Springer, To
appear.
  Synonyms: Wait-free registers, wait-free shared variables, asynchronous
communication hardware. Problem Definition: Consider a system of asynchronous
processes that communicate among themselves by only executing read and write
operations on a set of shared variables (also known as shared registers). The
system has no global clock or other synchronization primitives.


title: A disk-covering problem with application in optical interferometry

abstract:
  Given a disk O in the plane called the objective, we want to find n small
disks P_1,...,P_n called the pupils such that $\bigcup_{i,j=1}^n P_i \ominus
P_j \supseteq O$, where $\ominus$ denotes the Minkowski difference operator,
while minimizing the number of pupils, the sum of the radii or the total area
of the pupils. This problem is motivated by the construction of very large
telescopes from several smaller ones by so-called Optical Aperture Synthesis.
In this paper, we provide exact, approximate and heuristic solutions to several
variations of the problem.


title: Experimental Information and Statistical Modeling of Physical Laws

abstract:
  Statistical modeling of physical laws connects experiments with mathematical
descriptions of natural phenomena. The modeling is based on the probability
density of measured variables expressed by experimental data via a kernel
estimator. As an objective kernel the scattering function determined by
calibration of the instrument is introduced. This function provides for a new
definition of experimental information and redundancy of experimentation in
terms of information entropy. The redundancy increases with the number of
experiments, while the experimental information converges to a value that
describes the complexity of the data. The difference between the redundancy and
the experimental information is proposed as the model cost function. From its
minimum, a proper number of data in the model is estimated. As an optimal,
nonparametric estimator of the relation between measured variables the
conditional average extracted from the kernel estimator is proposed. The
modeling is demonstrated on noisy chaotic data.


title:
Using Combinatorics to Prune Search Trees: Independent and Dominating
  Set

abstract: This paper has been withdrawn by the author.


title: A Classification of 6R Manipulators

abstract:
  This paper presents a classification of generic 6-revolute jointed (6R)
manipulators using homotopy class of their critical point manifold. A part of
classification is listed in this paper because of the complexity of homotopy
class of 4-torus. The results of this classification will serve future research
of the classification and topological properties of maniplators joint space and
workspace.


title: Loop corrections for approximate inference

abstract:
  We propose a method for improving approximate inference methods that corrects
for the influence of loops in the graphical model. The method is applicable to
arbitrary factor graphs, provided that the size of the Markov blankets is not
too large. It is an alternative implementation of an idea introduced recently
by Montanari and Rizzo (2005). In its simplest form, which amounts to the
assumption that no loops are present, the method reduces to the minimal Cluster
Variation Method approximation (which uses maximal factors as outer clusters).
On the other hand, using estimates of the effect of loops (obtained by some
approximate inference algorithm) and applying the Loop Correcting (LC) method
usually gives significantly better results than applying the approximate
inference algorithm directly without loop corrections. Indeed, we often observe
that the loop corrected error is approximately the square of the error of the
approximate inference method used to estimate the effect of loops. We compare
different variants of the Loop Correcting method with other approximate
inference methods on a variety of graphical models, including "real world"
networks, and conclude that the LC approach generally obtains the most accurate
results.


title: Estimating Aggregate Properties on Probabilistic Streams

abstract:
  The probabilistic-stream model was introduced by Jayram et al. \cite{JKV07}.
It is a generalization of the data stream model that is suited to handling
``probabilistic'' data where each item of the stream represents a probability
distribution over a set of possible events. Therefore, a probabilistic stream
determines a distribution over potentially a very large number of classical
"deterministic" streams where each item is deterministically one of the domain
values. The probabilistic model is applicable for not only analyzing streams
where the input has uncertainties (such as sensor data streams that measure
physical processes) but also where the streams are derived from the input data
by post-processing, such as tagging or reconciling inconsistent and poor
quality data.
  We present streaming algorithms for computing commonly used aggregates on a
probabilistic stream. We present the first known, one pass streaming algorithm
for estimating the \AVG, improving results in \cite{JKV07}. We present the
first known streaming algorithms for estimating the number of \DISTINCT items
on probabilistic streams. Further, we present extensions to other aggregates
such as the repeat rate, quantiles, etc. In all cases, our algorithms work with
provable accuracy guarantees and within the space constraints of the data
stream model.


title: Code Spectrum and Reliability Function: Binary Symmetric Channel

abstract:
  A new approach for upper bounding the channel reliability function using the
code spectrum is described. It allows to treat in a unified way both a low and
a high rate cases. In particular, the earlier known upper bounds are improved,
and a new derivation of the sphere-packing bound is presented.


title:
Acronym-Meaning Extraction from Corpora Using Multi-Tape Weighted
  Finite-State Machines

abstract:
  The automatic extraction of acronyms and their meaning from corpora is an
important sub-task of text mining. It can be seen as a special case of string
alignment, where a text chunk is aligned with an acronym. Alternative
alignments have different cost, and ideally the least costly one should give
the correct meaning of the acronym. We show how this approach can be
implemented by means of a 3-tape weighted finite-state machine (3-WFSM) which
reads a text chunk on tape 1 and an acronym on tape 2, and generates all
alternative alignments on tape 3. The 3-WFSM can be automatically generated
from a simple regular expression. No additional algorithms are required at any
stage. Our 3-WFSM has a size of 27 states and 64 transitions, and finds the
best analysis of an acronym in a few milliseconds.


title: Predictable Disruption Tolerant Networks and Delivery Guarantees

abstract:
  This article studies disruption tolerant networks (DTNs) where each node
knows the probabilistic distribution of contacts with other nodes. It proposes
a framework that allows one to formalize the behaviour of such a network. It
generalizes extreme cases that have been studied before where (a) either nodes
only know their contact frequency with each other or (b) they have a perfect
knowledge of who meets who and when. This paper then gives an example of how
this framework can be used; it shows how one can find a packet forwarding
algorithm optimized to meet the 'delay/bandwidth consumption' trade-off:
packets are duplicated so as to (statistically) guarantee a given delay or
delivery probability, but not too much so as to reduce the bandwidth, energy,
and memory consumption.


title: Distributed Slicing in Dynamic Systems

abstract:
  Peer to peer (P2P) systems are moving from application specific architectures
to a generic service oriented design philosophy. This raises interesting
problems in connection with providing useful P2P middleware services that are
capable of dealing with resource assignment and management in a large-scale,
heterogeneous and unreliable environment. One such service, the slicing
service, has been proposed to allow for an automatic partitioning of P2P
networks into groups (slices) that represent a controllable amount of some
resource and that are also relatively homogeneous with respect to that
resource, in the face of churn and other failures. In this report we propose
two algorithms to solve the distributed slicing problem. The first algorithm
improves upon an existing algorithm that is based on gossip-based sorting of a
set of uniform random numbers. We speed up convergence via a heuristic for
gossip peer selection. The second algorithm is based on a different approach:
statistical approximation of the rank of nodes in the ordering. The
scalability, efficiency and resilience to dynamics of both algorithms relies on
their gossip-based models. We present theoretical and experimental results to
prove the viability of these algorithms.


title: Revisiting Matrix Product on Master-Worker Platforms

abstract:
  This paper is aimed at designing efficient parallel matrix-product algorithms
for heterogeneous master-worker platforms. While matrix-product is
well-understood for homogeneous 2D-arrays of processors (e.g., Cannon algorithm
and ScaLAPACK outer product algorithm), there are three key hypotheses that
render our work original and innovative:
  - Centralized data. We assume that all matrix files originate from, and must
be returned to, the master.
  - Heterogeneous star-shaped platforms. We target fully heterogeneous
platforms, where computational resources have different computing powers.
  - Limited memory. Because we investigate the parallelization of large
problems, we cannot assume that full matrix panels can be stored in the worker
memories and re-used for subsequent updates (as in ScaLAPACK).
  We have devised efficient algorithms for resource selection (deciding which
workers to enroll) and communication ordering (both for input and result
messages), and we report a set of numerical experiments on various platforms at
Ecole Normale Superieure de Lyon and the University of Tennessee. However, we
point out that in this first version of the report, experiments are limited to
homogeneous platforms.


title: Least Significant Digit First Presburger Automata

abstract:
  Since 1969 \cite{C-MST69,S-SMJ77}, we know that any Presburger-definable set
\cite{P-PCM29} (a set of integer vectors satisfying a formula in the
first-order additive theory of the integers) can be represented by a
state-based symmbolic representation, called in this paper Finite Digit Vector
Automata (FDVA). Efficient algorithms for manipulating these sets have been
recently developed. However, the problem of deciding if a FDVA represents such
a set, is a well-known hard problem first solved by Muchnik in 1991 with a
quadruply-exponential time algorithm. In this paper, we show how to determine
in polynomial time whether a FDVA represents a Presburger-definable set, and we
provide in this positive case a polynomial time algorithm that constructs a
Presburger-formula that defines the same set.


title: Non-Archimedean analysis, T-functions, and cryptography

abstract:
  These are lecture notes of a 20-hour course at the International Summer
School \emph{Mathematical Methods and Technologies in Computer Security} at
Lomonosov Moscow State University, July 9--23, 2006.
  Loosely speaking, a $T$-function is a map of $n$-bit words into $n$-bit words
such that each $i$-th bit of image depends only on low-order bits $0,..., i$ of
the pre-image. For example, all arithmetic operations (addition,
multiplication) are $T$-functions, all bitwise logical operations ($\XOR$,
$\AND$, etc.) are $T$-functions. Any composition of $T$-functions is a
$T$-function as well. Thus $T$-functions are natural computer word-oriented
functions.
  It turns out that $T$-functions are continuous (and often differentiable!)
functions with respect to the so-called 2-adic distance. This observation gives
a powerful tool to apply 2-adic analysis to construct wide classes of
$T$-functions with provable cryptographic properties (long period, balance,
uniform distribution, high linear complexity, etc.); these functions currently
are being used in new generation of fast stream ciphers. We consider these
ciphers as specific automata that could be associated to dynamical systems on
the space of 2-adic integers. From this view the lectures could be considered
as a course in cryptographic applications of the non-Archimedean dynamics; the
latter has recently attracted significant attention in connection with
applications to physics, biology and cognitive sciences.
  During the course listeners study non-Archimedean machinery and its
applications to stream cipher design.


title: Computing the Equilibria of Bimatrix Games using Dominance Heuristics

abstract:
  We propose a formulation of a general-sum bimatrix game as a bipartite
directed graph with the objective of establishing a correspondence between the
set of the relevant structures of the graph (in particular elementary cycles)
and the set of the Nash equilibria of the game. We show that finding the set of
elementary cycles of the graph permits the computation of the set of
equilibria. For games whose graphs have a sparse adjacency matrix, this serves
as a good heuristic for computing the set of equilibria. The heuristic also
allows the discarding of sections of the support space that do not yield any
equilibrium, thus serving as a useful pre-processing step for algorithms that
compute the equilibria through support enumeration.


title: The Workshop on Internet Topology (WIT) Report

abstract:
  Internet topology analysis has recently experienced a surge of interest in
computer science, physics, and the mathematical sciences. However, researchers
from these different disciplines tend to approach the same problem from
different angles. As a result, the field of Internet topology analysis and
modeling must untangle sets of inconsistent findings, conflicting claims, and
contradicting statements.
  On May 10-12, 2006, CAIDA hosted the Workshop on Internet topology (WIT). By
bringing together a group of researchers spanning the areas of computer
science, physics, and the mathematical sciences, the workshop aimed to improve
communication across these scientific disciplines, enable interdisciplinary
crossfertilization, identify commonalities in the different approaches, promote
synergy where it exists, and utilize the richness that results from exploring
similar problems from multiple perspectives.
  This report describes the findings of the workshop, outlines a set of
relevant open research problems identified by participants, and concludes with
recommendations that can benefit all scientific communities interested in
Internet topology research.


title: Viterbi Algorithm Generalized for n-Tape Best-Path Search

abstract:
  We present a generalization of the Viterbi algorithm for identifying the path
with minimal (resp. maximal) weight in a n-tape weighted finite-state machine
(n-WFSM), that accepts a given n-tuple of input strings (s_1,... s_n). It also
allows us to compile the best transduction of a given input n-tuple by a
weighted (n+m)-WFSM (transducer) with n input and m output tapes. Our algorithm
has a worst-case time complexity of O(|s|^n |E| log (|s|^n |Q|)), where n and
|s| are the number and average length of the strings in the n-tuple, and |Q|
and |E| the number of states and transitions in the n-WFSM, respectively. A
straight forward alternative, consisting in intersection followed by classical
shortest-distance search, operates in O(|s|^n (|E|+|Q|) log (|s|^n |Q|)) time.


title:
Decentralized Maximum Likelihood Estimation for Sensor Networks Composed
  of Nonlinearly Coupled Dynamical Systems

abstract:
  In this paper we propose a decentralized sensor network scheme capable to
reach a globally optimum maximum likelihood (ML) estimate through
self-synchronization of nonlinearly coupled dynamical systems. Each node of the
network is composed of a sensor and a first-order dynamical system initialized
with the local measurements. Nearby nodes interact with each other exchanging
their state value and the final estimate is associated to the state derivative
of each dynamical system. We derive the conditions on the coupling mechanism
guaranteeing that, if the network observes one common phenomenon, each node
converges to the globally optimal ML estimate. We prove that the synchronized
state is globally asymptotically stable if the coupling strength exceeds a
given threshold. Acting on a single parameter, the coupling strength, we show
how, in the case of nonlinear coupling, the network behavior can switch from a
global consensus system to a spatial clustering system. Finally, we show the
effect of the network topology on the scalability properties of the network and
we validate our theoretical findings with simulation results.


title: About the Lifespan of Peer to Peer Networks

abstract:
  We analyze the ability of peer to peer networks to deliver a complete file
among the peers. Early on we motivate a broad generalization of network
behavior organizing it into one of two successive phases. According to this
view the network has two main states: first centralized - few sources (roots)
hold the complete file, and next distributed - peers hold some parts (chunks)
of the file such that the entire network has the whole file, but no individual
has it. In the distributed state we study two scenarios, first, when the peers
are ``patient'', i.e, do not leave the system until they obtain the complete
file; second, peers are ``impatient'' and almost always leave the network
before obtaining the complete file.


title: The Relay-Eavesdropper Channel: Cooperation for Secrecy

abstract:
  This paper establishes the utility of user cooperation in facilitating secure
wireless communications. In particular, the four-terminal relay-eavesdropper
channel is introduced and an outer-bound on the optimal rate-equivocation
region is derived. Several cooperation strategies are then devised and the
corresponding achievable rate-equivocation region are characterized. Of
particular interest is the novel Noise-Forwarding (NF) strategy, where the
relay node sends codewords independent of the source message to confuse the
eavesdropper. This strategy is used to illustrate the deaf helper phenomenon,
where the relay is able to facilitate secure communications while being totally
ignorant of the transmitted messages. Furthermore, NF is shown to increase the
secrecy capacity in the reversely degraded scenario, where the relay node fails
to offer performance gains in the classical setting. The gain offered by the
proposed cooperation strategies is then proved theoretically and validated
numerically in the additive White Gaussian Noise (AWGN) channel.


title: SIMPS: Using Sociology for Personal Mobility

abstract:
  Assessing mobility in a thorough fashion is a crucial step toward more
efficient mobile network design. Recent research on mobility has focused on two
main points: analyzing models and studying their impact on data transport.
These works investigate the consequences of mobility. In this paper, instead,
we focus on the causes of mobility. Starting from established research in
sociology, we propose SIMPS, a mobility model of human crowd motion. This model
defines two complimentary behaviors, namely socialize and isolate, that
regulate an individual with regard to her/his own sociability level. SIMPS
leads to results that agree with scaling laws observed both in small-scale and
large-scale human motion. Although our model defines only two simple individual
behaviors, we observe many emerging collective behaviors (group
formation/splitting, path formation, and evolution). To our knowledge, SIMPS is
the first model in the networking community that tackles the roots governing
mobility.


title: Social Networks and Social Information Filtering on Digg

abstract:
  The new social media sites -- blogs, wikis, Flickr and Digg, among others --
underscore the transformation of the Web to a participatory medium in which
users are actively creating, evaluating and distributing information. Digg is a
social news aggregator which allows users to submit links to, vote on and
discuss news stories. Each day Digg selects a handful of stories to feature on
its front page. Rather than rely on the opinion of a few editors, Digg
aggregates opinions of thousands of its users to decide which stories to
promote to the front page.
  Digg users can designate other users as ``friends'' and easily track friends'
activities: what new stories they submitted, commented on or read. The friends
interface acts as a \emph{social filtering} system, recommending to user
stories his or her friends liked or found interesting. By tracking the votes
received by newly submitted stories over time, we showed that social filtering
is an effective information filtering approach. Specifically, we showed that
(a) users tend to like stories submitted by friends and (b) users tend to like
stories their friends read and liked. As a byproduct of social filtering,
social networks also play a role in promoting stories to Digg's front page,
potentially leading to ``tyranny of the minority'' situation where a
disproportionate number of front page stories comes from the same small group
of interconnected users. Despite this, social filtering is a promising new
technology that can be used to personalize and tailor information to individual
users: for example, through personal front pages.


title: Social Browsing on Flickr

abstract:
  The new social media sites - blogs, wikis, del.icio.us and Flickr, among
others - underscore the transformation of the Web to a participatory medium in
which users are actively creating, evaluating and distributing information. The
photo-sharing site Flickr, for example, allows users to upload photographs,
view photos created by others, comment on those photos, etc. As is common to
other social media sites, Flickr allows users to designate others as
``contacts'' and to track their activities in real time. The contacts (or
friends) lists form the social network backbone of social media sites. We claim
that these social networks facilitate new ways of interacting with information,
e.g., through what we call social browsing. The contacts interface on Flickr
enables users to see latest images submitted by their friends. Through an
extensive analysis of Flickr data, we show that social browsing through the
contacts' photo streams is one of the primary methods by which users find new
images on Flickr. This finding has implications for creating personalized
recommendation systems based on the user's declared contacts lists.


title: Queue Model of Leaf Degree Keeping Process in Gnutella Network

abstract:
  Leaf degree keeping process of Gnutella is discussed in this paper. Queue
system based on rules of Gnutella protocol are introduced to modeling this
process. The leaf degree distributions resulted from the queue system and from
our real measurement are compared. The well match of those distributions reveal
that the leaf degree distribution in Gnutella network should not be power law
or power law like as reported before. It is more likely a distribution driven
by certain queue process specified by the protocol.


title: Power Control in Distributed Cooperative OFDMA Cellular Networks

abstract: This paper has been withdrawn by the author.


title: Explicit factors of some iterated resultants and discriminants

abstract:
  In this paper, the result of applying iterative univariate resultant
constructions to multivariate polynomials is analyzed. We consider the input
polynomials as generic polynomials of a given degree and exhibit explicit
decompositions into irreducible factors of several constructions involving two
times iterated univariate resultants and discriminants over the integer
universal ring of coefficients of the entry polynomials. Cases involving from
two to four generic polynomials and resultants or discriminants in one of their
variables are treated. The decompositions into irreducible factors we get are
obtained by exploiting fundamental properties of the univariate resultants and
discriminants and induction on the degree of the polynomials. As a consequence,
each irreducible factor can be separately and explicitly computed in terms of a
certain multivariate resultant. With this approach, we also obtain as direct
corollaries some results conjectured by Collins and McCallum which correspond
to the case of polynomials whose coefficients are themselves generic
polynomials in other variables. Finally, a geometric interpretation of the
algebraic factorization of the iterated discriminant of a single polynomial is
detailled.


title:
On the Decoder Error Probability of Bounded Rank-Distance Decoders for
  Maximum Rank Distance Codes

abstract:
  In this paper, we first introduce the concept of elementary linear subspace,
which has similar properties to those of a set of coordinates. We then use
elementary linear subspaces to derive properties of maximum rank distance (MRD)
codes that parallel those of maximum distance separable codes. Using these
properties, we show that, for MRD codes with error correction capability t, the
decoder error probability of bounded rank distance decoders decreases
exponentially with t^2 based on the assumption that all errors with the same
rank are equally likely.


title: Budget Optimization in Search-Based Advertising Auctions

abstract:
  Internet search companies sell advertisement slots based on users' search
queries via an auction. While there has been a lot of attention on the auction
process and its game-theoretic aspects, our focus is on the advertisers. In
particular, the advertisers have to solve a complex optimization problem of how
to place bids on the keywords of their interest so that they can maximize their
return (the number of user clicks on their ads) for a given budget. We model
the entire process and study this budget optimization problem. While most
variants are NP hard, we show, perhaps surprisingly, that simply randomizing
between two uniform strategies that bid equally on all the keywords works well.
More precisely, this strategy gets at least 1-1/e fraction of the maximum
clicks possible. Such uniform strategies are likely to be practical. We also
present inapproximability results, and optimal algorithms for variants of the
budget optimization problem.


title:
Deriving Schrodinger Equation From A Soft-Decision Iterative Decoding
  Algorithm

abstract:
  The belief propagation algorithm has been recognized in the information
theory community as a soft-decision iterative decoding algorithm. It is the
most powerful algorithm found so far for attacking hard optimization problems
in channel decoding. Quantum mechanics is the foundation of modern physics with
the time-independent Schrodinger equation being one of the most important
equations. This paper shows that the equation can be derived from a generalized
belief propagation algorithm. Such a connection on a mathematical basis might
shed new insights into the foundations of quantum mechanics and quantum
computing.


title: Lightweight security mechanism for PSTN-VoIP cooperation

abstract:
  In this paper we describe a new, lightweight security mechanism for PSTN-VoIP
cooperation that is based on two information hiding techniques: digital
watermarking and steganography. Proposed scheme is especially suitable for
PSTN-IP-PSTN (toll-by-passing) scenario which nowadays is very popular
application of IP Telephony systems. With the use of this mechanism we
authenticate end-to-end transmitted voice between PSTN users. Additionally we
improve IP part traffic security (both media stream and VoIP signalling
messages). Exemplary scenario is presented for SIP signalling protocol along
with SIP-T extension and H.248/Megaco protocol.


title: Linear Probing with Constant Independence

abstract:
  Hashing with linear probing dates back to the 1950s, and is among the most
studied algorithms. In recent years it has become one of the most important
hash table organizations since it uses the cache of modern computers very well.
Unfortunately, previous analysis rely either on complicated and space consuming
hash functions, or on the unrealistic assumption of free access to a truly
random hash function. Already Carter and Wegman, in their seminal paper on
universal hashing, raised the question of extending their analysis to linear
probing. However, we show in this paper that linear probing using a pairwise
independent family may have expected {\em logarithmic} cost per operation. On
the positive side, we show that 5-wise independence is enough to ensure
constant expected time per operation. This resolves the question of finding a
space and time efficient hash function that provably ensures good performance
for linear probing.


title: Conscious Intelligent Systems - Part 1 : I X I

abstract:
  Did natural consciousness and intelligent systems arise out of a path that
was co-evolutionary to evolution? Can we explain human self-consciousness as
having risen out of such an evolutionary path? If so how could it have been?
  In this first part of a two-part paper (titled IXI), we take a learning
system perspective to the problem of consciousness and intelligent systems, an
approach that may look unseasonable in this age of fMRI's and high tech
neuroscience.
  We posit conscious intelligent systems in natural environments and wonder how
natural factors influence their design paths. Such a perspective allows us to
explain seamlessly a variety of natural factors, factors ranging from the rise
and presence of the human mind, man's sense of I, his self-consciousness and
his looping thought processes to factors like reproduction, incubation,
extinction, sleep, the richness of natural behavior, etc. It even allows us to
speculate on a possible human evolution scenario and other natural phenomena.


title:
Conscious Intelligent Systems - Part II - Mind, Thought, Language and
  Understanding

abstract:
  This is the second part of a paper on Conscious Intelligent Systems. We use
the understanding gained in the first part (Conscious Intelligent Systems Part
1: IXI (arxiv id cs.AI/0612056)) to look at understanding. We see how the
presence of mind affects understanding and intelligent systems; we see that the
presence of mind necessitates language. The rise of language in turn has
important effects on understanding. We discuss the humanoid question and how
the question of self-consciousness (and by association mind/thought/language)
would affect humanoids too.


title:
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling
  and Counting

abstract:
  We present a near-optimal reduction from approximately counting the
cardinality of a discrete set to approximately sampling elements of the set. An
important application of our work is to approximating the partition function
$Z$ of a discrete system, such as the Ising model, matchings or colorings of a
graph. The typical approach to estimating the partition function $Z(\beta^*)$
at some desired inverse temperature $\beta^*$ is to define a sequence, which we
call a {\em cooling schedule}, $\beta_0=0<\beta_1<...<\beta_\ell=\beta^*$ where
Z(0) is trivial to compute and the ratios $Z(\beta_{i+1})/Z(\beta_i)$ are easy
to estimate by sampling from the distribution corresponding to $Z(\beta_i)$.
Previous approaches required a cooling schedule of length $O^*(\ln{A})$ where
$A=Z(0)$, thereby ensuring that each ratio $Z(\beta_{i+1})/Z(\beta_i)$ is
bounded. We present a cooling schedule of length $\ell=O^*(\sqrt{\ln{A}})$.
  For well-studied problems such as estimating the partition function of the
Ising model, or approximating the number of colorings or matchings of a graph,
our cooling schedule is of length $O^*(\sqrt{n})$, which implies an overall
savings of $O^*(n)$ in the running time of the approximate counting algorithm
(since roughly $\ell$ samples are needed to estimate each ratio).


title:
Synchronization recovery and state model reduction for soft decoding of
  variable length codes

abstract:
  Variable length codes exhibit de-synchronization problems when transmitted
over noisy channels. Trellis decoding techniques based on Maximum A Posteriori
(MAP) estimators are often used to minimize the error rate on the estimated
sequence. If the number of symbols and/or bits transmitted are known by the
decoder, termination constraints can be incorporated in the decoding process.
All the paths in the trellis which do not lead to a valid sequence length are
suppressed. This paper presents an analytic method to assess the expected error
resilience of a VLC when trellis decoding with a sequence length constraint is
used. The approach is based on the computation, for a given code, of the amount
of information brought by the constraint. It is then shown that this quantity
as well as the probability that the VLC decoder does not re-synchronize in a
strict sense, are not significantly altered by appropriate trellis states
aggregation. This proves that the performance obtained by running a
length-constrained Viterbi decoder on aggregated state models approaches the
one obtained with the bit/symbol trellis, with a significantly reduced
complexity. It is then shown that the complexity can be further decreased by
projecting the state model on two state models of reduced size.


title: The Common Prefix Problem On Trees

abstract:
  We present a theoretical study of a problem arising in database query
optimization, which we call as The Common Prefix Problem. We present a
$(1-o(1))$ factor approximation algorithm for this problem, when the underlying
graph is a binary tree. We then use a result of Feige and Kogan to show that
even on stars, the problem is hard to approximate.


title: Trustworthy content push

abstract:
  Delivery of content to mobile devices gains increasing importance in
industrial environments to support employees in the field. An important
application are e-mail push services like the fashionable Blackberry. These
systems are facing security challenges regarding data transport to, and storage
of the data on the end user equipment. The emerging Trusted Computing
technology offers new answers to these open questions.


title: Unifying Lexicons in view of a Phonological and Morphological Lexical DB

abstract:
  The present work falls in the line of activities promoted by the European
Languguage Resource Association (ELRA) Production Committee (PCom) and raises
issues in methods, procedures and tools for the reusability, creation, and
management of Language Resources. A two-fold purpose lies behind this
experiment. The first aim is to investigate the feasibility, define methods and
procedures for combining two Italian lexical resources that have incompatible
formats and complementary information into a Unified Lexicon (UL). The adopted
strategy and the procedures appointed are described together with the driving
criterion of the merging task, where a balance between human and computational
efforts is pursued. The coverage of the UL has been maximized, by making use of
simple and fast matching procedures. The second aim is to exploit this newly
obtained resource for implementing the phonological and morphological layers of
the CLIPS lexical database. Implementing these new layers and linking them with
the already exisitng syntactic and semantic layers is not a trivial task. The
constraints imposed by the model, the impact at the architectural level and the
solution adopted in order to make the whole database `speak' efficiently are
presented. Advantages vs. disadvantages are discussed.


title: Improving Precision of Type Analysis Using Non-Discriminative Union

abstract:
  This paper presents a new type analysis for logic programs. The analysis is
performed with a priori type definitions; and type expressions are formed from
a fixed alphabet of type constructors. Non-discriminative union is used to join
type information from different sources without loss of precision. An operation
that is performed repeatedly during an analysis is to detect if a fixpoint has
been reached. This is reduced to checking the emptiness of types. Due to the
use of non-discriminative union, the fundamental problem of checking the
emptiness of types is more complex in the proposed type analysis than in other
type analyses with a priori type definitions. The experimental results,
however, show that use of tabling reduces the effect to a small fraction of
analysis time on a set of benchmarks.
  Keywords: Type analysis, Non-discriminative union, Abstract interpretation,
Tabling


title: Bounds on Key Appearance Equivocation for Substitution Ciphers

abstract:
  The average conditional entropy of the key given the message and its
corresponding cryptogram, H(K|M,C), which is reffer as a key appearance
equivocation, was proposed as a theoretical measure of the strength of the
cipher system under a known-plaintext attack by Dunham in 1980. In the same
work (among other things), lower and upper bounds for H(S}_{M}|M^L,C^L) are
found and its asymptotic behaviour as a function of cryptogram length L is
described for simple substitution ciphers i.e. when the key space S_{M} is the
symmetric group acting on a discrete alphabet M. In the present paper we
consider the same problem when the key space is an arbitrary subgroup K of
S_{M} and generalize Dunham's result.


title:
An equilibrium model for matching impatient demand and patient supply
  over time

abstract:
  We present a simple dynamic equilibrium model for an online exchange where
both buyers and sellers arrive according to a exogenously defined stochastic
process. The structure of this exchange is motivated by the limit order book
mechanism used in stock markets. Both buyers and sellers are elastic in the
price-quantity space; however, only the sellers are assumed to be patient, i.e.
only the sellers have a price - time elasticity, whereas the buyers are assumed
to be impatient. Sellers select their selling price as a best response to all
the other sellers' strategies. We define and establish the existence of the
equilibrium in this model and show how to numerically compute this equilibrium.
We also show how to compute other relevant quantities such as the equilibrium
expected time to sale and equilibrium expected order density, as well as the
expected order density conditioned on current selling price. We derive a closed
form for the equilibrium distribution when the demand is price independent. At
this equilibrium the selling (limit order) price distribution is power tailed
as is empirically observed in order driven financial markets.


title: Optimal Filtering for DDoS Attacks

abstract:
  Distributed Denial-of-Service (DDoS) attacks are a major problem in the
Internet today. In one form of a DDoS attack, a large number of compromised
hosts send unwanted traffic to the victim, thus exhausting the resources of the
victim and preventing it from serving its legitimate clients. One of the main
mechanisms that have been proposed to deal with DDoS is filtering, which allows
routers to selectively block unwanted traffic. Given the magnitude of DDoS
attacks and the high cost of filters in the routers today, the successful
mitigation of a DDoS attack using filtering crucially depends on the efficient
allocation of filtering resources. In this paper, we consider a single router,
typically the gateway of the victim, with a limited number of available
filters. We study how to optimally allocate filters to attack sources, or
entire domains of attack sources, so as to maximize the amount of good traffic
preserved, under a constraint on the number of filters. We formulate the
problem as an optimization problem and solve it optimally using dynamic
programming, study the properties of the optimal allocation, experiment with a
simple heuristic and evaluate our solutions for a range of realistic
attack-scenarios. First, we look at a single-tier where the collateral damage
is high due to the filtering at the granularity of domains. Second, we look at
the two-tier problem where we have an additional constraint on the number of
filters and the filtering is performed on the granularity of attackers and
domains.


title:
Retrieving Reed-Solomon coded data under interpolation-based list
  decoding

abstract:
  A transform that enables generator-matrix-based Reed-Solomon (RS) coded data
to be recovered under interpolation-based list decoding is presented. The
transform matrix needs to be computed only once and the transformation of an
element from the output list to the desired RS coded data block incurs $k^{2}$
field multiplications, given a code of dimension $k$.


title: Interactive Configuration by Regular String Constraints

abstract:
  A product configurator which is complete, backtrack free and able to compute
the valid domains at any state of the configuration can be constructed by
building a Binary Decision Diagram (BDD). Despite the fact that the size of the
BDD is exponential in the number of variables in the worst case, BDDs have
proved to work very well in practice. Current BDD-based techniques can only
handle interactive configuration with small finite domains. In this paper we
extend the approach to handle string variables constrained by regular
expressions. The user is allowed to change the strings by adding letters at the
end of the string. We show how to make a data structure that can perform fast
valid domain computations given some assignment on the set of string variables.
  We first show how to do this by using one large DFA. Since this approach is
too space consuming to be of practical use, we construct a data structure that
simulates the large DFA and in most practical cases are much more space
efficient. As an example a configuration problem on $n$ string variables with
only one solution in which each string variable is assigned to a value of
length of $k$ the former structure will use $\Omega(k^n)$ space whereas the
latter only need $O(kn)$. We also show how this framework easily can be
combined with the recent BDD techniques to allow both boolean, integer and
string variables in the configuration problem.


title: Cores of Countably Categorical Structures

abstract:
  A relational structure is a core, if all its endomorphisms are embeddings.
This notion is important for computational complexity classification of
constraint satisfaction problems. It is a fundamental fact that every finite
structure has a core, i.e., has an endomorphism such that the structure induced
by its image is a core; moreover, the core is unique up to isomorphism. Weprove
that every \omega -categorical structure has a core. Moreover, every
\omega-categorical structure is homomorphically equivalent to a model-complete
core, which is unique up to isomorphism, and which is finite or \omega
-categorical. We discuss consequences for constraint satisfaction with \omega
-categorical templates.


title: Generalizations of the Hanoi Towers Problem

abstract:
  Our theme bases on the classical Hanoi Towers Problem. In this paper we will
define a new problem, permitting some positions, that were not legal in the
classical problem. Our goal is to find an optimal (shortest possible) sequence
of discs' moves. Besides that, we will research all versions of 3-pegs
classical problem with some special constraints, when some types of moves are
disallowed.


title:
Why is Open Access Development so Successful? Stigmergic organization
  and the economics of information

abstract:
  The explosive development of "free" or "open source" information goods
contravenes the conventional wisdom that markets and commercial organizations
are necessary to efficiently supply products. This paper proposes a theoretical
explanation for this phenomenon, using concepts from economics and theories of
self-organization. Once available on the Internet, information is intrinsically
not a scarce good, as it can be replicated virtually without cost. Moreover,
freely distributing information is profitable to its creator, since it improves
the quality of the information, and enhances the creator's reputation. This
provides a sufficient incentive for people to contribute to open access
projects. Unlike traditional organizations, open access communities are open,
distributed and self-organizing. Coordination is achieved through stigmergy:
listings of "work-in-progress" direct potential contributors to the tasks where
their contribution is most likely to be fruitful. This obviates the need both
for centralized planning and for the "invisible hand" of the market.


title: Stochastic Models for Budget Optimization in Search-Based Advertising

abstract:
  Internet search companies sell advertisement slots based on users' search
queries via an auction. Advertisers have to determine how to place bids on the
keywords of their interest in order to maximize their return for a given
budget: this is the budget optimization problem. The solution depends on the
distribution of future queries.
  In this paper, we formulate stochastic versions of the budget optimization
problem based on natural probabilistic models of distribution over future
queries, and address two questions that arise.
  [Evaluation] Given a solution, can we evaluate the expected value of the
objective function?
  [Optimization] Can we find a solution that maximizes the objective function
in expectation?
  Our main results are approximation and complexity results for these two
problems in our three stochastic models. In particular, our algorithmic results
show that simple prefix strategies that bid on all cheap keywords up to some
level are either optimal or good approximations for many cases; we show other
cases to be NP-hard.


title: On the Fingerprinting Capacity Under the Marking Assumption

abstract:
  We address the maximum attainable rate of fingerprinting codes under the
marking assumption, studying lower and upper bounds on the value of the rate
for various sizes of the attacker coalition. Lower bounds are obtained by
considering typical coalitions, which represents a new idea in the area of
fingerprinting and enables us to improve the previously known lower bounds for
coalitions of size two and three. For upper bounds, the fingerprinting problem
is modelled as a communications problem. It is shown that the maximum code rate
is bounded above by the capacity of a certain class of channels, which are
similar to the multiple-access channel. Converse coding theorems proved in the
paper provide new upper bounds on fingerprinting capacity.
  It is proved that capacity for fingerprinting against coalitions of size two
and three over the binary alphabet satisfies $0.25 \leq C_{2,2} \leq 0.322$ and
$0.083 \leq C_{3,2} \leq 0.199$ respectively. For coalitions of an arbitrary
fixed size $t,$ we derive an upper bound $(t\ln2)^{-1}$ on fingerprinting
capacity in the binary case. Finally, for general alphabets, we establish upper
bounds on the fingerprinting capacity involving only single-letter mutual
information quantities.


title: Energy Efficient Randomized Communication in Unknown AdHoc Networks

abstract:
  This paper studies broadcasting and gossiping algorithms in random and
general AdHoc networks. Our goal is not only to minimise the broadcasting and
gossiping time, but also to minimise the energy consumption, which is measured
in terms of the total number of messages (or transmissions) sent. We assume
that the nodes of the network do not know the network, and that they can only
send with a fixed power, meaning they can not adjust the areas sizes that their
messages cover. We believe that under these circumstances the number of
transmissions is a very good measure for the overall energy consumption.
  For random networks, we present a broadcasting algorithm where every node
transmits at most once. We show that our algorithm broadcasts in $O(\log n)$
steps, w.h.p, where $n$ is the number of nodes. We then present a $O(d \log n)$
($d$ is the expected degree) gossiping algorithm using $O(\log n)$ messages per
node.
  For general networks with known diameter $D$, we present a randomised
broadcasting algorithm with optimal broadcasting time $O(D \log (n/D) + \log^2
n)$ that uses an expected number of $O(\log^2 n / \log (n/D))$ transmissions
per node. We also show a tradeoff result between the broadcasting time and the
number of transmissions: we construct a network such that any oblivious
algorithmusing a time-invariant distribution requires $\Omega(\log^2 n / \log
(n/D))$ messages per node in order to finish broadcasting in optimal time. This
demonstrates the tightness of our upper bound. We also show that no oblivious
algorithm can complete broadcasting w.h.p. using $o(\log n)$ messages per node.


title: Intermediate Performance of Rateless Codes

abstract:
  Rateless/fountain codes are designed so that all input symbols can be
recovered from a slightly larger number of coded symbols, with high probability
using an iterative decoder. In this paper we investigate the number of input
symbols that can be recovered by the same decoder, but when the number of coded
symbols available is less than the total number of input symbols. Of course
recovery of all inputs is not possible, and the fraction that can be recovered
will depend on the output degree distribution of the code.
  In this paper we (a) outer bound the fraction of inputs that can be recovered
for any output degree distribution of the code, and (b) design degree
distributions which meet/perform close to this bound. Our results are of
interest for real-time systems using rateless codes, and for Raptor-type
two-stage designs.


title:
A New Approach for Capacity Analysis of Large Dimensional Multi-Antenna
  Channels

abstract:
  This paper adresses the behaviour of the mutual information of correlated
MIMO Rayleigh channels when the numbers of transmit and receive antennas
converge to infinity at the same rate. Using a new and simple approach based on
Poincar\'{e}-Nash inequality and on an integration by parts formula, it is
rigorously established that the mutual information converges to a Gaussian
random variable whose mean and variance are evaluated. These results confirm
previous evaluations based on the powerful but non rigorous replica method. It
is believed that the tools that are used in this paper are simple, robust, and
of interest for the communications engineering community.


title: Algebraic Signal Processing Theory

abstract:
  This paper presents an algebraic theory of linear signal processing. At the
core of algebraic signal processing is the concept of a linear signal model
defined as a triple (A, M, phi), where familiar concepts like the filter space
and the signal space are cast as an algebra A and a module M, respectively, and
phi generalizes the concept of the z-transform to bijective linear mappings
from a vector space of, e.g., signal samples, into the module M. A signal model
provides the structure for a particular linear signal processing application,
such as infinite and finite discrete time, or infinite or finite discrete
space, or the various forms of multidimensional linear signal processing. As
soon as a signal model is chosen, basic ingredients follow, including the
associated notions of filtering, spectrum, and Fourier transform. The shift
operator is a key concept in the algebraic theory: it is the generator of the
algebra of filters A. Once the shift is chosen, a well-defined methodology
leads to the associated signal model. Different shifts correspond to infinite
and finite time models with associated infinite and finite z-transforms, and to
infinite and finite space models with associated infinite and finite
C-transforms (that we introduce). In particular, we show that the 16 discrete
cosine and sine transforms are Fourier transforms for the finite space models.
Other definitions of the shift naturally lead to new signal models and to new
transforms as associated Fourier transforms in one and higher dimensions,
separable and non-separable. We explain in algebraic terms shift-invariance
(the algebra of filters A is commutative), the role of boundary conditions and
signal extensions, the connections between linear transforms and linear finite
Gauss-Markov fields, and several other concepts and connections.


title:
Effect of Finite Rate Feedback on CDMA Signature Optimization and MIMO
  Beamforming Vector Selection

abstract:
  We analyze the effect of finite rate feedback on CDMA (code-division multiple
access) signature optimization and MIMO (multi-input-multi-output) beamforming
vector selection. In CDMA signature optimization, for a particular user, the
receiver selects a signature vector from a codebook to best avoid interference
from other users, and then feeds the corresponding index back to the specified
user. For MIMO beamforming vector selection, the receiver chooses a beamforming
vector from a given codebook to maximize throughput, and feeds back the
corresponding index to the transmitter. These two problems are dual: both can
be modeled as selecting a unit norm vector from a finite size codebook to
"match" a randomly generated Gaussian matrix. In signature optimization, the
least match is required while the maximum match is preferred for beamforming
selection.
  Assuming that the feedback link is rate limited, our main result is an exact
asymptotic performance formulae where the length of the signature/beamforming
vector, the dimensions of interference/channel matrix, and the feedback rate
approach infinity with constant ratios. The proof rests on a large deviation
principle over a random matrix ensemble. Further, we show that random codebooks
generated from the isotropic distritution are asymptotically optimal not only
on average, but also with probability one.


title: Executing the same binary on several operating systems

abstract:
  We notice a way to execute a binary file on Windows and ELF-based systems. It
can be used to create software installers and other applications not exceeding
64 kilo bytes.


title:
On the Decrease Rate of the Non-Gaussianness of the Sum of Independent
  Random Variables

abstract:
  Several proofs of the monotonicity of the non-Gaussianness (divergence with
respect to a Gaussian random variable with identical second order statistics)
of the sum of n independent and identically distributed (i.i.d.) random
variables were published. We give an upper bound on the decrease rate of the
non-Gaussianness which is proportional to the inverse of n, for large n. The
proof is based on the relationship between non-Gaussianness and minimum
mean-square error (MMSE) and causal minimum mean-square error (CMMSE) in the
time-continuous Gaussian channel.