Valerie King - RankMe

134 papers A* 33A 11B 8C 3Misc 5Journal 53Unranked 15

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	A Polynomial-Time Algorithm for EFX Orientations of Chores. CoRR Kevin Hsu, Valerie King
2025	B	`conf`	Bankrupting DoS Attackers. SIROCCO Trisha Chakraborty, Abir Islam, Valerie King, Daniel Rayborn, Jared Saia, Maxwell Young
2025	A	`conf`	Brief Announcement: Distributed Download from an External Data Source in Asynchronous Faulty Settings. DISC John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg
2025	A*	`conf`	Brief Announcement: Distributed Download from an External Data Source in Byzantine Majority Settings. PODC John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg
2025	B	`conf`	Distributed Download from an External Data Source in Asynchronous Faulty Settings. OPODIS John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg
2025	J	`jnl`	Distributed Download from an External Data Source in Asynchronous Faulty Settings. CoRR John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg
2025	A	`conf`	Distributed Download from an External Data Source in Byzantine Majority Settings. DISC John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg
2025	A	`conf`	Polynomial-Time Algorithms for Fair Orientations of Chores. ECAI Kevin Hsu, Valerie King
2024	J	`jnl`	Distributed Download from an External Data Source in Faulty Majority Settings. CoRR John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg
2023	J	`jnl`	Communication costs in a geometric communication network. Theor. Comput. Sci. Sima Hajiaghaei Shanjani, Valerie King
2023	A*	`conf`	Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time. IJCAI Valerie King, Alex Thomo, Quinton Yong
2022	J	`jnl`	Bankrupting DoS Attackers Despite Uncertainty. CoRR Trisha Chakraborty, Abir Islam, Valerie King, Daniel Rayborn, Jared Saia, Maxwell Young
2022	J	`jnl`	Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time. CoRR Valerie King, Alex Thomo, Quinton Yong
2021	—	`ed.`	4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021 SOSA Hung Viet Le, Valerie King
2021	J	`jnl`	Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model. Distributed Comput. Ali Mashreghi, Valerie King
2021	Misc	`conf`	Communication Costs in a Geometric Communication Network. ICDCN Sima Hajiaghaei Shanjani, Valerie King
2021	J	`jnl`	Communication Costs in a Geometric Communication Network. CoRR Sima Hajiaghaei Shanjani, Valerie King
2020	—	`conf`	Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT. FSTTCS Omer Wasim, Valerie King
2020	A	`conf`	Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols. DISC John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, Jared Saia
2019	A	`conf`	Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. DISC Ali Mashreghi, Valerie King
2019	J	`jnl`	Faster asynchronous MST and low diameter tree construction with sublinear communication. CoRR Ali Mashreghi, Valerie King
2019	J	`jnl`	Kinetic Comput. Geom. Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides
2019	A*	`conf`	Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges. FOCS Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick
2019	J	`jnl`	Random k-out subgraph leaves only O(n/k) inter-component edges. CoRR Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick
2019	J	`jnl`	Scalable and Secure Computation Among Strangers: Resource-Competitive Byzantine Protocols. CoRR John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, Jared Saia
2018	J	`jnl`	A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in O͠(n CoRR Udit Agarwal, Vijaya Ramachandran, Valerie King, Matteo Pontecorvi
2018	A*	`conf`	A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds. PODC Udit Agarwal, Vijaya Ramachandran, Valerie King, Matteo Pontecorvi
2018	J	`jnl`	A resource-competitive jamming defense. Distributed Comput. Valerie King, Seth Pettie, Jared Saia, Maxwell Young
2018	A	`conf`	Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model. DISC Ali Mashreghi, Valerie King
2018	J	`jnl`	Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model. CoRR Ali Mashreghi, Valerie King
2018	J	`jnl`	Communication-efficient randomized consensus. Distributed Comput. Dan Alistarh, James Aspnes, Valerie King, Jared Saia
2018	J	`jnl`	Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016. CoRR Valerie King, Jared Saia
2017	A*	`ed.`	Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 STOC Hamed Hatami, Pierre McKenzie, Valerie King
2017	J	`jnl`	Secure Multi-Party Computation in Large Networks. IACR Cryptol. ePrint Arch. Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani
2017	J	`jnl`	Secure multi-party computation in large networks. Distributed Comput. Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani
2017	Misc	`conf`	Time-communication trade-offs for minimum spanning tree construction. ICDCN Ali Mashreghi, Valerie King
2016	J	`jnl`	Byzantine Agreement in Expected Polynomial Time. J. ACM Valerie King, Jared Saia
2016	—	`ch.`	Fully Dynamic Connectivity. Encyclopedia of Algorithms Valerie King
2016	—	`ch.`	Fully Dynamic Transitive Closure. Encyclopedia of Algorithms Valerie King
2016	—	`conf`	Simultaneous Secrecy and Reliability Amplification for a General Channel Model. TCC (B1) Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
2016	J	`jnl`	Simultaneous Secrecy and Reliability Amplification for a General Channel Model. IACR Cryptol. ePrint Arch. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
2016	B	`conf`	Stability of certainty and opinion in influence networks. ASONAM Ariel Webster, Bruce M. Kapron, Valerie King
2015	J	`jnl`	A simple, faster method for kinetic proximity problems. Comput. Geom. Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides, Alireza Zarei
2015	A*	`conf`	Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication. PODC Valerie King, Shay Kutten, Mikkel Thorup
2015	J	`jnl`	Construction and impromptu repair of an MST in a distributed network with o(m) communication. CoRR Valerie King, Shay Kutten, Mikkel Thorup
2015	J	`jnl`	Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR David Gibb, Bruce M. Kapron, Valerie King, Nolan Thorn
2014	B	`conf`	(Near) optimal resource-competitive broadcast with jamming. SPAA Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, Maxwell Young
2014	C	`conf`	(Reverse) MIG Zahed Rahmati, Valerie King, Sue Whitesides
2014	A	`conf`	Communication-Efficient Randomized Consensus. DISC Dan Alistarh, James Aspnes, Valerie King, Jared Saia
2014	A*	`conf`	Faster Agreement via a Spectral Method for Detecting Malicious Behavior. SODA Valerie King, Jared Saia
2014	J	`jnl`	Kinetic $k$-Semi-Yao Graph and its Applications. CoRR Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides
2014	—	`conf`	Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d. CCCG Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides
2014	J	`jnl`	Kinetic Reverse $k$-Nearest Neighbor Problem. CoRR Zahed Rahmati, Valerie King, Sue Whitesides
2014	C	`conf`	Kinetic Reverse k-Nearest Neighbor Problem. IWOCA Zahed Rahmati, Valerie King, Sue Whitesides
2014	Misc	`conf`	Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation. ICDCN Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia
2013	J	`jnl`	A Simple, Faster Method for Kinetic Proximity Problems. CoRR Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides, Alireza Zarei
2013	A*	`conf`	Brief announcement: byzantine agreement with a strong adversary in polynomial expected time. PODC Valerie King, Jared Saia
2013	A*	`conf`	Byzantine agreement in polynomial expected time: [extended abstract]. STOC Valerie King, Jared Saia
2013	A*	`conf`	Dynamic graph connectivity in polylogarithmic worst case time. SODA Bruce M. Kapron, Valerie King, Ben Mountjoy
2013	A*	`conf`	Kinetic data structures for all nearest neighbors and closest pair in the plane. SoCG Zahed Rahmati, Valerie King, Sue Whitesides
2013	—	`ed.`	Proceedings Ninth International Workshop on Foundations of Mobile Computing, FOMC 2013, Jerusalem, Israel, October 17-18, 2013. FOMC Keren Censor-Hillel, Valerie King
2013	J	`jnl`	Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation. CoRR Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia
2012	J	`jnl`	Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary CoRR Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia
2012	A*	`conf`	Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary. PODC Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia
2012	A	`conf`	Kinetic and Stationary Point-Set Embeddability for Plane Graphs. GD Zahed Rahmati, Sue Whitesides, Valerie King
2012	J	`jnl`	Predicting missing contacts in mobile social networks. Pervasive Mob. Comput. Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
2012	J	`jnl`	Resource-Competitive Communication CoRR Valerie King, Jared Saia, Maxwell Young
2012	—	`conf`	Resource-competitive analysis: a new perspective on attack-resistant distributed computing. FOMC Seth Gilbert, Jared Saia, Valerie King, Maxwell Young
2012	J	`jnl`	They Know Where You Live! CoRR Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
2011	J	`jnl`	Breaking the J. ACM Valerie King, Jared Saia
2011	A*	`conf`	Conflict on a communication channel. PODC Valerie King, Jared Saia, Maxwell Young
2011	—	`conf`	Empirical Comparison of Information Spreading Algorithms in the Presence of 1-Whiskers. SocialCom/PASSAT Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
2011	Misc	`conf`	Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. ICDCN Valerie King, Steven Lonargan, Jared Saia, Amitabh Trehan
2011	C	`conf`	Predicting missing contacts in mobile social networks. WOWMOM Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
2011	J	`jnl`	Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks. Algorithmica Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young
2011	J	`jnl`	The evolution of friendships in Chinese online social networks. Int. J. Soc. Comput. Cyber Phys. Syst. Louis Lei Yu, Valerie King
2010	—	`conf`	An empirical study of a scalable Byzantine agreement algorithm. IPDPS Workshops Olumuyiwa Oluwasanmi, Jared Saia, Valerie King
2010	A	`conf`	Attack-resistant frequency counting. IPDPS Bo Wu, Jared Saia, Valerie King
2010	A*	`conf`	Breaking the PODC Valerie King, Jared Saia
2010	J	`jnl`	Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary CoRR Valerie King, Jared Saia
2010	J	`jnl`	Fast asynchronous Byzantine agreement and leader election with full information. ACM Trans. Algorithms Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani
2010	—	`conf`	Human Contact Prediction Using Contact Graph Inference. GreenCom/CPSCom Kazem Jahanbakhsh, Gholamali C. Shoja, Valerie King
2010	J	`jnl`	Scalable byzantine computation. SIGACT News Valerie King, Jared Saia
2010	—	`conf`	Social-Greedy: a socially-based greedy routing algorithm for delay tolerant networks. MobiOpp Kazem Jahanbakhsh, Gholamali C. Shoja, Valerie King
2010	—	`conf`	The Evolution of Friendships in Chinese Online Social Networks. SocialCom/PASSAT Louis Yu, Valerie King
2009	A*	`conf`	Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary. PODC Valerie King, Jared Saia
2009	A	`conf`	From Almost Everywhere to Everywhere: Byzantine Agreement with Õ(n DISC Valerie King, Jared Saia
2009	—	`conf`	Guanxi in the Chinese Web. CSE (4) Valerie King, Louis Yu, Yan Zhuang
2008	A*	`conf`	Fast asynchronous byzantine agreement and leader election with full information. SODA Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani
2008	—	`ch.`	Fully Dynamic Connectivity. Encyclopedia of Algorithms Valerie King
2008	—	`ch.`	Fully Dynamic Transitive Closure. Encyclopedia of Algorithms Valerie King
2008	A*	`conf`	Guanxi in the chinese web - a study of mutual linking. WWW Valerie King, Louis Lei Yu, Yan Zhuang
2008	J	`jnl`	Lower bound for scalable Byzantine Agreement. Distributed Comput. Dan Holtby, Bruce M. Kapron, Valerie King
2008	B	`conf`	Scalable Ubiquitous Data Access in Clustered Sensor Networks. SSDBM Yueh-Hua Lee, Alex Thomo, Kui Wu, Valerie King
2008	A*	`conf`	Sleeping on the job: energy-efficient and robust broadcast for radio networks. PODC Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young
2007	J	`jnl`	Choosing a Random Peer in Chord. Algorithmica Valerie King, Scott Lewis, Jared Saia, Maxwell Young
2007	J	`jnl`	Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks CoRR Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young
2006	A*	`conf`	Lower bound for scalable Byzantine Agreement. PODC Dan Holtby, Bruce M. Kapron, Valerie King
2006	A*	`conf`	Scalable leader election. SODA Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee
2006	A*	`conf`	Towards Secure and Scalable Computation in Peer-to-Peer Networks. FOCS Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee
2005	B	`conf`	Randomized Coverage-Preserving Scheduling Schemes for Wireless Sensor Networks. NETWORKING Chong Liu, Kui Wu, Valerie King
2005	—	`conf`	Very low cost sensor localization for hostile environments. ICC Kui Wu, Chong Liu, Valerie King
2004	A*	`conf`	Choosing a random peer. PODC Valerie King, Jared Saia
2004	—	`conf`	Connectivity of Wireless Sensor Networks with Constant Density. ADHOC-NOW Sarah Carruthers, Valerie King
2004	—	`conf`	Utilizing the Uncertainty of Intrusion Detection to Strengthen Security for Ad Hoc Networks. ADHOC-NOW Dennis Dreef, Sanaz Ahari, Kui Wu, Valerie King
2003	A*	`conf`	On the complexity of distance-based evolutionary tree reconstruction. SODA Valerie King, Li Zhang, Yunhong Zhou
2002	J	`jnl`	A Fully Dynamic Algorithm for Maintaining the Transitive Closure. J. Comput. Syst. Sci. Valerie King, Garry Sagert
2001	Misc	`conf`	A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms. COCOON Valerie King, Mikkel Thorup
2001	J	`jnl`	Maintaining Minimum Spanning Forests in Dynamic Graphs. SIAM J. Comput. Monika Rauch Henzinger, Valerie King
2001	B	`conf`	On the Complexity of Parity Word Automata. FoSSaCS Valerie King, Orna Kupferman, Moshe Y. Vardi
1999	A*	`conf`	A Fully Dynamic Algorithm for Maintaining the Transitive Closure. STOC Valerie King, Garry Sagert
1999	J	`jnl`	Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology. Algorithmica Monika Rauch Henzinger, Valerie King, Tandy J. Warnow
1999	A*	`conf`	Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. FOCS Valerie King
1999	J	`jnl`	Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation. J. ACM Monika Rauch Henzinger, Valerie King
1997	J	`jnl`	A Simpler Minimum Spanning Tree Verification Algorithm. Algorithmica Valerie King
1997	J	`jnl`	An Optimal EREW PRAM Algorithm for Minimum Spanning Tree Verification. Inf. Process. Lett. Valerie King, Chung Keung Poon, Vijaya Ramachandran, Santanu Sinha
1997	A*	`conf`	Maintaining Minimum Spanning Trees in Dynamic Graphs. ICALP Monika Rauch Henzinger, Valerie King
1996	A*	`conf`	Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology. SODA Monika Rauch Henzinger, Valerie King, Tandy J. Warnow
1996	J	`jnl`	Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. J. Comput. Syst. Sci. Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski
1995	B	`conf`	A Simpler Minimum Spanning Tree Verification Algorithm. WADS Valerie King
1995	A*	`conf`	Fully Dynamic Biconnectivity and Transitive Closure. FOCS Monika Rauch Henzinger, Valerie King
1995	A*	`conf`	Randomized dynamic graph algorithms with polylogarithmic time per operation. STOC Monika Rauch Henzinger, Valerie King
1994	J	`jnl`	A Faster Deterministic Maximum Flow Algorithm. J. Algorithms Valerie King, S. Rao, Robert Endre Tarjan
1994	J	`jnl`	On Boolean Decision Trees with Faulty Nodes. Random Struct. Algorithms Claire Kenyon, Valerie King
1993	A	`conf`	Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. STACS Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski
1993	J	`jnl`	Optimal Randomized Algorithms for Local Sorting and Set-Maxima. SIAM J. Comput. Wayne Goddard, Claire Kenyon, Valerie King, Leonard J. Schulman
1992	A*	`conf`	A Faster Deterministic Maximum Flow Algorithm. SODA Valerie King, S. Rao, Robert Endre Tarjan
1992	—	`conf`	On Boolean Decision Trees with Faulty Nodes. ISTCS Claire Kenyon, Valerie King
1991	J	`jnl`	An Omega(n Comb. Valerie King
1990	J	`jnl`	A lower bound for the recognition of digraph properties. Comb. Valerie King
1990	A*	`conf`	Optimal Randomized Algorithms for Local Sorting and Set-Maxima STOC Wayne Goddard, Valerie King, Leonard J. Schulman
1989	—	`conf`	Managing the VLSI Design Process. MIT-JSME Workshop Tzi-cker Chiueh, Randy H. Katz, Valerie King
1989	A*	`conf`	Verifying Partial Orders STOC Claire Kenyon-Mathieu, Valerie King
1988	A*	`conf`	Lower Bounds on the Complexity of Graph Properties STOC Valerie King