Edit Profile (opens in new tab) King, Valerie Co-Author Distance Author ID: king.valerie Published as: King, Valerie; King, V. External Links: MGP · Wikidata · dblp Documents Indexed: 55 Publications since 1990 2 Contributions as Editor Co-Authors: 50 Co-Authors with 53 Joint Publications 1,854 Co-Co-Authors all top 5 Co-Authors 4 single-authored 17 Saia, Jared 8 Kapron, Bruce M. 7 Rauch Henzinger, Monika 5 Rahmati, Zahed 5 Whitesides, Sue H. 5 Young, Maxwell 3 Impagliazzo, Russell 3 Sanwalani, Vishal 2 Abam, Mohammad Ali 2 Dani, Varsha 2 Fich, Faith Ellen 2 Holtby, Dan 2 Kempe, David 2 Kenyon, Claire M. 2 Kutyłowski, Mirosław 2 Mashreghi, Ali 2 Movahedi, Mahnush 2 Phillips, Cynthia A. 2 Ramachandran, Vijaya 2 Sagert, Garry 2 Tarjan, Robert Endre 2 Thorup, Mikkel 2 Warnow, Tandy J. 1 Agarwal, Udit 1 Alistarh, Dan 1 Aspnes, James 1 Goddard, Wayne Dean 1 Hajiaghaei Shanjani, Sima 1 Hatami, Hamed 1 Jaiswal, Ragesh 1 Kabanets, Valentine 1 Kupferman, Orna 1 Kutten, Shay 1 Le, Hung Viet 1 Lewis, Scott J. 1 McKenzie, Pierre 1 Mountjoy, Ben 1 Pettie, Seth 1 Pontecorvi, Matteo 1 Poon, Chung Keung 1 Saia Jared 1 Schulman, Leonard J. 1 Sinha, Santanu 1 Tessaro, Stefano 1 Vardi, Moshe Ya’akov 1 Vee Erik 1 Zamani, Mahdi 1 Zarei, Alireza 1 Zhang, Li 1 Zhou, Yunhong all top 5 Serials 5 Distributed Computing 4 Algorithmica 3 Journal of the ACM 2 Journal of Computer and System Sciences 2 SIAM Journal on Computing 2 Combinatorica 2 Computational Geometry 1 Information Processing Letters 1 Theoretical Computer Science 1 Journal of Algorithms 1 Random Structures & Algorithms 1 ACM Transactions on Algorithms all top 5 Fields 55 Computer science (68-XX) 16 Combinatorics (05-XX) 7 Information and communication theory, circuits (94-XX) 4 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Operations research, mathematical programming (90-XX) 2 General and overarching topics; collections (00-XX) 2 Numerical analysis (65-XX) 2 Biology and other natural sciences (92-XX) 1 Probability theory and stochastic processes (60-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 48 Publications have been cited 364 times in 267 Documents Cited by ▼ Year ▼ A faster deterministic maximum flow algorithm. Zbl 1321.05269 King, V.; Rao, S.; Tarjan, R. 31 1994 Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Zbl 1065.68665 Henzinger, Monika R.; King, Valerie 29 1999 Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Zbl 0936.68026 Henzinger, M. R.; King, V.; Warnow, T. 24 1999 Dynamic graph connectivity in polylogarithmic worst case time. Zbl 1423.68345 Kapron, Bruce M.; King, Valerie; Mountjoy, Ben 24 2013 Scalable leader election. Zbl 1192.91082 King, Valerie; Saia, Jared; Sanwalani, Vishal; Vee Erik 24 2006 Fully dynamic biconnectivity and transitive closure. Zbl 0938.68919 Rauch Henzinger, Monika; King, Valerie 21 1995 On the complexity of distance-based evolutionary tree reconstruction. Zbl 1094.68614 King, Valerie; Zhang, Li; Zhou, Yunhong 18 2003 Randomized dynamic graph algorithms with polylogarithmic time per operation. Zbl 0978.68556 Rauch Henzinger, Monika; King, Valerie 17 1995 Maintaining minimum spanning forests in dynamic graphs. Zbl 0996.68129 Henzinger, Monika R.; King, Valerie 11 2001 A simpler minimum spanning tree verification algorithm. Zbl 0868.68061 King, V. 10 1997 Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary. Zbl 1315.68272 King, Valerie; Saia, Jared 10 2010 From almost everywhere to everywhere: Byzantine agreement with \(\tilde{O}(n^{3/2})\) bits. Zbl 1261.68167 King, Valerie; Saia, Jared 9 2009 Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication. Zbl 1333.68213 King, Valerie; Kutten, Shay; Thorup, Mikkel 9 2015 Maintaining minimum spanning trees in dynamic graphs. Zbl 1401.68249 Henzinger, Monika R.; King, Valerie 9 1997 On the complexity of parity word automata. Zbl 0978.68077 King, Valerie; Kupferman, Orna; Vardi, Moshe Y. 8 2001 A fully dynamic algorithm for maintaining the transitive closure. Zbl 1020.68106 King, Valerie; Sagert, Garry 8 2002 Conflict on a communication channel. Zbl 1321.68027 King, Valerie; Saia, Jared; Young, Maxwell 8 2011 Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary. Zbl 1281.68047 King, Valerie; Saia, Jared 8 2011 A faster deterministic maximum flow algorithm. Zbl 0829.68094 King, V.; Rao, S.; Tarjan, R. 7 1992 Optimal randomized algorithms for local sorting and set-maxima. Zbl 0770.68047 Goddard, Wayne; Kenyon, Claire; King, Valerie; Schulman, Leonard J. 7 1993 Fast asynchronous byzantine agreement and leader election with full information. Zbl 1192.68083 Kapron, Bruce; Kempe, David; King, Valerie; Saia Jared; Sanwalani, Vishal 7 2008 A lower bound for the recognition of digraph properties. Zbl 0733.05041 King, V. 6 1990 On Boolean decision trees with faulty nodes. Zbl 0811.68101 Kenyon, Claire; King, Valerie 6 1994 A simple, faster method for kinetic proximity problems. Zbl 1314.65032 Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza 6 2015 Choosing a random peer. Zbl 1321.68051 King, Valerie; Saia, Jared 6 2004 A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds. Zbl 1428.68363 Agarwal, Udit; Ramachandran, Vijaya; King, Valerie; Pontecorvi, Matteo 6 2018 Fast asynchronous Byzantine agreement and leader election with full information. Zbl 1300.68012 Kapron, Bruce M.; Kempe, David; King, Valerie; Saia, Jared; Sanwalani, Vishal 5 2010 Byzantine agreement in expected polynomial time. Zbl 1426.68024 King, Valerie; Saia, Jared 5 2016 Brief announcement: Breaking the \(O(nm)\) bit barrier, secure multiparty computation with a static adversary. Zbl 1301.68251 Dani, Varsha; King, Valerie; Movahedi, Mahnush; Saia, Jared 5 2012 Limits on the power of parallel random access machines with weak forms of write conflict resolution. Zbl 0842.68033 Fich, Faith E.; Impagliazzo, Russell; Kapron, Bruce; King, Valerie; Kutylowski, Miroslaw 4 1993 Secure multi-party computation in large networks. Zbl 1409.68041 Dani, Varsha; King, Valerie; Movahedi, Mahnush; Saia, Jared; Zamani, Mahdi 4 2017 Byzantine agreement in polynomial expected time (extended abstract). Zbl 1293.68056 King, Valerie; Saia, Jared 3 2013 An optimal EREW PRAM algorithm for minimum spanning tree verification. Zbl 1337.68285 King, Valerie; Poon, Chung Keung; Ramachandran, Vijaya; Sinha, Santanu 3 1997 A space saving trick for directed dynamic transitive closure and shortest path algorithms. Zbl 0996.68526 King, Valerie; Thorup, Mikkel 3 2001 Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Zbl 0848.68077 Rauch Henzinger, Monika; King, Valerie; Warnow, Tandy 2 1996 Sleeping on the job: energy-efficient and robust broadcast for radio networks. Zbl 1225.68050 King, Valerie; Phillips, Cynthia; Saia, Jared; Young, Maxwell 2 2011 Kinetic data structures for all nearest neighbors and closest pair in the plane. Zbl 1305.68070 Rahmati, Zahed; King, Valerie; Whitesides, Sue 2 2013 Sleeping on the job, energy-efficient and robust broadcast for radio networks. Zbl 1301.68036 King, Valerie; Phillips, Cynthia; Saia, Jared; Young, Maxwell 2 2008 A resource-competitive jamming defense. Zbl 1482.68048 King, Valerie; Pettie, Seth; Saia, Jared; Young, Maxwell 2 2018 An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties. Zbl 0743.68077 King, Valerie 1 1991 Kinetic reverse \(k\)-nearest neighbor problem. Zbl 1401.68352 Rahmati, Zahed; King, Valerie; Whitesides, Sue 1 2015 Lower bound for scalable Byzantine agreement. Zbl 1267.68068 Holtby, Dan; Kapron, Bruce M.; King, Valerie 1 2008 A fully dynamic algorithm for maintaining the transitive closure. Zbl 1345.05102 King, Valerie; Sagert, Garry 1 1999 A simpler minimum spanning tree verification algorithm. Zbl 1502.68236 King, Valerie 1 1995 Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. Zbl 1497.68567 Mashreghi, Ali; King, Valerie 1 2018 Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. Zbl 1522.68733 Mashreghi, Ali; King, Valerie 1 2021 Kinetic and stationary point-set embeddability for plane graphs. Zbl 1377.68186 Rahmati, Zahed; Whitesides, Sue H.; King, Valerie 1 2013 Kinetic \(k\)-semi-Yao graph and its applications. Zbl 1506.68018 Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue 1 2019 Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. Zbl 1522.68733 Mashreghi, Ali; King, Valerie 1 2021 Kinetic \(k\)-semi-Yao graph and its applications. Zbl 1506.68018 Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue 1 2019 A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds. Zbl 1428.68363 Agarwal, Udit; Ramachandran, Vijaya; King, Valerie; Pontecorvi, Matteo 6 2018 A resource-competitive jamming defense. Zbl 1482.68048 King, Valerie; Pettie, Seth; Saia, Jared; Young, Maxwell 2 2018 Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. Zbl 1497.68567 Mashreghi, Ali; King, Valerie 1 2018 Secure multi-party computation in large networks. Zbl 1409.68041 Dani, Varsha; King, Valerie; Movahedi, Mahnush; Saia, Jared; Zamani, Mahdi 4 2017 Byzantine agreement in expected polynomial time. Zbl 1426.68024 King, Valerie; Saia, Jared 5 2016 Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication. Zbl 1333.68213 King, Valerie; Kutten, Shay; Thorup, Mikkel 9 2015 A simple, faster method for kinetic proximity problems. Zbl 1314.65032 Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza 6 2015 Kinetic reverse \(k\)-nearest neighbor problem. Zbl 1401.68352 Rahmati, Zahed; King, Valerie; Whitesides, Sue 1 2015 Dynamic graph connectivity in polylogarithmic worst case time. Zbl 1423.68345 Kapron, Bruce M.; King, Valerie; Mountjoy, Ben 24 2013 Byzantine agreement in polynomial expected time (extended abstract). Zbl 1293.68056 King, Valerie; Saia, Jared 3 2013 Kinetic data structures for all nearest neighbors and closest pair in the plane. Zbl 1305.68070 Rahmati, Zahed; King, Valerie; Whitesides, Sue 2 2013 Kinetic and stationary point-set embeddability for plane graphs. Zbl 1377.68186 Rahmati, Zahed; Whitesides, Sue H.; King, Valerie 1 2013 Brief announcement: Breaking the \(O(nm)\) bit barrier, secure multiparty computation with a static adversary. Zbl 1301.68251 Dani, Varsha; King, Valerie; Movahedi, Mahnush; Saia, Jared 5 2012 Conflict on a communication channel. Zbl 1321.68027 King, Valerie; Saia, Jared; Young, Maxwell 8 2011 Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary. Zbl 1281.68047 King, Valerie; Saia, Jared 8 2011 Sleeping on the job: energy-efficient and robust broadcast for radio networks. Zbl 1225.68050 King, Valerie; Phillips, Cynthia; Saia, Jared; Young, Maxwell 2 2011 Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary. Zbl 1315.68272 King, Valerie; Saia, Jared 10 2010 Fast asynchronous Byzantine agreement and leader election with full information. Zbl 1300.68012 Kapron, Bruce M.; Kempe, David; King, Valerie; Saia, Jared; Sanwalani, Vishal 5 2010 From almost everywhere to everywhere: Byzantine agreement with \(\tilde{O}(n^{3/2})\) bits. Zbl 1261.68167 King, Valerie; Saia, Jared 9 2009 Fast asynchronous byzantine agreement and leader election with full information. Zbl 1192.68083 Kapron, Bruce; Kempe, David; King, Valerie; Saia Jared; Sanwalani, Vishal 7 2008 Sleeping on the job, energy-efficient and robust broadcast for radio networks. Zbl 1301.68036 King, Valerie; Phillips, Cynthia; Saia, Jared; Young, Maxwell 2 2008 Lower bound for scalable Byzantine agreement. Zbl 1267.68068 Holtby, Dan; Kapron, Bruce M.; King, Valerie 1 2008 Scalable leader election. Zbl 1192.91082 King, Valerie; Saia, Jared; Sanwalani, Vishal; Vee Erik 24 2006 Choosing a random peer. Zbl 1321.68051 King, Valerie; Saia, Jared 6 2004 On the complexity of distance-based evolutionary tree reconstruction. Zbl 1094.68614 King, Valerie; Zhang, Li; Zhou, Yunhong 18 2003 A fully dynamic algorithm for maintaining the transitive closure. Zbl 1020.68106 King, Valerie; Sagert, Garry 8 2002 Maintaining minimum spanning forests in dynamic graphs. Zbl 0996.68129 Henzinger, Monika R.; King, Valerie 11 2001 On the complexity of parity word automata. Zbl 0978.68077 King, Valerie; Kupferman, Orna; Vardi, Moshe Y. 8 2001 A space saving trick for directed dynamic transitive closure and shortest path algorithms. Zbl 0996.68526 King, Valerie; Thorup, Mikkel 3 2001 Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Zbl 1065.68665 Henzinger, Monika R.; King, Valerie 29 1999 Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Zbl 0936.68026 Henzinger, M. R.; King, V.; Warnow, T. 24 1999 A fully dynamic algorithm for maintaining the transitive closure. Zbl 1345.05102 King, Valerie; Sagert, Garry 1 1999 A simpler minimum spanning tree verification algorithm. Zbl 0868.68061 King, V. 10 1997 Maintaining minimum spanning trees in dynamic graphs. Zbl 1401.68249 Henzinger, Monika R.; King, Valerie 9 1997 An optimal EREW PRAM algorithm for minimum spanning tree verification. Zbl 1337.68285 King, Valerie; Poon, Chung Keung; Ramachandran, Vijaya; Sinha, Santanu 3 1997 Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Zbl 0848.68077 Rauch Henzinger, Monika; King, Valerie; Warnow, Tandy 2 1996 Fully dynamic biconnectivity and transitive closure. Zbl 0938.68919 Rauch Henzinger, Monika; King, Valerie 21 1995 Randomized dynamic graph algorithms with polylogarithmic time per operation. Zbl 0978.68556 Rauch Henzinger, Monika; King, Valerie 17 1995 A simpler minimum spanning tree verification algorithm. Zbl 1502.68236 King, Valerie 1 1995 A faster deterministic maximum flow algorithm. Zbl 1321.05269 King, V.; Rao, S.; Tarjan, R. 31 1994 On Boolean decision trees with faulty nodes. Zbl 0811.68101 Kenyon, Claire; King, Valerie 6 1994 Optimal randomized algorithms for local sorting and set-maxima. Zbl 0770.68047 Goddard, Wayne; Kenyon, Claire; King, Valerie; Schulman, Leonard J. 7 1993 Limits on the power of parallel random access machines with weak forms of write conflict resolution. Zbl 0842.68033 Fich, Faith E.; Impagliazzo, Russell; Kapron, Bruce; King, Valerie; Kutylowski, Miroslaw 4 1993 A faster deterministic maximum flow algorithm. Zbl 0829.68094 King, V.; Rao, S.; Tarjan, R. 7 1992 An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties. Zbl 0743.68077 King, Valerie 1 1991 A lower bound for the recognition of digraph properties. Zbl 0733.05041 King, V. 6 1990 all cited Publications top 5 cited Publications all top 5 Cited by 531 Authors 13 King, Valerie 12 Rauch Henzinger, Monika 9 Saia, Jared 7 Italiano, Giuseppe Francesco 7 Jansson, Jesper 6 Baswana, Surender 6 Rahmati, Zahed 6 Young, Maxwell 5 Hellmuth, Marc 5 Roch, Sébastien 5 Roditty, Liam 4 Augustine, John E. 4 Censor-Hillel, Keren 4 Chatterjee, Krishnendu 4 Cohen, Ran 4 Demetrescu, Camil 4 Karczmarz, Adam 4 Krinninger, Sebastian 4 Movahedi, Mahnush 4 Nanongkai, Danupon 4 Paschos, Vangelis Th. 4 Stadler, Peter F. 3 Bernstein, Aaron 3 Boria, Nicolas 3 Chan, Timothy Moon-Yew 3 Chechik, Shiri 3 Dani, Varsha 3 Franciosa, Paolo Giulio 3 Geiß, Manuela 3 Goldberg, Andrew V. 3 Kaplan, Haim 3 Łącki, Jakub 3 Mostefaoui, Achour 3 Pandurangan, Gopal 3 Pettie, Seth 3 Raynal, Michel 3 Robinson, Peter 3 Scheideler, Christian 3 Sivasubramaniam, Sumathi 3 Whitesides, Sue H. 2 Abam, Mohammad Ali 2 Acar, Umut A. 2 Afshar, Ramtin 2 Alon, Noga 2 Andoni, Alexandr 2 Balzotti, Lorenzo 2 Boyle, Elette 2 Bradford, Phillip G. 2 Brown, Daniel G. 2 Chakraborty, Dibyayan 2 Chan, T.-H. Hubert 2 Chandran, L. Sunil 2 Charalampopoulos, Panagiotis 2 Choudhary, Keerti 2 Cohen, Sarel 2 Ding, Wei 2 Fernández-Baca, David 2 Fich, Faith Ellen 2 Fleischer, Rudolf 2 Gawrychowski, Paweł 2 Ghiyasvand, Mehdi 2 Goel, Aarushi 2 Goodrich, Michael Truman 2 Habib, Michel 2 Haitner, Iftach 2 Henzinger, Thomas A. 2 Hernandez-Rosales, Maribel 2 Hochbaum, Dorit S. 2 Holm, Jacob 2 Iwano, Kazuo 2 Kashyop, Manas Jyoti 2 Katoh, Naoki 2 Khan, Shahbaz 2 Korman, Amos 2 Korman, Matias 2 Kowaluk, Mirosław 2 Kuhn, Fabian 2 Kutyłowski, Mirosław 2 Lenzen, Christoph 2 Lingas, Andrzej 2 Loryś, Krzysztof 2 Loss, Julian 2 Lundell, Eva-Marta 2 Mashreghi, Ali 2 Mathieu, Claire 2 McCormick, S. Thomas 2 Micali, Silvio 2 Molla, Anisur Rahaman 2 Monnot, Jérôme 2 Mossel, Elchanan 2 Nayak, Kartik 2 Orlin, James B. 2 Padinhatteeri, Sajith 2 Pass, Rafael 2 Paz, Ami 2 Pillai, Raji R. 2 Qiu, Ke 2 Queyranne, Maurice 2 Ragde, Prabhakar L. 2 Raghuraman, Srinivasan ...and 431 more Authors all top 5 Cited in 54 Serials 23 Algorithmica 19 Theoretical Computer Science 17 Distributed Computing 14 SIAM Journal on Computing 10 Discrete Applied Mathematics 7 Journal of Computer and System Sciences 7 Networks 5 Information Processing Letters 5 Information and Computation 5 Random Structures & Algorithms 4 Journal of Mathematical Biology 4 Journal of Cryptology 4 Mathematical Programming. Series A. Series B 3 European Journal of Combinatorics 3 Discrete & Computational Geometry 3 Journal of Parallel and Distributed Computing 3 Computational Geometry 3 Journal of Graph Algorithms and Applications 3 Journal of the ACM 3 Journal of Discrete Algorithms 3 Algorithms 2 Applied Mathematics and Computation 2 Information Sciences 2 Combinatorica 2 Computers & Operations Research 2 SIAM Journal on Discrete Mathematics 2 The Annals of Applied Probability 2 Theory of Computing Systems 2 Journal of Combinatorial Optimization 2 ACM Journal of Experimental Algorithmics 1 Acta Informatica 1 Discrete Mathematics 1 International Journal of Theoretical Physics 1 Journal of Graph Theory 1 Naval Research Logistics 1 Advances in Applied Mathematics 1 Operations Research Letters 1 Applied Mathematical Modelling 1 European Journal of Operational Research 1 SIAM Review 1 SIAM Journal on Optimization 1 Computational Complexity 1 Journal of Functional Programming 1 The Journal of Artificial Intelligence Research (JAIR) 1 Discussiones Mathematicae. Graph Theory 1 Constraints 1 Data Mining and Knowledge Discovery 1 RAIRO. Operations Research 1 Journal of Machine Learning Research (JMLR) 1 Internet Mathematics 1 Parallel Processing Letters 1 Discrete Optimization 1 Transactions on Combinatorics 1 Computer Science Review all top 5 Cited in 16 Fields 202 Computer science (68-XX) 99 Combinatorics (05-XX) 40 Operations research, mathematical programming (90-XX) 26 Biology and other natural sciences (92-XX) 21 Information and communication theory, circuits (94-XX) 10 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 9 Numerical analysis (65-XX) 5 Probability theory and stochastic processes (60-XX) 2 Convex and discrete geometry (52-XX) 2 Statistics (62-XX) 2 Quantum theory (81-XX) 1 Commutative algebra (13-XX) 1 Group theory and generalizations (20-XX) 1 Functions of a complex variable (30-XX) 1 Functional analysis (46-XX) 1 Geometry (51-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.