OpenRaiser/Intern-Atlas huggingface dataset:
Substitute Valuations: Generation and Structure
Venue: arXiv cs.GT 2008
Year: 2008

Substitute valuations (in some contexts called gross substitute valuations) are prominent in combinatorial auction theory. An algorithm is given in this paper for generating a substitute valuation through Monte Carlo simulation. In addition, the geometry of the set of all substitute valuations for a fixed number of goods K is investigated. The set consists of a union of polyhedrons, and the maximal polyhedrons are identified for K=4. It is shown that the maximum dimension of the maximal polyhedrons increases with K nearly as fast as two to the power K. Consequently, under broad conditions, if a combinatorial algorithm can present an arbitrary substitute valuation given a list of input numbers, the list must grow nearly as fast as two to the power K.
Biology of Applied Digital Ecosystems
Venue: arXiv cs.NE 2008
Year: 2008

A primary motivation for our research in Digital Ecosystems is the desire to exploit the self-organising properties of biological ecosystems. Ecosystems are thought to be robust, scalable architectures that can automatically solve complex, dynamic problems. However, the biological processes that contribute to these properties have not been made explicit in Digital Ecosystems research. Here, we discuss how biological properties contribute to the self-organising features of biological ecosystems, including population dynamics, evolution, a complex dynamic environment, and spatial distributions for generating local interactions. The potential for exploiting these properties in artificial systems is then considered. We suggest that several key features of biological ecosystems have not been fully explored in existing digital ecosystems, and discuss how mimicking these features may assist in developing robust, scalable self-organising architectures. An example architecture, the Digital Ecosystem, is considered in detail. The Digital Ecosystem is then measured experimentally through simulations, with measures originating from theoretical ecology, to confirm its likeness to a biological ecosystem. Including the responsiveness to requests for applications from the user base, as a measure of the 'ecological succession' (development).
Security for Wiretap Networks via Rank-Metric Codes
Venue: arXiv cs.IT 2008
Year: 2008

The problem of securing a network coding communication system against a wiretapper adversary is considered. The network implements linear network coding to deliver $n$ packets from source to each receiver, and the wiretapper can eavesdrop on $μ$ arbitrarily chosen links. A coding scheme is proposed that can achieve the maximum possible rate of $k=n-μ$ packets that are information-theoretically secure from the adversary. A distinctive feature of our scheme is that it is universal: it can be applied on top of any communication network without requiring knowledge of or any modifications on the underlying network code. In fact, even a randomized network code can be used. Our approach is based on Rouayheb-Soljanin's formulation of a wiretap network as a generalization of the Ozarow-Wyner wiretap channel of type II. Essentially, the linear MDS code in Ozarow-Wyner's coset coding scheme is replaced by a maximum-rank-distance code over an extension of the field in which linear network coding operations are performed.
On the Relationship between Transmission Power and Capacity of an Underwater Acoustic Communication Channel
Venue: arXiv cs.IT 2008
Year: 2008

The underwater acoustic channel is characterized by a path loss that depends not only on the transmission distance, but also on the signal frequency. As a consequence, transmission bandwidth depends on the transmission distance, a feature that distinguishes an underwater acoustic system from a terrestrial radio system. The exact relationship between power, transmission band, distance and capacity for the Gaussian noise scenario is a complicated one. This work provides a closed-form approximate model for 1) power consumption, 2) band-edge frequency and 3) bandwidth as functions of distance and capacity required for a data link. This approximate model is obtained by numerical evaluation of analytical results which takes into account physical models of acoustic propagation loss and ambient noise. The closed-form approximations may become useful tools in the design and analysis of underwater acoustic networks.
Sum Capacity of the Gaussian Interference Channel in the Low Interference Regime
Venue: arXiv cs.IT 2008
Year: 2008

New upper bounds on the sum capacity of the two-user Gaussian interference channel are derived. Using these bounds, it is shown that treating interference as noise achieves the sum capacity if the interference levels are below certain thresholds.
A System Theoretic Approach to Bandwidth Estimation
Venue: arXiv cs.NI 2008
Year: 2008

It is shown that bandwidth estimation in packet networks can be viewed in terms of min-plus linear system theory. The available bandwidth of a link or complete path is expressed in terms of a {\em service curve}, which is a function that appears in the network calculus to express the service available to a traffic flow. The service curve is estimated based on measurements of a sequence of probing packets or passive measurements of a sample path of arrivals. It is shown that existing bandwidth estimation methods can be derived in the min-plus algebra of the network calculus, thus providing further mathematical justification for these methods. Principal difficulties of estimating available bandwidth from measurement of network probes are related to potential non-linearities of the underlying network. When networks are viewed as systems that operate either in a linear or in a non-linear regime, it is argued that probing schemes extract the most information at a point when the network crosses from a linear to a non-linear regime. Experiments on the Emulab testbed at the University of Utah evaluate the robustness of the system theoretic interpretation of networks in practice. Multi-node experiments evaluate how well the convolution operation of the min-plus algebra provides estimates for the available bandwidth of a path from estimates of individual links.
A logical analysis of entanglement and separability in quantum higher-order functions
Venue: arXiv cs.LO 2008
Year: 2008

We present a logical separability analysis for a functional quantum computation language. This logic is inspired by previous works on logical analysis of aliasing for imperative functional programs. Both analyses share similarities notably because they are highly non-compositional. Quantum setting is harder to deal with since it introduces non determinism and thus considerably modifies semantics and validity of logical assertions. This logic is the first proposal of entanglement/separability analysis dealing with a functional quantum programming language with higher-order functions.
Call-by-value Termination in the Untyped lambda-calculus
Venue: arXiv cs.PL 2008
Year: 2008

A fully-automated algorithm is developed able to show that evaluation of a given untyped lambda-expression will terminate under CBV (call-by-value). The ``size-change principle'' from first-order programs is extended to arbitrary untyped lambda-expressions in two steps. The first step suffices to show CBV termination of a single, stand-alone lambda;-expression. The second suffices to show CBV termination of any member of a regular set of lambda-expressions, defined by a tree grammar. (A simple example is a minimum function, when applied to arbitrary Church numerals.) The algorithm is sound and proven so in this paper. The Halting Problem's undecidability implies that any sound algorithm is necessarily incomplete: some lambda-expressions may in fact terminate under CBV evaluation, but not be recognised as terminating. The intensional power of the termination algorithm is reasonably high. It certifies as terminating many interesting and useful general recursive algorithms including programs with mutual recursion and parameter exchanges, and Colson's ``minimum'' algorithm. Further, our type-free approach allows use of the Y combinator, and so can identify as terminating a substantial subset of PCF.
Generative Unbinding of Names
Venue: arXiv cs.PL 2008
Year: 2008

This paper is concerned with the form of typed name binding used by the FreshML family of languages. Its characteristic feature is that a name binding is represented by an abstract (name,value)-pair that may only be deconstructed via the generation of fresh bound names. The paper proves a new result about what operations on names can co-exist with this construct. In FreshML the only observation one can make of names is to test whether or not they are equal. This restricted amount of observation was thought necessary to ensure that there is no observable difference between alpha-equivalent name binders. Yet from an algorithmic point of view it would be desirable to allow other operations and relations on names, such as a total ordering. This paper shows that, contrary to expectations, one may add not just ordering, but almost any relation or numerical function on names without disturbing the fundamental correctness result about this form of typed name binding (that object-level alpha-equivalence precisely corresponds to contextual equivalence at the programming meta-level), so long as one takes the state of dynamically created names into account.
Almost 2-SAT is Fixed-Parameter Tractable
Venue: arXiv cs.DS 2008
Year: 2008

We consider the following problem. Given a 2-CNF formula, is it possible to remove at most $k$ clauses so that the resulting 2-CNF formula is satisfiable? This problem is known to different research communities in Theoretical Computer Science under the names 'Almost 2-SAT', 'All-but-$k$ 2-SAT', '2-CNF deletion', '2-SAT deletion'. The status of fixed-parameter tractability of this problem is a long-standing open question in the area of Parameterized Complexity. We resolve this open question by proposing an algorithm which solves this problem in $O(15^k*k*m^3)$ and thus we show that this problem is fixed-parameter tractable.
An Algorithm to Compute the Nearest Point in the Lattice $A_{n}^*$
Venue: arXiv cs.IT 2008
Year: 2008

The lattice $A_n^*$ is an important lattice because of its covering properties in low dimensions. Clarkson \cite{Clarkson1999:Anstar} described an algorithm to compute the nearest lattice point in $A_n^*$ that requires $O(n\log{n})$ arithmetic operations. In this paper, we describe a new algorithm. While the complexity is still $O(n\log{n})$, it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.
The emerging field of language dynamics
Venue: arXiv cs.CL 2008
Year: 2008

A simple review by a linguist, citing many articles by physicists: Quantitative methods, agent-based computer simulations, language dynamics, language typology, historical linguistics
Core Persistence in Peer-to-Peer Systems: Relating Size to Lifetime
Venue: arXiv cs.DC 2008
Year: 2008

Distributed systems are now both very large and highly dynamic. Peer to peer overlay networks have been proved efficient to cope with this new deal that traditional approaches can no longer accommodate. While the challenge of organizing peers in an overlay network has generated a lot of interest leading to a large number of solutions, maintaining critical data in such a network remains an open issue. In this paper, we are interested in defining the portion of nodes and frequency one has to probe, given the churn observed in the system, in order to achieve a given probability of maintaining the persistence of some critical data. More specifically, we provide a clear result relating the size and the frequency of the probing set along with its proof as well as an analysis of the way of leveraging such an information in a large scale dynamic distributed system.
An Evaluation of a Structured Spreadsheet Development Methodology
Venue: arXiv cs.CY 2008
Year: 2008

This paper presents the results of an empirical evaluation of the quality of a structured methodology for the development of spreadsheet models, proposed in numerous previous papers by Rajalingham K, Knight B and Chadwick D et al. This paper also describes an improved version of their methodology, supported by appropriate examples. The principal objective of a structured and disciplined methodology for the construction of spreadsheet models is to reduce the occurrence of user-generated errors in the models. The evaluation of the effectiveness of the methodology has been carried out based on a number of real-life experiments. The results of these experiments demonstrate the methodology's potential for improved integrity control and enhanced comprehensibility of spreadsheet models.
Synthesis of Large Dynamic Concurrent Programs from Dynamic Specifications
Venue: arXiv cs.LO 2008
Year: 2008

We present a tractable method for synthesizing arbitrarily large concurrent programs, for a shared memory model with common hardware-available primitives such as atomic registers, compare-and-swap, load-linked/store conditional, etc. The programs we synthesize are dynamic: new processes can be created and added at run-time, and so our programs are not finite-state, in general. Nevertheless, we successfully exploit automatic synthesis and model-checking methods based on propositional temporal logic. Our method is algorithmically efficient, with complexity polynomial in the number of component processes (of the program) that are ``alive'' at any time. Our method does not explicitly construct the automata-theoretic product of all processes that are alive, thereby avoiding \intr{state explosion}. Instead, for each pair of processes which interact, our method constructs an automata-theoretic product (\intr{pair-machine}) which embodies all the possible interactions of these two processes. From each pair-machine, we can synthesize a correct \intr{pair-program} which coordinates the two involved processes as needed. We allow such pair-programs to be added dynamically at run-time. They are then ``composed conjunctively'' with the currently alive pair-programs to re-synthesize the program as it results after addition of the new pair-program. We are thus able to add new behaviors, which result in new properties being satisfied, at run-time. We establish a ``large model'' theorem which shows that the synthesized large program inherits correctness properties from the pair-programs.
A Family of Counter Examples to an Approach to Graph Isomorphism
Venue: arXiv cs.CC 2008
Year: 2008

We give a family of counter examples showing that the two sequences of polytopes $Φ_{n,n}$ and $Ψ_{n,n}$ are different. These polytopes were defined recently by S. Friedland in an attempt at a polynomial time algorithm for graph isomorphism.
A Framework for Designing Teleconsultation Systems in Africa
Venue: arXiv cs.HC 2008
Year: 2008

All of the countries within Africa experience a serious shortage of medical professionals, particularly specialists, a problem that is only exacerbated by high emigration of doctors with better prospects overseas. As a result, those that remain in Africa, particularly those practicing in rural regions, experience a shortage of specialists and other colleagues with whom to exchange ideas. Telemedicine and teleconsultation are key areas that attempt to address this problem by leveraging remote expertise for local problems. This paper presents an overview of teleconsultation in the developing world, with a particular focus on how lessons learned apply to Africa. By teleconsultation, we are addressing non-real-time communication between health care professionals for the purposes of providing expertise and informal recommendations, without the real-time, interactive requirements typical of diagnosis and patient care, which is impractical for the vast majority of existing medical practices. From these previous experiences, we draw a set of guidelines and examine their relevance to Ghana in particular. Based on 6 weeks of needs assessment, we identify key variables that guide our framework, and then illustrate how our framework is used to inform the iterative design of a prototype system.
MathPSfrag 2: Convenient LaTeX Labels in Mathematica
Venue: arXiv cs.GR 2008
Year: 2008

This article introduces the next version of MathPSfrag. MathPSfrag is a Mathematica package that during export automatically replaces all expressions in a plot by corresponding LaTeX commands. The new version can also produce LaTeX independent images; e.g., PDF files for inclusion in pdfLaTeX. Moreover from these files a preview is generated and shown within Mathematica.
New Outer Bounds on the Capacity Region of Gaussian Interference Channels
Venue: arXiv cs.IT 2008
Year: 2008

Recent outer bounds on the capacity region of Gaussian interference channels are generalized to $m$-user channels with $m>2$ and asymmetric powers and crosstalk coefficients. The bounds are again shown to give the sum-rate capacity for Gaussian interference channels with low powers and crosstalk coefficients. The capacity is achieved by using single-user detection at each receiver, i.e., treating the interference as noise incurs no loss in performance.
Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
Venue: arXiv cs.IT 2008
Year: 2008

Second-order coding rate of channel coding is discussed for general sequence of channels. The optimum second-order transmission rate with a constant error constraint $ε$ is obtained by using the information spectrum method. We apply this result to the discrete memoryless case, the discrete memoryless case with a cost constraint, the additive Markovian case, and the Gaussian channel case with an energy constraint. We also clarify that the Gallager bound does not give the optimum evaluation in the second-order coding rate.
Algorithms for eps-approximations of Terrains
Venue: arXiv cs.CG 2008
Year: 2008

Consider a point set D with a measure function w : D -> R. Let A be the set of subsets of D induced by containment in a shape from some geometric family (e.g. axis-aligned rectangles, half planes, balls, k-oriented polygons). We say a range space (D, A) has an eps-approximation P if max {R \in A} | w(R \cap P)/w(P) - w(R \cap D)/w(D) | <= eps. We describe algorithms for deterministically constructing discrete eps-approximations for continuous point sets such as distributions or terrains. Furthermore, for certain families of subsets A, such as those described by axis-aligned rectangles, we reduce the size of the eps-approximations by almost a square root from O(1/eps^2 log 1/eps) to O(1/eps polylog 1/eps). This is often the first step in transforming a continuous problem into a discrete one for which combinatorial techniques can be applied. We describe applications of this result in geo-spatial analysis, biosurveillance, and sensor networks.
Balancing transparency, efficiency and security in pervasive systems
Venue: arXiv cs.HC 2008
Year: 2008

This chapter will survey pervasive computing with a look at how its constraint for transparency affects issues of resource management and security. The goal of pervasive computing is to render computing transparent, such that computing resources are ubiquitously offered to the user and services are proactively performed for a user without his or her intervention. The task of integrating computing infrastructure into everyday life without making it excessively invasive brings about tradeoffs between flexibility and robustness, efficiency and effectiveness, as well as autonomy and reliability. As the feasibility of ubiquitous computing and its real potential for mass applications are still a matter of controversy, this chapter will look into the underlying issues of resource management and authentication to discover how these can be handled in a least invasive fashion. The discussion will be closed by an overview of the solutions proposed by current pervasive computing efforts, both in the area of generic platforms and for dedicated applications such as pervasive education and healthcare.
A Pyramidal Evolutionary Algorithm with Different Inter-Agent Partnering Strategies for Scheduling Problems
Venue: arXiv cs.NE 2008
Year: 2008

This paper combines the idea of a hierarchical distributed genetic algorithm with different inter-agent partnering strategies. Cascading clusters of sub-populations are built from bottom up, with higher-level sub-populations optimising larger parts of the problem. Hence higher-level sub-populations search a larger search space with a lower resolution whilst lower-level sub-populations search a smaller search space with a higher resolution. The effects of different partner selection schemes amongst the agents on solution quality are examined for two multiple-choice optimisation problems. It is shown that partnering strategies that exploit problem-specific knowledge are superior and can counter inappropriate (sub-) fitness measurements.
Complex Eigenvalues for Binary Subdivision Schemes
Venue: arXiv cs.GR 2008
Year: 2008

Convergence properties of binary stationary subdivision schemes for curves have been analyzed using the techniques of z-transforms and eigenanalysis. Eigenanalysis provides a way to determine derivative continuity at specific points based on the eigenvalues of a finite matrix. None of the well-known subdivision schemes for curves have complex eigenvalues. We prove when a convergent scheme with palindromic mask can have complex eigenvalues and that a lower limit for the size of the mask exists in this case. We find a scheme with complex eigenvalues achieving this lower bound. Furthermore we investigate this scheme numerically and explain from a geometric viewpoint why such a scheme has not yet been used in computer-aided geometric design.
On the Effects of Idiotypic Interactions for Recommendation Communities in Artificial Immune Systems
Venue: arXiv cs.NE 2008
Year: 2008

It has previously been shown that a recommender based on immune system idiotypic principles can out perform one based on correlation alone. This paper reports the results of work in progress, where we undertake some investigations into the nature of this beneficial effect. The initial findings are that the immune system recommender tends to produce different neighbourhoods, and that the superior performance of this recommender is due partly to the different neighbourhoods, and partly to the way that the idiotypic effect is used to weight each neighbours recommendations.
5-cycles and the Petersen graph
Venue: arXiv cs.DM 2008
Year: 2008

We show that if G is a connected bridgeless cubic graph whose every 2-factor is comprised of cycles of length five then G is the Petersen graph.
Crossing Borders: Security and Privacy Issues of the European e-Passport
Venue: arXiv cs.CR 2008
Year: 2008

The first generation of European e-passports will be issued in 2006. We discuss how borders are crossed regarding the security and privacy erosion of the proposed schemes, and show which borders need to be crossed to improve the security and the privacy protection of the next generation of e-passports. In particular we discuss attacks on Basic Access Control due to the low entropy of the data from which the access keys are derived, we sketch the European proposals for Extended Access Control and the weaknesses in that scheme, and show how fundamentally different design decisions can make e-passports more secure.
On Reliability of Dynamic Addressing Routing Protocols in Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2008
Year: 2008

In this paper, a reliability analysis is carried out to state a performance comparison between two recently proposed proactive routing algorithms. These protocols are able to scale in ad hoc and sensor networks by resorting to dynamic addressing, to face with the topology variability, which is typical of ad hoc, and sensor networks. Numerical simulations are also carried out to corroborate the results of the analysis.