OpenRaiser/Intern-Atlas huggingface dataset:
Minimum Enclosing Polytope in High Dimensions
Venue: arXiv cs.CG 2004
Year: 2004

We study the problem of covering a given set of $n$ points in a high, $d$-dimensional space by the minimum enclosing polytope of a given arbitrary shape. We present algorithms that work for a large family of shapes, provided either only translations and no rotations are allowed, or only rotation about a fixed point is allowed; that is, one is allowed to only scale and translate a given shape, or scale and rotate the shape around a fixed point. Our algorithms start with a polytope guessed to be of optimal size and iteratively moves it based on a greedy principle: simply move the current polytope directly towards any outside point till it touches the surface. For computing the minimum enclosing ball, this gives a simple greedy algorithm with running time $O(nd/\eps)$ producing a ball of radius $1+\eps$ times the optimal. This simple principle generalizes to arbitrary convex shape when only translations are allowed, requiring at most $O(1/\eps^2)$ iterations. Our algorithm implies that {\em core-sets} of size $O(1/\eps^2)$ exist not only for minimum enclosing ball but also for any convex shape with a fixed orientation. A {\em Core-Set} is a small subset of $poly(1/\eps)$ points whose minimum enclosing polytope is almost as large as that of the original points. Although we are unable to combine our techniques for translations and rotations for general shapes, for the min-cylinder problem, we give an algorithm similar to the one in \cite{HV03}, but with an improved running time of $2^{O(\frac{1}{\eps^2}\log \frac{1}{\eps})} nd$.
Multi-agent coordination using nearest neighbor rules: revisiting the Vicsek model
Venue: arXiv cs.MA 2004
Year: 2004

Recently, Jadbabaie, Lin, and Morse (IEEE TAC, 48(6)2003:988-1001) offered a mathematical analysis of the discrete time model of groups of mobile autonomous agents raised by Vicsek et al. in 1995. In their paper, Jadbabaie et al. showed that all agents shall move in the same heading, provided that these agents are periodically linked together. This paper sharpens this result by showing that coordination will be reached under a very weak condition that requires all agents are finally linked together. This condition is also strictly weaker than the one Jadbabaie et al. desired.
Exposing Software Defined Radio Functionality To Native Operating System Applications via Virtual Devices
Venue: arXiv cs.AR 2004
Year: 2004

Many reconfigurable platforms require that applications be written specifically to take advantage of the reconfigurable hardware. In a PC-based environment, this presents an undesirable constraint in that the many already available applications cannot leverage on such hardware. Greatest benefit can only be derived from reconfigurable devices if even native OS applications can transparently utilize reconfigurable devices as they would normal full-fledged hardware devices. This paper presents how Proteus Virtual Devices are used to expose reconfigurable hardware in a transparent manner for use by typical native OS applications.
Model Checking of Statechart Models: Survey and Research Directions
Venue: arXiv cs.SE 2004
Year: 2004

We survey existing approaches to the formal verification of statecharts using model checking. Although the semantics and subset of statecharts used in each approach varies considerably, along with the model checkers and their specification languages, most approaches rely on translating the hierarchical structure into the flat representation of the input language of the model checker. This makes model checking difficult to scale to industrial models, as the state space grows exponentially with flattening. We look at current approaches to model checking hierarchical structures and find that their semantics is significantly different from statecharts. We propose to address the problem of state space explosion using a combination of techniques, which are proposed as directions for further research.
Decomposition Based Search - A theoretical and experimental evaluation
Venue: arXiv cs.AI 2004
Year: 2004

In this paper we present and evaluate a search strategy called Decomposition Based Search (DBS) which is based on two steps: subproblem generation and subproblem solution. The generation of subproblems is done through value ranking and domain splitting. Subdomains are explored so as to generate, according to the heuristic chosen, promising subproblems first. We show that two well known search strategies, Limited Discrepancy Search (LDS) and Iterative Broadening (IB), can be seen as special cases of DBS. First we present a tuning of DBS that visits the same search nodes as IB, but avoids restarts. Then we compare both theoretically and computationally DBS and LDS using the same heuristic. We prove that DBS has a higher probability of being successful than LDS on a comparable number of nodes, under realistic assumptions. Experiments on a constraint satisfaction problem and an optimization problem show that DBS is indeed very effective if compared to LDS.
Postponing Branching Decisions
Venue: arXiv cs.AI 2004
Year: 2004

Solution techniques for Constraint Satisfaction and Optimisation Problems often make use of backtrack search methods, exploiting variable and value ordering heuristics. In this paper, we propose and analyse a very simple method to apply in case the value ordering heuristic produces ties: postponing the branching decision. To this end, we group together values in a tie, branch on this sub-domain, and defer the decision among them to lower levels of the search tree. We show theoretically and experimentally that this simple modification can dramatically improve the efficiency of the search strategy. Although in practise similar methods may have been applied already, to our knowledge, no empirical or theoretical study has been proposed in the literature to identify when and to what extent this strategy should be used.
PELCR: Parallel Environment for Optimal Lambda-Calculus Reduction
Venue: arXiv cs.LO 2004
Year: 2004

In this article we present the implementation of an environment supporting Lévy's \emph{optimal reduction} for the $λ$-calculus \cite{Lev78} on parallel (or distributed) computing systems. In a similar approach to Lamping's one in \cite{Lamping90}, we base our work on a graph reduction technique known as \emph{directed virtual reduction} \cite{DPR97} which is actually a restriction of Danos-Regnier virtual reduction \cite{DanosRegnier93}. The environment, which we refer to as PELCR (Parallel Environment for optimal Lambda-Calculus Reduction) relies on a strategy for directed virtual reduction, namely {\em half combustion}, which we introduce in this article. While developing PELCR we have adopted both a message aggregation technique, allowing a reduction of the communication overhead, and a fair policy for distributing dynamically originated load among processors. We also present an experimental study demonstrating the ability of PELCR to definitely exploit parallelism intrinsic to $λ$-terms while performing the reduction. By the results we show how PELCR allows achieving up to 70/80% of the ideal speedup on last generation multiprocessor computing systems. As a last note, the software modules have been developed with the {\tt C} language and using a standard interface for message passing, i.e. MPI, thus making PELCR itself a highly portable software package.
A measure of similarity between graph vertices
Venue: arXiv cs.IR 2004
Year: 2004

We introduce a concept of similarity between vertices of directed graphs. Let G_A and G_B be two directed graphs. We define a similarity matrix whose (i, j)-th real entry expresses how similar vertex j (in G_A) is to vertex i (in G_B. The similarity matrix can be obtained as the limit of the normalized even iterates of a linear transformation. In the special case where G_A=G_B=G, the matrix is square and the (i, j)-th entry is the similarity score between the vertices i and j of G. We point out that Kleinberg's "hub and authority" method to identify web-pages relevant to a given query can be viewed as a special case of our definition in the case where one of the graphs has two vertices and a unique directed edge between them. In analogy to Kleinberg, we show that our similarity scores are given by the components of a dominant eigenvector of a non-negative matrix. Potential applications of our similarity concept are numerous. We illustrate an application for the automatic extraction of synonyms in a monolingual dictionary.
ParFORM: Parallel Version of the Symbolic Manipulation Program FORM
Venue: arXiv cs.SC 2004
Year: 2004

After an introduction to the sequential version of FORM and the mechanisms behind, we report on the status of our project of parallelization. We have now a parallel version of FORM running on Cluster- and SMP-architectures. This version can be used to run arbitrary FORM programs in parallel.
Consensus on Transaction Commit
Venue: arXiv cs.DC 2004
Year: 2004

The distributed transaction commit problem requires reaching agreement on whether a transaction is committed or aborted. The classic Two-Phase Commit protocol blocks if the coordinator fails. Fault-tolerant consensus algorithms also reach agreement, but do not block whenever any majority of the processes are working. Running a Paxos consensus algorithm on the commit/abort decision of each participant yields a transaction commit protocol that uses 2F +1 coordinators and makes progress if at least F +1 of them are working. In the fault-free case, this algorithm requires one extra message delay but has the same stable-storage write delay as Two-Phase Commit. The classic Two-Phase Commit algorithm is obtained as the special F = 0 case of the general Paxos Commit algorithm.
The Expected Size of the Rule k Dominating Set
Venue: arXiv cs.DM 2004
Year: 2004

Rule k is a localized approximation algorithm that finds a small connected dominating set in a graph. We estimate the expected size of the Rule k dominating set for the model of random unit disk graphs constructed from n random points in an s_n by s_n square region of the plane.
Probabilistic heuristics for disseminating information in networks
Venue: arXiv cs.NI 2004
Year: 2004

We study the problem of disseminating a piece of information through all the nodes of a network, given that it is known originally only to a single node. In the absence of any structural knowledge on the network other than the nodes' neighborhoods, this problem is traditionally solved by flooding all the network's edges. We analyze a recently introduced probabilistic algorithm for flooding and give an alternative probabilistic heuristic that can lead to some cost-effective improvements, like better trade-offs between the message and time complexities involved. We analyze the two algorithms both mathematically and by means of simulations, always within a random-graph framework and considering relevant node-degree distributions.
Default reasoning over domains and concept hierarchies
Venue: arXiv cs.AI 2004
Year: 2004

W.C. Rounds and G.-Q. Zhang (2001) have proposed to study a form of disjunctive logic programming generalized to algebraic domains. This system allows reasoning with information which is hierarchically structured and forms a (suitable) domain. We extend this framework to include reasoning with default negation, giving rise to a new nonmonotonic reasoning framework on hierarchical knowledge which encompasses answer set programming with extended disjunctive logic programs. We also show that the hierarchically structured knowledge on which programming in this paradigm can be done, arises very naturally from formal concept analysis. Together, we obtain a default reasoning paradigm for conceptual knowledge which is in accordance with mainstream developments in nonmonotonic reasoning.
Distance properties of expander codes
Venue: arXiv cs.IT 2004
Year: 2004

We study the minimum distance of codes defined on bipartite graphs. Weight spectrum and the minimum distance of a random ensemble of such codes are computed. It is shown that if the vertex codes have minimum distance $\ge 3$, the overall code is asymptotically good, and sometimes meets the Gilbert-Varshamov bound. Constructive families of expander codes are presented whose minimum distance asymptotically exceeds the product bound for all code rates between 0 and 1.
Shannon meets Wiener II: On MMSE estimation in successive decoding schemes
Venue: arXiv cs.IT 2004
Year: 2004

We continue to discuss why MMSE estimation arises in coding schemes that approach the capacity of linear Gaussian channels. Here we consider schemes that involve successive decoding, such as decision-feedback equalization or successive cancellation.
A Digital Signature with Threshold Generation and Verification
Venue: arXiv cs.CR 2004
Year: 2004

This paper proposes a signature scheme where the signatures are generated by the cooperation of a number of people from a given group of senders and the signatures are verified by a certain number of people from the group of recipients. Shamir's threshold scheme and Schnorr's signature scheme are used to realize the proposed scheme.
Two Models for the Study of Congested Internet Connections
Venue: arXiv cs.NI 2004
Year: 2004

In this paper, we introduce two deterministic models aimed at capturing the dynamics of congested Internet connections. The first model is a continuous-time model that combines a system of differential equations with a sudden change in one of the state variables. The second model is a discrete-time model with a time step that arises naturally from the system. Results from these models show good agreement with the well-known ns network simulator, better than the results of a previous, similar model. This is due in large part to the use of the sudden change to reflect the impact of lost data packets. We also discuss the potential use of this model in network traffic state estimation.
Proximity Inversion Functions on the Non-Negative Integers
Venue: arXiv cs.DM 2004
Year: 2004

We consider functions mapping non-negative integers to non-negative real numbers such that a and a+n are mapped to values at least 1/n apart. In this paper we use a novel method to construct such a function. We conjecture that the supremum of the generated function is optimal and pose some unsolved problems.
Bounds on the decoding complexity of punctured codes on graphs
Venue: arXiv cs.IT 2004
Year: 2004

We present two sequences of ensembles of non-systematic irregular repeat-accumulate codes which asymptotically (as their block length tends to infinity) achieve capacity on the binary erasure channel (BEC) with bounded complexity per information bit. This is in contrast to all previous constructions of capacity-achieving sequences of ensembles whose complexity grows at least like the log of the inverse of the gap (in rate) to capacity. The new bounded complexity result is achieved by puncturing bits, and allowing in this way a sufficient number of state nodes in the Tanner graph representing the codes. We also derive an information-theoretic lower bound on the decoding complexity of randomly punctured codes on graphs. The bound holds for every memoryless binary-input output-symmetric channel, and is refined for the BEC.
Business Processes: The Theoretical Impact of Process Thinking on Information Systems Development
Venue: arXiv cs.OH 2004
Year: 2004

This paper investigates two aspects of process thinking that affect the success rate of IT projects. These two aspects are the changes in the structure of organizations and the epistemology of Information Systems Development. Firstly, the conception of business processes within the management of organizations increases the structural complexity of Information Systems, because existing systems have to be integrated into a coherent cross-functional architecture. Secondly, process thinking leads to a particular view of organizations that ultimately has a negative effect on the support of Information Systems. As an illustration of process thinking, the Business Process Reengineering movement adheres to a technocratic management perspective of organizations. Particularly this conception of organization views people as mechanisms to realize certain organizational goals. As a result of this view stakeholders are confronted with the implemented systems, rather than consulted about the scope and functionality of those systems. Therefore, both aspects of process thinking have a negative impact on the success of IT projects. The problem of structural complexity is an area that is addressed by Enterprise Application Integration, and mainly requires technical solutions. However, the problems associated with the conception of organization require a different, markedly non-technical, perspective. Several directions are discussed to overcome some limitations of process thinking, but these directions are merely small pointers. If truly effective and useful Information Systems are to be acquired, IT practitioners and scientists require a completely different mindset.
Four Principles Fundamental to Design Practice for Human Centred Systems
Venue: arXiv cs.HC 2004
Year: 2004

A Survey of the principal literature on Human Centred Design reveals the four most referenced principles. These are discussed with reference to the application of a particular website, and a user survey is constructed based upon the four principles.
Inapproximability of Combinatorial Optimization Problems
Venue: arXiv cs.CC 2004
Year: 2004

We survey results on the hardness of approximating combinatorial optimization problems.
FORM Matters: Fast Symbolic Computation under UNIX
Venue: arXiv cs.SC 2004
Year: 2004

We give a brief introduction to FORM, a symbolic programming language for massive batch operations, designed by J.A.M. Vermaseren. In particular, we stress various methods to efficiently use FORM under the UNIX operating system. Several scripts and examples are given, and suggestions on how to use the vim editor as development platform.
From Digital Television to Internet?
Venue: arXiv cs.MM 2004
Year: 2004

This paper provides a general technical overview of the Multimedia Home Platform (MHP) specifications. MHP is a generic interface between digital applications and user machines, whether they happen to be set top boxes, digital TV sets or Multimedia PC's. MHP extends the DVB open standards. Addressed are MHP architexture, System core and MHP Profiles.
The Infati Data
Venue: arXiv cs.DB 2004
Year: 2004

The ability to perform meaningful empirical studies is of essence in research in spatio-temporal query processing. Such studies are often necessary to gain detailed insight into the functional and performance characteristics of proposals for new query processing techniques. We present a collection of spatio-temporal data, collected during an intelligent speed adaptation project, termed INFATI, in which some two dozen cars equipped with GPS receivers and logging equipment took part. We describe how the data was collected and how it was "modified" to afford the drivers some degree of anonymity. We also present the road network in which the cars were moving during data collection. The GPS data is publicly available for non-commercial purposes. It is our hope that this resource will help the spatio-temporal research community in its efforts to develop new and better query processing techniques.
Shannon Information and Kolmogorov Complexity
Venue: arXiv cs.IT 2004
Year: 2004

We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and where they are fundamentally different. We discuss and relate the basic notions of both theories: Shannon entropy versus Kolmogorov complexity, the relation of both to universal coding, Shannon mutual information versus Kolmogorov (`algorithmic') mutual information, probabilistic sufficient statistic versus algorithmic sufficient statistic (related to lossy compression in the Shannon theory versus meaningful information in the Kolmogorov theory), and rate distortion theory versus Kolmogorov's structure function. Part of the material has appeared in print before, scattered through various publications, but this is the first comprehensive systematic comparison. The last mentioned relations are new.
Source Coding with Fixed Lag Side Information
Venue: arXiv cs.IT 2004
Year: 2004

We consider source coding with fixed lag side information at the decoder. We focus on the special case of perfect side information with unit lag corresponding to source coding with feedforward (the dual of channel coding with feedback) introduced by Pradhan. We use this duality to develop a linear complexity algorithm which achieves the rate-distortion bound for any memoryless finite alphabet source and distortion measure.
Comment on A dynamic ID-based Remote User Authentication Scheme
Venue: arXiv cs.CR 2004
Year: 2004

Since 1981, when Lamport introduced the remote user authentication scheme using table, a plenty of schemes had been proposed with tables or without table using. Recently Das et al. proposed a dynamic id-based remote user authentication scheme. They claimed that their scheme is secure against ID-theft, and can resist the reply attacks, forgery attacks, insider attacks an so on. In this paper we show that Das et al's scheme is completly insecure and using of this scheme is like an open server access without password.
HEP@Home - A distributed computing system based on BOINC
Venue: arXiv cs.DC 2004
Year: 2004

Project SETI@HOME has proven to be one of the biggest successes of distributed computing during the last years. With a quite simple approach SETI manages to process large volumes of data using a vast amount of distributed computer power. To extend the generic usage of this kind of distributed computing tools, BOINC is being developed. In this paper we propose HEP@HOME, a BOINC version tailored to the specific requirements of the High Energy Physics (HEP) community. The HEP@HOME will be able to process large amounts of data using virtually unlimited computing power, as BOINC does, and it should be able to work according to HEP specifications. In HEP the amounts of data to be analyzed or reconstructed are of central importance. Therefore, one of the design principles of this tool is to avoid data transfer. This will allow scientists to run their analysis applications and taking advantage of a large number of CPUs. This tool also satisfies other important requirements in HEP, namely, security, fault-tolerance and monitoring.
Finite-Length Scaling and Finite-Length Shift for Low-Density Parity-Check Codes
Venue: arXiv cs.IT 2004
Year: 2004

Consider communication over the binary erasure channel BEC using random low-density parity-check codes with finite-blocklength n from `standard' ensembles. We show that large error events is conveniently described within a scaling theory, and explain how to estimate heuristically their effect. Among other quantities, we consider the finite length threshold e(n), defined by requiring a block error probability P_B = 1/2. For ensembles with minimum variable degree larger than two, the following expression is argued to hold e(n) = e -e_1 n^{-2/3} +Θ(n^{-1}) with a calculable shift} parameter e_1>0.
The Key Authority - Secure Key Management in Hierarchical Public Key Infrastructures
Venue: arXiv cs.CR 2004
Year: 2004

We model a private key`s life cycle as a finite state machine. The states are the key`s phases of life and the transition functions describe tasks to be done with the key. Based on this we define and describe the key authority, a trust center module, which potentiates the easy enforcement of secure management of private keys in hierarchical public key infrastructures. This is done by assembling all trust center tasks concerning the crucial handling of private keys within one centralized module. As this module resides under full control of the trust center`s carrier it can easily be protected by well-known organizational and technical measures.