Please read our student and staff community guidance on COVID-19
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.

  • 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, Sohler, Christian, 2019. 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 Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019)
  • 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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
  • 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
Title Funder Award start Award end
IBM Faculty Award: Efficient Processing Methods for Big Graphs IBM 01 Oct 2017 31 Dec 2020
Weizmann - UK Joint Research Program: Combinatorial and Algorithmic Primitives for Modern Networks Weizmann Institute of Science 01 Oct 2018 30 Sep 2020
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