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 |

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

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 fellow at the School of Mathematics at Charles University in Prague, working in collaboration with Jan Krajicek. I completed my phd in the Theory of Computation Group at Columbia University, jointly advised by Tal Malkin and Rocco Servedio. In a more distant past, 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. More specific research directions and interests include:

- Circuit Complexity.

- Connections between Algorithms and Lower Bounds.

- Monotonicity in Algorithms and Complexity.

- Logic in Complexity Theory.

- Randomness in Computation.

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 combinatorics play a more fundamental role, respectively.

| Publications and Preprints.

- Discrete complexity.

Preprint, 2018.

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

Submitted, 2018.

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

Submitted, 2018.

- 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 ] [ Oded's Choices ]

Symposium on Theory of Computing (STOC), 2017.

- Pseudodeterministic constructions in subexponential time (with Rahul Santhanam). [ ECCC ] [ slides ] [ Shtetl-Optimized Blog ] [ Inspired Research Newsletter ] [ Oded's Choices ]

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 ] [ CS@CU Press Release ]

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 ] [ Computational Complexity Blog ]

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 ] [ Oded's Choices ]

(Survey) Electronic Colloquium on Computational Complexity, 2013.

- Constructing hard functions from learning algorithms (with Adam Klivans and Pravesh Kothari). [ ECCC ] [ slides ] [ Godel's Lost Letter and P = NP Blog ] [ Oded's Choices ]

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 events that I plan to attend:

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

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 Conference on Randomization and Computation (RANDOM) (Princeton, August 20-22)

Simons Boot Camp: Lower Bounds in Computational Complexity (Berkeley, August 20-24)

BIRS-CMO Workshop: Theory and Practice of Satisfiability Solving (Oaxaca, August 26-31).

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

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

Symposium on Foundations of Computer Science (FOCS) (Paris, October 7-9).

| 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: October/2018 ]