Search results for "Theoretical Computer Science"

On finding common neighborhoods in massive graphs

2003

AbstractWe consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We prove lower bounds on the resources needed to solve this problem on resource-bounded models of computation. In streaming models, in which algorithms can access the input only a constant number of times and only sequentially, we show that, even with randomization, any algorithm that determines if there exists any pair of vertices with a large common neighborhood must essentially store and process the input graph off line. In sampling models, in which algorithms can only query an oracle for the common neighborhoods of specified vertex pairs, we show that any algorithm must …

On Fine and Wilf's theorem for bidimensional words

2003

AbstractGeneralizations of Fine and Wilf's Periodicity Theorem are obtained for the case of bidimensional words using geometric arguments. The domains considered constitute a large class of convex subsets of R2 which include most parallelograms. A complete discussion is provided for the parallelogram case.

Two shortest path metrics on well-formed parentheses strings

1996

We present an analysis of two transformations on well-formed parentheses strings. Using a lattice approach, the corresponding least-move distances are computable, the first in linear time and the second in quadratic time.

A generalization of Sardinas and Patterson's algorithm to z-codes

1993

Abstract This paper concerns the framework of z-codes theory. The main contribution consists in an extension of the algorithm of Sardinas and Patterson for deciding whether a finite set of words X is a z-code. To improve the efficiency of this test we have found a tight upper bound on the length of the shortest words that might have a double z-factorization over X. Some remarks on the complexity of the algorithm are also given. Moreover, a slight modification of this algorithm allows us to compute the z-deciphering delay of X.

Closedness properties in ex-identification

2001

In this paper we investigate in which cases unions of identifiable classes are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Though not closed under the set union, these identification types still have features resembling closedness. For each of them we and n such that (1) if every union of n − 1 classes out of U1, ... , Un is identifiable, so is the union of all n classes; (2) there are classes U1, ... ,Un−1 such that every union of n−2 classes out of them is identifiable, while the union of n − 1 classes is not. We show that by finding these n we can distinguish which requirements put on the identifiability of unions of cl…

On embedding Boolean as a subtype of integer

1990

Learning with belief levels

2008

AbstractWe study learning of predicate logics formulas from “elementary facts,” i.e. from the values of the predicates in the given model. Several models of learning are considered, but most of our attention is paid to learning with belief levels. We propose an axiom system which describes what we consider to be a human scientist's natural behavior when trying to explore these elementary facts. It is proved that no such system can be complete. However we believe that our axiom system is “practically” complete. Theorems presented in the paper in some sense confirm our hypothesis.

On the inductive inference of recursive real-valued functions

1999

AbstractWe combine traditional studies of inductive inference and classical continuous mathematics to produce a study of learning real-valued functions. We consider two possible ways to model the learning by example of functions with domain and range the real numbers. The first approach considers functions as represented by computable analytic functions. The second considers arbitrary computable functions of recursive real numbers. In each case we find natural examples of learnable classes of functions and unlearnable classes of functions.

Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms

2005

The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.

Counting by Statistics on Search Trees: Application to Constraint Satisfaction Problems

1997

In 1975, Knuth proposed a simple statistical method for investigating search trees. We use this technique for estimating the number of solutions of constraint satisfaction problem CSP and boolean satisfiability problem SAT instances. We show that, depending on domain reductions, tree-based estimates have a lower variance than estimates based on uniform sampling from the search space. Nevertheless, because the variance remains extremely high in the general case, a confidence interval cannot be derived, but a lower bound of the number of solutions. These results are confirmed by many experiments.