Artur Czumaj

Publications (selection)

April 27, 2017




  1. NEW! A. Czumaj and P. Davies. Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks [pdf]. In Proceedings of the 36th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2017), pages 3 - 12, Washington, DC, USA, July 25 - 27, 2017. Best student paper. A preliminary version appeared at arXiv:1703.01859.

  2. NEW! 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 arXiv:1512.03315.

  3. A. Czumaj and P. Davies. Brief Announcement: Optimal Leader Election in Multi-hop Radio Networks. In Proceedings of the 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2016), pages 47 - 49, Chicago, Illinois, USA, July 25 - 28, 2016. A preliminary version appeared at arXiv:1505.06149.

  4. A. Czumaj and P. Davies. Faster Deterministic Communication in Radio Networks. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), article 139, Rome, Italy, July 12 - 15, 2016. A preliminary version appeared at arXiv:1506.00853.

  5. 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.

  6. 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.

  7. A. Czumaj and P. 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 arXiv:1505.06107.

  8. 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.

  9. 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.

  10. 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 arXiv:1504.03294.

  11. A. Czumaj, M. Fasoulakis, and M. Jurdziński. Approximate Well-supported 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 arXiv:1407.3004.

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

  13. 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 arXiv:1007.4230.

  14. 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.

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

  16. P. Berenbrink, A. Czumaj, M. Englert, T. Friedetzky, and L. Nagel. Multiple-choice 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, Springer-Verlag, Berlin, Heidelberg, 2012.

  17. 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 ©]

  18. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA'2012), pages 1681 - 1689, Kyoto, Japan, January 17 - 19, 2012. SIAM, Philadelphia, PA, 2012. [pdf ©]

  19. 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 arXiv:1407.2109.

  20. 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, Springer-Verlag, Berlin, Heidelberg, 2011. [pdf ©].

  21. 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 ©].

  22. A. Czumaj, J. Czyzowicz, L. Gąsieniec, J. Jansson, A. Lingas, P. Zylinski. Approximation Algorithms for Buy-at-Bulk 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, Springer-Verlag, Berlin, Heidelberg, 2009.

  23. 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, Springer-Verlag, Berlin, Heidelberg, 2010.

  24. A. Czumaj and C. Sohler. Sublinear-time Algorithms. Invited contribution in Property Testing. Current Research and Surveys, pages 42 - 66, editd by O. Goldreich, LNCS 6390, Springer-Verlag, 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.

  25. 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, Springer-Verlag, Berlin, Heidelberg, 2010.

  26. A. Adamaszek, A. Czumaj, and A. Lingas. PTAS for k-tour 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, Springer-Verlag, Berlin, Heidelberg, 2009.
    Manuscript, April 2009, available at arXiv:0904.2576.

  27. A. Czumaj and C. Sohler. Testing Expansion in Bounded-Degree Graphs. Combinatorics, Probability and Computing, 19(5-6): 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 ©].

  28. 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 ©]

  29. M. Adamaszek, A. Czumaj, and C. Sohler. Testing Monotone Continuous Distributions on High-dimensional Real Cubes. In Proceedings of the 21st ACM-SIAM 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, Springer-Verlag, Berlin, Heidelberg, 2010.

  30. 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 ©]

  31. A. Czumaj and C. Sohler. Small Space Representations for Metric Min-sum k-Clustering 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. Springer-Verlag, Berlin, 2007. [DRAFT ©].

  32. A. Czumaj and A. Lingas. Finding a Heaviest Vertex-Weighted 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 ACM-SIAM Symposium on Discrete Algorithms (SODA'07), pages 986 - 994, New Orleans, LA, January 7 - 9, 2007. SIAM, Philadelphia, PA, 2007. [DRAFT ©]

  33. A. Czumaj, A. Shapira, and C. Sohler. Testing Hereditary Properties of Nonexpanding Bounded-Degree 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 ACM-SIAM 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 TR07-083 [DRAFT ©].

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

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

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

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

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

  39. A. Czumaj and X. Wang. Communication Problems in Random Line-of-Sight Ad-hoc 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. Springer-Verlag, Berlin, 2007. [DRAFT ©].

  40. 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 ©].

  41. A. Czumaj and A. Lingas. Approximation Schemes for Minimum-cost k-Connectivity 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 ©]

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

  43. A. Czumaj and B. Vöcking. Tight Bounds for Worst-Case 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 ACM-SIAM Symposium on Discrete Algorithms (SODA'02), pages 413 - 420, San Francisco, CA, January 6 - 8, 2002. SIAM, Philadelphia, PA, 2002.

  44. A. Czumaj and C. Sohler. Sublinear-Time Approximation Algorithms for Clustering via Random Sampling. Random Structures and Algorithms, 30(1-2): 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. Springer-Verlag, 2004. [DRAFT ©] .

  45. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA'04), pages 739 - 748, New Orleans, LA, January 11 - 13, 2004. SIAM, Philadelphia, PA, 2004.

  46. 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 ©]

  47. A. Czumaj and C. Sohler. Sublinear-time 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, Springer-Verlag, Berlin, Heidelberg, 2010.

  48. 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 ©]

  49. A. Czumaj, F. Ergün, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, and C. Sohler. Sublinear-time 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 ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pages 813 - 822, Baltimore, MD, January 12 - 14, 2003. SIAM, Philadelphia, PA, 2003. [DRAFT ©]

  50. 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 ©]

  51. 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, Springer-Verlag, Berlin, 2003. [DRAFT ©]

  52. 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, Springer-Verlag, Berlin, 2001.

  53. A. Berger, A. Czumaj, M. Grigni, and H. Zhao. Approximation Schemes for Minimum 2-Connected 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. Springer-Verlag, 2005.

  54. 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., Springer-Verlag, 2005.

  55. A. Czumaj and H. Zhao. Fault-Tolerant 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.

  56. A. Czumaj and A. Ronen. On the Expected Payment of Mechanisms for Task Allocation . In Proceedings of the 23rd Annual ACM SIGACT-SIGOPS 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.

  57. 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.

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

  59. 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.

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

  61. 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, Springer-Verlag, Berlin, 2003. [DRAFT of full version ©]

  62. A. Czumaj, A. Lingas, and H. Zhao. Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem. Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP'02), pages 973-984, 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, Springer-Verlag, Berlin, 2002.

  63. 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 ©]

  64. 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(1-2): 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, Springer-Verlag, Berlin, 1999.

  65. 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, Springer-Verlag, Berlin, 2001. [DRAFT ©]

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

  67. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA'99), pages 271 - 280, Baltimore, Maryland, January 17 - 19, 1999. SIAM, Philadelphia, PA, 1999.

  68. 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.

  69. A. Czumaj and M. Kutylowski. Delayed Path Coupling and Generating Random Permutations . Random Structures and Algorithms, 17(3-4): 238 - 259, November 2000.

    A preliminary version (containing also some other results) appeared in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), pages 271-280, Baltimore, Maryland, January 17-19, 1999. SIAM, Philadelphia, PA, 1999.

  70. A. Czumaj and C. Scheideler. Coloring Nonuniform Hypergraphs: A New Algorithmic Approach to the General Lovász Local Lemma . Random Structures and Algorithms, 17(3-4): 213 - 237, November 2000.

    A preliminary version appeared in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00), pages 30-39, San Francisco, CA, January 9 - 11, 2000. SIAM, Philadelphia, PA, 2000. [DRAFT ©]

  71. 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, Springer-Verlag, Berlin, 1996.

  72. 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 Triple-Logarithmic 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, Springer-Verlag, Berlin, 1995.

  73. 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, Springer-Verlag, 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.

  74. A. Czumaj and A. Lingas. Fast Approximation Schemes for Euclidean Minimum-Cost Multi-Connectivity (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, Springer-Verlag, Berlin, 2000. [DRAFT ©]

  75. 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 ©]

  76. 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, Springer-Verlag, Berlin, 2000. [DRAFT ©]

  77. 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 ©

  78. M. Crochemore, A. Czumaj, L. Gąsieniec, T. Lecroq, W. Plandowski, and W. Rytter. Fast Practical Multi-Pattern Matching . Information Processing Letters, 71(3-4): 107 - 113, August 27, 1999.

  79. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA'99), pages 271 - 280, Baltimore, Maryland, January 17 - 19, 1999. SIAM, Philadelphia, PA.

  80. A. Czumaj and A. Lingas. On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem . Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 281 - 290, Baltimore, Maryland, January 17 - 19, 1999. SIAM, Philadelphia, PA.

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

  82. 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, Springer-Verlag, Berlin, 1996. [DRAFT ©]

  83. A. Czumaj and A. Lingas. A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity. 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, Springer-Verlag, Berlin.

  84. 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, Tel-Aviv, Israel, January 4 - 6, 1995, IEEE Computer Society Press, Los Alamitos, CA, 1995 [DRAFT ©]


  85. 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, Springer-Verlag, Berlin, 1994. [DRAFT ©]

  86. D. Breslauer, A. Czumaj, D. P. Dubhashi, and F. Meyer auf der Heide. Transforming Comparison Model Lower Bounds to the Parallel-Random-Access-Machine . 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 ©]

  87. 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, Springer-Verlag, Berlin. [DRAFT ©]

  88. 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 ©]

  89. B. S. Chlebus, A. Czumaj, and J. Sibeyn. Routing on the PADAM: Degrees of Optimality. Proceedings of the Euro-Par'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, Springer-Verlag, Berlin. [DRAFT ©]

  90. 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 ©]

  91. 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 Near-Optimal 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, Springer-Verlag, Berlin. [DRAFT ©]

  92. 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, Springer-Verlag, Berlin.

  93. A. Czumaj, Z. Galil, L. Gąsieniec, K. Park, and W. Plandowski. Work-Time-Optimal 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.

  94. M. Crochemore, A. Czumaj, L. Gąsieniec, S. Jarominek, T. Lecroq, W. Plandowski, and W. Rytter. Speeding Up Two String-Matching 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, Springer-Verlag, Berlin.

  95. 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, Springer-Verlag, Berlin. [DRAFT ©]

  96. M. Crochemore, A. Czumaj, L. Gąsieniec, S. Jarominek, T. Lecroq, W. Plandowski, and W. Rytter. Deux Methodes pour Accelerer l'Algorithme de Boyer-Moore. In Actes des Deuxiemes Journees franco-belges ``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.

  97. 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: Addison-Wesley, 1994), xiii+657pp. ISBN 0-201-55802-5.
    Polish version entitled »Matematyka Konkretna« was published in 1996 by Polskie Wydawnictwa Naukowe PWN, Warszawa, Poland. ISBN 83-01-1214-6. Polish 2nd edition was published in 1998. Polish 4th edition was published in 2004.


© Copyright Notice:
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.