Publications

Papers

Susanna F. de Rezende, Aaron Potechin, and Kilian Risse. Clique Is Hard on Average for Unary Sherali-Adams. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS '23), November 2023.

Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, and Kilian Risse. Graph colouring is hard on average for polynomial calculus and Nullstellensatz. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS '23), November 2023.

Susanna F. de Rezende, Mika Göös, and Robert Robere. Proofs, Circuits, and Communication. SIGACT News Complexity Theory Column 112, volume 53, issue 1, pages 59-82, March 2022. (arXiv)

Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Dmitry Sokolov. The Power of Negative Reasoning. In Proceedings of the 36th Annual Computational Complexity Conference (CCC '21), July 2021.

Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, and Dmitry Sokolov. Automating Algebraic Proof Systems Is NP-Hard. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC '21), June 2021. (ECCC)

Susanna F. de Rezende. Automating Tree-Like Resolution in Time n^o(log n) Is ETH-Hard. In Proceedings of the 11th Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS '21), May 2021. (ECCC)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, and Robert Robere. KRW Composition Theorems via Lifting. computational complexity, volume 33, article 4, April 2024. Preliminary version in FOCS '20. (arXiv, ECCC)

Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, and Marc Vinyals. Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20), November 2020. (arXiv, ECCC)

Susanna F. de Rezende, Jakob Nordström, Kilian Risse, and Dmitry Sokolov. Exponential Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. In Proceedings of the 35th Computational Complexity Conference (CCC '20), July 2020. (ECCC)

Susanna F. de Rezende, Or Meir, Jakob Nordström, and Robert Robere. Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. computational complexity, volume 30, article 4, pages 1-45, February 2021. Preliminary version in CCC '19. (ECCC)

Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Jakob Nordström, Massimo Lauria, and Alexander Razborov. Clique Is Hard on Average for Regular Resolution. Journal of the ACM, volume 68, issue 4, article 23, pages 1-26, June 2021. Preliminary version in STOC '18. (arXiv)

Joël Alwen, Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. Cumulative Space in Black-White Pebbling and Resolution. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS '17), January 2017.

Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS '16), October 2016. (ECCC)
Julio Araujo, Nathann Cohen, Susanna F. de Rezende, Frédéric Havet, and Phablo F.S. Moura. On the Proper Orientation Number of Bipartite Graphs. Theoretical Computer Science, volume 566, pages 59-75, February 2015.
Susanna F. de Rezende, Cristina G. Fernandes, Daniel M. Martins, and Yoshiko Wakabayashi. Intersecting Longest Paths. Discrete Mathematics, volume 313, issue 12, pages 1401-1408, June 2013. Preliminary version in EuroComb '11.