Valerie King
According to our database^{1},
Valerie King
authored at least 93 papers
between 1988 and 2019.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2014, "For contributions to randomized algorithms, especially dynamic graph algorithms and fault tolerant distributed computing.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at dl.acm.org
On csauthors.net:
Bibliography
2019
Faster asynchronous MST and low diameter tree construction with sublinear communication.
CoRR, 2019
Scalable and Secure Computation Among Strangers: ResourceCompetitive Byzantine Protocols.
CoRR, 2019
Kinetic kSemiYao graph and its applications.
Comput. Geom., 2019
Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication.
Proceedings of the 33rd International Symposium on Distributed Computing, 2019
Random kout Subgraph Leaves only O(n/k) InterComponent Edges.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019
2018
A resourcecompetitive jamming defense.
Distributed Computing, 2018
Communicationefficient randomized consensus.
Distributed Computing, 2018
Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016.
CoRR, 2018
A Deterministic Distributed Algorithm for Exact Weighted AllPairs Shortest Paths in O͠(n^{3/2}) Rounds.
CoRR, 2018
Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018
A Deterministic Distributed Algorithm for Exact Weighted AllPairs Shortest Paths in Õ(n 3/2 ) Rounds.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018
2017
Secure multiparty computation in large networks.
Distributed Computing, 2017
Timecommunication tradeoffs for minimum spanning tree construction.
Proceedings of the 18th International Conference on Distributed Computing and Networking, 2017
2016
Fully Dynamic Transitive Closure.
Encyclopedia of Algorithms, 2016
Fully Dynamic Connectivity.
Encyclopedia of Algorithms, 2016
Byzantine Agreement in Expected Polynomial Time.
J. ACM, 2016
Simultaneous Secrecy and Reliability Amplification for a General Channel Model.
IACR Cryptology ePrint Archive, 2016
Stability of certainty and opinion in influence networks.
Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2016
2015
Dynamic graph connectivity with improved worst case update time and sublinear space.
CoRR, 2015
A simple, faster method for kinetic proximity problems.
Comput. Geom., 2015
Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015
2014
Kinetic $k$SemiYao Graph and its Applications.
CoRR, 2014
(Near) optimal resourcecompetitive broadcast with jamming.
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014
Faster Agreement via a Spectral Method for Detecting Malicious Behavior.
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
(Reverse) knearest neighbors for moving objects.
Proceedings of the Seventh International Conference on Motion in Games, Playa Vista, CA, USA, November 06, 2014
Kinetic Reverse kNearest Neighbor Problem.
Proceedings of the Combinatorial Algorithms  25th International Workshop, 2014
Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation.
Proceedings of the Distributed Computing and Networking  15th International Conference, 2014
Kinetic Data Structures for the SemiYao Graph and All Nearest Neighbors in R^d.
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014
2013
Byzantine agreement in polynomial expected time: [extended abstract].
Proceedings of the Symposium on Theory of Computing Conference, 2013
Dynamic graph connectivity in polylogarithmic worst case time.
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
Brief announcement: byzantine agreement with a strong adversary in polynomial expected time.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013
Kinetic data structures for all nearest neighbors and closest pair in the plane.
Proceedings of the Symposuim on Computational Geometry 2013, 2013
2012
Predicting missing contacts in mobile social networks.
Pervasive Mob. Comput., 2012
Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary
CoRR, 2012
ResourceCompetitive Communication
CoRR, 2012
They Know Where You Live!
CoRR, 2012
Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012
Kinetic and Stationary PointSet Embeddability for Plane Graphs.
Proceedings of the Graph Drawing  20th International Symposium, 2012
Resourcecompetitive analysis: a new perspective on attackresistant distributed computing.
Proceedings of the FOMC'12, 2012
2011
Breaking the O(n^{2}) bit barrier: Scalable byzantine agreement with an adaptive adversary.
J. ACM, 2011
The evolution of friendships in Chinese online social networks.
IJSCCPS, 2011
Sleeping on the Job: EnergyEfficient and Robust Broadcast for Radio Networks.
Algorithmica, 2011
Empirical Comparison of Information Spreading Algorithms in the Presence of 1Whiskers.
Proceedings of the PASSAT/SocialCom 2011, Privacy, 2011
Conflict on a communication channel.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011
Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information.
Proceedings of the Distributed Computing and Networking  12th International Conference, 2011
2010
Fast asynchronous Byzantine agreement and leader election with full information.
ACM Trans. Algorithms, 2010
Scalable byzantine computation.
SIGACT News, 2010
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary
CoRR, 2010
The Evolution of Friendships in Chinese Online Social Networks.
Proceedings of the 2010 IEEE Second International Conference on Social Computing, 2010
SocialGreedy: a sociallybased greedy routing algorithm for delay tolerant networks.
Proceedings of the Second International Workshop on Mobile Opportunistic Networking, 2010
Attackresistant frequency counting.
Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing, 2010
An empirical study of a scalable Byzantine agreement algorithm.
Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing, 2010
Human Contact Prediction Using Contact Graph Inference.
Proceedings of the 2010 IEEE/ACM Int'l Conference on Green Computing and Communications, 2010
2009
From Almost Everywhere to Everywhere: Byzantine Agreement with Õ(n^{3/2}) Bits.
Proceedings of the Distributed Computing, 23rd International Symposium, 2009
Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009
Guanxi in the Chinese Web.
Proceedings of the 12th IEEE International Conference on Computational Science and Engineering, 2009
2008
Fully Dynamic Transitive Closure.
Proceedings of the Encyclopedia of Algorithms  2008 Edition, 2008
Fully Dynamic Connectivity.
Proceedings of the Encyclopedia of Algorithms  2008 Edition, 2008
Lower bound for scalable Byzantine Agreement.
Distributed Computing, 2008
Guanxi in the chinese web  a study of mutual linking.
Proceedings of the 17th International Conference on World Wide Web, 2008
Scalable Ubiquitous Data Access in Clustered Sensor Networks.
Proceedings of the Scientific and Statistical Database Management, 2008
2007
Sleeping on the Job: EnergyEfficient Broadcast for Radio Networks
CoRR, 2007
Choosing a Random Peer in Chord.
Algorithmica, 2007
2006
Scalable leader election.
Proceedings of the Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms, 2006
Towards Secure and Scalable Computation in PeertoPeer Networks.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
2005
Randomized CoveragePreserving Scheduling Schemes for Wireless Sensor Networks.
Proceedings of the NETWORKING 2005: Networking Technologies, 2005
Very low cost sensor localization for hostile environments.
Proceedings of IEEE International Conference on Communications, 2005
2004
Choosing a random peer.
Proceedings of the TwentyThird Annual ACM Symposium on Principles of Distributed Computing, 2004
Utilizing the Uncertainty of Intrusion Detection to Strengthen Security for Ad Hoc Networks.
Proceedings of the AdHoc, Mobile, and Wireless Networks: Third International Conference, 2004
Connectivity of Wireless Sensor Networks with Constant Density.
Proceedings of the AdHoc, Mobile, and Wireless Networks: Third International Conference, 2004
2003
On the complexity of distancebased evolutionary tree reconstruction.
Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2003
2002
A Fully Dynamic Algorithm for Maintaining the Transitive Closure.
J. Comput. Syst. Sci., 2002
2001
Maintaining Minimum Spanning Forests in Dynamic Graphs.
SIAM J. Comput., 2001
On the Complexity of Parity Word Automata.
Proceedings of the Foundations of Software Science and Computation Structures, 2001
A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001
1999
Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.
J. ACM, 1999
Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.
Algorithmica, 1999
Fully Dynamic Algorithms for Maintaining AllPairs Shortest Paths and Transitive Closure in Digraphs.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1997
An Optimal EREW PRAM Algorithm for Minimum Spanning Tree Verification.
Inf. Process. Lett., 1997
A Simpler Minimum Spanning Tree Verification Algorithm.
Algorithmica, 1997
Maintaining Minimum Spanning Trees in Dynamic Graphs.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997
1996
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution.
J. Comput. Syst. Sci., 1996
1995
Randomized dynamic graph algorithms with polylogarithmic time per operation.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
Fully Dynamic Biconnectivity and Transitive Closure.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995
1994
On Boolean Decision Trees with Faulty Nodes.
Random Struct. Algorithms, 1994
A Faster Deterministic Maximum Flow Algorithm.
J. Algorithms, 1994
1993
Optimal Randomized Algorithms for Local Sorting and SetMaxima.
SIAM J. Comput., 1993
1991
An Omega(n^{5/4}) lower bound on the randomized complexity of graph properties.
Combinatorica, 1991
1990
A lower bound for the recognition of digraph properties.
Combinatorica, 1990
Optimal Randomized Algorithms for Local Sorting and SetMaxima
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
1989
Verifying Partial Orders
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Managing the VLSI Design Process.
Proceedings of the ComputerAided Cooperative Product Development, MITJSME Workshop, 1989
1988
Lower Bounds on the Complexity of Graph Properties
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988