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.
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.
I was a research fellow at the Simons Institute for the Theory of Computing, University of California, Berkeley for the Satisfiability: Theory, Practice and Beyond Program in 2021 and for the Lower Bounds in Computational Complexity Program in 2018.
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 the
University of São Paulo, Brazil.
My cv: PDF
(updated June 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, 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.
To appear 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.
In
Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20),
November 2020.
(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.
Thesis
Other
Main organizer of the workshop Rising Stars at KTH 2019.
|
