Selected Publications

Conference and Journal Papers

• Fraud Detection for Random Walks by Varsha Dani, Tom Hayes, Seth Pettie and Jared Saia Innovations in Theoretical Computer Science, 2024.

• Defending Hash Tables from Subterfuge with Depth Charge by Trisha Chakraborty, Jared Saia, Maxwell Young 24th International Conference On Distributed Computing And Networking, 2024. Best Paper Award.

• Boundary Sketching with Asymptotically Optimal Distance and Rotation (Full Paper) by Varsha Dani, Abir Islam, and Jared Saia Journal of Theoretical Computer Science, 2024.

• Boundary Sketching with Asymptotically Optimal Distance and Rotation by Varsha Dani, Abir Islam, and Jared Saia International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2023. Best Student Paper Award.

• Bankrupting Sybil Despite Churn, Full Paper by Diksha Gupta, Jared Saia, Maxwell Young, Journal of Computer and System Sciences, 2022. This is significantly expanded over the conference paper, with extended exposition on the ABC model of churn.

• Bankrupting Sybil Despite Churn by Diksha Gupta, Jared Saia, Maxwell Young, International Conference on Distributed Computing Systems (ICDCS), 2021. Video of Talk by Diksha Gupta (8 minutes).

• Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols by John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia, Symposium on Distributed Computing (DISC), 2020. Talk Slides. Video of Talk (20 minutes).

• Resource Burning for Permissionless Systems by Diksha Gupta, Jared Saia and Maxwell Young, Invited Paper to International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2020. Talk Slides. Video of Talk (60 minutes).

• ANTS on a Plane by Abhinav Aggarwal and Jared Saia, International Colloquium on Structural Information and Communication Complexity (SIROCCO), Best Paper Award, 2020. Talk Slides. Video of Talk (40 minutes).

• Peace Through Superior Puzzling: An Asymmetric Sybil Defense by Diksha Gupta, Jared Saia and Maxwell Young, IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2019.

• Bootstrapping Public Blockchains Without a Trusted Setup by Abhinav Aggarwal, Mahnush Movahedi, Jared Saia, Mahdi Zamani, Brief Announcement at Principles of Distributed Computing (PODC) 2019.

• A Most Irrational Foraging Algorithm by A Aggarwal, W. Vining, D. Gupta, J Saia, M. Moses, Brief Announcement at Principles of Distributed Computing (PODC) 2019.

• Multiparty Interactive Communication with Private Channels by A Aggarwal, V Dani, TP Hayes, J Saia, International Conference on Distributed Computing and Networking (ICDCN), Best Paper Award Nominee. 2019.

• Making Social-Network Data Sets More Human: A Topological Approach by Jon Berry, Cindy Phillips and Jared Saia Journal of Statistical Analysis and Data Mining, 2019.

• Proof of Work Without All the Work: Computationally Efficient Attack-Resistant Systems by D Gupta, J Saia, M Young, International Conference on Distributed Computing and Networking (ICDCN), 2018.

• Sending a Message with Unknown Noise by Abhinav Aggarwal, Varsha Dani, Tom Hayes, and Jared Saia International Conference on Distributed Computing and Networking (ICDCN) 2018.

• Communication-efficient Randomized Consensus by Dan Alistarh, James Aspnes, Valerie King, Jared Saia Journal of Distributed Computing 2018.

• Interactive Communication with Unknown Noise Rate by Varsha Dani, Tom Hayes, Mahnush Mohavedi, Jared Saia and Maxwell Young, Journal of Information and Computation 2018.

• A Resource-competitive Jamming Defense by Valerie King, Seth Pettie, Jared Saia, Maxwell Young , Journal of Distributed Computing, 2018.

• Tiny Groups Tackle Byzantine Advesaries by Mercy Jaiyeola, Kyle Patron, Jared Saia, Maxwell Young and Qian Zhou IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2018.

• A Theoretical and Empirical Evaluation of an Algorithm for Self-Healing Computation by George Saad and Jared Saia, Journal of Distribted Computing,, 2017.

• TorBricks: Blocking-Resistant Tor Bridge Distribution by Mahdi Zamani, Jared Saia, Jedidiah Crandall, International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2017.

• Byzantine Agreement in Expected Polynomial Time by Valerie King and Jared Saia, Journal of the ACM(JACM), 2016. This corrigendum corrects a technical error in the original paper.

• Recent Results in Scalable Multi-party Computation by Jared Saia and Mahdi Zamani, International Conference on Current Trends in Theory and Practice of Informatics, 2015.

• Secure Multi-Party Shuffling by Mahnush Movahedi, Jared Saia and Mahdi Zamani, International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2015.

• Shuffle To Baffle: Towards Scalable Protocols for Secure Multi-party Shuffling by Mahnush Movahedi, Jared Saia and Mahdi Zamani, International Conference on Distributed Computing Systems (ICDCS), 2015.

• Resource Competitive Algorithms by M. Bender, V. Dani, J. Fineman, S. Gilbert, M. Movahed, S. Pettie, J. Saia, M. Young, ACM SIGACT News, 2015.

• Interactive Communication with Unknown Noise Rate by Varsha Dani, Tom Hayes, Mahnush Mohavedi, Jared Saia and Maxwell Young, International Colloquium on Automata, Languages, and Programming (ICALP) 2015. Invited to special issue of "Information and Computation" devoted to selected papers from ICALP 2015.

• Cooperative Computing for Autonomous Data Centers by JW Berry, M Collins, A Kearns, CA Phillips, J Saia, RD Smith IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2015.

• Communication-efficient Randomized Consensus by D Alistarh, J Aspnes, V King, J Saia Symposium on Distributed Computing (DISC) 2014.

• (Near) Optimal Resource-Competitive Broadcast with Jamming by Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, and Maxwell Young, Symposium on Parallelism in Algorithms and Architectures (SPAA) 2014.

• Faster Agreement Via a Spectral Method for Detecting Malicious Behavior by Valerie King and Jared Saia, Symposium on Discrete Algorithms (SODA), 2014. Slides from Talk (SODA)

• Self-Healing Computation by George Saad and Jared Saia, Proceedings of the 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2014.

• Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation by Varsha Dani, Valerie King, Mahnush Movahedi and Jared Saia, International Conference on Distributed Computing and Networking (ICDCN), 2014. Best Paper Award Winner in Distributed Computing Track.

• Towards Provably-Secure Scalable Anonymous Broadcast by Mahdi Zamani, Jared Saia, Mahnush Movahedi, and Joud Khoury, USENIX Workshop on Free and Open Communications on the Internet (FOCI'13), 2013.

• The Power of Mediation in an Extended El-Farol Game by Dieter Mitsche, George Saad and Jared Saia, Symposium on on Algorithmic Game Theory (SAGT), 2013.

• Byzantine Agreement in Polynomial Expected Time by Valerie King and Jared Saia, Symposium on Theory of Computing (STOC), 2013. Slides from Talk (Ann Arbor)

• Self-Healing of Byzantine Faults by Jeffrey Knockel, George Saad and Jared Saia, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2013.

• Resource-Competitive Analysis: A New Perspective on Attack-Resistant Distributed Computing by Seth Gilbert, Valerie King, Jared Saia, Maxwell Young, International Workshop on Foundations of Mobile Computing (FOMC), 2012.

• Scalable Byzantine agreement with a Random Beacon by Olumuyiwa Oluwasanmi and Jared Saia, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2012.

• Whiskey, Weed, and Wukan on the World Wide Web: On Measuring Censors' Resources and Motivations by Nicholas Aase, Jedidiah R. Crandall, Alvaro Diaz, Jeffrey Knockel, Jorge Ocana Molinero, Jared Saia, Dan Wallach, Tao Zhu, USENIX Workshop on Free and Open Communications on the Internet. (FOCI) 2011.

• Breaking the $O(nm)$ Bit Barrier: Secure Multiparty Computation with a Static Adversary by Varsha Dani, Valerie King, Mahnush Mohavedi and Jared Saia, Brief Announcement, PODC 2012.

• Load balanced scalable byzantine agreement through quorum building, with full information by King, Valerie, Steven Lonargan, Jared Saia, and Amitabh Trehan International Conference on Distributed Computing and Networking 2011.
  UPDATE: Optimal Load-Balanced Scalable Distributed Agreement by Gelles and Komargodski, in STOC 2024, gives a computationally efficient version of the result from our paper.

• Three Researchers, Five Conjectures by Jeffrey Knockel, Jed Crandall and Jared Saia, USENIX Workshop on Free and Open Communications on the Internet. (FOCI) 2011.

• Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary by Valerie King and Jared Saia, Journal of the ACM(JACM), 2011.

• Combinatorial Auctions with Budgets by Amos Fiat, Stefano Leonardi, Jared Saia and Piotr Sankowski, ACM Conference on Electronic Commerce (EC), 2011.

• Conflict on a Communication Channel by Valerie King, Jared Saia and Maxwell Young, Principles of Distributed Computing (PODC), 2011.

• Scalable Mechanisms for Rational Secret Sharing by Varsha Dani, Mahnush Movahedi, Yamel Rodriguez and Jared Saia, Principles of Distributed Computing (PODC), 2011.

• Fast Asynchronous Byzantine Agreement and Leader Election with Full Information by Bruce Kapron, David Kempe, Valerie King, Jared Saia and Vishal Sanwalani In ACM Transactions on Algorithms (TALG), 2010.

• Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary by Valerie King and Jared Saia, Principles of Distributed Computing (PODC), 2010. Best Paper Award. Slides.

• Scalable Byzantine Agreement by Valerie King and Jared Saia, SIGACT Distributed Computing Column 39, 2010.

• Load balanced Scalable Byzantine Agreement through Quorum Building, with Full Information by Valerie King, Steve Lonargan, Jared Saia and Amitabh Trehan, International Conference on Distributed Computing and Networking (ICDCN), 2010.

• A Note on Improving the Performance of Approximation Algorithms for Radiation Therapy by Therese Biedl, Shuang Luan, Stephane Durocher, Jared Saia, Holger H. Hoos, Maxwell Young, Information Processing Letters (IPL), 2010.

• Attack-Resistant Frequency Counting by Bo Wu, Valerie King and Jared Saia, IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2010.

• Finding Spread Blockers in Dynamic Networks by Habiba, Yintao Yu, Tanya Berger-Wolf and Jared Saia, SNAKDD 2008, LNCS 5498, pp. 55--76. Springer, Heidelberg (2010).

• An Empirical Study of a Scalable Byzantine Agreement Algorithm by Olumuyiwa Oluwasanmi, Valerie King and Jared Saia, Heterogeneity in Computing Workshop (HWC), 2010.

• From Almost Everywhere to Everwhere: Byzantine Agreement with soft-O(n^{3/2}) bits by Valerie King and Jared Saia, International Symposium on Distributed Computing (DISC) , 2009.

• The Forgiving Graph: A Distributed Data Structure for Low Stretch under Adversarial Attack by Tom Hayes, Jared Saia and Amitabh Trehan, Principles of Distributed Computing (PODC), 2009.

• On the Power of Mediators by Josep Diaz, Dieter Mitsche, Navin Rustagi and Jared Saia In Workshop on Internet and Network Economies (WINE), 2009.

• Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks by Valerie King, Cynthia Phillips, Jared Saia and Maxwell Young Principles of Distributed Computing (PODC), 2008.

• The Forgiving Tree: A Self-Healing Distributed Data Structure by Tom Hayes, Navin Rustagi, Jared Saia and Amitabh Trehan Principles of Distributed Computing (PODC), 2008.

• Picking up the Pieces: Self-Healing in Reconfigurable Networks by Jared Saia and Amitabh Trehan IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2008.

• Fast Asynchronous Byzantine Agreement and Leader Election with Full Information by Bruce Kapron, David Kempe, Valerie King, Jared Saia and Vishal Sanwalani Symposium on Discrete Algorithms (SODA), 2008 Invited submission to "Transactions on Algorithms" best papers of SODA 2008.

• Worm versus alert: Who wins in a battle for control of a large-scale network?" by James Aspnes, Navin Rustagi and Jared Saia Principles Of Distributed Systems (OPODIS), 2007.

• Towards Secure and Scalable Computation in Peer-to-peer Networks by Valerie King, Jared Saia, Visal Sanwalani and Erik Vee. Foundations of Computer Science (FOCS), 2006.

• Censorship Resistant Peer-to-peer Networks by Amos Fiat and Jared Saia. Journal of the Theory of Computing (TOC), 2007. Invited Issue of best papers from SODA 2002.

• Reducing Communication Costs in Robust Peer-to-Peer Networks" by Jared Saia and Maxwell Young Information Processing Letters (IPL), 2008.

• Approximation Algorithms for Minimizing Segments in Radiation Therapy by Shuang Luan, Jared Saia, and Maxwell Young. Information Processing Letters(IPL), 2006.

• Self-Healing Algorithms for Reconfigurable Networks by Iching Boman, Chaouki Abdallah, Edl Schamiloglu and Jared Saia. International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS), 2006.

• Nonnegative Integral Subset Representations of Integer Sets by Michael Collins, David Kempe, Jared Saia and Maxwell Young. Information Processing Letters (IPL) Vol 101 Issue 3, , 2007.

• Choosing a Random Peer in Chord by Valerie King, Scott Lewis, Jared Saia and Maxwell Young. Algorithmica,2006.

• A Framework for the Analysis of Dynamic Social Networks by Tanya Berger-Wolf and Jared Saia. Knowledge Discovery and Datamining (KDD), 2006.

• Scalable Leader Election by Valerie King, Jared Saia, Vishal Sanwalani and Erik Vee. Symposium on Discrete Algorithms (SODA), 2006. Corrigendum fixing a problem with load balancing in the original paper.

• Making Chord Robust to Byzantine Attacks by Amos Fiat, Jared Saia and Maxwell Young. European Symposium on Algorithms (ESA), 2005.

• A Computational Approach to Animal Breeding by Tanya Berger-Wolf, Cris Moore and Jared Saia, Conference on Computational and Mathematical Population Dynamics, 2004. Submitted by invitationJournal of Theoretical Biology, 2005.

• The Impact of Social Networks on Multi-Agent Recommender Systems by Hamilton Link, Terran Lane, Jared Saia, and Renard Laviolette, Proceedings of the PKDD- 2005 Workshop on Cooperative Multi-Agent Learning, 2005.

• Choosing a Random Peer by Valerie King and Jared Saia. In Principles of Distributed Computing (PODC), 2004.

• Discrete Sensor Placement Problems in Distribution Networks by Tanya Berger-Wolf, Bill Hart and Jared Saia. In SIAM Conference on Mathematics for Industry, 2004 and Journal of Mathematical and Computer Modeling, 2005.

• Scalable Byzantine Agreement by Scott Lewis and Jared Saia. In NIPS Workshop on Robust Communication Dynamics in Complex Networks, 2004.

• Dynamically Fault-Tolerant Content Addressable Networks by Jared Saia, Amos Fiat, Steve Gribble, Anna R. Karlin and Stefan Saroiu. First International Workshop on Peer-to-Peer Systems, 2002

• Censorship Resistant Peer-To-Peer Content Addressable Networks by Amos Fiat and Jared Saia. Symposium on Discrete Algorithms (SODA), 2002.

• On Algorithms for Efficient Data Migration by Joe Hall, Jason Hartline, Anna Karlin, Jared Saia and John Wilkes. Symposium on Discrete Algorithms, 2001.

• An Experimental Study of Data Migration Algorithms by Eric Anderson, Joe Hall, Jason Hartline, Michael Hobbes, Anna Karlin, Jared Saia, Ram Swaminathan and John Wilkes. Workshop on Algorithm Engineering, 2001. (Code used in paper)

• Spectral Analysis of Data by Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry and Jared Saia. Symposium on Theory of Computing (STOC), 2001.

• Online and Offline Preemptive Two-Machine Job Shop Scheduling by Tracy Kimbrel and Jared Saia. Journal of Scheduling, 2000.

Dissertation and Milestone Papers

• Algorithms for Managing Data in Distributed Systems by Jared Saia. Dissertation submitted to the University of Washington Computer Science and Engineering Department, 2002.

• Spectral Analysis for Information Retrieval and Data Mining by Jared Saia. Generals paper submitted to the University of Washington Computer Science and Engineering Department, 1999.