Quick Links

CS418/CS938: Advanced Topics in Algorithms and Complexity: Computational Learning Theory (Term 1 - 2021/22)

Complexity Network (Warwick, Oxford, Imperial)

Oxford-Warwick Complexity Meetings

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

Announcements

- The Computational Complexity Conference (CCC) will take place in Warwick in July 2023!

- If you're a local student or researcher interested in computational complexity theory, check out the website of the Complexity Network (Warwick, Oxford, Imperial).

- If you're looking for a postdoc position in complexity theory, I'll be happy to support the application of strong candidates to one of these fellowships: Marie Curie, Leverhulme, Newton, Eutopia, EPSRC.

- I'm interesed in advising phd students with a strong theoretical background. We accept applications twice a year; more information is available here.

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. In particular, over the last few years I have been involved with the following research directions:

Unconditional complexity lower bounds

Connecting the design of 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 (PI) on "New approaches to unconditional computational lower bounds" and an EPSRC New Horizons Grant (co-I) on "Structure vs randomness in algorithms and computation".

Seminars

Warwick: [Complexity Network] [Oxford-Warwick Complexity Meetings] [DIMAP Seminar] [Combinatorics Seminar] [CS Colloquium] [Maths Colloquium]

Birmingham: [TCS/Logic Seminar] [Lab Lunch] [Combinatorics Seminar]

Teaching Activities

CS418/CS938: Advanced Topics in Algorithms and Complexity: Computational Learning Theory (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

Herby Bowden (MSc Student).

Bruno P. Cavalar (PhD Student).

Jiatu Li (Visitor / Research Intern).

Zhenjian Lu (Research Fellow). April 2020 to March 2022.

Publications and Preprints

A few representative results and highlights include:

- Showing that the design of provably correct learning algorithms requires progress in computational complexity theory.

- Establishing new complexity bounds for graph connectivity, addition, and symmetric functions in the setting of bounded-depth circuits.

- A proof that circuit minimisation of total functions is NP-hard.

- Investigation of a hardness magnification phenomenon under which minor extensions of known complexity lower bounds lead to breakthroughs.

- Showing that some theories of arithmetic cannot prove the easiness of computational problems.

- A proof that infinitely many prime numbers have succinct and efficient probabilistic representations.

List of Publications:

- Theory and applications of probabilistic Kolmogorov complexity (with Zhenjian Lu).

The Computational Complexity Column - Bulletin of EATCS No 137 (to appear), 2022.

- Probabilistic Kolmogorov complexity with applications to average-case complexity (with Halley Goldberg, Valentine Kabanets, and Zhenjian Lu). [ ECCC ]

Computational Complexity Conference (CCC), 2022.

- Optimal coding theorems in time-bounded Kolmogorov complexity (with Zhenjian Lu and Marius Zimand). [ arXiv ]

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

- LEARN-uniform circuit lower bounds and provability in bounded arithmetic (with Marco Carmosino, Valentine Kabanets, and Antonina Kolokolova). [ ECCC ] [ Marco's FOCS talk ] [ Antonina's talk ]

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

- Quantum learning algorithms imply circuit lower bounds (with Srinivasan Arunachalam, Alex Grilo, Tom Gur, and Aarthi Sundaram). [ arXiv ] [ slides ] [ video ] [ Tom's QIP talk ] [ Alex's Simons talk ]

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 Lijie Chen, Zhenjian Lu, and Xin Lyu). [ ECCC ] [ slides ] [ Xin's ICALP talk ]

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

- An efficient coding theorem via probabilistic representations and its applications (with Zhenjian Lu). [ ECCC ] [ overview ] [ slides ] [ video ] [ Zhenjian's ICALP talk ]

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

- Pseudodeterministic algorithms and the structure of probabilistic time (with Zhenjian Lu and Rahul Santhanam). [ ECCC ] [ Zhenjian's STOC talk ]

Symposium on Theory of Computing (STOC), 2021.

- NP-hardness of circuit minimization for multi-output functions (with Rahul Ilango and Bruno Loff). [ ECCC ] [ Rahul's TCS+ talk ] [ Rahul's CCC talk ] [ Bruno's HSE talk ] [ see also Eric Allender's survey ]

Computational Complexity Conference (CCC), 2020.

- Algorithms and lower bounds for de Morgan formulas of low-communication leaf gates (with Valentine Kabanets, Sajin Koroth, Zhenjian Lu, and Dimitrios Myrisiotis). [ ECCC ] [ Dimitrios' CCC talk ]

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 Jan Bydzovsky and Jan Krajicek). [ arXiv ] [ slides ] [ short slides ] [ video ] [ see also Jan Krajicek's Fields talk ]

Logical Methods in Computer Science, Volume 16, Issue 2, 2020.

- Beyond natural proofs: hardness magnification and locality (with Lijie Chen, Shuichi Hirahara, Jan Pich, Ninad Rajgopal, and Rahul Santhanam). [ arXiv ] [ notes ] [ video ] [ slides ] [ Ninad's ITCS talk ]

Innovations in Theoretical Computer Science (ITCS), 2020. Journal of the ACM (to appear), 2022.

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

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

Computational Complexity Conference (CCC), 2019. Theory of Computing (CCC'19 Special Isssue, to appear), 2021.

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

Innovations in Theoretical Computer Science (ITCS), 2019. Computational Complexity 31(1):4-1:60, 2022.

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

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 ] [ see also Chen-Ren for subsequent developments ]

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

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 ] [ see also Rahul's IAS talk ]

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 connectivity (with Xi Chen, Rocco Servedio, and Li-Yang Tan). [ arXiv ] [ see also Srikanth Srinivasan's exposition ]

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 MSR talk ]

Theory of Cryptography Conference (TCC), 2015.

- 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.

[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).

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:

[ Simons Institute ] [ Godel's Lost Letter ] [ Shtetl Optimized I ] [ Shtetl Optimized II ] [ Oxford Inspired Research ] [ CS@Columbia ] [ Oded's Choices ]

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.

DIMACS Workshop "Meta-Complexity, Barriers, and Derandomization" (DIMACS/Rutgers, 25-27 April, 2022).

Workshop "Complexity Theory with a Human Face, 3rd Edition" (Prague, 27 June to 1 July, 2022).

Workshop "Mathematical Approaches to Lower Bounds: Complexity of Proofs and Computation" (ICMS Edinburgh, 4-8 July, 2022).

Computational Complexity Conference (Philadelphia, 20-23 July, 2022).

Dagstuhl Workshop "Algebraic and Analytic Methods in Computational Complexity" (11-16 September, 2022).

Meta-Complexity (Simons Institute, Spring 2023) & Workshop "Lower Bounds, Learning, and Average-Case Complexity" (Simons Institute, 10 January to 12 May, 2023).

Check DIMAP's website for local events.

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