Robert Robere

I am an Assistant Professor in the School of Computer Science at McGill University. My research interests are in computational complexity theory, and particularly in circuit complexity, proof complexity, communication complexity, and related topics. I also maintain an interest in the theory and practice of SAT solving and model checking.

I have now officially joined McGill, and I am excited to supervise students! If you would like to chat about research opportunities, drop me an e-mail!

contact

E-Mail: robere [at] cs [dot] mcgill [dot] ca
Office: TBD
McGill University
Montreal, QC, Canada

Prior to joining McGill, I was...

teaching

research

    • Automating Algebraic Proof Systems is NP-Hard
    • Susanna F. de Rezende, Mika Göös, Jakob Nördstrom, Toniann Pitassi, Robert Robere, Dmitry Sokolov.
    • Manuscript 2020. [ECCC]
    • KRW Composition Theorems via Lifting
    • Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere
    • FOCS 2020. [ECCC]
    • Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
    • Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere, Marc Vinyals.
    • FOCS 2020. [ECCC]
    • Lower Bounds for (Non-monotone) Comparator Circuits
    • Anna Gál, Robert Robere
    • ITCS 2020. [ECCC] [DROPS]
    • Nullstellensatz Size-Degree Trade-Offs from Reversible Pebbling
    • Suzanna F. de Rezende, Or Meir, Jakob Nördstrom, Robert Robere
    • CCC 2019. [ECCC] [DROPS]
    • Adventures in Monotone Complexity and TFNP
    • Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
    • ITCS 2019. [ECCC] [DROPS]
    • Learning-Sensitive Backdoors with Restarts
    • Edward Zulkoski, Ruben Martins, Christoph M. Wintersteiger, Robert Robere, Jia Liang, Krzysztof Czarnecki and Vijay Ganesh
    • CP 2018.
    • The Proof Complexity of SMT Solvers
    • Robert Robere, Antonina Kolokolova, Vijay Ganesh.
    • CAV 2018.
    • Stabbing Planes.
    • Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere.
    • ITCS 2018. [ECCC]
    • Random Θ(log n)-CNFs are Hard for Cutting Planes.
    • Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere.
    • FOCS 2017. [ECCC]
    • Strongly Exponential Lower Bounds for Monotone Computation.
    • Toniann Pitassi, Robert Robere.
    • STOC 2017. [ECCC] [Slides]
    • Exponential Lower Bounds for Monotone Span Programs.
    • Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook.
    • FOCS 2016. [ECCC] [Slides] [Talk at BIRS] [Talk at FOCS 2016]
    • Invited to the special journal issue for FOCS 2016.
    • When Thinking Never Comes To A Halt: Using Formal Methods in Making Sure Your AI Gets the Job Done Good Enough
    • Tarek R. Besold and Robert Robere
    • Fundamental Issues of Artificial Intelligence (2016). Volume 376:43-62. [DOI]
    • Path Graphs, Clique Trees, and Flowers.
    • Lalla Mouatadid and Robert Robere.
    • Manuscript 2015. [ArXiv]
    • When Almost Is Not Even Close: Remarks on the Approximability of HDTP.
    • Tarek R. Besold and Robert Robere.
    • AGI 2013. [DOI]
    • Awarded the Cognitive Science Society Prize for Best Student Paper.
    • A Note on Tractability and Artificial Intelligence.
    • Tarek R. Besold and Robert Robere.
    • AGI 2013. [DOI]
    • Average Case Lower Bounds for Monotone Switching Networks.
    • Stephen A. Cook, Yuval Filmus, Toniann Pitassi, Robert Robere.
    • FOCS 2013. [ECCC]
    • Complex Analogies: Remarks on the Complexity of HDTP.
    • Tarek R. Besold and Robert Robere.
    • Australasian Conference on Artificial Intelligence (AI 2012). [DOI]
    • A Change for the Better? Assessing the Computational Cost of Re-representation.
    • Todd Wareham, Robert Robere and Iris van Rooij.
    • International Conference on Cognitive Modeling [ICCM 2012].

theses

[curriculum vitae]

fun facts