{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:50Z","timestamp":1750220690465,"version":"3.41.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319575858"},{"type":"electronic","value":"9783319575865"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-57586-5_39","type":"book-chapter","created":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T15:23:34Z","timestamp":1492097014000},"page":"469-484","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Stathis Zachos at 70!"],"prefix":"10.1007","author":[{"given":"Eleni","family":"Bakali","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiotis","family":"Cheilaris","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6864-8960","authenticated-orcid":false,"given":"Dimitris","family":"Fotakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"F\u00fcrer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Costas D.","family":"Koutras","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Euripides","family":"Markou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Nomikos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6220-3722","authenticated-orcid":false,"given":"Aris","family":"Pagourtzis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaos S.","family":"Papaspyrou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katerina","family":"Potika","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,14]]},"reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time (extended abstract). In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18\u201321 June 2016, pp. 684\u2013697. ACM (2016)","DOI":"10.1145\/2897518.2897542"},{"key":"39_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/978-3-319-57586-5_6","volume-title":"CIAC 2017","author":"E Bakali","year":"2017","unstructured":"Bakali, E., Chalki, A., Pagourtzis, A., Pantavos, P., Zachos, S.: Completeness results for counting problems with easy decision. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 55\u201366. Springer, Cham (2017)"},{"key":"39_CR3","doi-asserted-by":"publisher","unstructured":"Bampas, E., G\u00f6bel, A.-N., Pagourtzis, A., Tentes, A.: On the connection between interval size functions and path counting. Comput. Complex. (2016). doi:10.1007\/s00037-016-0137-8","DOI":"10.1007\/s00037-016-0137-8"},{"issue":"4","key":"39_CR4","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1109\/TNET.2011.2173948","volume":"20","author":"E Bampas","year":"2012","unstructured":"Bampas, E., Pagourtzis, A., Pierrakos, G., Potika, K.: On a noncooperative model for wavelength assignment in multifiber optical networks. IEEE\/ACM Trans. Netw. 20(4), 1125\u20131137 (2012)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"39_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-38233-8_3","volume-title":"Algorithms and Complexity","author":"E Bampas","year":"2013","unstructured":"Bampas, E., Pagourtzis, A., Pierrakos, G., Syrgkanis, V.: Selfish resource allocation in optical networks. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 25\u201336. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-38233-8_3"},{"key":"39_CR6","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2012.04.036","volume":"444","author":"A Bar-Noy","year":"2012","unstructured":"Bar-Noy, A., Cheilaris, P., Lampis, M., Mitsou, V., Zachos, S.: Ordered coloring of grids and related graphs. Theoret. Comput. Sci. 444, 40\u201351 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"39_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90084-S","volume":"103","author":"R Beigel","year":"1992","unstructured":"Beigel, R., Gill, J.: Counting classes: thresholds, parity, mods, and fewness. Theor. Comput. Sci. 103(1), 3\u201323 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"39_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"RB Boppana","year":"1987","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127\u2013132 (1987)","journal-title":"Inf. Process. Lett."},{"key":"39_CR9","unstructured":"Cheilaris, P., Ramirez, J., Zachos, S.: Checking in linear time if an $$S$$-term normalizes. In: Proceedings of the 8th Panhellenic Logic Symposium (2011)"},{"issue":"3","key":"39_CR10","first-page":"469","volume":"51","author":"P Cheilaris","year":"2010","unstructured":"Cheilaris, P., Specker, E., Zachos, S.: Neochromatica. Commentationes Math. Univ. Carol. 51(3), 469\u2013480 (2010)","journal-title":"Commentationes Math. Univ. Carol."},{"issue":"3","key":"39_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.comgeo.2006.12.001","volume":"38","author":"C Fragoudakis","year":"2007","unstructured":"Fragoudakis, C., Markou, E., Zachos, S.: Maximizing the guarded boundary of an Art Gallery is APX-complete. Comput. Geom.: Theory Appl. 38(3), 170\u2013180 (2007)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"39_CR12","first-page":"249","volume":"5","author":"M F\u00fcrer","year":"1989","unstructured":"F\u00fcrer, M., Goldreich, O., Mansour, Y., Sipser, M., Zachos, S.: On completeness and soundness in interactive proof systems. Adv. Comput. Res. 5, 249\u2013442 (1989)","journal-title":"Adv. Comput. Res."},{"issue":"5","key":"39_CR13","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1137\/S0097539705447013","volume":"36","author":"LA Hemaspaandra","year":"2007","unstructured":"Hemaspaandra, L.A., Homan, C.M., Kosub, S., Wagner, K.W.: The complexity of computing the size of an interval. SIAM J. Comput. 36(5), 1264\u20131300 (2007)","journal-title":"SIAM J. Comput."},{"key":"39_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/3-540-38076-0_29","volume-title":"Advances in Informatics","author":"A Kiayias","year":"2003","unstructured":"Kiayias, A., Pagourtzis, A., Sharma, K., Zachos, S.: Acceptor-definable counting classes. In: Manolopoulos, Y., Evripidou, S., Kakas, A.C. (eds.) PCI 2001. LNCS, vol. 2563, pp. 453\u2013463. Springer, Heidelberg (2003). doi:10.1007\/3-540-38076-0_29"},{"key":"39_CR15","unstructured":"Kiayias, A., Pagourtzis, A., Zachos, S.: Cook reductions blur structural differences between functional complexity classes. In: Proceedings of the 2nd Panhellenic Logic Symposium, Delphi, 13\u201317 July 1999, pp. 132\u2013137 (1999)"},{"issue":"3","key":"39_CR16","doi-asserted-by":"crossref","first-page":"281","DOI":"10.3233\/FI-1999-38303","volume":"38","author":"CD Koutras","year":"1999","unstructured":"Koutras, C.D., Koletsos, G., Zachos, S.: Many-valued modal non-monotonic reasoning: sequential stable sets and logics with linear truth spaces. Fundam. Inform. 38(3), 281\u2013324 (1999)","journal-title":"Fundam. Inform."},{"issue":"1","key":"39_CR17","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1093\/jigpal\/8.1.33","volume":"8","author":"CD Koutras","year":"2000","unstructured":"Koutras, C.D., Zachos, S.: Many-valued reflexive autoepistemic logic. Logic J. IGPL 8(1), 33\u201354 (2000)","journal-title":"Logic J. IGPL"},{"key":"39_CR18","unstructured":"Markou, E., Fragoudakis, C., Zachos, S.: Approximating visibility problems within a constant. In: Proceedings of the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, pp. 91\u2013103 (2002)"},{"key":"39_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/3-540-44849-7_10","volume-title":"Algorithms and Complexity","author":"E Markou","year":"2003","unstructured":"Markou, E., Zachos, S., Fragoudakis, C.: Maximizing the guarded boundary of an Art Gallery is APX-complete. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol. 2653, pp. 24\u201335. Springer, Heidelberg (2003). doi:10.1007\/3-540-44849-7_10"},{"key":"39_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-24693-0_13","volume-title":"Networking 2004","author":"C Nomikos","year":"2004","unstructured":"Nomikos, C., Pagourtzis, A., Potika, K., Zachos, S.: Fiber cost reduction and wavelength minimization in multifiber WDM networks. In: Mitrou, N., Kontovasilis, K., Rouskas, G.N., Iliadis, I., Merakos, L. (eds.) NETWORKING 2004. LNCS, vol. 3042, pp. 150\u2013161. Springer, Heidelberg (2004). doi:10.1007\/978-3-540-24693-0_13"},{"issue":"1","key":"39_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comnet.2004.11.028","volume":"50","author":"C Nomikos","year":"2006","unstructured":"Nomikos, C., Pagourtzis, A., Potika, K., Zachos, S.: Routing and wavelength assignment in multifiber WDM networks with non-uniform fiber cost. Comput. Netw. 50(1), 1\u201314 (2006)","journal-title":"Comput. Netw."},{"issue":"5","key":"39_CR22","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0020-0190(01)00167-3","volume":"80","author":"C Nomikos","year":"2001","unstructured":"Nomikos, C., Pagourtzis, A., Zachos, S.: Routing and path multicoloring. Inf. Process. Lett. 80(5), 249\u2013256 (2001)","journal-title":"Inf. Process. Lett."},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"Nomikos, C., Pagourtzis, A., Zachos, S.: Minimizing request blocking in all-optical rings. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM 2003), San Franciso, CA, USA, 30 March\u20133 April 2003. IEEE (2003)","DOI":"10.1109\/INFCOM.2003.1208971"},{"issue":"1","key":"39_CR24","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S1389-1286(02)00448-6","volume":"42","author":"C Nomikos","year":"2003","unstructured":"Nomikos, C., Pagourtzis, A., Zachos, S.: Satisfying a maximum number of pre-routed requests in all-optical rings. Comput. Netw. 42(1), 55\u201363 (2003)","journal-title":"Comput. Netw."},{"key":"39_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/978-3-540-74456-6_63","volume-title":"Mathematical Foundations of Computer Science 2007","author":"C Nomikos","year":"2007","unstructured":"Nomikos, C., Pagourtzis, A., Zachos, S.: Randomized and approximation algorithms for blue-red matching. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 715\u2013725. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-74456-6_63"},{"issue":"3","key":"39_CR26","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s00607-007-0234-2","volume":"80","author":"A Pagourtzis","year":"2007","unstructured":"Pagourtzis, A., Potika, K., Zachos, S.: Path multicoloring with fewer colors in spiders and caterpillars. Computing 80(3), 255\u2013274 (2007)","journal-title":"Computing"},{"key":"39_CR27","series-title":"Australian Computer Science Communications","first-page":"291","volume-title":"Proceedings of Computing: The Fourth Australasian Theory Symposium (CATS 1998)","author":"A Pagourtzis","year":"1998","unstructured":"Pagourtzis, A., Sharma, K., Zachos, S.: Tree models, probabilistic polynomial time computations. In: Lin, X. (ed.) Proceedings of Computing: The Fourth Australasian Theory Symposium (CATS 1998). Australian Computer Science Communications, vol. 20, pp. 291\u2013304. Springer-Verlag Singapore Pte. Ltd., Singapore (1998)"},{"key":"39_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1007\/11821069_64","volume-title":"Mathematical Foundations of Computer Science 2006","author":"A Pagourtzis","year":"2006","unstructured":"Pagourtzis, A., Zachos, S.: The complexity of counting functions with easy decision version. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 741\u2013752. Springer, Heidelberg (2006). doi:10.1007\/11821069_64"},{"key":"39_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BFb0009651","volume-title":"Theoretical Computer Science","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Zachos, S.K.: Two remarks on the power of counting. In: Cremers, A.B., Kriegel, H.-P. (eds.) GI-TCS 1983. LNCS, vol. 145, pp. 269\u2013275. Springer, Heidelberg (1982). doi:10.1007\/BFb0036487"},{"key":"39_CR30","unstructured":"Papaspyrou, N.S., Zachos, S.: Teaching programming through problem solving: the role of the programming language. In: Proceedings of the 4th Workshop on Advances in Programming Languages (WAPL 2013), Federated Conference on Computer Science and Information Systems (FedCSIS 2013), pp. 1533\u20131536, Krak\u00f3w, Poland, September 2013"},{"key":"39_CR31","volume-title":"To Mock a Mockingbird and Other Logic Puzzles Including an Amazing Adventure in Combinatory Logic","author":"R Smullyan","year":"1985","unstructured":"Smullyan, R.: To Mock a Mockingbird and Other Logic Puzzles Including an Amazing Adventure in Combinatory Logic. Knopf, New York (1985)"},{"key":"39_CR32","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/inco.2000.2874","volume":"159","author":"J Waldmann","year":"2000","unstructured":"Waldmann, J.: The combinator $$S$$. Inf. Comput. 159, 2\u201321 (2000)","journal-title":"Inf. Comput."},{"key":"39_CR33","unstructured":"Zachos, S.: Kombinatorische Logik und $$S$$-Terme. Ph.D. thesis, ETH Z\u00fcrich (1978)"},{"issue":"3","key":"39_CR34","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0019-9958(82)80019-3","volume":"54","author":"S Zachos","year":"1982","unstructured":"Zachos, S.: Robustness of probabilistic computational complexity classes under definitional perturbations. Inf. Control 54(3), 143\u2013154 (1982)","journal-title":"Inf. Control"},{"key":"39_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/3-540-18625-5_67","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"S Zachos","year":"1987","unstructured":"Zachos, S., Furer, M.: Probabilistic quantifiers vs. distrustful adversaries. In: Nori, K.V. (ed.) FSTTCS 1987. LNCS, vol. 287, pp. 443\u2013455. Springer, Heidelberg (1987). doi:10.1007\/3-540-18625-5_67"},{"issue":"1\u20133","key":"39_CR36","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-9958(86)80044-4","volume":"69","author":"S Zachos","year":"1986","unstructured":"Zachos, S., Heller, H.: A decisive characterization of BPP. Inf. Control 69(1\u20133), 125\u2013135 (1986)","journal-title":"Inf. Control"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-57586-5_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:20:56Z","timestamp":1750198856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-57586-5_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319575858","9783319575865"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-57586-5_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"14 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/ciac2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}