## Susanna F. de Rezende
Credit: Annie Raymond ## AboutI work on computational complexity, with primary focus on proof complexity. I am currently a postdoc at the Institute of Mathematics of the Czech Academy of Sciences, Prague, Czech Republic, hosted by Prof. Pavel Pudlák with a grant from the Knut and Alice Wallenberg Foundation. I am also a research fellow at the Satisfiability: Theory, Practice and Beyond Program at the Simons Institute, University of California, Berkeley, USA. Prior to that I was a PhD student of Prof. Jakob Nordström in the Theoretical Computer Science Group at KTH Royal Institute of Technology in Stockholm, Sweden. I received the Stockholm Mathematics Centre Prize for Excellent Doctoral Dissertation 2018/2019. In 2018, I was a research fellow at the Lower Bounds in Computational Complexity Program at the Simons Institute, University of California, Berkeley, USA. During my Master's studies, I worked on graph theory under the supervision of Prof. Yoshiko Wakabayashi at the Institute of Mathematics and Statistics at University of São Paulo, Brazil. My cv: PDF
(updated February 2021)
## Contact Info
## Papers-
Susanna F. de Rezende.
**Automating Tree-Like Resolution in Time n^o(log n) Is ETH-Hard.**Submitted manuscript, 2021. -
Susanna F. de Rezende, Or Meir, Jakob Nordström, and Robert Robere.
**Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling**.*computational complexity*,**30**, 4 (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**. To appear in STOC '21. -
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, and Robert Robere.
**KRW Composition Theorems via Lifting**. In*Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20)*, November 2020. (Full version.) -
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. (Full version.) -
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. (Full version.) -
Susanna F. de Rezende, Or Meir, Jakob Nordström, and Robert Robere.
**Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling**. In*Proceedings of the 34th Computational Complexity Conference (CCC '19)*, July 2019. -
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Jakob Nordström, Massimo Lauria, and Alexander Razborov.
**Clique Is Hard on Average for Regular Resolution**. In*Proceedings of the 50th Annual ACM Symposiumn on Theory of Computing (STOC '18)*, June 2018. (Full version.) -
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. -
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**. In*Theoretical Computer Science,***566**59-75, February 2015. -
Susanna F. de Rezende, Cristina G. Fernandes, Daniel M. Martins, and Yoshiko Wakabayashi.
**Intersecting Longest Paths**. In*Discrete Mathematics,***313**1401-1408, June 2013. -
Susanna F. de Rezende, Cristina G. Fernandes, Daniel M. Martins, and Yoshiko Wakabayashi.
Intersection of Longest Paths in a Graph.
In
*Electronic Notes in Discrete Mathematics (EuroComb '11)***38**743-748, December 2011.
## Thesis- PhD thesis: Lower Bounds and Trade-offs in Proof Complexity, June 2019. Received the Stockholm Mathematics Centre Prize for Excellent Doctoral Dissertation 2018/2019.
- MSc dissertation: Caminhos mais longos em grafos (Longest paths in graphs), May 2014. (Summary, also in Portuguese.) Selected among the top 10 in Brazil in the area of Computer Science in 2014 by the Brazilian Society of Computation (SBC).
## OtherMain organizer of the workshop Rising Stars at KTH 2019. |