Artur Czumaj (University of Warwick)

Artur Czumaj

Department of Computer Science and
Centre for Discrete Mathematics and its Applications (DIMAP)
University of Warwick
Coventry CV4 7AL
United Kingdom
Room: CS.213
Phone: +44 +24 7657 3796
Fax: +44 +24 7657 3024
E-mail:
URL: http://www.dcs.warwick.ac.uk/~czumaj/

Head of Department of Computer Science at the University of Warwick
Director of the Centre for Discrete Mathematics and its Applications (DIMAP)
Member of the Foundations of Computer Science (FoCS) Research Group

My research is supported by EPSRC grants EP/D063191/1, EP/G064679/1, EP/G069034/1, and also by a Weizmann-UK Making Connections Grant »The Interplay between Algorithms and Randomness«.
Information for Students: I have no summer internships!!! (and apologies for not responding to such email requests)

Publications

Research areas:
Theoretical Computer Science, especially the analysis and design of algorithms and data structures
The main fields of research are:: Randomized algorithms and their probabilistic analysis; Graph theory, graph algorithms and computational geometry; Algorithmic aspects of game theory and economics; Combinatorics and discrete mathematics; String/pattern matching (applications and efficient implementations); Parallel and distributed algorithms and communication networks; Complexity theory

Teaching:

Some ideas for 3rd year projects.
In the academic year 2011/2012, I will be teaching:
- CS 409: Algorithmic Game Theory
In the academic year 2010/2011, I was teaching:
- CS 409: Algorithmic Game Theory
In the academic year 2009/2010, I was teaching:
- CS 409: Algorithmic Game Theory
In the academic year 2008/2009, I was teaching:
In the academic year 2007/2008, I was teaching:
In the academic year 2006/2007, I was teaching:
- CS244: Algorithm Design
- CS301: Complexity of Algorithms

Office hours: Monday 14:00 - 16:00 (in the term time only)

Program Committees: SODA 2011, IPDPS 2010, WINE 2009, SAGA 2009, APPROX 2009, FOCS 2008, ICALP 2008, WG 2008, CO 2008, ESA 2007, STOC 2007, PODC 2005, SWAT 2004, and STACS 2000.

Events I am/was involved in organizing:

39th International Colloquium on Automata, Languages and Programming (ICALP 2012), University of Warwick, July 9 - 13, 2012.

Warwick-Weizmann Workshop 2011, Department of Computer Science and DIMAP, University of Warwick, September 12 - 16, 2011 (co-organized by Amin Coja-Oghlan, Matthias Englert, Uri Feige, and Robert Krauthgamer).

Workshop on Sublinear Algorithms, Bertinoro International Center for informatics, University of Bologna Residential Center Bertinoro (Forli), Italy, May 22 - 27, 2011 (co-organized by Piotr Indyk, Robert Krauthgamer, and Ronitt Rubinfeld).

Weizmann-Warwick Workshop 2010, Weizmann Institute of Science, Israel, December 5 - 9, 2010 (co-organized by Amin Coja-Oghlan, Uri Feige, Robert Krauthgamer, and Harry Räcke).

DIMAP Summer School on Approximation and Randomized Algorithms, DIMAP, University of Warwick, July 12 - 16, 2010 (co-organized with Matthias Englert and Harry Räcke).

Dagstuhl seminar No. 08341 on »Sublinear Algorithms«, Dagstuhl Castle, Leibniz Center for Informatics, Germany, August 17 - 22, 2008 (co-organized with S. Muthukrishnan, R. Rubinfeld, and C. Sohler).

»Mike66«, a workshop in honour of Professor Mike Paterson's 66th birthday, DIMAP, University of Warwick, September 18 - 19, 2008 (co-organized with Leslie Ann Goldberg and Uri Zwick).

DIMAP Algorithms Day, DIMAP, University of Warwick, October 24, 2008 (co-organized with Matthias Englert, Oded Lachish, and Rahul Savani).

25th British Colloquium for Theoretical Computer Science (BCTCS), University of Warwick, April 6 - 9, 2009 (co-organized with Sara Kalvala and Steve Matthews).

3rd Workshop on »Flexible Network Design«, DIMAP, University of Warwick, UK, July 13 - 16, 2008 (co-organized with A. Gupta, S. Leonardi, R. Ravi, and H. Räcke).

DIMAP Workshop on »Algorithmic Game Theory«, University of Warwick, UK, March 25 - 28, 2007.

Workshop on »Algorithmic Graph Theory«, Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach, Germany, February 12 - 18, 2006 (co-organized by K. Jansen, F. Meyer auf der Heide, and I. Schiermeyer).

Dagstuhl seminar No. 05291 on »Sublinear Algorithms«, Dagstuhl Castle, the International Conference and Research Center for Computer Science, Germany, July 17 - 22, 2005 (co-organized with S. Muthukrishnan, R. Rubinfeld, and C. Sohler).

Draft of »Finding Cycles and Trees in Sublinear Time«, coauthored by O. Goldreich, D. Ron, C. Seshadhri, A. Shapira, and C. Sohler, manuscript, July 2010, arXive:1007.4230.

Draft of »Testing Expansion in Bounded-Degree Graphs« © coauthored by Christian Sohler (FOCS'2007)

Draft of »Small Space Representations for Metric Min-Sum k-Clustering and their Applications« © coauthored by Christian Sohler (Preliminary version appeared in STACS'2007)

Draft of the full version of »Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs« © with Asaf Shapira and Christian Sohler. (Preliminary version appeared in SODA'2007)
Draft of »Finding a heaviest triangle is not harder than matrix multiplication« © with Andrzej Lingas. (Preliminary version appeared in SODA'2007)

Draft of a survey on sublinear-time algorithms © (coauthored by Christian Sohler) that appeared in Bulletin of the EATCS, 89: 23 - 47, June 2006.

Draft of a paper »Faster algorithms for finding lowest common ancestors in directed acyclic graphs«, coauthored by Miroslaw Kowaluk and Andrzej Lingas, that appeared in Theoretical Computer Science, 380(1-2): 37 - 46, June 2007. (This paper combines my earlier draft Improved algorithms for the all-pairs lowest common ancestor problem in directed acyclic graphs (joint work with Andrzej Lingas) with ICALP 2005 paper LCA queries in directed acyclic graphs by Miroslaw Kowaluk and Andrzej Lingas.)

Materials from the Dagstuhl seminar on Sublinear Algorithms that I (together with S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler) organized in July 2005. (A picture from the seminar.)

Full version of the paper »Tight Bounds for Worst-Case Equilibria« (extended version of SODA'2002 paper, co-authored by B. Vöcking);
this paper has been submitted to Journal of Algorithms in 2002, accepted there in 2003 ... and finally appeared in ... ACM Transactions on Algorithms, 3(1), February 2007.

Drafts of full versions of two papers on property testing that have been published in conference proceedings long time ago:
- Part I of ESA 2000 paper »Testing Convex Position«
- Part II of ESA 2000 paper »Testing Euclidean Minimum Spanning Trees in the Plane«

Some pictures from various conferences:
- Summer School in Warwick, July 2010; and another picture during excursion to Bletchley Park
- RSA ...
- ICALP 2009, enjoying Rhodes and its food, and giving a presentation
- Mike 66, Workshop in Honour of Prof. Mike Paterson's 66th Birthday, September 2008; one more picture, and yet one more.
- Dagstuhl 2008 (workshop "Sublinear Algorithms," August 2008) (workshop web page)
- Group picture from Snowdonia and another picture
- Dagstuhl 2007 (workshop "Probabilistic Methods in the Design and Analysis of Algorithms," September 2007) (workshop web page)
- Dagstuhl 2007 (workshop "Computational Social Systems and the Internet," July 2007) (workshop web page)
- DIMAP launch, March 2007
- Dagstuhl 2005 (workshop "Sublinear Algorithms," July 2005) (workshop web page)
- Dagstuhl 2005 (workshop "Design and Analysis of Randomized and Approximation Algorithms," May 2005) (workshop web page)
- Dagstuhl 2005 (workshop "Computing and Markets," January 2005) (workshop web page)
- Oberwolfach 2004 (workshop "Approximation Algorithms for NP-Hard Problems," June 2004)
- Braunwald (near Zurich - Andrzej R. is next to me and Alps are in the background) ... and another (group) picture
- Dagstuhl 2003 (workshop "Algorithmic Game Theory and the Internet," June 2003)
- Dagstuhl 2003 (another view)
- Oberwolfach 2000 (workshop "Efficient Algorithms," August 2000)
- RS&A conference in Poznan, August 1999 (bonfire, I'm sitting in 2nd row)

Poznan, November 2010

Current students:

My old web page at the Department of Computer Science, New Jersey Institute of Technology

My (old and out-dated) Web-page from Paderborn, in Germany, where I spent over 6 years (1993-1999) working in the Research Group of Prof. Meyer auf der Heide.

My undergraduate study: Faculty of Mathematics, Informatics and Mechanics at the Warsaw University
- Computer Science students from Warsaw University are the winners of the 2007 World Championship (the 31st ACM International Collegiate Programming Contest, World Finals, sponsored by IBM, March 12 - 16, 2007), and
- Computer Science students won the 2003 World Championship (The 27th Annual ACM International Collegiate Programming Competition (World Finals))

My high school: XIV LO im. Staszica (aka Gottwald). If you're persistent (and can read in Polish), you might even find there a picture of my class taken many-many-many years ago. But in that case, I doubt if you'd be able to recognize me. (OK, the the photo is here.)