Igor Carboni Oliveira


PhD Student - Department of Computer Science
Columbia University - New York.

Email: [last name] at cs.columbia.edu
Office: CSB 516

 igor

About Me

I'm a phd student in the Theory of Computation Group at Columbia University, where I'm fortunate to be advised by Rocco Servedio and Tal Malkin. Before that, I was a student at University of Campinas, Brazil.

Research Interests

I'm mainly interested in computational complexity theory, but I also have strong interests in combinatorics and mathematical logic. 


Publications/Preprints

An algebraic formulation of the graph reconstruction conjecture.  
(with B. Thatte)
[arXiv:1301.4121]

Constructing hard functions from learning algorithms.
(with A. Klivans and P. Kothari)
[CCC 2013 - to appear]

Intersection problems in sparse random hypergraphs.
(with M. Gauy, H. Han and Y. Kohayakawa)
[In preparation]

Old Papers, Tech Reports, etc.

An algorithmic proof of the Chernoff-Hoeffding bound.
[Manuscript]

A new look at some classical results in complexity theory.
(with A. Moura)
[ECCC TR09-025]

On an abstract theory of 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)
[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]