Valerie King

Theor. Comput. Sci., October, 2023

Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time.

[BibT_eX]

[DOI]

Alex Thomo

Quinton Yong

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

2022

Bankrupting DoS Attackers Despite Uncertainty.

[BibT_eX]

[DOI]

CoRR, 2022

2021

Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model.

[BibT_eX]

[DOI]

Distributed Comput., 2021

2020

Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT.

[BibT_eX]

[DOI]

Omer Wasim

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

2019

Faster asynchronous MST and low diameter tree construction with sublinear communication.

[BibT_eX]

[DOI]

CoRR, 2019

Scalable and Secure Computation Among Strangers: Resource-Competitive Byzantine Protocols.

[BibT_eX]

[DOI]

CoRR, 2019

Kinetic k-Semi-Yao graph and its applications.

[BibT_eX]

[DOI]

Comput. Geom., 2019

Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

A resource-competitive jamming defense.

[BibT_eX]

[DOI]

Distributed Comput., 2018

Communication-efficient randomized consensus.

[BibT_eX]

[DOI]

Distributed Comput., 2018

Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016.

[BibT_eX]

[DOI]

CoRR, 2018

A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in O͠(n3/2) Rounds.

[BibT_eX]

[DOI]

CoRR, 2018

A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

2017

Secure multi-party computation in large networks.

[BibT_eX]

[DOI]

Distributed Comput., 2017

Time-communication trade-offs for minimum spanning tree construction.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Distributed Computing and Networking, 2017

2016

Fully Dynamic Transitive Closure.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Fully Dynamic Connectivity.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Byzantine Agreement in Expected Polynomial Time.

[BibT_eX]

[DOI]

J. ACM, 2016

Simultaneous Secrecy and Reliability Amplification for a General Channel Model.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2016

Stability of certainty and opinion in influence networks.

[BibT_eX]

[DOI]

Ariel Webster

Bruce M. Kapron

Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2016

2015

Dynamic graph connectivity with improved worst case update time and sublinear space.

[BibT_eX]

[DOI]

CoRR, 2015

A simple, faster method for kinetic proximity problems.

[BibT_eX]

[DOI]

Comput. Geom., 2015

Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication.

[BibT_eX]

[DOI]

Shay Kutten

Mikkel Thorup

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

2014

Kinetic $k$-Semi-Yao Graph and its Applications.

[BibT_eX]

[DOI]

CoRR, 2014

(Near) optimal resource-competitive broadcast with jamming.

[BibT_eX]

[DOI]

Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

Faster Agreement via a Spectral Method for Detecting Malicious Behavior.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

(Reverse) k-nearest neighbors for moving objects.

[BibT_eX]

[DOI]

Proceedings of the Seventh International Conference on Motion in Games, Playa Vista, CA, USA, November 06, 2014

Kinetic Reverse k-Nearest Neighbor Problem.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 25th International Workshop, 2014

Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing and Networking - 15th International Conference, 2014

Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d.

[BibT_eX]

[DOI]

Proceedings of the 26th Canadian Conference on Computational Geometry, 2014

2013

Byzantine agreement in polynomial expected time: [extended abstract].

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Dynamic graph connectivity in polylogarithmic worst case time.

[BibT_eX]

[DOI]

Bruce M. Kapron

Ben Mountjoy

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Brief announcement: byzantine agreement with a strong adversary in polynomial expected time.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

Kinetic data structures for all nearest neighbors and closest pair in the plane.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Computational Geometry 2013, 2013

2012

Predicting missing contacts in mobile social networks.

[BibT_eX]

[DOI]

Pervasive Mob. Comput., 2012

Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary

[BibT_eX]

[DOI]

CoRR, 2012

Resource-Competitive Communication

[BibT_eX]

[DOI]

Maxwell Young

CoRR, 2012

They Know Where You Live!

[BibT_eX]

[DOI]

CoRR, 2012

Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Kinetic and Stationary Point-Set Embeddability for Plane Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing - 20th International Symposium, 2012

Resource-competitive analysis: a new perspective on attack-resistant distributed computing.

[BibT_eX]

[DOI]

Proceedings of the FOMC'12, 2012

2011

Breaking the O(n2) bit barrier: Scalable byzantine agreement with an adaptive adversary.

[BibT_eX]

[DOI]

J. ACM, 2011

The evolution of friendships in Chinese online social networks.

[BibT_eX]

[DOI]

Louis Lei Yu

Int. J. Soc. Comput. Cyber Phys. Syst., 2011

Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks.

[BibT_eX]

[DOI]

Algorithmica, 2011

Empirical Comparison of Information Spreading Algorithms in the Presence of 1-Whiskers.

[BibT_eX]

[DOI]

Proceedings of the PASSAT/SocialCom 2011, Privacy, 2011

Conflict on a communication channel.

[BibT_eX]

[DOI]

Maxwell Young

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing and Networking - 12th International Conference, 2011

2010

Fast asynchronous Byzantine agreement and leader election with full information.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Scalable byzantine computation.

[BibT_eX]

[DOI]

SIGACT News, 2010

Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary

[BibT_eX]

[DOI]

CoRR, 2010

The Evolution of Friendships in Chinese Online Social Networks.

[BibT_eX]

[DOI]

Louis Yu

Proceedings of the 2010 IEEE Second International Conference on Social Computing, 2010

Social-Greedy: a socially-based greedy routing algorithm for delay tolerant networks.

[BibT_eX]

[DOI]

Proceedings of the Second International Workshop on Mobile Opportunistic Networking, 2010

Attack-resistant frequency counting.

[BibT_eX]

[DOI]

Bo Wu

Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing, 2010

An empirical study of a scalable Byzantine agreement algorithm.

[BibT_eX]

[DOI]

Olumuyiwa Oluwasanmi

Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing, 2010

Human Contact Prediction Using Contact Graph Inference.

[BibT_eX]

[DOI]

Proceedings of the 2010 IEEE/ACM Int'l Conference on Green Computing and Communications, 2010

2009

From Almost Everywhere to Everywhere: Byzantine Agreement with Õ(n3/2) Bits.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

Guanxi in the Chinese Web.

[BibT_eX]

[DOI]

Louis Yu

Yan Zhuang

Proceedings of the 12th IEEE International Conference on Computational Science and Engineering, 2009

2008

Fully Dynamic Transitive Closure.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Fully Dynamic Connectivity.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower bound for scalable Byzantine Agreement.

[BibT_eX]

[DOI]

Dan Holtby

Bruce M. Kapron

Distributed Comput., 2008

Guanxi in the chinese web - a study of mutual linking.

[BibT_eX]

[DOI]

Louis Lei Yu

Yan Zhuang

Proceedings of the 17th International Conference on World Wide Web, 2008

Scalable Ubiquitous Data Access in Clustered Sensor Networks.

[BibT_eX]

[DOI]

Proceedings of the Scientific and Statistical Database Management, 2008

2007

Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks

[BibT_eX]

[DOI]

CoRR, 2007

Choosing a Random Peer in Chord.

[BibT_eX]

[DOI]

Algorithmica, 2007

2006

Scalable leader election.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Towards Secure and Scalable Computation in Peer-to-Peer Networks.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Randomized Coverage-Preserving Scheduling Schemes for Wireless Sensor Networks.

[BibT_eX]

[DOI]

Chong Liu

Kui Wu

Proceedings of the NETWORKING 2005: Networking Technologies, 2005

Very low cost sensor localization for hostile environments.

[BibT_eX]

[DOI]

Kui Wu

Chong Liu

Proceedings of IEEE International Conference on Communications, 2005

2004

Choosing a random peer.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Utilizing the Uncertainty of Intrusion Detection to Strengthen Security for Ad Hoc Networks.

[BibT_eX]

[DOI]

Proceedings of the Ad-Hoc, Mobile, and Wireless Networks: Third International Conference, 2004

Connectivity of Wireless Sensor Networks with Constant Density.

[BibT_eX]

[DOI]

Sarah Carruthers

Proceedings of the Ad-Hoc, Mobile, and Wireless Networks: Third International Conference, 2004

2003

On the complexity of distance-based evolutionary tree reconstruction.

[BibT_eX]

[DOI]

Li Zhang

Yunhong Zhou

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002

A Fully Dynamic Algorithm for Maintaining the Transitive Closure.

[BibT_eX]

[DOI]

Garry Sagert

J. Comput. Syst. Sci., 2002

2001

Maintaining Minimum Spanning Forests in Dynamic Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

On the Complexity of Parity Word Automata.

[BibT_eX]

[DOI]

Orna Kupferman

Moshe Y. Vardi

Proceedings of the Foundations of Software Science and Computation Structures, 2001

A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms.

[BibT_eX]

[DOI]

Mikkel Thorup

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

1999

Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.

[BibT_eX]

[DOI]

J. ACM, 1999

Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.

[BibT_eX]

[DOI]

Tandy J. Warnow

Algorithmica, 1999

Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1997

An Optimal EREW PRAM Algorithm for Minimum Spanning Tree Verification.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

A Simpler Minimum Spanning Tree Verification Algorithm.

[BibT_eX]

[DOI]

Algorithmica, 1997

Maintaining Minimum Spanning Trees in Dynamic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996

Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

1995

Randomized dynamic graph algorithms with polylogarithmic time per operation.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Fully Dynamic Biconnectivity and Transitive Closure.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

On Boolean Decision Trees with Faulty Nodes.

[BibT_eX]

[DOI]

Claire Kenyon

Random Struct. Algorithms, 1994

A Faster Deterministic Maximum Flow Algorithm.

[BibT_eX]

[DOI]

S. Rao

Robert Endre Tarjan

J. Algorithms, 1994

1993

Optimal Randomized Algorithms for Local Sorting and Set-Maxima.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

1991

An Omega(n5/4) lower bound on the randomized complexity of graph properties.

[BibT_eX]

[DOI]

Comb., 1991

1990

A lower bound for the recognition of digraph properties.

[BibT_eX]

[DOI]

Comb., 1990

Optimal Randomized Algorithms for Local Sorting and Set-Maxima

[BibT_eX]

[DOI]

Wayne Goddard

Leonard J. Schulman

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

1989

Verifying Partial Orders

[BibT_eX]

[DOI]

Claire Kenyon-Mathieu

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Managing the VLSI Design Process.

[BibT_eX]

[DOI]

Tzi-cker Chiueh

Randy H. Katz

Proceedings of the Computer-Aided Cooperative Product Development, MIT-JSME Workshop, 1989

1988

Lower Bounds on the Complexity of Graph Properties

[BibT_eX]

[DOI]