Paul Spirakis - Major publications #

Publication list

"The Complexity of the Connected Subgraph Problem" with L Kirousis and M Serna; SIAM J. of Computing, June 1993

"Tail bounds for occupancy and the Satisfiability Threshold Conjecture" with A. Kamath , R. Motwani and K. Palem; J. of Random Structures and Algorithms, 1995.

"BSP vs LOGP" with G Bilardi , A Pietracaprina , G Pucci ,K Herley; Algorithmica Special issue on Parallel Computation, 1999, 24:405-422

"Minimum Congestion Redundant assignments to tolerate Random Faults" wiht D Fotakis; Algorithmica Journal, 2002

"Approximate Equilibria and Ball Fusion", with M. Mavronicolas and E. Koutsoupias; Theory of Computing Systems (TOCS) Journal, TOCS 36, 683-693, 2003, Springer Verlag, New York Inc.

"Space Efficient Hash Tables with Worst Case Constant Access Time" with D. Fotakis, P. Sanders , Rasmus Pagh; Theory of Computer Systems Journal (TOCS), Special issue for best papers of STACS 03, vol 38(2) pp 229-248 , 2005.

"Selfish Unsplittable Flows" with S. Kontogiannis and D. Fotakis; Theoretical Computer Science (TCS) Track A, Elsevier Press, 2005, TCSA 348(2005) pp 226-239

"Max-Min fair flow control sensitive to priorities" with P. Fatourou and M. Mavronicolas; Journal of Interconnection Networks (JOIN) , World-Scientific Publ., Summer 2005.

"Random Sampling of colourings of Sparse Random Graphs with a Constant number of colours" with Ch. Eythymiou; Journal of Theoretical Computer Science, TCS 407, pp 134-154 , Elsevier, Nov. 2008.

"An Optimization Approach for Approximate Nash Equilibria" with H. Tsaknakis; Journal Internet Mathematics, 2009.