Robert Robere

I am an Assistant Professor of Computer Science at McGill University. Prior to this, I was a postdoctoral researcher jointly appointed between DIMACS at Rutgers University (January-August 2019) and the Institute for Advanced Study in Princeton (September 2019-August 2020). Before that, I was a research fellow in the Lower Bounds program at the Simons Institute at UC Berkeley.

I received my PhD from the University of Toronto, where I was a member of the DCS Theory Group under the supervision of Toni Pitassi and Stephen Cook.

My primary area of research is computational complexity theory, with an emphasis 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.

teaching

publications

    • 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
    • To appear at 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.
    • To appear at 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]

address

008 Simonyi Hall
School of Mathematics
Institute for Advanced Study
1 Einstein Drive
Princeton, NJ
E-Mail: rrobere [at] ias [dot] edu

fun facts