OpenRaiser/Intern-Atlas huggingface dataset:
Artificial Immune Systems (AIS) - A New Paradigm for Heuristic Decision Making
Venue: arXiv cs.NE 2008
Year: 2008

Over the last few years, more and more heuristic decision making techniques have been inspired by nature, e.g. evolutionary algorithms, ant colony optimisation and simulated annealing. More recently, a novel computational intelligence technique inspired by immunology has emerged, called Artificial Immune Systems (AIS). This immune system inspired technique has already been useful in solving some computational problems. In this keynote, we will very briefly describe the immune system metaphors that are relevant to AIS. We will then give some illustrative real-world problems suitable for AIS use and show a step-by-step algorithm walkthrough. A comparison of AIS to other well-known algorithms and areas for future work will round this keynote off. It should be noted that as AIS is still a young and evolving field, there is not yet a fixed algorithm template and hence actual implementations might differ somewhat from the examples given here.
A Neyman-Pearson Approach to Universal Erasure and List Decoding
Venue: arXiv cs.IT 2008
Year: 2008

When information is to be transmitted over an unknown, possibly unreliable channel, an erasure option at the decoder is desirable. Using constant-composition random codes, we propose a generalization of Csiszar and Korner's Maximum Mutual Information decoder with erasure option for discrete memoryless channels. The new decoder is parameterized by a weighting function that is designed to optimize the fundamental tradeoff between undetected-error and erasure exponents for a compound class of channels. The class of weighting functions may be further enlarged to optimize a similar tradeoff for list decoders -- in that case, undetected-error probability is replaced with average number of incorrect messages in the list. Explicit solutions are identified. The optimal exponents admit simple expressions in terms of the sphere-packing exponent, at all rates below capacity. For small erasure exponents, these expressions coincide with those derived by Forney (1968) for symmetric channels, using Maximum a Posteriori decoding. Thus for those channels at least, ignorance of the channel law is inconsequential. Conditions for optimality of the Csiszar-Korner rule and of the simpler empirical-mutual-information thresholding rule are identified. The error exponents are evaluated numerically for the binary symmetric channel.
Concerning Olga, the Beautiful Little Street Dancer (Adjectives as Higher-Order Polymorphic Functions)
Venue: arXiv cs.CL 2008
Year: 2008

In this paper we suggest a typed compositional seman-tics for nominal compounds of the form [Adj Noun] that models adjectives as higher-order polymorphic functions, and where types are assumed to represent concepts in an ontology that reflects our commonsense view of the world and the way we talk about it in or-dinary language. In addition to [Adj Noun] compounds our proposal seems also to suggest a plausible explana-tion for well known adjective ordering restrictions.
Non-Deterministic Communication Complexity of Regular Languages
Venue: arXiv cs.CC 2008
Year: 2008

In this thesis, we study the place of regular languages within the communication complexity setting. In particular, we are interested in the non-deterministic communication complexity of regular languages. We show that a regular language has either O(1) or Omega(log n) non-deterministic complexity. We obtain several linear lower bound results which cover a wide range of regular languages having linear non-deterministic complexity. These lower bound results also imply a result in semigroup theory: we obtain sufficient conditions for not being in the positive variety Pol(Com). To obtain our results, we use algebraic techniques. In the study of regular languages, the algebraic point of view pioneered by Eilenberg (\cite{Eil74}) has led to many interesting results. Viewing a semigroup as a computational device that recognizes languages has proven to be prolific from both semigroup theory and formal languages perspectives. In this thesis, we provide further instances of such mutualism.
Information Width
Venue: arXiv cs.DM 2008
Year: 2008

Kolmogorov argued that the concept of information exists also in problems with no underlying stochastic model (as Shannon's information representation) for instance, the information contained in an algorithm or in the genome. He introduced a combinatorial notion of entropy and information $I(x:\sy)$ conveyed by a binary string $x$ about the unknown value of a variable $\sy$. The current paper poses the following questions: what is the relationship between the information conveyed by $x$ about $\sy$ to the description complexity of $x$ ? is there a notion of cost of information ? are there limits on how efficient $x$ conveys information ? To answer these questions Kolmogorov's definition is extended and a new concept termed {\em information width} which is similar to $n$-widths in approximation theory is introduced. Information of any input source, e.g., sample-based, general side-information or a hybrid of both can be evaluated by a single common formula. An application to the space of binary functions is considered.
Bicretieria Optimization in Routing Games
Venue: arXiv cs.GT 2008
Year: 2008

Two important metrics for measuring the quality of routing paths are the maximum edge congestion $C$ and maximum path length $D$. Here, we study bicriteria in routing games where each player $i$ selfishly selects a path that simultaneously minimizes its maximum edge congestion $C_i$ and path length $D_i$. We study the stability and price of anarchy of two bicriteria games: - {\em Max games}, where the social cost is $\max(C,D)$ and the player cost is $\max(C_i, D_i)$. We prove that max games are stable and convergent under best-response dynamics, and that the price of anarchy is bounded above by the maximum path length in the players' strategy sets. We also show that this bound is tight in worst-case scenarios. - {\em Sum games}, where the social cost is $C+D$ and the player cost is $C_i+D_i$. For sum games, we first show the negative result that there are game instances that have no Nash-equilibria. Therefore, we examine an approximate game called the {\em sum-bucket game} that is always convergent (and therefore stable). We show that the price of anarchy in sum-bucket games is bounded above by $C^* \cdot D^* / (C^* + D^*)$ (with a poly-log factor), where $C^*$ and $D^*$ are the optimal coordinated congestion and path length. Thus, the sum-bucket game has typically superior price of anarchy bounds than the max game. In fact, when either $C^*$ or $D^*$ is small (e.g. constant) the social cost of the Nash-equilibria is very close to the coordinated optimal $C^* + D^*$ (within a poly-log factor). We also show that the price of anarchy bound is tight for cases where both $C^*$ and $D^*$ are large.
Solving the Maximum Agreement SubTree and the Maximum Compatible Tree problems on many bounded degree trees
Venue: arXiv cs.CC 2008
Year: 2008

Given a set of leaf-labeled trees with identical leaf sets, the well-known "Maximum Agreement SubTree" problem (MAST) consists of finding a subtree homeomorphically included in all input trees and with the largest number of leaves. Its variant called "Maximum Compatible Tree" (MCT) is less stringent, as it allows the input trees to be refined. Both problems are of particular interest in computational biology, where trees encountered have often small degrees. In this paper, we study the parameterized complexity of MAST and MCT with respect to the maximum degree, denoted by D, of the input trees. It is known that MAST is polynomial for bounded D. As a counterpart, we show that the problem is W[1]-hard with respect to parameter D. Moreover, relying on recent advances in parameterized complexity we obtain a tight lower bound: while MAST can be solved in O(N^{O(D)}) time where N denotes the input length, we show that an O(N^{o(D)}) bound is not achievable, unless SNP is contained in SE. We also show that MCT is W[1]-hard with respect to D, and that MCT cannot be solved in O(N^{o(2^{D/2})}) time, SNP is contained in SE.
A topological formal treatment for scenario-based software specification of concurrent real-time systems
Venue: arXiv cs.SE 2008
Year: 2008

Real-time systems are computing systems in which the meeting of their requirements is vital for their correctness. Consequently, if the real-time requirements of these systems are poorly understood and verified, the results can be disastrous and lead to irremediable project failures at the early phases of development. The present work addresses the problem of detecting deadlock situations early in the requirements specification phase of a concurrent real time system, proposing a simple proof-of-concepts prototype that joins scenario-based requirements specifications and techniques based on topology. The efforts are concentrated in the integration of the formal representation of Message Sequence Chart scenarios into the deadlock detection algorithm of Fajstrup et al., based on geometric and algebraic topology.
Energy Aware Self-Organizing Density Management in Wireless Sensor Networks
Venue: arXiv cs.DC 2008
Year: 2008

Energy consumption is the most important factor that determines sensor node lifetime. The optimization of wireless sensor network lifetime targets not only the reduction of energy consumption of a single sensor node but also the extension of the entire network lifetime. We propose a simple and adaptive energy-conserving topology management scheme, called SAND (Self-Organizing Active Node Density). SAND is fully decentralized and relies on a distributed probing approach and on the redundancy resolution of sensors for energy optimizations, while preserving the data forwarding and sensing capabilities of the network. We present the SAND's algorithm, its analysis of convergence, and simulation results. Simulation results show that, though slightly increasing path lengths from sensor to sink nodes, the proposed scheme improves significantly the network lifetime for different neighborhood densities degrees, while preserving both sensing and routing fidelity.
Timed Quorum System for Large-Scale and Dynamic Environments
Venue: arXiv cs.DC 2008
Year: 2008

This paper presents Timed Quorum System (TQS), a new quorum system especially suited for large-scale and dynamic systems. TQS requires that two quorums intersect with high probability if they are used in the same small period of time. It proposed an algorithm that implements TQS and that verifies probabilistic atomicity: a consistency criterion that requires each operation to respect atomicity with high probability. This TQS implementation has quorum of size O(\sqrt{nD}) and expected access time of O(log \sqrt{nD}) message delays, where n measures the size of the system and D is a required parameter to handle dynamism.
(Generalized) Post Correspondence Problem and semi-Thue systems
Venue: arXiv cs.DM 2008
Year: 2008

Let PCP(k) denote the Post Correspondence Problem for k input pairs of strings. Let ACCESSIBILITY(k) denote the the word problem for k-rule semi-Thue systems. In 1980, Claus showed that if ACCESSIBILITY(k) is undecidable then PCP(k + 4) is also undecidable. The aim of the paper is to present a clean, detailed proof of the statement. We proceed in two steps, using the Generalized Post Correspondence Problem as an auxiliary. First, we prove that if ACCESSIBILITY(k) is undecidable then GPCP(k + 2) is also undecidable. Then, we prove that if GPCP(k) is undecidable then PCP(k + 2) is also undecidable. (The latter result has also been shown by Harju and Karhumaki.) To date, the sharpest undecidability bounds for both PCP and GPCP have been deduced from Claus's result: since Matiyasevich and Senizergues showed that ACCESSIBILITY(3) is undecidable, GPCP(5) and PCP(7) are undecidable.
Average-Case Analysis of Online Topological Ordering
Venue: arXiv cs.DS 2008
Year: 2008

Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of online topological ordering algorithms. We prove an expected runtime of O(n^2 polylog(n)) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). This is much less than the best known worst-case bound O(n^{2.75}) for this problem.
Multi-Use Unidirectional Proxy Re-Signatures
Venue: arXiv cs.CR 2008
Year: 2008

In 1998, Blaze, Bleumer, and Strauss suggested a cryptographic primitive named proxy re-signatures where a proxy turns a signature computed under Alice's secret key into one from Bob on the same message. The semi-trusted proxy does not learn either party's signing key and cannot sign arbitrary messages on behalf of Alice or Bob. At CCS 2005, Ateniese and Hohenberger revisited the primitive by providing appropriate security definitions and efficient constructions in the random oracle model. Nonetheless, they left open the problem of designing a multi-use unidirectional scheme where the proxy is able to translate in only one direction and signatures can be re-translated several times. This paper solves this problem, suggested for the first time 10 years ago, and shows the first multi-hop unidirectional proxy re-signature schemes. We describe a random-oracle-using system that is secure in the Ateniese-Hohenberger model. The same technique also yields a similar construction in the standard model (i.e. without relying on random oracles). Both schemes are efficient and require newly defined -- but falsifiable -- Diffie-Hellman-like assumptions in bilinear groups.
Exchange of Limits: Why Iterative Decoding Works
Venue: arXiv cs.IT 2008
Year: 2008

We consider communication over binary-input memoryless output-symmetric channels using low-density parity-check codes and message-passing decoding. The asymptotic (in the length) performance of such a combination for a fixed number of iterations is given by density evolution. Letting the number of iterations tend to infinity we get the density evolution threshold, the largest channel parameter so that the bit error probability tends to zero as a function of the iterations. In practice we often work with short codes and perform a large number of iterations. It is therefore interesting to consider what happens if in the standard analysis we exchange the order in which the blocklength and the number of iterations diverge to infinity. In particular, we can ask whether both limits give the same threshold. Although empirical observations strongly suggest that the exchange of limits is valid for all channel parameters, we limit our discussion to channel parameters below the density evolution threshold. Specifically, we show that under some suitable technical conditions the bit error probability vanishes below the density evolution threshold regardless of how the limit is taken.
Some results on (a:b)-choosability
Venue: arXiv cs.DM 2008
Year: 2008

A solution to a problem of Erdős, Rubin and Taylor is obtained by showing that if a graph $G$ is $(a:b)$-choosable, and $c/d > a/b$, then $G$ is not necessarily $(c:d)$-choosable. Applying probabilistic methods, an upper bound for the $k^{th}$ choice number of a graph is given. We also prove that a directed graph with maximum outdegree $d$ and no odd directed cycle is $(k(d+1):k)$-choosable for every $k \geq 1$. Other results presented in this article are related to the strong choice number of graphs (a generalization of the strong chromatic number). We conclude with complexity analysis of some decision problems related to graph choosability.
Convergence of some leader election algorithms
Venue: arXiv cs.DC 2008
Year: 2008

We start with a set of n players. With some probability P(n,k), we kill n-k players; the other ones stay alive, and we repeat with them. What is the distribution of the number X_n of phases (or rounds) before getting only one player? We present a probabilistic analysis of this algorithm under some conditions on the probability distributions P(n,k), including stochastic monotonicity and the assumption that roughly a fixed proportion alpha of the players survive in each round. We prove a kind of convergence in distribution for X_n-log_a n, where the basis a=1/alpha; as in many other similar problems there are oscillations and no true limit distribution, but suitable subsequences converge, and there is an absolutely continuous random variable Z such that the distribution of X_n can be approximated by Z+log_a n rounded to the nearest larger integer. Applications of the general result include the leader election algorithm where players are eliminated by independent coin tosses and a variation of the leader election algorithm proposed by W.R. Franklin. We study the latter algorithm further, including numerical results.
Les Agents comme des interpréteurs Scheme : Spécification dynamique par la communication
Venue: arXiv cs.MA 2008
Year: 2008

We proposed in previous papers an extension and an implementation of the STROBE model, which regards the Agents as Scheme interpreters. These Agents are able to interpret messages in a dedicated environment including an interpreter that learns from the current conversation therefore representing evolving meta-level Agent's knowledge. When the Agent's interpreter is a nondeterministic one, the dialogues may consist of subsequent refinements of specifications in the form of constraint sets. The paper presents a worked out example of dynamic service generation - such as necessary on Grids - by exploiting STROBE Agents equipped with a nondeterministic interpreter. It shows how enabling dynamic specification of a problem. Then it illustrates how these principles could be effective for other applications. Details of the implementation are not provided here, but are available.
A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization
Venue: arXiv cs.LG 2008
Year: 2008

We present a general approach for collaborative filtering (CF) using spectral regularization to learn linear operators from "users" to the "objects" they rate. Recent low-rank type matrix completion approaches to CF are shown to be special cases. However, unlike existing regularization based CF methods, our approach can be used to also incorporate information such as attributes of the users or the objects -- a limitation of existing regularization based CF methods. We then provide novel representer theorems that we use to develop new estimation methods. We provide learning algorithms based on low-rank decompositions, and test them on a standard CF dataset. The experiments indicate the advantages of generalizing the existing regularization based CF methods to incorporate related information about users and objects. Finally, we show that certain multi-task learning methods can be also seen as special cases of our proposed approach.
Minimal Committee Problem for Inconsistent Systems of Linear Inequalities on the Plane
Venue: arXiv cs.DM 2008
Year: 2008

A representation of an arbitrary system of strict linear inequalities in R^n as a system of points is proposed. The representation is obtained by using a so-called polarity. Based on this representation an algorithm for constructing a committee solution of an inconsistent plane system of linear inequalities is given. A solution of two problems on minimal committee of a plane system is proposed. The obtained solutions to these problems can be found by means of the proposed algorithm.
SAT Has No Wizards
Venue: arXiv cs.CC 2008
Year: 2008

An (encoded) decision problem is a pair (E, F) where E=words that encode instances of the problem, F=words to be accepted. We use "strings" in a technical sense. With an NP problem (E, F) we associate the "logogram" of F relative to E, which conveys structural information on E, F, and how F is embedded in E. The kernel Ker(P) of a program P that solves (E, F) consists of those strings in the logogram that are used by P. There are relations between Ker(P) and the complexity of P. We develop an application to SAT that relies upon a property of internal independence of SAT. We show that SAT cannot have in its logogram strings serving as collective certificates. As consequence, all programs that solve SAT have same kernel.
Multi-hop Cooperative Wireless Networks: Diversity Multiplexing Tradeoff and Optimal Code Design
Venue: arXiv cs.IT 2008
Year: 2008

We consider single-source single-sink (ss-ss) multi-hop networks, with slow-fading links and single-antenna half-duplex relays. We identify two families of networks that are multi-hop generalizations of the well-studied two-hop network: K-Parallel-Path (KPP) networks and layered networks. KPP networks can be viewed as the union of K node-disjoint parallel relaying paths, each of length greater than one. KPP networks are then generalized to KPP(I) networks, which permit interference between paths and to KPP(D) networks, which possess a direct link from source to sink. We characterize the DMT of these families of networks completely for K > 3. Layered networks are networks comprising of relaying layers with edges existing only within the same layer or between adjacent layers. We prove that a linear DMT between the maximum diversity d_{max} and the maximum multiplexing gain of 1 is achievable for fully-connected layered networks. This is shown to be equal to the optimal DMT if the number of layers is less than 4. For multi-antenna KPP and layered networks, we provide an achievable DMT region. For arbitrary ss-ss single-antenna directed-acyclic full-duplex networks, we prove that a linear tradeoff between maximum diversity and maximum multiplexing gain is achievable. All protocols in this paper are explicit and use only amplify and forward (AF) relaying. We also construct codes with short block-lengths based on cyclic division algebras that achieve the optimal DMT for all the proposed schemes. Two key implications of the results in the paper are that the half-duplex constraint does not entail any rate loss for a large class of networks and that simple AF protocols are often sufficient to attain the optimal DMT.
Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem
Venue: arXiv cs.NE 2008
Year: 2008

There is considerable interest in the use of genetic algorithms to solve problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle the conflict between objectives and constraints that typically occurs in such problems. In order to overcome this, successful implementations frequently make use of problem specific knowledge. This paper is concerned with the development of a GA for a nurse rostering problem at a major UK hospital. The structure of the constraints is used as the basis for a co-evolutionary strategy using co-operating sub-populations. Problem specific knowledge is also used to define a system of incentives and disincentives, and a complementary mutation operator. Empirical results based on 52 weeks of live data show how these features are able to improve an unsuccessful canonical GA to the point where it is able to provide a practical solution to the problem