OpenRaiser/Intern-Atlas huggingface dataset:
A Distributed Economics-based Infrastructure for Utility Computing
Venue: arXiv cs.DC 2004
Year: 2004

Existing attempts at utility computing revolve around two approaches. The first consists of proprietary solutions involving renting time on dedicated utility computing machines. The second requires the use of heavy, monolithic applications that are difficult to deploy, maintain, and use. We propose a distributed, community-oriented approach to utility computing. Our approach provides an infrastructure built on Web Services in which modular components are combined to create a seemingly simple, yet powerful system. The community-oriented nature generates an economic environment which results in fair transactions between consumers and providers of computing cycles while simultaneously encouraging improvements in the infrastructure of the computational grid itself.
Simple Optimal Wait-free Multireader Registers
Venue: arXiv cs.DC 2005
Year: 2005

Multireader shared registers are basic objects used as communication medium in asynchronous concurrent computation. We propose a surprisingly simple and natural scheme to obtain several wait-free constructions of bounded 1-writer multireader registers from atomic 1-writer 1-reader registers, that is easier to prove correct than any previous construction. Our main construction is the first symmetric pure timestamp one that is optimal with respect to the worst-case local use of control bits; the other one is optimal with respect to global use of control bits; both are optimal in time.
Indexing schemes for similarity search: an illustrated paradigm
Venue: arXiv cs.DS 2005
Year: 2005

We suggest a variation of the Hellerstein--Koutsoupias--Papadimitriou indexability model for datasets equipped with a similarity measure, with the aim of better understanding the structure of indexing schemes for similarity-based search and the geometry of similarity workloads. This in particular provides a unified approach to a great variety of schemes used to index into metric spaces and facilitates their transfer to more general similarity measures such as quasi-metrics. We discuss links between performance of indexing schemes and high-dimensional geometry. The concepts and results are illustrated on a very large concrete dataset of peptide fragments equipped with a biologically significant similarity measure.
On local equilibrium equations for clustering states
Venue: arXiv cs.CC 2005
Year: 2005

In this note we show that local equilibrium equations (the generalization of the TAP equations or of the belief propagation equations) do have solutions in the colorable phase of the coloring problem. The same results extend to other optimization problems where the solutions has cost zero (e.g. K-satisfiability). On a random graph the solutions of the local equilibrium equations are associated to clusters of configurations (clustering states). On a random graph the local equilibrium equations have solutions almost everywhere in the uncolored phase; in this case we have to introduce the concept quasi-solution of the local equilibrium equations.
Interest Rate Model Calibration Using Semidefinite Programming
Venue: arXiv cs.CE 2005
Year: 2005

We show that, for the purpose of pricing Swaptions, the Swap rate and the corresponding Forward rates can be considered lognormal under a single martingale measure. Swaptions can then be priced as options on a basket of lognormal assets and an approximation formula is derived for such options. This formula is centered around a Black-Scholes price with an appropriate volatility, plus a correction term that can be interpreted as the expected tracking error. The calibration problem can then be solved very efficiently using semidefinite programming.
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots
Venue: arXiv cs.DS 2005
Year: 2005

An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of ``asleep'' robots, by having an awakened robot move to their locations. Once a robot is awake, it can assist in awakening other slumbering robots.The objective is to have all robots awake as early as possible. While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different. We consider both scenarios on graphs and in geometric environments.In graphs, robots sleep at vertices and there is a length function on the edges. Awake robots travel along edges, with time depending on edge length. For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots. We prove that the problem is NP-hard, even for the special case of star graphs. We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree.These lower bounds are complemented with several positive algorithmic results, including: (1) We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs. (2) We give a simple O(log D)-competitive online algorithm for graphs with maximum degree D and locally bounded edge weights. (3) We give a PTAS, running in nearly linear time, for geometrically embedded instances.
Epistemic Foundation of Stable Model Semantics
Venue: arXiv cs.AI 2005
Year: 2005

Stable model semantics has become a very popular approach for the management of negation in logic programming. This approach relies mainly on the closed world assumption to complete the available knowledge and its formulation has its basis in the so-called Gelfond-Lifschitz transformation. The primary goal of this work is to present an alternative and epistemic-based characterization of stable model semantics, to the Gelfond-Lifschitz transformation. In particular, we show that stable model semantics can be defined entirely as an extension of the Kripke-Kleene semantics. Indeed, we show that the closed world assumption can be seen as an additional source of `falsehood' to be added cumulatively to the Kripke-Kleene semantics. Our approach is purely algebraic and can abstract from the particular formalism of choice as it is based on monotone operators (under the knowledge order) over bilattices only.
Elements for Response Time Statistics in ERP Transaction Systems
Venue: arXiv cs.PF 2005
Year: 2005

We present some measurements and ideas for response time statistics in ERP systems. It is shown that the response time distribution of a given transaction in a given system is generically a log-normal distribution or, in some situations, a sum of two or more log-normal distributions. We present some arguments for this form of the distribution based on heuristic rules for response times, and we show data from performance measurements in actual systems to support the log-normal form. Deviations of the log-normal form can often be traced back to performance problems in the system. Consequences for the interpretation of response time data and for service level agreements are discussed.
Online Searching with Turn Cost
Venue: arXiv cs.DS 2005
Year: 2005

We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the searcher changes direction. This is a generalization of the well-studied linear-search problem. We describe a strategy that is guaranteed to find the object at a cost of at most 9*OPT + 2d, which has the optimal competitive ratio 9 with respect to OPT plus the minimum corresponding additive term. Our argument for upper and lower bound uses an infinite linear program, which we solve by experimental solution of an infinite series of approximating finite linear programs, estimating the limits, and solving the resulting recurrences. We feel that this technique is interesting in its own right and should help solve other searching problems. In particular, we consider the star search or cow-path problem with turn cost, where the hidden object is placed on one of m rays emanating from the original position of the searcher. For this problem we give a tight bound of (1+(2(m^m)/((m-1)^(m-1))) OPT + m ((m/(m-1))^(m-1) - 1) d. We also discuss tradeoff between the corresponding coefficients, and briefly consider randomized strategies on the line.
From truth to computability I
Venue: arXiv cs.LO 2005
Year: 2005

The recently initiated approach called computability logic is a formal theory of interactive computation. See a comprehensive online source on the subject at http://www.cis.upenn.edu/~giorgi/cl.html . The present paper contains a soundness and completeness proof for the deductive system CL3 which axiomatizes the most basic first-order fragment of computability logic called the finite-depth, elementary-base fragment. Among the potential application areas for this result are the theory of interactive computation, constructive applied theories, knowledgebase systems, systems for resource-bound planning and action. This paper is self-contained as it reintroduces all relevant definitions as well as main motivations.
PKI Scalability Issues
Venue: arXiv cs.CR 2005
Year: 2005

This report surveys different PKI technologies such as PKIX and SPKI and the issues of PKI that affect scalability. Much focus is spent on certificate revocation methodologies and status verification systems such as CRLs, Delta-CRLs, CRS, Certificate Revocation Trees, Windowed Certificate Revocation, OCSP, SCVP and DVCS.
Outlier Detection by Logic Programming
Venue: arXiv cs.AI 2005
Year: 2005

The development of effective knowledge discovery techniques has become in the recent few years a very active research area due to the important impact it has in several relevant application areas. One interesting task thereof is that of singling out anomalous individuals from a given population, e.g., to detect rare events in time-series analysis settings, or to identify objects whose behavior is deviant w.r.t. a codified standard set of "social" rules. Such exceptional individuals are usually referred to as outliers in the literature. Recently, outlier detection has also emerged as a relevant KR&R problem. In this paper, we formally state the concept of outliers by generalizing in several respects an approach recently proposed in the context of default logic, for instance, by having outliers not being restricted to single individuals but, rather, in the more general case, to correspond to entire (sub)theories. We do that within the context of logic programming and, mainly through examples, we discuss its potential practical impact in applications. The formalization we propose is a novel one and helps in shedding some light on the real nature of outliers. Moreover, as a major contribution of this work, we illustrate the exploitation of minimality criteria in outlier detection. The computational complexity of outlier detection problems arising in this novel setting is thoroughly investigated and accounted for in the paper as well. Finally, we also propose a rewriting algorithm that transforms any outlier detection problem into an equivalent inference problem under the stable model semantics, thereby making outlier computation effective and realizable on top of any stable model solver.
Feedback Capacity of the First-Order Moving Average Gaussian Channel
Venue: arXiv cs.IT 2005
Year: 2005

The feedback capacity of the stationary Gaussian additive noise channel has been open, except for the case where the noise is white. Here we find the feedback capacity of the stationary first-order moving average additive Gaussian noise channel in closed form. Specifically, the channel is given by $Y_i = X_i + Z_i,$ $i = 1, 2, ...,$ where the input $\{X_i\}$ satisfies a power constraint and the noise $\{Z_i\}$ is a first-order moving average Gaussian process defined by $Z_i = αU_{i-1} + U_i,$ $|α| \le 1,$ with white Gaussian innovations $U_i,$ $i = 0,1,....$ We show that the feedback capacity of this channel is $-\log x_0,$ where $x_0$ is the unique positive root of the equation $ ρx^2 = (1-x^2) (1 - |α|x)^2,$ and $ρ$ is the ratio of the average input power per transmission to the variance of the noise innovation $U_i$. The optimal coding scheme parallels the simple linear signalling scheme by Schalkwijk and Kailath for the additive white Gaussian noise channel -- the transmitter sends a real-valued information-bearing signal at the beginning of communication and subsequently refines the receiver's error by processing the feedback noise signal through a linear stationary first-order autoregressive filter. The resulting error probability of the maximum likelihood decoding decays doubly-exponentially in the duration of the communication. This feedback capacity of the first-order moving average Gaussian channel is very similar in form to the best known achievable rate for the first-order \emph{autoregressive} Gaussian noise channel studied by Butman, Wolfowitz, and Tiernan, although the optimality of the latter is yet to be established.
Measured descent: A new embedding method for finite metrics
Venue: arXiv cs.DS 2005
Year: 2005

We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This provides a refined and unified framework for the two primary methods of constructing Frechet embeddings for finite metrics, due to [Bourgain, 1985] and [Rao, 1999]. We prove that any n-point metric space (X,d) embeds in Hilbert space with distortion O(sqrt{alpha_X log n}), where alpha_X is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an O(sqrt{(log lambda_X) \log n}) distortion embedding, where λ_X is the doubling constant of X. Since λ_X\le n, this result recovers Bourgain's theorem, but when the metric X is, in a sense, ``low-dimensional,'' improved bounds are achieved. Our embeddings are volume-respecting for subsets of arbitrary size. One consequence is the existence of (k, O(log n)) volume-respecting embeddings for all 1 \leq k \leq n, which is the best possible, and answers positively a question posed by U. Feige. Our techniques are also used to answer positively a question of Y. Rabinovich, showing that any weighted n-point planar graph embeds in l_\infty^{O(log n)} with O(1) distortion. The O(log n) bound on the dimension is optimal, and improves upon the previously known bound of O((log n)^2).
A Survey of Distributed Intrusion Detection Approaches
Venue: arXiv cs.CR 2005
Year: 2005

Distributed intrustion detection systems detect attacks on computer systems by analyzing data aggregated from distributed sources. The distributed nature of the data sources allows patterns in the data to be seen that might not be detectable if each of the sources were examined individually. This paper describes the various approaches that have been developed to share and analyze data in such systems, and discusses some issues that must be addressed before fully decentralized distributed intrusion detection systems can be made viable.
On The Liniar Time Complexity of Finite Languages
Venue: arXiv cs.CC 2005
Year: 2005

The present paper presents and proves a proposition concerning the time complexity of finite languages. It is shown herein, that for any finite language (a language for which the set of words composing it is finite) there is a Turing machine that computes the language in such a way that for any input of length k the machine stops in, at most, k + 1 steps.
A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm
Venue: arXiv cs.IT 2005
Year: 2005

A simple and natural Gao algorithm for decoding algebraic codes is described. Its relation to the Welch-Berlekamp and Euclidean algorithms is given.
Fedora: An Architecture for Complex Objects and their Relationships
Venue: arXiv cs.DL 2005
Year: 2005

The Fedora architecture is an extensible framework for the storage, management, and dissemination of complex objects and the relationships among them. Fedora accommodates the aggregation of local and distributed content into digital objects and the association of services with objects. This al-lows an object to have several accessible representations, some of them dy-namically produced. The architecture includes a generic RDF-based relation-ship model that represents relationships among objects and their components. Queries against these relationships are supported by an RDF triple store. The architecture is implemented as a web service, with all aspects of the complex object architecture and related management functions exposed through REST and SOAP interfaces. The implementation is available as open-source soft-ware, providing the foundation for a variety of end-user applications for digital libraries, archives, institutional repositories, and learning object systems.
Estimating Range Queries using Aggregate Data with Integrity Constraints: a Probabilistic Approach
Venue: arXiv cs.DB 2005
Year: 2005

The problem of recovering (count and sum) range queries over multidimensional data only on the basis of aggregate information on such data is addressed. This problem can be formalized as follows. Suppose that a transformation T producing a summary from a multidimensional data set is used. Now, given a data set D, a summary S=T(D) and a range query r on D, the problem consists of studying r by modelling it as a random variable defined over the sample space of all the data sets D' such that T(D) = S. The study of such a random variable, done by the definition of its probability distribution and the computation of its mean value and variance, represents a well-founded, theoretical probabilistic approach for estimating the query only on the basis of the available information (that is the summary S) without assumptions on original data.
Thermodynamics of used punched tape: A weak and a strong equivalence principle
Venue: arXiv cs.IT 2005
Year: 2005

We study the repeated use of a monotonic recording medium--such as punched tape or photographic plate--where marks can be added at any time but never erased. (For practical purposes, also the electromagnetic "ether" falls into this class.) Our emphasis is on the case where the successive users act independently and selfishly, but not maliciously; typically, the "first user" would be a blind natural process tending to degrade the recording medium, and the "second user" a human trying to make the most of whatever capacity is left. To what extent is a length of used tape "equivalent"--for information transmission purposes--to a shorter length of virgin tape? Can we characterize a piece of used tape by an appropriate "effective length" and forget all other details? We identify two equivalence principles. The weak principle is exact, but only holds for a sequence of infinitesimal usage increments. The strong principle holds for any amount of incremental usage, but is only approximate; nonetheless, it is quite accurate even in the worst case and is virtually exact over most of the range--becoming exact in the limit of heavily used tape. The fact that strong equivalence does not hold exactly, but then it does almost exactly, comes as a bit of a surprise.
Concavity of the auxiliary function appearing in quantum reliability function an classical-quantum channels
Venue: arXiv cs.IT 2005
Year: 2005

Concavity of the auxiliary function which appears in the random coding exponent as the lower bound of the quantum reliability function for general quantum states is proven for s between 0 and 1.
Under-approximation of the Greatest Fixpoint in Real-Time System Verification
Venue: arXiv cs.SE 2005
Year: 2005

Techniques for the efficient successive under-approximation of the greatest fixpoint in TCTL formulas can be useful in fast refutation of inevitability properties and vacuity checking. We first give an integrated algorithmic framework for both under and over-approximate model-checking. We design the {\em NZF (Non-Zeno Fairness) predicate}, with a greatest fixpoint formulation, as a unified framework for the evaluation of formulas like $\exists\pfrrη_1$, $\exists\pfrr\pevtη_1$, and $\exists\pevt\pfrrη_1$. We then prove the correctness of a new formulation for the characterization of the NZF predicate based on zone search and the least fixpoint evaluation. The new formulation then leads to the design of an evaluation algorithm, with the capability of successive under-approximation, for $\exists\pfrrη_1$, $\exists\pfrr\pevtη_1$, and $\exists\pevt\pfrrη_1$. We then present techniques to efficiently search for the zones and to speed up the under-approximate evaluation of those three formulas. Our experiments show that the techniques have significantly enhanced the verification performance against several benchmarks over exact model-checking.
On The Tradeoff Between Two Types of Processing Gain
Venue: arXiv cs.IT 2005
Year: 2005

One of the features characterizing almost every multiple access (MA) communication system is the processing gain. Through the use of spreading sequences, the processing gain of Random CDMA systems (RCDMA), is devoted to both bandwidth expansion and orthogonalization of the signals transmitted by different users. Another type of multiple access system is Impulse Radio (IR). In many aspects, IR systems are similar to time division multiple access (TDMA) systems, and the processing gain of IR systems represents the ratio between the actual transmission time and the total time between two consecutive ransmissions (on-plus-off to on ratio). While CDMA systems, which constantly excite the channel, rely on spreading sequences to orthogonalize the signals transmitted by different users, IR systems transmit a series of short pulses and the orthogonalization between the signals transmitted by different users is achieved by the fact that most of the pulses do not collide with each other at the receiver. In this paper, a general class of MA communication systems that use both types of processing gain is presented, and both IR and RCDMA systems are demonstrated to be two special cases of this more general class of systems. The bit error rate (BER) of several receivers as a function of the ratio between the two types of processing gain is analyzed and compared under the constraint that the total processing gain of the system is large and fixed. It is demonstrated that in non inter-symbol interference (ISI) channels there is no tradeoff between the two types of processing gain. However, in ISI channels a tradeoff between the two types of processing gain exists. In addition, the sub-optimality of RCDMA systems in frequency selective channels is established.
Bandit Problems with Side Observations
Venue: arXiv cs.IT 2005
Year: 2005

An extension of the traditional two-armed bandit problem is considered, in which the decision maker has access to some side information before deciding which arm to pull. At each time t, before making a selection, the decision maker is able to observe a random variable X_t that provides some information on the rewards to be obtained. The focus is on finding uniformly good rules (that minimize the growth rate of the inferior sampling time) and on quantifying how much the additional information helps. Various settings are considered and for each setting, lower bounds on the achievable inferior sampling time are developed and asymptotically optimal adaptive schemes achieving these lower bounds are constructed.