Professional Interests

Curriculum Vitae

On-line Publications

• Amplifying Lower Bounds by Means of Self-Reducibility, (with Eric Allender), in Proc. of the 23rd Annual IEEE Conference on Computational Complexity, 2008, pp. 31-40.
• Randomised Individual Communication Complexity, (with Harry Buhrman, Nikolai K. Vereshchagin), in Proc. of the 23rd Annual IEEE Conference on Computational Complexity, 2008, pp. 321-331.
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs), (with Chen Avin, Zvi Lotker), in Proc. the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, pp. 121-132.
• Many random walks are faster than one, (with Noga Alon, Chen Avin, Gady Kozma, Zvi Lotker, Mark R. Tuttle), in Proc. of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2008, pp. 119-128.
• Inverting Onto Functions and Polynomial Hierarchy (with Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolai K. Vereshchagin), in Proc. of International Computer Science Symposium in Russia, CSR 2007, LNCS 4649, pp. 92-103.
• Circuit Complexity of Regular Languages, invited paper - expository article. Preliminary version appeared in Proceedings of Computation and Logic in the Real World - Third Conference of Computability in Europe, CiE 2007, LNCS 4497.
• Languages with Bounded Multiparty Communication Complexity, (with Arkadev Chattopadhyay, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien), in Proc. of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2007, LNCS 4393, pp. 500-511.
• Circuit Lower Bounds via Ehrenfeucht-Fraisse Games, (with Clemens Lautemann, Sebastian Poloczek, and Denis Thérien), in Proc. of the 21st Annual IEEE Conference on Computational Complexity (CCC), 2006, pp. 190-201.
• Incremental Branching Programs, (with Anna Gál, and Pierre McKenzie), in Proc. of International Computer Science Symposium in Russia, CSR 2006, LNCS 3967, pp. 178-190. Invited to a special issue of selected papers from the conference to appear in Theory of Computing Systems.
• Bounded-depth Circuits: Separating Wires from Gates, (with Pavel Pudlák, Denis Thérien). In Proc. of the 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 257-265.
• What can be efficiently reduced to the K-random strings?, (with Eric Allender, Harry Buhrman), Annals of Pure and Applied Logic, 138 (2006), pp. 2-19. (An earlier version appeared in Proc. 21st International Symposium on Theoretical Aspects of Computer Science (STACS), 2004. Lecture Notes in Computer Science 2996, pp. 584-595.)
• On traversal and exploration sequences, DIMACS Technical Report 2003-41, 2003.
• On traversal sequences, exploration sequences and completeness of Kolmogorov random strings, Ph.D. Thesis, Rutgers University, 2003.
• Derandomization and Distinguishing Complexity, (with Eric Allender, Detlef Ronneburger and Sambuddha Roy), in Proc. of the 18th Annual IEEE Conference on Computational Complexity, 2003.
• Power from Random Strings, (with Eric Allender, Harry Buhrman, Dieter van Melkebeek and Detlef Ronneburger), SIAM Journal on Computing, 35: 1467-1493, 2006. (Preliminary version in Proc. of the 43rd Annual Symposium on Foundations of Computer Science, 2002, pp. 669-678.)
• Space-Time Trade-offs in Counting Hierarchy, (with Eric Allender, Detlef Ronneburger, Sambuddha Roy, and V Vinay) in Proc. 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 295-302. (To appear in Theory of Computer Science.)
• Universal Traversal Sequences with Backtracking, in the special issue of Journal of Computer and System Sciences for CCC 2001, Vol 65, 2002, pp. 717-726. (Extended abstract in Proc. 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 21-26.)
• Universal Traversal Sequences for Cycles of Length O(n^4.03), in the special issue of Theoretical Computer Science for COCOON 2001, Vol 296(1), 2003, pp. 117-144. (Extended abstract in the proceedings of COCOON 2001, LNCS 2108, pp. 11-20, 2001).
• Marking One-Way Multihead Finite Automata, Master Thesis, May 1998, (in Czech)

Miscellaneous