Catálogo de publicaciones - libros

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions. In short, we show that both parts of Q1 and Q2 can be answered with ‘everywhere’, which generalize previous results by Pudlák and Beyersdorff. Regarding Q3, inequivalent canonical pairs tell that the proof systems are not “very similar”, while equivalent, P-inseparable canonical pairs tell that they are not “very different”. We can relate Q4 to the open problem in structural complexity that asks whether unions of disjoint NP-complete sets are NP-complete. This demonstrates a new connection between proof systems, disjoint NP-pairs, and unions of disjoint NP-complete sets.

We study the representations of and Log-space real numbers in this paper. We show that the classes of the and Log-space real numbers under the general left cut representation are among the most expressive representations. On the other hand, although the general left cut representation and the Cauchy function representation have the same expressive power in , the expressive power of the Cauchy function representation is weaker than that of the general left cut representation in if  ≠ . In addition, although the expressive power of the standard left cut representation is weaker than that of the Cauchy function representation in , the expressive powers of these two representations are incomparable in if  ≠ . Similar results hold in Log-space.

The computable enumerability (c.e., for short) is one of the most important notion in computability theory and is regarded as the first weakening of the computability. In this paper, we explore further possible weakening of computable enumerability. By restricting numbers of possible big jumps in an increasing computable sequence of rational numbers which converges to a c.e. real number we introduce the notion of -bounded c.e. reals and then shown that it leads naturally to an Ershov-style hierarchy of c.e. reals. However, the similar idea does not work for c.e. sets. We show that there is a computability gap between computable reals and the reals of c.e. binary expansions.

The last decade witnessed the extensive studies of algorithms for data streams. In this model, the input is given as a sequence of items passing only once or a few times, and we are required to compute (often approximately) some statistical quantity using a small amount of space. While many lower bounds on the space complexity have been proved for various tasks, almost all of them were done by reducing the problems to the cases where the desired statistical quantity is at one extreme end. For example, the lower bound of triangle-approximating was showed by reducing the problem to distinguishing between graphs without triangle and graphs with only one triangle.

However, data in many practical applications are not in the extreme, and/or usually we are interested in computing the statistical quantity only if it is in some range (and otherwise reporting “too large” or “too small”). This paper takes this practical relaxation into account by putting the computed quantity itself into the measure of space complexity. It turns out that all three possible types of dependence of the space complexity on the computed quantity exist: as the quantity goes from one end to the other, the space complexity can goes from max to min, remains at max, or goes to somewhere between.

The computational complexity of counting the number of matchings of size in a given triple set remains open, and it is conjectured that the problem is infeasible. In this paper, we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers and , and a given set of triples and an integer , produces a number in time (5.48 ln (2/)/) such that where is the total number of matchings of size in the triple set . Our algorithm is based on the recent improved color-coding techniques and the Monte-Carlo self-adjusting coverage algorithm developed by Karp and Luby.

The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string in (), where is the length of . Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of ( log log||) and (|| log loglog), with denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences.

The algorithm presented in the present paper does not need to resort to the FFT and yet is asymptotically faster than previously available ones. Specifically, an off-line algorithm is presented taking time (||), which is optimal for finite .

is an information dissemination problem in a connected network, in which one node, called the , disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Once informed, the nodes aid the originator in distributing the message. Finding the minimum broadcast time of a vertex in an arbitrary graph is NP-complete. The problem is solved polynomially only for trees. It is proved that the complexity of the problem of determining the minimum broadcast time of any vertex in an arbitrary tree  = (, ) is ||. In this paper we present an algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph  = (, ) in (||) time. This, combined with the obvious lower bound, gives a (||) solution for the problem of broadcasting in unicyclic graphs. As a byproduct, we also find a broadcast center of the unicyclic graph (a vertex in with the minimum broadcast time).

We revisit the problem in one dimension which we recently introduced at WAOA’06: given a sequence of points on the line, the objective is to partition the points into a minimum number of subsets, each enclosable by a unit interval. We present a new randomized online algorithm that achieves expected competitive ratio 11/6 against oblivious adversaries, improving the previous ratio of 15/8. This immediately leads to improved upper bounds for the problem in two and higher dimensions as well.

There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a time algorithm for finding a dominating set of size at most in a -degenerated graph with vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain as a topological minor, we give an improved algorithm for the problem with running time (()). For graphs which are -minor-free, the running time is further reduced to ((log)). Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs.

For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed and , we show that if an -minor-free graph with vertices contains an induced cycle of size , then such a cycle can be found in () expected time as well as in ( log) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs.

We study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. This is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. We prove that threshold graphs and chain graphs admit such sequences. Based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. Minimum completions and deletions into these classes are NP-hard to compute.