Prof Paul Spirakis PhD - Member of Academia Europaea

Professor in Computer Science Computer Science

    Publications

    2020

    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. (2020). How fast can we reach a target vertex in stochastic temporal graphs?. Journal of Computer and System Sciences, 114, 65-83. doi:10.1016/j.jcss.2020.05.005

    DOI: 10.1016/j.jcss.2020.05.005

    Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle (Journal article)

    Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (n.d.). Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. Retrieved from http://arxiv.org/abs/2004.06036v2

    Distributed Computation and Reconfiguration in Actively Dynamic Networks (Conference Paper)

    Michail, O., Skretas, G., & Spirakis, P. (2020). Distributed Computation and Reconfiguration in Actively Dynamic Networks. In PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 448-457). doi:10.1145/3382734.3405744

    DOI: 10.1145/3382734.3405744

    Crystal Structure Prediction via Oblivious Local Search (Journal article)

    Antypov, D., Deligkas, A., Gusev, V., Rosseinsky, M. J., Spirakis, P. G., & Theofilatos, M. (2020). Crystal Structure Prediction via Oblivious Local Search. 18th Symposium on Experimental Algorithms (SEA 2020), 160, 21:1-21:14. doi:10.4230/LIPIcs.SEA.2020.21

    DOI: 10.4230/LIPIcs.SEA.2020.21

    Temporal Vertex Cover with a Sliding Time Window (Journal article)

    Akrida, E., Mertzios, G. B., Spirakis, P., & Zamaraev, V. (2020). Temporal Vertex Cover with a Sliding Time Window. Journal of Computer and System Sciences, 107, 108-123. doi:10.1016/j.jcss.2019.08.002

    DOI: 10.1016/j.jcss.2019.08.002

    Crystal Structure Prediction via Oblivious Local Search. (Conference Paper)

    Antypov, D., Deligkas, A., Gusev, V. V., Rosseinsky, M. J., Spirakis, P. G., & Theofilatos, M. (2020). Crystal Structure Prediction via Oblivious Local Search.. In S. Faro, & D. Cantone (Eds.), SEA Vol. 160 (pp. 21:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from https://www.dagstuhl.de/dagpub/978-3-95977-148-1

    Distributed Computation and Reconfiguration in Actively Dynamic Networks (Conference Paper)

    Michail, O., Skretas, G., & Spirakis, P. G. (n.d.). Distributed Computation and Reconfiguration in Actively Dynamic Networks. Retrieved from http://arxiv.org/abs/2003.03355v1

    Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. (Conference Paper)

    Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2020). Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle.. In J. Esparza, & D. Král' (Eds.), MFCS Vol. 170 (pp. 27:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from http://www.informatik.uni-trier.de/~ley/db/conf/mfcs/mfcs2020.html

    Gathering in 1-Interval Connected Graphs (Journal article)

    Michail, O., Spirakis, P. G., & Theofilatos, M. (n.d.). Gathering in 1-Interval Connected Graphs. Retrieved from http://arxiv.org/abs/2008.07455v1

    Matching in Stochastically Evolving Graphs (Report)

    Akrida, E. C., Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (n.d.). Matching in Stochastically Evolving Graphs. Retrieved from http://arxiv.org/abs/2005.08263v1

    2019

    Fault Tolerant Network Constructors (Journal article)

    Michail, O., Spirakis, P. G., & Theofilatos, M. (2019). Fault Tolerant Network Constructors. Lecture Notes in Computer Science. Retrieved from http://arxiv.org/abs/1903.05992v2

    Connected Subgraph Defense Games (Conference Paper)

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

    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

    Temporal flows in Temporal networks (Journal article)

    Akrida, E., Czyzowicz, J., Gasieniec, L., Kuszner, L., & Spirakis, P. (2019). Temporal flows in Temporal networks. Journal of Computer and System Sciences, 103, 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. (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

    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

    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

    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, 102, 18-39. doi:10.1016/j.jcss.2018.12.001

    DOI: 10.1016/j.jcss.2018.12.001

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

    Akrida, E. C., Mertzios, G. B., & Spirakis, P. G. (2019). The temporal explorer who returns to the base. International Conference on Algorithms and Complexity (CIAC). Retrieved from http://arxiv.org/abs/1805.04713v1

    Temporal Network Optimization Subject to Connectivity Constraints (Journal article)

    Mertzios, G., Michail, O., & Spirakis, P. (2019). Temporal Network Optimization Subject to Connectivity Constraints. Algorithmica: an international journal in computer science, 81, 1416-1449. doi:10.1007/s00453-018-0478-6

    DOI: 10.1007/s00453-018-0478-6

    Binary Search in Graphs Revisited. (Journal article)

    Deligkas, A., Mertzios, G. B., & Spirakis, P. G. (2019). Binary Search in Graphs Revisited.. Algorithmica, 81, 1757-1780.

    Data-Driven Intrusion Detection for Ambient Intelligence (Conference Paper)

    Chatzigiannakis, I., Maiano, L., Trakadas, P., Anagnostopoulos, A., Bacci, F., Karkazis, P., . . . Zahariadis, T. (2019). Data-Driven Intrusion Detection for Ambient Intelligence. In AMBIENT INTELLIGENCE (AMI 2019) Vol. 11912 (pp. 235-251). doi:10.1007/978-3-030-34255-5_16

    DOI: 10.1007/978-3-030-34255-5_16

    Fault Tolerant Network Constructors. (Conference Paper)

    Michail, O., Spirakis, P. G., & Theofilatos, M. (2019). Fault Tolerant Network Constructors.. In M. Ghaffari, M. Nesterenko, S. Tixeuil, S. Tucci, & Y. Yamauchi (Eds.), SSS Vol. 11914 (pp. 243-255). Springer. Retrieved from https://doi.org/10.1007/978-3-030-34992-9

    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.. J. Comput. Syst. Sci., 102, 18-39.

    Temporal vertex cover with a sliding time window (Conference Paper)

    Akrida, E. C., Mertzios, G. B., Spirakis, P. G., & Zarnaraev, V. (2020). Temporal vertex cover with a sliding time window. In JOURNAL OF COMPUTER AND SYSTEM SCIENCES Vol. 107 (pp. 108-123). doi:10.1016/j.jcss.2019.08.002

    DOI: 10.1016/j.jcss.2019.08.002

    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

    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., & 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

    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

    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.

    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. (2018). The Price of Stability of Weighted Congestion Games. In LIPIcs : Leibniz International Proceedings in Informatics Vol. 107 (pp. 150:1-150:16). Prague: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ICALP.2018.150

    DOI: 10.4230/LIPIcs.ICALP.2018.150

    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

    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

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

    Melissourgos, T., Nikoletseas, S. E., Raptopoulos, C. L., & 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

    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

    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.01393v3

    Approximating the Existential Theory of the Reals. (Conference Paper)

    Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (2018). Approximating the Existential Theory of the Reals.. In G. Christodoulou, & T. Harks (Eds.), WINE Vol. 11316 (pp. 126-139). Springer. Retrieved from https://doi.org/10.1007/978-3-030-04612-5

    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

    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

    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

    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

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

    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

    Strategic Contention Resolution in Multiple Channels. (Journal article)

    Christodoulou, G., Melissourgos, T., & Spirakis, P. G. (2018). Strategic Contention Resolution in Multiple Channels.. CoRR, abs/1810.04565.

    2017

    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

    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.

    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

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

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

    DOI: 10.1007/s00453-016-0175-2

    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

    Deterministic Population Protocols for Exact Majority and Plurality (Conference Paper)

    Spirakis, P. G., Gasieniec, L., Martin, R., Hamilton, D., & Stachowiac, G. (2017). Deterministic Population Protocols for Exact Majority and Plurality. In LIPIcs. Madrit Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2016.14

    DOI: 10.4230/LIPIcs.OPODIS.2016.14

    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 (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

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

    Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C. L., & 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. (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

    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

    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

    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

    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

    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/

    2016

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

    Lipschitz Continuity and Approximate Equilibria (Conference Paper)

    Deligkas, A., Fearnley, J., & Spirakis, P. (2020). Lipschitz Continuity and Approximate Equilibria. In ALGORITHMICA Vol. 82 (pp. 2927-2954). doi:10.1007/s00453-020-00709-3

    DOI: 10.1007/s00453-020-00709-3

    Strategic Contention Resolution with Limited Feedback (Conference Paper)

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

    DOI: 10.4230/LIPIcs.ESA.2016.30

    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

    Traveling Salesman Problems in Temporal Graphs (Journal article)

    Spirakis, P. G., & Michail, O. (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

    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

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

    Strategic Contention Resolution with Limited Feedback. (Conference Paper)

    Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C. L., & 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

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

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

    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

    The Match-Maker: Constant-Space Distributed Majority via Random Walks (Conference Paper)

    Gasieniec, 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

    2014

    Ephemeral Networks with Random Availability of Links: Diameter and Connectivity (Conference Paper)

    Akrida, E. C., Gasieniec, L., Mertzios, G. B., Spirakis, P. G., & ACM. (2014). Ephemeral Networks with Random Availability of Links: Diameter and Connectivity. In PROCEEDINGS OF THE 26TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA'14) (pp. 267-276). doi:10.1145/2612669.2612693

    DOI: 10.1145/2612669.2612693

    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

    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

    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(01), 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/

    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

    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., & ACM. (2014). Simple and Efficient Local Codes for Distributed Stable Network Construction. In PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14) (pp. 76-85). doi:10.1145/2611462.2611466

    DOI: 10.1145/2611462.2611466

    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

    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

    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

    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 (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