2 citations · 3 across the 3 of their papers we have counts for
4 papers
Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
Susanna F. de Rezende, David Engström, Yassine Ghannane +2
We study the average-case hardness of establishing that a graph does not have a large clique in both proof and communication complexity. We show exponential lower bounds on the len…
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett +2
We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any circuit must have depth super-linear or even s…
Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions
Carola Doerr, Duri Andrea Janett, Johannes Lengler
In a seminal paper in 2013, Witt showed that the (1+1) Evolutionary Algorithm with standard bit mutation needs time to find the optimum of any linear function…
Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard
Duri Janett, Johannes Lengler
In this paper we show how to use drift analysis in the case of two random variables , when the drift is approximatively given by for a matrix . Th…