Exponential lower bounds for monotone span programs R Robere, T Pitassi, B Rossman, SA Cook 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS …, 2016 | 73 | 2016 |
Lifting Nullstellensatz to monotone span programs over any field T Pitassi, R Robere Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018 | 55 | 2018 |
Strongly exponential lower bounds for monotone computation T Pitassi, R Robere Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 53 | 2017 |
Adventures in monotone complexity and TFNP M Göös, P Kamath, R Robere, D Sokolov 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), 2019 | 46 | 2019 |
Interior point methods and linear programming R Robere University of Toronto, 1-15, 2012 | 46 | 2012 |
Stabbing planes P Beame, N Fleming, R Impagliazzo, A Kolokolova, D Pankratov, T Pitassi, ... arXiv preprint arXiv:1710.03219, 2017 | 31 | 2017 |
Lifting with simple gadgets and applications to circuit and proof complexity S de Rezende, O Meir, J Nordström, T Pitassi, R Robere, M Vinyals 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 24-30, 2020 | 28 | 2020 |
Random θ (log n)-CNFs are hard for cutting planes N Fleming, D Pankratov, T Pitassi, R Robere 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017 | 25 | 2017 |
The proof complexity of SMT solvers R Robere, A Kolokolova, V Ganesh Computer Aided Verification: 30th International Conference, CAV 2018, Held …, 2018 | 22 | 2018 |
Separations in proof complexity and TFNP M Göös, A Hollender, S Jain, G Maystre, W Pires, R Robere, R Tao 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS …, 2022 | 21 | 2022 |
Automating algebraic proof systems is NP-hard SF de Rezende, M Göös, J Nordström, T Pitassi, R Robere, D Sokolov Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021 | 21 | 2021 |
Further Collapses in TFNP M Göös, A Hollender, S Jain, G Maystre, W Pires, R Robere, R Tao arXiv preprint arXiv:2202.07761, 2022 | 20 | 2022 |
KRW Composition Theorems via Lifting SF de Rezende, O Meir, J Nordström, T Pitassi, R Robere 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 43-49, 2020 | 19 | 2020 |
Average case lower bounds for monotone switching networks Y Filmus, T Pitassi, R Robere, SA Cook 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 598-607, 2013 | 16 | 2013 |
A dynamic algorithm for loop detection in software defined networks D Kordalewski, R Robere University of Toronto, Tech. Rep, 2012 | 15 | 2012 |
Amortized circuit complexity, formal complexity measures, and catalytic algorithms R Robere, J Zuiddam 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS …, 2022 | 14 | 2022 |
On the Power and Limitations of Branch and Cut N Fleming, M Göös, R Impagliazzo, T Pitassi, R Robere, LY Tan, ... arXiv preprint arXiv:2102.05019, 2021 | 14 | 2021 |
Guest Column: Proofs, Circuits, and Communication SF de Rezende, M Göös, R Robere ACM SIGACT News 53 (1), 59-82, 2022 | 13 | 2022 |
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling SF De Rezende, O Meir, J Nordström, R Robere computational complexity 30 (1), 1-45, 2021 | 12 | 2021 |
Unified lower bounds for monotone computation R Robere University of Toronto (Canada), 2018 | 12 | 2018 |