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.
- 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
- 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, 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, 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, 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, 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
- 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, 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, 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. Simple, deterministic, constant-round coloring in the congested clique. 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020), Virtual conference, 3-6 Aug 2020
- 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
- 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, 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, 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, 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, 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, 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, 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 |