


default search action
Valerie King
Person information
- affiliation: University of Victoria, Canada
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [i23]John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg:
Distributed Download from an External Data Source in Faulty Majority Settings. CoRR abs/2412.19649 (2024) - 2023
- [j28]Sima Hajiaghaei Shanjani
, Valerie King:
Communication costs in a geometric communication network. Theor. Comput. Sci. 977: 114161 (2023) - [c68]Valerie King, Alex Thomo, Quinton Yong:
Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time. IJCAI 2023: 2160-2168 - 2022
- [i22]Trisha Chakraborty, Abir Islam, Valerie King, Daniel Rayborn, Jared Saia, Maxwell Young:
Bankrupting DoS Attackers Despite Uncertainty. CoRR abs/2205.08287 (2022) - [i21]Valerie King, Alex Thomo, Quinton Yong:
Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time. CoRR abs/2211.04627 (2022) - 2021
- [j27]Ali Mashreghi, Valerie King:
Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model. Distributed Comput. 34(4): 283-299 (2021) - [c67]Sima Hajiaghaei Shanjani, Valerie King:
Communication Costs in a Geometric Communication Network. ICDCN 2021: 36-45 - [e3]Hung Viet Le, Valerie King:
4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021. SIAM 2021, ISBN 978-1-61197-649-6 [contents] - [i20]Sima Hajiaghaei Shanjani, Valerie King:
Communication Costs in a Geometric Communication Network. CoRR abs/2104.13499 (2021) - 2020
- [c66]Omer Wasim
, Valerie King:
Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT. FSTTCS 2020: 33:1-33:19 - [c65]John Augustine
, Valerie King, Anisur Rahaman Molla
, Gopal Pandurangan
, Jared Saia
:
Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols. DISC 2020: 31:1-31:19
2010 – 2019
- 2019
- [j26]Zahed Rahmati
, Mohammad Ali Abam, Valerie King, Sue Whitesides:
Kinetic k-Semi-Yao graph and its applications. Comput. Geom. 77: 10-26 (2019) - [c64]Jacob Holm, Valerie King, Mikkel Thorup
, Or Zamir, Uri Zwick:
Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges. FOCS 2019: 896-909 - [c63]Ali Mashreghi, Valerie King:
Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. DISC 2019: 49:1-49:3 - [i19]John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, Jared Saia:
Scalable and Secure Computation Among Strangers: Resource-Competitive Byzantine Protocols. CoRR abs/1907.10308 (2019) - [i18]Ali Mashreghi, Valerie King:
Faster asynchronous MST and low diameter tree construction with sublinear communication. CoRR abs/1907.12152 (2019) - [i17]Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick:
Random k-out subgraph leaves only O(n/k) inter-component edges. CoRR abs/1909.11147 (2019) - 2018
- [j25]Valerie King, Seth Pettie, Jared Saia, Maxwell Young
:
A resource-competitive jamming defense. Distributed Comput. 31(6): 419-439 (2018) - [j24]Dan Alistarh, James Aspnes, Valerie King, Jared Saia:
Communication-efficient randomized consensus. Distributed Comput. 31(6): 489-501 (2018) - [c62]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: 199-205 - [c61]Ali Mashreghi, Valerie King:
Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model. DISC 2018: 37:1-37:17 - [i16]Udit Agarwal, Vijaya Ramachandran, Valerie King, Matteo Pontecorvi:
A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in O͠(n3/2) Rounds. CoRR abs/1804.05441 (2018) - [i15]Ali Mashreghi, Valerie King:
Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model. CoRR abs/1806.04328 (2018) - [i14]Valerie King, Jared Saia:
Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016. CoRR abs/1812.10169 (2018) - 2017
- [j23]Varsha Dani
, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani:
Secure multi-party computation in large networks. Distributed Comput. 30(3): 193-229 (2017) - [c60]Ali Mashreghi, Valerie King:
Time-communication trade-offs for minimum spanning tree construction. ICDCN 2017: 8 - [e2]Hamed Hatami, Pierre McKenzie, Valerie King:
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. ACM 2017, ISBN 978-1-4503-4528-6 [contents] - [i13]Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani:
Secure Multi-Party Computation in Large Networks. IACR Cryptol. ePrint Arch. 2017: 1003 (2017) - 2016
- [j22]Valerie King, Jared Saia:
Byzantine Agreement in Expected Polynomial Time. J. ACM 63(2): 13:1-13:21 (2016) - [c59]Ariel Webster, Bruce M. Kapron
, Valerie King:
Stability of certainty and opinion in influence networks. ASONAM 2016: 1309-1320 - [c58]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: 235-261 - [r4]Valerie King:
Fully Dynamic Connectivity. Encyclopedia of Algorithms 2016: 792-793 - [r3]Valerie King:
Fully Dynamic Transitive Closure. Encyclopedia of Algorithms 2016: 808-809 - [i12]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: 760 (2016) - 2015
- [j21]Zahed Rahmati
, Mohammad Ali Abam, Valerie King, Sue Whitesides, Alireza Zarei:
A simple, faster method for kinetic proximity problems. Comput. Geom. 48(4): 342-359 (2015) - [c57]Valerie King, Shay Kutten, Mikkel Thorup
:
Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication. PODC 2015: 71-80 - [i11]Valerie King, Shay Kutten, Mikkel Thorup:
Construction and impromptu repair of an MST in a distributed network with o(m) communication. CoRR abs/1502.03320 (2015) - [i10]David Gibb, Bruce M. Kapron, Valerie King, Nolan Thorn:
Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR abs/1509.06464 (2015) - 2014
- [c56]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 - [c55]Varsha Dani
, Valerie King, Mahnush Movahedi, Jared Saia:
Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation. ICDCN 2014: 242-256 - [c54]Zahed Rahmati
, Valerie King, Sue Whitesides:
Kinetic Reverse k-Nearest Neighbor Problem. IWOCA 2014: 307-317 - [c53]Zahed Rahmati
, Valerie King, Sue Whitesides:
(Reverse) k-nearest neighbors for moving objects. MIG 2014: 187 - [c52]Valerie King, Jared Saia:
Faster Agreement via a Spectral Method for Detecting Malicious Behavior. SODA 2014: 785-800 - [c51]Seth Gilbert
, Valerie King, Seth Pettie, Ely Porat, Jared Saia, Maxwell Young:
(Near) optimal resource-competitive broadcast with jamming. SPAA 2014: 257-266 - [c50]Dan Alistarh, James Aspnes, Valerie King, Jared Saia:
Communication-Efficient Randomized Consensus. DISC 2014: 61-75 - [i9]Zahed Rahmati, Valerie King, Sue Whitesides:
Kinetic Reverse $k$-Nearest Neighbor Problem. CoRR abs/1406.5554 (2014) - [i8]Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides:
Kinetic $k$-Semi-Yao Graph and its Applications. CoRR abs/1412.5697 (2014) - 2013
- [c49]Zahed Rahmati
, Valerie King, Sue Whitesides:
Kinetic data structures for all nearest neighbors and closest pair in the plane. SoCG 2013: 137-144 - [c48]Valerie King, Jared Saia:
Brief announcement: byzantine agreement with a strong adversary in polynomial expected time. PODC 2013: 187-189 - [c47]Bruce M. Kapron
, Valerie King, Ben Mountjoy:
Dynamic graph connectivity in polylogarithmic worst case time. SODA 2013: 1131-1142 - [c46]Valerie King, Jared Saia:
Byzantine agreement in polynomial expected time: [extended abstract]. STOC 2013: 401-410 - [e1]Keren Censor-Hillel, Valerie King:
Proceedings Ninth International Workshop on Foundations of Mobile Computing, FOMC 2013, Jerusalem, Israel, October 17-18, 2013. EPTCS 132, 2013 [contents] - [i7]Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia:
Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation. CoRR abs/1310.3486 (2013) - [i6]Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides, Alireza Zarei:
A Simple, Faster Method for Kinetic Proximity Problems. CoRR abs/1311.2032 (2013) - 2012
- [j20]Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja:
Predicting missing contacts in mobile social networks. Pervasive Mob. Comput. 8(5): 698-716 (2012) - [c45]Seth Gilbert
, Jared Saia, Valerie King, Maxwell Young:
Resource-competitive analysis: a new perspective on attack-resistant distributed computing. FOMC 2012: 1 - [c44]Zahed Rahmati
, Sue Whitesides, Valerie King:
Kinetic and Stationary Point-Set Embeddability for Plane Graphs. GD 2012: 279-290 - [c43]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: 227-228 - [i5]Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja:
They Know Where You Live! CoRR abs/1202.3504 (2012) - [i4]Valerie King, Jared Saia, Maxwell Young:
Resource-Competitive Communication. CoRR abs/1202.6456 (2012) - [i3]Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia:
Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary. CoRR abs/1203.0289 (2012) - 2011
- [j19]Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young:
Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks. Algorithmica 61(3): 518-554 (2011) - [j18]Louis Lei Yu, Valerie King:
The evolution of friendships in Chinese online social networks. Int. J. Soc. Comput. Cyber Phys. Syst. 1(2): 180-205 (2011) - [j17]Valerie King, Jared Saia:
Breaking the O(n2) bit barrier: Scalable byzantine agreement with an adaptive adversary. J. ACM 58(4): 18:1-18:24 (2011) - [c42]Valerie King, Steven Lonargan, Jared Saia, Amitabh Trehan
:
Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. ICDCN 2011: 203-214 - [c41]Valerie King, Jared Saia, Maxwell Young:
Conflict on a communication channel. PODC 2011: 277-286 - [c40]Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja:
Empirical Comparison of Information Spreading Algorithms in the Presence of 1-Whiskers. SocialCom/PASSAT 2011: 489-492 - [c39]Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja:
Predicting missing contacts in mobile social networks. WOWMOM 2011: 1-9 - 2010
- [j16]Valerie King, Jared Saia:
Scalable byzantine computation. SIGACT News 41(3): 89-104 (2010) - [j15]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): 68:1-68:28 (2010) - [c38]Kazem Jahanbakhsh, Gholamali C. Shoja, Valerie King:
Human Contact Prediction Using Contact Graph Inference. GreenCom/CPSCom 2010: 813-818 - [c37]Olumuyiwa Oluwasanmi, Jared Saia, Valerie King:
An empirical study of a scalable Byzantine agreement algorithm. IPDPS Workshops 2010: 1-13 - [c36]Bo Wu, Jared Saia, Valerie King:
Attack-resistant frequency counting. IPDPS 2010: 1-10 - [c35]Kazem Jahanbakhsh, Gholamali C. Shoja, Valerie King:
Social-Greedy: a socially-based greedy routing algorithm for delay tolerant networks. MobiOpp 2010: 159-162 - [c34]Valerie King, Jared Saia:
Breaking the O(n2) bit barrier: scalable byzantine agreement with an adaptive adversary. PODC 2010: 420-429 - [c33]Louis Yu, Valerie King:
The Evolution of Friendships in Chinese Online Social Networks. SocialCom/PASSAT 2010: 81-87 - [i2]Valerie King, Jared Saia:
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary. CoRR abs/1002.4561 (2010)
2000 – 2009
- 2009
- [c32]Valerie King, Louis Yu, Yan Zhuang:
Guanxi in the Chinese Web. CSE (4) 2009: 9-17 - [c31]Valerie King, Jared Saia:
Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary. PODC 2009: 304-305 - [c30]Valerie King, Jared Saia:
From Almost Everywhere to Everywhere: Byzantine Agreement with Õ(n3/2) Bits. DISC 2009: 464-478 - 2008
- [j14]Dan Holtby, Bruce M. Kapron
, Valerie King:
Lower bound for scalable Byzantine Agreement. Distributed Comput. 21(4): 239-248 (2008) - [c29]Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young:
Sleeping on the job: energy-efficient and robust broadcast for radio networks. PODC 2008: 243-252 - [c28]Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani:
Fast asynchronous byzantine agreement and leader election with full information. SODA 2008: 1038-1047 - [c27]Yueh-Hua Lee, Alex Thomo, Kui Wu, Valerie King:
Scalable Ubiquitous Data Access in Clustered Sensor Networks. SSDBM 2008: 533-540 - [c26]Valerie King, Louis Lei Yu, Yan Zhuang:
Guanxi in the chinese web - a study of mutual linking. WWW 2008: 1161-1162 - [r2]Valerie King:
Fully Dynamic Connectivity. Encyclopedia of Algorithms 2008 - [r1]Valerie King:
Fully Dynamic Transitive Closure. Encyclopedia of Algorithms 2008 - 2007
- [j13]Valerie King, Scott Lewis, Jared Saia, Maxwell Young:
Choosing a Random Peer in Chord. Algorithmica 49(2): 147-169 (2007) - [i1]Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young:
Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks. CoRR abs/0710.2532 (2007) - 2006
- [c25]Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee:
Towards Secure and Scalable Computation in Peer-to-Peer Networks. FOCS 2006: 87-98 - [c24]Dan Holtby, Bruce M. Kapron
, Valerie King:
Lower bound for scalable Byzantine Agreement. PODC 2006: 285-291 - [c23]Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee:
Scalable leader election. SODA 2006: 990-999 - 2005
- [c22]Kui Wu, Chong Liu, Valerie King:
Very low cost sensor localization for hostile environments. ICC 2005: 3197-3201 - [c21]Chong Liu, Kui Wu, Valerie King:
Randomized Coverage-Preserving Scheduling Schemes for Wireless Sensor Networks. NETWORKING 2005: 956-967 - 2004
- [c20]Dennis Dreef, Sanaz Ahari, Kui Wu, Valerie King:
Utilizing the Uncertainty of Intrusion Detection to Strengthen Security for Ad Hoc Networks. ADHOC-NOW 2004: 82-95 - [c19]Sarah Carruthers, Valerie King:
Connectivity of Wireless Sensor Networks with Constant Density. ADHOC-NOW 2004: 149-157 - [c18]Valerie King, Jared Saia:
Choosing a random peer. PODC 2004: 125-130 - 2003
- [c17]Valerie King, Li Zhang, Yunhong Zhou:
On the complexity of distance-based evolutionary tree reconstruction. SODA 2003: 444-453 - 2002
- [j12]Valerie King, Garry Sagert:
A Fully Dynamic Algorithm for Maintaining the Transitive Closure. J. Comput. Syst. Sci. 65(1): 150-167 (2002) - 2001
- [j11]Monika Rauch Henzinger, Valerie King:
Maintaining Minimum Spanning Forests in Dynamic Graphs. SIAM J. Comput. 31(2): 364-374 (2001) - [c16]Valerie King, Mikkel Thorup:
A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms. COCOON 2001: 268-277 - [c15]Valerie King, Orna Kupferman, Moshe Y. Vardi:
On the Complexity of Parity Word Automata. FoSSaCS 2001: 276-286
1990 – 1999
- 1999
- [j10]Monika Rauch Henzinger, Valerie King, Tandy J. Warnow:
Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology. Algorithmica 24(1): 1-13 (1999) - [j9]Monika Rauch Henzinger, Valerie King:
Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation. J. ACM 46(4): 502-516 (1999) - [c14]Valerie King:
Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. FOCS 1999: 81-91 - [c13]Valerie King, Garry Sagert:
A Fully Dynamic Algorithm for Maintaining the Transitive Closure. STOC 1999: 492-498 - 1997
- [j8]Valerie King:
A Simpler Minimum Spanning Tree Verification Algorithm. Algorithmica 18(2): 263-270 (1997) - [j7]Valerie King, Chung Keung Poon, Vijaya Ramachandran, Santanu Sinha:
An Optimal EREW PRAM Algorithm for Minimum Spanning Tree Verification. Inf. Process. Lett. 62(3): 153-159 (1997) - [c12]Monika Rauch Henzinger, Valerie King:
Maintaining Minimum Spanning Trees in Dynamic Graphs. ICALP 1997: 594-604 - 1996
- [j6]Faith E. Fich, Russell Impagliazzo
, Bruce M. Kapron
, Valerie King, Miroslaw Kutylowski:
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. J. Comput. Syst. Sci. 53(1): 104-111 (1996) - [c11]Monika Rauch Henzinger, Valerie King, Tandy J. Warnow:
Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology. SODA 1996: 333-340 - 1995
- [c10]Monika Rauch Henzinger, Valerie King:
Fully Dynamic Biconnectivity and Transitive Closure. FOCS 1995: 664-672 - [c9]Monika Rauch Henzinger, Valerie King:
Randomized dynamic graph algorithms with polylogarithmic time per operation. STOC 1995: 519-527 - [c8]Valerie King:
A Simpler Minimum Spanning Tree Verification Algorithm. WADS 1995: 440-448 - 1994
- [j5]Valerie King, S. Rao, Robert Endre Tarjan:
A Faster Deterministic Maximum Flow Algorithm. J. Algorithms 17(3): 447-474 (1994) - [j4]Claire Kenyon, Valerie King:
On Boolean Decision Trees with Faulty Nodes. Random Struct. Algorithms 5(3): 453-464 (1994) - 1993
- [j3]Wayne Goddard, Claire Kenyon, Valerie King, Leonard J. Schulman
:
Optimal Randomized Algorithms for Local Sorting and Set-Maxima. SIAM J. Comput. 22(2): 272-283 (1993) - [c7]Faith E. Fich, Russell Impagliazzo
, Bruce M. Kapron
, Valerie King, Miroslaw Kutylowski:
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. STACS 1993: 386-397 - 1992
- [c6]Claire Kenyon, Valerie King:
On Boolean Decision Trees with Faulty Nodes. ISTCS 1992: 24-31 - [c5]Valerie King, S. Rao, Robert Endre Tarjan:
A Faster Deterministic Maximum Flow Algorithm. SODA 1992: 157-164 - 1991
- [j2]Valerie King:
An Omega(n5/4) lower bound on the randomized complexity of graph properties. Comb. 11(1): 23-32 (1991) - 1990
- [j1]Valerie King:
A lower bound for the recognition of digraph properties. Comb. 10(1): 53-59 (1990) - [c4]Wayne Goddard, Valerie King, Leonard J. Schulman:
Optimal Randomized Algorithms for Local Sorting and Set-Maxima. STOC 1990: 45-53
1980 – 1989
- 1989
- [c3]Tzi-cker Chiueh, Randy H. Katz, Valerie King:
Managing the VLSI Design Process. MIT-JSME Workshop 1989: 183-199 - [c2]