← go back

all research papers

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