all research papers

1. Lower Bounds for Approximate Sign-Rank
   • Riju Bindua, Hamed Hatami, Hasti Karimi, Robert Robere
   • Manuscript. [ArXiV]
2. Res(log) Proves Bounded-Depth Frege Lower Bounds
   • Ben Davis, Robert Robere
   • Manuscript. [ECCC]
3. On Pigeonhole Principles and Ramsey in TFNP
   • Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun
   • FOCS 2024. [ECCC] [ArXiV]
4. Black-Box PPP is Not Turing-Closed
   • Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere.
   • STOC 2024. [ECCC]
5. Intersection Classes in TFNP and Proof Complexity
   • Yuhao Li, William Pires, Robert Robere
   • ITCS 2024. [DROPS]
6. Colourful TFNP and Propositional Proofs
   • Ben Davis and Robert Robere.
   • CCC 2023. [ECCC]
7. On Low End Obfuscation and Learning
   • Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, Gal Yehuda.
   • ITCS 2023. [DROPS]
8. Separations in Proof Complexity and TFNP
   • Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao.
   • FOCS 2022. [ECCC]
   • Journal of the ACM (2024). [ACM DL]
9. 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.
10. Proofs, Circuits, and Communication
    • Susanna de Rezende, Mika Göös, Robert Robere.
    • SIGACT News Complexity Theory Column, March 2022. [ArXiV] [Talk at BIRS]
11. Extremely Deep Proofs
    • Noah Fleming, Toniann Pitassi, Robert Robere
    • ITCS 2022. [ECCC] [Talk at ITCS]
12. Pseudorandom Self-Reductions for NP-Complete Problems
    • Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda.
    • ITCS 2022. [ECCC] [Talk at ITCS]
13. On Semi-Algebraic Proofs and Algorithms
    • Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere
    • ITCS 2022. [ECCC] [Talk at ITCS]
14. Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
    • Robert Robere, Jeroen Zuiddam.
    • FOCS 2021. [ECCC] [Talk at FOCS] [Talk at IAS]
15. 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.
16. 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]
17. KRW Composition Theorems via Lifting
    • Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere
    • FOCS 2020. [ECCC]
18. 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]
19. Lower Bounds for (Non-monotone) Comparator Circuits
    • Anna Gál, Robert Robere
    • ITCS 2020. [ECCC] [DROPS]
20. Nullstellensatz Size-Degree Trade-Offs from Reversible Pebbling
    • Suzanna F. de Rezende, Or Meir, Jakob Nördstrom, Robert Robere.
    • CCC 2019. [ECCC] [DROPS]
    • Computational Complexity 30, 4 (2021)
21. Adventures in Monotone Complexity and TFNP
    • Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
    • ITCS 2019. [ECCC] [DROPS]
22. Learning-Sensitive Backdoors with Restarts
    • Edward Zulkoski, Ruben Martins, Christoph M. Wintersteiger, Robert Robere, Jia Liang, Krzysztof Czarnecki and Vijay Ganesh
    • CP 2018.
23. The Proof Complexity of SMT Solvers
    • Robert Robere, Antonina Kolokolova, Vijay Ganesh.
    • CAV 2018.
24. Lifting Nullstellensatz to Monotone Span Programs over any Field.
    • Toniann Pitassi, Robert Robere.
    • STOC 2018. [ECCC] [Talk at Simons Institute]
25. Stabbing Planes.
    • Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere.
    • ITCS 2018. [ECCC]
26. 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)
27. Strongly Exponential Lower Bounds for Monotone Computation.
    • Toniann Pitassi, Robert Robere.
    • STOC 2017. [ECCC] [Slides]
28. 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.
29. 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]
30. Path Graphs, Clique Trees, and Flowers.
    • Lalla Mouatadid and Robert Robere.
    • Manuscript 2015. [ArXiv]
31. 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.
32. A Note on Tractability and Artificial Intelligence.
    • Tarek R. Besold and Robert Robere.
    • AGI 2013. [DOI]
33. Average Case Lower Bounds for Monotone Switching Networks.
    • Stephen A. Cook, Yuval Filmus, Toniann Pitassi, Robert Robere.
    • FOCS 2013. [ECCC]
34. Complex Analogies: Remarks on the Complexity of HDTP.
    • Tarek R. Besold and Robert Robere.
    • Australasian Conference on Artificial Intelligence (AI 2012). [DOI]
35. 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

• • Unified Lower Bounds for Monotone Computation
  • Robert Robere
  • PhD Thesis (2018).
  • Awarded the 2019 EATCS Distinguished Dissertation Award.
  • [Download]
• • Average Case Lower Bounds for Monotone Switching Networks
  • Robert Robere
  • Masters Thesis (2013).
  • [Download]