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 |

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.

During the Fall 2018 semester, I'll be a research fellow at UC Berkeley's Simons Institute in connection with the program on "Lower Bounds in Computational Complexity".

| 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. A recurring theme in my investigations is the interplay between algorithmic upper bounds, complexity lower bounds, and mathematical proofs.

In terms of techniques, the theory of pseudorandomness is an important ingredient in some of my works involving algorithms and complexity (see e.g. learning speedups, generation of prime numbers, and hardness of MCSP). In other settings such as independence results and circuit lower bounds (see also graph connectivity), ideas from logic and probabilistic combinatorics play a more fundamental role, respectively.

| Publication and Preprints.

- Hardness magnification (with Rahul Santhanam).

In preparation, 2018.

- Discrete complexity (with Rahul Santhanam).

In preparation, 2018.

- NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD circuits (with Shuichi Hirahara and Rahul Santhanam). [ ECCC ]

Submitted, 2018.

- Pseudo-derandomizing learning and approximation (with Rahul Santhanam).

Submitted, 2018.

- On monotone circuits with local oracles and clique lower bounds (with Jan Krajicek). [ arXiv ]

Submitted, 2018.

- An average-case lower bound against ACC (with Ruiwen Chen and Rahul Santhanam). [ ECCC ]

Latin American Theoretical Informatics (LATIN), 2018.

- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness (with Rahul Santhanam). [ arXiv ] [ slides ]

Computational Complexity Conference (CCC), 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.

- Pseudodeterministic constructions in subexponential time (with Rahul Santhanam). [ ECCC ] [ 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.

- An analogue of Rice's theorem for first-order logic (with Walter Carnielli). [ IGLP ] [ Erratum ] [ Related Note ]

Logic Journal of the IGPL, 16:6, 585-990, 2008.

[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 ] [ Related Note ]

University of Campinas, 2010.

| Teaching, Seminars, etc.

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

[ Last Update: February/2018 ]