|
Associate Professor
|
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.comRoom:
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.
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 Fellows, Students, and Long-Term Visitors Zhenjian
Lu (Research Fellow). April/2020 to March/2022 and August/2023 to December/2024. Ian Mertz
(Research Fellow). October/2022 to September/2024. Shuichi Hirahara (Research Fellow).
September/2022 to February/2023. Jinqiao Hu (PhD Student). Joined in October/2024. Dimitrios
Tsintsilidas (PhD Student). Joined in October/2023. Bruno P. Cavalar
(PhD Student). October/2020 to March/2024. Ondrej Jezil (Graduate Research Intern, Charles University in Prague). May/2025 to June/2025. Jiawei Li
(Graduate Research Intern, UT Austin). May/2023 to July/2023.
Herby Bowden (MSc
Student). January/2022 to August/2022.
Jingyi Lyu (Undergraduate Research Intern, Tsinghua University). March/2025 to June/2025. Jiatu Li
(Undergraduate Research Intern, Tsinghua University). 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.
- Lower bounds on the overhead of indistinguishability obfuscation (with Z. Lu, N. Mazor, and R. Pass). [ ePrint
] [ slides
] [ Noam's Simons talk
] [ Noam's EnCORE talk
]
[ PDF
]
Preprint.
- On the unprovability of circuit size bounds in intuitionistic S12 (with
L. Chen and J. Li).
[ arXiv
] [ PDF
]
Logical Methods in Computer Science (LMCS), 2025.
- Meta-mathematics of computational complexity theory.
[
ECCC
] [ PDF
]
SIGACT News Complexity Theory Column, 2025.
- Boolean circuit complexity and two-dimensional cover problems (with B. Cavalar).
[ arXiv
] [ slides
]
[ PDF
]
ACM Transactions on Computation Theory (TOCT), 2025.
- Provability of the circuit size hierarchy and its consequences (with
M. Carmosino, V. Kabanets, A. Kolokolova, and D. Tsintsilidas). [ Dimitrios' ITCS talk ]
[
ECCC
] [ PDF
]
Innovations in Theoretical Computer Science
(ITCS), 2025.
- 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 (LMCS), 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 (LMCS), 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 (CPC), 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 (JGT), 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)
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.