Robert Robere

According to our database, Robert Robere authored at least 39 papers between 2012 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\).

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

SIAM J. Comput., 2024

Black-Box PPP Is Not Turing-Closed.

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Intersection Classes in TFNP and Proof Complexity.

Yuhao Li, William Pires, Robert Robere

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

On Pigeonhole Principles and Ramsey in TFNP.

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

On Low-End Obfuscation and Learning.

Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, Gal Yehuda

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Colourful TFNP and Propositional Proofs.

Ben Davis, Robert Robere

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Guest Column: Proofs, Circuits, and Communication.

Susanna F. de Rezende, Mika Göös, Robert Robere

SIGACT News, 2022

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

J. ACM, 2022

Proofs, Circuits, and Communication.

Susanna F. de Rezende, Mika Göös, Robert Robere

CoRR, 2022

Extremely Deep Proofs.

Noah Fleming, Toniann Pitassi, Robert Robere

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

On Semi-Algebraic Proofs and Algorithms.

Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Pseudorandom Self-Reductions for NP-Complete Problems.

Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Separations in Proof Complexity and TFNP.

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Further Collapses in TFNP.

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Automating algebraic proof systems is NP-hard.

Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms.

Robert Robere, Jeroen Zuiddam

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

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

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Lower Bounds for (Non-Monotone) Comparator Circuits.

Anna Gál, Robert Robere

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.

Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

KRW Composition Theorems via Lifting.

Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna F. de Rezende

Electron. Colloquium Comput. Complex., 2019

Adventures in Monotone Complexity and TFNP.

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling.

Susanna F. de Rezende, Jakob Nordström, Or Meir, Robert Robere

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Unified Lower Bounds for Monotone Computation.

Robert Robere

PhD thesis, 2018

Lifting nullstellensatz to monotone span programs over any field.

Toniann Pitassi, Robert Robere

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Stabbing Planes.

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Learning-Sensitive Backdoors with Restarts.

Edward Zulkoski, Ruben Martins, Christoph M. Wintersteiger, Robert Robere, Jia Hui Liang, Krzysztof Czarnecki, Vijay Ganesh

Proceedings of the Principles and Practice of Constraint Programming, 2018

The Proof Complexity of SMT Solvers.

Robert Robere, Antonina Kolokolova, Vijay Ganesh

Proceedings of the Computer Aided Verification - 30th International Conference, 2018

2017

Random CNFs are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Relating Complexity-theoretic Parameters with SAT Solver Performance.

Edward Zulkoski, Ruben Martins, Christoph M. Wintersteiger, Robert Robere, Jia Liang, Krzysztof Czarnecki, Vijay Ganesh

CoRR, 2017

Strongly exponential lower bounds for monotone computation.

Toniann Pitassi, Robert Robere

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Random Θ(log n)-CNFs Are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Exponential Lower Bounds for Monotone Span Programs.

Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Path Graphs, Clique Trees, and Flowers.

Lalla Mouatadid, Robert Robere

CoRR, 2015

2013

When Thinking Never Comes to a Halt: Using Formal Methods in Making Sure Your AI Gets the Job Done Good Enough.

Tarek R. Besold, Robert Robere

Proceedings of the Fundamental Issues of Artificial Intelligence, 2013

Average Case Lower Bounds for Monotone Switching Networks.

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

A Note on Tractability and Artificial Intelligence.

Tarek Richard Besold, Robert Robere

Proceedings of the Artificial General Intelligence - 6th International Conference, 2013

When Almost Is Not Even Close: Remarks on the Approximability of HDTP.

Tarek Richard Besold, Robert Robere

Proceedings of the Artificial General Intelligence - 6th International Conference, 2013

2012

Complex Analogies: Remarks on the Complexity of HDTP.

Robert Robere, Tarek Richard Besold

Proceedings of the AI 2012: Advances in Artificial Intelligence, 2012