Igor Carboni Oliveira

  | Assistant Professor & Royal Society University Research Fellow.
  | Department of Computer Science, University of Warwick, UK.
  | Division of Theory and Foundations (FoCS).
  | Centre for Discrete Mathematics and its Applications (DIMAP)




| Contact Details.
Email:  igor.oliveira@warwick.ac.uk  |  igorcarb@gmail.com    Room:  CS2.02    Office hours:  Please contact me to schedule an appointment.    Address:  Info.

| News.
- I'm excited to be co-organising a workshop on the logical foundations of complexity theory to celebrate Jan Krajicek's 60th anniversary!
- An expository article discusses computational complexity and my recent work on hardness magnification. See also my notes for a technical introduction.
- I'm interesed in advising phd students with a strong theoretical background. See below for more information.
| About Me.
I'm a member of the Division of Theory and Foundations (FoCS) and of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick. Previously, I was a postdoctoral researcher at the Algorithms and Complexity Theory Group at the University of Oxford, a research fellow at UC Berkeley's Simons Institute, 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.

| Seminars.
[DIMAP Seminar]  [Oxford-Warwick Complexity Meetings]  [Combinatorics Seminar]  [CS Colloqium] [Probability Seminar]  [Math Postgraduate Seminar]  [Mathematics Colloqium]  

| Teaching Activities.
CS418 - Advances Topics in Algorithms and Complexity (Term 1, 2020/2021).
Logic and Complexity Student Seminar: "Infinitary Methods in Complexity Theory" (Prague, Winter Term, 2016).
Logic and Complexity Student Seminar: "Bounded Arithmetic and Feasible Complexity Theory" (Prague, Summer Term, 2016).
Logic and Complexity Student Seminar: "Reading Group" (Prague, Winter Term, 2015).

| Students and Postdocs.
Bruno Pasqualotto Cavalar (PhD Student).
Zhenjian Lu (Postdoc).

| Publications and Preprints.

- NP-hardness of circuit minimization for multi-output functions  (with Rahul Ilango and Bruno Loff).  ECCC ]  [ Ilango's TCS+ talk ]
- Algorithms and lower bounds for de Morgan formulas of low-communication leaf gates  (with Valentine Kabanets, Sajin Koroth, Zhenjian Lu, and Dimitrios Myrisiotis).  ECCC ]
- Consistency of circuit lower bounds with bounded theories  (with Jan Bydzovsky and Jan Krajicek).  arXiv ]  [ slides ] [ short slides ]  [ video ]  [ see also Krajicek's talk ]  
- Beyond natural proofs: hardness magnification and locality  (with Lijie Chen, Shuichi Hirahara, Jan Pich, Ninad Rajgopal, and Rahul Santhanam).  arXiv ]   notes ]
   Innovations in Theoretical Computer Science (ITCS), 2020.
- 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 ]   notes ]
   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 ]   notes ] 
   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 ]  [ Tal's talk ] 
   Theory of Cryptography Conference (TCC), 2015.
- A simple algorithmic explanation for the concentration of measure phenomenon.   pdf ]
   A short note not intended for publication, 2014.
- Algorithms versus circuit lower bounds.   ECCC ]   [ slides
   Survey / ECCC Report, 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).

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

| Recent and Upcoming Events.

A list with a few recent and upcoming conferences and workshops that could be of interest to students and researchers, including events that I might attend.

Algorithms UK at the University of Warwick  (University of Warwick, 17-18 September, 2019).

Lower Bounds in Computational Complexity Reunion (Simons Institute)  (Berkeley, 9-12 December, 2019).
Proof Complexity (BIRS)  (Banff, 19-24 January, 2020).
DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization  (Rutgers University, 27-29 April, 2020).
Workshop in Quantum Information, Complexity & Cryptography (University of York, 11-12 June, 2020).
Computational Complexity Conference (CCC)  (Saarbruecken, 27-31 July, 2020).
Krajicek's Fest and Complexity Theory with a Human Face  (Tabor, Czech Republic, 1-4 September, 2020).
Dagstuhl Workshop: Algebraic and Analytic Methods in Computational Complexity  (Schloss Dagstuhl, 13-18 September, 2020).

Check DIMAP's website for local events.

| Organization of Workshops.
Warwick Complexity Workshop (University of Warwick, 23-24 July, 2020).  
Krajicek Fest  (Tabor, Czech Republic, 1 September, 2020).

Oxford Complexity Day  (University of Oxford, 27 July, 2018).

| Information for Students, Postdocs, Visitors, etc.

*** I'm unable to host undergraduate students for internships of any kind. Please excuse me for not answering emails with such requests. ***

Warwick Students.
  If you're a student at Warwick interested in working with me, don't hesitate to get in touch to discuss this possibility.
PhD. Warwick has one of the strongest theory groups in the UK, with close interactions between the CS and Math departments. If you would like to apply for a phd position, more information can be found here (check also these scholarships: link1, link2link3link4). I would be happy to support the application of strong candidates based in the UK or from abroad.
You can find some potential topics here.
Postdocs. There are many opportunities for postdocs to come to Warwick, and some of them offer quite generous conditions. A few options are discussed on these pages: link1link2, and link3. You can also check funding opportunities available through Warwick IAS. The best strategy is to contact me as early as possible if you would like to apply for a position or fellowship.
Finally, check also the department's vacancies.

Resources for Warwick visitors