Piotr Berman, Marek Karpinski

We give improved trade-off results on approximating general

minimum cost scheduling problems.

Piotr Berman, Marek Karpinski, Yakov Nekrich

We prove upper and lower bounds for computing Merkle tree

traversals, and display optimal trade-offs between time

and space complexity of that problem.

Christoph Berkholz, Jakob NordstrÃ¶m

We show that there are CNF formulas which can be refuted in resolution

in both small space and small width, but for which any small-width

proof must have space exceeding by far the linear worst-case upper

bound. This significantly strengthens the space-width trade-offs in

[Ben-Sasson '09]}, and provides one more ...
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 >>>