×

Stathis Zachos at 70! (English) Zbl 1486.68007

Fotakis, Dimitris (ed.) et al., Algorithms and complexity. 10th international conference, CIAC 2017, Athens, Greece, May 24–26, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10236, 469-484 (2017).
Summary: This year we are celebrating the 70th birthday of Stathis! We take this chance to recall some of his remarkable contributions to Computer Science.
For the entire collection see [Zbl 1361.68008].

MSC:

68-03 History of computer science
01A70 Biographies, obituaries, personalia, bibliographies

Biographic References:

Zachos, Stathis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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–21 June 2016, pp. 684–697. ACM (2016) · Zbl 1376.68058 · doi:10.1145/2897518.2897542
[2] 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–66. Springer, Cham (2017) · Zbl 1486.68078 · doi:10.1007/978-3-319-57586-5_6
[3] Bampas, E., Göbel, 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 · Zbl 1241.68067 · doi:10.1007/s00037-016-0137-8
[4] 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–1137 (2012) · Zbl 1183.90084 · doi:10.1109/TNET.2011.2173948
[5] 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–36. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-38233-8_3 · Zbl 1382.91019 · doi:10.1007/978-3-642-38233-8_3
[6] Bar-Noy, A., Cheilaris, P., Lampis, M., Mitsou, V., Zachos, S.: Ordered coloring of grids and related graphs. Theoret. Comput. Sci. 444, 40–51 (2012) · Zbl 1246.05052 · doi:10.1016/j.tcs.2012.04.036
[7] Beigel, R., Gill, J.: Counting classes: thresholds, parity, mods, and fewness. Theor. Comput. Sci. 103(1), 3–23 (1992) · Zbl 0760.68028 · doi:10.1016/0304-3975(92)90084-S
[8] Boppana, R.B., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127–132 (1987) · Zbl 0653.68037 · doi:10.1016/0020-0190(87)90232-8
[9] Cheilaris, P., Ramirez, J., Zachos, S.: Checking in linear time if an \[ S \] -term normalizes. In: Proceedings of the 8th Panhellenic Logic Symposium (2011)
[10] Cheilaris, P., Specker, E., Zachos, S.: Neochromatica. Commentationes Math. Univ. Carol. 51(3), 469–480 (2010) · Zbl 1224.05164
[11] Fragoudakis, C., Markou, E., Zachos, S.: Maximizing the guarded boundary of an Art Gallery is APX-complete. Comput. Geom.: Theory Appl. 38(3), 170–180 (2007) · Zbl 1124.65023 · doi:10.1016/j.comgeo.2006.12.001
[12] Fürer, M., Goldreich, O., Mansour, Y., Sipser, M., Zachos, S.: On completeness and soundness in interactive proof systems. Adv. Comput. Res. 5, 249–442 (1989)
[13] 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–1300 (2007) · Zbl 1123.68041 · doi:10.1137/S0097539705447013
[14] 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–463. Springer, Heidelberg (2003). doi: 10.1007/3-540-38076-0_29 · Zbl 1026.68566 · doi:10.1007/3-540-38076-0_29
[15] 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–17 July 1999, pp. 132–137 (1999)
[16] 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–324 (1999) · Zbl 1040.03026
[17] Koutras, C.D., Zachos, S.: Many-valued reflexive autoepistemic logic. Logic J. IGPL 8(1), 33–54 (2000) · Zbl 1033.03021 · doi:10.1093/jigpal/8.1.33
[18] 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–103 (2002)
[19] 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–35. Springer, Heidelberg (2003). doi: 10.1007/3-540-44849-7_10 · Zbl 1032.68143 · doi:10.1007/3-540-44849-7_10
[20] 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–161. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-24693-0_13 · doi:10.1007/978-3-540-24693-0_13
[21] 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–14 (2006) · Zbl 1101.68347 · doi:10.1016/j.comnet.2004.11.028
[22] Nomikos, C., Pagourtzis, A., Zachos, S.: Routing and path multicoloring. Inf. Process. Lett. 80(5), 249–256 (2001) · Zbl 1003.68005 · doi:10.1016/S0020-0190(01)00167-3
[23] 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–3 April 2003. IEEE (2003) · Zbl 1035.68086 · doi:10.1109/INFCOM.2003.1208971
[24] Nomikos, C., Pagourtzis, A., Zachos, S.: Satisfying a maximum number of pre-routed requests in all-optical rings. Comput. Netw. 42(1), 55–63 (2003) · Zbl 1035.68086 · doi:10.1016/S1389-1286(02)00448-6
[25] Nomikos, C., Pagourtzis, A., Zachos, S.: Randomized and approximation algorithms for blue-red matching. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 715–725. Springer, Heidelberg (2007). doi: 10.1007/978-3-540-74456-6_63 · Zbl 1147.68872 · doi:10.1007/978-3-540-74456-6_63
[26] Pagourtzis, A., Potika, K., Zachos, S.: Path multicoloring with fewer colors in spiders and caterpillars. Computing 80(3), 255–274 (2007) · Zbl 1130.68082 · doi:10.1007/s00607-007-0234-2
[27] 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–304. Springer-Verlag Singapore Pte. Ltd., Singapore (1998) · Zbl 0953.68060
[28] Pagourtzis, A., Zachos, S.: The complexity of counting functions with easy decision version. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 741–752. Springer, Heidelberg (2006). doi: 10.1007/11821069_64 · Zbl 1132.68425 · doi:10.1007/11821069_64
[29] 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–275. Springer, Heidelberg (1982). doi: 10.1007/BFb0036487 · Zbl 0506.68039 · doi:10.1007/BFb0036487
[30] 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–1536, Kraków, Poland, September 2013
[31] Smullyan, R.: To Mock a Mockingbird and Other Logic Puzzles Including an Amazing Adventure in Combinatory Logic. Knopf, New York (1985)
[32] Waldmann, J.: The combinator \[ S \] . Inf. Comput. 159, 2–21 (2000) · Zbl 1005.03017 · doi:10.1006/inco.2000.2874
[33] Zachos, S.: Kombinatorische Logik und \[ S \] -Terme. Ph.D. thesis, ETH Zürich (1978)
[34] Zachos, S.: Robustness of probabilistic computational complexity classes under definitional perturbations. Inf. Control 54(3), 143–154 (1982) · Zbl 0529.68024 · doi:10.1016/S0019-9958(82)80019-3
[35] Zachos, S., Furer, M.: Probabilistic quantifiers vs. distrustful adversaries. In: Nori, K.V. (ed.) FSTTCS 1987. LNCS, vol. 287, pp. 443–455. Springer, Heidelberg (1987). doi: 10.1007/3-540-18625-5_67 · Zbl 0647.68052 · doi:10.1007/3-540-18625-5_67
[36] Zachos, S., Heller, H.: A decisive characterization of BPP. Inf. Control 69(1–3), 125–135 (1986) · Zbl 0616.68049 · doi:10.1016/S0019-9958(86)80044-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.