DIMACS logo

Tomas Vyskocil

Hello, I'm a first year PhD student at the Department of Applied Mathematics and the Institute for Theoretical Computer Science, at the Faculty of Mathematics and Physics of Charles University in Prague. I'm interested in combinatorics, graph theory and discrete geometry. In my master thesis I studied several problems concerning topological graphs.

I am working together with Jan Kyncl, Bernard Lidicky, Marek Sterzik, our graduate coordinator Jan Foniok and also with Daniel Kral, who visited us at DIMACS for a period of two weeks.

Our advisors are Michael Saks, Eric Allender and Van H. Vu.

We are working on the following problems:

Logspace and st-reachability

An input of the st-reachability problem is a directed graph G together with a pair of vertices s and t. The goal is to determine if s and t are connected by a directed path in G.

L (logspace) is the class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input, n. (The input itself is not counted as part of the memory.) The class NL is a non-deterministic version of L.

It is known that st-reachability is a complete problem for NL, whereas the undirected version lies in L. We are trying to improve the complexity bounds on some related problems, for example the planar st-reachability, where the input is a planar graph, or some special versios of grid graph reachability, where the vertices of the graph are located on the vertices of the square grid and each edge connects only adjacent vertices of the grid.