Artur Czumaj
Publications (selection)
February 10, 2022
Artur Czumaj, Shaofeng H.C. Jiang, Robert Krauthgamer, and Pavel Veselý.
Streaming Algorithms for Geometric Steiner Forest.
To appear in Proceedings of the 49th International Colloquium on Automata, Languages and Programming (ICALP 2022), pages 37:1  37:20, Paris, France, July 4  8, 2022.
Also in CoRR abs/2011.04324.

Sam Coy and Artur Czumaj.
Deterministic Massively Parallel Connectivity.
To appear in Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, June 20  24, 2022.
Also in CoRR abs/2108.04102.

Artur Czumaj and Andrzej Lingas.
On Truly Parallel Time in Population Protocols.
In CoRR abs/2108.11613.

Artur Czumaj, Peter Davies, and Merav Parter.
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.
ACM Transactions on Algorithms (TALG), 17(2): 16:116:27, June 2021.
A preliminary version appeared in SPAA 2020 and also in CoRR abs/1912.05390.

Artur Czumaj, Peter Davies, and Merav Parter.
Component Stability in LowSpace Massively Parallel Computations.
In Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), pages 481  491, virtual event, Italy, July 26  30, 2021.
Also in CoRR abs/2106.01880.

Artur Czumaj, Peter Davies, and Merav Parter.
Improved Deterministic (Δ+1)Coloring in LowSpace MPC.
In Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), pages 469  479, virtual event, Italy, July 26  30, 2021.
Also in CoRR abs/2112.05831.

Artur Czumaj, George Kontogeorgiou, Mike Paterson.
Haystack Hunting Hints and Locker Room Communication.
In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP 2021), pages 55:1  55:20, virtual event, Glasgow, Scotland, July 12  16, 2021.
Also in CoRR abs/2008.11448.

A. Czumaj and Peter Davies.
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks.
Journal of the ACM, 68(2): Article 13, March 2021.
A preliminary version appeared at PODC 2017 and also in CoRR abs/1703.01859.

A. Czumaj, J. Łącki, A. Mądry, S. Mitrović, K. Onak, P. Sankowski.
Round Compression for Parallel Matching Algorithms.
SIAM Journal on Computing, 49(5): STOC181–STOC1844, 2020, a special issue devoted to selected papers from STOC 2018.
A preliminary version appeared in STOC 2018 and also in CoRR abs/1707.03478.

A. Czumaj and Christian Konrad.
Detecting Cliques in CONGEST Networks.
Distributed Computing 33(6): 533  543, 2020.
A preliminary version appeared in Proceedings of the 32nd International Symposium on Distributed Computing October (DISC 2018), pages 16:1  14, New Orleans, LA, USA, October 15  19, 2018 and in CoRR abs/1807.01070.

Artur Czumaj, Peter Davies, and Merav Parter.
Simple, Deterministic, Constantround Coloring in the CONGESTED CLIQUE.
In Proceedings of the 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 309  318, virtual event, Italy, August 3  7, 2020.
Full version to appear in SIAM Journal on Computing, 2021.
Also in CoRR abs/2009.06043.

Artur Czumaj, Peter Davies, and Merav Parter.
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.
In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), pages 175  185, virtual event, USA, July 14  17, 2020.
Full version in ACM Transactions on Algorithms (TALG), 17(2): 16:116:27, June 2021.
Also in CoRR abs/1912.05390.

Artur Czumaj, Hendrik Fichtenberger, Pan Peng, Christian Sohler.
Testable Properties in General Graphs and Random Order Streaming.
In Proceedings of the 24th International Conference on Randomization and Computation (RANDOM 2020), pages 16:1  16:20, virtual event, USA, August 17  19, 2020.
Also in CoRR abs/1905.01644.

Artur Czumaj and Christian Sohler.
Sublinear Time Approximation of the Cost of a Metric knearest Neighbor Graph.
In Proceedings of the 31st ACMSIAM Symposium on Discrete Algorithms (SODA 2020), pages 2973  2992, Salt Lake City, UT, January 5  8, 2020.

Artur Czumaj and Christian Sohler.
A Characterization of Graph Properties Testable for General Planar Graphs with Onesided Error (It's all about forbidden subgraphs).
In Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019), pages 1513  1536, Baltimore, MD, November 9  12, 2019.
For a full version, see CoRR abs/1909.10647.

A. Czumaj, J. Łącki, A. Mądry, S. Mitrović, K. Onak, P. Sankowski.
Round Compression for Parallel Matching Algorithms.
In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), pages 471  484, Los Angeles, CA, USA, June 25  29, 2018.
A preliminary version appeared in CoRR abs/1707.03478.
Full version in SIAM Journal on Computing, 49(5): STOC181–STOC1844, 2020, a special issue devoted to selected papers from STOC 2018.

A. Czumaj and Peter Davies.
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks [pdf].
In Proceedings of the 36th ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC 2017), pages 3  12, Washington, DC, USA, July 25  27, 2017. Best student paper.
Full version to appear in Journal of the ACM, 68(2): Article 13, 2021.
A preliminary version appeared in CoRR abs/1703.01859.

A. Czumaj and Peter Davies.
Faster Deterministic Communication in Radio Networks.
SIAM Journal on Computing, 39(5): 1957  1987, February 2010.
A preliminary version appeared in Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), article 139, Rome, Italy, July 12  15, 2016 and at CoRR abs/1506.00853.

A. Czumaj and Peter Davies.
Randomized Communication Without Network Knowledge.
A Brief Announcement of this result appears in Proceedings of the 32nd International Symposium on Distributed Computing October (DISC 2018), pages 44:1  3, New Orleans, LA, USA, October 15  19, 2018.
For a full version, see CoRR abs/1805.04842.

A. Czumaj and Peter Davies.
Deterministic Blind Radio Networks.
In Proceedings of the 32nd International Symposium on Distributed Computing October (DISC 2018), pages 15:1  17, New Orleans, LA, USA, October 15  19, 2018.
A preliminary version appeared in CoRR abs/1805.04838.

M. Cygan, A. Czumaj, M. Mucha, and P. Sankowski.
Online Facility Location with Deletions.
In Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), pages 21:1  15, Helsinki, Finland, August 20  22, 2018.

A. Czumaj, M. Fasoulakis, and M. Jurdziński.
Multiplayer Approximate Nash Equilibria.
In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), pages 1511  1513, Sao Paulo, Brazil, May 8  12, 2017.

A. Czumaj, M. Fasoulakis, and M. Jurdziński.
ZeroSum Game Techniques for Approximate Nash Equilibria.
In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), pages 1514  1516, Sao Paulo, Brazil, May 8  12, 2017.

A. Czumaj,
A. Deligkas,
M. Fasoulakis,
J. Fearnley,
M. Jurdziński, and
R. Savani.
Distributed Methods for Computing Approximate Equilibria.
In Proceedings of the 12th Conference on Web and Internet Economics (WINE 2016), pages 15  28, Montreal, Canada, December 11  14, 2016. LNCS 10123.
A preliminary version appeared at CoRR abs/1512.03315.

A. Czumaj and Peter Davies.
Brief Announcement: Optimal Leader Election in Multihop Radio Networks.
In Proceedings of the 35th ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC 2016), pages 47  49, Chicago, Illinois, USA, July 25  28, 2016.
A preliminary version appeared at CoRR abs/1505.06149.

A. Czumaj, P. Peng, and C. Sohler.
Relating Two Property Testing Models for Bounded Degree Directed Graphs.
In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), pages 1033  1045, Cambridge, MA, June 19  21, 2016.

A. Czumaj, M. Fasoulakis, and M. Jurdziński.
Approximate Plutocratic and Egalitarian Nash Equilibria.
In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), pages 1409  1410, Singapore, May 9  13, 2016.

A. Czumaj and Peter Davies.
Communicating with Beeps.
In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS 2015), pages 420  435, Rennes, France, December 14  17, 2015.
Also available at CoRR abs/1505.06107.

A. Czumaj, M. Fasoulakis, and M. Jurdziński.
Approximate Nash Equilibria with Near Optimal Social Welfare.
In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pages 504  510, Buenos Aires, Argentina, July 25  31, 2015.

A. Czumaj.
Random Permutations using Switching Networks [pdf].
In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pages 703  712, Portland, OR, June 15  17, 2015.

A. Czumaj, P. Peng, and C. Sohler.
Testing Cluster Structure of Graphs [pdf].
In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pages 723  732, Portland, OR, June 15  17, 2015.
Also available at CoRR abs/1504.03294.

A. Czumaj, M. Fasoulakis, and M. Jurdziński.
Approximate Wellsupported Nash Equilibria in Symmetric Bimatrix Games.
In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT 2014), pages 244  255, Patras, Greece, September 30  October 2, 2014. LNCS 8768.
Also available at CoRR abs/1407.3004.

A. Czumaj and B. Vöcking.
Thorp Shuffling, Butterflies, and NonMarkovian Couplings.
In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), pages 344  355, Copenhagen, Denmark, July 811, 2014. LNCS 8572.

A. Czumaj,
O. Goldreich,
D. Ron,
C. Seshadhri,
A. Shapira, and
C. Sohler.
Finding Cycles and Trees in Sublinear Time.
Random Structures and Algorithms 45(2): 139  184, September 2014.
See also CoRR abs/1007.4230.

A. Czumaj,
R. Elsässer,
L. Gąsieniec
T. Sauerwald, and
X. Wang.
Fast Message Dissemination in Random Geometric Networks.
Distributed Computing, 26(1): 1  24, February 2013.

A. Czumaj,
C. Lammersen,
M. Monemizadeh, and
C. Sohler.
(1+ε)Approximation for Facility Location in Data Streams.
In Proceedings of the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'2013), pages 1710  1728,
New Orleans, LA, January 6  8, 2013. SIAM, Philadelphia, PA, 2013.

P. Berenbrink,
A. Czumaj,
M. Englert,
T. Friedetzky, and
L. Nagel.
Multiplechoice Balanced Allocation in (almost) Parallel.
In Proceedings of the 16th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'2012), pages 411  422,
MIT, Cambridge, MA, August 15  17, 2012.
LNCS 7408, SpringerVerlag, Berlin, Heidelberg, 2012.

A. Adamaszek,
A. Czumaj,
M. Englert, and
H. Räcke.
Optimal Online Buffer Scheduling for Block Devices.
In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC'12), pages 589  598, New York, NY, May 19  22, 2012. ACM Press, New York, NY, 2012.
[pdf ©]

A. Adamaszek,
A. Czumaj,
M. Englert, and
H. Räcke.
An O(log k)competitive Algorithm for Generalized Caching.
In Proceedings of the 23rd Annual ACMSIAM Symposium on Discrete Algorithms (SODA'2012), pages 1681  1689, Kyoto, Japan, January 17  19, 2012. SIAM, Philadelphia, PA, 2012.
[pdf ©]

A. Czumaj,
M. Monemizadeh,
K. Onak, and
C. Sohler.
Planar Graphs: Random Walks and Bipartiteness Testing.
In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS'11), pages 423  432, Palm Springs, CA, October 23  25, 2011.
IEEE Computer Society Press, Los Alamitos, CA, 2011.
[pdf ©].
See also CoRR abs/1407.2109.

A. Adamaszek,
A. Czumaj,
A. Lingas, and
J.O. Wojtaszczyk.
Approximation Schemes for Capacitated Geometric Network Design.
In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP'11), pages 25  36, Zürich, Switzerland, July 4  8, 2011.
LNCS 6755, SpringerVerlag, Berlin, Heidelberg, 2011.
[pdf ©].

A. Adamaszek,
A. Czumaj,
M. Englert, and
H. Räcke.
Almost Tight Bounds for Reordering Buffer Management.
In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11), pages 607  616,
San Jose, CA, June 6  8, 2011. ACM Press, New York, NY, 2011.
[pdf ©].

A. Czumaj,
J. Czyzowicz,
L. Gąsieniec,
J. Jansson,
A. Lingas,
P. Zylinski.
Approximation Algorithms for BuyatBulk Geometric Network Design.
International Journal of Foundations of Computer Science, 22(8): 1949  1969, 2011.
A preliminary version of the paper appeared in Proceedings of the 11th Algorithms and Data Structures Symposium (WADS'09), pages 168  180, Banff Conference Centre, Banff, Alberta, Canada, August 21  23, 2009. LNCS 5664, SpringerVerlag, Berlin, Heidelberg, 2009.

A. Czumaj.
Local Graph Exploration and Fast Property Testing.
Invited survey paper in Proceedings of the 8th Annual European Symposium (ESA'2010), pages 410  414, Liverpool, UK, September 6  8, 2010. LNCS 6346, SpringerVerlag, Berlin, Heidelberg, 2010.

A. Czumaj and
C. Sohler.
Sublineartime Algorithms.
Invited contribution in Property Testing. Current Research and Surveys, pages 42  66, editd by O. Goldreich, LNCS 6390, SpringerVerlag, Berlin, Heidelberg, 2010.
[DRAFT ©]
This is a slightly updated version of the survey paper that appeared in Bulletin of the EATCS, 89: 23  47, June 2006.

A. Czumaj and
C. Sohler.
Sublinear Clustering.
Invited contribution in Encyclopedia of Machine Learning, Part 20, pages 933  937, edited by Cl. Sammut and G. I. Webb, SpringerVerlag, Berlin, Heidelberg, 2010.

A. Adamaszek,
A. Czumaj, and
A. Lingas.
PTAS for ktour Cover Problem on the Plane for Moderately Large Values of k.
International Journal of Foundations of Computer Science, 21(6): 893  904, 2010.
A preliminary version of the paper appeared in
Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09), pages 994  1003, Hawaii, USA, December 16  18, 2009. LNCS, SpringerVerlag, Berlin, Heidelberg, 2009.
Manuscript, April 2009, available at CoRR abs/0904.2576.

A. Czumaj and
C. Sohler.
Testing Expansion in BoundedDegree Graphs.
Combinatorics, Probability and Computing, 19(56): 693  709.
A preliminary version of the paper appeared in
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07),
pages 570  578, Providence, RI, October 20  23, 2007. [DRAFT ©].

A. Czumaj,
P. Krysta, and
B. Vöcking.
Selfish Traffic Allocation for Server Farms.
SIAM Journal on Computing, 39(5): 1957  1987, February 2010.
A preliminary version of the paper
appeared in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC'02),
pages 287  296, Montreal, Quebec, Canada, May 19  21, 2002.
ACM Press, New York, NY, 2002.
[DRAFT ©]

M. Adamaszek,
A. Czumaj, and
C. Sohler.
Testing Monotone Continuous Distributions on Highdimensional Real Cubes.
In Proceedings of the 21st ACMSIAM Symposium on Discrete Algorithms (SODA'10),
pages 56  65, Austin, Texas, January 17  19, 2010. SIAM, Philadelphia, PA, 2010.
An extended abstract of the paper appeared also in Property Testing. Current Research and Surveys, pages 228  233, editd by O. Goldreich, LNCS 6390, SpringerVerlag, Berlin, Heidelberg, 2010.

A. Czumaj and
C. Sohler.
Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time.
SIAM Journal on Computing, 39(3): 904  922, August 2009.
A preliminary version of the paper
appeared in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC'04),
pages 175  183, Chicago, IL, June 13  15, 2004.
ACM Press, New York, NY, 2004.
[DRAFT of full version ©]

A. Czumaj and
C. Sohler.
Small Space Representations for Metric Minsum kClustering and Their Applications.
Theory of Computing Systems, 46(3): 416  442, April 2010, special issue of the journal devoted to selected papers from STACS'2007.
A preliminary version of the paper
appeared in Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS'07),
pages 536  548, Aachen, Germany, February 22  24, 2007. SpringerVerlag, Berlin, 2007.
[DRAFT ©].

A. Czumaj and
A. Lingas.
Finding a Heaviest VertexWeighted Triangle Is not Harder than Matrix Multiplication.
SIAM Journal on Computing, 39(2): 431  444, June 2009.
A preliminary version of the paper
appeared in Proceedings of the 18th ACMSIAM Symposium on Discrete Algorithms (SODA'07),
pages 986  994, New Orleans, LA, January 7  9, 2007.
SIAM, Philadelphia, PA, 2007.
[DRAFT ©]

A. Czumaj,
A. Shapira, and
C. Sohler.
Testing Hereditary Properties of Nonexpanding BoundedDegree Graphs.
SIAM Journal on Computing, 38(6): 2499  2510, April 2009.
A preliminary version of the paper entitled
On
Testable Properties in Bounded Degree Graphs (authors A. Czumaj and C. Sohler)
appeared in Proceedings of the 18th ACMSIAM Symposium on Discrete Algorithms
(SODA'07), pages 494  501, New Orleans, LA, January 7  9, 2007.
SIAM, Philadelphia, PA, 2007.
A draft of the paper appeared in
ECCC TR07083
[DRAFT
©].

A. Czumaj.
Euclidean Traveling Salesperson Problem.
In Encyclopedia of Algorithms, edited by M.J. Kao, Springer 2008.

A. Czumaj and A. Lingas.
Minimum kConnected Geometric Networks.
In Encyclopedia of Algorithms, edited by M.J. Kao, Springer 2008.

A. Czumaj and B. Vöcking.
Price of Anarchy for Machines Models.
In Encyclopedia of Algorithms, edited by M.J. Kao, Springer 2008.

A. Czumaj and
C. Sohler.
Testing Euclidean Minimum Spanning Trees in the Plane.
ACM Transactions on Algorithms, 4(3), June 2008.

A. Czumaj and
X. Wang.
Fast Message Dissemination in Random Geometric Adhoc Radio Networks.
In Proceedings of the 18th
International Symposium on Algorithms and Computation (ISAAC'07),
pages 220  231,
Sendai, Japan, December 17  19, 2007.
SpringerVerlag, Berlin, 2007.

A. Czumaj and
X. Wang.
Communication Problems in Random LineofSight Adhoc Radio Networks.
In Proceedings of the 4th Symposium
on Stochastic Algorithms, Foundations, and Applications (SAGA'07),
pages 70  81, Zurich, Switzerland, September 13  14, 2007.
SpringerVerlag, Berlin, 2007.
[DRAFT ©].

A. Czumaj,
G. Frahling, and
C. Sohler.
Efficient Kinetic Data Structures for MaxCut.
In 19th Canadian Conference
on Computational Geometry (CCCG'07),
pages 157  160, Ottawa, Canada, August 20  22, 2007.
[DRAFT ©].

A. Czumaj and A. Lingas.
Approximation Schemes for Minimumcost kConnectivity Problems in Geometric Graphs.
Chapter 51 in Handbook
of Approximation Algorithms and Metaheuristics, edited by
T.F. Gonzalez,
CRC Press,
Boca Raton, FL, 2007.
[DRAFT ©]

A. Czumaj,
M. Kowaluk, and
A. Lingas.
Faster Algorithms for Finding Lowest Common Ancestors in Directed Acyclic Graphs.
Theoretical Computer Science, 380(12): 37  46, June 2007.
[DRAFT ©]

A. Czumaj and
B. Vöcking.
Tight Bounds for WorstCase Equilibria.
ACM Transactions on Algorithms, 3(1), February 2007,
special issue devoted to selected papers from SODA'02.
[DRAFT ©]
A preliminary version
appeared in Proceedings of the 13th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'02),
pages 413  420, San Francisco, CA, January 6  8, 2002. SIAM, Philadelphia, PA, 2002.

A. Czumaj and
C. Sohler.
SublinearTime Approximation Algorithms for Clustering via Random Sampling.
Random Structures and Algorithms, 30(12): 226  256, January  March 2007.
A
preliminary version appeared in Proceedings of the 31st
International Colloquium on Automata, Languages and Programming (ICALP'04),
pages 396  407, Turku, Finland, July 12  16, 2004.
Volume 3142 of Lecture Notes in Computer Science edited by J. Diaz, J. Karhumaki, A. Lepisto, and D. Sannella.
SpringerVerlag, 2004.
[DRAFT ©] .

R. Beier,
A. Czumaj,
P. Krysta, and
B. Vöcking.
Computing
Equilibria for a Service Provider Game with (Im)perfect Information.
ACM Transactions on Algorithms, 2(4): 679  706, October 2006,
special issue devoted to selected papers from SODA'04.
[DRAFT ©]
A preliminary version entitled
"Computing Equilibria for Congestion Games with (Im)perfect Information"
appeared in Proceedings of the 15th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'04),
pages 739  748, New Orleans, LA, January 11  13, 2004.
SIAM, Philadelphia, PA, 2004.

A. Czumaj and
W. Rytter.
Broadcasting Algorithms in Radio Networks with Unknown Topology.
Journal of Algorithms, 60(2): 115  143, August 2006.
[DRAFT ©]
A preliminary version appeared in
Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03),
pages 492  501, Cambridge, MA, October 11  14, 2003.
IEEE Computer Society Press, Los Alamitos, CA, 2003.
[DRAFT ©]

A. Czumaj and
C. Sohler.
Sublineartime Algorithms.
Bulletin of the EATCS, 89: 23  47, June 2006.
[DRAFT ©]
A slightly updated version appeared in Property Testing. Current Research and Surveys, pages 42  66, editd by O. Goldreich, LNCS 6390, SpringerVerlag, Berlin, Heidelberg, 2010.

P. Berenbrink,
A. Czumaj,
A. Steger, and
B. Vöcking.
Balanced Allocations: The Heavily Loaded Case.
SIAM Journal on Computing, 35(6): 1350  1385, March 2006.
A
preliminary version appeared in Proceedings of the
32nd Annual ACM Symposium on Theory of Computing (STOC'00),
pages 745  754, Portland, OR, May 21  23, 2000.
ACM Press, New York, NY, 2000.
[DRAFT ©]

A. Czumaj,
F. Ergün,
L. Fortnow,
A. Magen,
I. Newman,
R. Rubinfeld, and
C. Sohler.
Sublineartime Approximation of Euclidean Minimum Spanning Tree.
SIAM Journal on Computing, 35(1): 91  109, 2005.
A preliminary version appeared in
Proceedings of the 14th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'03),
pages 813  822, Baltimore, MD, January 12  14, 2003.
SIAM, Philadelphia, PA, 2003.
[DRAFT ©]

A. Czumaj and
C. Sohler.
Abstract Combinatorial Programs and Efficient Property Testers.
SIAM Journal on Computing, 34(3): 580  615, 2005.
A preliminary version appeared in
Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer
Science (FOCS'02), pages 83  92, Vancouver, BC, Canada, November 16  19, 2002.
IEEE Computer Society Press, Los Alamitos, CA, 2002.
[DRAFT ©]

A. Czumaj,
M. M. Halldórsson,
A. Lingas, and
J. Nilsson.
Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth
.
Information Processing Letters, 94(2): 49  53, April 30, 2005.
A preliminary version
(authored by A. Czumaj, A. Lingas, and J. Nilsson,
entitled Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth)
appeared in Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC'03),
pages 544  553, Kyoto, Japan, December 15  17, 2003.
Volume 2906 of Lecture Notes in Computer Science edited by T. Ibaraki, N. Katoh, and H. Ono, SpringerVerlag, Berlin, 2003.
[DRAFT ©]

A. Czumaj and
C. Sohler.
Testing Hypergraph Coloring.
Theoretical Computer Science,
331(1): 37  52, February 15, 2005. Special issue
devoted to the selected papers from the 28th ICALP.
[DRAFT ©]
A preliminary version
appeared in Proceedings of the 28th International Colloquium on Automata, Languages
and Programming (ICALP'01),
pages 493  505, Crete, Greece, July 8  12, 2001. Volume 2076 of
Lecture Notes in Computer Science edited by F. Orejas,
P. G. Spirakis, and J. van Leeuwen, SpringerVerlag, Berlin, 2001.

A. Berger,
A. Czumaj,
M. Grigni, and
H. Zhao.
Approximation Schemes for Minimum 2Connected Spanning Subgraphs in Weighted Planar Graphs.
In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05),
pages 472  483, Mallorca, Spain, October 3  6, 2005.
Volume 3669 of Lecture Notes in Computer Science edited by
G. S. Brodal and S. Leonardi. SpringerVerlag, 2005.

M. Badoiu,
A. Czumaj,
P. Indyk, and
C. Sohler.
Facility Location in Sublinear Time.
In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming
(ICALP'05), pages 866  877, Lisboa, Portugal, July 11  15, 2005.
Volume 3580 of Lecture Notes in Computer Science edited by Luis Caires,
Giuseppe F. Italiano, Luis Monteiro, et al., SpringerVerlag, 2005.

A. Czumaj and
H. Zhao.
FaultTolerant Geometric Spanners.
Discrete and Computational Geometry,
32(2): 207  230, July 2004.
Special issue devoted to the selected papers from the 19th SoCG.
[DRAFT ©]
A preliminary version appeared in
Proceedings of the 19th ACM Symposium on Computational Geometry (SoCG'03),
pages 1  10, San Diego, CA, June 8  10, 2003.
ACM Press, New York, NY, 2003.

A. Czumaj and
A. Ronen.
On the Expected Payment of Mechanisms for Task Allocation
.
In Proceedings of the
23rd Annual
ACM SIGACTSIGOPS Symposium on Principles of Distributed
Computing (PODC'04), pages 98  106, St. John's,
Newfoundland, Canada, July 25  28, 2004.
ACM Press, New York, NY, 2004.
[DRAFT of full version ©]
Appeared also as a brief announcement
in Proceedings of the 5th
ACM Conference on Electronic Commerce (EC'04), pages 252  253,
New York, NY, May 17  20, 2004. ACM Press, New York, NY, 2004.

G. Cormode,
A. Czumaj and
S. M. Muthukrishnan.
How to Increase the Acceptance Ratios of Top Conferences?
In Proceedings of the
3rd International Conference on Fun with Algorithms (FUN 2004),
Isola d'Elba, Tuscany, Italy, May 26  28, 2004.

A. Czumaj,
M. Grigni,
P. Sissokho, and
H. Zhao.
Approximation Schemes for Minimum 2edgeconnected and Biconnected Subgraphs in Planar Graphs
.
In Proceedings of the 15th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'04),
pages 489  498, New Orleans, LA, January 11  13, 2004.
SIAM, Philadelphia, PA, 2004.
[DRAFT ©]

A. Czumaj.
Selfish Routing on the Internet
.
Chapter 42 in Handbook of Scheduling: Algorithms, Models, and Performance Analysis,
edited by J. Leung,
CRC Press,
Boca Raton, FL, 2004.

A. Czumaj,
L. Gąsieniec,
D. R. Gaur,
R. Krishnamurti,
W. Rytter, and
M. Zito.
Note: On Polynomialtime Approximation Algorithms for the
Variable Length Scheduling Problem.
Theoretical Computer Science, 302(13): 489  495, June 13, 2003.

A. Czumaj,
C. Riley, and
C. Scheideler.
Perfectly Balanced Allocation.
In Proceedings of the 7th International Workshop on Randomization and Approximation
Techniques in Computer Science (RANDOM'03), pages 240  251,
Princeton University, Princeton, NJ, August 24  26, 2003.
Volume 2764 of Lecture Notes in Computer Science,
edited by S. Arora, K. Jansen, J.D.P. Rolim, and A. Sahai,
SpringerVerlag, Berlin, 2003.
[DRAFT of full version ©]

A. Czumaj,
A. Lingas, and
H. Zhao.
PolynomialTime Approximation Schemes for the Euclidean Survivable Network Design Problem.
Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP'02),
pages 973984, Malaga, Spain, July 8  13, 2002.
Volume 2380 of Lecture Notes in Computer Science edited by
P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz, and R. Conejo, SpringerVerlag, Berlin, 2002.

A. Czumaj and
V. Stemann.
Randomized Allocation Processes.
Random Structures and Algorithms, 18(4): 297  331, June 2001.
A preliminary version appeared in Proceedings of the 38th IEEE Symposium on Foundations
of Computer Science (FOCS'97), pages 194  203, Miami Beach, FL, October 19  22, 1997,
IEEE Computer Society Press, Los Alamitos, CA, 1997.
[DRAFT ©]

A. Czumaj,
I. Finch,
L. Gąsieniec,
A. Gibbons,
P. Leng,
W. Rytter, and
M. Zito.
Efficient Web Searching Using Temporal Factors.
Theoretical Computer Science, 262(12): 569  582, July 6, 2001.
A preliminary version appeared in Proceedings of the 6th Workshop on Algorithms and Data
Structures (WADS'99), pages 294  305, Vancouver, Canada,
August 11  14, 1999, volume 1663 of Lecture Notes
in Computer Science edited by F. Dehne, A. Gupta, J.R. Sack,
and R. Tamassia, SpringerVerlag, Berlin, 1999.

A. Czumaj and
C. Sohler.
Property Testing with Geometric Queries
.
Proceedings of the 9th Annual European Symposium on Algorithms (ESA'01),
pages 266  277, BRICS, University of Aarhus, Denmark, August 28  31, 2001.
Volume 2161 of Lecture Notes in Computer Science edited
by F. Meyer auf der Heide, SpringerVerlag, Berlin, 2001.
[DRAFT ©]

A. Czumaj and
C. Sohler.
Soft Kinetic Data Structures.
Proceedings of the 12th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'01),
pages 865  872, Washington, DC, January 7  9, 2001. SIAM, Philadelphia, PA, 2001.

A. Czumaj,
P. Kanarek,
M. Kutylowski, and
K. Lorys.
Switching Networks for Generating Random Permutations
.
In Switching Networks: Recent Advances, pages 25  61,
D.Z. Du and H.Q. Ngo editors, Kluwer Academic Publishers, 2001.
Volume 5 in Series Network Theory and Applications.
A preliminary version
(containing also some other results) appeared in
Proceedings of the 10th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'99),
pages 271  280, Baltimore, Maryland,
January 17  19, 1999. SIAM, Philadelphia, PA, 1999.

A. Czumaj.
Recovery Time of Dynamic Allocation Processes.
Theory of Computing Systems, 33(5/6): 465  487, November 2000;
special issue dedicated to the selected papers presented at SPAA'98.
A preliminary version appeared in
Proceedings of the 10th Annual ACM Symposium on Parallel
Algorithms and Architectures (SPAA'98), pages 202  211,
Puerto Vallarta, Mexico, June 28  July 2, 1998,
ACM Press, New York, NY, 1998.

A. Czumaj and
M. Kutylowski.
Delayed Path Coupling and Generating Random Permutations
.
Random Structures and Algorithms, 17(34): 238  259, November 2000.
A preliminary version
(containing also some other results) appeared in
Proceedings of the 10th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'99),
pages 271280, Baltimore, Maryland,
January 1719, 1999. SIAM, Philadelphia, PA, 1999.

A. Czumaj and
C. Scheideler.
Coloring Nonuniform Hypergraphs: A New Algorithmic Approach to the General Lovász Local Lemma
.
Random Structures and Algorithms, 17(34): 213  237, November 2000.
A preliminary version
appeared in Proceedings of the 11th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'00),
pages 3039, San Francisco, CA, January 9  11, 2000.
SIAM, Philadelphia, PA, 2000.
[DRAFT ©]

B. S. Chlebus,
A. Czumaj,
L. Gąsieniec,
M. Kowaluk, and
W. Plandowski.
Algorithms for the Parallel Alternating Direction Access Machine
.
Theoretical Computer Science, 245(2): 151  173, August 28, 2000.
A preliminary version
appeared in Proceedings of the 21st Symposium on Mathematical
Foundations of Computer Science (MFCS'96),
pages 267  278, Cracow  Poland, September 2  6, 1996,
volume 1113 of Lecture Notes in Computer Science edited
by W. Penczek and A. Szalas, SpringerVerlag, Berlin, 1996.

A. Czumaj,
F. Meyer auf der Heide, and
V. Stemann.
Contention Resolution in Hashing Based Shared Memory Simulations
.
SIAM Journal on Computing, 29(5): 1703  1739, March 2000.
[DRAFT ©]
A preliminary extended abstract entitled
Shared Memory Simulations with TripleLogarithmic Delay
[DRAFT
©]
appeared in Proceedings of the 3rd European Symposium on Algorithms (ESA'95),
pages 46  59, Corfu, Greece, September 25  27, 1995,
volume 979 of Lecture Notes in Computer Science edited by P. Spirakis,
SpringerVerlag, Berlin, 1995.

A. Czumaj,
C. Sohler,
and
M. Ziegler.
Property Testing in Computational Geometry.
Proceedings of the 8th Annual European Symposium on Algorithms (ESA'00),
pages 155  166, Saarbrücken, Germany, September 5  8, 2000.
Volume 1879 of Lecture Notes in Computer Science
edited by M. Paterson, SpringerVerlag, Berlin, 2000.
[DRAFT ©]
Full version has been split into two parts:
Testing Convex Position
[DRAFT ©]
and Testing Euclidean Minimum Spanning Trees in the Plane,
ACM Transactions on Algorithms, 4(3), June 2008.

A. Czumaj and
A. Lingas.
Fast Approximation Schemes for Euclidean MinimumCost MultiConnectivity (Extended abstract)
.
Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP'00),
pages 856  868, Geneva, Switzerland, July 9  15, 2000.
Volume 1853 of Lecture Notes in Computer Science edited by
U. Montanari, J.D.P. Rolim, and E. Welzl,
SpringerVerlag, Berlin, 2000.
[DRAFT ©]

P. Berenbrink,
A. Czumaj,
T. Friedetzky, and
N.D. Vvedenskaya.
On the Analysis of Infinite Parallel Job Allocation Processes via Differential Equations (Extended abstract)
.
Proceedings of the 11th ACM Symposium on Parallel Algorithms and Architectures (SPAA'00),
pages 99  108, Bar Harbor, Maine, July 9  13, 2000.
ACM Press, New York, NY, 2000.
[DRAFT ©]

A. Czumaj and
L. Gąsieniec.
On the Complexity of Determining the Period of a String
.
Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM'00),
pages 412  422, Montreal, Canada, June 21  23, 2000.
Volume 1848 of Lecture Notes in Computer Science edited by
R. Giancarlo and D. Sankoff, SpringerVerlag, Berlin, 2000.
[DRAFT ©]

A. Czumaj and
C. Scheideler.
An Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems
©.
Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC'00),
pages 38  47, Portland, OR, May 21  23, 2000.
ACM Press, New York, NY, 2000.
[DRAFT ©

M. Crochemore,
A. Czumaj,
L. Gąsieniec,
T. Lecroq,
W. Plandowski, and
W. Rytter.
Fast Practical MultiPattern Matching
.
Information Processing Letters, 71(34): 107  113, August 27, 1999.

A. Czumaj,
P. Kanarek,
M. Kutylowski, and
K. Lorys.
Delayed Path Coupling and Generating Random Permutations via Distributed Stochastic Processes
.
Proceedings of the 10th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'99),
pages 271  280, Baltimore, Maryland,
January 17  19, 1999. SIAM, Philadelphia, PA.

A. Czumaj and
A. Lingas.
On Approximability of the MinimumCost kConnected Spanning Subgraph Problem
.
Proceedings of the 10th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
pages 281  290, Baltimore, Maryland,
January 17  19, 1999. SIAM, Philadelphia, PA.

A. Czumaj,
L. Gąsieniec, and
A. Pelc.
Time and Cost TradeOffs in Gossiping
.
SIAM Journal on Discrete Mathematics, 11(3): 400  413, August 1998.
[DRAFT ©]

A. Czumaj,
P. Kanarek,
M. Kutylowski, and
K. Lorys.
Fast Generation of Random Permutations via Networks Simulation
.
Algorithmica, 21(1): 2  20, May 1998.
A preliminary version appeared in Proceedings of the 4th Annual European Symposium
on Algorithms (ESA'96), pages 246  260, Barcelona, Spain, September 25  27, 1996,
volume 1136 of Lecture Notes in Computer Science edited by
J. Diaz and M. Serna, SpringerVerlag, Berlin, 1996.
[DRAFT ©]

A. Czumaj and
A. Lingas.
A Polynomial Time Approximation Scheme for Euclidean Minimum
Cost kConnectivity.
Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP),
pages 682  694, Aalborg, Denmark, July 13  17, 1998,
volume 1113 of Lecture Notes in Computer Science
edited by K. G. Larsen, S. Skyum, and G. Winskel,
SpringerVerlag, Berlin.

A. Czumaj,
F. Meyer auf der Heide, and
V. Stemann.
Simulating Shared Memory in Real Time:
On the Computational Power of Reconfigurable Architectures.
Information and Computation, 137(2): 103  120, September 1997.
A preliminary version of this paper appeared in two conference papers:
 Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Meshes
in Proceedings of the 2nd IEEE Workshop on Reconfigurable Architectures (RAW'95),
April 25, 1995, Santa Barbara, CA, 1995;
[DRAFT ©]
 Improved Optimal Shared Memory Simulations, and the Power of Reconfiguration
in Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems (ISTCS'95),
pages 11  19, TelAviv, Israel, January 4  6, 1995, IEEE Computer Society Press, Los Alamitos, CA, 1995
[DRAFT ©]

A. Czumaj,
L. Gąsieniec,
M. Piotrow, and
W. Rytter.
Sequential and Parallel Approximation of Shortest Superstrings
.
Journal of Algorithms, 23(1): 74  100, July 1997.
A preliminary version appeared in Proceedings of the 4th Scandinavian
Workshop on Algorithm Theory (SWAT'94), pages 95  106, Aarhus, Denmark,
July 6  8, 1994, volume 824 of Lecture Notes in Computer Science edited by
E. M. Schmidt and S. Skyum, SpringerVerlag, Berlin, 1994.
[DRAFT ©]

D. Breslauer,
A. Czumaj,
D. P. Dubhashi, and
F. Meyer auf der Heide.
Transforming Comparison Model Lower Bounds to the ParallelRandomAccessMachine
.
Information Processing Letters, 62(2): 103  110, May 21, 1997.
A preliminary version appeared in
Proceedings of the 5th Italian Conference on Theoretical Computer Science,
pages 482  491, Villa Rufolo, Ravello, Italy, September 9  11, 1995,
World Science Publishing, River Edge, NJ, 1996.
[DRAFT ©]

A. Czumaj and
W.B. Strothmann.
Bounded Degree Spanning Trees.
Proceedings of the 5th Annual European Symposium on Algorithms (ESA'97),
pages 104  117, Graz, Austria, September 15  17, 1997,
volume 1284 of Lecture Notes in Computer Science edited by
R. Burkard and G. Woeginger, SpringerVerlag, Berlin.
[DRAFT ©]

A. Czumaj,
P. Ferragina,
L. Gąsieniec,
S. Muthukrishnan, and
J. L. Träff.
The Architecture of a Software Library for String Processing.
Proceedings of the 1st Workshop on Algorithm Engineering,
Venice, Italy, September 11  13, 1997.
[DRAFT ©]

B. S. Chlebus,
A. Czumaj, and
J. Sibeyn.
Routing on the PADAM: Degrees of Optimality.
Proceedings of the EuroPar'97 Parallel Processing,
pages 272  279, Passau  Germany, August 26  29, 1997,
volume 1300 of Lecture Notes in Computer Science edited by
C. Lengauer, M. Griebl, and S. Gorlatch, SpringerVerlag, Berlin.
[DRAFT ©]

A. Czumaj,
K. Diks, and
T. Przytycka.
Parallel Maximum Independent Set in Convex Bipartite Graphs
.
Information Processing Letters, 59(6): 289  294, September 23, 1996.
[DRAFT ©]

A. Czumaj.
Very Fast Approximation of the Matrix Chain Product Problem
.
Journal of Algorithms, 21(1): 71  79, July 1996.
A preliminary version (entitled An Optimal Parallel Algorithm for Computing a NearOptimal Order of Matrix Multiplications)
appeared in Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory (SWAT'92),
pages 62  72, Helsinki, Finland, July 8  10, 1992, volume 621 of Lecture Notes in Computer Science,
edited by O. Nurmi and E. Ukkonen, SpringerVerlag, Berlin.
[DRAFT ©]

A. Czumaj and
A. Gibbons.
Guthrie's Problem: New Equivalences and Rapid Reductions
.
Theoretical Computer Science, 154(1): 3  22, January 1996.
A preliminary version (entitled Problems on Pairs of Trees and the Four Colour Problem of Planar Graphs)
appeared in Proceedings of the 20th Annual International Colloquium on Automata, Languages and Programming (ICALP'93),
pages 88  101, Lund, Sweden, July 5  9, 1993, volume 700 of Lecture Notes in Computer Science,
edited by A. Lingas, R. Karlsson and S. Carlsson, SpringerVerlag, Berlin.

A. Czumaj,
Z. Galil,
L. Gąsieniec,
K. Park, and
W. Plandowski.
WorkTimeOptimal Parallel Algorithms for String Problems
.
Proceedings of the 27th ACM Symposium on Theory of Computing (STOC),
pages 713  722, Las Vegas, Nevada, May 29  June 1, 1995.
ACM Press, New York, NY.

M. Crochemore,
A. Czumaj,
L. Gąsieniec,
S. Jarominek,
T. Lecroq,
W. Plandowski, and
W. Rytter.
Speeding Up Two StringMatching Algorithms.
Algorithmica, 12(4/5): 247  267, October 1994.
A preliminary version of this paper appeared in
Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS'92),
pages 589  600, Cachan, France, February 13  15, 1992, volume 577 of Lecture Notes in Computer Science 577,
edited by A. Finkel and M. Jantzen, SpringerVerlag, Berlin.

A. Czumaj.
Parallel Algorithm for the Matrix Chain Product and the Optimal Triangulation Problems.
Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science (STACS),
pages 294  305, Würzburg, Germany, February 25  27, 1993,
volume 665 of Lecture Notes in Computer Science 665,
edited by P. Enjalbert, A. Finkel, and K. W. Wagner, SpringerVerlag, Berlin.
[DRAFT ©]
 M. Crochemore,
A. Czumaj,
L. Gąsieniec,
S. Jarominek,
T. Lecroq,
W. Plandowski, and
W. Rytter.
Deux Methodes pour Accelerer l'Algorithme de BoyerMoore.
In Actes des Deuxiemes Journees francobelges
``Theorie des Automates et Applications,''
Universite de Rouen, 3  5 Septembre 1991, p. 45  63.
Edite par Daniel Krob, Publications de l'Universite de Rouen No 176.
 Polish translation (together with
P. Chrzastowski,
L. Gąsieniec, and
M. Raczunas)
of the book »Concrete Mathematics«
by Ronald L. Graham,
Donald E. Knuth, and
Oren Patashnik
(Reading, Massachusetts: AddisonWesley, 1994), xiii+657pp. ISBN 0201558025.
Polish version entitled »Matematyka Konkretna«
was published in 1996 by Polskie Wydawnictwa Naukowe PWN,
Warszawa, Poland. ISBN 830112146.
Polish 2nd edition was published in 1998.
Polish 4th edition was published in 2004.
The documents distributed by this server have been provided
by the contributing authors as a means to ensure timely
dissemination of scholarly and technical work on a
noncommercial basis. Copyright and all rights therein are
maintained by the authors or by other copyright holders,
notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked
by each author's copyright. These works may not be reposted
without the explicit permission of the copyright holder.