The problems of complexity of almost context-free languages [Abstract of thesis]
The reduction of binary trees by means of an input-restricted deque
The role of rudimentary relations in complexity theory
The size of triangulations supporting a given link.
The Structure and complexity of interactive zero-knowledge proofs
The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification
Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called haplotypes. In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based...
The Union of Balls and Its Dual Shape.
The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.
The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces.
Theorem proving through depth-first test
Threshold circuits for iterated matrix product and powering
Threshold Circuits for Iterated Matrix Product and Powering
The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension matrices with integer or rational entries is studied. We call these two problems and , respectively, for short. We prove that: (i) For , does not belong to , unless .newline (ii) For stochastic matrices : belongs to while, for , does not belong to , unless . (iii) For any k, belongs to .
Tiling Polygons with Parallelograms.
Time and space complexity of reversible pebbling
This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...
Time and space complexity of reversible pebbling
This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...
Topological views on computational complexity.
Tree inclusion problems
Given two trees (a target T and a pattern P) and a natural number w, window embedded subtree problems consist in deciding whether P occurs as an embedded subtree of T and/or finding the number of size (at most) w windows of T which contain pattern P as an embedded subtree. P is an embedded subtree of T if P can be obtained by deleting some nodes from T (if a node v is deleted, all edges adjacent to v are also deleted, and outgoing edges are replaced by edges going from the parent of v (if it exists)...
Treewidth and minimum fill-in on -trapezoid graphs.
Triangulating a Nonconvex Polytope.
Triangulating a Simple Polygon in Linear Time.