Susanna F. de Rezende
About
I 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
Email:
rezende at math dot cas dot cz
Phone:
+420-222 090 768
Postal address:
Institute of Mathematics AS CR, Žitná 25, 115 67 Praha 1, Czech Republic
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
Other
Main organizer of the workshop Rising Stars at KTH 2019.
|
