OpenRaiser/Intern-Atlas huggingface dataset:
Increasing Evolvability Considered as a Large-Scale Trend in Evolution
Venue: arXiv cs.NE 2002
Year: 2002

Evolvability is the capacity to evolve. This paper introduces a simple computational model of evolvability and demonstrates that, under certain conditions, evolvability can increase indefinitely, even when there is no direct selection for evolvability. The model shows that increasing evolvability implies an accelerating evolutionary pace. It is suggested that the conditions for indefinitely increasing evolvability are satisfied in biological and cultural evolution. We claim that increasing evolvability is a large-scale trend in evolution. This hypothesis leads to testable predictions about biological and cultural evolution.
Improving the Functionality of UDDI Registries through Web Service Semantics
Venue: arXiv cs.DB 2002
Year: 2002

In this paper we describe a framework for exploiting the semantics of Web services through UDDI registries. As a part of this framework, we extend the DAML-S upper ontology to describe the functionality we find essential for e-businesses. This functionality includes relating the services with electronic catalogs, describing the complementary services and finding services according to the properties of products or services. Once the semantics is defined, there is a need for a mechanism in the service registry to relate it with the service advertised. The ontology model developed is general enough to be used with any service registry. However when it comes to relating the semantics with services advertised, the capabilities provided by the registry effects how this is achieved. We demonstrate how to integrate the described service semantics to UDDI registries.
Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement
Venue: arXiv cs.CC 2003
Year: 2003

This paper gives the first formal treatment of a quantum analogue of multi-prover interactive proof systems. It is proved that the class of languages having quantum multi-prover interactive proof systems is necessarily contained in NEXP, under the assumption that provers are allowed to share at most polynomially many prior-entangled qubits. This implies that, in particular, if provers do not share any prior entanglement with each other, the class of languages having quantum multi-prover interactive proof systems is equal to NEXP. Related to these, it is shown that, in the case a prover does not have his private qubits, the class of languages having quantum single-prover interactive proof systems is also equal to NEXP.
Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time
Venue: arXiv cs.DS 2003
Year: 2003

We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.
Towards practical meta-querying
Venue: arXiv cs.DB 2003
Year: 2003

We describe a meta-querying system for databases containing queries in addition to ordinary data. In the context of such databases, a meta-query is a query about queries. Representing stored queries in XML, and using the standard XML manipulation language XSLT as a sublanguage, we show that just a few features need to be added to SQL to turn it into a fully-fledged meta-query language. The good news is that these features can be directly supported by extensible database technology.
When to Update the sequential patterns of stream data?
Venue: arXiv cs.DB 2003
Year: 2003

In this paper, we first define a difference measure between the old and new sequential patterns of stream data, which is proved to be a distance. Then we propose an experimental method, called TPD (Tradeoff between Performance and Difference), to decide when to update the sequential patterns of stream data by making a tradeoff between the performance of increasingly updating algorithms and the difference of sequential patterns. The experiments for the incremental updating algorithm IUS on two data sets show that generally, as the size of incremental windows grows, the values of the speedup and the values of the difference will decrease and increase respectively. It is also shown experimentally that the incremental ratio determined by the TPD method does not monotonically increase or decrease but changes in a range between 20 and 30 percentage for the IUS algorithm.
A Framework for Datatype Transformation
Venue: arXiv cs.PL 2003
Year: 2003

We study one dimension in program evolution, namely the evolution of the datatype declarations in a program. To this end, a suite of basic transformation operators is designed. We cover structure-preserving refactorings, but also structure-extending and -reducing adaptations. Both the object programs that are subject to datatype transformations, and the meta programs that encode datatype transformations are functional programs.
Eternity variables to prove simulation of specifications
Venue: arXiv cs.DC 2003
Year: 2003

Simulations of specifications are introduced as a unification and generalization of refinement mappings, history variables, forward simulations, prophecy variables, and backward simulations. A specification implements another specification if and only if there is a simulation from the first one to the second one that satisfies a certain condition. By adding stutterings, the formalism allows that the concrete behaviours take more (or possibly less) steps than the abstract ones. Eternity variables are introduced as a more powerful alternative for prophecy variables and backward simulations. This formalism is semantically complete: every simulation that preserves quiescence is a composition of a forward simulation, an extension with eternity variables, and a refinement mapping. This result does not need finite invisible nondeterminism and machine closure as in the Abadi-Lamport Theorem. Internal continuity is weakened to preservation of quiescence.
Practical and Robust Stenciled Shadow Volumes for Hardware-Accelerated Rendering
Venue: arXiv cs.GR 2003
Year: 2003

Twenty-five years ago, Crow published the shadow volume approach for determining shadowed regions in a scene. A decade ago, Heidmann described a hardware-accelerated stencil buffer-based shadow volume algorithm. Unfortunately hardware-accelerated stenciled shadow volume techniques have not been widely adopted by 3D games and applications due in large part to the lack of robustness of described techniques. This situation persists despite widely available hardware support. Specifically what has been lacking is a technique that robustly handles various "hard" situations created by near or far plane clipping of shadow volumes. We describe a robust, artifact-free technique for hardware-accelerated rendering of stenciled shadow volumes. Assuming existing hardware, we resolve the issues otherwise caused by shadow volume near and far plane clipping through a combination of (1) placing the conventional far clip plane "at infinity", (2) rasterization with infinite shadow volume polygons via homogeneous coordinates, and (3) adopting a zfail stencil-testing scheme. Depth clamping, a new rasterization feature provided by NVIDIA's GeForce3, preserves existing depth precision by not requiring the far plane to be placed at infinity. We also propose two-sided stencil testing to improve the efficiency of rendering stenciled shadow volumes.
Kalman filter control in the reinforcement learning framework
Venue: arXiv cs.LG 2003
Year: 2003

There is a growing interest in using Kalman-filter models in brain modelling. In turn, it is of considerable importance to make Kalman-filters amenable for reinforcement learning. In the usual formulation of optimal control it is computed off-line by solving a backward recursion. In this technical note we show that slight modification of the linear-quadratic-Gaussian Kalman-filter model allows the on-line estimation of optimal control and makes the bridge to reinforcement learning. Moreover, the learning rule for value estimation assumes a Hebbian form weighted by the error of the value estimation.
Open Network Handles Implemented in DNS
Venue: arXiv cs.NI 2003
Year: 2003

An Open Network Handle System (ONHS) provides an intermediate level of service between IP numbers and domain names. A handle adheres permanently to an owner, who may assign and reassign it to different addresses at will. But a handle is a number, carrying no significance in natural language. Any user desiring a handle may generate one from a public key. This memo describes a simple implementation of an Open Network Handle System using the security extensions to the Domain Name System (DNSSEC).
Hard satisfiable formulas for DPLL-type algorithms
Venue: arXiv cs.CC 2003
Year: 2003

We address lower bounds on the time complexity of algorithms solving the propositional satisfiability problem. Namely, we consider two DPLL-type algorithms, enhanced with the unit clause and pure literal heuristics. Exponential lower bounds for solving satisfiability on provably satisfiable formulas are proven.
Convergence and Loss Bounds for Bayesian Sequence Prediction
Venue: arXiv cs.LG 2003
Year: 2003

The probability of observing $x_t$ at time $t$, given past observations $x_1...x_{t-1}$ can be computed with Bayes' rule if the true generating distribution $μ$ of the sequences $x_1x_2x_3...$ is known. If $μ$ is unknown, but known to belong to a class $M$ one can base ones prediction on the Bayes mix $ξ$ defined as a weighted sum of distributions $ν\in M$. Various convergence results of the mixture posterior $ξ_t$ to the true posterior $μ_t$ are presented. In particular a new (elementary) derivation of the convergence $ξ_t/μ_t\to 1$ is provided, which additionally gives the rate of convergence. A general sequence predictor is allowed to choose an action $y_t$ based on $x_1...x_{t-1}$ and receives loss $\ell_{x_t y_t}$ if $x_t$ is the next symbol of the sequence. No assumptions are made on the structure of $\ell$ (apart from being bounded) and $M$. The Bayes-optimal prediction scheme $Λ_ξ$ based on mixture $ξ$ and the Bayes-optimal informed prediction scheme $Λ_μ$ are defined and the total loss $L_ξ$ of $Λ_ξ$ is bounded in terms of the total loss $L_μ$ of $Λ_μ$. It is shown that $L_ξ$ is bounded for bounded $L_μ$ and $L_ξ/L_μ\to 1$ for $L_μ\to \infty$. Convergence of the instantaneous losses are also proven.
Some remarks on the survey decimation algorithm for K-satisfiability
Venue: arXiv cs.CC 2003
Year: 2003

In this note we study the convergence of the survey decimation algorithm. An analytic formula for the reduction of the complexity during the decimation is derived. The limit of the converge of the algorithm are estimated in the random case: interesting phenomena appear near the boundary of convergence.
Fine-Grain Authorization for Resource Management in the Grid Environment
Venue: arXiv cs.CR 2003
Year: 2003

In this document we describe our work-in-progress for enabling fine-grain authorization of resource management. In particular, we address the needs of Virtual Organizations (VOs) to enforce their own policies in addition to those of the resource owners.
Many Hard Examples in Exact Phase Transitions with Application to Generating Hard Satisfiable Instances
Venue: arXiv cs.CC 2003
Year: 2003

This paper first analyzes the resolution complexity of two random CSP models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the threshold points exactly. By encoding CSPs into CNF formulas, it is proved that almost all instances of Model RB/RD have no tree-like resolution proofs of less than exponential size. Thus, we not only introduce new families of CNF formulas hard for resolution, which is a central task of Proof-Complexity theory, but also propose models with both many hard instances and exact phase transitions. Then, the implications of such models are addressed. It is shown both theoretically and experimentally that an application of Model RB/RD might be in the generation of hard satisfiable instances, which is not only of practical importance but also related to some open problems in cryptography such as generating one-way functions. Subsequently, a further theoretical support for the generation method is shown by establishing exponential lower bounds on the complexity of solving random satisfiable and forced satisfiable instances of RB/RD near the threshold. Finally, conclusions are presented, as well as a detailed comparison of Model RB/RD with the Hamiltonian cycle problem and random 3-SAT, which, respectively, exhibit three different kinds of phase transition behavior in NP-complete problems.
Data Structure for a Time-Based Bandwidth Reservations Problem
Venue: arXiv cs.DS 2003
Year: 2003

We discuss a problem of handling resource reservations. The resource can be reserved for some time, it can be freed or it can be queried what is the largest amount of reserved resource during a time interval. We show that the problem has a lower bound of $Ω(\log n)$ per operation on average and we give a matching upper bound algorithm. Our solution also solves a dynamic version of the related problems of a prefix sum and a partial sum.
The New AI: General & Sound & Relevant for Physics
Venue: arXiv cs.AI 2003
Year: 2003

Most traditional artificial intelligence (AI) systems of the past 50 years are either very limited, or based on heuristics, or both. The new millennium, however, has brought substantial progress in the field of theoretically optimal and practically feasible algorithms for prediction, search, inductive inference based on Occam's razor, problem solving, decision making, and reinforcement learning in environments of a very general type. Since inductive inference is at the heart of all inductive sciences, some of the results are relevant not only for AI and computer science but also for physics, provoking nontraditional predictions based on Zuse's thesis of the computer-generated universe.
Cg in Two Pages
Venue: arXiv cs.GR 2003
Year: 2003

Cg is a language for programming GPUs. This paper describes Cg briefly.
Unsupervised Learning in a Framework of Information Compression by Multiple Alignment, Unification and Search
Venue: arXiv cs.AI 2003
Year: 2003

This paper describes a novel approach to unsupervised learning that has been developed within a framework of "information compression by multiple alignment, unification and search" (ICMAUS), designed to integrate learning with other AI functions such as parsing and production of language, fuzzy pattern recognition, probabilistic and exact forms of reasoning, and others.
Fault-tolerant routing in peer-to-peer systems
Venue: arXiv cs.DS 2003
Year: 2003

We consider the problem of designing an overlay network and routing mechanism that permits finding resources efficiently in a peer-to-peer system. We argue that many existing approaches to this problem can be modeled as the construction of a random graph embedded in a metric space whose points represent resource identifiers, where the probability of a connection between two nodes depends only on the distance between them in the metric space. We study the performance of a peer-to-peer system where nodes are embedded at grid points in a simple metric space: a one-dimensional real line. We prove upper and lower bounds on the message complexity of locating particular resources in such a system, under a variety of assumptions about failures of either nodes or the connections between them. Our lower bounds in particular show that the use of inverse power-law distributions in routing, as suggested by Kleinberg (1999), is close to optimal. We also give efficient heuristics to dynamically maintain such a system as new nodes arrive and old nodes depart. Finally, we give experimental results that suggest promising directions for future work.
Hidden Polynomial(s) Cryptosystems
Venue: arXiv cs.CR 2003
Year: 2003

We propose variations of the class of hidden monomial cryptosystems in order to make it resistant to all known attacks. We use identities built upon a single bivariate polynomial equation with coefficients in a finite field. Indeed, it can be replaced by a ``small'' ideal, as well. Throughout, we set up probabilistic encryption protocols, too. The same ideas extend to digital signature algorithms, as well. Our schemes work as well on differential fields of positive characteristic, and elsewhere.
About compression of vocabulary in computer oriented languages
Venue: arXiv cs.CL 2003
Year: 2003

The author uses the entropy of the ideal Bose-Einstein gas to minimize losses in computer-oriented languages.
Techniques and Applications of Computation Slicing
Venue: arXiv cs.DC 2003
Year: 2003

Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems, especially those employed in safety-critical environments, should be able to operate properly even in the presence of software faults. Monitoring the execution of a distributed system, and, on detecting a fault, initiating the appropriate corrective action is an important way to tolerate such faults. This gives rise to the predicate detection problem which requires finding a consistent cut of a given computation that satisfies a given global predicate, if it exists. Detecting a predicate in a computation is, however, an NP-complete problem. To ameliorate the associated combinatorial explosion problem, we introduce the notion of computation slice. Formally, the slice of a computation with respect to a predicate is a (sub)computation with the least number of consistent cuts that contains all consistent cuts of the computation satisfying the predicate. To detect a predicate, rather than searching the state-space of the computation, it is much more efficient to search the state-space of the slice. We prove that the slice exists and is uniquely defined for all predicates. We present efficient slicing algorithms for several useful classes of predicates. We develop efficient heuristic algorithms for computing an approximate slice for predicates for which computing the slice is otherwise provably intractable. Our experimental results show that slicing can lead to an exponential improvement over existing techniques for predicate detection in terms of time and space.
Statistical efficiency of curve fitting algorithms
Venue: arXiv cs.CV 2003
Year: 2003

We study the problem of fitting parametrized curves to noisy data. Under certain assumptions (known as Cartesian and radial functional models), we derive asymptotic expressions for the bias and the covariance matrix of the parameter estimates. We also extend Kanatani's version of the Cramer-Rao lower bound, which he proved for unbiased estimates only, to more general estimates that include many popular algorithms (most notably, the orthogonal least squares and algebraic fits). We then show that the gradient-weighted algebraic fit is statistically efficient and describe all other statistically efficient algebraic fits.
An Effective Decision Procedure for Linear Arithmetic with Integer and Real Variables
Venue: arXiv cs.LO 2003
Year: 2003

This paper considers finite-automata based algorithms for handling linear arithmetic with both real and integer variables. Previous work has shown that this theory can be dealt with by using finite automata on infinite words, but this involves some difficult and delicate to implement algorithms. The contribution of this paper is to show, using topological arguments, that only a restricted class of automata on infinite words are necessary for handling real and integer linear arithmetic. This allows the use of substantially simpler algorithms, which have been successfully implemented.
Conferences with Internet Web-Casting as Binding Events in a Global Brain: Example Data From Complexity Digest
Venue: arXiv cs.NI 2003
Year: 2003

There is likeness of the Internet to human brains which has led to the metaphor of the world-wide computer network as a `Global Brain'. We consider conferences as 'binding events' in the Global Brain that can lead to metacognitive structures on a global scale. One of the critical factors for that phenomenon to happen (similar to the biological brain) are the time-scales characteristic for the information exchange. In an electronic newsletter- the Complexity Digest (ComDig) we include webcasting of audio (mp3) and video (asf) files from international conferences in the weekly ComDig issues. Here we present the time variation of the weekly rate of accesses to the conference files. From those empirical data it appears that the characteristic time-scales related to access of web-casting files is of the order of a few weeks. This is at least an order of magnitude shorter than the characteristic time-scales of peer reviewed publications and conference proceedings. We predict that this observation will have profound implications on the nature of future conference proceedings, presumably in electronic form.
Design Guidelines for Landmarks to Support Navigation in Virtual Environments
Venue: arXiv cs.HC 2003
Year: 2003

Unfamiliar, large-scale virtual environments are difficult to navigate. This paper presents design guidelines to ease navigation in such virtual environments. The guidelines presented here focus on the design and placement of landmarks in virtual environments. Moreover, the guidelines are based primarily on the extensive empirical literature on navigation in the real world. A rationale for this approach is provided by the similarities between navigational behavior in real and virtual environments.
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
Venue: arXiv cs.CC 2003
Year: 2003

Given a $k$-uniform hyper-graph, the E$k$-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier. This enables us to prove that E$k$-Vertex-Cover is NP-hard to approximate within factor $(k-1-ε)$ for any $k \geq 3$ and any $ε>0$. The result is essentially tight as this problem can be easily approximated within factor $k$. Our construction makes use of the biased Long-Code and is analyzed using combinatorial properties of $s$-wise $t$-intersecting families of subsets.
Grid-Enabling Natural Language Engineering By Stealth
Venue: arXiv cs.DC 2003
Year: 2003

We describe a proposal for an extensible, component-based software architecture for natural language engineering applications. Our model leverages existing linguistic resource description and discovery mechanisms based on extended Dublin Core metadata. In addition, the application design is flexible, allowing disparate components to be combined to suit the overall application functionality. An application specification language provides abstraction from the programming environment and allows ease of interface with computational grids via a broker.