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] |