Ausgabe 2/2021
Inhalt (7 Artikel)
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity
Toniann Pitassi, Morgan Shirley, Thomas Watson
Open Access
An Exponential Separation Between MA and AM Proofs of Proximity
Tom Gur, Yang P. Liu, Ron D. Rothblum
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
Lower Bounds for Arithmetic Circuits via the Hankel Matrix
Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre
Open Access
Factorization of Polynomials Given by Arithmetic Branching Programs
Amit Sinhababu , Thomas Thierauf
Correction
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov