2014 | |

[57] | Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids , 24th SODA, 2014. Accepted [info] |

2013 | |

[56] | Gossip Protocols for Renaming and Sorting , 27th DISC, Springer, 2013. Accepted [info] |

[55] | An O(sqrt n) Space Bound for Obstruction-Free Leader Election , 27th DISC, Springer, 2013. Accepted [info] |

[54] | An Optimal Implementation of Fetch-and-Increment , 27th DISC, Springer, 2013. Accepted [info] |

[53] | Brief Announcement: Resettable Objects and Efficient Memory Reclamation for Concurrent Algorithms , 32nd PODC, pp. 322--324, 2013. [info] [doi] |

[52] | Randomized Loose Renaming in O(log log n) Time , 32nd PODC, pp. 200--209, 2013. [info] [doi] |

[51] | Decoupled Speed Scaling: Analysis and Evaluation , Performance Evaluation, Elsevier, 2013. (Invited contribution.) [info] [pdf] [doi] |

2012 | |

[50] | RMR-Efficient Randomized Abortable Mutual Exclusion , 26th DISC, pp. 267-281, 2012. [info] [doi] |

[49] | Independence of Tabulation-Based Hash Classes , 10th LATIN, pp. 506-517, 2012. [info] [doi] |

[48] | Strongly Linearizable Implementations: Possibilities and Impossibilities , 31st PODC, pp. 385-394, 2012. [info] [doi] |

[47] | On the Time and Space Complexity of Randomized Test-And-Set , 31st PODC, pp. 19-28, 2012. Best paper award. Addendum
[info] [doi] |

[46] | Tight RMR Lower Bounds for Randomized Mutual Exclusion , 44th STOC, pp. 983-1002, 2012. [info] [doi] |

[45] | Low Randomness Rumor Spreading via Hashing , 29th STACS, pp. 314-325, 2012. [info] [doi] |

[44] | Decoupled Speed Scaling: Analysis and Evaluation , 9th QEST, pp. 2--12, IEEE Computer Society, 2012. Best paper award
[info] [doi] |

[43] | Efficient Fetch-and-Increment , 26th DISC, pp. 16-30, 2012. [info] [doi] |

[42] | RMR-efficient implementations of comparison primitives using read and write operations , Distributed Computing 25(2), pp. 109-162, 2012. [info] [doi] |

2011 | |

[41] | The Space Complexity of Long-Lived and One-Shot Timestamp Implementations , 30th PODC, pp. 139-148, 2011. Best paper award
[info] [pdf] [doi] |

[40] | On the Randomness Requirements of Rumor Spreading , 22nd SODA, pp. 449-461, 2011. [info] [pdf] |

[39] | Linearizable Implementations Do Not Suffice for Randomized Distributed Computation , 43rd STOC, pp. 373-382, 2011. [info] [pdf] [doi] |

[38] | Randomized Mutual Exclusion with Sub-Logarithmic RMR-Complexity , Distributed Computing 24(1), pp. 3-19, 2011. (Invited contribution.) [info] [doi] |

[37] | Precision, Local Search and Unimodal Functions , Algorithmica 59(3), pp. 301-322, 2011. (Invited contribution.) [info] [doi] |

[36] | Fully-adaptive algorithms for long-lived renaming , Distributed Computing 24(2), pp. 119-134, 2011. [info] [doi] |

2010 | |

[35] | Adaptive Randomized Mutual Exclusion in Sub-Logarithmic Expected Time , 29th PODC, pp. 141-150, 2010. [info] [pdf] [doi] |

[34] | An O(1) RMRs Leader Election Algorithm , SIAM Journal on Computing 39(7), pp. 2726-2760, 2010. [info] [doi] |

[33] | Tight Bounds for Blind Search on the Integers and the Reals , Combinatorics, Probability and Computing 19(5-6), pp. 711-728, 2010. [info] [doi] |

[32] | Separating Deterministic from Randomized Multiparty Communication Complexity , Theory of Computing 6(1), pp. 201-225, Theory of Computing, 2010. [info] [doi] |

2009 | |

[31] | Randomized Mutual Exclusion in O(log N/loglog N) RMRs , 28th PODC, pp. 26-35, 2009. [info] [pdf] [doi] |

[30] | Tight Lower Bounds for Greedy Routing in Uniform Small World Rings , 41st STOC, pp. 591-600, 2009. [info] [pdf] [doi] |

[29] | Representation of graphs by OBDDs , Discrete Applied Mathematics 157(2), pp. 247-261, 2009. [info] [doi] |

2008 | |

[28] | Precision, Local Search and Unimodal Functions , GECCO, pp. 771-778, 2008. Best paper award, formal theory track
[info] [pdf] [doi] |

[27] | Tight Bounds for Blind Search on the Integers , 25th STACS, pp. 241-252, 2008. [info] [doi] |

[26] | Tight RMR Lower Bounds for Mutual Exclusion and Other Problems , 40th STOC, pp. 217-226, 2008. [info] [pdf] [doi] |

2007 | |

[25] | Constant-RMR Implementations of CAS and Other Synchronization Primitives Using Read and Write Operations , 26th PODC, pp. 3-12, 2007. [info] [pdf] [doi] |

[24] | Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity , 34th ICALP, pp. 134-145, 2007. [info] [doi] |

[23] | New Results on the Complexity of the Middle Bit of Multiplication , Computational Complexity 16(3), pp. 298-323, 2007. [info] [doi] |

2006 | |

[22] | Maintaining External Memory Efficient Hash Tables , 10th RANDOM, pp. 508-519, 2006. [info] [doi] |

[21] | Asymmetric Balanced Allocation with Simple Hash Functions , 17th SODA, pp. 424-434, 2006. [info] [pdf] [doi] |

[20] | An O(1) RMRs Leader Election Algorithm , 25th PODC, pp. 238-274, 2006. [info] [pdf] [doi] |

[19] | Fully Adaptive Algorithms for Long-Lived Renaming , 20th DISC, pp. 413-427, 2006. [info] [doi] |

[18] | A Construction Method for Optimally Universal Hash Families and its Consequences for the Existence of RBIBDs , Theoretical Computer Science (special issue on COCOON 2004) 363(1), pp. 76-84, 2006. (Invited contribution.)
[info] [doi] |

[17] | Symbolic Topological Sorting with OBDDs , Journal of Discrete Algorithms 4(1), pp. 51-71, 2006. [info] [doi] |

[16] | Parity Graph-Driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication , Theoretical Computer Science 362(1-3), pp. 86-99, 2006. [info] [doi] |

2005 | |

[15] | New Results on the Complexity of the Middle Bit of Multiplication , 20th CCC, pp. 100-110, 2005. [info] [doi] |

[14] | Representation of Graphs by OBDDs , 16th ISAAC, pp. 1132-1142, 2005. [info] [doi] |

[13] | Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing , Journal of Computer and System Sciences 71(4), pp. 520-534, 2005. [info] [doi] |

[12] | A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and its Applications , Theory of Computing Systems 38(6), pp. 671-685, 2005. [info] [doi] |

2004 | |

[11] | A Construction Method for Optimally Universal Hash Families and its Consequences for the Existence of RBIBDs , 10th COCOON, pp. 23-32, 2004. [info] [doi] |

2003 | |

[10] | Symbolic Topological Sorting with OBDDs , 28th MFCS, pp. 671-680, 2003. [info] [doi] |

[9] | Time-Space Tradeoff Lower Bounds for Integer Multiplication and Graphs of Arithmetic Functions , 35th STOC, pp. 186-195, 2003. [info] [pdf] [doi] |

[8] | Almost Random Graphs with Simple Hash Functions , 35th STOC, pp. 629-638, 2003. [info] [pdf] [doi] |

2002 | |

[7] | On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism , 17th CCC, pp. 80-89, 2002. [info] [doi] |

[6] | A Lower Bound Technique for Restricted Branching Programs and Applications , 19th STACS, pp. 431-442, 2002. [info] [doi] |

[5] | Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication , 2nd IFIPTCS, pp. 83-94, 2002. [info] |

[4] | A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and its Applications , 27th MFCS, pp. 131-142, 2002. [info] [doi] |

2001 | |

[3] | New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing , 18th STACS, pp. 563-574, 2001. (journal version) [info] [doi] |

[2] | A Read-Once Branching Program Lower Bound of Ω(2^(n/4)) for Integer Multiplication Using Universal Hashing , 33rd STOC, pp. 419-424, 2001. [info] [pdf] [doi] |

1999 | |

[1] | Efficient Strongly Universal and Optimally Universal Hashing , 24th MFCS, pp. 262-272, 1999. [draft] [info] [doi] |