Computer Science and Discrete Mathematics (CSDM)
Arithmetic complexity is considered (for many good reasons) simpler to understand than Boolean complexity. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive.
This paper proves the first super-logarithmic lower bounds on the cell-probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.
Communication complexity studies the minimal amount of information two parties need to exchange to compute a joint function of their inputs. Results, especially lower bounds in this basic model found applications in many other areas of computer science.