Michael Dinitz

Shi Li

CoRR, 2023

Improved Approximations for Relative Survivable Network Design.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Smoothed Analysis of Information Spreading in Dynamic Networks.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Partially Optimal Edge Fault-Tolerant Spanners.

[BibT_eX]

[DOI]

Caleb Robelle

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Algorithms with Prediction Portfolios.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Vertex Fault-Tolerant Emulators.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Relative Survivable Network Design.

[BibT_eX]

[DOI]

Ama Koranteng

Proceedings of the Approximation, 2022

Fair Disaster Containment via Graph-Cut Problems.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Fair Disaster Containment via Graph-Cut Problems.

[BibT_eX]

[DOI]

CoRR, 2021

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time.

[BibT_eX]

[DOI]

Caleb Robelle

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Faster Matchings via Learned Duals.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Approximate Moore Graphs are good expanders.

[BibT_eX]

[DOI]

Gal Shahaf

J. Comb. Theory, Ser. B, 2020

Lasserre Integrality Gaps for Graph Spanners and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 18th International Workshop, 2020

Efficient and Simple Algorithms for Fault-Tolerant Spanners.

[BibT_eX]

[DOI]

Caleb Robelle

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks.

[BibT_eX]

[DOI]

Benjamin Moseley

Proceedings of the 39th IEEE Conference on Computer Communications, 2020

2019

Brief Announcement: Massively Parallel Approximate Distance Sketches.

[BibT_eX]

[DOI]

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

The Capacity of Smartphone Peer-To-Peer Networks.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

Calvin Newport

Alex Weaver

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

Distributed Minimum Degree Spanning Trees.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

Taisuke Izumi

Calvin Newport

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

Massively Parallel Approximate Distance Sketches.

[BibT_eX]

[DOI]

Proceedings of the 23rd International Conference on Principles of Distributed Systems, 2019

The Norms of Graph Spanners.

[BibT_eX]

[DOI]

Thomas Robinson

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Approximating the Norms of Graph Spanners.

[BibT_eX]

[DOI]

Thomas Robinson

Proceedings of the Approximation, 2019

Reception Capacity: Definitions, Game Theory and Hardness.

[BibT_eX]

[DOI]

Naomi Ephraim

Proceedings of the Algorithms for Sensor Systems, 2019

2018

The Densest k-Subhypergraph Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Smoothed analysis of dynamic networks.

[BibT_eX]

[DOI]

Distributed Comput., 2018

Distributed Approximate Distance Oracles.

[BibT_eX]

[DOI]

CoRR, 2018

Distributed Algorithms for Minimum Degree Spanning Trees.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

Calvin Newport

CoRR, 2018

Optimal Vertex Fault Tolerant Spanners (for fixed stretch).

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Merav Parter

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Policy Regret in Repeated Games.

[BibT_eX]

[DOI]

Raman Arora

Teodor Vanislavov Marinov

Mehryar Mohri

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Brief Announcement: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network.

[BibT_eX]

[DOI]

Amy Babay

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network.

[BibT_eX]

[DOI]

Amy Babay

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

Large Low-Diameter Graphs are Good Expanders.

[BibT_eX]

[DOI]

Gal Shahaf

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Improved Approximation Algorithm for Steiner <i>k</i>-Forest with Nearly Uniform Weights.

[BibT_eX]

[DOI]

Zeev Nutov

ACM Trans. Algorithms, 2017

Approximating k-spanners in the LOCAL model.

[BibT_eX]

[DOI]

CoRR, 2017

Multicast Capacity Through Perfect Domination.

[BibT_eX]

[DOI]

Naomi Ephraim

CoRR, 2017

Explicit Expanding Expanders.

[BibT_eX]

[DOI]

Asaf Valadarsky

Algorithmica, 2017

Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion.

[BibT_eX]

[DOI]

Yury Makarychev

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Distributed Distance-Bounded Network Design Through Distributed Convex Programming.

[BibT_eX]

[DOI]

Proceedings of the 21st International Conference on Principles of Distributed Systems, 2017

Approximating Approximate Distance Oracles.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Load balancing with bounded convergence in dynamic networks.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE Conference on Computer Communications, 2017

Timely, Reliable, and Cost-Effective Internet Transport Service Using Dissemination Graphs.

[BibT_eX]

[DOI]

Proceedings of the 37th IEEE International Conference on Distributed Computing Systems, 2017

2016

Lowest-Degree k-Spanner: Approximation and Hardness.

[BibT_eX]

[DOI]

Theory Comput., 2016

Label Cover Instances with Large Girth and the Hardness of Approximating Basic <i>k</i>-Spanner.

[BibT_eX]

[DOI]

Ran Raz

ACM Trans. Algorithms, 2016

Approximating Low-Stretch Spanners.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Xpander: Towards Optimal-Performance Datacenters.

[BibT_eX]

[DOI]

Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies, 2016

Computing Approximate PSD Factorizations.

[BibT_eX]

[DOI]

Amitabh Basu

Xin Li

Proceedings of the Approximation, 2016

2015

Introduction to the Special Issue on SPAA 2013.

[BibT_eX]

[DOI]

Torsten Hoefler

ACM Trans. Parallel Comput., 2015

Efficient distributed computation of distance sketches in networks.

[BibT_eX]

[DOI]

Atish Das Sarma

Gopal Pandurangan

Distributed Comput., 2015

Xpander: Unveiling the Secrets of High-Performance Datacenters.

[BibT_eX]

[DOI]

Asaf Valadarsky

Proceedings of the 14th ACM Workshop on Hot Topics in Networks, Philadelphia, PA, USA, November 16, 2015

Towards Resistance Sparsifiers.

[BibT_eX]

[DOI]

Tal Wagner

Proceedings of the Approximation, 2015

2014

Matroid Secretary for Regular and Decomposable Matroids.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights.

[BibT_eX]

[DOI]

Zeev Nutov

Proceedings of the Approximation, 2014

2013

Recent advances on the matroid secretary problem.

[BibT_eX]

[DOI]

SIGACT News, 2013

Braess's Paradox in Wireless Networks: The Danger of Improved Technology.

[BibT_eX]

[DOI]

Merav Parter

Proceedings of the Distributed Computing - 27th International Symposium, 2013

Packing Interdiction and Partial Covering Problems.

[BibT_eX]

[DOI]

Anupam Gupta

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

2012

Efficient computation of distance sketches in distributed networks.

[BibT_eX]

[DOI]

Atish Das Sarma

Gopal Pandurangan

Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012

Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.

[BibT_eX]

[DOI]

Ran Raz

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Everywhere-Sparse Spanners via Dense Subgraphs.

[BibT_eX]

[DOI]

Eden Chlamtac

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

iBGP and Constrained Connectivity.

[BibT_eX]

[DOI]

Gordon T. Wilfong

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Directed spanners via flow-based linear programs.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Fault-tolerant spanners: better and simpler.

[BibT_eX]

[DOI]

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

2010

Algorithms and Models for Problems in Networking.

[BibT_eX]

[DOI]

PhD thesis, 2010

Graphical representations of clutters.

[BibT_eX]

Ars Comb., 2010

Distributed Algorithms for Approximating Wireless Network Capacity.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2010. 29th IEEE International Conference on Computer Communications, 2010

2009

Secretary problems: weights and discounts.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Brief announcement: distributed algorithms for approximating wireless network capacity.

[BibT_eX]

[DOI]

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

Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model: Complexity and Game Theory.

[BibT_eX]

[DOI]

Matthew Andrews

Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

2008

Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 22nd International Symposium, 2008

Online and dynamic embeddings of approximate ultrametrics.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

2007

Compact routing with slack.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

2006

Full Rank Tilings of Finite Abelian Groups.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2006

Spanners with Slack.

[BibT_eX]

[DOI]

T.-H. Hubert Chan