Igor Carboni Oliveira

Old Papers, Technical Reports, etc.

A note on some classical results in computational complexity.
(with A. Moura)
[Manuscript] [ECCC TR09-025]

On computational models and the converse of Rice's theorem.
(with W. Carnielli and A. Moura)
[Manuscript]

The Ricean objection: an analogue of Rice's theorem for first-order theories.
(with W. Carnielli)
[Manuscript] [Logic Journal of the IGPL]

Expositions/Lecture Notes

Learning vs circuit lower bounds [pdf]

Inaccessible entropy and its applications [pdf]

Learning using the Fourier transform [pdf]

Basic lower bound techniques in communication complexity [pdf]