Selected Publications

Conference and Journal Papers

• Byzantine Agreement in Expected Polynomial Time by Valerie King and Jared Saia, Journal of the ACM(JACM), 2016.

• 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.

• (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 ( pdf).

• "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. ( pdf).

• "Byzantine Agreement in Polynomial Expected Time" by Valerie King and Jared Saia, Symposium on Theory of Computing (STOC), 2013 ( pdf). 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. ( pdf).

• "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. ( pdf).

• "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. ( pdf).

• ``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. ( pdf).

• ``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. ( pdf).

• ``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. ( pdf).

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

• ``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. ( pdf).

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

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

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

• "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 ( pdf)

• ``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. ( pdf). Slides. Best Paper Award Winner

• ``Scalable Byzantine Agreement'' by Valerie King and Jared Saia, SIGACT Distributed Computing Column 39, 2010. (link).

• ``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. ( pdf).

• ``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. ( pdf).

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

• ``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) ( pdf)

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

• "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. ( pdf)

• "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. ( pdf)

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

• "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. ( pdf)

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

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

• "Fast Asynchronous Byzantine Agreement and Leader Election with Full Information" by Bruce Kapron, David Kempe, Valerie King, Jared Saia and Vishal Sanwalani In Symposium on Discrete Algorithms (SODA), 2008 ( pdf) 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 In International Conference on Principles Of Distributed Systems (OPODIS), 2007. Lecture Notes in Computer Science volume 4878. Springer-Verlag, December 2007, pp. 443-456 ( pdf )

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

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

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

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

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

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

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

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

• "Scalable Leader Election" by Valerie King, Jared Saia, Vishal Sanwalani and Erik Vee. In Symposium on Discrete Algorithms (SODA), 2006 ( pdf)

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

• "A Computational Approach to Animal Breeding" by Tanya Berger-Wolf, Cris Moore and Jared Saia ( pdf). In Conference on Computational and Mathematical Population Dynamics, 2004. Submitted by invitation and appearing in Journal of Theoretical Biology, 2005.

• "The Impact of Social Networks on Multi-Agent Recommender Systems," by Link, H., Saia, J., Lane, T., and Laviolette, R. In Proceedings of the PKDD- 2005 Workshop on Cooperative Multi-Agent Learning, 2005. ( pdf)

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

• "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 (pdf).

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

• "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. ( ps , pdf).

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

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

• "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. ( ps , pdf).
  (Java Code used for the experiments in this paper.)

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

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

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. ( ps ).

• "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. ( ps , pdf).