Valerie King

Publication Activity (10 Years)

Years Active: 1988-2023
Publications (10 Years): 33

Top Venues

CoRR

Distributed Comput.

DISC

ICDCN

Publications

Valerie King, Alex Thomo, Quinton Yong
Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time. IJCAI (2023)
Sima Hajiaghaei Shanjani, Valerie King
Communication costs in a geometric communication network. Theor. Comput. Sci. 977 (2023)
Valerie King, Alex Thomo, Quinton Yong
Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time. CoRR (2022)
Trisha Chakraborty, Abir Islam, Valerie King, Daniel Rayborn, Jared Saia, Maxwell Young
Bankrupting DoS Attackers Despite Uncertainty. CoRR (2022)
Sima Hajiaghaei Shanjani, Valerie King
Communication Costs in a Geometric Communication Network. ICDCN (2021)
Sima Hajiaghaei Shanjani, Valerie King
Communication Costs in a Geometric Communication Network. CoRR (2021)
Ali Mashreghi, Valerie King
Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model. Distributed Comput. 34 (4) (2021)
John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, Jared Saia
Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols. DISC (2020)
Omer Wasim, Valerie King
Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT. FSTTCS (2020)
Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick
Random k-out subgraph leaves only O(n/k) inter-component edges. CoRR (2019)
Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick
Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges. FOCS (2019)
Ali Mashreghi, Valerie King
Faster asynchronous MST and low diameter tree construction with sublinear communication. CoRR (2019)
Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides
-Semi-Yao graph and its applications. Comput. Geom. 77 (2019)
John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, Jared Saia
Scalable and Secure Computation Among Strangers: Resource-Competitive Byzantine Protocols. CoRR (2019)
Ali Mashreghi, Valerie King
Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. DISC (2019)
Dan Alistarh, James Aspnes, Valerie King, Jared Saia
Communication-efficient randomized consensus. Distributed Comput. 31 (6) (2018)
Ali Mashreghi, Valerie King
Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model. CoRR (2018)
Valerie King, Seth Pettie, Jared Saia, Maxwell Young
A resource-competitive jamming defense. Distributed Comput. 31 (6) (2018)
Valerie King, Jared Saia
Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016. CoRR (2018)
Udit Agarwal, Vijaya Ramachandran, Valerie King, Matteo Pontecorvi
A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds. PODC (2018)
Ali Mashreghi, Valerie King
Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model. DISC (2018)
Udit Agarwal, Vijaya Ramachandran, Valerie King, Matteo Pontecorvi
) Rounds. CoRR (2018)
Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani
Secure multi-party computation in large networks. Distributed Comput. 30 (3) (2017)
Ali Mashreghi, Valerie King
Time-communication trade-offs for minimum spanning tree construction. ICDCN (2017)
Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani
Secure Multi-Party Computation in Large Networks. IACR Cryptol. ePrint Arch. 2017 (2017)
Ariel Webster, Bruce M. Kapron, Valerie King
Stability of certainty and opinion in influence networks. ASONAM (2016)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
Simultaneous Secrecy and Reliability Amplification for a General Channel Model. TCC (B1) (2016)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
Simultaneous Secrecy and Reliability Amplification for a General Channel Model. IACR Cryptol. ePrint Arch. 2016 (2016)
Valerie King, Jared Saia
Byzantine Agreement in Expected Polynomial Time. J. ACM 63 (2) (2016)
Valerie King, Shay Kutten, Mikkel Thorup
Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication. PODC (2015)
David Gibb, Bruce M. Kapron, Valerie King, Nolan Thorn
Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR (2015)
Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides, Alireza Zarei
A simple, faster method for kinetic proximity problems. Comput. Geom. 48 (4) (2015)
Valerie King, Shay Kutten, Mikkel Thorup
Construction and impromptu repair of an MST in a distributed network with o(m) communication. CoRR (2015)
Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides
Kinetic $k$-Semi-Yao Graph and its Applications. CoRR (2014)
Zahed Rahmati, Valerie King, Sue Whitesides
Kinetic Reverse k-Nearest Neighbor Problem. IWOCA (2014)
Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, Maxwell Young
(Near) optimal resource-competitive broadcast with jamming. SPAA (2014)
Zahed Rahmati, Valerie King, Sue Whitesides
-nearest neighbors for moving objects. MIG (2014)
Valerie King, Jared Saia
Faster Agreement via a Spectral Method for Detecting Malicious Behavior. SODA (2014)
Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides
Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d. CCCG (2014)
Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia
Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation. ICDCN (2014)
Dan Alistarh, James Aspnes, Valerie King, Jared Saia
Communication-Efficient Randomized Consensus. DISC (2014)
Zahed Rahmati, Valerie King, Sue Whitesides
Kinetic Reverse $k$-Nearest Neighbor Problem. CoRR (2014)
Valerie King, Jared Saia
Brief announcement: byzantine agreement with a strong adversary in polynomial expected time. PODC (2013)
Zahed Rahmati, Valerie King, Sue Whitesides
Kinetic data structures for all nearest neighbors and closest pair in the plane. SoCG (2013)
Valerie King, Jared Saia
Byzantine agreement in polynomial expected time: [extended abstract]. STOC (2013)
Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia
Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation. CoRR (2013)
Bruce M. Kapron, Valerie King, Ben Mountjoy
Dynamic graph connectivity in polylogarithmic worst case time. SODA (2013)
Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides, Alireza Zarei
A Simple, Faster Method for Kinetic Proximity Problems. CoRR (2013)
Zahed Rahmati, Sue Whitesides, Valerie King
Kinetic and Stationary Point-Set Embeddability for Plane Graphs. Graph Drawing (2012)
Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia
Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary CoRR (2012)
Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia
Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary. PODC (2012)
Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
They Know Where You Live! CoRR (2012)
Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
Predicting missing contacts in mobile social networks. Pervasive Mob. Comput. 8 (5) (2012)
Seth Gilbert, Jared Saia, Valerie King, Maxwell Young
Resource-competitive analysis: a new perspective on attack-resistant distributed computing. FOMC (2012)
Valerie King, Jared Saia, Maxwell Young
Resource-Competitive Communication CoRR (2012)
Louis Lei Yu, Valerie King
The evolution of friendships in Chinese online social networks. Int. J. Soc. Comput. Cyber Phys. Syst. 1 (2) (2011)
Valerie King, Jared Saia, Maxwell Young
Conflict on a communication channel. PODC (2011)
Valerie King, Steven Lonargan, Jared Saia, Amitabh Trehan
Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. ICDCN (2011)
Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
Empirical Comparison of Information Spreading Algorithms in the Presence of 1-Whiskers. SocialCom/PASSAT (2011)
Valerie King, Jared Saia
) bit barrier: Scalable byzantine agreement with an adaptive adversary. J. ACM 58 (4) (2011)
Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
Predicting missing contacts in mobile social networks. WOWMOM (2011)
Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young
Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks. Algorithmica 61 (3) (2011)
Bo Wu, Jared Saia, Valerie King
Attack-resistant frequency counting. IPDPS (2010)
Valerie King, Jared Saia
Scalable byzantine computation. SIGACT News 41 (3) (2010)
Louis Yu, Valerie King
The Evolution of Friendships in Chinese Online Social Networks. SocialCom/PASSAT (2010)
Valerie King, Jared Saia
) bit barrier: scalable byzantine agreement with an adaptive adversary. PODC (2010)
Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani
Fast asynchronous Byzantine agreement and leader election with full information. ACM Trans. Algorithms 6 (4) (2010)
Valerie King, Jared Saia
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary CoRR (2010)
Kazem Jahanbakhsh, Gholamali C. Shoja, Valerie King
Human Contact Prediction Using Contact Graph Inference. GreenCom/CPSCom (2010)
Olumuyiwa Oluwasanmi, Jared Saia, Valerie King
An empirical study of a scalable Byzantine agreement algorithm. IPDPS Workshops (2010)
Kazem Jahanbakhsh, Gholamali C. Shoja, Valerie King
Social-Greedy: a socially-based greedy routing algorithm for delay tolerant networks. MobiOpp (2010)
Valerie King, Jared Saia
) Bits. DISC (2009)
Valerie King, Louis Yu, Yan Zhuang
Guanxi in the Chinese Web. CSE (4) (2009)
Valerie King, Jared Saia
Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary. PODC (2009)
Yueh-Hua Lee, Alex Thomo, Kui Wu, Valerie King
Scalable Ubiquitous Data Access in Clustered Sensor Networks. SSDBM (2008)
Dan Holtby, Bruce M. Kapron, Valerie King
Lower bound for scalable Byzantine Agreement. Distributed Comput. 21 (4) (2008)
Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani
Fast asynchronous byzantine agreement and leader election with full information. SODA (2008)
Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young
Sleeping on the job: energy-efficient and robust broadcast for radio networks. PODC (2008)
Valerie King, Louis Lei Yu, Yan Zhuang
Guanxi in the chinese web - a study of mutual linking. WWW (2008)
Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young
Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks CoRR (2007)
Valerie King, Scott Lewis, Jared Saia, Maxwell Young
Choosing a Random Peer in Chord. Algorithmica 49 (2) (2007)
Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee
Towards Secure and Scalable Computation in Peer-to-Peer Networks. FOCS (2006)
Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee
Scalable leader election. SODA (2006)
Dan Holtby, Bruce M. Kapron, Valerie King
Lower bound for scalable Byzantine Agreement. PODC (2006)
Chong Liu, Kui Wu, Valerie King
Randomized Coverage-Preserving Scheduling Schemes for Wireless Sensor Networks. NETWORKING (2005)
Kui Wu, Chong Liu, Valerie King
Very low cost sensor localization for hostile environments. ICC (2005)
Sarah Carruthers, Valerie King
Connectivity of Wireless Sensor Networks with Constant Density. ADHOC-NOW (2004)
Valerie King, Jared Saia
Choosing a random peer. PODC (2004)
Dennis Dreef, Sanaz Ahari, Kui Wu, Valerie King
Utilizing the Uncertainty of Intrusion Detection to Strengthen Security for Ad Hoc Networks. ADHOC-NOW (2004)
Valerie King, Li Zhang, Yunhong Zhou
On the complexity of distance-based evolutionary tree reconstruction. SODA (2003)
Valerie King, Garry Sagert
A Fully Dynamic Algorithm for Maintaining the Transitive Closure. J. Comput. Syst. Sci. 65 (1) (2002)
Monika Rauch Henzinger, Valerie King
Maintaining Minimum Spanning Forests in Dynamic Graphs. SIAM J. Comput. 31 (2) (2001)
Valerie King, Mikkel Thorup
A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms. COCOON (2001)
Valerie King, Orna Kupferman, Moshe Y. Vardi
On the Complexity of Parity Word Automata. FoSSaCS (2001)
Valerie King
Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. FOCS (1999)
Monika Rauch Henzinger, Valerie King, Tandy J. Warnow
Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology. Algorithmica 24 (1) (1999)
Valerie King, Garry Sagert
A Fully Dynamic Algorithm for Maintaining the Transitive Closure. STOC (1999)
Monika Rauch Henzinger, Valerie King
Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation. J. ACM 46 (4) (1999)
Valerie King, Chung Keung Poon, Vijaya Ramachandran, Santanu Sinha
An Optimal EREW PRAM Algorithm for Minimum Spanning Tree Verification. Inf. Process. Lett. 62 (3) (1997)
Monika Rauch Henzinger, Valerie King
Maintaining Minimum Spanning Trees in Dynamic Graphs. ICALP (1997)

Valerie King.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Valerie King