Skip to main content Skip to navigation

Artur Czumaj

Job Title
Professor
Department
Computer Science
Phone
+44 24 7657 3796
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.

  • Coy, Sam, Czumaj, Artur, Davies-Peck, Peter, Mishra, Gopinath, 2024. Parallel derandomization for coloring. 38th IEEE International Parallel & Distributed Processing Symposium (IPDPS), San Francisco, 27-31 May 2024, Published in Proceedings of the 38th IEEE International Parallel & Distributed Processing Symposium (IPDPS)
  • Coy, Sam, Czumaj, Artur, Mishra, Gopinath, 2023. On parallel k-center clustering. SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures, Orlando, Florida, USA, 16-19 Jun 2023, Published in Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 65-75
  • Coy, Sam, Czumaj, Artur, Davies, Peter, Mishra, Gopinath, 2023. Optimal (degree+1)-coloring in congested clique. ICALP 2023: 50th EATCS International Colloquium on Automata, Languages and Programming, Paderborn, Germany, 10-14 Jul 2023, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 45:1-45:16
  • Czumaj, Artur, 2023. Modern parallel algorithms. 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 3:1-3:2
  • 'Czumaj, Artur, 'Jiang, Shaofeng H.-C., 'Krauthgamer, Robert, 'Vesel?, Pavel, 2022. 'Streaming algorithms for geometric Steiner forest. 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
  • 'Czumaj, Artur, 'Jiang, Shaofeng H.-C., 'Krauthgamer, Robert, 'Vesely, Pavel, 'Yang, Mingwei, 2022. 'Streaming facility location in high dimension via geometric hashing. 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)
  • 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. 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, 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. 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 PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 469-479
  • 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, 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, 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, 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
  • 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
  • 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, 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, 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, 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, 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
  • 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
  • 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
  • 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
  • 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
  • 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, 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. 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
  • 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, 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, 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. 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, 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
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 2023
IBM Faculty Award: Efficient Processing Methods for Big Graphs IBM UNITED KINGDOM TRUST 01 Oct 2017 31 Aug 2023
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
Professor of Computer Science
Director of DIMAP
Office Hours

15:00 - 17:00 Monday (during term time only)

Research Page