igor  Igor Carboni Oliveira

 | Department of Computer Science
 | University of Oxford
 | Wolfson Building, Parks Road, Oxford, OX1 3QD, UK.

 Email:  igor.carboni.oliveira@cs.ox.ac.uk / igorcarb@gmail.com

| About Me.

I'm a researcher at the Algorithms and Complexity Theory Group (Oxford), where I'm hosted by Rahul Santhanam. Previously,  I was a postdoctoral researcher at the School of  Mathematics at Charles University in Prague, hosted by Jan Krajicek. I completed my phd in the Theory of Computation Group at Columbia University, where I was jointly advised by Tal Malkin and Rocco Servedio. Before this, I was a student at University of Campinas in Brazil.  

| Research Interests.

Computational complexity theory and its connections to algorithms, combinatorics, and mathematical logic. I'm particularly interested in unconditional computational lower bounds and their applications.

| Publication and Preprints.

- An average-case lower bound against ACC  (with Ruiwen Chen and Rahul Santhanam).   ECCC ]
- On monotone circuits with local oracles and clique lower bounds  (with Jan Krajicek).   [ arXiv ]
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness  (with Rahul Santhanam).   [ arXiv ]   [ slides ]
   Computational Complexity Conference (CCC), 2017.
- Pseudodeterministic constructions in subexponential time  (with Rahul Santhanam).   ECCC ]   [ slides ]
   Symposium on Theory of Computing (STOC), 2017.
- Addition is exponentially harder than counting for shallow monotone circuits  (with Xi Chen and Rocco Servedio).   arXiv ]   [ slides ]
   Symposium on Theory of Computing (STOC), 2017.
- Unprovability of circuit upper bounds in Cook's theory PV  (with Jan Krajicek).   arXiv ]   [ slides ]
   Logical Methods in Computer Science, Volume 13, Issue 1, 2017.
- Erdos-Ko-Rado for random hypergraphs: asymptotics and stability  (with Marcelo Gauy and Hiep Han).   arXiv ]
   Combinatorics, Probability and Computing, 26(3), 406-422, 2017.
- Near-optimal small-depth lower bounds for small distance connecticity  (with Xi Chen, Rocco Servedio, and Li-Yang Tan).   arXiv ]
   Symposium on Theory of Computing (STOC), 2016.
- An algebraic formulation of the graph reconstruction conjecture  (with Bhalchandra Thatte).   arXiv ]
   J. Graph Theory, 81: 351-363, 2016.
- On the monotone complexity of the satisfiability problem.   Chapter 3 - Phd Thesis ]
   Manuscript, 2015.
- Learning circuits with few negations.  (with Eric Blais, Clement Canonne, Rocco Servedio, and Li-Yang Tan).   ECCC ]
   International Workshop on Randomization and Computation (RANDOM), 2015.
- Majority is incompressible by AC[p] circuits  (with Rahul Santhanam).   ECCC ]   [ slides ] 
   Conference on Computational Complexity (CCC), 2015.
- The power of negations in cryptography  (with Siyao Guo, Tal Malkin, and Alon Rosen).   ePrint ]   [ slides ] 
   Theory of Cryptography Conference (TCC), 2015.
- A simple algorithmic explanation for the concentration of measure phenomenon.   [ note ]
   Manuscript (not intended for publication), 2014.
- Algorithms versus Circuit lower bounds.   ECCC ]   [ slides ]
   (Survey) Electronic Colloquium on Computational Complexity, 2013.
- Constructing hard functions from learning algorithms  (with Adam Klivans and Pravesh Kothari).   ECCC ]   [ slides ] 
   Conference on Computational Complexity (CCC), 2013.

[PhD Thesis]  Unconditional lower bounds in complexity theory.   [ External Link ]  
  Columbia University, 2015.
[Master's Thesis]  Computational complexity and the P vs. NP problem  (In Portuguese).   External Link ]  
  University of Campinas, 2010.

| Teaching, Seminars, etc.

For now, check my old website at  http://www.karlin.mff.cuni.cz/~igorcarb/

[ Last Update: November/2017 ]