Nonapproximablity of the Normalized Information Distance (2009)
Terwijn, Sebastiaan A., Torenvliet, Leen, Vitanyi, Paul M. B.
Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved,...
A Post's Program For Complexity Theory (2009)
Jacobo Torán, Harry Buhrman, Leen Torenvliet
Some of the most important and chalenging problems in complexity theory deal with the separation of complexity classes. Apart from the results derived from the hierarchy theorems and some lower...
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, Leen Torenvliet
Let k, n ∈ N and f: {0, 1} n × {0, 1} n → {0, 1}. Assume Alice has x1,..., xk ∈ {0, 1} n, Bob has y1,..., yk ∈ {0, 1} n, and they want to compute f k (x1x2 · · · xk, y1y2 · · · yk) =...
Sparse Selfreducible Sets and Polynomial Size Circuit (2008)
Lower Bounds, Harry Buhrman, Leen Torenvliet
Abstract. It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely...
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is an k(n)-enumerator if for every input x of length n, h(x) is...
Table of Contents Preface.......................................................... V (2008)
S. Barry Cooper, Benedikt Löwe, Leen Torenvliet, Jose L. Balcázar
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates
The Malleability of TSP 2Opt (2007)
Sophie Fischer, Leen Torenvliet
We prove that the local search optimization problem TSP2Opt|though not known to be PLS-complete|shares an important infeasibility property with other PLS-complete sets. 1
The Communication Complexity of Enumeration, Elimination, and Selection (2007)
Andris Ambainis Univ, Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, Leen Torenvliet, ...
Let f : {0, 1} n {0, 1} n # {0, 1}. Assume Alice has x 1 , . . . , x k # {0, 1} n , Bob has y 1 , . . . , y k # {0, 1} n , and they want to compute f(x 1 , y 1 ) f(x k , y k ) communicating as few...
Harry Buhrman, Steven Homer, Leen Torenvliet
We demonstrate differences between reducibilities and corresponding completeness notions for nondeterministic time and space classes. For time classes the studied completeness notions under...
the Netherlands TWO MODELS FOR THE RECONSTRUCTION PROBLEM FOR DYNAMIC DATA STRUCTURES* (2007)
Leen Torenvliet, Leen Torenvliet, Leen Torenvlietl, ...
Two models for the reconstruction problem for dynamic data structures
THE RECONSTRUCTION OF DYNAMIC DATA STRUCTURES (2007)
Michiel Smid, Mark Overmars, Vakgroep Informatica, Leen Torenvliet, Leen Torenvliet, ...
dynamic data structures
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, Leen Torenvliet
N and f: {0,
Richard Beigel, Harry Buhrman, Lance Fortnow, Leen Torenvliet
We consider the hardness of enumerating k possible values for the Kolmogorov complexity function C(x) so that one of them is correct. We show several results including Any computable enumerator for...
Twenty Questions to a P-selector (2007)
Harry Buhrman, Leen Torenvliet, Peter Emde Boas
We show in this note, that any set that is positive Turing reducible to a p-selective set is in fact many-one reducible to this set. Therefore, such a set is itself p-selective. 1
Nondeterminism, Fairness and a Fundamental Analogy (2007)
In this note we propose a model for unbounded nondeterministic computation which provides a very natural basis for the structural analogy between recursive function theory and computational...
Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract) (2007)
Sophie Fischer, Lane Hemaspaandra, Leen Torenvliet
? ) Sophie Fischer, 1 Lane Hemaspaandra, 2 and Leen Torenvliet 1 1 University of Amsterdam, Department of Computer Science, Plantage Muidergracht 24, 1018 TV Amsterdam. Supported (in part) by grants...
A Note on Time and Space (2007)
In this paper we show that single-tape nondeterministic time T (n) bounded Turing Machines can be simulated on single-tape nondeterministic p T (n) space-bounded Turing Machines in time T (n). 0.1...
Sebastiaan A. Terwijn, Leen Torenvliet
. We develop arithmetical measure theory along the lines of Lutz [10]. This yields the same notion of "measure 0 set" as considered before by Martin-Lof, Schnorr, and others. We prove that...
Two Oracles that Force a Big Crunch (2007)
Harry Buhrman, Stephen Fenner, Lance Fortnow, Leen Torenvliet
We construct an oracle A such that NEXP . The construction of this oracle answers a long standing open question rst posed by Heller, and unsuccessfully attacked many times since. For the rst...
Harry Buhrman, Benjamin Hescott, Steven Homer, Leen Torenvliet
Reductions and completeness notions form the heart of computational complexity theory. Recently non-uniform reductions have been naturally introduced in a variety of settings concerning completeness...
Enumerations of the Kolmogorov function (2006)
Beigel, Richard, Buhrman, Harry, Fejer, Peter, Fortnow, Lance, Grabowski, Piotr, Longpré, Luc, ...
A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is a k(n)-enumerator if for every input x of length n, h(x) is among...
P-Selectivity, Immunity, and the Power of One Bit (2005)
Hemaspaandra, Lane A., Torenvliet, Leen
We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset, but we also prove...
P-Selectivity, Immunity, and the Power of One Bit (2005)
Hemaspaandra, Lane A., Torenvliet, Leen
We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset, but we also prove...
Separating complexity classes using structural properties (2004)
Harry Buhrman, Leen Torenvliet
We study the robustness of complete sets for various complexity classes. A complete set A is robust if for any f(n)-dense set S ∈ P, A − S is still complete, where f(n) ranges from log(n),...
Harry Buhrman, Leen Torenvliet
We study the set of incompressible strings for various resource bounded versions of Kolmogorov complexity. The resource bounded versions of Kolmogorov complexity we study are: polynomial time CD...
The Communication Complexity of Enumeration, Elimination, and Selection (2000)
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, Leen Torenvliet
Let k, n # N and f : {0, 1} n {0, 1} n # {0, 1}. Assume Alice has x 1 , . . . , x k # {0, 1} n , Bob has y 1 , . . . , y k # {0, 1} n , and they want to compute f(x 1 , y 1 ) f(x k , y k )...
Two Oracles that Force a Big Crunch (1999)
Harry Buhrman, Stephen Fenner, Lance Fortnow, Leen Torenvliet
The central theme of this paper is the construction of an oracle A such that NEXP A = P NP A . The construction of this oracle answers a long standing open question rst posed by Heller, and...
Separating complexity classes using autoreducibility (1998)
Buhrman, Harry, Fortnow, Lance, Torenvliet, Leen, Van Melkebeek, Dieter
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman Cwi, Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman Cwi, Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Complicated Complementations (1998)
Harry Buhrman, Leen Torenvliet
Kolmogorov complexity has proven to be a very useful tool in simplifying and improving proofs that use complicated combinatorial arguments. In this paper we use Kolmogorov complexity for oracle...
Harry Buhrman, Leen Torenvliet
We study the set of incompressible strings for various resource bounded versions of Kolmogorov complexity. The resource bounded versions of Kolmogorov complexity we study are: polynomial time CD...
Complete Sets and Structure in Subrecursive Classes (1998)
Harry Buhrman, Leen Torenvliet
In this expository paper, we investigate the structure of complexity classes and the structure of complete sets therein. We give an overview of recent results on both set structure and class...
Sebastiaan A. Terwijn, Leen Torenvliet
Abstract. We develop arithmetical measure theory along the lines of Lutz [10]. This yields the same notion of “measure 0 set ” as considered before by Martin-Löf, Schnorr, and others. We prove...
Six Hypotheses in Search of a Theorem (1997)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
We consider the following six hypotheses: ffl P = NP. ffl SAT is truth-table reducible to a P-selective set. ffl SAT is truth-table reducible to a k- approximable set for some k. ffl FP NP jj = FP...
Witness-Isomorphic Reductions and Local Search (1997)
Sophie Fischer, Lane Hemaspaandra, Leen Torenvliet
We study witness-isomorphic reductions, a type of structurepreserving reduction between NP decision problems. We completely determine the relative power of the different models of witnessisomorphic...
Witness-Isomorphic Reductions and Local Search (1996)
Fischer, Sophie, Hemaspaandra, Lane A., Torenvliet, Leen
We study witness-isomorphic reductions, a type of structure-preserving reduction between NP decision problems. We completely determine the relative power of the different models of witness-isomorphic...
P-selective Self-reducible sets: A New Characterization of P (1996)
Harry Buhrman, Leen Torenvliet
We show that any p-selective and self-reducible set is in P . As the converse is also true, we obtain a new characterization of the class P . A generalization and several consequences of this theorem...
P-selective Self-reducible sets: A New Characterization of (1996)
Harry Buhrman, Leen Torenvliet
We show that any p-selective and self-reducible set is in P . As the converse is also true, we obtain a new characterization of the class P . A generalization and several consequences of this theorem...
Witness-Isomorphic Reductions and Local Search (1996)
Sophie Fischer, Lane Hemaspaandra, Leen Torenvliet
We study witness-isomorphic reductions, a type of structurepreserving reduction between NP decision problems. We completely determine the relative power of the different models of witnessisomorphic...
A Note on the Complexity of Restricted Attribute-Value Grammars (1995)
Torenvliet, Leen, Trautwein, Marten
The recognition problem for attribute-value grammars (AVGs) was shown to be undecidable by Johnson in 1988. Therefore, the general form of AVGs is of no practical use. In this paper we study a very...
The Malleability of TSP 2Opt (1995)
Sophie Fischer, Leen Torenvliet
We prove that the local search optimization problem TSP 2Opt ---though not known to be PLS-complete---shares an important infeasibility property with other PLS-complete sets. 1 Introduction NP...
A Note on the Complexity of Restricted Attribute-Value Grammars (1995)
Leen Torenvliet, Marten Trautwein
The recognition problem for attribute-value grammars(AVGs) was shown to be undecidable by Johnson in 1988. Therefore, the general form of AVGs is of no practical use. In this paper we study a very...
Using Autoreducibility to Separate Complexity Classes (1995)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
A language is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate exponential space from doubly...
Using Autoreducibility to Separate Complexity Classes (1995)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
A language is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate exponential space from doubly...
Semi-Membership Algorithms: Some Recent Advances (1994)
Denny-Brown, Derek, Han, Yenjo, Hemaspaandra, Lane A., Torenvliet, Leen
A semi-membership algorithm for a set A is, informally, a program that when given any two strings determines which is logically more likely to be in A. A flurry of interest in this topic in the late...
Hemaspaandra, Lane A., Torenvliet, Leen
Ko [1983] proved that the P-selective sets are in the advice class P/quadratic. We prove that the P-selective sets are in NP/linear \cap coNP/linear. We show this to be optimal in terms of the amount...
Lane A. Hemaspaandra, Leen Torenvliet
Ko [Ko83] proved that the P-selective sets are in the advice class P/quadratic. We prove that the P-selective sets are in NP=linear T coNP=linear. We show this to be optimal in terms of the amount of...
On the Cutting Edge of Relativization: The Resource Bounded Injury Method (1994)
Harry Buhrman, Leen Torenvliet
In this report we present a new method of diagonalization that is a refinement of the well-known finite injury priority method discovered independently by Friedberg and Muchnik in 1957. In the...
On the Structure of Complete Sets (1994)
Harry Buhrman Leen, Harry Buhrman, Leen Torenvliet
The many types of resource bounded reductions that are both object of study and research tool in structural complexity theory have given rise to a large variety of completeness notions. A complete...
Semi-Membership Algorithms: Some Recent Advances (1994)
Derek Denny-brown, Yenjo Han, Lane A. Hemaspaandra, Leen Torenvliet
A semi-membership algorithm for a set A is, informally, a program that when given any two strings determines which is logically more likely to be in A. A flurry of interest in this topic in the late...
On the Structure of Complete Sets (1994)
Harry Buhrman, Leen Torenvliet
The many types of resource bounded reductions that are both object of study and research tool in structural complexity theory have given rise to a large variety of completeness notions. A complete...
On the Cutting Edge of Relativization: The Resource Bounded Injury Method (1994)
Harry Buhrman, Pau Gargallo, Leen Torenvliet
In this paper we construct an oracle A such that NEXP A ` P NP A . For the construction of this oracle we present a new variation on the finite injury priority method that we call the resource...
Twenty Questions to a P-selector (1994)
Harry Buhrman, Leen Torenvliet
We show in this note, that any set that is positive Turing reducible to a p-selective set is in fact many-one reducible to this set. Therefore, such a set is itself p-selective. 1 Introduction...
Lane A. Hemaspaandra, Leen Torenvliet
Ko proved that the P-selective sets are in the advice class P=quadratic, and Hemaspaandra, Naik, Ogihara, and Selman showed that they are in PP=linear. We strengthen the latter result by establishing...
Splittings, Robustness and Structure of Complete Sets (1993)
Harry Buhrman, Albrecht Hoene, Leen Torenvliet
We investigate the structure of EXP and NEXP complete and hard sets under various kinds of reductions. In particular, we are interested in the way in which information that makes the set complete is...
Harry Buhrman Edith, Edith Spaan, Leen Torenvliet
We study properties of resource-- and otherwise bounded reductions and corresponding completeness notions on nondeterministic time classes which contain exponential time. As it turns out, most of...
Splittings, Robustness and Structure of Complete Sets (1993)
Harry Buhrman, Albrecht Hoene, Leen Torenvliet
We investigate the structure of EXP and NEXP complete and hard sets under various kinds of reductions. In particular, we are interested in the way in which information that makes the set complete is...
Harry Buhrman, Edith Spaan, Leen Torenvliet
We study properties of resource-- and otherwise bounded reductions and corresponding completeness notions on nondeterministic time classes which contain exponential time. As it turns out, most of...
A parallel functional implementation of range queries (1989)
Hartel, Pieter H., Smid, Michiel H.M., Torenvliet, Leen, Vree, Wilem G.
The Relative Power Of Logspace And Polynomial Time Reductions
Harry Buhrman, Edith Spaan, Leen Torenvliet
. There exist many different formalisms to model the notion of resource bounded `truth-table' reduction. Most papers in which truthtable reductions appear refer to the seminal paper of Ladner,...
A Note on the Complexity of Restricted Attribute-Value Grammars
Leen Torenvliet, Marten Trautwein
The recognition problem for attribute-value grammars(AVGs) was shown to be undecidable by Johnson in 1988. Therefore, the general form of AVGs is of no practical use. In this paper we study a very...
The Relative Power Of Logspace And Polynomial Time Reductions
Harry Buhrman, Edith Spaan, Leen Torenvliet
. There exist many different formalisms to model the notion of resource bounded `truth-table' reduction. Most papers in which truthtable reductions appear refer to the seminal paper of Ladner,...