
Retracting Graphs to Cycles
S. Haney, M. Liaee, B. M. Maggs, D. Panigrahi, R. Rajaraman, and R. Sundaram
[To appear in]Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP)July2019

Foundations of Differentially Oblivious Algorithms
T.H. H. Chan, K.M. Chung, B. M. Maggs, and E. Shi
Proceedings of the 30th Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
January2019

Gearing up for the 21st century space race
D. Bhattacherjee, W. Aqeel, I. N. Bozkurt, A. Aquirre, B. Chandrasekaran, P. B. Godfrey, G. Laughlin, B. Maggs, and A. Singla
ACM Workshop on Hot Topics in Networks (HotNets)
November2018

Is the Web Ready for OCSP MustStaple?
T. Chung, J. Lok, B. Chandrasekaran, D. Choffnes, D. Levin, B. M. Maggs, A. Mislove, J. Rula, N. Sullivan, and C. Wilson
Proceedings of the ACM Internet Measurement Conference 2018 (IMC)
October2018

Redesigning CDNBroker Interactions for Improved Content Delivery
Winner of Best Paper Award
M. K. Mukerjee, I. N. Bozkurt, D. Ray, B. M. Maggs, S. Seshan, and H. Zhang
Proceedings of the 13th ACM International Conference on emerging Networking EXperiments and Technologies (CoNEXT)
December2017

Understanding the role of registrars in the DNSSEC deployment
Finalist for Best Paper Award
2019 IETF/IRTF Applied Networking Research Prize (ANRP)
T. Chung, R. v. RijswijkDeij, B. Chandrasekaran, D. Choffnes, D. Levin, B. M. Maggs, A. Mislove, and C. Wilson
Proceedings of the ACM Internet Measurement Conference 2017 (IMC)
October2017

Symmetric interdiction for matching problems
S. Haney, B. Maggs, B. Maiti, D. Panigrahi, R. Rajaraman, and R. Sundaram
Proceedings of the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
August2017

A Longitudinal, endtoend view of the DNSSEC ecosystem
Distinguished Paper Award
T. Chung, R. v. RijswijkDeij, B. Chandrasekaran, D. Choffnes, D. Levin, B. M. Maggs, A. Mislove, and C. Wilson
Proceedings of the 26th USENIX Security Symposium (USENIX Security)
August2017

CRLite: a scalable system for pushing all TLS revocations to all browsers
2017 IEEE Cybersecurity Innovation Award
J. Larisch, D. Choffnes, D. Levin, B. M. Maggs, A. Mislove, and C. Wilson
Proceedings of the 38th IEEE Symposium on Security and Privacy (Oakland)
May2017

Why is the Internet so slow?!
Best Dataset Award
I. Bozkurt, B. Chandrasekaran, A. Aguirre, P. Godfrey, G. Laughlin, B. Maggs, and A. Singla
Proceedings of the Passive and Active Measurement Conference 2017 (PAM)
March2017

Measuring and Applying Invalid SSL Certificates: The Silent Majority
T. Chung, Y. Liu, D. Choffnes, D. Levin, B. Maggs, A. Mislove, and C. Wilson
Proceedings of the ACM Internet Measurement Conference 2016 (IMC)
November2016

Measurement and Analysis of Private Key Sharing in the HTTPS Ecosystem
F. Cangialosi, T. Chung, D. Choffnes, D. Levin, B. Maggs, A. Mislove, and C. Wilson
Proceedings of the 23rd ACM Conference on Computer and Communications Security (CCS)
October2016

The Impact of Brokers on the Future of Content Delivery
M. K. Mukerjee, I. N. Bozkurt, B. Maggs, S. Seshan, and H. Zhang
ACM Workshop on Hot Topics in Networks (HotNets)
October2016

Reducing Latency Through Pageaware Management of Web Objects by Content Delivery Networks
S. P. Narayanan, Y. S. Nam, A. Sivakumar, B. Chandrasekaran, B. Maggs, and S. Rao
Proceedings of the ACM SIGMETRICS/IFIP Performance Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS)
June2016

An EndtoEnd Measurement of Certificate Revocation in the Web's PKI
Y. Liu, W. Tome, L. Zhang, D. Choffnes, D. Levin, B. Maggs, A. Mislove, A. Schulman, and C. Wilson
Proceedings of the ACM Internet Measurement Conference 2015 (IMC)
October2015

Backoffice Web traffic on the Internet
E. Pujol, P. Richter, B. Chandrasekaran, G. Smaragdakis, A. Feldmann, B. M. Maggs, and K. C. Ng
Proceedings of the ACM Internet Measurment Conference 2014 (IMC)
November2014

The Internet at the speed of light
A. Singla, B. Chandrasekaran, B. Godfrey, B. M. Maggs
Proceedings of the Thirteenth ACM Workshop on Hot Topics in Networks (HotNets)
October2014

Peerassisted content distribution in Akamai NetSession
M. Zhao, P. Aditya, A. Chen, Y. Lin, A. Haeberlen, P. Druschel, B. M. Maggs, B. Wishon, and M. Ponec
Proceedings of the Internet Measurement Conference 2013 (IMC)
October2013

Less pain, most of the gain: incrementally deployable ICN
S. K. Fayazbakhsh, Y. Lin, A. Tootoonchian, A. Ghodsi, T. Koponen, B. M. Maggs, K. C. Ng, V. Sekar, and S. Shenker
Proceedings of the ACM SIGCOMM 2013 Conference (SIGCOMM)
August2013

Reliable client accounting for P2Pinfrastructure hybrids
P. Aditya, M. Zhao, Y. Lin, A. Haeberlen, P. Druschel, B. M. Maggs, and B. Wishon
Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI)
April2012

Cutting the electrical bill for Internetscale systems
A. Qureshi, R. Weber, H. Balakrishnan, J. Guttag, and B. M. Maggs
Proceedings of the ACM SIGCOMM 2009 Conference (SIGCOMM)
August2009

Holistic query transformations for dynamic Web applications
A. Manji, C. Garrod, B. M. Maggs, T. C. Mowry, and A. Tomasic
Proceedings of the 2009 IEEE 25th International Conference on Data Engineering (ICDE)
April2009

Holistic application analysis for updateindependence
C. Garrod, A. Manji, B. Maggs, T. Mowry, and A. Tomasic
Proceedings of the Second IEEE Workshop on Hot Topics in Web Systems and Technologies (HotWeb 2008), pp. 1–6
October2008

Scalable query result caching for Web applications
C. Garrod, A. Manji, A. Ailamaki, B. Maggs, T. Mowry, C. Olson, and A. Tomasic
Proceedings of the 34th International Conference on Very Large Databases (VLDB)
August2008

On the impact of route monitor selection
Y. Zhang, Z. Zhang, Z. M. Mao, Y. C. Hu, and B. M. Maggs
Proceedings of the Internet Measurement Conference 2007 (IMC)
October2007

Portcullis: Protecting connection setup from denialofcapability attacks
B. Parno, D. Wendlandt, E. Shi, A. Perrig, B. Maggs, and Y.C. Hu
Proceedings of the ACM SIGCOMM 2007 Conference (SIGCOMM)
August2007

RBGP: Staying connected in a connected world
N. Kushman, S. Kandula, D. Katabi, and B. M. Maggs
Proceedings of the 4th USENIX Symposium on Networked Systems Design & Implementation (NSDI)
April2007

Invalidation clues for database scalability services
A. Manjhi, P. B. Gibbons, A. Ailamaki, B. M. Maggs, T. C. Mowry, C. Olston, A. Tomasic, and H. Yu
Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering (ICDE)
April2007

Quorum placement in networks: Minimizing network congestion
D. Golovin, A. Gupta, B. Maggs, F. Oprea, and M. Reiter
Proceedings of the 18th Annual ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC)
July2006

Simultaneous scalability and security for dataintensive Web applications
A. Manjhi, A. Ailamaki, B. M. Maggs, T. C. Mowry, C. Olston, and A. Tomasic
Proceedings of ACM SIGMOD 2006 (SIGMOD)
June2006

Finding effective supporttree preconditioners
B. M. Maggs, G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo
Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)
July2005

Quorum placement in networks to minimize access delays
A. Gupta, B. Maggs, F. Oprea, and M. Reiter
Proceedings of the 17th Annual ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC)
July2005

A Scalability service for dynamic Web applications
C. Olston, A. Manjhi, C. Garrod, A. Ailamaki, B. M. Maggs, and T. C. Mowry
Proceedings of the 2nd Biennial Conference on Innovative Data Systems Research (CIDR)
January2005

On Hierarchical Routing in Doubling Metrics
H. TH. Chan, A. Gupta, B. M. Maggs, and S. Zhou
Proceedings of the 16th Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
January2005

A Methodology for Estimating Interdomain Web Traffic Demand
A. Feldmann, N. Kammenhuber, O. Maennel, B. Maggs, R. De Prisco, and R. Sundaram
Proceedings of the Internet Measurement Conference 2004 (IMC)
October2004

An Analysis of Live Streaming Workloads on the Internet
K. Sripanidkulchai, B. Maggs, and H. Zhang
Proceedings of the Internet Measurement Conference 2004 (IMC)
October2004

Availability, Usage, and Deployment Characteristics of the Domain Name System
J. Pang, J. Hendricks, A. Akella, R. De Prisco, B. Maggs, and S. Seshan
Proceedings of the Internet Measurement Conference 2004 (IMC)
October2004

Simultaneous Source Location
K. Andreev, C. Garrod, B. Maggs, and A. Meyerson
Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
August2004

Locating Internet Routing Instabilities
A. Feldmann, O. Maennel, Z. Morley Mao, A. Berger, and B. Maggs
Proceedings of the ACM SIGCOMM 2004 Conference (SIGCOMM)
August2004

A Comparison of Overlay Routing and Multihoming Route Control
A. Akella, J. Pang, A. Shaikh, B. Maggs, and S. Seshan
Proceedings of the ACM SIGCOMM 2004 Conference (SIGCOMM)
August2004

The Feasibility of Supporting LargeScale Live Streaming Applications with Dynamic Application EndPoints
K. Sripanidkulchai, A. Ganjam, B. Maggs, and H. Zhang
Proceedings of the ACM SIGCOMM 2004 Conference (SIGCOMM)
August2004

A MeasurementBased Analysis of Multihoming
A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman
Proceedings of the ACM SIGCOMM 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM)
August2003
Appeared as —
On the Performance Benefits of Multihoming Route Control
A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman
IEEE/ACM Transactions on Networking, Vol. 16, No. 1, pp. 91–104
February2008

Designing Overlay Multicast Networks for Streaming
K. Andreev, B. M. Maggs, A. Meyerson, and R. Sitaraman
ACM Symposium on Parallel Algorithms and Architectures (SPAA)
June2003

Efficient content location using interestbased locality in peertopeer systems
K. Sripanidkulchai, B. Maggs, and H. Zhang
Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03)
April2003

Spaceefficient finger search on degreebalanced search trees
G. E. Blelloch, B. M. Maggs, and S. L. M. Woo
Proceedings of the 14th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 374–383
January2003

Tradeoffs between parallelism and fill in nested dissection
C. F. Bornstein, B. M. Maggs, and G. L. Miller
Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 191–200
June1999

Protocols for Asymmetric Communication Channels
M. Adler and B. M. Maggs
Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 522–533
October1998
Appeared as —
Protocols for Asymmetric Communication Channels
M. Adler and B. M. Maggs
Journal of Computer and Systems Sciences, Vol. 63, No. 4, pp. 573–596
December2001

On Balls and Bins with Deletions
R. Cole, A. Frieze, B. M. Maggs, M. Mitzenmacher, A. W. Richa, R. K. Sitaraman, and E. Upfal
Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pp. 145–158
October1998

Randomized protocols for lowcongestion circuit routing in multistage interconnection networks
R. Cole, B. M. Maggs, F. Meyer auf der Heide, M. Mitzenmacher, A. W. Richa, K. Schroeder, R. K. Sitaraman, and B. Voecking
Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pp. 378–388
May1998

On the bisection width and expansion of butterfly networks
C. F. Bornstein, A. Litman, B. M. Maggs, R. K. Sitaraman, and T. Yatzkar
Proceedings of the 12th International Parallel Processing Symposium (IPPS), pp. 144–150
March1998
Appeared as —
On the bisection width and expansion of butterfly networks
C. F. Bornstein, A. Litman, B. M. Maggs, R. K. Sitaraman, and T. Yatzkar
Theory of Computing Systems, Vol. 34, No. 6, pp. 491–518
November2001

Parallel Gaussian elimination with linear work and fill
C. Bornstein, B. Maggs, G. Miller, and R. Ravi
Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 274–283
October1997

Exploiting locality for data management in systems of limited bandwidth
B. M. Maggs, F. Meyer auf der Heide, B. Voecking, and M. Westermann
Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 284–293
October1997

Improved routing and sorting on multibutterflies
B. M. Maggs and B. Voecking
Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC), pp. 517–530
May1997
Appeared as —
Improved routing and sorting on multibutterflies
B. M. Maggs and B. Voecking
Algorithmica, Vol. 28, No. 4, 2000, pp. 438–464
December2000

On the benefit of supporting virtual channels in wormhole routers
R. J. Cole, B. M. Maggs, and R. K. Sitaraman
Proceedings of the 8th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 131–141
June1996
Appeared as —
On the benefit of supporting virtual channels in wormhole routers
R. J. Cole, B. M. Maggs, and R. K. Sitaraman
Journal of Computer and System Sciences, Vol. 62, No. 1, pp. 152–177
February2001

Routing on butterfly networks with random faults
R. Cole, B. Maggs, and R. Sitaraman
Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 558–570
October1995

Tight analyses of two local load balancing algorithms
B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. Zuckerman
Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (STOC), pp. 548–558
May1995

Fast algorithms for finding O(congestion+dilation) packet routing schedules
T. Leighton and B. Maggs
Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS), Volume 2, pp. 555–563
January1995
Appeared as —
Fast algorithms for finding O(congestion+dilation) packet routing schedules (with minor corrections)
F. T. Leighton, B. M. Maggs and A. W. Richa
Combinatorica, Vol. 19, No. 3, pp. 375–401
1999

An algorithm for finding predecessors in integer sets
B. Maggs and M. Rauch
Proceedings of the 3rd Workshop on Algorithms and Data Structures (WADS), Vol. 709 of Lecture Notes in Computer Science, SpringVerlag, pp. 483–493
August1993

Multiscale emulation: A technique for reconfiguring arrays with faults
R. Cole, B. Maggs, and R. Sitaraman
Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC), pp. 561–572
May1993
Appeared as —
Reconfiguring arrays with faults part I: worstcase faults
R. J. Cole, B. M. Maggs, and R. K. Sitaraman
SIAM Journal on Computing, Vol. 26, No. 6, pp. 1581–1611
December1997

Approximate load balancing on dynamic and asynchronous networks
W. Aiello, B. Awerbuch, B. Maggs, and S. Rao
Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC), pp. 632–641
May1993

Sortingbased selection algorithms for hypercubic networks
P. Berthome, A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton
Proceedings of the 7th International Parallel Processing Symposium (IPPS), pp. 89–95
April1993
Appeared as —
Sortingbased selection algorithms for hypercubic networks
P. Berthome, A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton
Algorithmica, Vol. 26, No. 2, pp. 237–254
2000

On the fault tolerance of some popular boundeddegree networks
T. Leighton, B. Maggs, and R. Sitaraman
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 542–552
October1992
Appeared as —
A Formal Study on the Fault Tolerance of Parallel and Distributed Systems
C. V. Papadopoulos
IEEE Conference on Architectures and Algorithms for Parallel Processing (ICAAAPP)
April1995

Stereo without disparity gradient smoothing: a Bayesian sensor fusion solution
I. J. Cox, S. L. Hingorani, B. M. Maggs, S. B. Rao
D. Hogg and R. Boyle, ed., Proceedings of the British Machine Vision Conference, SpringerVerlag, pp. 337346
September1992

Simple algorithms for routing on butterfly networks with bounded queues
B. M. Maggs and R. K. Sitaraman
Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (STOC), pp. 150–161
May1992

A comparison of sorting algorithms for the Connection Machine CM2
G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. Smith, and M. Zagha
Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 3–16
July1991
Appeared as —
An experimental analysis of parallel sorting algorithms
G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. Smith, and M. Zagha
Theory of Computing Systems, Vol. 31, No. 2, pp. 135–167
March/April1998

Empirical evaluation of randomlywired multistage networks
D. Lisinski, T. Leighton, and B. Maggs
Proceedings of the 1990 International Conference on Computer Design (ICCD), pp. 380–385
September1990

Fast algorithms for bitserial routing on a hypercube
B. Aiello, T. Leighton, B. Maggs and M. Newman
Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 55–64
July1990
Appeared as —
Fast algorithms for bitserial routing on a hypercube
B. Aiello, T. Leighton, B. Maggs and M. Newman
Mathematical Systems Theory, Vol. 24
1991

Online algorithms for path selection in a nonblocking network
S. Arora, F. T. Leighton and B. M. Maggs
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 149–158
May1990
Appeared as —
Online algorithms for path selection in a nonblocking network
S. Arora, F. T. Leighton and B. M. Maggs
SIAM Journal on Computing, Vol. 25, No. 3, pp. 600–625
June1996

Expanders might be practical: fast algorithms for routing around faults on multibutterflies
T. Leighton and B. Maggs
Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 384–389
October1989
Appeared as —
Fast algorithms for routing around faults in multibutterflies and randomlywired splitter networks
T. Leighton and B. Maggs
IEEE Transactions on Computers, Vol. 41, No. 5
May1992

Workpreserving emulations of fixedconnection networks
R. Koch, T. Leighton, B. Maggs, S. Rao, and A. Rosenberg
Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 227–240
May1989
Appeared as —
Workpreserving emulations of fixedconnection networks
R. R. Koch, F. T. Leighton, B. M. Maggs, S. B. Rao, A. L. Rosenberg, and E. J. Schwabe
Journal of the ACM, Vol. 44, No. 1, pp. 104–147
January1997

Universal packet routing algorithms
T. Leighton, B. Maggs, and S. Rao
Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS), pp. 256–271
October1988
Appeared as —
Packet routing and jobshop scheduling in O(congestion+dilation) steps
T. Leighton, B. Maggs, and S. Rao
Combinatorica, Vol. 14, No. 2
1994
Appeared as —
Randomized routing and sorting on fixedconnection networks
F. T. Leighton, B. M. Maggs, S. B. Rao, and A. G. Ranade
Journal of Algorithms, Vol. 17, No. 1
July1994

Communicationefficient parallel graph algorithms
Daniel L. Slotnick Award for Most Original Paper
C. E. Leiserson and B. M. Maggs
Proceedings of the 1986 International Conference on Parallel Processing (ICPP), pp. 861–868
August1986
Appeared as —
Communicationefficient parallel graph algorithms for distributed randomaccess machines
C. E. Leiserson and B. M. Maggs
Algorithmica, Vol. 3
1988