- Author:
- Michal Koucky,
- Director:
- Eric Allender
Traversal sequences were defined by Aleliunas et al. (1979) as a tool for the study of undirected s - t -connectivity. In the first part of this thesis we study traversal sequences. We improve on previous results and we present a simple construction of polynomial length universal traversal sequences for 2-regular graphs. These universal traversal sequences are log-space (even NC 1 ) constructible and are of length O ( n 4.03 ).
Further, we introduce a new notion of traversal sequences that we call exploration sequences . Exploration sequences share many properties with the original traversal sequences but they also exhibit some new properties. For instance, they have an ability to backtrack, and their random properties are robust under choice of the probability distribution on labels. We present simple constructions of polynomial length universal exploration sequences for several classes of graphs, e.g., 2-regular graphs, cliques, expanders, trees. These constructions do not obey previously known lower bounds on the length of universal traversal sequences thus, they highlight another difference between exploration and traversal sequences. We also show that universal traversal sequences can be efficiently converted into universal exploration sequences. Further, we show certain self-correcting properties of traversal and exploration sequences and we propose a candidate universal exploration sequence.
In the second part of this thesis we study Kolmogorov complexity, which is a measure of randomness of finite strings, and its resource-bounded variants. We show that sets consisting of strings of high resource-bounded Kolmogorov complexity provide examples of sets that are complete for complexity classes in which they naturally lie under probabilistic and non-uniform reductions whereas they are provably not complete under the usual many-one reductions.
Further, our results imply that under certain intractability assumptions, resource-bounded Kolmogorov complexity of a string as well as circuit size, formula size and branching program size of a Boolean function can not be efficiently approximated.
We also study unbounded Kolmogorov complexity. We show completeness results in that setting and point out certain inconsistencies caused by the usual definition of Kolmogorov complexity. We also consider the problem of deterministically generating a Kolmogorov random string when the set of Kolmogorov random strings is given to us as an oracle.
Cited By
- Disser Y, Hackfeld J and Klimm M Undirected graph exploration with Θ(log log n) pebbles Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, (25-39)
- Reingold O (2008). Undirected connectivity in log-space, Journal of the ACM (JACM), 55:4, (1-24), Online publication date: 1-Sep-2008.
- Reingold O Undirected ST-connectivity in log-space Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, (376-385)
Index Terms
- On traversal sequences, exploration sequences and completeness of kolmogorov random strings
Recommendations
On the Autoreducibility of Random Sequences
A binary sequence $A=A(0)A(1)\ldots$ is called infinitely often (i.o.)~Turing-au\-to\-re\-duc\-ible if $A$~is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either $A(x)$ or a don't-...
Length lower bounds for reflecting sequences and universal traversal sequences
A universal traversal sequence for the family of all connected d -regular graphs of order n with an edge-labeling is a sequence of { 0 , 1 , , d - 1 } that traverses every graph of the family starting at every vertex of the graph. Reflecting sequences ...
-completeness of generalized multi-Skolem sequences
A Skolem sequence is a sequence a 1, a 2,…, a 2 n (where a i ý A ={1,…, n }), each a i occurs exactly twice in the sequence and the two occurrences are exactly a i positions apart. A set A that can be used to construct ...