12 citations · 12 across the 3 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2012
Scrabble is PSPACE-Complete
Michael Lampis, Valia Mitsou, Karolina Sołtys
In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Eri…
cs.CC2011★ 12 cited
Hierarchies of Inefficient Kernelizability
Danny Hermelin, Stefan Kratsch, Karolina Sołtys +2
The framework of Bodlaender et al. (ICALP 2008) and Fortnow and Santhanam (STOC 2008) allows us to exclude the existence of polynomial kernels for a range of problems under reasona…
cs.CC2011
The hardness of Median in the synchronized bit communication model
Karolina Sołtys
The synchronized bit communication model, defined recently by Impagliazzo and Williams in \emph{Communication complexity with synchronized clocks}, CCC '10, is a communication mode…