About Me | Research Interests | Seminars | Teaching Activities | Research Group | Publications | Videos | Slides | Events | ERC-UKRI Project
Quick Links
Meta-Complexity Reading Group (Term 1 - 2024/25)
Warwick Algorithms & Complexity Workshop
Online Complexity Seminar
Complexity Network (Warwick, Oxford, Imperial)
Logical Foundations of Complexity Theory Research Program (Isaac Newton Institute for Mathematical Sciences, Cambridge)
Contact Details
Email: igor.oliveira@warwick.ac.uk | igorcarb@gmail.com Room: CS2.02 Office hours: Please write to me to schedule a meeting. Address: Info
Research Interests
Computational complexity theory and its connections to algorithms, combinatorics, and mathematical logic. I'm interested in the possibilities and limitations of efficient computations and what we can prove about them. More specifically, over the last few years I have been involved with the following research directions:
- Unconditional complexity lower bounds;
- Connecting the design of learning algorithms to complexity lower bounds;
- Computational pseudorandomness, probabilistic Kolmogorov complexity, and their applications;
- Hardness magnification: understanding the difficulty of proving weak lower bounds;
- Unprovability results in mathematical logic;
- Meta-complexity and NP-hardness of circuit minimisation and related problems.
My research is currently supported by a Royal Society University Research Fellowship, an EPSRC New Horizons Grant, and an ERC Starting Grant/UKRI Frontier Research Guarantee.
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.
[ Curriculum Vitae ]
Seminars
Warwick: [Meta-Complexity Reading Group] [Complexity Seminar] [DIMAP Seminar] [Combinatorics Seminar] [Complexity Network] [Foundations of AI] [CS Colloquium] [Maths Colloquium]
Oxford: [Algorithms/Complexity Seminar]
Birmingham: [TCS/Logic Seminar]
Teaching Activities
CS418/CS938: Advanced Topics in Algorithms and Complexity: Computational Learning Theory (Warwick, Term 1 - 2022/2023).
CS418/CS938: Advanced Topics in Algorithms and Complexity (Warwick, Term 1 - 2021/2022).
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).
Research Fellows, Students, and Long-Term Visitors
Current Members:
Zhenjian Lu (Research Fellow). Joined in August/2023.
Ian Mertz (Research Fellow). Joined in October/2022.
Jinqiao Hu (PhD Student). Joined in October/2024.
Dimitrios Tsintsilidas (PhD Student). Joined in October/2023. Dimitrios is jointly supervised by Christian Ikenmeyer.
Past Members:
Shuichi Hirahara (Research Fellow). September/2022 to February/2023.
Zhenjian Lu (Research Fellow). April/2020 to March/2022.
Bruno P. Cavalar (PhD Student). October/2020 to March/2024.
Jiawei Li (Graduate Research Intern). May/2023 to July/2023.
Herby Bowden (MSc Student). January/2022 to August/2022.
Jiatu Li (Undergraduate Research Intern). March/2022 to July/2022.
Prospective PhD students and postdocs: If our research interests overlap and you are interested in joining my research group, feel free to get in touch with me. I can also support the application of strong candidates to one of these postdoctoral fellowships: Marie Curie, Leverhulme, Newton, Eutopia, EPSRC, 1851 Fellowship.
Publications and Preprints
A few representative results include:
- Showing that the design of provably correct learning algorithms requires progress in computational complexity theory. See these slides for an overview.
- Establishing new complexity bounds for graph connectivity, addition, and symmetric functions in the setting of bounded-depth circuits.
- Investigation of a hardness magnification phenomenon under which minor extensions of known complexity lower bounds lead to breakthroughs. See these slides for an overview.
- Showing that some theories of arithmetic cannot prove the easiness and the hardness of computational problems. See these slides and the introduction of this paper.
- A proof that infinitely many prime numbers have succinct and efficient probabilistic representations. See this related survey on probabilistic Kolmogorov complexity.
List of Publications:
- Lower bounds on the overhead of indistinguishability obfuscation (with Z. Lu, N. Mazor, and R. Pass). [ ePrint ] [ slides ] [ PDF ]
Preprint.
- Meta-mathematics of computational complexity theory. [ PDF ]
Preprint.
- Boolean circuit complexity and two-dimensional cover problems (with B. Cavalar). [ slides ] [ PDF ]
Preprint.
- Provability of the circuit size hierarchy and its consequences (with M. Carmosino, V. Kabanets, A. Kolokolova, and D. Tsintsilidas). [ ECCC ] [ PDF ]
Preprint.
- On the unprovability of circuit size bounds in intuitionistic S12 (with L. Chen and J. Li). [ arXiv ] [ PDF ]
Preprint.
- One-way functions and pKt complexity (with S. Hirahara and Z. Lu). [ ePrint ] [ PDF ]
Theory of Cryptography Conference (TCC), 2024.
- On the complexity of avoiding heavy elements (with Z. Lu, H. Ren, and R. Santhanam). [ ECCC ] [ Zhenjian's FOCS talk ] [ PDF ]
Symposium on Foundations of Computer Science (FOCS), 2024.
- Reverse mathematics of complexity lower bounds (with L. Chen and J. Li). [ ECCC ] [ slides ] [ Jiatu's FOCS talk ] [ PDF ]
Symposium on Foundations of Computer Science (FOCS), 2024.
- Exact search-to-decision reductions for time-bounded Kolmogorov complexity (with S. Hirahara, V. Kabanets, and Z. Lu). [ ECCC ] [ PDF ]
Computational Complexity Conference (CCC), 2024.
- Polynomial-time pseudodeterministic construction of primes (with L. Chen, Z. Lu, H. Ren, R. Santhanam). [ ECCC ] [ slides ] [ CIRM talk ] [ Hanlin's TCS+ talk ] [ Hanlin's IAS talk ] [ Quanta ] [ PDF ]
Symposium on Foundations of Computer Science (FOCS), 2023.
- Constant-depth circuits vs. monotone circuits (with B.P. Cavalar). [ ECCC ] [ Bruno's MIAO talk ] [ PDF ]
Computational Complexity Conference (CCC), 2023.
- Unprovability of strong complexity lower bounds in bounded arithmetic (with J. Li). [ ECCC ] [ slides ] [ Simons talk ] [ Jiatu's STOC talk ] [ PDF ]
Symposium on Theory of Computing (STOC), 2023.
- A duality between OWFs and average-case SoI (with S. Hirahara, R. Ilango, Z. Lu, and M. Nanashima). [ ePrint ] [ slides ] [ CIRM talk ] [ Zhenjian's Simons talk ] [ Mikito's STOC talk ] [ PDF ]
Symposium on Theory of Computing (STOC), 2023.
- Theory and applications of probabilistic Kolmogorov complexity (with Z. Lu). [ ECCC ] [ slides ] [ CIRM talk ] [ Simons talk ] [ PDF ]
The Computational Complexity Column - Bulletin of EATCS No 137, 2022.
- Probabilistic Kolmogorov complexity with applications to average-case complexity (with H. Goldberg, V. Kabanets, Z. Lu). [ ECCC ] [ slides ] [ Halley's CCC talk ] [ Zhenjian's DIMACS talk ] [ PDF ]
Computational Complexity Conference (CCC), 2022.
- Optimal coding theorems in time-bounded Kolmogorov complexity (with Z. Lu and M. Zimand). [ arXiv ] [ slides ] [ Zhenjian's DIMACS talk ] [ PDF ]
International Colloquium on Automata, Languages and Programming (ICALP), 2022.
- LEARN-uniform circuit lower bounds and provability in bounded arithmetic (with M. Carmosino, V. Kabanets, A. Kolokolova). [ ECCC ] [ slides ] [ ICMS talk ] [ Marco's talk ] [ Antonina's talk ] [ PDF ]
Symposium on Foundations of Computer Science (FOCS), 2021.
- Quantum learning algorithms imply circuit lower bounds (with S. Arunachalam, A. Grilo, T. Gur, and A. Sundaram). [ arXiv ] [ slides ] [ DIMACS talk ] [ FOCS talk ] [ Tom's talk ] [ Alex's talk ] [ PDF ]
Symposium on Foundations of Computer Science (FOCS), 2021. Quantum Information Processing (QIP), 2021.
- Majority vs. Approximate Linear Sum and average-case complexity below NC1 (with L. Chen, Z. Lu, and X. Lyu). [ ECCC ] [ slides ] [ Xin's ICALP talk ] [ PDF ]
International Colloquium on Automata, Languages and Programming (ICALP), 2021.
- An efficient coding theorem via probabilistic representations and its applications (with Z. Lu). [ ECCC ] [ overview ] [ slides ] [ LMS Colloquium talk ] [ Zhenjian's ICALP talk ] [ PDF ]
International Colloquium on Automata, Languages and Programming (ICALP), 2021.
- Pseudodeterministic algorithms and the structure of probabilistic time (with Z. Lu and R. Santhanam). [ ECCC ] [ Zhenjian's STOC talk ] [ PDF ]
Symposium on Theory of Computing (STOC), 2021.
- NP-hardness of circuit minimization for multi-output functions (with R. Ilango, B. Loff). [ ECCC ] [ Rahul's TCS+ talk ] [ Rahul's CCC talk ] [ Bruno's HSE talk ] [ see also Eric Allender's survey ] [ PDF ]
Computational Complexity Conference (CCC), 2020.
- Algorithms and lower bounds for de Morgan formulas of low-communication leaf gates (with V. Kabanets, S. Koroth, Z. Lu, and D. Myrisiotis). [ ECCC ] [ Dimitrios' CCC talk ] [ PDF ]
Computational Complexity Conference (CCC), 2020. ACM Trans. Comput. Theory 13(4): 23:1-23:37, 2021.
- Consistency of circuit lower bounds with bounded theories (with J. Bydzovsky and J. Krajicek). [ arXiv ] [ slides ] [ short slides ] [ Banff talk ] [ see also Jan Krajicek's Fields talk ] [ PDF ]
Logical Methods in Computer Science, Volume 16, Issue 2, 2020.
- Beyond natural proofs: hardness magnification and locality (with L. Chen, S. Hirahara, J. Pich, N. Rajgopal, and R. Santhanam). [ arXiv ] [ notes ] [ STOC talk ] [ slides ] [ Ninad's ITCS talk ] [ PDF ]
Innovations in Theoretical Computer Science (ITCS), 2020. Journal of the ACM (JACM), 2022.
- Randomness and intractability in Kolmogorov complexity. [ ECCC ] [ slides ] [ LMS Colloquium talk ] [ PDF ]
International Colloquium on Automata, Languages and Programming (ICALP), 2019.
- Parity helps to compute Majority (with R. Santhanam and S. Srinivasan). [ ECCC ] [ slides ] [ PDF ]
Computational Complexity Conference (CCC), 2019.
- Hardness magnification near state-of-the-art lower bounds (with J. Pich and R. Santhanam). [ ECCC ] [ notes ] [ slides ] [ PDF ]
Computational Complexity Conference (CCC), 2019. Theory of Computing (ToC), 2021.
- Expander-based cryptography meets natural proofs (with R. Santhanam and R. Tell). [ ECCC ] [ PDF ]
Innovations in Theoretical Computer Science (ITCS), 2019. Computational Complexity 31(1):4-1:60, 2022.
- Hardness magnification for natural problems (with R. Santhanam). [ ECCC ] [ slides ] [ Simons talk ] [ notes ] [ informal exposition ] [ PDF ]
Symposium on Foundations of Computer Science (FOCS), 2018.
- On monotone circuits with local oracles and clique lower bounds (with J. Krajicek). [ CJTCS ] [ arXiv ] [ PDF ]
Chicago Journal of Theoretical Computer Science (CJTCS), 2018.
- Pseudo-derandomizing learning and approximation (with R. Santhanam). [ ECCC ] [ slides ] [ PDF ]
International Workshop on Randomization and Computation (RANDOM), 2018.
- NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD circuits (with S. Hirahara and R. Santhanam). [ ECCC ] [ PDF ]
Computational Complexity Conference (CCC), 2018.
- An average-case lower bound against ACC (with R. Chen and R. Santhanam). [ ECCC ] [ slides ] [ see also Chen-Ren for subsequent developments ] [ PDF ]
Latin American Theoretical Informatics (LATIN, co-winner of the Best Paper Award), 2018.
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness (with R. Santhanam). [ arXiv ] [ slides ] [ PDF ]
Computational Complexity Conference (CCC), 2017.
- Addition is exponentially harder than counting for shallow monotone circuits (with X. Chen and R. Servedio). [ arXiv ] [ slides ] [Simons talk ] [ PDF ]
Symposium on Theory of Computing (STOC), 2017.
- Pseudodeterministic constructions in subexponential time (with R. Santhanam). [ ECCC ] [ slides ] [ LMS Colloquium talk ] [ see also Rahul's IAS talk ] [ PDF ]
Symposium on Theory of Computing (STOC), 2017.
- Unprovability of circuit upper bounds in Cook's theory PV (with J. Krajicek). [ arXiv ] [ slides ] [ PDF ]
Logical Methods in Computer Science, Volume 13, Issue 1, 2017.
- Erdos-Ko-Rado for random hypergraphs: asymptotics and stability (with M. Gauy and H. Han). [ arXiv ] [ PDF ]
Combinatorics, Probability and Computing, 26(3), 406-422, 2017.
- Near-optimal small-depth lower bounds for small distance connectivity (with X. Chen, R. Servedio, and L. Tan). [ arXiv ] [ see also Srikanth Srinivasan's exposition ] [ PDF ]
Symposium on Theory of Computing (STOC), 2016.
- An algebraic formulation of the graph reconstruction conjecture (with B. Thatte). [ arXiv ] [ PDF ]
J. Graph Theory, 81: 351-363, 2016.
- Learning circuits with few negations (with E. Blais, C. Canonne, R. Servedio, and L. Tan). [ ECCC ] [ PDF ]
International Workshop on Randomization and Computation (RANDOM), 2015.
- Majority is incompressible by AC[p] circuits (with R. Santhanam). [ ECCC ] [ slides ] [ PDF ]
Conference on Computational Complexity (CCC), 2015.
- The power of negations in cryptography (with S. Guo, T. Malkin, and A. Rosen). [ ePrint ] [ slides ] [ Tal's MSR talk ] [ PDF ]
Theory of Cryptography Conference (TCC), 2015.
- Algorithms versus circuit lower bounds. [ ECCC ] [ slides ] [ PDF ]
Survey / ECCC Report, 2013.
- Constructing hard functions from learning algorithms (with A. Klivans and P. Kothari). [ ECCC ] [ slides ] [ PDF ]
Conference on Computational Complexity (CCC), 2013.
[PhD Thesis] Unconditional lower bounds in complexity theory. [ External Link ] [ PDF ]
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 ] [ PDF ]
University of Campinas, August/2010 (Advisor: Arnaldo Vieira Moura).
Notes and Expositions:
- Advances in hardness magnification. December, 2019. [ PDF ]
- Notes on the method of approximations and the emergence of the fusion method. August, 2018. [ PDF ]
- A simple algorithmic explanation for the concentration of measure phenomenon. October, 2014. [ PDF ]
Open Problems:
Simons Institute ("Lower Bounds in Computational Complexity" - Fall/2018)
Informal expositions | media coverage | online discussions:
[ Quanta Magazine ] [ Computational Complexity Blog I ] [ Computational Complexity Blog II ] [ Computational Complexity Blog III ] [ Simons Institute I ] [ Simons Institute II ] [ Godel's Lost Letter ] [ Shtetl Optimized I ] [ Shtetl Optimized II ] [ Oxford Inspired Research ] [ CS@Columbia ] [ Oded's Choices ]
Videos of Invited Talks and Tutorials
For a list of some recorded talks and tutorials, see this page.
Slides of Some Recent Talks
Hardness of Near-Optimal Indistinguishability Obfuscation [Oxford Proof Complexity Workshop, 2024]
Levin Complexity and Pseudodeterministic Constructions of Primes [Leonid Levin's 75th Birthday Symposium, 2024]
Meta-Mathematics of Complexity Theory [Oberwolfach Workshop "Proof Complexity and Beyond", 2024]
Theory of Probabilistic Kolmogorov Complexity: [ Video 1 Slides 1 ] [ Video 2 Slides 2 ] [ Video 3 Slides 3 ] [CIRM Workshop "Randomness, Information, and Complexity", 2024]
Polynomial-Time Pseudodeterministic Construction of Primes [STACS - Symposium on Theoretical Aspects of Computer Science, 2024]
Complexity Theory Through the Lens of Kolmogorov Complexity [Czech Academy of Sciences, 2023]
Meta-Mathematics of Computational Complexity Theory [Logic Colloquium, 2023]
Extracting Computational Hardness from Classical and Quantum Learning Algorithms [MIT Algorithms & Complexity Seminar, 2022]
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.
Leonid Levin's 75th Birthday Symposium [Boston University, 10-11 July, 2024]
Computational Complexity Conference (CCC) [Ann Arbor, Michigan, 22-25 July, 2024]
RANDOM/APPROX [London, 28-30 August, 2024]
Oxford Workshop "Proof Complexity" [University of Oxford, 3-5 September, 2024]
British Logic Colloquium [University of Birmingham, 5-7 September, 2024]
Proof Society International School and Workshop [University of Birmingham, 9-13 September, 2024]
Dagstuhl Workshop "Algebraic and Analytic Methods in Computational Complexity" [Schloss Dagstuhl, 15-20 September, 2024]
Warwick Algorithms & Complexity Workshop [University of Warwick, 23-24 Semptember, 2024]
Symposium on Foundations of Computer Science (FOCS) [Chicago, 27-30 October, 2024]
Dagstuhl Workshop "Computational Complexity of Discrete Problems" [Schloss Dagstuhl, 9-14 March, 2025]
Check DIMAP's website for local events.
Organization of Workshops, Research Programs, and Other Events
Logical Foundations of Complexity Theory Research Program (Isaac Newton Institute for Mathematical Sciences, University of Cambridge)
Warwick Algorithms & Complexity Workshop
Warwick-Oxford-Imperial Complexity Network
Online Complexity Seminar
FOCS Workshop "Recent Developments in Explicit Constructions"
Meta-Complexity Research Program (Simons Institute, UC Berkeley)
Workshop "Lower Bounds, Learning, and Average-Case Complexity" (Simons Institute, UC Berkeley)
Oxford Complexity Day
Information for Students, Postdocs, Visitors, etc.
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 Europe, 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, link2, link3, link4). 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: link1, link2, 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