Prof Paul Spirakis PhD - Member of Academia Europaea

Professor in Computer Science Computer Science

    Publications

    2017

    A 3-player protocol preventing persistence in strategic contention with limited feedback (Conference Paper)

    Christodoulou, G., Gairing, M., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (n.d.). A 3-player protocol preventing persistence in strategic contention with limited feedback. Retrieved from http://arxiv.org/abs/1707.01439v1

    Binary search in graphs revisited (Conference Paper)

    Deligkas, A., Mertzios, G. B., & Spirakis, P. G. (2017). Binary search in graphs revisited. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 83. doi:10.4230/LIPIcs.MFCS.2017.20

    DOI: 10.4230/LIPIcs.MFCS.2017.20

    Connectivity preserving network transformers (Journal article)

    Michail, O., & Spirakis, P. G. (2017). Connectivity preserving network transformers. THEORETICAL COMPUTER SCIENCE, 671, 36-55. doi:10.1016/j.tcs.2016.02.040

    DOI: 10.1016/j.tcs.2016.02.040

    Determining majority in networks with local interactions and very small local memory (Journal article)

    Mertzios, G. B., Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2017). Determining majority in networks with local interactions and very small local memory. DISTRIBUTED COMPUTING, 30(1), 1-16. doi:10.1007/s00446-016-0277-8

    DOI: 10.1007/s00446-016-0277-8

    Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values (Conference Paper)

    Melissourgos, T., & Spirakis, P. (n.d.). Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values. Retrieved from http://arxiv.org/abs/1701.08108v1

    How many cooks spoil the soup? (Journal article)

    Michail, O., & Spirakis, P. G. (n.d.). How many cooks spoil the soup?. Distributed Computing. doi:10.1007/s00446-017-0317-z

    DOI: 10.1007/s00446-017-0317-z

    Network Constructors: A Model for Programmable Matter (Conference Paper)

    Michail, O., & Spirakis, P. G. (2017). Network Constructors: A Model for Programmable Matter. In SOFSEM 2017: THEORY AND PRACTICE OF COMPUTER SCIENCE Vol. 10139 (pp. 15-34). doi:10.1007/978-3-319-51963-0_3

    DOI: 10.1007/978-3-319-51963-0_3

    On the Chromatic Number of Non-Sparse Random Intersection Graphs (Journal article)

    Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2017). On the Chromatic Number of Non-Sparse Random Intersection Graphs. THEORY OF COMPUTING SYSTEMS, 60(1), 112-127. doi:10.1007/s00224-016-9733-x

    DOI: 10.1007/s00224-016-9733-x

    On the Transformation Capability of Feasible Mechanisms for Programmable Matter (Conference Paper)

    Michail, O., Skretas, G., & Spirakis, P. G. (n.d.). On the Transformation Capability of Feasible Mechanisms for Programmable Matter. Retrieved from http://arxiv.org/abs/1703.04381v1

    Population protocols for majority in arbitrary networks (Journal article)

    Mertzios, G. B., Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2017). Population protocols for majority in arbitrary networks. Trends in Mathematics, 6, 77-82. doi:10.1007/978-3-319-51753-7_13

    DOI: 10.1007/978-3-319-51753-7_13

    Resolving Braess's Paradox in Random Networks (Journal article)

    Fotakis, D., Kaporis, A. C., Lianeas, T., & Spirakis, P. G. (2017). Resolving Braess's Paradox in Random Networks. ALGORITHMICA, 78(3), 788-818. doi:10.1007/s00453-016-0175-2

    DOI: 10.1007/s00453-016-0175-2

    Temporal flows in Temporal networks (Conference Paper)

    Akrida, E. C., Czyzowicz, J., Gasieniec, L., Kuszner, L., & Spirakis, P. G. (n.d.). Temporal flows in Temporal networks. Retrieved from http://arxiv.org/abs/1606.01091v2

    The Complexity of Optimal Design of Temporally Connected Graphs (Journal article)

    Akrida, E. C., Gasieniec, L., Mertzios, G. B., & Spirakis, P. G. (2017). The Complexity of Optimal Design of Temporally Connected Graphs. THEORY OF COMPUTING SYSTEMS, 61(3), 907-944. doi:10.1007/s00224-017-9757-x

    DOI: 10.1007/s00224-017-9757-x

    The computational complexity of weighted greedy matching (Conference Paper)

    Deligkas, A., Mertzios, G. B., & Spirakis, P. G. (2017). The computational complexity of weighted greedy matching. In 31st AAAI Conference on Artificial Intelligence, AAAI 2017 (pp. 466-472).

    2016

    Algorithms and Almost Tight Results for -Colorability of Small Diameter Graphs (Journal article)

    Mertzios, G. B., & Spirakis, P. G. (2016). Algorithms and Almost Tight Results for -Colorability of Small Diameter Graphs. ALGORITHMICA, 74(1), 385-414. doi:10.1007/s00453-014-9949-6

    DOI: 10.1007/s00453-014-9949-6

    Connectivity Preserving Network Transformers (Conference Paper)

    Michail, O., & Spirakis. (n.d.). Connectivity Preserving Network Transformers. In Emergence, Complexity and Computation Vol. 24 (pp. 337-359).

    Deterministic population protocols for exact majority and plurality (Conference Paper)

    Gasieniec, L., Hamilton, D., Martin, R., Spirakis, P. G., & Stachowiak, G. (2017). Deterministic population protocols for exact majority and plurality. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 70 (pp. 14.1-14.14). doi:10.4230/LIPIcs.OPODIS.2016.14

    DOI: 10.4230/LIPIcs.OPODIS.2016.14

    Ephemeral networks with random availability of links: The case of fast networks (Journal article)

    Akrida, E. C., Gasieniec, L., Mertzios, G. B., & Spirakis, P. G. (2016). Ephemeral networks with random availability of links: The case of fast networks. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 87, 109-120. doi:10.1016/j.jpdc.2015.10.002

    DOI: 10.1016/j.jpdc.2015.10.002

    How Many Cooks Spoil the Soup? (Conference Paper)

    Michail, O., & Spirakis, P. G. (2016). How Many Cooks Spoil the Soup?. In Structural Information and Communication Complexity, SIROCCO 2016 Vol. 9988 (pp. 3-18). doi:10.1007/978-3-319-48314-6_1

    DOI: 10.1007/978-3-319-48314-6_1

    On the Complexity of Weighted Greedy Matchings (Journal article)

    Deligkas, A., Mertzios, G. B., & Spirakis, P. G. (n.d.). On the Complexity of Weighted Greedy Matchings. Retrieved from http://arxiv.org/abs/1602.05909v2

    Simple and efficient local codes for distributed stable network construction (Journal article)

    Michail, O., & Spirakis, P. G. (2016). Simple and efficient local codes for distributed stable network construction. DISTRIBUTED COMPUTING, 29(3), 207-237. doi:10.1007/s00446-015-0257-1

    DOI: 10.1007/s00446-015-0257-1

    Stably computing order statistics with arithmetic population protocols (Conference Paper)

    Mertzios, G. B., Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2016). Stably computing order statistics with arithmetic population protocols. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 58. doi:10.4230/LIPIcs.MFCS.2016.68

    DOI: 10.4230/LIPIcs.MFCS.2016.68

    Strategic Contention Resolution with Limited Feedback (Conference Paper)

    Christodoulou, G., Gairing, M., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (n.d.). Strategic Contention Resolution with Limited Feedback. Retrieved from http://arxiv.org/abs/1606.06580v1

    Strategic Contention Resolution with Limited Feedback (Conference Paper)

    Gairing, M., Christodoulou, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2016). Strategic Contention Resolution with Limited Feedback. In Leibniz International Proceedings in Informatics (LIPIcs) (pp. 30:1-30:16). Aarhus. doi:10.4230/LIPIcs.ESA.2016.30

    DOI: 10.4230/LIPIcs.ESA.2016.30

    Temporal Graphs (Thesis / Dissertation)

    Akrida, E. (2016, November 15). Temporal Graphs.

    Traveling salesman problems in temporal graphs (Journal article)

    Michail, O., & Spirakis, P. G. (2016). Traveling salesman problems in temporal graphs. THEORETICAL COMPUTER SCIENCE, 634, 1-23. doi:10.1016/j.tcs.2016.04.006

    DOI: 10.1016/j.tcs.2016.04.006

    2015

    Designing and Testing Temporally Connected Graphs. (Journal article)

    Akrida, E. C., Gasieniec, L., Mertzios, G. B., & Spirakis, P. G. (2015). Designing and Testing Temporally Connected Graphs.. CoRR, abs/1502.04579.

    NETCS: A New Simulator of Population Protocols and Network Constructors (Journal article)

    Amaxilatis, D., Logaras, M., Michail, O., & Spirakis, P. G. (n.d.). NETCS: A New Simulator of Population Protocols and Network Constructors. Retrieved from http://arxiv.org/abs/1508.06731v1

    On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols (Conference Paper)

    Czyzowicz, J., Gasieniec, L., Kosowski, A., Kranakis, E., Spirakis, P. G., & Uznanski, P. (2015). On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols. In Automata, Languages, and Programming, Pt I Vol. 9134 (pp. 393-405). doi:10.1007/978-3-662-47672-7_32

    DOI: 10.1007/978-3-662-47672-7_32

    On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols. (Conference Paper)

    Czyzowicz, J., Gasieniec, L., Kosowski, A., Kranakis, E., Spirakis, P. G., & Uznanski, P. (2015). On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols.. In M. M. Halldórsson, K. Iwama, N. Kobayashi, & B. Speckmann (Eds.), ICALP (1) Vol. 9134 (pp. 393-405). Springer. doi:10.1007/978-3-662-47672-7_32

    DOI: 10.1007/978-3-662-47672-7_32

    On Equilibrium Computation in Biased Games with Quadratic Penalties. (Journal article)

    Deligkas, A., & Spirakis, P. G. (2015). On Equilibrium Computation in Biased Games with Quadratic Penalties.. CoRR, abs/1509.02023.

    On Temporally Connected Graphs of Small Cost (Conference Paper)

    Akrida, E. C., Gasieniec, L., Mertzios, G. B., & Spirakis, P. G. (2015). On Temporally Connected Graphs of Small Cost. In APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2015 Vol. 9499 (pp. 84-96). doi:10.1007/978-3-319-28684-6_8

    DOI: 10.1007/978-3-319-28684-6_8

    On the structure of equilibria in basic network formation (Journal article)

    Nikoletseas, S., Panagopoulou, P., Raptopoulos, C., & Spirakis, P. G. (2015). On the structure of equilibria in basic network formation. THEORETICAL COMPUTER SCIENCE, 590, 96-105. doi:10.1016/j.tcs.2015.03.029

    DOI: 10.1016/j.tcs.2015.03.029

    On verifying and maintaining connectivity of interval temporal networks (Conference Paper)

    Akrida, E. C., & Spirakis, P. G. (2015). On verifying and maintaining connectivity of interval temporal networks. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 9536 (pp. 142-154). doi:10.1007/978-3-319-28472-9_11

    DOI: 10.1007/978-3-319-28472-9_11

    Rationality authority for provable rational behavior (Conference Paper)

    Dolev, S., Panagopoulou, P. N., Rabie, M., Schiller, E. M., & Spirakis, P. G. (2015). Rationality authority for provable rational behavior. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 9295 (pp. 33-48). doi:10.1007/978-3-319-24024-4_5

    DOI: 10.1007/978-3-319-24024-4_5

    Simple and efficient local codes for distributed stable network construction (Journal article)

    Michail, O., & Spirakis, P. G. (2016). Simple and efficient local codes for distributed stable network construction. Distributed Computing, 29(3), 207-237. doi:10.1007/s00446-015-0257-4

    DOI: 10.1007/s00446-015-0257-4

    Terminating population protocols via some minimal global knowledge assumptions (Journal article)

    Michail, O., & Spirakis, P. G. (2015). Terminating population protocols via some minimal global knowledge assumptions. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 81-82, 1-10. doi:10.1016/j.jpdc.2015.02.005

    DOI: 10.1016/j.jpdc.2015.02.005

    The match-maker: Constant-space distributed majority via random walks (Conference Paper)

    Gąsieniec, L., Hamilton, D. D., Martin, R., & Spirakis, P. G. (2015). The match-maker: Constant-space distributed majority via random walks. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 9212 (pp. 67-80). doi:10.1007/978-3-319-21741-3_5

    DOI: 10.1007/978-3-319-21741-3_5

    2014

    Approximating Fixation Probabilities in the Generalized Moran Process (Journal article)

    Diaz, J., Goldberg, L. A., Mertzios, G. B., Richerby, D., Serna, M., & Spirakis, P. G. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. ALGORITHMICA, 69(1), 78-91. doi:10.1007/s00453-012-9722-7

    DOI: 10.1007/s00453-012-9722-7

    Causality, influence, and computation in possibly disconnected synchronous dynamic networks (Journal article)

    Michail, O., Chatzigiannakis, I., & Spirakis, P. G. (2014). Causality, influence, and computation in possibly disconnected synchronous dynamic networks. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 74(1), 2016-2026. doi:10.1016/j.jpdc.2013.07.007

    DOI: 10.1016/j.jpdc.2013.07.007

    Computing Approximate Nash Equilibria in Polymatrix Games (Conference Paper)

    Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. (2014). Computing Approximate Nash Equilibria in Polymatrix Games. In WEB AND INTERNET ECONOMICS Vol. 8877 (pp. 58-71). Retrieved from http://gateway.webofknowledge.com/

    Computing Approximate Nash Equilibria in Polymatrix Games (Journal article)

    Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. (2017). Computing Approximate Nash Equilibria in Polymatrix Games. ALGORITHMICA, 77(2), 487-514. doi:10.1007/s00453-015-0078-7

    DOI: 10.1007/s00453-015-0078-7

    Determining Majority in Networks with Local Interactions and Very Small Local Memory (Conference Paper)

    Mertzios, G. B., Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2014). Determining Majority in Networks with Local Interactions and Very Small Local Memory. In AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP 2014), PT I Vol. 8572 (pp. 871-882). Retrieved from http://gateway.webofknowledge.com/

    Ephemeral networks with random availability of links: Diameter and connectivity (Conference Paper)

    Akrida, E. C., Mertzios, G. B., Ga̧sieniec, L., & Spirakis, P. G. (2014). Ephemeral networks with random availability of links: Diameter and connectivity. In Annual ACM Symposium on Parallelism in Algorithms and Architectures (pp. 267-276). doi:10.1145/2612669.2612693

    DOI: 10.1145/2612669.2612693

    Information security for sensors by overwhelming random sequences and permutations (Journal article)

    Dolev, S., Gilboa, N., Kopeetsky, M., Persiano, G., & Spirakis, P. G. (2014). Information security for sensors by overwhelming random sequences and permutations. AD HOC NETWORKS, 12, 193-200. doi:10.1016/j.adhoc.2011.09.002

    DOI: 10.1016/j.adhoc.2011.09.002

    On the hardness of network design for bottleneck routing games (Journal article)

    Fotakis, D., Kaporis, A. C., Lianeas, T., & Spirakis, P. G. (2014). On the hardness of network design for bottleneck routing games. THEORETICAL COMPUTER SCIENCE, 521, 107-122. doi:10.1016/j.tcs.2013.11.035

    DOI: 10.1016/j.tcs.2013.11.035

    Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof) (Journal article)

    Panagopoulou, P. N., & Spirakis, P. G. (2014). Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof). THEORY OF COMPUTING SYSTEMS, 54(3), 479-490. doi:10.1007/s00224-013-9446-3

    DOI: 10.1007/s00224-013-9446-3

    Simple and Efficient Local Codes for Distributed Stable Network Construction (Conference Paper)

    Michail, O., & Spirakis, P. G. (n.d.). Simple and Efficient Local Codes for Distributed Stable Network Construction. Retrieved from http://arxiv.org/abs/1309.6978v2

    Traveling Salesman Problems in Temporal Graphs (Conference Paper)

    Michail, O., & Spirakis, P. G. (2014). Traveling Salesman Problems in Temporal Graphs. In MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE, PT II Vol. 8635 (pp. 553-564). Retrieved from http://gateway.webofknowledge.com/

    2013

    Moving in temporal graphs with very sparse random availability of edges (Journal article)

    Spirakis, P. G., & Akrida, E. C. (n.d.). Moving in temporal graphs with very sparse random availability of edges. Retrieved from http://arxiv.org/abs/1310.7898v1

    2010

    Passively Mobile Communicating Logarithmic Space Machines (Journal article)

    Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., & Spirakis, P. G. (n.d.). Passively Mobile Communicating Logarithmic Space Machines. Retrieved from http://arxiv.org/abs/1004.3395v1

    2009

    On the Performance of Approximate Equilibria in Congestion Games. (Conference Paper)

    Christodoulou, G., Koutsoupias, E., & Spirakis, P. G. (2009). On the Performance of Approximate Equilibria in Congestion Games.. In ESA (pp. 251-262). Copenhagen: Springer.

    2008

    Random sampling of colourings of sparse random graphs with a constant number of colours (Journal article)

    Efthymiou, C., & Spirakis, P. G. (n.d.). Random sampling of colourings of sparse random graphs with a constant number of colours. doi:10.1016/j.tcs.2008.05.008

    DOI: 10.1016/j.tcs.2008.05.008

    Untitled Document