| 2025 | ECAI | Polynomial-Time Algorithms for Fair Orientations of Chores. | Kevin Hsu, Valerie King |
| 2025 | OPODIS | Distributed Download from an External Data Source in Asynchronous Faulty Settings. | John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg |
| 2025 | PODC | Brief Announcement: Distributed Download from an External Data Source in Byzantine Majority Settings. | John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg |
| 2025 | SIROCCO | Bankrupting DoS Attackers. | Trisha Chakraborty, Abir Islam, Valerie King, Daniel Rayborn, Jared Saia, Maxwell Young |
| 2023 | IJCAI | Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time. | Valerie King, Alex Thomo, Quinton Yong |
| 2021 | ICDCN | Communication Costs in a Geometric Communication Network. | Sima Hajiaghaei Shanjani, Valerie King |
| 2019 | FOCS | Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges. | Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick |
| 2018 | PODC | A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in (n 3/2 ) Rounds. | Udit Agarwal, Vijaya Ramachandran, Valerie King, Matteo Pontecorvi |
| 2017 | ICDCN | Time-communication trade-offs for minimum spanning tree construction. | Ali Mashreghi, Valerie King |
| 2016 | TCC | Simultaneous Secrecy and Reliability Amplification for a General Channel Model. | Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro |
| 2015 | PODC | Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication. | Valerie King, Shay Kutten, Mikkel Thorup |
| 2014 | ICDCN | Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation. | Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia |
| 2014 | IWOCA | Kinetic Reverse k-Nearest Neighbor Problem. | Zahed Rahmati, Valerie King, Sue Whitesides |
| 2014 | MIG | (Reverse) | Zahed Rahmati, Valerie King, Sue Whitesides |
| 2014 | SODA | Faster Agreement via a Spectral Method for Detecting Malicious Behavior. | Valerie King, Jared Saia |
| 2014 | SPAA | (Near) optimal resource-competitive broadcast with jamming. | Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, Maxwell Young |
| 2013 | PODC | Brief announcement: byzantine agreement with a strong adversary in polynomial expected time. | Valerie King, Jared Saia |
| 2013 | SODA | Dynamic graph connectivity in polylogarithmic worst case time. | Bruce M. Kapron, Valerie King, Ben Mountjoy |
| 2013 | STOC | Byzantine agreement in polynomial expected time: [extended abstract]. | Valerie King, Jared Saia |
| 2012 | GD | Kinetic and Stationary Point-Set Embeddability for Plane Graphs. | Zahed Rahmati, Sue Whitesides, Valerie King |
| 2012 | PODC | Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary. | Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia |
| 2011 | ICDCN | Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. | Valerie King, Steven Lonargan, Jared Saia, Amitabh Trehan |
| 2011 | PODC | Conflict on a communication channel. | Valerie King, Jared Saia, Maxwell Young |
| 2011 | WoWMoM | Predicting missing contacts in mobile social networks. | Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja |
| 2010 | PODC | Breaking the | Valerie King, Jared Saia |
| 2009 | PODC | Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary. | Valerie King, Jared Saia |
| 2008 | PODC | Sleeping on the job: energy-efficient and robust broadcast for radio networks. | Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young |
| 2008 | WWW | Guanxi in the chinese web - a study of mutual linking. | Valerie King, Louis Lei Yu, Yan Zhuang |
| 2008 | SODA | Fast asynchronous byzantine agreement and leader election with full information. | Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani |
| 2008 | SSDBM | Scalable Ubiquitous Data Access in Clustered Sensor Networks. | Yueh-Hua Lee, Alex Thomo, Kui Wu, Valerie King |
| 2006 | FOCS | Towards Secure and Scalable Computation in Peer-to-Peer Networks. | Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee |
| 2006 | PODC | Lower bound for scalable Byzantine Agreement. | Dan Holtby, Bruce M. Kapron, Valerie King |
| 2006 | SODA | Scalable leader election. | Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee |
| 2005 | Networking | Randomized Coverage-Preserving Scheduling Schemes for Wireless Sensor Networks. | Chong Liu, Kui Wu, Valerie King |
| 2004 | PODC | Choosing a random peer. | Valerie King, Jared Saia |
| 2003 | SODA | On the complexity of distance-based evolutionary tree reconstruction. | Valerie King, Li Zhang, Yunhong Zhou |
| 2001 | COCOON | A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms. | Valerie King, Mikkel Thorup |
| 2001 | FOSSACS | On the Complexity of Parity Word Automata. | Valerie King, Orna Kupferman, Moshe Y. Vardi |
| 1999 | FOCS | Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. | Valerie King |
| 1999 | STOC | A Fully Dynamic Algorithm for Maintaining the Transitive Closure. | Valerie King, Garry Sagert |
| 1997 | ICALP | Maintaining Minimum Spanning Trees in Dynamic Graphs. | Monika Rauch Henzinger, Valerie King |
| 1996 | SODA | Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology. | Monika Rauch Henzinger, Valerie King, Tandy J. Warnow |
| 1995 | FOCS | Fully Dynamic Biconnectivity and Transitive Closure. | Monika Rauch Henzinger, Valerie King |
| 1995 | STOC | Randomized dynamic graph algorithms with polylogarithmic time per operation. | Monika Rauch Henzinger, Valerie King |
| 1995 | WADS | A Simpler Minimum Spanning Tree Verification Algorithm. | Valerie King |
| 1993 | STACS | Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. | Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski |
| 1992 | SODA | A Faster Deterministic Maximum Flow Algorithm. | Valerie King, S. Rao, Robert Endre Tarjan |
| 1990 | STOC | Optimal Randomized Algorithms for Local Sorting and Set-Maxima | Wayne Goddard, Valerie King, Leonard J. Schulman |
| 1989 | STOC | Verifying Partial Orders | Claire Kenyon-Mathieu, Valerie King |
| 1988 | STOC | Lower Bounds on the Complexity of Graph Properties | Valerie King |