Invited Speaker


Dr. Blair D. Sullivan (NC State University, USA)
Saturday, Dec 15 from 9:00am-10:00am

Title: Bringing Structure to Network Science: Sparsity and Rounding

Abstract: The field of network science has burgeoned in the last two decades, developing new methods for analyzing complex network data of ever-increasing scale. Surprisingly, few tools from structural graph theory – an area rich with efficient algorithms – have been assimilated. In part, this is due to the theoretical nature of the related literature, and a lack of cross-pollination of the research communities. This talk will give a brief survey of structural graph algorithms, and discuss two recent approaches to incorporating them in real-world network analysis.

The relevant methodology is centered around parameterized algorithms and complexity, which offer a framework for solving many NP-hard problems in polynomial time when some parameter of the instance is bounded. Often, the parameter measures some structural feature of a network, and one major challenge has been to identify structure that is both realistic and algorithmically useful. We first describe results showing that bounded expansion, a notion of structural sparsity introduced by Neˇsetˇril and Ossona de Mendez in 2009, offers a auspicious solution to this problem. Random graph models designed to mimic real-world networks produce bounded expansion classes with high probability, theoretically efficient algorithms are known for many NP-hard problems, and careful algorithm engineering can result in practical implementations. Our second approach is complementary, and based on two fundamental observations: many network analysis tasks don’t require exact solutions, and real-world data is noisy. We describe a new structural rounding framework for generalizing approximation algorithms for highly structured (unrealistic) graph classes to networks that are close to the class.

This talk includes joint work with subsets of C.T. Brown, E. Demaine, B. Lavallee, Q. Liu, D. Moritz, M. O'Brien, F. Reidl, T. Reiter, P. Rossmanith, F. Sanchez Villaamil, S. Sikdar, A. Vakilian, and A. van der Poel.

Bio: Blair D. Sullivan is an Associate Professor in the Department of Computer Science at North Carolina State University, and a member of the Data-Driven Science cluster of the Chancellor’s Faculty Excellence Program. Prior to joining NC State, Dr. Sullivan was a Research Scientist in the Computer Science and Mathematics Division at Oak Ridge National Laboratory, where she still holds a Joint Faculty Appointment. She received her Ph.D. in Mathematics from Princeton University in 2008 as a Department of Homeland Security Graduate Fellow, and B.S. degrees in Applied Mathematics and Computer Science from Georgia Tech in 2003. Sullivan’s research cross-cuts the fields of theoretical computer science, network science, data-driven science, and discrete mathematics. In 2014, Sullivan was named one of 14 Moore Investigators in Data-Driven Discovery.


Dr. Bruce Maggs (Duke University, USA)
Sunday, Dec 16, 8:30-9:30am

TItle: The Web PKI in Theory and Malpractice

Abstract: The Public Key Infrastructure (PKI) for the web was designed to help thwart "phishing" attacks by providing a mechanism for browsers to authenticate web sites, and also to help prevent the disclosure of confidential information by enabling encrypted communications. For users to reap these benefits, however, the parties that implement and operate the PKI, including certificate authorities, web-site operators, and browser vendors, must each perform their roles properly. This talk focuses on one aspect of the PKI: certificate revocation. The security of a web site hinges on the ability of the site operator to keeps its private keys private. While most operators guard their keys carefully, on occasion software vulnerabilities such as the notorious Heartbleed Bug have put millions of keys at risk. If a web-site operator fears that its private key has been compromised, it should ask its certificate authority to revoke the corresponding certificate. Browsers, however, often do not fully check whether the certificates they receive have been revoked, and mobile browsers never check. There are a variety of reasons for not checking, but the most important are the amount of bandwidth required to download certificate revocation lists in advance, the latency of checking certificates on the fly, and the slow progress of upgrading every web server to support the newer certificate status stapling approach. This talk presents a new and much more efficient system, CRLite, for pushing the revocation status of every certificate to every browser. CRLite leverages a recent development: although lists of revoked certificates were previously available, Google's Certificate Transparency project now also provides a log of all unrevoked certificates as well. With both lists in hand, a compact data structure called a filter cascade can be used to represent the status of every certificate with no false positives and no false negatives. CRLite requires a browser to download a 1.2MB filter cascade initially, and then a 40KB update (on average) every day. Our results demonstrate that complete revocation checking is within reach for all clients.

Bio: Bruce Maggs received the S.B., S.M., and Ph.D. degrees in computer science from the Massachusetts Institute of Technology in 1985, 1986, and 1989, respectively. His advisor was Charles Leiserson. After spending one year as a Postdoctoral Associate at MIT, he worked as a Research Scientist at NEC Research Institute in Princeton from 1990 to 1993. In 1994, he moved to Carnegie Mellon, where he stayed until joining Duke University in 2009. While on a two-year leave-of-absence from Carnegie Mellon, Maggs helped to launch Akamai Technologies, serving as its first Vice President for Research and Development. He retains a part-time role at Akamai as Vice President for Research. In 2017 he won the Best Dataset Award at the Passive and Active Measurement Conference, The Best Paper Award at CoNEXT, a Distinguished Paper Award at USENIX Security, and the 2017 IEEE Cybersecurity Innovation Award for work that appeared at IEEE Security and Privacy. In 2018 he was part of a large team that received the inaugural SIGCOMM Networking Systems Award for the Akamai CDN.