Job Title

Professor

Department

Computer Science

Phone

+44 24 7657 3796

Email

Web Link

Research Interests

The main fields of research interest are: - Randomized algorithms and their probabilistic analysis, - Algorithmic aspects of game theory and economics, - Combinatorics and discrete mathematics, - Graph theory and graph algorithms, - String/pattern matching (applications and efficient implementations), - Parallel and distributed algorithms and communication networks.

- 'Adamaszek, Anna, 'Czumaj, Artur, 'Englert, Matthias, 'R?cke, Harald, 2022. 'Almost tight bounds for reordering buffer management. SIAM Journal on Computing
- Czumaj, Artur, Davies, Peter, 2021. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. Journal of the ACM, 68 (2)
- Czumaj, Artur, Davies, Peter, Parter, Merav, 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms, 17 (2)
- Czumaj, Artur, Lacki, Jakub, Madry, Aleksander, Mitrovic, Slobodan, Onak, Krzysztof, Sankowski, Piotr, 2019. Round compression for parallel matching algorithms. SIAM Journal of Computing, 49 (5)
- Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin, Savani, Rahul, 2018. Distributed methods for computing approximate equilibria. Algorithmica
- Adamaszek, Anna, Czumaj, Artur, Englert, Matthias, Räcke , Harald, 2018. An O(log k)-competitive algorithm for generalized caching. ACM Transactions on Algorithms, 15 (1), pp. 1-18
- Czumaj, Artur, Davies, Peter, 2018. Deterministic communication in radio networks. SIAM Journal on Computing, 47 (1), pp. 218-240
- Adamaszek, Anna, Czumaj, Artur, Lingas, Andrzej, Wojtaszczyk, Jakub Onufry, 2018. Approximation Schemes for Capacitated Geometric Network Design. SIAM Journal on Discrete Mathematics, 32 (4), pp. 2720-2746
- Czumaj, Artur, Goldreich, Oded, Ron, Dana, Seshadhri, C., Shapira, Asaf, Sohler, Christian, 2014. Finding cycles and trees in sublinear time. Random Structures & Algorithms, 45 (2), pp. 139-184
- Adamaszek, Anna, Czumaj, Artur, 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, 21 (6), pp. 893-904
- Czumaj, Artur, Krysta, Piotr, Vöcking, Berthold, 2010. Selfish traffic allocation for server farms. SIAM Journal on Computing, Vol.39 (No.5), pp. 1957-1987
- Czumaj, Artur, 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
- Czumaj, Artur, Sohler, Christian, 2009. Small space representations for metric min-sum k-clustering and their applications. Theory of Computing Systems, 46 (3), pp. 416-442
- Czumaj, Artur, Shapira, Asaf, Sohler, Christian, 2009. Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing, 38 (6), pp. 2499-2510
- Czumaj, Artur, Lingas, Andrzej, 2009. Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM Journal on Computing, 39 (2), pp. 431-444
- Czumaj, Artur, Sohler, Christian, 2008. Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Algorithms, 4 (3)
- Czumaj, Artur, Kowaluk, Miroslaw, 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

- Czumaj, Artur, Fasoulakis, Michail, 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, Springer Berlin Heidelberg, pp. 244-254
- Czumaj, Artur, Vöcking, Berthold, 2014. Thorp shuffling, butterflies, and non-Markovian couplings. In Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; Koutsoupias, Elias (eds.), Automata, Languages, and Programming, Springer Berlin Heidelberg, pp. 344-355
- Berenbrink, Petra, Czumaj, Artur, Englert, Matthias, Friedetzky, Thomas, Nagel, Lars, 2012. Multiple-choice balanced allocation in (almost) parallel. In Gupta , Anupam; Jansen , Klaus; Rolim , José; 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, Berlin Heidelberg, Springer-Verlag, pp. 411-422
- Czumaj, Artur, Czyzowicz, J., Gasieniec, L., Jansson, J., Lingas, Andrzej, Zylinski, P., 2009. Approximation algorithms for buy-at-bulk geometric network design. In Dehne, F.; Gavrilova, M.; Sack, J. R.; Toth, C. D. (eds.), Algorithms and data structures, Springer, pp. 168-180
- Czumaj, Artur, 2008. Euclidean traveling salesperson problem. In Kao, Ming-Yang (ed.), Encyclopedia of algorithms, Springer Verlag, pp. 281-284
- Czumaj, Artur, Lingas, Andrzej, 2008. Minimum k-connected geometric networks. In Kao, Ming-Yang (ed.), Encyclopedia of algorithms, Springer Verlag, pp. 536-539
- Czumaj, Artur, Vöcking, Berthold, 2008. Price of anarchy for machines models. In Kao, Ming-Yang (ed.), Encyclopedia of algorithms, Springer Verlag, pp. 1-99
- Czumaj, Artur, Sohler, Christian, 2007. Small space representations for metric min-sum k-clustering and their applications. In Thomas, W.; Weil, P. (eds.), STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Proceedings, Springer Berlin Heidelberg, pp. 536-548
- Czumaj, Artur, Wang, Xin, 2007. Communication problems in random line-of-sight ad-hoc radio networks. In Hromkovic, J.; Kralovic, R.; Nunkesser, M.; Widmayer, P. (eds.), Stochastic Algorithms : Foundations and Applications, Springer Berlin Heidelberg, pp. 70-81
- Czumaj, Artur, Wang, Xin, 2007. Fast message dissemination in random geometric ad-hoc radio networks. In Tokuyama, T. (ed.), Algorithms and Computation, Springer Berlin Heidelberg, pp. 220-231

- 'Coy, Sam, 'Czumaj, Artur, 'Feldmann, Michael, 'Hinnenthal, Kristian, 'Kuhn, Fabian, 'Scheideler, Christian, 'Schneider, Philipp, 'Struijs, Martijn, 2022. 'Near-shortest path routing in hybrid communication networks. 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), pp. 11:1-11:23
- Czumaj, Artur, Davies, Peter, Parter, Merav, 2021. Improved deterministic (? + 1)-coloring in low-space MPC. 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), Virtual, Italy, 26-30 Jul 2021, Published in Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021)
- 'Czumaj, Artur, 'Kontogeorgiou, George, 'Paterson, Michael S., 2021. 'Haystack hunting hints and locker room communication. 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), pp. 58 : 1-58: 20
- 'Czumaj, Artur, 'Davies, Peter, 'Parter, Merav, 2021. 'Component stability in low-space massively parallel computation. 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
- Czumaj, Artur, Sohler, Christian, 2020. Sublinear time approximation of the cost of a metric k-nearest neighbor graph. 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
- Czumaj, Artur, Davies, Peter, Parter, Merav, 2020. Graph sparsification for derandomizing massively parallel computation with low space. 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
- Czumaj, Artur, Sohler, Christian, 2020. A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs). 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)
- Czumaj, Artur, Davies, Peter, Parter, Merav, 2020. Simple, deterministic, constant-round coloring in the congested clique. 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
- Czumaj, Artur, Fichtenberger, Hendrik, Peng, Pan, Sohler, Christian, 2020. Testable properties in general graphs and random order streaming. 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), pp. 1-20
- Czumaj, Artur, Lacki, Jakub, Madry, Aleksander, Mitrovic, Slobodan, Onak, Krzysztof, Sankowski, Piotr, 2018. Round compression for parallel matching algorithms. 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
- Cygan, Marek, Czumaj, Artur, Mucha, Marcin, Sankowski, Piotr, 2018. Online facility location with deletions. 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 20-24 Aug 2018, Published in {26th Annual European Symposium on Algorithms (ESA 2018), pp. 21:1-21:15
- Czumaj, Artur, Konrad, Christian, 2018. Detecting cliques in CONGEST networks. 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), pp. 16:1-16:15
- Czumaj, Artur, Davies, Peter, 2018. Deterministic blind radio networks. 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), pp. 15:1-15:17
- Czumaj, Artur, Davies, Peter, 2018. Faster deterministic communication in radio networks. 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 1-14
- Czumaj, Artur, Davies, Peter, 2017. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. 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
- Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin, Savani, Rahul, 2016. Distributed methods for computing approximate equilibria. International Conference on Web and Internet Economics, WINE 2016, Montréal, Canada, 11-14 Dec 2016, Published in Web and Internet Economics. WINE 2016, pp. 15-28
- Czumaj, Artur, Peng, Pan, Sohler, Christian, 2016. Relating two property testing models for bounded degree directed graphs. 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
- Czumaj, Artur, 2015. Random permutations using switching networks. 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
- Czumaj, Artur, Peng, Pan, Sohler, Christian, 2015. Testing cluster structure of graphs. 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
- Adamaszek, Anna, Czumaj, Artur, Englert, Matthias, Räcke, Harald, 2012. An O(log k)-competitive algorithm for generalized caching. 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
- Adamaszek, Anna, Czumaj, Artur, Englert, Matthias, Räcke, Harald, 2011. Almost tight bounds for reordering buffer management. 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
- Czumaj, Artur, Monemizadeh, Morteza, Onak, Krzysztof, Sohler, Christian, 2011. Planar graphs : random walks and bipartiteness testing. 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
- Czumaj, Artur, 2010. Local graph exploration and fast property testing. 16th Annual European Symposium on Algorithms (ESA 2010), Liverpool, England, 6-8 Sep 2010, Published in Lecture Notes in Computer Science, pp. 410-414
- Czumaj, Artur, Sohler, Christian, 2010. Sublinear-time algorithms. Workshop on Property Testing, Tsinghua University, Peoples Republic of China, Published in Property Testing : Current Research and Surveys, pp. 41-64
- Czumaj, Artur, Sohler, Christian, 2010. Testing expansion in bounded-degree graphs. Meeting on Combinatorics and Probability, Mathemat Res Inst, Oberwolfach, Germany, April 26-May 02, 2009, Published in Combinatorics, Probability and Computing, pp. 693-709
- Adamaszek, Michal, Czumaj, Artur, Sohler, Christian, 2010. Testing monotone continuous distributions on high-dimensional real cubes. Workshop on Property Testing, Tsinghua University, Peoples Republic of China, Published in Property Testing : Current Research and Surveys, pp. 228-233
- Czumaj, Artur, Adamaszek, Michal, Sohler, Christian, 2010. Testing monotone continuous distributions on high-dimensional real cubes. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10), Austin, Texas, 17-19 Jan 2010, Published in SIAM, pp. 56-65
- Adamaszek, Anna, Czumaj, Artur, Lingas, Andrzej, 2009. PTAS for k-tour cover problem on the plane for moderately large values of k. 20th International Symposium on Algorithms and Computations (ISAAC 2009), Honolulu, HI, December 16-18, 2009, Published in Lecture Notes in Computer Science, pp. 994-1003
- Czumaj, Artur, Sohler, Christian, 2007. On testable properties in bounded degree graphs. 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
- Czumaj, Artur, Sohler, Christian, 2007. Sublinear-time approximation algorithms for clustering via random sampling. 12th International Conference on Random Structures and Algorithms, Poznan, Poland, 01-05 Aug 2005, Published in Random Structures & Algorithms, pp. 226-256
- Czumaj, Artur, Sohler, Christian, 2007. Testing expansion in bounded-degree graphs. 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
- Czumaj, Artur, Lingas, Andrzej, 2007. Finding a heaviest triangle is not harder than matrix multiplication. 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

- Czumaj, Artur, 1992. An optimal parallel algorithm for computing a near-optimal order of matrix multiplications. University of Warwick. Department of Computer Science
- Czumaj, Artur, 1992. Parallel algorithm for the matrix chain product problem. University of Warwick. Department of Computer Science

Title | Funder | Award start | Award end |
---|---|---|---|

Theoretical Foundations of Modern Parallel and Distributed Algorithms | EPSRC | 01 Apr 2021 | 31 Mar 2024 |

Weizmann - UK Joint Research Program: Combinatorial and Algorithmic Primitives for Modern Networks | Weizmann Institute of Science | 01 Oct 2018 | 30 Sep 2022 |

IBM Faculty Award: Efficient Processing Methods for Big Graphs | IBM | 01 Oct 2017 | 30 Aug 2022 |

Sublinear Algorithms for Big Graphs | EPSRC | 01 Jan 2016 | 31 Dec 2018 |

Scalable Indexing and Compression: Algorithms and Combinatorics (Early Career Fellowship for Golnaz Badkobeh) | Leverhulme Trust | 01 Sep 2015 | 31 Aug 2018 |

International Exchanges Scheme - 2013/R1; Advances in Approximation Algorithms. | Royal Society | 01 Sep 2013 | 29 Feb 2016 |

Extension to DIMAP - The centre for discrete mathematics and its applications | EPSRC | 26 Mar 2013 | 25 Mar 2014 |

PATTERN MATCHING ALGORITHMS FOR STREAMING DATA (PDF FOR BEN SACH) | EPSRC | 01 Oct 2010 | 30 Sep 2013 |

Efficient Decentralised Approaches in Algorithmic Game Theory | EPSRC | 01 Oct 2009 | 30 Sep 2012 |

Advances in Sublinear Algorithms | EPSRC | 01 Sep 2009 | 31 Aug 2012 |

The Interplay between Algorithms and Randomness | Weizmann Institute of Science | 01 Jan 2010 | 31 Dec 2011 |

Workshop on extremal and probabilistic combinatorics - PI is J Hladky, PhD student | British Combinatorial Committee | 18 Jul 2010 | 25 Jul 2010 |

Workshop on Extremal and Probabilistic Combinatorics - J Hladky PI | London Mathematical Society | 18 Jul 2010 | 25 Jul 2010 |