Professional Interests

Theoretical computer science - computational complexity, data structures, combinatorics.

Project EPAC: Efficient approximation algorithms and circuit complexity

Project LBCAD: Lower bounds for combinatorial algorithms and dynamic problems

On-line Publications

Please note that many of the publications below are subject to copyright restrictions but you are free to use such publications for personal use.

On-line Manuscripts, Technical Reports and Thesis

On-line presentations

  • Catalytic Computation. Prague Gathering of Logicians, Prague, 2014.
  • The story of superconcentrators – the missing link. Seventh International Conference on Computability, Complexity and Randomness (CCR 2012), Cambridge, UK, 2012.
  • Are lower bounds hard to prove? Workshop: Synergies in Lower Bounds, Aarhus, 2011.
  • Pseudorandom generators for group products. STOC, San Jose, CA, 2011.
  • A new characterization of ACC0 and probabilistic CC0. Workshop on Circuits, Logic, and Games, Dagstuhl, 2010.
  • Jak se pohybovat v rychle se měnícím světě: Doba pokrytí dynamických grafů. (How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)) STTI, Praha, 2009.
  • Winning concurrent reachability games requires doubly-exponential patience. LICS, Los Angeles, CA, 2009.
  • Amplifying lower bounds by means of self-reducibility. CCC, Washington, DC, 2008. Longer version, Workshop on Computational Complexity of Discrete Problems, Dagstuhl, 2008.
  • High entropy random selection protocols. RANDOM, Princeton, NJ, 2007. Longer version, Tel Aviv, 2007.
  • Circuit complexity of regular languages. CiE, Siena, 2007.
  • Circuit lower bounds via Ehrenfeucht-Fraissé games. CCC, Praha, 2006.
  • Bounded-depth circuits: separating wires from gates. STOC, Baltimore, MD, 2005.


  • Smart Ulist (UserList) for Novell NetWare 3.11+.
  • Hexadecimal file dump.
  • Check out the programming contest problem set archive.