all research papers (chronological)

  1. Separations in Proof Complexity and TFNP
    • Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao.
    • To appear at FOCS 2022. [ECCC]
  2. Further Collapses in TFNP
    • Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao.
    • To appear at CCC 2022. [ECCC] [DROPS]
    • Contributed presentation at HALG 2022.
  3. Proofs, Circuits, and Communication
    • Susanna de Rezende, Mika Göös, Robert Robere.
    • SIGACT News Complexity Theory Column, March 2022. [ArXiV]
  4. Extremely Deep Proofs
  5. Pseudorandom Self-Reductions for NP-Complete Problems
  6. On Semi-Algebraic Proofs and Algorithms
  7. Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
  8. On the Power and Limitations of Branch and Cut
    • Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
    • CCC 2021. [ECCC] [arXiv]
    • Invited to the special journal issue for CCC 2021.
  9. Automating Algebraic Proof Systems is NP-Hard
    • Susanna F. de Rezende, Mika Göös, Jakob Nördstrom, Toniann Pitassi, Robert Robere, Dmitry Sokolov.
    • STOC 2021. [ECCC]
  10. KRW Composition Theorems via Lifting
    • Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere
    • FOCS 2020. [ECCC]
  11. 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]
  12. Lower Bounds for (Non-monotone) Comparator Circuits
  13. Nullstellensatz Size-Degree Trade-Offs from Reversible Pebbling
  14. Adventures in Monotone Complexity and TFNP
    • Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
    • ITCS 2019. [ECCC] [DROPS]
  15. Learning-Sensitive Backdoors with Restarts
    • Edward Zulkoski, Ruben Martins, Christoph M. Wintersteiger, Robert Robere, Jia Liang, Krzysztof Czarnecki and Vijay Ganesh
    • CP 2018.
  16. The Proof Complexity of SMT Solvers
    • Robert Robere, Antonina Kolokolova, Vijay Ganesh.
    • CAV 2018.
  17. Lifting Nullstellensatz to Monotone Span Programs over any Field.
  18. Stabbing Planes.
    • Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere.
    • ITCS 2018. [ECCC]
  19. Random Θ(log n)-CNFs are Hard for Cutting Planes.
    • Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere.
    • FOCS 2017. [ECCC]
    • To appear in the Journal of the ACM.
  20. Strongly Exponential Lower Bounds for Monotone Computation.
  21. Exponential Lower Bounds for Monotone Span Programs.
  22. 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]
  23. Path Graphs, Clique Trees, and Flowers.
    • Lalla Mouatadid and Robert Robere.
    • Manuscript 2015. [ArXiv]
  24. 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.
  25. A Note on Tractability and Artificial Intelligence.
    • Tarek R. Besold and Robert Robere.
    • AGI 2013. [DOI]
  26. Average Case Lower Bounds for Monotone Switching Networks.
    • Stephen A. Cook, Yuval Filmus, Toniann Pitassi, Robert Robere.
    • FOCS 2013. [ECCC]
  27. Complex Analogies: Remarks on the Complexity of HDTP.
    • Tarek R. Besold and Robert Robere.
    • Australasian Conference on Artificial Intelligence (AI 2012). [DOI]
  28. 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