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 |

| Quick Links.

List of Open Problems - Simons Institute ("Lower Bounds in Computational Complexity" - Fall/2018)

Oxford Complexity Day (27/July/2018)

| About Me.

I'm a postdoctoral researcher at the Algorithms and Complexity Theory Group (Oxford). Previously, I was a research fellow at UC Berkeley's Simons Institute in connection with the program on "Lower Bounds in Computational Complexity", and a postdoctoral fellow at the School of Mathematics at Charles University in Prague. I completed my phd in the Theory of Computation Group at Columbia University. In a more distant past, 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. A recurring theme in my investigations is the interplay between algorithmic upper bounds, complexity lower bounds, and mathematical proofs. More specific research directions and interests include:

- Circuit Complexity.

- Connections between Algorithms and Lower Bounds.

- Logic in Complexity Theory.

- Randomness in Computation.

- Applications of Complexity Theory in Learning Theory and Cryptography.

In terms of techniques, the theory of pseudorandomness is an important ingredient in some of my works involving algorithms and complexity. In other settings such as independence results and circuit lower bounds, ideas from logic and combinatorics play a more fundamental role, respectively.

| Publications and Preprints.

- Consistency of circuit lower bounds with bounded theories (with Jan Bydzovsky and Jan Krajicek). [ arXiv ]

Submitted, 2019.

- Randomness and intractability in Kolmogorov complexity. [ ECCC ] [ slides ]

International Colloquium on Automata, Languages and Programming (ICALP), 2019.

- Parity helps to compute Majority (with Rahul Santhanam and Srikanth Srinivasan). [ ECCC ] [ slides ]

Computational Complexity Conference (CCC), 2019.

- Hardness magnification near state-of-the-art lower bounds (with Jan Pich and Rahul Santhanam). [ ECCC ]

Computational Complexity Conference (CCC), 2019.

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

Innovations in Theoretical Computer Science (ITCS), 2019.

- Hardness magnification for natural problems (with Rahul Santhanam). [ ECCC ] [ slides ] [ video ]

Symposium on Foundations of Computer Science (FOCS), 2018.

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

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

- Pseudo-derandomizing learning and approximation (with Rahul Santhanam). [ ECCC ] [ slides ]

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 ] [ video ]

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.

- The Ricean objection: an analogue of Rice's theorem for first-order theories (with Walter Carnielli). [ IGPL ] [ Correction ] [ Related Note ]

Logic Journal of the IGPL, 16(6), 585-590, 2008.

[PhD Thesis] Unconditional lower bounds in complexity theory. [ External Link ]

Columbia University, June/2015 (Advisors: Tal Malkin and Rocco Servedio).

[Master's Thesis] Computational complexity and the P vs. NP problem (In Portuguese). [ External Link ] [ Related Note ]

University of Campinas, August/2010 (Advisor: Arnaldo Vieira Moura).

| Conferences and Workshops.

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

International Colloquium on Automata, Languages and Programming (ICALP) and Workshop on Logic and Computational Complexity (LCC) (Patras, 7-12 July, 2019).

Computational Complexity Conference (CCC) and DIMACS Day of Complexity Tutorials (New Brunswick, 17-20 July, 2019).

Logic Colloquium (Prague, 11-16 August, 2019).

Lower Bounds in Computational Complexity Reunion (Simons Institute) (Berkeley, 9-12 December, 2019).

Proof Complexity (BIRS) (Banff, 19-24 January, 2020).

| 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] [Probability Seminar] [Junior Probability Seminar]

[ Last Update: July/2019 ]