Artur Czumaj

Orcid: 0000-0002-7743-438X

Affiliations:
  • University of Warwick, UK


According to our database1, Artur Czumaj authored at least 172 papers between 1992 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Component stability in low-space massively parallel computation.
Distributed Comput., March, 2024

Routing schemes for hybrid communication networks.
Theor. Comput. Sci., February, 2024

Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph.
SIAM J. Comput., 2024

Log Diameter Rounds MST Verification and Sensitivity in MPC.
Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, 2024

Streaming Graph Algorithms in the Massively Parallel Computation Model.
Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, 2024

Parallel Derandomization for Coloring.
Proceedings of the IEEE International Parallel and Distributed Processing Symposium, 2024

Fully-Scalable MPC Algorithms for Clustering in High Dimension.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Parallel Derandomization for Coloring (Abstract).
Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing, 2024

2023
Deterministic Massively Parallel Connectivity.
SIAM J. Comput., October, 2023

Haystack hunting hints and locker room communication.
Random Struct. Algorithms, July, 2023

On parallel time in population protocols.
Inf. Process. Lett., 2023

Fast Parallel Degree+1 List Coloring.
CoRR, 2023

On Parallel k-Center Clustering.
Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Modern Parallel Algorithms (Invited Talk).
Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Optimal (Degree+1)-Coloring in Congested Clique.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022
Almost Tight Bounds for Reordering Buffer Management.
SIAM J. Comput., 2022

Letter from the President.
Bull. EATCS, 2022

Routing Schemes for Hybrid Communication Networks in Unit-Disk Graphs.
CoRR, 2022

Streaming Facility Location in High Dimension via New Geometric Hashing.
CoRR, 2022

Streaming Algorithms for Geometric Steiner Forest.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Streaming Facility Location in High Dimension via Geometric Hashing.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.
ACM Trans. Algorithms, 2021

Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.
SIAM J. Comput., 2021

Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks.
J. ACM, 2021

On Truly Parallel Time in Population Protocols.
CoRR, 2021

Component Stability in Low-Space Massively Parallel Computation.
Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Improved Deterministic (Δ+1) Coloring in Low-Space MPC.
Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Near-Shortest Path Routing in Hybrid Communication Networks.
Proceedings of the 25th International Conference on Principles of Distributed Systems, 2021

2020
Round Compression for Parallel Matching Algorithms.
SIAM J. Comput., 2020

Report on ICALP 2020.
Bull. EATCS, 2020

The EATCS Award 2020 - Laudatio for Mihalis Yannakakis.
Bull. EATCS, 2020

Detecting cliques in CONGEST networks.
Distributed Comput., 2020

Combinatorial Communication in the Locker Room.
CoRR, 2020

Sublinear time approximation of the cost of a metric <i>k</i>-nearest neighbor graph.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Simple, Deterministic, Constant-Round Coloring in the Congested Clique.
Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Testable Properties in General Graphs and Random Order Streaming.
Proceedings of the Approximation, 2020

2019
Leader election in multi-hop radio networks.
Theor. Comput. Sci., 2019

An <i>O</i>(log <i>k</i>)-Competitive Algorithm for Generalized Caching.
ACM Trans. Algorithms, 2019

Planar graphs: Random walks and bipartiteness testing.
Random Struct. Algorithms, 2019

Communicating with beeps.
J. Parallel Distributed Comput., 2019

The EATCS Award 2020 - Call for Nominations.
Bull. EATCS, 2019

A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs).
CoRR, 2019

Distributed Methods for Computing Approximate Equilibria.
Algorithmica, 2019

A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs).
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
3rd Highlights of Algorithms (HALG 2018).
SIGACT News, 2018

Approximation Schemes for Capacitated Geometric Network Design.
SIAM J. Discret. Math., 2018

Deterministic Communication in Radio Networks.
SIAM J. Comput., 2018

Report on HALG 2018.
Bull. EATCS, 2018

Randomized Communication Without Network Knowledge.
CoRR, 2018

Brief Announcement: Randomized Blind Radio Networks.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Deterministic Blind Radio Networks.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Sublinear Graph Augmentation for Fast Query Implementation.
Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

Online Facility Location with Deletions.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017
Sublinear Clustering.
Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

HALG: Highlights of Algorithms.
SIGACT News, 2017

Report on HALG 2016/2017.
Bull. EATCS, 2017

Zero-Sum Game Techniques for Approximate Nash Equilibria.
Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Multi-player Approximate Nash Equilibria.
Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

2016
Price of Anarchy for Machines Models.
Encyclopedia of Algorithms, 2016

Minimum <i>k</i>-Connected Geometric Networks.
Encyclopedia of Algorithms, 2016

Euclidean Traveling Salesman Problem.
Encyclopedia of Algorithms, 2016

Relating two property testing models for bounded degree directed graphs.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Faster Deterministic Communication in Radio Networks.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Approximate Plutocratic and Egalitarian Nash Equilibria: (Extended Abstract).
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

2015
Almost Optimal Deterministic Broadcast in Radio Networks.
CoRR, 2015

Optimal leader election in multi-hop radio networks.
CoRR, 2015

Testing Cluster Structure of Graphs.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Random Permutations using Switching Networks.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate Nash Equilibria with Near Optimal Social Welfare.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

2014
Approximate Well-Supported Nash Equilibria in Symmetric Bimatrix Games.
Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

Thorp Shuffling, Butterflies, and Non-Markovian Couplings.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Fast message dissemination in random geometric networks.
Distributed Comput., 2013

(1+ Є)-approximation for facility location in data streams.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
Finding Cycles and Trees in Sublinear Time.
Electron. Colloquium Comput. Complex., 2012

Optimal online buffer scheduling for block devices.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Multiple-Choice Balanced Allocation in (Almost) Parallel.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Approximation Algorithms for Buy-at-Bulk Geometric Network Design.
Int. J. Found. Comput. Sci., 2011

2010
Sublinear Clustering.
Proceedings of the Encyclopedia of Machine Learning, 2010

Selfish Traffic Allocation for Server Farms.
SIAM J. Comput., 2010

Small Space Representations for Metric Min-sum <i>k</i>-Clustering and Their Applications.
Theory Comput. Syst., 2010

Ptas for k-Tour Cover Problem on the Plane for Moderately Large Values of k.
Int. J. Found. Comput. Sci., 2010

Testing Expansion in Bounded-Degree Graphs.
Comb. Probab. Comput., 2010

Testing Monotone Continuous Distributions on High-dimensional Real Cubes.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Sublinear-time Algorithms.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Monotone Continuous Distributions on High-Dimensional Real Cubes.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Local Graph Exploration and Fast Property Testing.
Proceedings of the Algorithms, 2010

2009
Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs.
SIAM J. Comput., 2009

Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time.
SIAM J. Comput., 2009

Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication.
SIAM J. Comput., 2009

PTAS for <i>k</i>-Tour Cover Problem on the Plane for Moderately Large Values of <i>k</i>.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008
Price of Anarchy for Machines Models.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Minimum k-Connected Geometric Networks.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Euclidean Traveling Salesperson Problem.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Testing Euclidean minimum spanning trees in the plane.
ACM Trans. Algorithms, 2008

08341 Executive Summary - Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

08341 Abstracts Collection - Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

2007
Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Faster algorithms for finding lowest common ancestors in directed acyclic graphs.
Theor. Comput. Sci., 2007

Tight bounds for worst-case equilibria.
ACM Trans. Algorithms, 2007

Sublinear-time approximation algorithms for clustering via random sampling.
Random Struct. Algorithms, 2007

Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs.
Electron. Colloquium Comput. Complex., 2007

On testable properties in bounded degree graphs.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Communication Problems in Random Line-of-Sight Ad-Hoc Radio Networks.
Proceedings of the Stochastic Algorithms: Foundations and Applications, 2007

Fast Message Dissemination in Random Geometric Ad-Hoc Radio Networks.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Efficient Kinetic Data Structures for MaxCut.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2006
Computing equilibria for a service provider game with (Im)perfect information.
ACM Trans. Algorithms, 2006

Balanced Allocations: The Heavily Loaded Case.
SIAM J. Comput., 2006

Broadcasting algorithms in radio networks with unknown topology.
J. Algorithms, 2006

Finding a Heaviest Triangle is not Harder than Matrix Multiplication.
Electron. Colloquium Comput. Complex., 2006

Sublinear-Time Algorithms.
Bull. EATCS, 2006

2005
Testing hypergraph colorability.
Theor. Comput. Sci., 2005

Abstract Combinatorial Programs and Efficient Property Testers.
SIAM J. Comput., 2005

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.
SIAM J. Comput., 2005

Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth.
Inf. Process. Lett., 2005

Facility Location in Sublinear Time.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs.
Proceedings of the Algorithms, 2005

05291 Abstracts Collection -- Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

2004
Selfish Routing on the Internet.
Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004

Fault-Tolerant Geometric Spanners.
Discret. Comput. Geom., 2004

Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Computing equilibria for congestion games with (im)perfect information.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

On the expected payment of mechanisms for task allocation: [extended abstract].
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

On the expected payment of mechanisms for task allocation.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Sublinear-Time Approximation for Clustering Via Random Sampling.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
On polynomial-time approximation algorithms for the variable length scheduling problem.
Theor. Comput. Sci., 2003

Sublinear-time approximation of Euclidean minimum spanning tree.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Perfectly Balanced Allocation.
Proceedings of the Approximation, 2003

Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002
Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001
Efficient web searching using temporal factors.
Theor. Comput. Sci., 2001

Randomized allocation processes.
Random Struct. Algorithms, 2001

Soft kinetic data structures.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Testing Hypergraph Coloring.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Property Testing with Geometric Queries.
Proceedings of the Algorithms, 2001

2000
Algorithms for the parallel alternating direction access machine.
Theor. Comput. Sci., 2000

Contention Resolution in Hashing Based Shared Memory Simulations.
SIAM J. Comput., 2000

Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma.
Random Struct. Algorithms, 2000

Delayed path coupling and generating random permutations.
Random Struct. Algorithms, 2000

Recovery Time of Dynamic Allocation Processes.
Theory Comput. Syst., 2000

A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Infinite parallel job allocation (extended abstract).
Proceedings of the Twelfth annual ACM Symposium on Parallel Algorithms and Architectures, 2000

Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Fast Approximation Schemes for Euclidean Multi-connectivity Problems.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Property Testing in Computational Geometry.
Proceedings of the Algorithms, 2000

On the Complexity of Determining the Period of a String.
Proceedings of the Combinatorial Pattern Matching, 11th Annual Symposium, 2000

1999
Fast Practical Multi-Pattern Matching.
Inf. Process. Lett., 1999

On Approximability of the Minimum-Cost <i>k</i>-Connected Spanning Subgraph Problem.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Delayed Path Coupling and Generating Random Permutations via Distributed Stochastic Processes.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
Time and Cost Trade-Offs in Gossiping.
SIAM J. Discret. Math., 1998

Fast Generation of Random Permutations Via Networks Simulation.
Algorithmica, 1998

A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997
Sequential and Parallel Approximation of Shortest Superstrings.
J. Algorithms, 1997

Transforming Comparison Model Lower Bounds to the Parallel-Random-Access-Machine.
Inf. Process. Lett., 1997

Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures.
Inf. Comput., 1997

The Architecture of a Software Library for String Processing.
Proceedings of the Workshop on Algorithm Engineering, 1997

Routing on the PADAM: Degrees of Optimality.
Proceedings of the Euro-Par '97 Parallel Processing, 1997

Bounded Degree Spanning Trees (Extended Abstract).
Proceedings of the Algorithms, 1997

1996
Guthrie's Problem: New Equivalences and Rapid Reductions.
Theor. Comput. Sci., 1996

Very Fast Approximation of the Matrix Chain Product Problem.
J. Algorithms, 1996

Parallel Maximum Independent Set in Convex Bipartite Graphs.
Inf. Process. Lett., 1996

Parallel Alternating-Direction Access Machine.
Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

1995
Parallel Algorithmic Techniques: PRAM algorithms and PRAM simulations.
PhD thesis, 1995

Work-time-optimal parallel algorithms for string problems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Improved Optimal Shared Memory Simulations, and the Power of Reconfiguration.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Shared Memory Simulations with Triple-Logarithmic Delay.
Proceedings of the Algorithms, 1995

1994
Speeding Up Two String-Matching Algorithms.
Algorithmica, 1994

Parallel and Sequential Approximations of Shortest Superstrings.
Proceedings of the Algorithm Theory, 1994

1993
Parallel Algorithm for the Matrix Chain Product and the Optimal Triangulation Problems (Extended Abstract).
Proceedings of the STACS 93, 1993

Problems on Pairs of Trees and the Four Colour Problem of Planar Graphs.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

1992
An Optimal Parallel Algorithm for Computing a Near-Optimal Order of Matrix Multiplications.
Proceedings of the Algorithm Theory, 1992


  Loading...