OpenRaiser/Intern-Atlas huggingface dataset:
Byzantine Agreement with Faulty Majority using Bounded Broadcast
Venue: arXiv cs.DC 2003
Year: 2003

Byzantine Agreement introduced in [Pease, Shostak, Lamport, 80] is a widely used building block of reliable distributed protocols. It simulates broadcast despite the presence of faulty parties within the network, traditionally using only private unicast links. Under such conditions, Byzantine Agreement requires more than 2/3 of the parties to be compliant. [Fitzi, Maurer, 00], constructed a Byzantine Agreement protocol for any compliant majority based on an additional primitive allowing transmission to any two parties simultaneously. They proposed a problem of generalizing these results to wider channels and fewer compliant parties. We prove that 2f < kh condition is necessary and sufficient for implementing broadcast with h compliant and f faulty parties using k-cast channels.
On termination of meta-programs
Venue: arXiv cs.PL 2003
Year: 2003

The term {\em meta-programming} refers to the ability of writing programs that have other programs as data and exploit their semantics. The aim of this paper is presenting a methodology allowing us to perform a correct termination analysis for a broad class of practical meta-interpreters, including negation and performing different tasks during the execution. It is based on combining the power of general orderings, used in proving termination of term-rewrite systems and programs, and on the well-known acceptability condition, used in proving termination of logic programs. The methodology establishes a relationship between the ordering needed to prove termination of the interpreted program and the ordering needed to prove termination of the meta-interpreter together with this interpreted program. If such a relationship is established, termination of one of those implies termination of the other one, i.e., the meta-interpreter preserves termination. Among the meta-interpreters that are analysed correctly are a proof trees constructing meta-interpreter, different kinds of tracers and reasoners. To appear without appendix in Theory and Practice of Logic Programming.
Probabilistic analysis of a differential equation for linear programming
Venue: arXiv cs.CC 2003
Year: 2003

In this paper we address the complexity of solving linear programming problems with a set of differential equations that converge to a fixed point that represents the optimal solution. Assuming a probabilistic model, where the inputs are i.i.d. Gaussian variables, we compute the distribution of the convergence rate to the attracting fixed point. Using the framework of Random Matrix Theory, we derive a simple expression for this distribution in the asymptotic limit of large problem size. In this limit, we find that the distribution of the convergence rate is a scaling function, namely it is a function of one variable that is a combination of three parameters: the number of variables, the number of constraints and the convergence rate, rather than a function of these parameters separately. We also estimate numerically the distribution of computation times, namely the time required to reach a vicinity of the attracting fixed point, and find that it is also a scaling function. Using the problem size dependence of the distribution functions, we derive high probability bounds on the convergence rates and on the computation times.
A continuation semantics of interrogatives that accounts for Baker's ambiguity
Venue: arXiv cs.CL 2003
Year: 2003

Wh-phrases in English can appear both raised and in-situ. However, only in-situ wh-phrases can take semantic scope beyond the immediately enclosing clause. I present a denotational semantics of interrogatives that naturally accounts for these two properties. It neither invokes movement or economy, nor posits lexical ambiguity between raised and in-situ occurrences of the same wh-phrase. My analysis is based on the concept of continuations. It uses a novel type system for higher-order continuations to handle wide-scope wh-phrases while remaining strictly compositional. This treatment sheds light on the combinatorics of interrogatives as well as other kinds of so-called A'-movement.
How long is a Proof? - A short note
Venue: arXiv cs.CC 2003
Year: 2003

Withdrawn. Silly notion and out of context.
Independence Properties of Algorithmically Random Sequences
Venue: arXiv cs.CC 2003
Year: 2003

A bounded Kolmogorov-Loveland selection rule is an adaptive strategy for recursively selecting a subsequence of an infinite binary sequence; such a subsequence may be interpreted as the query sequence of a time-bounded Turing machine. In this paper we show that if A is an algorithmically random sequence, A_0 is selected from A via a bounded Kolmogorov-Loveland selection rule, and A_1 denotes the sequence of nonselected bits of A, then A_1 is independent of A_0; that is, A_1 is algorithmically random relative to A_0. This result has been used by Kautz and Miltersen [1] to show that relative to a random oracle, NP does not have p-measure zero (in the sense of Lutz [2]). [1] S. M. Kautz and P. B. Miltersen. Relative to a random oracle, NP is not small. Journal of Computer and System Sciences, 53:235-250, 1996. [2] J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220-258, 1992.
Novel Runtime Systems Support for Adaptive Compositional Modeling on the Grid
Venue: arXiv cs.CE 2003
Year: 2003

Grid infrastructures and computing environments have progressed significantly in the past few years. The vision of truly seamless Grid usage relies on runtime systems support that is cognizant of the operational issues underlying grid computations and, at the same time, is flexible enough to accommodate diverse application scenarios. This paper addresses the twin aspects of Grid infrastructure and application support through a novel combination of two computational technologies: Weaves - a source-language independent parallel runtime compositional framework that operates through reverse-analysis of compiled object files, and runtime recommender systems that aid in dynamic knowledge-based application composition. Domain-specific adaptivity is exploited through a novel compositional system that supports runtime recommendation of code modules and a sophisticated checkpointing and runtime migration solution that can be transparently deployed over Grid infrastructures. A core set of "adaptivity schemas" are provided as templates for adaptive composition of large-scale scientific computations. Implementation issues, motivating application contexts, and preliminary results are described.
Smoothed Analysis of Interior-Point Algorithms: Termination
Venue: arXiv cs.DS 2003
Year: 2003

We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/σ))$. In contrast, the best known bound on the worst-case complexity of linear programming is $O (m^{3} L)$, where $L$ could be as large as $m$. We include an introduction to smoothed analysis and a tutorial on proof techniques that have been useful in smoothed analyses.
PHORMA: Perfectly Hashable Order Restricted Multidimensional Arrays
Venue: arXiv cs.DS 2003
Year: 2003

In this paper we propose a simple and efficient data structure yielding a perfect hashing of quite general arrays. The data structure is named phorma, which is an acronym for perfectly hashable order restricted multidimensional array. Keywords: Perfect hash function, Digraph, Implicit enumeration, Nijenhuis-Wilf combinatorial family.
A semantic framework for preference handling in answer set programming
Venue: arXiv cs.AI 2003
Year: 2003

We provide a semantic framework for preference handling in answer set programming. To this end, we introduce preference preserving consequence operators. The resulting fixpoint characterizations provide us with a uniform semantic framework for characterizing preference handling in existing approaches. Although our approach is extensible to other semantics by means of an alternating fixpoint theory, we focus here on the elaboration of preferences under answer set semantics. Alternatively, we show how these approaches can be characterized by the concept of order preservation. These uniform semantic characterizations provide us with new insights about interrelationships and moreover about ways of implementation.
Double-Negation Elimination in Some Propositional Logics
Venue: arXiv cs.LO 2003
Year: 2003

This article answers two questions (posed in the literature), each concerning the guaranteed existence of proofs free of double negation. A proof is free of double negation if none of its deduced steps contains a term of the form n(n(t)) for some term t, where n denotes negation. The first question asks for conditions on the hypotheses that, if satisfied, guarantee the existence of a double-negation-free proof when the conclusion is free of double negation. The second question asks about the existence of an axiom system for classical propositional calculus whose use, for theorems with a conclusion free of double negation, guarantees the existence of a double-negation-free proof. After giving conditions that answer the first question, we answer the second question by focusing on the Lukasiewicz three-axiom system. We then extend our studies to infinite-valued sentential calculus and to intuitionistic logic and generalize the notion of being double-negation free. The double-negation proofs of interest rely exclusively on the inference rule condensed detachment, a rule that combines modus ponens with an appropriately general rule of substitution. The automated reasoning program OTTER played an indispensable role in this study.
Bounds on the Number of Longest Common Subsequences
Venue: arXiv cs.DM 2003
Year: 2003

This paper performs the analysis necessary to bound the running time of known, efficient algorithms for generating all longest common subsequences. That is, we bound the running time as a function of input size for algorithms with time essentially proportional to the output size. This paper considers both the case of computing all distinct LCSs and the case of computing all LCS embeddings. Also included is an analysis of how much better the efficient algorithms are than the standard method of generating LCS embeddings. A full analysis is carried out with running times measured as a function of the total number of input characters, and much of the analysis is also provided for cases in which the two input sequences are of the same specified length or of two independently specified lengths.
Computing the Number of Longest Common Subsequences
Venue: arXiv cs.DS 2003
Year: 2003

This note provides very simple, efficient algorithms for computing the number of distinct longest common subsequences of two input strings and for computing the number of LCS embeddings.
Smoothed Analysis of Interior-Point Algorithms: Condition Number
Venue: arXiv cs.DS 2003
Year: 2003

We show that the smoothed complexity of the logarithm of Renegar's condition number is O(log (n/sigma)).
Economic and On Demand Brain Activity Analysis on Global Grids
Venue: arXiv cs.DC 2003
Year: 2003

The lack of computational power within an organization for analyzing scientific data, and the distribution of knowledge (by scientists) and technologies (advanced scientific devices) are two major problems commonly observed in scientific disciplines. One such scientific discipline is brain science. The analysis of brain activity data gathered from the MEG (Magnetoencephalography) instrument is an important research topic in medical science since it helps doctors in identifying symptoms of diseases. The data needs to be analyzed exhaustively to efficiently diagnose and analyze brain functions and requires access to large-scale computational resources. The potential platform for solving such resource intensive applications is the Grid. This paper describes a MEG data analysis system developed by us, leveraging Grid technologies, primarily Nimrod-G, Gridbus, and Globus. This paper explains the application of economy-based grid scheduling algorithms to the problem domain for on-demand processing of analysis jobs.
Tight Logic Programs
Venue: arXiv cs.AI 2003
Year: 2003

This note is about the relationship between two theories of negation as failure -- one based on program completion, the other based on stable models, or answer sets. Francois Fages showed that if a logic program satisfies a certain syntactic condition, which is now called ``tightness,'' then its stable models can be characterized as the models of its completion. We extend the definition of tightness and Fages' theorem to programs with nested expressions in the bodies of rules, and study tight logic programs containing the definition of the transitive closure of a predicate.
Glottochronology and problems of protolanguage reconstruction
Venue: arXiv cs.CL 2003
Year: 2003

A method of languages genealogical trees construction is proposed.
The measurements, parameters and construction of Web proxy cache
Venue: arXiv cs.NI 2003
Year: 2003

The aim of this paper is an experimental study of cache systems in order to optimize proxy cache systems and to modernize construction principles. Our investigations lead to the criteria for the optimal use of storage capacity and allow the description of the basic effects of the ratio between construction parts, steady-state performance, optimal size, etc. We want to outline that the results obtained and the plan of the experiment follow from the theoretical model. Special consideration is given to the modification of the key formulas supposed by Wolman at al.
A Neural Network Assembly Memory Model with Maximum-Likelihood Recall and Recognition Properties
Venue: arXiv cs.AI 2003
Year: 2003

It has been shown that a neural network model recently proposed to describe basic memory performance is based on a ternary/binary coding/decoding algorithm which leads to a new neural network assembly memory model (NNAMM) providing maximum-likelihood recall/recognition properties and implying a new memory unit architecture with Hopfield two-layer network, N-channel time gate, auxiliary reference memory, and two nested feedback loops. For the data coding used, conditions are found under which a version of Hopfied network implements maximum-likelihood convolutional decoding algorithm and, simultaneously, linear statistical classifier of arbitrary binary vectors with respect to Hamming distance between vector analyzed and reference vector given. In addition to basic memory performance and etc, the model explicitly describes the dependence on time of memory trace retrieval, gives a possibility of one-trial learning, metamemory simulation, generalized knowledge representation, and distinct description of conscious and unconscious mental processes. It has been shown that an assembly memory unit may be viewed as a model of a smallest inseparable part or an 'atom' of consciousness. Some nontraditional neurobiological backgrounds (dynamic spatiotemporal synchrony, properties of time dependent and error detector neurons, early precise spike firing, etc) and the model's application to solve some interdisciplinary problems from different scientific fields are discussed.
Algorithmic Clustering of Music
Venue: arXiv cs.SD 2003
Year: 2003

We present a fully automatic method for music classification, based only on compression of strings that represent the music pieces. The method uses no background knowledge about music whatsoever: it is completely general and can, without change, be used in different areas like linguistic classification and genomics. It is based on an ideal theory of the information content in individual objects (Kolmogorov complexity), information distance, and a universal similarity metric. Experiments show that the method distinguishes reasonably well between various musical genres and can even cluster pieces by composer.
Recent Results on No-Free-Lunch Theorems for Optimization
Venue: arXiv cs.NE 2003
Year: 2003

The sharpened No-Free-Lunch-theorem (NFL-theorem) states that the performance of all optimization algorithms averaged over any finite set F of functions is equal if and only if F is closed under permutation (c.u.p.) and each target function in F is equally likely. In this paper, we first summarize some consequences of this theorem, which have been proven recently: The average number of evaluations needed to find a desirable (e.g., optimal) solution can be calculated; the number of subsets c.u.p. can be neglected compared to the overall number of possible subsets; and problem classes relevant in practice are not likely to be c.u.p. Second, as the main result, the NFL-theorem is extended. Necessary and sufficient conditions for NFL-results to hold are given for arbitrary, non-uniform distributions of target functions. This yields the most general NFL-theorem for optimization presented so far.
TCTL Inevitability Analysis of Dense-time Systems
Venue: arXiv cs.SC 2003
Year: 2003

Inevitability properties in branching temporal logics are of the syntax forall eventually ϕ, where ϕis an arbitrary (timed) CTL formula. In the sense that "good things will happen", they are parallel to the "liveness" properties in linear temporal logics. Such inevitability properties in dense-time logics can be analyzed with greatest fixpoint calculation. We present algorithms to model-check inevitability properties both with and without requirement of non-Zeno computations. We discuss a technique for early decision on greatest fixpoints in the temporal logics, and experiment with the effect of non-Zeno computations on the evaluation of greatest fixpoints. We also discuss the TCTL subclass with only universal path quantifiers which allows for the safe abstraction analysis of inevitability properties. Finally, we report our implementation and experiments to show the plausibility of our ideas.
Hidden Polynomial(s) Cryptosystems
Venue: arXiv cs.CR 2003
Year: 2003

We propose public-key cryptosystems with public key a system of polynomial equations, algebraic or differential, and private key a single polynomial or a small-size ideal. We set up probabilistic encryption, signature, and signcryption protocols.
Ground Canonicity
Venue: arXiv cs.LO 2003
Year: 2003

We explore how different proof orderings induce different notions of saturation. We relate completion, paramodulation, saturation, redundancy elimination, and rewrite system reduction to proof orderings.
Revolutionary Ideas for Radio Regulation
Venue: arXiv cs.CY 2003
Year: 2003

Radio technology seems destined to become part of the standard micro-processor input/output system. But unlike for memory or display systems, for radio systems government regulation matters a lot. Much discussion of radio regulation has focused on narrow spectrum management and interference issues. Reflecting on historical experience and centuries of conversation about fundamental political choices, persons working with radio technology should also ponder three questions. First, what is a good separation and balance of powers in radio regulation? Second, how should radio regulation be geographically configured? Third, how should radio regulation understand and respect personal freedom and equality? Working out answering to these questions involves a general process of shaping good government. This process will be hugely important for radio regulation, technology, and applications.
Exploiting Sublanguage and Domain Characteristics in a Bootstrapping Approach to Lexicon and Ontology Creation
Venue: arXiv cs.CL 2003
Year: 2003

It is very costly to build up lexical resources and domain ontologies. Especially when confronted with a new application domain lexical gaps and a poor coverage of domain concepts are a problem for the successful exploitation of natural language document analysis systems that need and exploit such knowledge sources. In this paper we report about ongoing experiments with `bootstrapping techniques' for lexicon and ontology creation.
An Approach for Resource Sharing in Multilingual NLP
Venue: arXiv cs.CL 2003
Year: 2003

In this paper we describe an approach for the analysis of documents in German and English with a shared pool of resources. For the analysis of German documents we use a document suite, which supports the user in tasks like information retrieval and information extraction. The core of the document suite is based on our tool XDOC. Now we want to exploit these methods for the analysis of English documents as well. For this aim we need a multilingual presentation format of the resources. These resources must be transformed into an unified format, in which we can set additional information about linguistic characteristics of the language depending on the analyzed documents. In this paper we describe our approach for such an exchange model for multilingual resources based on XML.
$P \ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle
Venue: arXiv cs.CC 2003
Year: 2003

Recent results established exponential lower bounds for the length of any Resolution proof for the weak pigeonhole principle. More formally, it was proved that any Resolution proof for the weak pigeonhole principle, with $n$ holes and any number of pigeons, is of length $Ω(2^{n^ε})$, (for a constant $ε= 1/3$). One corollary is that certain propositional formulations of the statement $P \ne NP$ do not have short Resolution proofs. After a short introduction to the problem of $P \ne NP$ and to the research area of propositional proof complexity, I will discuss the above mentioned lower bounds for the weak pigeonhole principle and the connections to the hardness of proving $P \ne NP$.
On probabilistic analog automata
Venue: arXiv cs.OH 2003
Year: 2003

We consider probabilistic automata on a general state space and study their computational power. The model is based on the concept of language recognition by probabilistic automata due to Rabin and models of analog computation in a noisy environment suggested by Maass and Orponen, and Maass and Sontag. Our main result is a generalization of Rabin's reduction theorem that implies that under very mild conditions, the computational power of the automaton is limited to regular languages.
Hardness of approximating the weight enumerator of a binary linear code
Venue: arXiv cs.CC 2003
Year: 2003

We consider the problem of evaluation of the weight enumerator of a binary linear code. We show that the exact evaluation is hard for polynomial hierarchy. More exactly, if WE is an oracle answering the solution of the evaluation problem then P^WE=P^GapP. Also we consider the approximative evaluation of the weight enumerator. In the case of approximation with additive accuracy $2^{αn}$, $α$ is constant the problem is hard in the above sense. We also prove that approximate evaluation at a single point $e^{πi/4}$ is hard for $0<\al<\al_0\approx0.88$.
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves
Venue: arXiv cs.DS 2003
Year: 2003

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This solves a long-standing open problem, stated explicitly, e.g., in [J.I. Munro and V. Raman, Sorting with minimum data movement, J. Algorithms, 13, 374-93, 1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.