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 |

Oxford Complexity Day (July 27 - Mathematical Institute, Oxford).

| 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.

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.

| Publications and Preprints.

- Discrete complexity.

Preprint, 2018.

- A magnification phenomenon near state-of-the-art lower bounds (with Jan Pich and Rahul Santhanam)

Preprint, 2018.

- Hardness magnification for natural problems (with Rahul Santhanam).

Submitted, 2018.

- Expander-based cryptography meets natural proofs (with Rahul Santhanam and Roei Tell).

Submitted, 2018.

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

Chicago Journal of Theoretical Computer Science (CJTCS, to appear), 2018.

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

International Workshop on Randomization and Computation (RANDOM), 2018.

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

Computational Complexity Conference (CCC), 2018.

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

Latin American Theoretical Informatics (LATIN, co-winner of the Best Paper Award), 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.

[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.

| Conferences and Workshops

A list of some recent and upcoming workshops that could be of interest to students and researchers, including events that I might attend:

Computational Complexity Conference (CCC) (San Diego, June 22-24).

Summer School on Algorithms and Lower Bounds (Prague, July 6-9)

FLoC Workshop on Proof Complexity (Oxford, July 7-8).

Logic in Computer Science (LICS) (Oxford, July 9-12).

Logic and Computational Complexity (LCC) (Oxford, July 13).

CMI/Oxford Complexity Theory Workshop (Oxford, July 23-26)

Oxford Complexity Day (Oxford, July 27).

International Congress of Mathematicians (ICM) (Rio de Janeiro, August 1-9).

Swedish Summer School in Computer Science (S3CS) (Stockholm, August 5-9).

Simons Workshop: Boolean Devices (Berkeley, September 10-14).

Dagstuhl Workshop: Algebraic Methods in Computational Complexity (Wadern, September 23-28).

| Teaching, Seminars, etc.

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

Oxford: [Algorithms and Complexity Seminar] [Combinatorial Theory Seminar] [Logic Seminar] [Cryptography Seminar]

[ Last Update: June/2018 ]