All reports by Author Susanna de Rezende:

__
TR20-099
| 6th July 2020
__

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere#### KRW Composition Theorems via Lifting

__
TR20-064
| 2nd May 2020
__

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende#### Automating Algebraic Proof Systems is NP-Hard

Revisions: 1

__
TR20-001
| 31st December 2019
__

Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende#### Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Revisions: 2

__
TR19-186
| 31st December 2019
__

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende#### Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Revisions: 4

__
TR19-174
| 2nd December 2019
__

Susanna de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov#### Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f ... more >>>

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende

We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula $F$, it is NP-hard to find a refutation of $F$ in the Nullstellensatz, Polynomial Calculus, or Sherali--Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a ... more >>>

Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ ... more >>>

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open ... more >>>

Susanna de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov

We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as in [Ben-Sasson and Wigderson '01] and highly unbalanced, dense ... more >>>