all research papers
No posts yet.
pre-ai
All research papers listed below had their major ideas developed independent of AI.
Provable Reductions in TFNP
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere
Manuscript 2026. [PDF]
Lower Bounds for Approximate Sign-Rank
Riju Bindua, Hamed Hatami, Hasti Karimi, Robert Robere
Manuscript 2026. [ArXiV]
Res(log) Proves Bounded-Depth Frege Lower Bounds
Ben Davis, Robert Robere
Manuscript 2026. [ECCC]
On Pigeonhole Principles and Ramsey in TFNP
Black-Box PPP is Not Turing-Closed
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere.
STOC 2024. [ECCC]
Intersection Classes in TFNP and Proof Complexity
Yuhao Li, William Pires, Robert Robere
ITCS 2024. [DROPS]
Colourful TFNP and Propositional Proofs
Ben Davis and Robert Robere.
CCC 2023. [ECCC]
On Low End Obfuscation and Learning
Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, Gal Yehuda.
ITCS 2023. [DROPS]
Separations in Proof Complexity and TFNP
Further Collapses in TFNP
Proofs, Circuits, and Communication
Susanna de Rezende, Mika Göös, Robert Robere.
SIGACT News Complexity Theory Column, March 2022. [ArXiV] [Talk at BIRS]
Extremely Deep Proofs
Noah Fleming, Toniann Pitassi, Robert Robere
ITCS 2022. [ECCC] [Talk at ITCS]
Pseudorandom Self-Reductions for NP-Complete Problems
Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda.
ITCS 2022. [ECCC] [Talk at ITCS]
On Semi-Algebraic Proofs and Algorithms
Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere
ITCS 2022. [ECCC] [Talk at ITCS]
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
Robert Robere, Jeroen Zuiddam.
FOCS 2021. [ECCC] [Talk at FOCS] [Talk at IAS]
On the Power and Limitations of Branch and Cut
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]
KRW Composition Theorems via Lifting
Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere
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.
FOCS 2020. [ECCC]
Lower Bounds for (Non-monotone) Comparator Circuits
Nullstellensatz Size-Degree Trade-Offs from Reversible Pebbling
Suzanna F. de Rezende, Or Meir, Jakob Nördstrom, Robert Robere.
Adventures in Monotone Complexity and TFNP
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.
Lifting Nullstellensatz to Monotone Span Programs over any Field.
Toniann Pitassi, Robert Robere.
STOC 2018. [ECCC] [Talk at Simons Institute]
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]
J. ACM 69(3) (2022)
Strongly Exponential Lower Bounds for Monotone Computation.
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].