all research papers (chronological)

  1. Extremely Deep Proofs
    • Noah Fleming, Toniann Pitassi, Robert Robere
    • To appear at ITCS 2022. [ECCC]
  2. Pseudorandom Self-Reductions for NP-Complete Problems
    • Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda.
    • To appear at ITCS 2022. [ECCC]
  3. On Semi-Algebraic Proofs and Algorithms
    • Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere
    • To appear at ITCS 2022. [ECCC]
  4. Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
    • Robert Robere, Jeroen Zuiddam.
    • To appear at FOCS 2021. [ECCC]
  5. 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.
  6. 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]
  7. KRW Composition Theorems via Lifting
    • Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere
    • FOCS 2020. [ECCC]
  8. 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]
  9. Lower Bounds for (Non-monotone) Comparator Circuits
  10. Nullstellensatz Size-Degree Trade-Offs from Reversible Pebbling
  11. Adventures in Monotone Complexity and TFNP
    • Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
    • ITCS 2019. [ECCC] [DROPS]
  12. Learning-Sensitive Backdoors with Restarts
    • Edward Zulkoski, Ruben Martins, Christoph M. Wintersteiger, Robert Robere, Jia Liang, Krzysztof Czarnecki and Vijay Ganesh
    • CP 2018.
  13. The Proof Complexity of SMT Solvers
    • Robert Robere, Antonina Kolokolova, Vijay Ganesh.
    • CAV 2018.
  14. Lifting Nullstellensatz to Monotone Span Programs over any Field.
  15. Stabbing Planes.
    • Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere.
    • ITCS 2018. [ECCC]
  16. 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.
  17. Strongly Exponential Lower Bounds for Monotone Computation.
  18. Exponential Lower Bounds for Monotone Span Programs.
  19. 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]
  20. Path Graphs, Clique Trees, and Flowers.
    • Lalla Mouatadid and Robert Robere.
    • Manuscript 2015. [ArXiv]
  21. 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.
  22. A Note on Tractability and Artificial Intelligence.
    • Tarek R. Besold and Robert Robere.
    • AGI 2013. [DOI]
  23. Average Case Lower Bounds for Monotone Switching Networks.
    • Stephen A. Cook, Yuval Filmus, Toniann Pitassi, Robert Robere.
    • FOCS 2013. [ECCC]
  24. Complex Analogies: Remarks on the Complexity of HDTP.
    • Tarek R. Besold and Robert Robere.
    • Australasian Conference on Artificial Intelligence (AI 2012). [DOI]
  25. 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