Journal Article

Czumaj, Artur and Lingas, Andrzej (2023) On parallel time in population protocols. Information Processing Letters, 179 . 106314. doi:10.1016/j.ipl.2022.106314 ISSN 0020-0190.

Adamaszek, Anna, Czumaj, Artur, Englert, Matthias and Räcke, Harald (2022) Almost tight bounds for reordering buffer management. SIAM Journal on Computing, 51 (3). pp. 701-722. doi:10.1137/20M1326167 ISSN 0097-5397.

Czumaj, Artur, Kontogeorgiou, George and Paterson, Mike (2022) Haystack hunting hints and locker room communication. Random Structures & Algorithms . doi:10.1002/rsa.21114 ISSN 1042-9832. (In Press)

Czumaj, Artur, Davies, Peter and Parter, Merav (2021) Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms, 17 (2). 16. doi:10.1145/3451992 ISSN 1549-6325.

Czumaj, Artur and Davies, Peter (2021) Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. Journal of the ACM, 68 (2). 13. doi:10.1145/3446383 ISSN 0004-5411.

Czumaj, Artur, Łącki, Jakub, Mądry, Aleksander, Mitrović, Slobodan, Onak, Krzysztof and Sankowski, Piotr (2019) Round compression for parallel matching algorithms. SIAM Journal of Computing, 49 (5). p. 1. STOC18-1–STOC18-44. doi:10.1137/18M1197655 ISSN 0097-5397.

Adamaszek, Anna, Czumaj, Artur, Englert, Matthias and Räcke , Harald (2018) An O(log k)-competitive algorithm for generalized caching. ACM Transactions on Algorithms , 15 (1). pp. 1-18. 6. doi:10.1145/3280826 ISSN 1549-6325.

Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin and Savani, Rahul (2018) Distributed methods for computing approximate equilibria. Algorithmica . doi:10.1007/s00453-018-0465-y ISSN 0178-4617.

Czumaj, Artur and Davies, Peter (2018) Deterministic communication in radio networks. SIAM Journal on Computing, 47 (1). pp. 218-240. doi:10.1137/17M1111322 ISSN 0097-5397.

Adamaszek, Anna, Czumaj, Artur, Lingas, Andrzej and Wojtaszczyk, Jakub Onufry (2018) Approximation Schemes for Capacitated Geometric Network Design. SIAM Journal on Discrete Mathematics, 32 (4). pp. 2720-2746. doi:10.1137/16M1108005 ISSN 0895-4801.

Czumaj, Artur, Goldreich, Oded, Ron, Dana, Seshadhri, C., Shapira, Asaf and Sohler, Christian (2014) Finding cycles and trees in sublinear time. Random Structures & Algorithms, Volume 45 (Number 2). pp. 139-184. doi:10.1002/rsa.20462 ISSN 1042-9832.

Adamaszek, Anna, Czumaj, Artur and Lingas, Andrzej (2010) PTAS for k-tour cover problem on the plane for moderately large values of k. International Journal of Foundations of Computer Science, Volume 21 (Number 6). pp. 893-904. doi:10.1142/S0129054110007623 ISSN 0129-0541.

Czumaj, Artur, Krysta, Piotr and Vöcking, Berthold (2010) Selfish traffic allocation for server farms. SIAM Journal on Computing, Vol.39 (No.5). pp. 1957-1987. doi:10.1137/070693862 ISSN 0097-5397.

Czumaj, Artur and Sohler, Christian (2009) Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, Vol.39 (No.3). pp. 904-922. doi:10.1137/060672121 ISSN 0097-5397.

Czumaj, Artur and Sohler, Christian (2009) Small space representations for metric min-sum k-clustering and their applications. Theory of Computing Systems, Volume 46 (Number 3). pp. 416-442. doi:10.1007/s00224-009-9235-1 ISSN 1433-0490.

Czumaj, Artur and Lingas, Andrzej (2009) Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM Journal on Computing, Volume 39 (Number 2). pp. 431-444. doi:10.1137/070695149 ISSN 0097-5397.

Czumaj, Artur, Shapira, Asaf and Sohler, Christian (2009) Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing, Volume 38 (Number 6). pp. 2499-2510. doi:10.1137/070681831 ISSN 0097-5397.

Czumaj, Artur and Sohler, Christian (2008) Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Algorithms, Volume 4 (Number 3). p. 31. Article Number 31. doi:10.1145/1367064.1367071 ISSN 1549-6325.

Czumaj, Artur, Kowaluk, Miroslaw and Lingas, Andrzej (2007) Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theoretical Computer Science, Vol.380 (No.1-2). pp. 37-46. doi:10.1016/j.tcs.2007.02.053 ISSN 0304-3975.

Book Item

Czumaj, Artur, Fasoulakis, Michail and Jurdzinski, Marcin (2014) Approximate well-supported Nash equilibria in symmetric bimatrix games. In: Lavi, Ron, (ed.) Algorithmic Game Theory : 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. Lecture Notes in Computer Science, Volume 8768 . Springer Berlin Heidelberg, pp. 244-254. ISBN 9783662448021

Czumaj, Artur and Vöcking, Berthold (2014) Thorp shuffling, butterflies, and non-Markovian couplings. In: Esparza, Javier and Fraigniaud, Pierre and Husfeldt, Thore and Koutsoupias, Elias, (eds.) Automata, Languages, and Programming. Lecture Notes in Computer Science, Volume 8572 . Springer Berlin Heidelberg, pp. 344-355. ISBN 9783662439470

Berenbrink, Petra, Czumaj, Artur, Englert, Matthias, Friedetzky, Thomas and Nagel, Lars (2012) Multiple-choice balanced allocation in (almost) parallel. In: Gupta , Anupam and Jansen , Klaus and Rolim , José and Servedio , Rocco , (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques : 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. Lecture Notes in Computer Science, Volume 7408 . Berlin Heidelberg: Springer-Verlag, pp. 411-422. ISBN 9783642325113

Czumaj, Artur, Czyzowicz, J., Gąsieniec, L., Jansson, J., Lingas, Andrzej and Zylinski, P. (2009) Approximation algorithms for buy-at-bulk geometric network design. In: Dehne, F. and Gavrilova, M. and Sack, J. R. and Toth, C. D., (eds.) Algorithms and data structures. Lecture Notes in Computer Science, Volume 5664 . Springer, pp. 168-180. ISBN 9783642033667

Czumaj, Artur (2008) Euclidean traveling salesperson problem. In: Kao, Ming-Yang, (ed.) Encyclopedia of algorithms. Springer Verlag, pp. 281-284. ISBN 9780387301624

Czumaj, Artur and Lingas, Andrzej (2008) Minimum k-connected geometric networks. In: Kao, Ming-Yang, (ed.) Encyclopedia of algorithms. Springer Verlag, pp. 536-539. ISBN 9780387301624

Czumaj, Artur and Vöcking, Berthold (2008) Price of anarchy for machines models. In: Kao, Ming-Yang, (ed.) Encyclopedia of algorithms. Springer Verlag, pp. 1-99. ISBN 9780387301624

Czumaj, Artur and Wang, Xin (2007) Communication problems in random line-of-sight ad-hoc radio networks. In: Hromkovic, J. and Kralovic, R. and Nunkesser, M. and Widmayer, P., (eds.) Stochastic Algorithms : Foundations and Applications. Lecture Notes in Computer Science, Volume 4665 . Springer Berlin Heidelberg, pp. 70-81. ISBN 9783540748700

Czumaj, Artur and Wang, Xin (2007) Fast message dissemination in random geometric ad-hoc radio networks. In: Tokuyama, T., (ed.) Algorithms and Computation. Lecture Notes in Computer Science, Volume 4835 . Springer Berlin Heidelberg, pp. 220-231. ISBN 9783540771180

Czumaj, Artur and Sohler, Christian (2007) Small space representations for metric min-sum k-clustering and their applications. In: Thomas, W. and Weil, P., (eds.) STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Proceedings. Lecture Notes in Computer Science, Volume 4393 . Springer Berlin Heidelberg, pp. 536-548. ISBN 9783540709176

Conference Item

Czumaj, Artur, Jiang, Shaofeng H.-C., Krauthgamer, Robert and Veselý, Pavel (2022) Streaming algorithms for geometric Steiner forest. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Paris, France, 04-08 Jul 2022. Published in: Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) pp. 1-20. ISBN 9783959772358. doi:10.4230/LIPIcs.ICALP.2022.47 ISSN 1868-8969.

Coy, Sam, Czumaj, Artur, Feldmann, Michael, Hinnenthal, Kristian, Kuhn, Fabian, Scheideler, Christian, Schneider, Philipp and Struijs, Martijn (2022) Near-shortest path routing in hybrid communication networks. In: 25th International Conference on Principles of Distributed Systems (OPODIS 2021), Strasbourg, France, 13–15 Dec 2021. Published in: 25th International Conference on Principles of Distributed Systems (OPODIS 2021), 217 11:1-11:23. ISBN 9783959772198. doi:10.4230/LIPIcs.OPODIS.2021.11

Coy, Sam and Czumaj, Artur (2022) Deterministic massively parallel connectivity. In: ACM SIGACT Symposium on Theory of Computing (STOC ’22), Rome, Italy, 20-24 Jun. Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’22) ISBN 9781450392648. doi:10.1145/3519935.3520055 (In Press)

Czumaj, Artur, Jiang, Shaofeng H.-C., Krauthgamer, Robert, Vesely, Pavel and Yang, Mingwei (2022) Streaming facility location in high dimension via geometric hashing. In: The 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022), Denver, CO, USA, 31 Oct - 03 Nov 2022. Published in: Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022) (In Press)

Czumaj, Artur, Davies, Peter and Parter, Merav (2021) Component stability in low-space massively parallel computation. In: 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), Virtual, Italy, 26-30 Jul 2021. Published in: PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing pp. 481-491. ISBN 9781450385480. doi:10.1145/3465084.3467903

Czumaj, Artur, Davies, Peter and Parter, Merav (2021) Improved deterministic (Δ + 1)-coloring in low-space MPC. In: 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), Virtual, Italy, 26-30 Jul 2021. Published in: PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing pp. 469-479. ISBN 9781450385480. doi:10.1145/3465084.3467937

Czumaj, Artur, Kontogeorgiou, George and Paterson, Michael S. (2021) Haystack hunting hints and locker room communication. In: 48th International Colloquium on Automata, Languages and Programming (ICALP 2021), Virtual, Scotland, 12-16 Jul 2021. Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198 58 : 1-58: 20. ISBN 9783959771955. doi:10.4230/LIPIcs.ICALP.2021.58 ISSN 1868-8969.

Czumaj, Artur, Fichtenberger, Hendrik, Peng, Pan and Sohler, Christian (2020) Testable properties in general graphs and random order streaming. In: 24th International Conference on Randomization and Computation (RANDOM 2020), Virtual, USA, 17-19 Aug 2020. Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), 179 pp. 1-20. ISBN 9783959771641. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.16 ISSN 1868-8969.

Czumaj, Artur, Davies, Peter and Parter, Merav (2020) Simple, deterministic, constant-round coloring in the congested clique. In: 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020), Virtual conference, 3-7 Aug 2020. Published in: PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing pp. 309-318. ISBN 9781450375825. doi:10.1145/3382734.3405751

Czumaj, Artur, Davies, Peter and Parter, Merav (2020) Graph sparsification for derandomizing massively parallel computation with low space. In: 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), Virtual, USA, 15-17 Jul 2020. Published in: SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures pp. 175-185. ISBN 9781450369350. doi:10.1145/3350755.3400282

Czumaj, Artur and Sohler, Christian (2020) A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs). In: The 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019), Baltimore, MD, 9-12 Nov 2019. Published in: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) doi:10.1109/FOCS.2019.00091 ISSN 2575-8454.

Czumaj, Artur and Sohler, Christian (2020) Sublinear time approximation of the cost of a metric k-nearest neighbor graph. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2020), Salt Lake City, Utah, USA, January 5-8, 2020, Salt Lake City, Utah, USA, 5-8 Jan 2020. Published in: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms pp. 2973-2992. ISBN 9781611975994. doi:10.1137/1.9781611975994.180

Czumaj, Artur and Konrad, Christian (2018) Detecting cliques in CONGEST networks. In: 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, 15-19 Oct 2018. Published in: 32nd International Symposium on Distributed Computing (DISC 2018), 121 16:1-16:15. ISBN 9783959770927. doi:10.4230/LIPIcs.DISC.2018.16 ISSN 1868-8969.

Czumaj, Artur and Davies, Peter (2018) Deterministic blind radio networks. In: 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, 15-19 Oct 2018. Published in: 32nd International Symposium on Distributed Computing (DISC 2018), 121 15:1-15:17. ISBN 9783959770927. doi:10.4230/LIPIcs.DISC.2018.15 ISSN 1868-8969.

Czumaj, Artur and Davies, Peter (2018) Faster deterministic communication in radio networks. In: 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 55 pp. 1-14. ISBN 9783959770132. doi:10.4230/LIPIcs.ICALP.2016.139 ISSN 0097-5397.

Cygan, Marek, Czumaj, Artur, Mucha, Marcin and Sankowski, Piotr (2018) Online facility location with deletions. In: 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 20-24 Aug 2018. Published in: {26th Annual European Symposium on Algorithms (ESA 2018), 112 21:1-21:15. ISBN 9783959770811. doi:10.4230/LIPIcs.ESA.2018.21 ISSN 1868-8969.

Czumaj, Artur, Łącki, Jakub, Mądry, Aleksander, Mitrović, Slobodan, Onak, Krzysztof and Sankowski, Piotr (2018) Round compression for parallel matching algorithms. In: The 50th Annual ACM Symposium on Theory of Computing (STOC 2018), Los Angeles, 25-29 Jun 2018. Published in: STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing pp. 471-484. ISBN 9781450355599 . doi:10.1145/3188745.3188764

Czumaj, Artur and Davies, Peter (2017) Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. In: ACM Symposium on Principles of Distributed Computing (PODC 2017), Washington, DC, USA, 25 - 27 July 2017. Published in: Proceedings of the 36th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2017) pp. 3-12. ISBN 9781450349925. doi:10.1145/3087801.3087825

Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin and Savani, Rahul (2016) Distributed methods for computing approximate equilibria. In: International Conference on Web and Internet Economics, WINE 2016, Montréal, Canada, 11-14 Dec 2016. Published in: Web and Internet Economics. WINE 2016, 10123 pp. 15-28. ISBN 9783662541098. doi:10.1007/978-3-662-54110-4_2 ISSN 0302-9743.

Czumaj, Artur, Peng, Pan and Sohler, Christian (2016) Relating two property testing models for bounded degree directed graphs. In: 48th Annual ACM Symposium on Theory of Computing (STOC 2016), Cambridge, MA, 19-21 Jun 2016. Published in: STOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing pp. 1033-1045. ISBN 9781450341325. doi:10.1145/2897518.2897575

Czumaj, Artur (2015) Random permutations using switching networks. In: Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, 15-17 Jun 2015. Published in: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing pp. 703-712. ISBN 9781450335362. doi:10.1145/2746539.2746629

Czumaj, Artur, Peng, Pan and Sohler, Christian (2015) Testing cluster structure of graphs. In: Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, 15-17 Jun 2015. Published in: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing pp. 723-732. ISBN 9781450335362. doi:10.1145/2746539.2746618

Adamaszek, Anna, Czumaj, Artur, Englert, Matthias and Räcke, Harald (2012) An O(log k)-competitive algorithm for generalized caching. In: 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 17-19 Jan 2012. Published in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1681-1689. ISSN 9781611972108.

Czumaj, Artur, Monemizadeh, Morteza, Onak, Krzysztof and Sohler, Christian (2011) Planar graphs : random walks and bipartiteness testing. In: 52nd Annual Symposium on Foundations of Computer Science (FOCS), Palm Springs, CA, 22-25 Oct. 2011. Published in: Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on pp. 423-432. ISBN 9781457718434. doi:10.1109/FOCS.2011.69 ISSN 0272-5428.

Adamaszek, Anna, Czumaj, Artur, Englert, Matthias and Räcke, Harald (2011) Almost tight bounds for reordering buffer management. In: STOC'11 Symposium on Theory of Computing Conference (Co-located with FCRC 2011), San Jose, CA, USA, 6-8 Jun 2011. Published in: STOC '11 Proceedings of the 43rd annual ACM symposium on Theory of computing pp. 607-616. doi:10.1145/1993636.1993717 ISSN 9781450306911.

Czumaj, Artur and Sohler, Christian (2010) Testing expansion in bounded-degree graphs. In: Meeting on Combinatorics and Probability, Mathemat Res Inst, Oberwolfach, Germany, April 26-May 02, 2009. Published in: Combinatorics, Probability and Computing, Vol.19 (No.Special Issue 5-6). pp. 693-709. doi:10.1017/S096354831000012X ISSN 0963-5483.

Czumaj, Artur, Adamaszek, Michał and Sohler, Christian (2010) Testing monotone continuous distributions on high-dimensional real cubes. In: 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10), Austin, Texas, 17-19 Jan 2010. Published in: SIAM pp. 56-65. doi:10.1007/978-3-642-16367-8_13

Czumaj, Artur and Sohler, Christian (2010) Sublinear-time algorithms. In: Workshop on Property Testing, Tsinghua University, Peoples Republic of China. Published in: Property Testing : Current Research and Surveys, Vol.6390 pp. 41-64. doi:10.1007/978-3-642-16367-8_5 ISSN 0302-9743.

Adamaszek, Michał, Czumaj, Artur and Sohler, Christian (2010) Testing monotone continuous distributions on high-dimensional real cubes. In: Workshop on Property Testing, Tsinghua University, Peoples Republic of China. Published in: Property Testing : Current Research and Surveys, Vol.6390 pp. 228-233. doi:10.1007/978-3-642-16367-8_13 ISSN 0302-9743.

Czumaj, Artur (2010) Local graph exploration and fast property testing. In: 16th Annual European Symposium on Algorithms (ESA 2010), Liverpool, England, 6-8 Sep 2010. Published in: Lecture Notes in Computer Science, Vol.6346 pp. 410-414. doi:10.1007/978-3-642-15775-2_35 ISSN 0302-9743.

Adamaszek, Anna, Czumaj, Artur and Lingas, Andrzej (2009) PTAS for k-tour cover problem on the plane for moderately large values of k. In: 20th International Symposium on Algorithms and Computations (ISAAC 2009), Honolulu, HI, December 16-18, 2009. Published in: Lecture Notes in Computer Science, 5878 pp. 994-1003. ISBN 978-3-642-10630-9. doi:10.1007/978-3-642-10631-6_100 ISSN 0302-9743.

Czumaj, Artur and Sohler, Christian (2007) Sublinear-time approximation algorithms for clustering via random sampling. In: 12th International Conference on Random Structures and Algorithms, Poznan, Poland, 01-05 Aug 2005. Published in: Random Structures & Algorithms, Volume 30 (Number 1-2). pp. 226-256. doi:10.1002/rsa.20157 ISSN 1042-9832.

Czumaj, Artur and Lingas, Andrzej (2007) Finding a heaviest triangle is not harder than matrix multiplication. In: 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Los Angeles, 07-09 Jan 2007. Published in: Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms pp. 986-994. ISBN 9780898716245.

Czumaj, Artur and Sohler, Christian (2007) On testable properties in bounded degree graphs. In: 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Los Angeles, 07-09 Jan 2007. Published in: Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms pp. 494-501. ISBN 9780898716245.

Czumaj, Artur and Sohler, Christian (2007) Testing expansion in bounded-degree graphs. In: 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, 20-23 Oct 2007. Published in: 48th Annual IEEE Symposium on Foundations of Computer Science, 2007. FOCS '07. pp. 570-578. ISBN 9780769530109. doi:10.1109/FOCS.2007.4389526

Report

Czumaj, Artur (1992) Parallel algorithm for the matrix chain product problem. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Czumaj, Artur (1992) An optimal parallel algorithm for computing a near-optimal order of matrix multiplications. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)