Selected Publications

Conference and Journal Papers

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

• "Towards Provably-Secure Scalable Anonymous Broadcast" by Mahdi Zamani, Jared Saia, Mahnush Movahedi, and Joud Khoury in 3rd USENIX Workshop on Free and Open Communications on the Internet (FOCI'13) , 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)

• "Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation" by Varsha Dani, Valerie King, Mahnush Movahedi and Jared Saia, Under Submission. ( 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).

• "Self-Healing of Byzantine Faults" by Jeffrey Knockel, George Saad and Jared Saia, Under submission. 2012. ( 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).

• ``Three Researchers, Five Conjectures'' by Jeffrey Knockel, Jed Crandall and Jared Saia in 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 to appear in Journal of the ACM(JACM), 2011. ( pdf).

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

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

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

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

• ``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 In the International Conference on Distributed Computing and Networking, 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 In 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 in 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)

• "Fast, scalable Byzantine agreement in the full information model with a Nonadaptive adversary" 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, Cahoki 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).