Publications
Articles in
Journals
Conferences
Theses
Others
Filter by Author
2022
Fast Consensus via the Unconstrained Undecided State Dynamics
Proc. of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022
2021
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Transactions on Algorithms 17(4): 29:1-29:51, 2021
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
SIAM Journal on Computing 50(3): STOC16-98-STOC16-137, 2021
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
SIAM Journal on Computing 50(3): 815-856, 2021
Randomized Renaming in Shared Memory Systems
Journal of Parallel and Distributed Computing 150: 112-120, 2021
Time-space trade-offs in population protocols for the majority problem
Distributed Computing 34(2): 91-111, 2021
Minor Sparsifiers and the Distributed Laplacian Paradigm
Proc. of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2021
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions
Proc. of the 25th International Conference on Principles of Distributed Systems (OPODIS), 2021
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
Proc. of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021
Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion
Proc. of the 35th International Symposium on Distributed Computing (DISC), 2021
2020
Positive Aging Admits Fast Asynchronous Plurality Consensus
Proc. of the 39th ACM Symposium on Principles of Distributed Computing (PODC), 2020
Towards Accurate Simulation of Global Challenges on Data Centers Infrastructures via Coupling of Models and Data Sources
Proc. of the 20th Annual International Conference on Computational Science (ICCS) - Multiscale Modelling and Simulation (MMS), 2020
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Proc. of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020
2019
Local Fast Rerouting with Low Congestion: A Randomized Approach
Proc. of the 27th IEEE International Conference on Network Protocols (ICNP), 2019
Dynamic low-stretch trees via dynamic low-diameter decompositions
Proc. of the 51st Annual ACM Symposium on the Theory of Computing (STOC), 2019
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Proc. of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019
2018
Recent Results in Population Protocols for Exact Majority and Leader Election
Bulletin of the EATCS 126, 2018
Breaking the log n Barrier on Rumor Spreading
Distributed Computing 31(6): 503-513, 2018
A note on hardness of diameter approximation
Information Processing Letters 133: 10-15, 2018
A Faster Distributed Single-Source Shortest Paths Algorithm
Proc. of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2018
A population protocol for exact majority with O(log^{5/3} n) stabilization time and Θ(log n) states
Proc. of the 32nd International Symposium on Distributed Computing (DISC), 2018
2017
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
Transactions on Algorithms 13(4): 51:1-51:24, 2017
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Proc. of the 31st International Symposium on Distributed Computing (DISC'17), 2017.
Brief Announcement: A Note on Hardness of Diameter Approximation
Proc. of the 31st International Symposium on Distributed Computing (DISC'17), 2017.
Ignore or Comply? On Breaking Symmetry in Consensus
Proc. of the 36st ACM Symposium on Principles of Distributed Computing (PODC'17), 2017.
Brief Announcement: Population protocols for leader election and exact majority with O(log^2 n) states and O(log^2 n) convergence time
Proc. of the 36st ACM Symposium on Principles of Distributed Computing (PODC'17), 2017.
Brief Announcement: Rapid Asynchronous Plurality Consensus
Proc. of the 36st ACM Symposium on Principles of Distributed Computing (PODC'17), 2017.
2016
Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
Distributed Computing 29(5): 317-339 (2016)
On the Voting Time of the Deterministic Majority Process
Proc. of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), 2016.
On the Isomorphism of Graphs Having Some Eigenvalues of Moderate Multiplicity
Linear Algebra and Its Applications 488: 377-395 (2016).
Efficient Randomized Algorithms for Information Dissemination, Distributed Voting, and Plurality Consensus
PhD thesis, University of Salzburg, 2016.
2015
Fast Consensus for Voting on General Expander Graphs
Proc. of the 29th International Symposium on Distributed Computing (DISC 2015), 2015.
Brief Announcement: On the Voting Time of the Deterministic Majority Process
Proc. of the 29th International Symposium on Distributed Computing (DISC 2015), 2015.
Communication Complexity of Quasirandom Rumor Spreading
Algorithmica 72(2): 467-492 (2015)
Discrete Load Balancing in Heterogeneous Networks with a Focus on Second-Order Diffusion
Proc. of the 35th IEEE International Conference on Distributed
Computing Systems (ICDCS 2015), 2015.
On the Influence of Graph Density on Randomized Gossiping
Proc. of the 29th IEEE International Parallel &
Distributed Processing Symposium (IPDPS 2015), 2015.
Randomized Renaming in Shared Memory Systems
Proc. of the 29th IEEE International Parallel &
Distributed Processing Symposium (IPDPS 2015), 2015.
Weighted Straight Skeletons in the Plane
Computational Geometry: Theory and Applications, 48(2):120–133, February 2015
A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons
Information Processing Letters, 115(2):243–247, February 2015
2014
Randomised Broadcasting: Memory vs. Randomness
Theoretical Computer Science 520, 27-42, 2014.
C2 Approximation of Planar Curvilinear Profiles by Cubic B-Splines
Computer-Aided Design and Applications, Vol. 11 Nr. 2, 206-219, 2014
The Power of Two Choices in Distributed Voting
Proc. of the 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), 435-446, 2014.
Straight Skeletons of Monotone Polygons
Proc. of the 30th European Workshop on Computational Geometry (EuroCG 2014), Ein-Gedi, Israel, March 2014
2013
Coalescing Random Walks and Voting on Connected Graphs
SIAM Journal on Discrete Mathematics, 27(4), 1748-1758.
Multifrequency lock-in detection with nonsinusoidal references
IEEE Trans. Instrum. Meas., 62, 2013, 785-793.
Fast Message Dissemination in Random Geometric Graphs
Distributed Computing, 26, 2013, 1-24.
Faster Rumor Spreading: Breaking the log n Barrier
Proc. of the 27th International Symposium on Distributed Computing (DISC'13), 209-223, 2013.
Agent Based Simulations of Epidemics on a Large Scale
Proc. of the 3rd International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH'13), 2013.
Weighted Straight Skeletons In the Plane
Proc. of the 25th Canadian Conference on Computational Geometry (CCCG '13), pages 13 – 18, Waterloo, Canada, August 2013
Curvature-Continuous Approximation of Planar Curvilinear Profiles
Proc. of the Computer Aided Design Conference, pages 88–89, Bergamo, Italy, June 17 – 20, 2013
2012
Coalescing Random Walks and Voting on Graphs
Proc. of the 31st ACM Symposium on Principles of Distributed Computing (PODC'12), 2012, 47-56.
The Impact of the Power Law Exponent on the Behavior of a Dynamic Epidemic Type Process
Proc. of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'12), 2012, 131-139.
Reliable online-prediction of characteristic process parameters by FTNIR-spectroscopic analysis.
Proc. of the 14th International Meeting on Chemical Sensors, IMCS 2012, 237-240.
2011
Faster Coupon Collecting via Replication with Applications in Gossiping
Proc. of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11), 2011, 72-83.
Settling the Complexity of Local Max-Cut (Almost) Completely
Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP'11), 2011, 171-182.
Tight Bounds for the Cover Time of Multiple Random Walks
Theoretical Computer Science, 412, 2011, 2623-2641 (special issue for invited ICALP'09 papers).
The triple distribution of codes and ordered codes
Discrete Math., 311, 2011, 2283-2294.
Cubic and higher degree bounds for codes and (t, m, s)-nets.
Des. Codes Cryptogr., 60, 2011, 101-121.
2010
Communication Complexity of Quasirandom Rumor Spreading
Proc. of the the 18th Annual European Symposium on Algorithms (ESA'10), 2010, 134-145.
Discrete Load Balancing is (Almost) as Easy as Continuous Load Balancing
Proc. of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'10), 2010, 346-354.
Efficient Information Exchange in the Random Phone-Call Model
Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP'10), 2010, 127-138.
Speeding Up Random Walks with Neighbourhood Exploration
Proc. of the 21st Annual ACM/SIAM Symposium on Discrete Algorithms (SODA'10), 2010, 1422-1435.
Efficient Broadcast on Random Geometric Graphs
Proc. of the 21st Annual ACM/SIAM Symposium on Discrete Algorithms (SODA'10), 2010, 1412-1421.
Efficient Broadcasting in Random Power Law Networks
Proc. of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG'10), 2010, 279-291.
Randomised Broadcasting: Memory vs. Randomness
Proc. of the 9th Latin American Theoretical Informatics Symposium (LATIN'10), 2010, 306-319.
Toward Proper Random Graph Models for Real World Networks
Proc. of the 9th International Conference on Networks (ICN'10), 2010, 306-315.
New explicit bounds for ordered codes and (t, m, s)-nets
Discrete Math., 310, 2010, 970-975.
Transforming Rectangular and Polar Iris Images to Enable Cancelable Biometrics
Proc. of the International Conference on Image Analysis and Recognition (ICIAR'10), pages 276–386, Povoa de Varzim, Portugal, Springer LNCS, 6112, June 21 – 23, 2010
2009
Tight Bounds for the Cover Time of Multiple Random Walks
Proc. of the 36th International Colloquium on Automata, Languages and Programming (ICALP'09), 2010, 415-426.
Cover Time and Broadcast Time
Proc. of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS'09), 2008, 373-384.
On the Runtime and Robustness of Randomized Broadcasting
Theoretical Computer Science, 410, 2009, 3414-3427.
On Randomized Broadcasting in Star Graphs
Discrete Applied Mathematics, 157, 2009, 126-139.
A simple derivation of the MacWilliams identity for linear ordered codes and orthogonal arrays
Des. Codes Cryptogr., 50, 2009, 229-234.
2008
On Radio Broadcasting in Random Geometric Graphs
Proc. of the 22nd International Symposium on Distributed Computing (DISC'08), 2008, 212-226.
Efficient Randomised Broadcasting in Random Regular Networks with Applications in Peer-to-Peer Systems
Proc. of the 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'08), 2008, 155-164.
The Power of Memory in Randomized Broadcasting
Proc. of the 19th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA'08), 2008, 218-227.
2007
Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs
Proc. of the 24st International Symposium on Theoretical Aspects of Computer Science (STACS'07), 2007, 163-174.
Agent-Based Randomized Broadcasting in Large Networks
Discrete Applied Mathematics, 155, 2007, 150-160 (special issue for invited MFCS'04 papers).
On linear programming bounds for nets.
Proc. Appl. Math. and Mech. 7, 2007, 1022603-1022604.
2006
On the Runtime and Robustness of Randomized Broadcasting
Proc. of the 17th International Symposium on Algorithms and Computation (ISAAC'06), 2006, 349-358.
On Randomized Broadcasting in Power Law Networks
Proc. of the 20th International Symposium on Distributed Computing (DISC'06), 2006, 370-384.
Toward the Eigenvalue Power Law
Proc. of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS'06), 2006, 351-362.
On the Communication Complexity of Randomized Broadcasting in Random-Like Graphs
Proc. of the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'06), 2006, 148-157.
Radio Communication in Random Graphs
Journal of Computer and System Sciences, 72, 2006, 490-506.
Distributing Unit Size Workload Packages in Heterogeneous Networks
Journal of Graph Algorithms and Applications, 10, 2006, 51-68 (special issue for invited ESA'04 papers)
2005
Radio Communication in Random Graphs
Proc. of the 17th ACM Symposium on Parallel Algorithms and Architectures (SPAA'05), 2005, 309-315.
On Randomized Broadcasting in Star Graphs
Proc. of the 31th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05), 2005, 307-318.
A Simple Graph-Theoretic Model for Selfish Restricted Scheduling
Proc. of the 1st Workshop on Internet and Network Economics (WINE'05), 2005, 195-209.
2004
Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Networks
Proc. of the 12th European Symposium on Algorithms (ESA'04), 2004, 640-651.
Agent-Based Information Handling in Large Networks
Proc. of the 7th International Symposium on Mathematical Foundations of Computer Science (MFCS'04), 2004, 586-598.
Load Balancing in Dynamic Networks
Proc. of the 7th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'04), 2004, 193-200.
Optimal Diffusion Schemes and Load Balancing on Product Graphs
Parallel Processing Letters, 14, 2004, 61-73.
New spectral lower bounds on the bisection width of graphs
Theoretical Computer Science, 320, 2004, 155-174.
2003
Sparse Topologies with Small Spectrum Size
Theoretical Computer Science, 307, 2003, 549-565.
Diffusion Load Balancing in Static and Dynamic Networks
Proc. International Workshop on Ambient Intelligence Computing, 2003, 49-62.
Load Balancing of Unit Size Tokens and Expansion Properties of Graphs
Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA'03), 2003, 266-273.
Edge-Isoperimetric Problems for Cartesian Powers of Regular Graphs
Theoretical Computer Science, 307, 2003, 473-492.
On Spectral Bounds for the k-Partitioning of Graphs
Theory of Computing Systems, 36, 2003, 461-478, (special issue for invited SPAA'01 papers).
2002
Diffusion Schemes for Load Balancing on Heterogeneous Networks
Theory of Computing Systems, 35, 2002, 305-320, (special issue for invited SPAA'00 papers).
Spectral Methods for Efficient Load Balancing Strategies
German Informatics Society - Outstanding Dissertation.
Toward Optimal Diffusion Matrices
Proc. of the 16th International Parallel and Distributed Processing Symposium (IPDPS'02), 2002.
2001
Edge Isoperimetric Problems for Cartesian Powers of Regular Graphs
Proc. of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'01), 2001.
New Spectral Bounds on k-Partitioning of Graphs
Proc. of the Thirtheenth ACM Symposium on Parallel Algorithms and Architectures (SPAA'01), 2001, 255-262.
Scalable Sparse Topologies with Small Spectrum
Proc. of the 18th Annual Symposium on Theoretical Aspects of Computer Science,Proc. (STACS'01), 2001, 218-229.
2000
The Spider Poset is Macaulay
Journal of Combinatorial Theory A, 90, 2000, 1-26.
An Edge Isoperimetric Problem for Powers of the Petersen Graph
Annals of Combinatorics, 4, 2000, 153-169.
New spectral lower bounds on the bisection width of graphs
Proc. of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'00), Ulrik Brandes, Dorothea Wagner (eds.), Springer, LNCS 1928, Jun 2000, 23-34.
Diffusive Load Balancing Schemes on Heterogeneous Networks
Proc. of the 12th ACM Symposium on Parallel Algorithms and Architectures (SPAA'00), 2000, 30-38.
1999
Optimal Cuts for Powers of the Petersen Graph
Proc. of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), LNCS 1665, 1999, 228-239.
On k-partitioning of Hamming Graphs
Discrete Applied Mathematics, 95, 1999, 127-140.
On Bounds for the k-Partitioning of Graphs
Proc. of the Conference on Computing and Combinatorics (COCOON'99), 1999, 154-163.
Optimal and Alternating-Direction Loadbalancing Schemes
Euro-Par'99, Parallel Processing, 1999, 280-290.