Juraj Hromkovič - Major publications#

1. Hromkovič, J.: Algorithmic Adventures. From Knowledge to Magic, Springer 2008.

2. Hromkovič, J. - Klasing, R. - Pelc, A. - Ruzicka, P. - Unger, W.: Dissemination of Information in Communication Networks. Broadcasting, Gossiping, Leader Election, Fault-Tolerance, Springer-Verlag 2005, ISBN 3-540-00846-2, 361p. .

3. Hromkovič, J.: Algorithmics for Hard Problems (Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics), Springer-Verlag 2001, ISBN 3-540-66860-8, 492p. (Appeared in further editions in 2002 and 2004, and in Japanese in 2005)

4. Hromkovič, J.: Communication Complexity and Parallel Computing. Texts in Theoretical Computer Science - An EATCS Series, Springer-Verlag, ISBN 3-540-57459-X , 336p. (Also appeared as a special edition for the People’s Republic of China)

5. Hromkovič, J.: Communication Protocols - An Exemplary Study of the Power of Randomness. In: Handbook on Randomized Computing, Chapter 14, P.Pardalos, S.Rajasekaran, J.Reif, J.Rolim, Eds., Kluwer Publ. 2001, Vol.2, ISBN 0-7923-6959-9, pp. 533-596.

6. Hromkovič, J. - Klasing, R. - Monien, B. - Peine, R.: Dissemination of Information in Interconnection Networks (Broadcasting and Cossiping). In: Combinatorial Network Theory, Eds: Frank Hsu, Ding-Zhu Du, 1995 Kluwer Academic Publishers, ISBN 0-7923-3777-8, pp. 125-212.

7. Bockenhauer H.J., Hromkovic J., Klasing R., et al.: Approximation algorithms for the TSP with sharpened triangle inequality. Information Processing Letters, Vol. 75, 3, pp. 133-138 (2000).

8. Hromkovič, J.: On the Power of Alternation in Automata Theory. Journal of Computer and System Sciences, Vol. 31, 1, pp.28-39 (1985).

9. Hromkovič,J., Schnitger,G.: Nondeterministic communication with a limited number of advice bits. SIAM Journal on Computing 33 (2003), No.1, 43-68; Preliminary version in AMS STOC96.

10. Hromkovič,J., Seibert,S., Wilke,T.: Translating regular expressions into small -free nondeterministic finite automata. Journal of Computer and System Sciences 62 (2001), 565-588; Preliminary version in STACS97. (Cited altogether 46 times in ISI web of science.)

11. Hromkovič,J., Georg Schnitger; Ambiguity and Communication. STACS 2009, 553-564 (Solves a problem that was open for 30 years. Shows that there is an exponential gap in the size between NFAs with constant ambiguity and NFAs with polynomial ambiguity with a completely new technique)

12. Hromkovič,J., Georg Schnitger; Comparing the size of NFAs with and without epsilon-transitions. Theor. Comput. Sci. 380, (1-2): 100-114 (2007) (Also solves a 30 year old problem)

13. Juraj Hromkovič, Georg Schnitger : Ambiguity and Communication. STACS 2009 (This solves a 30 year old problem: exponential gap in the size between NFAs with constant ambiguity and NFAs polynomial ambiguity with a new technique)