Prof Paul Spirakis PhD - Member of Academia Europaea

Professor in Computer Science Computer Science

    Publications

    2019

    On Verifying and Maintaining Connectivity of Interval Temporal Networks (Journal article)

    Akrida, E., & Spirakis, P. (2019). On Verifying and Maintaining Connectivity of Interval Temporal Networks. Parallel Processing Letters. doi:10.1142/S0129626419500099

    DOI: 10.1142/S0129626419500099

    Connected Subgraph Defense Games (Journal article)

    Akrida, E. C., Deligkas, A., Melissourgos, T., & Spirakis, P. G. (n.d.). Connected Subgraph Defense Games. Retrieved from http://arxiv.org/abs/1906.02774v1

    On the Transformation Capability of Feasible Mechanisms for Programmable Matter (Journal article)

    Michail, O., Skretas, G., & Spirakis, P. G. (2019). On the Transformation Capability of Feasible Mechanisms for Programmable Matter. Journal of Computer and System Sciences.

    Temporal Network Optimization Subject to Connectivity Constraints (Journal article)

    Mertzios, G. B., Michail, O., & Spirakis, P. G. (2019). Temporal Network Optimization Subject to Connectivity Constraints. ALGORITHMICA, 81(4), 1416-1449. doi:10.1007/s00453-018-0478-6

    DOI: 10.1007/s00453-018-0478-6

    Fault Tolerant Network Constructors (Journal article)

    Michail, O., Spirakis, P. G., & Theofilatos, M. (n.d.). Fault Tolerant Network Constructors. Retrieved from http://arxiv.org/abs/1903.05992v2

    How fast can we reach a target vertex in stochastic temporal graphs? (Journal article)

    Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., Spirakis, P. G., & Zamaraev, V. (n.d.). How fast can we reach a target vertex in stochastic temporal graphs?. Retrieved from http://arxiv.org/abs/1903.03636v1

    Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem (Journal article)

    Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (n.d.). Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. Retrieved from http://arxiv.org/abs/1903.03101v1

    Temporal flows in Temporal networks (Journal article)

    Akrida, E., Czyzowicz, J., Gasieniec, L., Kuszner, L., & Spirakis, P. (n.d.). Temporal flows in Temporal networks. Journal of Computer and System Sciences. doi:10.1016/j.jcss.2019.02.003

    DOI: 10.1016/j.jcss.2019.02.003

    THE PRICE OF STABILITY OF WEIGHTED CONGESTION GAMES (Journal article)

    Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P. G. (2019). THE PRICE OF STABILITY OF WEIGHTED CONGESTION GAMES. SIAM JOURNAL ON COMPUTING, 48(5), 1544-1582. doi:10.1137/18M1207880

    DOI: 10.1137/18M1207880

    2018

    Approximating the Existential Theory of the Reals (Conference Paper)

    Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (n.d.). Approximating the Existential Theory of the Reals. Retrieved from http://arxiv.org/abs/1810.01393v2

    How many cooks spoil the soup? (Journal article)

    Michail, O., & Spirakis, P. G. (2018). How many cooks spoil the soup?. DISTRIBUTED COMPUTING, 31(6), 455-469. doi:10.1007/s00446-017-0317-z

    DOI: 10.1007/s00446-017-0317-z

    Strong bounds for evolution in networks (Journal article)

    Mertzios, G. B., & Spirakis, P. G. (2018). Strong bounds for evolution in networks. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 97, 60-82. doi:10.1016/j.jcss.2018.04.004

    DOI: 10.1016/j.jcss.2018.04.004

    Simple and Fast Approximate Counting and Leader Election in Populations (Conference Paper)

    Michail, O., Spirakis, P. G., & Theofilatos, M. (2018). Simple and Fast Approximate Counting and Leader Election in Populations. In Springer LNCS. Tokyo, Japan..

    Cover Time in Edge-Uniform Stochastically-Evolving Graphs (Journal article)

    Lamprou, I., Martin, R., & Spirakis, P. G. (2018). Cover Time in Edge-Uniform Stochastically-Evolving Graphs. Algorithms, 11(10). doi:10.3390/a11100149

    DOI: 10.3390/a11100149

    Brief announcement: Exact size counting in uniform population protocols in nearly logarithmic time (Conference Paper)

    Doty, D., Eftekhari, M., Michail, O., Spirakis, P. G., & Theofilatos, M. (2018). Brief announcement: Exact size counting in uniform population protocols in nearly logarithmic time. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 121. doi:10.4230/LIPIcs.DISC.2018.46

    DOI: 10.4230/LIPIcs.DISC.2018.46

    Short Paper: Strategic Contention Resolution in Multiple Channels with Limited Feedback (Conference Paper)

    Christodoulou, G., Melissourgos, T., & Spirakis, P. G. (2018). Short Paper: Strategic Contention Resolution in Multiple Channels with Limited Feedback. In Unknown Conference (pp. 245-250). Springer International Publishing. doi:10.1007/978-3-319-99660-8_22

    DOI: 10.1007/978-3-319-99660-8_22

    Strategic Contention Resolution in Multiple Channels (Conference Paper)

    Christodoulou, G., Melissourgos, T., & Spirakis, P. G. (n.d.). Strategic Contention Resolution in Multiple Channels. Retrieved from http://arxiv.org/abs/1810.04565v1

    Binary Search in Graphs Revisited (Journal article)

    Spirakis, P. G., Deligkas, A., & mertzios, G. (2018). Binary Search in Graphs Revisited. Algorithmica: an international journal in computer science.

    Temporal Vertex Cover with a Sliding Time Window (Conference Paper)

    Akrida, E. C., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (n.d.). Temporal Vertex Cover with a Sliding Time Window. Retrieved from http://arxiv.org/abs/1802.07103v3

    Preface (Conference Paper)

    Potapov, I., Spirakis, P., & Worrell, J. (2018). Preface. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 117. doi:10.4230/LIPIcs.MFCS.2018.0

    DOI: 10.4230/LIPIcs.MFCS.2018.0

    The Price of Stability of Weighted Congestion Games (Conference Paper)

    Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P. G. (n.d.). The Price of Stability of Weighted Congestion Games. Retrieved from http://arxiv.org/abs/1802.09952v4

    Fast Approximate Counting and Leader Election in Populations (Conference Paper)

    Michail, O., Spirakis, P. G., & Theofilatos, M. (n.d.). Fast Approximate Counting and Leader Election in Populations. Retrieved from http://arxiv.org/abs/1806.02638v1

    Brief Announcement: Providing End-to-End Secure Communication in Low-Power Wide Area Networks (Conference Paper)

    Chatzigiannakis, I., Liagkou, V., & Spirakis, P. G. (2018). Brief Announcement: Providing End-to-End Secure Communication in Low-Power Wide Area Networks. In Unknown Conference (pp. 101-104). Springer International Publishing. doi:10.1007/978-3-319-94147-9_8

    DOI: 10.1007/978-3-319-94147-9_8

    Exact size counting in uniform population protocols in nearly logarithmic time (Journal article)

    Doty, D., Eftekhari, M., Michail, O., Spirakis, P. G., & Theofilatos, M. (n.d.). Exact size counting in uniform population protocols in nearly logarithmic time. Retrieved from http://arxiv.org/abs/1805.04832v1

    The temporal explorer who returns to the base (Journal article)

    Akrida, E. C., Mertzios, G. B., & Spirakis, P. G. (n.d.). The temporal explorer who returns to the base. Retrieved from http://arxiv.org/abs/1805.04713v1

    Mutants and Residents with Different Connection Graphs in the Moran Process. (Conference Paper)

    Melissourgos, T., Nikoletseas, S. E., Raptopoulos, C., & Spirakis, P. G. (2018). Mutants and Residents with Different Connection Graphs in the Moran Process.. In M. A. Bender, M. Farach-Colton, & M. A. Mosteiro (Eds.), LATIN Vol. 10807 (pp. 790-804). Springer. Retrieved from https://doi.org/10.1007/978-3-319-77404-6

    Mutants and Residents with Different Connection Graphs in the Moran Process (Journal article)

    Melissourgos, T., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2018). Mutants and Residents with Different Connection Graphs in the Moran Process. LATIN 2018: THEORETICAL INFORMATICS, 10807, 790-804. doi:10.1007/978-3-319-77404-6_57

    DOI: 10.1007/978-3-319-77404-6_57

    Communications of ACM (CACM) (Journal article)

    Spirakis, P. G., & Michail, O. (2018). Communications of ACM (CACM). Communications of the ACM.

    Elements of the Theory of Dynamic Networks (Journal article)

    Michail, O., & Spirakis, P. G. (2018). Elements of the Theory of Dynamic Networks. COMMUNICATIONS OF THE ACM, 61(2), 72-81. doi:10.1145/3156693

    DOI: 10.1145/3156693

    Brief announcement: Fast approximate counting and leader election in populations (Conference Paper)

    Michail, O., Spirakis, P. G., & Theofilatos, M. (2018). Brief Announcement: Fast Approximate Counting and Leader Election in Populations. In Unknown Conference (pp. 38-42). Springer International Publishing. doi:10.1007/978-3-030-01325-7_7

    DOI: 10.1007/978-3-030-01325-7_7

    Random input helps searching predecessors (Conference Paper)

    Belazzougui, D., Kaporis, A. C., & Spirakis, P. G. (2018). Random input helps searching predecessors. In CEUR Workshop Proceedings Vol. 2113 (pp. 106-115).

    2017

    Cover Time in Edge-Uniform Stochastically-Evolving Graphs (Conference Paper)

    Lamprou, I., Martin, R., & Spirakis, P. (n.d.). Cover Time in Edge-Uniform Stochastically-Evolving Graphs. In Algorithms Vol. 11 (pp. 149). MDPI AG. doi:10.3390/a11100149

    DOI: 10.3390/a11100149

    Cover Time in Edge-Uniform Stochastically-Evolving Graphs (Journal article)

    Lamprou, I., Martin, R., & Spirakis, P. (2017). Cover Time in Edge-Uniform Stochastically-Evolving Graphs. Lecture Notes in Computer Science. Retrieved from http://arxiv.org/abs/1702.05412v5

    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

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

    Spirakis, P. G., Christodoulou, G., Gairing, M., Nikoletseas, S., & Raptopoulos, C. (2017). A 3-player protocol preventing persistence in strategic contention with limited feedback. In LNCS ARCoSS. L'Acquilla Iatly.

    Binary Search in Graphs Revisited (Conference Paper)

    Deligkas, A., Mertzios, G. B., & Spirakis, P. G. (n.d.). Binary Search in Graphs Revisited. Retrieved from http://arxiv.org/abs/1702.08899v2

    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

    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

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

    Melissourgos, T., & Spirakis, P. (2017). Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values. In ALGORITHMS AND COMPLEXITY (CIAC 2017) Vol. 10236 (pp. 418-429). doi:10.1007/978-3-319-57586-5_35

    DOI: 10.1007/978-3-319-57586-5_35

    Temporal flows in temporal networks (Conference Paper)

    Akrida, E. C., Czyzowicz, J., Gasieniec, L., Kuszner, L., & Spirakis, P. G. (2019). Temporal flows in temporal networks. In JOURNAL OF COMPUTER AND SYSTEM SCIENCES Vol. 103 (pp. 46-60). doi:10.1016/j.jcss.2019.02.003

    DOI: 10.1016/j.jcss.2019.02.003

    Temporal Flows in Temporal Networks (Conference Paper)

    Akrida, E. C., Czyzowicz, J., Gasieniec, L., Kuszner, L., & Spirakis, P. G. (2017). Temporal Flows in Temporal Networks. In ALGORITHMS AND COMPLEXITY (CIAC 2017) Vol. 10236 (pp. 43-54). doi:10.1007/978-3-319-57586-5_5

    DOI: 10.1007/978-3-319-57586-5_5

    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

    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

    The Computational Complexity of Weighted Greedy Matching (Conference Paper)

    Deligkas, A., Mertzios, G. B., Spirakis, P. G., & AAAI. (2017). The Computational Complexity of Weighted Greedy Matching. In THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE (pp. 466-472). Retrieved from http://gateway.webofknowledge.com/

    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

    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

    A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback. (Conference Paper)

    Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C., & Spirakis, P. G. (2017). A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback.. In V. Bilò, & M. Flammini (Eds.), SAGT Vol. 10504 (pp. 240-251). Springer. Retrieved from https://doi.org/10.1007/978-3-319-66700-3

    Bounding the Cover Time in Edge-Uniform Stochastic Graphs. (Journal article)

    Lamprou, I., Martin, R., & Spirakis, P. G. (2017). Bounding the Cover Time in Edge-Uniform Stochastic Graphs.. CoRR, abs/1702.05412.

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

    Melissourgos, T., & Spirakis, P. G. (2017). Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values.. In D. Fotakis, A. Pagourtzis, & V. T. Paschos (Eds.), CIAC Vol. 10236 (pp. 418-429). Retrieved from https://doi.org/10.1007/978-3-319-57586-5

    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. Unknown Journal, 77-82. doi:10.1007/978-3-319-51753-7_13

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

    2016

    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

    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).

    How Many Cooks Spoil the Soup ? (Conference Paper)

    Michail, O., & Spirakis, P. G. (2016). How Many Cooks Spoil the Soup ?. In Lecture Notes in Computer Science Vol. 9988 (pp. 1-16). Helsinki , Finland: Springer Verlag (Germany).

    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

    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

    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

    Traveling Salesman Problems in Temporal Graphs (Journal article)

    Spirakis, P. G., & Michail, O. (n.d.). Traveling Salesman Problems in Temporal Graphs. Theoretical Computer Science.

    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

    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

    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

    Flows in Temporal networks. (Journal article)

    Akrida, E. C., Czyzowicz, J., Gasieniec, L., Kuszner, L., & Spirakis, P. G. (2016). Flows in Temporal networks.. CoRR, abs/1606.01091.

    Lipschitz Continuity and Approximate Equilibria (Journal article)

    Deligkas, A., Fearnley, J., & Spirakis, P. (2016). Lipschitz Continuity and Approximate Equilibria. ALGORITHMIC GAME THEORY, SAGT 2016, 9928, 15-26. doi:10.1007/978-3-662-53354-3_2

    DOI: 10.1007/978-3-662-53354-3_2

    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 Unknown Conference (pp. 142-154). Springer International Publishing. doi:10.1007/978-3-319-28472-9_11

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

    Strategic Contention Resolution with Limited Feedback. (Conference Paper)

    Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C., & Spirakis, P. G. (2016). Strategic Contention Resolution with Limited Feedback.. In P. Sankowski, & C. D. Zaroliagis (Eds.), ESA Vol. 57 (pp. 30:1). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Retrieved from http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16013

    2015

    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 Unknown Conference (pp. 33-48). Springer International Publishing. 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

    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

    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 Unknown Conference (pp. 67-80). Springer International Publishing. doi:10.1007/978-3-319-21741-3_5

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

    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.

    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. Retrieved from https://doi.org/10.1007/978-3-662-47672-7

    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

    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

    2014

    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/

    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

    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/

    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 (Conference Paper)

    Akrida, E. C., Gasieniec, L., Mertzios, G. B., & Spirakis, P. G. (2014). Ephemeral networks with random availability of links. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures - SPAA '14. ACM Press. 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

    2013

    Naming and Counting in Anonymous Unknown Dynamic Networks (Conference Paper)

    Michail, O., Chatzigiannakis, I., & Spirakis, P. G. (2013). Naming and Counting in Anonymous Unknown Dynamic Networks. In STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2013 Vol. 8255 (pp. 281-295). Retrieved from http://gateway.webofknowledge.com/

    The computational power of simple protocols for self-awareness on graphs (Journal article)

    Chatzigiannakis, I., Michail, O., Nikolaou, S., & Spirakis, P. G. (2013). The computational power of simple protocols for self-awareness on graphs. THEORETICAL COMPUTER SCIENCE, 512, 98-118. doi:10.1016/j.tcs.2012.08.026

    DOI: 10.1016/j.tcs.2012.08.026

    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

    Temporal Network Optimization Subject to Connectivity Constraints (Conference Paper)

    Mertzios, G. B., Michail, O., Chatzigiannakis, I., & Spirakis, P. G. (2013). Temporal Network Optimization Subject to Connectivity Constraints. In AUTOMATA, LANGUAGES, AND PROGRAMMING, PT II Vol. 7966 (pp. 657-668). Retrieved from http://gateway.webofknowledge.com/

    2012

    Causality, Influence, and Computation in Possibly Disconnected Synchronous Dynamic Networks (Conference Paper)

    Michail, O., Chatzigiannakis, I., & Spirakis, P. G. (2012). Causality, Influence, and Computation in Possibly Disconnected Synchronous Dynamic Networks. In Unknown Conference (pp. 269-283). Springer Berlin Heidelberg. doi:10.1007/978-3-642-35476-2_19

    DOI: 10.1007/978-3-642-35476-2_19

    Brief Announcement: Naming and Counting in Anonymous Unknown Dynamic Networks (Conference Paper)

    Michail, O., Chatzigiannakis, I., & Spirakis, P. G. (2012). Brief Announcement: Naming and Counting in Anonymous Unknown Dynamic Networks. In DISTRIBUTED COMPUTING, DISC 2012 Vol. 7611 (pp. 437-438). Retrieved from http://gateway.webofknowledge.com/

    Terminating Population Protocols via Some Minimal Global Knowledge Assumptions (Conference Paper)

    Michail, O., Chatzigiannakis, I., & Spirakis, P. G. (2012). Terminating Population Protocols via Some Minimal Global Knowledge Assumptions. In Unknown Conference (pp. 77-89). Springer Berlin Heidelberg. doi:10.1007/978-3-642-33536-5_8

    DOI: 10.1007/978-3-642-33536-5_8

    2011

    The Computational Power of Simple Protocols for Self-awareness on Graphs (Conference Paper)

    Chatzigiannakis, I., Michail, O., Nikolaou, S., & Spirakis, P. G. (2011). The Computational Power of Simple Protocols for Self-awareness on Graphs. In STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS Vol. 6976 (pp. 135-147). Retrieved from http://gateway.webofknowledge.com/

    Passively mobile communicating machines that use restricted space (Journal article)

    Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., & Spirakis, P. G. (2011). Passively mobile communicating machines that use restricted space. THEORETICAL COMPUTER SCIENCE, 412(46), 6469-6483. doi:10.1016/j.tcs.2011.07.001

    DOI: 10.1016/j.tcs.2011.07.001

    Passively mobile communicating machines that use restricted space (Conference Paper)

    Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., & Spirakis, P. G. (2011). Passively mobile communicating machines that use restricted space. In Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing - FOMC '11. ACM Press. doi:10.1145/1998476.1998480

    DOI: 10.1145/1998476.1998480

    Mediated population protocols (Journal article)

    Michail, O., Chatzigiannakis, I., & Spirakis, P. G. (2011). Mediated population protocols. THEORETICAL COMPUTER SCIENCE, 412(22), 2434-2450. doi:10.1016/j.tcs.2011.02.003

    DOI: 10.1016/j.tcs.2011.02.003

    Computational models for networks of tiny artifacts: A survey (Journal article)

    Àlvarez, C., Chatzigiannakis, I., Duch, A., Gabarró, J., Michail, O., Serna, M., & Spirakis, P. G. (2011). Computational models for networks of tiny artifacts: A survey. Computer Science Review, 5(1), 7-25. doi:10.1016/j.cosrev.2010.09.001

    DOI: 10.1016/j.cosrev.2010.09.001

    2010

    All Symmetric Predicates in NSPACE(n(2)) Are Stably Computable by the Mediated Population Protocol Model (Conference Paper)

    Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., & Spirakis, P. G. (2010). All Symmetric Predicates in NSPACE(n(2)) Are Stably Computable by the Mediated Population Protocol Model. In MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2010 Vol. 6281 (pp. 270-+). Retrieved from http://gateway.webofknowledge.com/

    Algorithmic Verification of Population Protocols (Conference Paper)

    Chatzigiannakis, I., Michail, O., & Spirakis, P. G. (2010). Algorithmic Verification of Population Protocols. In STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS Vol. 6366 (pp. 221-235). Retrieved from http://gateway.webofknowledge.com/

    Stably Decidable Graph Languages by Mediated Population Protocols (Conference Paper)

    Chatzigiannakis, I., Michail, O., & Spirakis, P. G. (2010). Stably Decidable Graph Languages by Mediated Population Protocols. In STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS Vol. 6366 (pp. 252-266). Retrieved from http://gateway.webofknowledge.com/

    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

    Not All Fair Probabilistic Schedulers Are Equivalent (Conference Paper)

    Chatzigiannakis, I., Dolev, S., Fekete, S. P., Michail, O., & Spirakis, P. C. (2009). Not All Fair Probabilistic Schedulers Are Equivalent. In PRINCIPLES OF DISTRIBUTED SYSTEMS, PROCEEDINGS Vol. 5923 (pp. 33-+). Retrieved from http://gateway.webofknowledge.com/

    Mediated Population Protocols (Conference Paper)

    Chatzigiannakis, I., Michail, O., & Spirakis, P. G. (2009). Mediated Population Protocols. In AUTOMATA, LANGUAGES AND PROGRAMMING, PT II, PROCEEDINGS Vol. 5556 (pp. 363-+). Retrieved from http://gateway.webofknowledge.com/

    Recent Advances in Population Protocols (Conference Paper)

    Chatzigiannakis, I., Michail, O., & Spirakis, P. G. (2009). Recent Advances in Population Protocols. In MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009 Vol. 5734 (pp. 56-76). Retrieved from http://gateway.webofknowledge.com/

    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