13 citations · 46 across the 31 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.DM2012★ 3 cited
Local Improvement Gives Better Expanders
Michael Lampis
It has long been known that random regular graphs are with high probability good expanders. This was first established in the 1980s by Bollobás by directly calculating the probabil…
cs.CC2012
Improved Inapproximability for TSP
Michael Lampis
The Traveling Salesman Problem is one of the most studied problems in computational complexity and its approximability has been a long standing open question. Currently, the best k…
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…