title: Bidding to the Top: VCG and Equilibria of Position-Based Auctions

abstract:
  Many popular search engines run an auction to determine the placement of
advertisements next to search results. Current auctions at Google and Yahoo!
let advertisers specify a single amount as their bid in the auction. This bid
is interpreted as the maximum amount the advertiser is willing to pay per click
on its ad. When search queries arrive, the bids are used to rank the ads
linearly on the search result page. The advertisers pay for each user who
clicks on their ad, and the amount charged depends on the bids of all the
advertisers participating in the auction. In order to be effective, advertisers
seek to be as high on the list as their budget permits, subject to the market.
  We study the problem of ranking ads and associated pricing mechanisms when
the advertisers not only specify a bid, but additionally express their
preference for positions in the list of ads. In particular, we study "prefix
position auctions" where advertiser $i$ can specify that she is interested only
in the top $b_i$ positions.
  We present a simple allocation and pricing mechanism that generalizes the
desirable properties of current auctions that do not have position constraints.
In addition, we show that our auction has an "envy-free" or "symmetric" Nash
equilibrium with the same outcome in allocation and pricing as the well-known
truthful Vickrey-Clarke-Groves (VCG) auction. Furthermore, we show that this
equilibrium is the best such equilibrium for the advertisers in terms of the
profit made by each advertiser. We also discuss other position-based auctions.


title: A new function algebra of EXPTIME functions by safe nested recursion

abstract:
  Bellantoni and Cook have given a function-algebra characterization of the
polynomial-time computable functions via an unbounded recursion scheme which is
called safe recursion. Inspired by their work, we characterize the
exponential-time computable functions with the use of a safe variant of nested
recursion.


title:
Web-Based Enterprise Information Systems Development: The Integrated
  Methodology

abstract:
  The paper considers software development issues for large-scale enterprise
information systems (IS) with databases (DB) in global heterogeneous
distributed computational environment. Due to high IT development rates, the
present-day society has accumulated and rapidly increases an extremely huge
data burden. Manipulating with such huge data arrays becomes an essential
problem, particularly due to their global distribution, heterogeneous and
weak-structured character. The conceptual approach to integrated Internet-based
IS design, development and implementation is presented, including formal
models, software development methodology and original software development
tools for visual problem-oriented development and content management. IS
implementation results proved shortening terms and reducing costs of
implementation compared to commercial software available.


title: Expressing Implicit Semantic Relations without Supervision

abstract:
  We present an unsupervised learning algorithm that mines large text corpora
for patterns that express implicit semantic relations. For a given input word
pair X:Y with some unspecified semantic relations, the corresponding output
list of patterns <P1,...,Pm> is ranked according to how well each pattern Pi
expresses the relations between X and Y. For example, given X=ostrich and
Y=bird, the two highest ranking output patterns are "X is the largest Y" and "Y
such as the X". The output patterns are intended to be useful for finding
further pairs with the same relations, to support the construction of lexicons,
ontologies, and semantic networks. The patterns are sorted by pertinence, where
the pertinence of a pattern Pi for a word pair X:Y is the expected relational
similarity between the given pair and typical pairs for Pi. The algorithm is
empirically evaluated on two tasks, solving multiple-choice SAT word analogy
questions and classifying semantic relations in noun-modifier pairs. On both
tasks, the algorithm achieves state-of-the-art results, performing
significantly better than several alternative pattern ranking algorithms, based
on tf-idf.


title: Object-Based Groupware: Theory, Design and Implementation Issues

abstract:
  Document management software systems are having a wide audience at present.
However, groupware as a term has a wide variety of possible definitions.
Groupware classification attempt is made in this paper. Possible approaches to
groupware are considered including document management, document control and
mailing systems. Lattice theory and concept modelling are presented as a
theoretical background for the systems in question. Current technologies in
state-of-the-art document managenent software are discussed. Design and
implementation aspects for user-friendly integrate enterprise systems are
described. Results for a real system to be implemented are given. Perspectives
of the field in question are discussed.


title:
Enterprise Content Management: Theory and Engineering for Entire
  Lifecycle Support

abstract:
  The paper considers enterprise content management (ECM) issues in global
heterogeneous distributed computational environment. Present-day enterprises
have accumulated a huge data burden. Manipulating with such a bulk becomes an
essential problem, particularly due to its global distribution, heterogeneous
and weak-structured character. The conceptual approach to integrated ECM
lifecycle support is presented, including overview of formal models, software
development methodology and innovative software development tools.
Implementation results proved shortening terms and reducing costs of
implementation compared to commercial software available.


title: Enterprise Portal Development Tools: Problem-Oriented Approach

abstract:
  The paper deals with problem-oriented visual information system (IS)
engineering for enterprise Internet-based applications, which is a vital part
of the whole development process. The suggested approach is based on semantic
network theory and a novel ConceptModeller CASE tool.


title:
ConceptModeller: a Problem-Oriented Visual SDK for Globally Distributed
  Enterprise Systems

abstract:
  The paper describes problem-oriented approach to software development. The
approach is a part of the original integrated methodology of enterprise
Internet-based software design and implementation. All aspects of software
development, from theory to implementation, are covered.


title: Enterprise Portal: from Model to Implementation

abstract:
  Portal technology can significantly improve the entire corporate information
infrastructure. The approach proposed is based on rigorous and consistent
(meta)data model and provides for efficient and accurate front-end integration
of heterogeneous corporate applications including enterprise resource planning
(ERP) systems, multimedia data warehouses and proprietary content databases.
The methodology proposed embraces entire software lifecycle; it is illustrated
by an enterprise-level Intranet portal implementation.


title: Abstract Machine as a Model of Content Management Information System

abstract:
  Enterprise content management is an urgent issue of current scientific and
practical activities in software design and implementation. However, papers
known as yet give insufficient coverage of theoretical background of the
software in question. The paper gives an attempt of building a state-based
model of content management. In accordance with the theoretical principles
outlined, a content management information system (CMIS) has been implemented
in a large international oil-and-gas group of companies.


title: Integrating Enterprise Software Applications with Web Portal Technology

abstract:
  Web-portal based approach can significantly improve the entire corporate
information infrastructure. The approach proposed provides for rapid and
accurate front-end integration of heterogeneous corporate applications
including enterprise resource planning (ERP) systems. Human resources ERP
component and multimedia data warehouse implementations are discussed as
essential instances.


title: The Integrated Approach to ERP: Embracing the Web

abstract:
  Integrated approach to enterprise resource planning (ERP) software design and
implementation can significantly improve the entire corporate information
infrastructure and it helps to benefit from power of Internet services. The
approach proposed provides for corporate Web portal integrity, consistency,
urgency and front-end data processing. Human resources (HR) ERP component
implementation is discussed as an essential instance.


title: Enterprise Resource Planning Systems: the Integrated Approach

abstract:
  Enterprise resource planning (ERP) systems enjoy an increasingly wide
coverage. However, no truly integrate solution has been proposed as yet. ERP
classification is given. Recent trends in commercial systems are analyzed on
the basis of human resources (HR) management software. An innovative "straight
through" design and implementation process of an open, secure, and scalable
integrated event-driven enterprise solution is suggested. Implementation
results are presented.


title:
Towards Implementing an Enterprise Groupware-Integrated Human Resources
  Information System

abstract:
  Human resources management software is having a wide audience at present.
However, no truly integrate solution has been proposed yet to improve the
systems concerned. Approaches to extra data collection for appraisal
decision-making are considered on the concept modeling theoretical basis.
Current technologies in state-of-the-art HR management software are compared.
Design and implementation aspects for a Web-wired truly integrated secure and
scalable event-driven enterprise system are described. Benchmark results are
presented. Field perspectives are discussed.


title: Tardos fingerprinting is better than we thought

abstract:
  We review the fingerprinting scheme by Tardos and show that it has a much
better performance than suggested by the proofs in Tardos' original paper. In
particular, the length of the codewords can be significantly reduced.
  First we generalize the proofs of the false positive and false negative error
probabilities with the following modifications: (1) we replace Tardos'
hard-coded numbers by variables and (2) we allow for independently chosen false
positive and false negative error rates. It turns out that all the
collusion-resistance properties can still be proven when the code length is
reduced by a factor of more than 2.
  Second, we study the statistical properties of the fingerprinting scheme, in
particular the average and variance of the accusations. We identify which
colluder strategy forces the content owner to employ the longest code. Using a
gaussian approximation for the probability density functions of the
accusations, we show that the required false negative and false positive error
rate can be achieved with codes that are a factor 2 shorter than required for
rigid proofs.
  Combining the results of these two approaches, we show that the Tardos scheme
can be used with a code length approximately 5 times shorter than in the
original construction.


title:
On q-ary codes correcting all unidirectional errors of a limited
  magnitude

abstract:
  We consider codes over the alphabet Q={0,1,..,q-1}intended for the control of
unidirectional errors of level l. That is, the transmission channel is such
that the received word cannot contain both a component larger than the
transmitted one and a component smaller than the transmitted one. Moreover, the
absolute value of the difference between a transmitted component and its
received version is at most l.
  We introduce and study q-ary codes capable of correcting all unidirectional
errors of level l. Lower and upper bounds for the maximal size of those codes
are presented.
  We also study codes for this aim that are defined by a single equation on the
codeword coordinates(similar to the Varshamov-Tenengolts codes for correcting
binary asymmetric errors). We finally consider the problem of detecting all
unidirectional errors of level l.


title: Self-Replication and Self-Assembly for Manufacturing

abstract:
  It has been argued that a central objective of nanotechnology is to make
products inexpensively, and that self-replication is an effective approach to
very low-cost manufacturing. The research presented here is intended to be a
step towards this vision. We describe a computational simulation of nanoscale
machines floating in a virtual liquid. The machines can bond together to form
strands (chains) that self-replicate and self-assemble into user-specified
meshes. There are four types of machines and the sequence of machine types in a
strand determines the shape of the mesh they will build. A strand may be in an
unfolded state, in which the bonds are straight, or in a folded state, in which
the bond angles depend on the types of machines. By choosing the sequence of
machine types in a strand, the user can specify a variety of polygonal shapes.
A simulation typically begins with an initial unfolded seed strand in a soup of
unbonded machines. The seed strand replicates by bonding with free machines in
the soup. The child strands fold into the encoded polygonal shape, and then the
polygons drift together and bond to form a mesh. We demonstrate that a variety
of polygonal meshes can be manufactured in the simulation, by simply changing
the sequence of machine types in the seed.


title: Leading strategies in competitive on-line prediction

abstract:
  We start from a simple asymptotic result for the problem of on-line
regression with the quadratic loss function: the class of continuous
limited-memory prediction strategies admits a "leading prediction strategy",
which not only asymptotically performs at least as well as any continuous
limited-memory strategy but also satisfies the property that the excess loss of
any continuous limited-memory strategy is determined by how closely it imitates
the leading strategy. More specifically, for any class of prediction strategies
constituting a reproducing kernel Hilbert space we construct a leading
strategy, in the sense that the loss of any prediction strategy whose norm is
not too large is determined by how closely it imitates the leading strategy.
This result is extended to the loss functions given by Bregman divergences and
by strictly proper scoring rules.


title:
A polynomial-time approximation algorithm for the number of k-matchings
  in bipartite graphs

abstract:
  We show that the number of $k$-matching in a given undirected graph
  $G$ is equal to the number of perfect matching of the corresponding graph
  $G_k$ on an even number of vertices divided by a suitable factor.
  If $G$ is bipartite then one can construct a bipartite $G_k$.
  For bipartite graphs this result implies that the number of $k$-matching has
a polynomial-time approximation algorithm. The above results are extended to
permanents and hafnians of corresponding matrices.


title: Competing with Markov prediction strategies

abstract:
  Assuming that the loss function is convex in the prediction, we construct a
prediction strategy universal for the class of Markov prediction strategies,
not necessarily continuous. Allowing randomization, we remove the requirement
of convexity.


title: Multicasting with selective delivery: A SafetyNet for vertical handoffs

abstract:
  In future mobility support will require handling roaming in heterogeneous
access networks. In order to enable seamless roaming it is necessary to
minimize the impact of the vertical handoffs. Localized mobility management
schemes such as FMIPv6 and HMIPv6 do not provide sufficient handoff
performance, since they have been designed for horizontal handoffs. In this
paper, we propose the SafetyNet protocol, which allows a Mobile Node to perform
seamless vertical handoffs. Further, we propose a handoff timing algorithm
which allows a Mobile Node to delay or even completely avoid upward vertical
handoffs. We implement the SafetyNet protocol and compare its performance with
the Fast Handovers for Mobile IPv6 protocol in our wireless test bed and
analyze the results. The experimental results indicate that the proposed
SafetyNet protocol can provide an improvement of up to 95% for TCP performance
in vertical handoffs, when compared with FMIPv6 and an improvement of 64% over
FMIPv6 with bicasting. We use numerical analysis of the protocol to show that
its signaling and data transmission overhead is comparable to Fast Mobile IPv6
and significantly smaller than that of FMIPv6 with bicasting.


title: A Foundation to Perception Computing, Logic and Automata

abstract:
  In this report, a novel approach to intelligence and learning is introduced,
this approach is based on what we call 'perception logic'. Based on this logic,
a computing mechanism and automata are introduced. Multi-resolution analysis of
perceptual information is given, in which learning is accomplished in at most
O(log(N))epochs, where N is the number of samples, and the convergence is
guarnteed. This approach combines the favors of computational modeles in the
sense that they are structured and mathematically well-defined, and the
adaptivity of soft computing approaches, in addition to the continuity and
real-time response of dynamical systems.


title: Parallel repetition: simplifications and the no-signaling case

abstract:
  Consider a game where a refereed a referee chooses (x,y) according to a
publicly known distribution P_XY, sends x to Alice, and y to Bob. Without
communicating with each other, Alice responds with a value "a" and Bob responds
with a value "b". Alice and Bob jointly win if a publicly known predicate
Q(x,y,a,b) holds.
  Let such a game be given and assume that the maximum probability that Alice
and Bob can win is v<1. Raz (SIAM J. Comput. 27, 1998) shows that if the game
is repeated n times in parallel, then the probability that Alice and Bob win
all games simultaneously is at most v'^(n/log(s)), where s is the maximal
number of possible responses from Alice and Bob in the initial game, and v' is
a constant depending only on v.
  In this work, we simplify Raz's proof in various ways and thus shorten it
significantly. Further we study the case where Alice and Bob are not restricted
to local computations and can use any strategy which does not imply
communication among them.


title:
Stylized Facts in Internal Rates of Return on Stock Index and its
  Derivative Transactions

abstract:
  Universal features in stock markets and their derivative markets are studied
by means of probability distributions in internal rates of return on buy and
sell transaction pairs. Unlike the stylized facts in log normalized returns,
the probability distributions for such single asset encounters encorporate the
time factor by means of the internal rate of return defined as the continuous
compound interest. Resulting stylized facts are shown in the probability
distributions derived from the daily series of TOPIX, S & P 500 and FTSE 100
index close values. The application of the above analysis to minute-tick data
of NIKKEI 225 and its futures market, respectively, reveals an interesting
diffference in the behavior of the two probability distributions, in case a
threshold on the minimal duration of the long position is imposed. It is
therefore suggested that the probability distributions of the internal rates of
return could be used for causality mining between the underlying and derivative
stock markets. The highly specific discrete spectrum, which results from noise
trader strategies as opposed to the smooth distributions observed for
fundamentalist strategies in single encounter transactions may be also useful
in deducing the type of investment strategy from trading revenues of small
portfolio investors.


title:
Logic Column 16: Higher-Order Abstract Syntax: Setting the Record
  Straight

abstract:
  This article responds to a critique of higher-order abstract syntax appearing
in Logic Column 14, ``Nominal Logic and Abstract Syntax'', cs.LO/0511025.


title:
Employing Trusted Computing for the forward pricing of pseudonyms in
  reputation systems

abstract:
  Reputation and recommendation systems are fundamental for the formation of
community market places. Yet, they are easy targets for attacks which disturb a
market's equilibrium and are often based on cheap pseudonyms used to submit
ratings. We present a method to price ratings using trusted computing, based on
pseudonymous tickets.


title:
Target Type Tracking with PCR5 and Dempster's rules: A Comparative
  Analysis

abstract:
  In this paper we consider and analyze the behavior of two combinational rules
for temporal (sequential) attribute data fusion for target type estimation. Our
comparative analysis is based on Dempster's fusion rule proposed in
Dempster-Shafer Theory (DST) and on the Proportional Conflict Redistribution
rule no. 5 (PCR5) recently proposed in Dezert-Smarandache Theory (DSmT). We
show through very simple scenario and Monte-Carlo simulation, how PCR5 allows a
very efficient Target Type Tracking and reduces drastically the latency delay
for correct Target Type decision with respect to Demspter's rule. For cases
presenting some short Target Type switches, Demspter's rule is proved to be
unable to detect the switches and thus to track correctly the Target Type
changes. The approach proposed here is totally new, efficient and promising to
be incorporated in real-time Generalized Data Association - Multi Target
Tracking systems (GDA-MTT) and provides an important result on the behavior of
PCR5 with respect to Dempster's rule. The MatLab source code is provided in


title: Levels of Product Differentiation in the Global Mobile Phones Market

abstract:
  The sixth product level called compliant product is a connecting element
between the physical product characteristics and the strategy of the producer
company. The article discusses the differentiation among the product offers of
companies working in the global markets, as well as the strategies which they
use and could use in that respect.


title: Geometric definition of a new skeletonization concept

abstract:
  The Divider set, as an innovative alternative concept to maximal disks,
Voronoi sets and cut loci, is presented with a formal definition based on
topology and differential geometry. The relevant mathematical theory by
previous authors and a comparison with other medial axis definitions is
presented. Appropriate applications are proposed and examined.


title: Modeling Adversaries in a Logic for Security Protocol Analysis

abstract:
  Logics for security protocol analysis require the formalization of an
adversary model that specifies the capabilities of adversaries. A common model
is the Dolev-Yao model, which considers only adversaries that can compose and
replay messages, and decipher them with known keys. The Dolev-Yao model is a
useful abstraction, but it suffers from some drawbacks: it cannot handle the
adversary knowing protocol-specific information, and it cannot handle
probabilistic notions, such as the adversary attempting to guess the keys. We
show how we can analyze security protocols under different adversary models by
using a logic with a notion of algorithmic knowledge. Roughly speaking,
adversaries are assumed to use algorithms to compute their knowledge; adversary
capabilities are captured by suitable restrictions on the algorithms used. We
show how we can model the standard Dolev-Yao adversary in this setting, and how
we can capture more general capabilities including protocol-specific knowledge
and guesses.


title: Fusion of qualitative beliefs using DSmT

abstract:
  This paper introduces the notion of qualitative belief assignment to model
beliefs of human experts expressed in natural language (with linguistic
labels). We show how qualitative beliefs can be efficiently combined using an
extension of Dezert-Smarandache Theory (DSmT) of plausible and paradoxical
quantitative reasoning to qualitative reasoning. We propose a new arithmetic on
linguistic labels which allows a direct extension of classical DSm fusion rule
or DSm Hybrid rules. An approximate qualitative PCR5 rule is also proposed
jointly with a Qualitative Average Operator. We also show how crisp or interval
mappings can be used to deal indirectly with linguistic labels. A very simple
example is provided to illustrate our qualitative fusion rules.


title: A Finite Equational Base for CCS with Left Merge and Communication Merge

abstract:
  Using the left merge and communication merge from ACP, we present an
equational base (i.e., a ground-complete and $\omega$-complete set of valid
equations) for the fragment of CCS without recursion, restriction and
relabelling. Our equational base is finite if the set of actions is finite.


title:
An Introduction to the DSm Theory for the Combination of Paradoxical,
  Uncertain, and Imprecise Sources of Information

abstract:
  The management and combination of uncertain, imprecise, fuzzy and even
paradoxical or high conflicting sources of information has always been, and
still remains today, of primal importance for the development of reliable
modern information systems involving artificial reasoning. In this
introduction, we present a survey of our recent theory of plausible and
paradoxical reasoning, known as Dezert-Smarandache Theory (DSmT) in the
literature, developed for dealing with imprecise, uncertain and paradoxical
sources of information. We focus our presentation here rather on the
foundations of DSmT, and on the two important new rules of combination, than on
browsing specific applications of DSmT available in literature. Several simple
examples are given throughout the presentation to show the efficiency and the
generality of this new approach.


title: On a solution to display non-filled-in quaternionic Julia sets

abstract:
  During early 1980s, the so-called `escape time' method, developed to display
the Julia sets for complex dynamical systems, was exported to quaternions in
order to draw analogous pictures in this wider numerical field. Despite of the
fine results in the complex plane, where all topological configurations of
Julia sets have been successfully displayed, the `escape time' method fails to
render properly the non-filled-in variety of quaternionic Julia sets. So their
digital visualisation remained an open problem for several years. Both the
solution for extending this old method to non-filled-in quaternionic Julia sets
and its implementation into a program are explained here.


title: Separating the articles of authors with the same name

abstract:
  I describe a method to separate the articles of different authors with the
same name. It is based on a distance between any two publications, defined in
terms of the probability that they would have as many coincidences if they were
drawn at random from all published documents. Articles with a given author name
are then clustered according to their distance, so that all articles in a
cluster belong very likely to the same author. The method has proven very
useful in generating groups of papers that are then selected manually. This
simplifies considerably citation analysis when the author publication lists are
not available.


title: A field-theory motivated approach to symbolic computer algebra

abstract:
  Field theory is an area in physics with a deceptively compact notation.
Although general purpose computer algebra systems, built around generic
list-based data structures, can be used to represent and manipulate
field-theory expressions, this often leads to cumbersome input formats,
unexpected side-effects, or the need for a lot of special-purpose code. This
makes a direct translation of problems from paper to computer and back
needlessly time-consuming and error-prone. A prototype computer algebra system
is presented which features TeX-like input, graph data structures, lists with
Young-tableaux symmetries and a multiple-inheritance property system. The
usefulness of this approach is illustrated with a number of explicit
field-theory problems.


title:
A Graph-based Framework for Transmission of Correlated Sources over
  Broadcast Channels

abstract:
  In this paper we consider the communication problem that involves
transmission of correlated sources over broadcast channels. We consider a
graph-based framework for this information transmission problem. The system
involves a source coding module and a channel coding module. In the source
coding module, the sources are efficiently mapped into a nearly semi-regular
bipartite graph, and in the channel coding module, the edges of this graph are
reliably transmitted over a broadcast channel. We consider nearly semi-regular
bipartite graphs as discrete interface between source coding and channel coding
in this multiterminal setting. We provide an information-theoretic
characterization of (1) the rate of exponential growth (as a function of the
number of channel uses) of the size of the bipartite graphs whose edges can be
reliably transmitted over a broadcast channel and (2) the rate of exponential
growth (as a function of the number of source samples) of the size of the
bipartite graphs which can reliably represent a pair of correlated sources to
be transmitted over a broadcast channel.


title: On the randomness of independent experiments

abstract:
  Given a probability distribution P, what is the minimum amount of bits needed
to store a value x sampled according to P, such that x can later be recovered
(except with some small probability)? Or, what is the maximum amount of uniform
randomness that can be extracted from x? Answering these and similar
information-theoretic questions typically boils down to computing so-called
smooth entropies. In this paper, we derive explicit and almost tight bounds on
the smooth entropies of n-fold product distributions.


title: The minimum linear arrangement problem on proper interval graphs

abstract:
  We present a linear time algorithm for the minimum linear arrangement problem
on proper interval graphs. The obtained ordering is a 4-approximation for
general interval graphs


title: Stability in multidimensional Size Theory

abstract:
  This paper proves that in Size Theory the comparison of multidimensional size
functions can be reduced to the 1-dimensional case by a suitable change of
variables. Indeed, we show that a foliation in half-planes can be given, such
that the restriction of a multidimensional size function to each of these
half-planes turns out to be a classical size function in two scalar variables.
This leads to the definition of a new distance between multidimensional size
functions, and to the proof of their stability with respect to that distance.


title: MIMO scheme performance and detection in epsilon noise

abstract:
  New approach for analysis and decoding MIMO signaling is developed for usual
model of nongaussion noise consists of background and impulsive noise named
epsilon - noise. It is shown that non-gaussion noise performance significantly
worse than gaussion ones. Stimulation results strengthen out theory. Robust in
statistical sense detection rule is suggested for such kind of noise features
much best robust detector performance than detector designed for Gaussian noise
in impulsive environment and modest margin in background noise. Proposed
algorithms performance are comparable with developed potential bound. Proposed
tool, is crucial issue for MIMO communication system design, since real noise
environment has impulsive character that contradict with wide used Gaussian
approach, so real MIMO performance much different for Gaussian a non-Gaussian
noise model.


title: The Many Faces of Rationalizability

abstract:
  The rationalizability concept was introduced in \cite{Ber84} and
  \cite{Pea84} to assess what can be inferred by rational players in a
non-cooperative game in the presence of common knowledge. However, this notion
can be defined in a number of ways that differ in seemingly unimportant minor
details. We shed light on these differences, explain their impact, and clarify
for which games these definitions coincide. Then we apply the same analysis to
explain the differences and similarities between various ways the iterated
elimination of strictly dominated strategies was defined in the literature.
This allows us to clarify the results of \cite{DS02} and \cite{CLL05} and
improve upon them. We also consider the extension of these results to strict
dominance by a mixed strategy. Our approach is based on a general study of the
operators on complete lattices. We allow transfinite iterations of the
considered operators and clarify the need for them. The advantage of such a
general approach is that a number of results, including order independence for
some of the notions of rationalizability and strict dominance, come for free.


title:
Opti{c,m}al: Optical/Optimal Routing in Massively Dense Wireless
  Networks

abstract:
  We study routing for massively dense wireless networks, i.e., wireless
networks that contain so many nodes that, in addition to their usual
microscopic description, a novel macroscopic description becomes possible. The
macroscopic description is not detailed, but nevertheless contains enough
information to permit a meaningful study and performance optimization of the
network. Within this context, we continue and significantly expand previous
work on the analogy between optimal routing and the propagation of light
according to the laws of Geometrical Optics. Firstly, we pose the analogy in a
more general framework than previously, notably showing how the eikonal
equation, which is the central equation of Geometrical Optics, also appears in
the networking context. Secondly, we develop a methodology for calculating the
cost function, which is the function describing the network at the macroscopic
level. We apply this methodology for two important types of networks: bandwidth
limited and energy limited.


title:
Pull-Based Data Broadcast with Dependencies: Be Fair to Users, not to
  Items

abstract:
  Broadcasting is known to be an efficient means of disseminating data in
wireless communication environments (such as Satellite, mobile phone
networks,...). It has been recently observed that the average service time of
broadcast systems can be considerably improved by taking into consideration
existing correlations between requests. We study a pull-based data broadcast
system where users request possibly overlapping sets of items; a request is
served when all its requested items are downloaded. We aim at minimizing the
average user perceived latency, i.e. the average flow time of the requests. We
first show that any algorithm that ignores the dependencies can yield arbitrary
bad performances with respect to the optimum even if it is given arbitrary
extra resources. We then design a $(4+\epsilon)$-speed
$O(1+1/\epsilon^2)$-competitive algorithm for this setting that consists in 1)
splitting evenly the bandwidth among each requested set and in 2) broadcasting
arbitrarily the items still missing in each set into the bandwidth the set has
received. Our algorithm presents several interesting features: it is simple to
implement, non-clairvoyant, fair to users so that no user may starve for a long
period of time, and guarantees good performances in presence of correlations
between user requests (without any change in the broadcast protocol). We also
present a $ (4+\epsilon)$-speed $O(1+1/\epsilon^3)$-competitive algorithm which
broadcasts at most one item at any given time and preempts each item broadcast
at most once on average. As a side result of our analysis, we design a
competitive algorithm for a particular setting of non-clairvoyant job
scheduling with dependencies, which might be of independent interest.


title: Localization for Anchoritic Sensor Networks

abstract:
  We introduce a class of anchoritic sensor networks, where communications
between sensor nodes is undesirable or infeasible, e.g., due to harsh
environment, energy constraints, or security considerations.


title: Towards "Propagation = Logic + Control"

abstract:
  Constraint propagation algorithms implement logical inference. For
efficiency, it is essential to control whether and in what order basic
inference steps are taken. We provide a high-level framework that clearly
differentiates between information needed for controlling propagation versus
that needed for the logical semantics of complex constraints composed from
primitive ones. We argue for the appropriateness of our controlled propagation
framework by showing that it captures the underlying principles of manually
designed propagation algorithms, such as literal watching for unit clause
propagation and the lexicographic ordering constraint. We provide an
implementation and benchmark results that demonstrate the practicality and
efficiency of our framework.


title: ACD Term Rewriting

abstract:
  We introduce Associative Commutative Distributive Term Rewriting (ACDTR), a
rewriting language for rewriting logical formulae. ACDTR extends AC term
rewriting by adding distribution of conjunction over other operators.
Conjunction is vital for expressive term rewriting systems since it allows us
to require that multiple conditions hold for a term rewriting rule to be used.
ACDTR uses the notion of a "conjunctive context", which is the conjunction of
constraints that must hold in the context of a term, to enable the programmer
to write very expressive and targeted rewriting rules. ACDTR can be seen as a
general logic programming language that extends Constraint Handling Rules and
AC term rewriting. In this paper we define the semantics of ACDTR and describe
our prototype implementation.


title: Infinite Qualitative Simulations by Means of Constraint Programming

abstract:
  We introduce a constraint-based framework for studying infinite qualitative
simulations concerned with contingencies such as time, space, shape, size,
abstracted into a finite set of qualitative relations. To define the
simulations, we combine constraints that formalize the background knowledge
concerned with qualitative reasoning with appropriate inter-state constraints
that are formulated using linear temporal logic. We implemented this approach
in a constraint programming system by drawing on ideas from bounded model
checking. The resulting system allows us to test and modify the problem
specifications in a straightforward way and to combine various knowledge
aspects.


title: The single-serving channel capacity

abstract:
  In this paper we provide the answer to the following question: Given a noisy
channel and epsilon>0, how many bits can be transmitted with an error of at
most epsilon by a single use of the channel?


title: Relation Variables in Qualitative Spatial Reasoning

abstract:
  We study an alternative to the prevailing approach to modelling qualitative
spatial reasoning (QSR) problems as constraint satisfaction problems. In the
standard approach, a relation between objects is a constraint whereas in the
alternative approach it is a variable. The relation-variable approach greatly
simplifies integration and implementation of QSR. To substantiate this point,
we discuss several QSR algorithms from the literature which in the
relation-variable approach reduce to the customary constraint propagation
algorithm enforcing generalised arc-consistency.


title: Quasi-friendly sup-interpretations

abstract:
  In a previous paper, the sup-interpretation method was proposed as a new tool
to control memory resources of first order functional programs with pattern
matching by static analysis. Basically, a sup-interpretation provides an upper
bound on the size of function outputs. In this former work, a criterion, which
can be applied to terminating as well as non-terminating programs, was
developed in order to bound polynomially the stack frame size. In this paper,
we suggest a new criterion which captures more algorithms computing values
polynomially bounded in the size of the inputs. Since this work is related to
quasi-interpretations, we compare the two notions obtaining two main features.
The first one is that, given a program, we have heuristics for finding a
sup-interpretation when we consider polynomials of bounded degree. The other
one consists in the characterizations of the set of function computable in
polynomial time and in polynomial space.


title:
The Shannon capacity of a graph and the independence numbers of its
  powers

abstract:
  The independence numbers of powers of graphs have been long studied, under
several definitions of graph products, and in particular, under the strong
graph product. We show that the series of independence numbers in strong powers
of a fixed graph can exhibit a complex structure, implying that the Shannon
Capacity of a graph cannot be approximated (up to a sub-polynomial factor of
the number of vertices) by any arbitrarily large, yet fixed, prefix of the
series. This is true even if this prefix shows a significant increase of the
independence number at a given power, after which it stabilizes for a while.


title: Expressing Security Properties Using Selective Interleaving Functions

abstract:
  McLean's notion of Selective Interleaving Functions (SIFs) is perhaps the
best-known attempt to construct a framework for expressing various security
properties. We examine the expressive power of SIFs carefully. We show that
SIFs cannot capture nondeducibility on strategies (NOS). We also prove that the
set of security properties expressed with SIFs is not closed under conjunction,
from which it follows that separability is strictly stronger than double
generalized noninterference. However, we show that if we generalize the notion
of SIF in a natural way, then NOS is expressible, and the set of security
properties expressible by generalized SIFs is closed under conjunction.


title: Optimal resource allocation for OFDM multiuser channels

abstract:
  In this paper, a unifying framework for orthogonal frequency division
multiplexing (OFDM) multiuser resource allocation is presented. The isolated
seeming problems of maximizing a weighted sum of rates for a given power budget
$\bar{P}$ and minimizing sum power for given rate requirements
$\mathbf{\bar{R}}$ can be interpreted jointly in this framework. To this end we
embed the problems in a higher dimensional space. Based on these results, we
subsequently consider the combined problem of maximizing a weighted sum of
rates under given rate requirements $\mathbf{\bar{R}}$ and a fixed power budget
$\bar{P}$. This new problem is challenging, since the additional constraints do
not allow to use the hitherto existing approaches. Interestingly, the optimal
decoding orders turn out to be the ordering of the Lagrangian factors in all
problems.


title: Cryptanalysis of an Encryption Scheme Based on Blind Source Separation

abstract:
  Recently Lin et al. proposed a method of using the underdetermined BSS (blind
source separation) problem to realize image and speech encryption. In this
paper, we give a cryptanalysis of this BSS-based encryption and point out that
it is not secure against known/chosen-plaintext attack and chosen-ciphertext
attack. In addition, there exist some other security defects: low sensitivity
to part of the key and the plaintext, a ciphertext-only differential attack,
divide-and-conquer (DAC) attack on part of the key. We also discuss the role of
BSS in Lin et al.'s efforts towards cryptographically secure ciphers.


title:
User-Network Association in a WLAN-UMTS Hybrid Cell: Global & Individual
  Optimality

abstract:
  We study optimal user-network association in an integrated 802.11 WLAN and
3G-UMTS hybrid cell. Assuming saturated resource allocation on the downlink of
WLAN and UMTS networks and a single QoS class of mobiles arriving at an average
location in the hybrid cell, we formulate the problem with two different
approaches: Global and Individual optimality. The Globally optimal association
is formulated as an SMDP (Semi Markov Decision Process) connection routing
decision problem where rewards comprise a financial gain component and an
aggregate network throughput component. The corresponding Dynamic Programming
equations are solved using Value Iteration method and a stationary optimal
policy with neither convex nor concave type switching curve structure is
obtained. Threshold type and symmetric switching curves are observed for the
analogous homogenous network cases. The Individual optimality is studied under
a non-cooperative dynamic game framework with expected service time of a mobile
as the decision cost criteria. It is shown that individual optimality in a
WLAN-UMTS hybrid cell, results in a threshold policy curve of descending
staircase form with increasing Poisson arrival rate of mobiles.


title:
New Cross-Layer Channel Switching Policy for TCP Transmission on 3G UMTS
  Downlink

abstract:
  In 3G UMTS, two main transport channels have been provided for downlink data
transmission: a common FACH channel and a dedicated DCH channel. The
performance of TCP in UMTS depends much on the channel switching policy used.
In this paper, we propose and analyze three new basic threshold-based channel
switching policies for UMTS that we name as QS (Queue Size), FS (Flow Size) and
QSFS (QS & FS combined) policy. These policies significantly improve over a
modified threshold policy in [1] by about 17% in response time metrics. We
further propose and evaluate a new improved switching policy that we call
FS-DCH (at-least flow-size threshold on DCH) policy. This policy is biased
towards short TCP flows of few packets and is thus a cross-layer policy that
improves the performance of TCP by giving priority to the initial few packets
of a flow on the fast DCH channel. Extensive simulation results confirm this
improvement for the case when number of TCP connections is low.


title: myADS-arXiv - a Tailor-Made, Open Access, Virtual Journal

abstract:
  The myADS-arXiv service provides the scientific community with a one stop
shop for staying up-to-date with a researcher's field of interest. The service
provides a powerful and unique filter on the enormous amount of bibliographic
information added to the ADS on a daily basis. It also provides a complete view
with the most relevant papers available in the subscriber's field of interest.
With this service, the subscriber will get to know the lastest developments,
popular trends and the most important papers. This makes the service not only
unique from a technical point of view, but also from a content point of view.
On this poster we will argue why myADS-arXiv is a tailor-made, open access,
virtual journal and we will illustrate its unique character.


title: Using Sets of Probability Measures to Represent Uncertainty

abstract:
  I explore the use of sets of probability measures as a representation of
uncertainty.


title: Guessing Facets: Polytope Structure and Improved LP Decoder

abstract:
  A new approach for decoding binary linear codes by solving a linear program
(LP) over a relaxed codeword polytope was recently proposed by Feldman et al.
In this paper we investigate the structure of the polytope used in the LP
relaxation decoding. We begin by showing that for expander codes, every
fractional pseudocodeword always has at least a constant fraction of
non-integral bits. We then prove that for expander codes, the active set of any
fractional pseudocodeword is smaller by a constant fraction than the active set
of any codeword. We exploit this fact to devise a decoding algorithm that
provably outperforms the LP decoder for finite blocklengths. It proceeds by
guessing facets of the polytope, and resolving the linear program on these
facets. While the LP decoder succeeds only if the ML codeword has the highest
likelihood over all pseudocodewords, we prove that for expander codes the
proposed algorithm succeeds even with a constant number of pseudocodewords of
higher likelihood. Moreover, the complexity of the proposed algorithm is only a
constant factor larger than that of the LP decoder.


title: On Quasi-Interpretations, Blind Abstractions and Implicit Complexity

abstract:
  Quasi-interpretations are a technique to guarantee complexity bounds on
first-order functional programs: with termination orderings they give in
particular a sufficient condition for a program to be executable in polynomial
time, called here the P-criterion. We study properties of the programs
satisfying the P-criterion, in order to better understand its intensional
expressive power. Given a program on binary lists, its blind abstraction is the
nondeterministic program obtained by replacing lists by their lengths (natural
numbers). A program is blindly polynomial if its blind abstraction terminates
in polynomial time. We show that all programs satisfying a variant of the
P-criterion are in fact blindly polynomial. Then we give two extensions of the
P-criterion: one by relaxing the termination ordering condition, and the other
one (the bounded value property) giving a necessary and sufficient condition
for a program to be polynomial time executable, with memoisation.


title: Secure Positioning of Mobile Terminals with Simplex Radio Communication

abstract:
  With the rapid spread of various mobile terminals in our society, the
importance of secure positioning is growing for wireless networks in
adversarial settings. Recently, several authors have proposed a secure
positioning mechanism of mobile terminals which is based on the geometric
property of wireless node placement, and on the postulate of modern physics
that a propagation speed of information never exceeds the velocity of light. In
particular, they utilize the measurements of the round-trip time of radio
signal propagation and bidirectional communication for variants of the
challenge-and-response. In this paper, we propose a novel means to construct
the above mechanism by use of unidirectional communication instead of
bidirectional communication. Our proposal is based on the assumption that a
mobile terminal incorporates a high-precision inner clock in a tamper-resistant
protected area. In positioning, the mobile terminal uses its inner clock and
the time and location information broadcasted by radio from trusted stations.
Our proposal has a major advantage in protecting the location privacy of mobile
terminal users, because the mobile terminal need not provide any information to
the trusted stations through positioning procedures. Besides, our proposal is
free from the positioning error due to claimant's processing-time fluctuations
in the challenge-and-response, and is well-suited for mobile terminals in the
open air, or on the move at high speed, in terms of practical usage. We analyze
the security, the functionality, and the feasibility of our proposal in
comparison to previous proposals.


title: Satisfying KBO Constraints

abstract:
  This paper presents two new approaches to prove termination of rewrite
systems with the Knuth-Bendix order efficiently. The constraints for the weight
function and for the precedence are encoded in (pseudo-)propositional logic and
the resulting formula is tested for satisfiability. Any satisfying assignment
represents a weight function and a precedence such that the induced
Knuth-Bendix order orients the rules of the encoded rewrite system from left to
right.


title: A Study on Learnability for Rigid Lambek Grammars

abstract:
  We present basic notions of Gold's "learnability in the limit" paradigm,
first presented in 1967, a formalization of the cognitive process by which a
native speaker gets to grasp the underlying grammar of his/her own native
language by being exposed to well formed sentences generated by that grammar.
Then we present Lambek grammars, a formalism issued from categorial grammars
which, although not as expressive as needed for a full formalization of natural
languages, is particularly suited to easily implement a natural interface
between syntax and semantics. In the last part of this work, we present a
learnability result for Rigid Lambek grammars from structured examples.


title: Security Assessment of E-Tax Filing Websites

abstract:
  Technical security is only part of E-Commerce security operations; human
usability and security perception play major and sometimes dominating factors.
For instance, slick websites with impressive security icons but no real
technical security are often perceived by users to be trustworthy (and thus
more profitable) than plain vanilla websites that use powerful encryption for
transmission and server protection. We study one important type of E-Commerce
transaction website, E-Tax Filing, that is exposed to large populations. We
assess a large number of international (5), Federal (USA), and state E-Tax
filing websites (38) for both technical security protection and human
perception of security. As a result of this assessment, we identify security
best practices across these E-Tax Filing websites and recommend additional
security techniques that have not been found in current use by E-Tax Filing
websites.


title: Resource Usage Analysis for the Pi-Calculus

abstract:
  We propose a type-based resource usage analysis for the π-calculus
extended with resource creation/access primitives. The goal of the resource
usage analysis is to statically check that a program accesses resources such as
files and memory in a valid manner. Our type system is an extension of previous
behavioral type systems for the π-calculus, and can guarantee the safety
property that no invalid access is performed, as well as the property that
necessary accesses (such as the close operation for a file) are eventually
performed unless the program diverges. A sound type inference algorithm for the
type system is also developed to free the programmer from the burden of writing
complex type annotations. Based on the algorithm, we have implemented a
prototype resource usage analyzer for the π-calculus. To the authors'
knowledge, ours is the first type-based resource usage analysis that deals with
an expressive concurrent language like the pi-calculus.


title: Reversal Complexity Revisited

abstract:
  We study a generalized version of reversal bounded Turing machines where,
apart from several tapes on which the number of head reversals is bounded by
r(n), there are several further tapes on which head reversals remain
unrestricted, but size is bounded by s(n). Recently, such machines were
introduced as a formalization of a computation model that restricts random
access to external memory and internal memory space. Here, each of the tapes
with a restriction on the head reversals corresponds to an external memory
device, and the tapes of restricted size model internal memory. We use
ST(r(n),s(n),O(1)) to denote the class of all problems that can be solved by
deterministic Turing machines that comply to the above resource bounds.
Similarly, NST and RST, respectively, are used for the corresponding
nondeterministic and randomized classes.
  While previous papers focused on lower bounds for particular problems,
including sorting, the set equality problem, and several query evaluation
problems, the present paper addresses the relations between the (R,N)ST-classes
and classical complexity classes and investigates the structural complexity of
the (R,N)ST-classes. Our main results are (1) a trade-off between internal
memory space and external memory head reversals, (2) correspondences between
the (R,N)ST-classes and ``classical'' time-bounded, space-bounded,
reversal-bounded, and circuit complexity classes, and (3) hierarchies of
(R)ST-classes in terms of increasing numbers of head reversals on external
memory tapes.


title:
Cascade hash tables: a series of multilevel double hashing schemes with
  O(1) worst case lookup time

abstract:
  In this paper, the author proposes a series of multilevel double hashing
schemes called cascade hash tables. They use several levels of hash tables. In
each table, we use the common double hashing scheme. Higher level hash tables
work as fail-safes of lower level hash tables. By this strategy, it could
effectively reduce collisions in hash insertion. Thus it gains a constant worst
case lookup time with a relatively high load factor(70%-85%) in random
experiments. Different parameters of cascade hash tables are tested.


title: Morphisms of Coloured Petri Nets

abstract:
  We introduce the concept of a morphism between coloured nets. Our definition
generalizes Petris definition for ordinary nets. A morphism of coloured nets
maps the topological space of the underlying undirected net as well as the
kernel and cokernel of the incidence map. The kernel are flows along the
transition-bordered fibres of the morphism, the cokernel are classes of
markings of the place-bordered fibres. The attachment of bindings, colours,
flows and marking classes to a subnet is formalized by using concepts from
sheaf theory. A coloured net is a sheaf-cosheaf pair over a Petri space and a
morphism between coloured nets is a morphism between such pairs. Coloured nets
and their morphisms form a category. We prove the existence of a product in the
subcategory of sort-respecting morphisms. After introducing markings our
concepts generalize to coloured Petri nets.


title: The weak pigeonhole principle for function classes in S^1_2

abstract:
  It is well known that S^1_2 cannot prove the injective weak pigeonhole
principle for polynomial time functions unless RSA is insecure. In this note we
investigate the provability of the surjective (dual) weak pigeonhole principle
in S^1_2 for provably weaker function classes.


title:
An Embedding of the BSS Model of Computation in Light Affine
  Lambda-Calculus

abstract:
  This paper brings together two lines of research: implicit characterization
of complexity classes by Linear Logic (LL) on the one hand, and computation
over an arbitrary ring in the Blum-Shub-Smale (BSS) model on the other. Given a
fixed ring structure K we define an extension of Terui's light affine
lambda-calculus typed in LAL (Light Affine Logic) with a basic type for K. We
show that this calculus captures the polynomial time function class FP(K):
every typed term can be evaluated in polynomial time and conversely every
polynomial time BSS machine over K can be simulated in this calculus.


title: The Dynamics of A Self-Forming Network

abstract:
  This article describes our strategy for deploying self-forming ad hoc
networks based on the Internet Protocol version 6 and evaluates the dynamics of
this proposal. Among others, we suggest a technique called adaptive routing
that provides secure intelligent routing capabilities to computer communication
networks. This technique uses the flow label, supports hybrid metrics, network
load sharing, and is not restricted to evaluation of performance on first hop
routers when making routing decisions. Selective anycasting is an extension to
the anycast addressing model that supports exclusion of members of groups that
perform poorly or inappropriately on a per-host basis. Distributed name lookup
is suggested for integrating self-forming and global networks where they
coexist. At last, we pose an address hierarchy to support unmanaged discovery
of services in unknown networks.


title:
An Improved Sphere-Packing Bound for Finite-Length Codes on Symmetric
  Memoryless Channels

abstract:
  This paper derives an improved sphere-packing (ISP) bound for finite-length
codes whose transmission takes place over symmetric memoryless channels. We
first review classical results, i.e., the 1959 sphere-packing (SP59) bound of
Shannon for the Gaussian channel, and the 1967 sphere-packing (SP67) bound of
Shannon et al. for discrete memoryless channels. A recent improvement on the
SP67 bound, as suggested by Valembois and Fossorier, is also discussed. These
concepts are used for the derivation of a new lower bound on the decoding error
probability (referred to as the ISP bound) which is uniformly tighter than the
SP67 bound and its recent improved version. The ISP bound is applicable to
symmetric memoryless channels, and some of its applications are exemplified.
Its tightness is studied by comparing it with bounds on the ML decoding error
probability, and computer simulations of iteratively decoded turbo-like codes.
The paper also presents a technique which performs the entire calculation of
the SP59 bound in the logarithmic domain, thus facilitating the exact
calculation of this bound for moderate to large block lengths without the need
for the asymptotic approximations provided by Shannon.


title: Using Users' Expectations to Adapt Business Intelligence Systems

abstract:
  This paper takes a look at the general characteristics of business or
economic intelligence system. The role of the user within this type of system
is emphasized. We propose two models which we consider important in order to
adapt this system to the user. The first model is based on the definition of
decisional problem and the second on the four cognitive phases of human
learning. We also describe the application domain we are using to test these
models in this type of system.


title: Network Coding in a Multicast Switch

abstract:
  We consider the problem of serving multicast flows in a crossbar switch. We
show that linear network coding across packets of a flow can sustain traffic
patterns that cannot be served if network coding were not allowed. Thus,
network coding leads to a larger rate region in a multicast crossbar switch. We
demonstrate a traffic pattern which requires a switch speedup if coding is not
allowed, whereas, with coding the speedup requirement is eliminated completely.
In addition to throughput benefits, coding simplifies the characterization of
the rate region. We give a graph-theoretic characterization of the rate region
with fanout splitting and intra-flow coding, in terms of the stable set
polytope of the 'enhanced conflict graph' of the traffic pattern. Such a
formulation is not known in the case of fanout splitting without coding. We
show that computing the offline schedule (i.e. using prior knowledge of the
flow arrival rates) can be reduced to certain graph coloring problems. Finally,
we propose online algorithms (i.e. using only the current queue occupancy
information) for multicast scheduling based on our graph-theoretic formulation.
In particular, we show that a maximum weighted stable set algorithm stabilizes
the queues for all rates within the rate region.


title: LiveWN, cpu scavenging in the Grid Era

abstract:
  The goal of this research is to introduce an easy and versatile way to
provide and use Grid resources without the need of any OS installation or
middleware configuration. At the same time we provide an excellent training
tool for newer Grid users and people that want to experiment, without enforcing
any installation. We have been testing it thoroughly under different
circumstances with firm success.


title: From Grid Middleware to a Grid Operating System

abstract:
  Grid computing has made substantial advances during the last decade. Grid
middleware such as Globus has contributed greatly in making this possible.
There are, however, significant barriers to the adoption of Grid computing in
other fields, most notably day-to-day user computing environments. We will
demonstrate in this paper that this is primarily due to the limitations of the
existing Grid middleware which does not take into account the needs of everyday
scientific and business users. In this paper we will formally advocate a Grid
Operating System and propose an architecture to migrate Grid computing into a
Grid operating system which we believe would help remove most of the technical
barriers to the adoption of Grid computing and make it relevant to the
day-to-day user. We believe this proposed transition to a Grid operating system
will drive more pervasive Grid computing research and application development
and deployment in future.


title: Lessons Learned from MammoGrid for Integrated Biomedical Solutions

abstract:
  This paper presents an overview of the MammoGrid project and some of its
achievements. In terms of the global grid project, and European research in
particular, the project has successfully demonstrated the capacity of a
grid-based system to support effective collaboration between physicians,
including handling and querying image databases, as well as using grid
services, such as image standardization and Computer-Aided Detection (CADe) of
suspect or indicative features. In terms of scientific results, in radiology,
there have been significant epidemiological findings in the assessment of
breast density as a risk factor, but the results for CADe are less clear-cut.
Finally, the foundations of a technology transfer process to establish a
working MammoGrid plus system in Spain through the company Maat GKnowledge and
the collaboration of CIEMAT and hospitals in Extremadura.


title: Bulk Scheduling with the DIANA Scheduler

abstract:
  Results from the research and development of a Data Intensive and Network
Aware (DIANA) scheduling engine, to be used primarily for data intensive
sciences such as physics analysis, are described. In Grid analyses, tasks can
involve thousands of computing, data handling, and network resources. The
central problem in the scheduling of these resources is the coordinated
management of computation and data at multiple locations and not just data
replication or movement. However, this can prove to be a rather costly
operation and efficient sing can be a challenge if compute and data resources
are mapped without considering network costs. We have implemented an adaptive
algorithm within the so-called DIANA Scheduler which takes into account data
location and size, network performance and computation capability in order to
enable efficient global scheduling. DIANA is a performance-aware and
economy-guided Meta Scheduler. It iteratively allocates each job to the site
that is most likely to produce the best performance as well as optimizing the
global queue for any remaining jobs. Therefore it is equally suitable whether a
single job is being submitted or bulk scheduling is being performed. Results
indicate that considerable performance improvements can be gained by adopting
the DIANA scheduling approach.


title:
Solving non-uniqueness in agglomerative hierarchical clustering using
  multidendrograms

abstract:
  In agglomerative hierarchical clustering, pair-group methods suffer from a
problem of non-uniqueness when two or more distances between different clusters
coincide during the amalgamation process. The traditional approach for solving
this drawback has been to take any arbitrary criterion in order to break ties
between distances, which results in different hierarchical classifications
depending on the criterion followed. In this article we propose a
variable-group algorithm that consists in grouping more than two clusters at
the same time when ties occur. We give a tree representation for the results of
the algorithm, which we call a multidendrogram, as well as a generalization of
the Lance and Williams' formula which enables the implementation of the
algorithm in a recursive way.


title:
Post-Processing Hierarchical Community Structures: Quality Improvements
  and Multi-scale View

abstract:
  Dense sub-graphs of sparse graphs (communities), which appear in most
real-world complex networks, play an important role in many contexts. Most
existing community detection algorithms produce a hierarchical structure of
community and seek a partition into communities that optimizes a given quality
function. We propose new methods to improve the results of any of these
algorithms. First we show how to optimize a general class of additive quality
functions (containing the modularity, the performance, and a new similarity
based quality function we propose) over a larger set of partitions than the
classical methods. Moreover, we define new multi-scale quality functions which
make it possible to detect the different scales at which meaningful community
structures appear, while classical approaches find only one partition.


title: Modules over Monads and Linearity

abstract:
  Inspired by the classical theory of modules over a monoid, we give a first
account of the natural notion of module over a monad. The associated notion of
morphism of left modules ("Linear" natural transformations) captures an
important property of compatibility with substitution, in the heterogeneous
case where "terms" and variables therein could be of different types as well as
in the homogeneous case. In this paper, we present basic constructions of
modules and we show examples concerning in particular abstract syntax and
lambda-calculus.


title: GDF - A general dataformat for biosignals

abstract:
  Biomedical signals are stored in many different data formats. Most formats
have been developed for a specific purpose of a specialized community for ECG
research, EEG analysis, sleep research, etc. So far none of the existing
formats can be considered a general purpose data format for biomedical signals.
In order to solve this problem and to unify the various needs of the various
biomedical signal processing fields, the so-called "General Data Format for
biomedical signals" (GDF) is developed. This GDF format is fully described and
specified. Software for reading and writing GDF data is implemented in
Octave/Matlab and C/C++ and provided through BioSig - an free and open source
software library for biomedical signal processing. BioSig privides also
converters from various data formats to GDF, and a viewing and scoring
software.


title: Renormalization group approach to the P versus NP question

abstract:
  This paper argues that the ideas underlying the renormalization group
technique used to characterize phase transitions in condensed matter systems
could be useful for distinguishing computational complexity classes. The paper
presents a renormalization group transformation that maps an arbitrary Boolean
function of $N$ Boolean variables to one of $N-1$ variables. When this
transformation is applied repeatedly, the behavior of the resulting sequence of
functions is different for a generic Boolean function than for Boolean
functions that can be written as a polynomial of degree $\xi$ with $\xi \ll N$
as well as for functions that depend on composite variables such as the
arithmetic sum of the inputs. Being able to demonstrate that functions are
non-generic is of interest because it suggests an avenue for constructing an
algorithm capable of demonstrating that a given Boolean function cannot be
computed using resources that are bounded by a polynomial of $N$.


title: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

abstract:
  How much can randomness help computation? Motivated by this general question
and by volume computation, one of the few instances where randomness provably
helps, we analyze a notion of dispersion and connect it to asymptotic convex
geometry. We obtain a nearly quadratic lower bound on the complexity of
randomized volume algorithms for convex bodies in R^n (the current best
algorithm has complexity roughly n^4, conjectured to be n^3). Our main tools,
dispersion of random determinants and dispersion of the length of a random
point from a convex body, are of independent interest and applicable more
generally; in particular, the latter is closely related to the variance
hypothesis from convex geometry. This geometric dispersion also leads to lower
bounds for matrix problems and property testing.


title: MDS Ideal Secret Sharing Scheme from AG-codes on Elliptic Curves

abstract:
  For a secret sharing scheme, two parameters $d_{min}$ and $d_{cheat}$ are
defined in [12] and [13]. These two parameters measure the error-correcting
capability and the secret-recovering capability of the secret sharing scheme
against cheaters. Some general properties of the parameters have been studied
in [12,[9] and [13]. The MDS secret-sharing scheme was defined in [12] and it
is proved that MDS perfect secret sharing scheme can be constructed for any
monotone access structure. The famous Shamir $(k,n)$ threshold secret sharing
scheme is the MDS with $d_{min}=d_{cheat}=n-k+1$. In [3] we proposed the linear
secret sharing scheme from algebraic-geometric codes. In this paper the linear
secret sharing scheme from AG-codes on elliptic curves is studied and it is
shown that many of them are MDS linear secret sharing scheme.


title: Wiretap Channel With Side Information

abstract: This submission has been withdrawn by the author.


title: Hybrid Elections Broaden Complexity-Theoretic Resistance to Control

abstract:
  Electoral control refers to attempts by an election's organizer ("the chair")
to influence the outcome by adding/deleting/partitioning voters or candidates.
The groundbreaking work of Bartholdi, Tovey, and Trick [BTT92] on
(constructive) control proposes computational complexity as a means of
resisting control attempts: Look for election systems where the chair's task in
seeking control is itself computationally infeasible.
  We introduce and study a method of combining two or more candidate-anonymous
election schemes in such a way that the combined scheme possesses all the
resistances to control (i.e., all the NP-hardnesses of control) possessed by
any of its constituents: It combines their strengths. From this and new
resistance constructions, we prove for the first time that there exists an
election scheme that is resistant to all twenty standard types of electoral
control.


title: Evolution of the Internet AS-Level Ecosystem

abstract:
  We present an analytically tractable model of Internet evolution at the level
of Autonomous Systems (ASs). We call our model the multiclass preferential
attachment (MPA) model. As its name suggests, it is based on preferential
attachment. All of its parameters are measurable from available Internet
topology data. Given the estimated values of these parameters, our analytic
results predict a definitive set of statistics characterizing the AS topology
structure. These statistics are not part of the model formulation. The MPA
model thus closes the "measure-model-validate-predict" loop, and provides
further evidence that preferential attachment is a driving force behind
Internet evolution.


title:
A Distribution Law for CCS and a New Congruence Result for the
  pi-calculus

abstract:
  We give an axiomatisation of strong bisimilarity on a small fragment of CCS
that does not feature the sum operator. This axiomatisation is then used to
derive congruence of strong bisimilarity in the finite pi-calculus in absence
of sum. To our knowledge, this is the only nontrivial subcalculus of the
pi-calculus that includes the full output prefix and for which strong
bisimilarity is a congruence.


title: Duality and Capacity Region of AF Relay MAC and BC

abstract:
  We consider multi-hop multiple access (MAC) and broadcast channels (BC) where
communication takes place with the assistance of relays that amplify and
forward (AF) their received signals. For a two hop parallel AF relay MAC,
assuming a sum power constraint across all relays we characterize optimal relay
amplification factors and the resulting capacity regions. We find that the
parallel AF relay MAC with total transmit power of the two users $P_1+P_2=P$
and total relay power $P_R$ is the dual of the parallel AF relay BC where the
MAC source nodes become the BC destination nodes, the MAC destination node
becomes the BC source node, the dual BC source transmit power is $P_R$ and the
total transmit power of the AF relays is $P$. The duality means that the
capacity region of the AF relay MAC with a sum power constraint $P$ on the
transmitters is the same as that of the dual BC. The duality relationship is
found to be useful in characterizing the capacity region of the AF relay BC as
the union of MAC capacity regions. The duality extends to distributed relays
with multiple antennas and more than 2 hops as well.


title: Concurrent Processing Memory

abstract:
  A theoretical memory with limited processing power and internal connectivity
at each element is proposed. This memory carries out parallel processing within
itself to solve generic array problems. The applicability of this in-memory
finest-grain massive SIMD approach is studied in some details. For an array of
N items, it reduces the total instruction cycle count of universal operations
such as insertion/deletion and match finding to ~ 1, local operations such as
filtering and template matching to ~ local operation size, and global
operations such as sum, finding global limit and sorting to ~\sqroot{N}
instruction cycles. It eliminates most streaming activities for data processing
purpose on the system bus. Yet it remains general-purposed, easy to use, pin
compatible with conventional memory, and practical for implementation.


title: Tarski's influence on computer science

abstract:
  The influence of Alfred Tarski on computer science was indirect but
significant in a number of directions and was in certain respects fundamental.
Here surveyed is the work of Tarski on the decision procedure for algebra and
geometry, the method of elimination of quantifiers, the semantics of formal
languages, modeltheoretic preservation theorems, and algebraic logic; various
connections of each with computer science are taken up.


title: A Generic Lazy Evaluation Scheme for Exact Geometric Computations

abstract:
  We present a generic C++ design to perform efficient and exact geometric
computations using lazy evaluations. Exact geometric computations are critical
for the robustness of geometric algorithms. Their efficiency is also critical
for most applications, hence the need for delaying the exact computations at
run time until they are actually needed. Our approach is generic and extensible
in the sense that it is possible to make it a library which users can extend to
their own geometric objects or primitives. It involves techniques such as
generic functor adaptors, dynamic polymorphism, reference counting for the
management of directed acyclic graphs and exception handling for detecting
cases where exact computations are needed. It also relies on multiple precision
arithmetic as well as interval arithmetic. We apply our approach to the whole
geometric kernel of CGAL.


title:
A linear algebra approach to the differentiation index of generic DAE
  systems

abstract:
  The notion of differentiation index for DAE systems of arbitrary order with
generic second members is discussed by means of the study of the behavior of
the ranks of certain Jacobian associated sub-matrices. As a by-product, we
obtain upper bounds for the regularity of the Hilbert-Kolchin function and the
order of the ideal associated to the DAE systems under consideration, not
depending on characteristic sets. Some quantitative and algorithmic results
concerning differential transcendence bases and induced equivalent explicit ODE
systems are also established.


title:
Combinatorial and Arithmetical Properties of Infinite Words Associated
  with Non-simple Quadratic Parry Numbers

abstract:
  We study arithmetical and combinatorial properties of $\beta$-integers for
$\beta$ being the root of the equation $x^2=mx-n, m,n \in \mathbb N, m \geq
n+2\geq 3$. We determine with the accuracy of $\pm 1$ the maximal number of
$\beta$-fractional positions, which may arise as a result of addition of two
$\beta$-integers. For the infinite word $u_\beta$ coding distances between
consecutive $\beta$-integers, we determine precisely also the balance. The word
$u_\beta$ is the fixed point of the morphism $A \to A^{m-1}B$ and $B\to
A^{m-n-1}B$. In the case $n=1$ the corresponding infinite word $u_\beta$ is
sturmian and therefore 1-balanced. On the simplest non-sturmian example with
$n\geq 2$, we illustrate how closely the balance and arithmetical properties of
$\beta$-integers are related.


title: k-Connectivity in the Semi-Streaming Model

abstract:
  We present the first semi-streaming algorithms to determine k-connectivity of
an undirected graph with k being any constant. The semi-streaming model for
graph algorithms was introduced by Muthukrishnan in 2003 and turns out to be
useful when dealing with massive graphs streamed in from an external storage
device.
  Our two semi-streaming algorithms each compute a sparse subgraph of an input
graph G and can use this subgraph in a postprocessing step to decide
k-connectivity of G. To this end the first algorithm reads the input stream
only once and uses time O(k^2*n) to process each input edge. The second
algorithm reads the input k+1 times and needs time O(k+alpha(n)) per input
edge. Using its constructed subgraph the second algorithm can also generate all
l-separators of the input graph for all l<k.


title: On Polynomial Time Computable Numbers

abstract:
  It will be shown that the polynomial time computable numbers form a field,
and especially an algebraically closed field.


title:
The Aligned-Coordinated Geographical Routing for Multihop Wireless
  Networks

abstract:
  The stateless, low overhead and distributed nature of the Geographic routing
protocols attract a lot of research attentions recently. Since the geographic
routing would face void problems, leading to complementary routing such as
perimeter routing which degrades the performance of geographic routing, most
research works are focus on optimizing this complementary part of geographic
routing to improve it. The greedy forwarding part of geographic routing
provides an optimal routing performance in terms of path stretch. If the
geographic routing could adapt the greedy forwarding more, its performance
would be enhanced much more than to optimize the complementary routing such as
perimeter routings. Our work is the first time to do so. The aligned physical
coordinate is used to do the greedy forwarding routing decision which would
lead more greedy forwarding. We evaluate our design to most geographic routing
protocols, showing it helps much and maintain the stateless nature of
geographic routing.


title: JiTS: Just-in-Time Scheduling for Real-Time Sensor Data Dissemination

abstract:
  We consider the problem of real-time data dissemination in wireless sensor
networks, in which data are associated with deadlines and it is desired for
data to reach the sink(s) by their deadlines. To this end, existing real-time
data dissemination work have developed packet scheduling schemes that
prioritize packets according to their deadlines. In this paper, we first
demonstrate that not only the scheduling discipline but also the routing
protocol has a significant impact on the success of real-time sensor data
dissemination. We show that the shortest path routing using the minimum number
of hops leads to considerably better performance than Geographical Forwarding,
which has often been used in existing real-time data dissemination work. We
also observe that packet prioritization by itself is not enough for real-time
data dissemination, since many high priority packets may simultaneously contend
for network resources, deteriorating the network performance. Instead,
real-time packets could be judiciously delayed to avoid severe contention as
long as their deadlines can be met. Based on this observation, we propose a
Just-in-Time Scheduling (JiTS) algorithm for scheduling data transmissions to
alleviate the shortcomings of the existing solutions. We explore several
policies for non-uniformly delaying data at different intermediate nodes to
account for the higher expected contention as the packet gets closer to the
sink(s). By an extensive simulation study, we demonstrate that JiTS can
significantly improve the deadline miss ratio and packet drop ratio compared to
existing approaches in various situations. Notably, JiTS improves the
performance requiring neither lower layer support nor synchronization among the
sensor nodes.


title: Finite State Channels with Time-Invariant Deterministic Feedback

abstract:
  We consider capacity of discrete-time channels with feedback for the general
case where the feedback is a time-invariant deterministic function of the
output samples. Under the assumption that the channel states take values in a
finite alphabet, we find an achievable rate and an upper bound on the capacity.
We further show that when the channel is indecomposable, and has no intersymbol
interference (ISI), its capacity is given by the limit of the maximum of the
(normalized) directed information between the input $X^N$ and the output $Y^N$,
i.e. $C = \lim_{N \to \infty} \frac{1}{N} \max I(X^N \to Y^N)$, where the
maximization is taken over the causal conditioning probability
$Q(x^N||z^{N-1})$ defined in this paper. The capacity result is used to show
that the source-channel separation theorem holds for time-invariant determinist
feedback. We also show that if the state of the channel is known both at the
encoder and the decoder then feedback does not increase capacity.


title: Broadcast Cooperation Strategies for Two Colocated Users

abstract:
  This work considers the problem of communication from a single transmitter,
over a network with colocated users, through an independent block Rayleigh
fading channel. The colocation nature of the users allows cooperation, which
increases the overall achievable rate, from the transmitter to the destined
user. The transmitter is ignorant of the fading coefficients, while receivers
have access to perfect channel state information (CSI). This gives rise to the
multi-layer broadcast approach used by the transmitter. The broadcast approach
allows, in our network setting, to improve the cooperation between the
colocated users. That is due to the nature of broadcasting, where the better
the channel quality, the more layers that can be decoded. The cooperation
between the users is performed over an additive white Gaussian channels (AWGN),
with a relaying power constraint, and unlimited bandwidth. Three commonly used
cooperation techniques are studied: amplify-forward (AF), compress-forward
(CF), and decode-forward (DF). These methods are extended using the broadcast
approach, for the case of relaxed decoding delay constraint. For this case a
separated processing of the layers, which includes multi-session cooperation is
shown to be beneficial. Further, closed form expressions for infinitely many AF
sessions and recursive expressions for the more complex CF are given. Numerical
results for the various cooperation strategies demonstrate the efficiency of
multi-session cooperation.


title:
Applications of Random Parameter Matrices Kalman Filtering in Uncertain
  Observation and Multi-Model Systems

abstract:
  This paper considers the Linear Minimum Variance recursive state estimation
for the linear discrete time dynamic system with random state transition and
measurement matrices, i.e., random parameter matrices Kalman filtering. It is
shown that such system can be converted to a linear dynamic system with
deterministic parameter matrices but state-dependent process and measurement
noises. It is proved that under mild conditions, the recursive state estimation
of this system is still of the form of a modified Kalman filtering. More
importantly, this result can be applied to Kalman filtering with intermittent
and partial observations as well as randomly variant dynamic systems.


title: Parametrical Neural Networks and Some Other Similar Architectures

abstract:
  A review of works on associative neural networks accomplished during last
four years in the Institute of Optical Neural Technologies RAS is given. The
presentation is based on description of parametrical neural networks (PNN). For
today PNN have record recognizing characteristics (storage capacity, noise
immunity and speed of operation). Presentation of basic ideas and principles is
accentuated.


title: From Invariants to Canonization in Parallel

abstract:
  A function $f$ of a graph is called a complete graph invariant if the
isomorphism of graphs $G$ and $H$ is equivalent to the equality $f(G)=f(H)$.
If, in addition, $f(G)$ is a graph isomorphic to $G$, then $f$ is called a
canonical form for graphs. Gurevich proves that graphs have a polynomial-time
computable canonical form exactly when they have a polynomial-time computable
complete invariant. We extend this equivalence to the polylogarithmic-time
model of parallel computation for classes of graphs with bounded rigidity index
and for classes of graphs with small separators. In particular, our results
apply to three representative classes of graphs embeddable into a fixed
surface, namely, to 5-connected graphs, to 3-connected graphs admitting a
polyhedral embedding, and 3-connected graphs admitting a large-edge-width
embedding. Another application covers graphs with bounded treewidth. Since in
the latter case an NC complete-invariant algorithm is known, we conclude that
graphs of bounded treewidth have a canonical form (and even a canonical
labeling) computable in NC.


title: Design of multimedia processor based on metric computation

abstract:
  Media-processing applications, such as signal processing, 2D and 3D graphics
rendering, and image compression, are the dominant workloads in many embedded
systems today. The real-time constraints of those media applications have
taxing demands on today's processor performances with low cost, low power and
reduced design delay. To satisfy those challenges, a fast and efficient
strategy consists in upgrading a low cost general purpose processor core. This
approach is based on the personalization of a general RISC processor core
according the target multimedia application requirements. Thus, if the extra
cost is justified, the general purpose processor GPP core can be enforced with
instruction level coprocessors, coarse grain dedicated hardware, ad hoc
memories or new GPP cores. In this way the final design solution is tailored to
the application requirements. The proposed approach is based on three main
steps: the first one is the analysis of the targeted application using
efficient metrics. The second step is the selection of the appropriate
architecture template according to the first step results and recommendations.
The third step is the architecture generation. This approach is experimented
using various image and video algorithms showing its feasibility.


title: Oblivious-Transfer Amplification

abstract:
  Oblivious transfer is a primitive of paramount importance in cryptography or,
more precisely, two- and multi-party computation due to its universality.
Unfortunately, oblivious transfer cannot be achieved in an unconditionally
secure way for both parties from scratch. Therefore, it is a natural question
what information-theoretic primitives or computational assumptions oblivious
transfer can be based on.
  The results in our thesis are threefold. First, we present a protocol that
implements oblivious transfer from a weakened oblivious transfer called
universal oblivious transfer, where one of the two players may get additional
information. Our reduction is about twice as efficient as previous results.
  Weak oblivious transfer is an even weaker form of oblivious transfer, where
both players may obtain additional information about the other player's input,
and where the output can contain errors. We give a new, weaker definition of
weak oblivious transfer, as well as new reductions with a more detailed
analysis.
  Finally, we carry over our results to the computational setting and show how
a weak oblivious transfer that is sometimes incorrect and only mildly secure
against computationally bounded adversaries can be strengthened.


title: The Effect of Scheduling on Link Capacity in Multi-hopWireless Networks

abstract:
  Existing models of Multi-Hop Wireless Networks (MHWNs) assume that
interference estimators of link quality such as observed busy time predict the
capacity of the links. We show that these estimators do not capture the
intricate interactions that occur at the scheduling level, which have a large
impact on effective link capacity under contention based MAC protocols. We
observe that scheduling problems arise only among those interfering sources
whose concurrent transmissions cannot be prevented by the MAC protocol's
collision management mechanisms; other interfering sources can arbitrate the
medium and coexist successfully. Based on this observation, we propose a
methodology for rating links and show that it achieves high correlation with
observed behavior in simulation. We then use this rating as part of a
branch-and-bound framework based on a linear programming formulation for
traffic engineering in static MHWNs and show that it achieves considerable
improvement in performance relative to interference based models.


title:
Searching for Globally Optimal Functional Forms for Inter-Atomic
  Potentials Using Parallel Tempering and Genetic Programming

abstract:
  We develop a Genetic Programming-based methodology that enables discovery of
novel functional forms for classical inter-atomic force-fields, used in
molecular dynamics simulations. Unlike previous efforts in the field, that fit
only the parameters to the fixed functional forms, we instead use a novel
algorithm to search the space of many possible functional forms. While a
follow-on practical procedure will use experimental and {\it ab inito} data to
find an optimal functional form for a forcefield, we first validate the
approach using a manufactured solution. This validation has the advantage of a
well-defined metric of success. We manufactured a training set of atomic
coordinate data with an associated set of global energies using the well-known
Lennard-Jones inter-atomic potential. We performed an automatic functional form
fitting procedure starting with a population of random functions, using a
genetic programming functional formulation, and a parallel tempering
Metropolis-based optimization algorithm. Our massively-parallel method
independently discovered the Lennard-Jones function after searching for several
hours on 100 processors and covering a miniscule portion of the configuration
space. We find that the method is suitable for unsupervised discovery of
functional forms for inter-atomic potentials/force-fields. We also find that
our parallel tempering Metropolis-based approach significantly improves the
optimization convergence time, and takes good advantage of the parallel cluster
architecture.


title:
Algorithmic linear dimension reduction in the l_1 norm for sparse
  vectors

abstract:
  This paper develops a new method for recovering m-sparse signals that is
simultaneously uniform and quick. We present a reconstruction algorithm whose
run time, O(m log^2(m) log^2(d)), is sublinear in the length d of the signal.
The reconstruction error is within a logarithmic factor (in m) of the optimal
m-term approximation error in l_1. In particular, the algorithm recovers
m-sparse signals perfectly and noisy signals are recovered with polylogarithmic
distortion. Our algorithm makes O(m log^2 (d)) measurements, which is within a
logarithmic factor of optimal. We also present a small-space implementation of
the algorithm. These sketching techniques and the corresponding reconstruction
algorithms provide an algorithmic dimension reduction in the l_1 norm. In
particular, vectors of support m in dimension d can be linearly embedded into
O(m log^2 d) dimensions with polylogarithmic distortion. We can reconstruct a
vector from its low-dimensional sketch in time O(m log^2(m) log^2(d)).
Furthermore, this reconstruction is stable and robust under small
perturbations.


title: Lower Bounds on the Algebraic Immunity of Boolean Functions

abstract:
  From the motivation of algebraic attacks to stream and block
ciphers([1,2,7,13,14,15]), the concept of {\em algebraic immunity} (AI) was
introduced in [21] and studied in [3,5,10,11,17,18,19,20,21]. High algebraic
immunity is a necessary condition for resisting algebraic attacks. In this
paper, we give some lower bounds on algebraic immunity of Boolean functions.
The results are applied to give lower bounds on AI of symmetric Boolean
functions and rotation symmetric Boolean functions. Some balanced rotation
symmetric Boolean functions with their AI near the maximum possible value
$\lceil \frac{n}{2}\rceil$ are constructed.


title: How Hard Is Bribery in Elections?

abstract:
  We study the complexity of influencing elections through bribery: How
computationally complex is it for an external actor to determine whether by a
certain amount of bribing voters a specified candidate can be made the
election's winner? We study this problem for election systems as varied as
scoring protocols and Dodgson voting, and in a variety of settings regarding
homogeneous-vs.-nonhomogeneous electorate bribability,
bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted
voters, and succinct-vs.-nonsuccinct input specification. We obtain both
polynomial-time bribery algorithms and proofs of the intractability of bribery,
and indeed our results show that the complexity of bribery is extremely
sensitive to the setting. For example, we find settings in which bribery is
NP-complete but manipulation (by voters) is in P, and we find settings in which
bribing weighted voters is NP-complete but bribing voters with individual bribe
thresholds is in P. For the broad class of elections (including plurality,
Borda, k-approval, and veto) known as scoring protocols, we prove a dichotomy
result for bribery of weighted voters: We find a simple-to-evaluate condition
that classifies every case as either NP-complete or in P.


title: Competition and Request Routing Policies in Content Delivery Networks

abstract:
  The role of competition and monetary benefits in the design of Content
Delivery Networks (CDNs) is largely an unexplored area. In this paper, we
investigate the effect of competition among the competitive web based CDNs and
show that little difference in their performance may cause significant
financial gain/loss. It turns out that the economy of scale effect is very
significant for the success of a CDN in a competitive market. So CDN peering
might be a good idea. Since performance and conforming to the service level
agreement (SLA) with content providers is very important, we then focus on
designing CDN from this perspective. We provide an asymptotically optimal
static request routing policy for a CDN under a model where a CDN company
guarantees a certain level of user latency to the content providers in the SLA.