Valerie King

According to our database1, Valerie King authored at least 106 papers between 1988 and 2018.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

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 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
A resource-competitive jamming defense.
Distributed Computing, 2018

Communication-efficient randomized consensus.
Distributed Computing, 2018

Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model.
CoRR, 2018

A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in O͠(n3/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 All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

2017
Secure Multi-Party Computation in Large Networks.
IACR Cryptology ePrint Archive, 2017

Secure multi-party computation in large networks.
Distributed Computing, 2017

Time-communication trade-offs 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

Simultaneous Secrecy and Reliability Amplification for a General Channel Model.
Proceedings of the Theory of Cryptography - 14th International Conference, 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
Construction and impromptu repair of an MST in a distributed network with o(m) communication.
CoRR, 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 Reverse $k$-Nearest Neighbor Problem.
CoRR, 2014

Kinetic $k$-Semi-Yao Graph and its Applications.
CoRR, 2014

Communication-Efficient Randomized Consensus.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

(Near) optimal resource-competitive 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 Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

(Reverse) k-nearest neighbors for moving objects.
Proceedings of the Seventh International Conference on Motion in Games, Playa Vista, CA, USA, November 06, 2014

Kinetic Reverse k-Nearest 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 Semi-Yao Graph and All Nearest Neighbors in R^d.
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014

2013
A Simple, Faster Method for Kinetic Proximity Problems.
CoRR, 2013

Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation.
CoRR, 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 Twenty-Fourth Annual ACM-SIAM 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 and Mobile Computing, 2012

Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary
CoRR, 2012

Resource-Competitive 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 Point-Set Embeddability for Plane Graphs.
Proceedings of the Graph Drawing - 20th International Symposium, 2012

Resource-competitive analysis: a new perspective on attack-resistant distributed computing.
Proceedings of the FOMC'12, 2012

2011
Breaking the O(n2) 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: Energy-Efficient and Robust Broadcast for Radio Networks.
Algorithmica, 2011

Predicting missing contacts in mobile social networks.
Proceedings of the 12th IEEE International Symposium on a World of Wireless, 2011

Empirical Comparison of Information Spreading Algorithms in the Presence of 1-Whiskers.
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

Breaking the O(n2) bit barrier: scalable byzantine agreement with an adaptive adversary.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Social-Greedy: a socially-based greedy routing algorithm for delay tolerant networks.
Proceedings of the Second International Workshop on Mobile Opportunistic Networking, 2010

Attack-resistant 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 Õ(n3/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

Fully Dynamic Connectivity.
Proceedings of the Encyclopedia of Algorithms, 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

Fast asynchronous byzantine agreement and leader election with full information.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Sleeping on the job: energy-efficient and robust broadcast for radio networks.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

2007
Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks
CoRR, 2007

Choosing a Random Peer in Chord.
Algorithmica, 2007

2006
Scalable leader election.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Lower bound for scalable Byzantine Agreement.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

Towards Secure and Scalable Computation in Peer-to-Peer Networks.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Randomized Coverage-Preserving 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 Twenty-Third 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 Ad-Hoc, Mobile, and Wireless Networks: Third International Conference, 2004

Connectivity of Wireless Sensor Networks with Constant Density.
Proceedings of the Ad-Hoc, Mobile, and Wireless Networks: Third International Conference, 2004

2003
On the complexity of distance-based evolutionary tree reconstruction.
Proceedings of the Fourteenth Annual ACM-SIAM 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

A Fully Dynamic Algorithm for Maintaining the Transitive Closure.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Fully Dynamic Algorithms for Maintaining All-Pairs 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

Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995
A Simpler Minimum Spanning Tree Verification Algorithm.
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Randomized dynamic graph algorithms with polylogarithmic time per operation.
Proceedings of the Twenty-Seventh 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 Set-Maxima.
SIAM J. Comput., 1993

Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution.
Proceedings of the STACS 93, 1993

1992
A Faster Deterministic Maximum Flow Algorithm.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

On Boolean Decision Trees with Faulty Nodes.
Proceedings of the Theory of Computing and Systems, 1992

1991
An Omega(n5/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 Set-Maxima
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 Computer-Aided Cooperative Product Development, MIT-JSME Workshop, 1989

1988
Lower Bounds on the Complexity of Graph Properties
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988


  Loading...