I am interested in all aspects of computational complexity, including machine-based complexity, communication complexity, models of parallel computation, distributed computation, algorithms, as well as problems inspired by the world wide web.

I am working on complexity theory, and algorithms in diverse subareas: combinatorial algorithms, algorithms in bioinformatics, algorithms for distributed systems, etc.

I am interested in learning about techniques that may provide tools for proving lower bounds.

More or less recent work on combinatorial algorithms includes graph theoretic models of optical networks, in particular the complexity of assigning wavelengths to optical communication paths, and graph problems inspired by the model.

Recent work on distributed algorithms includes algorithms for information distribution in (very idealized) mobile networks. I have a nagging interest in the firing squad problem for cellular automata. I am also interested in error tolerance.

There are interesting combinatorial problems whose solution is of interest to biologists.

I have interests in electronic publishing, and in the uses of the Internet--both the technical problems and the social implications.

Papers Available in Electronic Form

I will try to keep this up to date.

• Analysis of Multi-Hop Emergency Message Propagation in Vehicular Ad Hoc Networks (with Giovanni Resta and Paolo Santi) to appear in MobiHoc 07.
• The Undecidability of the Generalized Collatz Problem (with Stuart Kurtz) in Proceedings of TAMC07 Theory and Applications of Models of Computation (Shanghai, May 2007) LNCS
• Silence is Golden with High Probability: Maintaining a Connected Backbone in Wireless Sensor Networks (with Paolo Santi) in 1st European Workshop on Wireless Sensor Networks (Berlin, Jan 2004) Power Point slides
• Decidable Properties of All-Optical Networks preprint. (with L. Margara). ICALP 2001 Proceedings published in LNCS series by Springer © Springer-Verlag.
• Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link preprint. (with L. Margara). ICALP 2000 Proceedings published in LNCS series by Springer © Springer-Verlag.
• On the Complexity of the Discrete Fourier Transform and Related Linear Transforms", preprint. (with B. Codenotti).
• Active Transport in Biological Computing in 2nd Annual DIMACS Workshop on DNA-based Computers. (with S. Mahaney, J. Royer and S. Kurtz).
• Randomness in Distributed Systems Preliminary version of the paper on the number of random bits needed to break symmetry (with B. Codenotti P. Gemmell and P. Pudlak).
• Biological Computing Final version appeared in Complexity Theory Retrospective II (Hemaspaandra and Selman, eds), Springer. (with S. Mahaney, J. Royer and S. Kurtz).
• Symmetry Preliminary version of the paper on symmetry breaking (with B. Codenotti and P. Gemmell).
• Leader election. Preliminary version of deterministic self-stabilizing leader election on prime size rings of finite automata (with C. Lin andhttp://cnet.uchicago.edu G. Itkis).
• Average depth. Preliminary version of superlogarithmic lower bounds on average circuit depth for explicit monotone circuits (with B. Codenotti and P. Gemmell).

A scanned version of our out-of-print book Aspectos Teóricos da Computação, (with Cláudio L. Lucchesi, Imre Simon, Istvan Simon, and Tomasz Kowaltowski) can be accessed from its USP mirror.