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

KRW Composition Theorems via Lifting.

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

Comput. Complex., June, 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

Electron. Colloquium Comput. Complex., 2024

On Pigeonhole Principles and Ramsey in TFNP.

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

Electron. Colloquium Comput. Complex., 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

2023

Colourful TFNP and Propositional Proofs.

Ben Davis, Robert Robere

Electron. Colloquium Comput. Complex., 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

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

Separations in Proof Complexity and TFNP.

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

Electron. Colloquium Comput. Complex., 2022

Further Collapses in TFNP.

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

Electron. Colloquium Comput. Complex., 2022

On Semi-Algebraic Proofs and Algorithms.

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

Electron. Colloquium Comput. Complex., 2022

Proofs, Circuits, and Communication.

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

CoRR, 2022

2021

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

Robert Robere, Jeroen Zuiddam

Electron. Colloquium Comput. Complex., 2021

Extremely Deep Proofs.

Noah Fleming, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 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

Electron. Colloquium Comput. Complex., 2021

Pseudorandom Self-Reductions for NP-Complete Problems.

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

Electron. Colloquium Comput. Complex., 2021

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling.

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

Comput. Complex., 2021

2020

Automating Algebraic Proof Systems is NP-Hard.

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

Electron. Colloquium Comput. Complex., 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

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

Lower Bounds for (Non-monotone) Comparator Circuits.

Anna Gál, Robert Robere

Electron. Colloquium Comput. Complex., 2019

2018

Unified Lower Bounds for Monotone Computation.

Robert Robere

PhD thesis, 2018

Adventures in Monotone Complexity and TFNP.

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

Electron. Colloquium Comput. Complex., 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

Lifting Nullstellensatz to Monotone Span Programs over Any Field.

Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Random CNFs are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Stabbing Planes.

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, 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

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

Strongly Exponential Lower Bounds for Monotone Computation.

Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2016

Exponential Lower Bounds for Monotone Span Programs.

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

Electron. Colloquium Comput. Complex., 2016

2015

Path Graphs, Clique Trees, and Flowers.

Lalla Mouatadid, Robert Robere

CoRR, 2015

2013

Average Case Lower Bounds for Monotone Switching Networks.

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

Electron. Colloquium Comput. Complex., 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

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