Igor Carboni Oliveira Igor Carboni Oliveira

Email: igorcarb [at] gmail [dot] com

School of Mathematics
Faculty of Mathematics and Physics
Charles University in Prague

Sokolovska 83, 186 75  Praha 8.

About Me

I'm currently a postdoctoral researcher at the School of Mathematics at Charles University in Prague, hosted by Jan Krajicek.
I received my Ph.D. from Columbia University
in 2015, where I was advised by Tal Malkin and Rocco Servedio.
Previously, I was a student at University of Campinas, Brazil (2005-2010).

Research Interests

Computational Complexity, Combinatorics, Algorithms, and Mathematical Logic, with an emphasis on interactions between these fields.


Publications & Preprints

On monotone circuits with local oracles and clique lower bounds (with Jan Krajicek).
Preprint
, 2017.


Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness (with 
Rahul Santhanam).
Computational Complexity Conference [CCC'17].

Pseudodeterministic constructions in subexponential time (with Rahul Santhanam).
Symposium on Theory of Computing [STOC'17].

Addition is exponentially harder than counting for shallow monotone circuits (with Xi Chen and Rocco Servedio).
Symposium on Theory of Computing [STOC'17].

Unprovability of circuit upper bounds in Cook's theory PV (with Jan Krajicek).  [slides]
Logical Methods in Computer Science, 2017
.

Erdos-Ko-Rado for random hypergraphs: asymptotics and stability (with Marcelo Gauy and Hiep Han).
Combinatorics, Probability and Computing, 2017.


Near-optimal small-depth lower bounds for small-distance connectivity (with Xi Chen, Rocco Servedio, and Li-Yang Tan).
Symposium on Theory of Computing [STOC'16].

Unconditional Lower Bounds in Complexity Theory.
[Ph.D. Thesis] -  Columbia University, 2015.


Learning circuits with few negations (with Eric Blais, Clement Canonne, Rocco Servedio, and Li-Yang Tan).
International Workshop on Randomization and Computation [RANDOM'15].

Majority is incompressible by AC0[p] circuits (with Rahul Santhanam).
Computational Complexity Conference [CCC'15].

The power of negations in cryptography (with Siyao Guo, Tal Malkin, and Alon Rosen).
Theory of Cryptography Conference [TCC'15].

An algebraic formulation of the graph reconstruction conjecture (with Bhalchandra Thatte).
Journal of Graph Theory, 2015.

A simple algorithmic explanation for the concentration of measure phenomenon.
Manuscript (not intended for publication), 2014.


Algorithms versus Circuit lower bounds (Survey).
Electronic Colloquium on Computational Complexity (ECCC), 2013.

Constructing hard functions from learning algorithms (with Adam Klivans and Pravesh Kothari).
Conference on Computational Complexity [CCC'13].


Computational Complexity and the P versus NP Problem (in Portuguese).
[Master's Thesis] -  University of Campinas, 2010.



Seminars & Research Groups in Prague

I have co-organized the following courses and seminars:

Logic & Complexity Student Seminar (Winter 2016)

Logic & Complexity Student Seminar (Summer 2016)
Logic & Complexity Student Seminar (Winter 2015)


Additional seminars of interest listed below.

* Logic Seminar - IM.
* Seminar on Limits of Efficient Computation - IUUK.
* Graduate Student Seminar on Combinatorics - KAM.
* Noon Lectures, Combinatorics - KAM
* Logic & Complexity Student Seminar - MFF.
* Seminar on Computational Complexity - IM.

Extremal Graph Theory Group   Kafka Seminar

[KAM - Charles Univ.]   [IUUK - Charles Univ.]   [IM - Academy of Sciences]   [ITI - Charles Univ.]   [DIMATIA]  [Logic - Charles Univ.] 
[MFF - Charles Univ.]
   [KTIML - Charles Univ.]   [TCS - Academy of Sciences]


[Last update:  April 21, 2017]