Publications by my students while they were studying with me that I did not co-author are below.
Defend Dissent: Digital Suppression and Cryptographic Defense of Social Movements
Glencora Borradaile
* Open Textbook @ OSU, 2021
The Motivated Can Encrypt (Even with PGP)
Glencora Borradaile, Kelsy Kretschmer, Michele Gretes, Alexandria LeClerc
* PETS 2021
[ arXiv ]
Listen up, STEM: We Don’t Just Teach Facts
Glencora Borradaile
* Chapter in Transformative Approaches to Social Justice Education, Routledge 2021
[ last unproofed version ]
Sousveillance Capitalism
Glencora Borradaile, Joshua Reeves
* Surveillance and Society 2020
[ doi ]
Low-stretch spanning trees of graphs with bounded width
Glencora Borradaile, Erin Chambers, David Eppstein, Will Maxwell, Amir Nayyeri
* SWAT 2020
[ arXiv ] [ summary by David Eppstein ]
Minimum bounded chains and minimum homologous chains in
embedded simplicial complexes
Glencora Borradaile, Will Maxwell, Amir Nayyeri
* SoCG 2020
[ arXiv ]
Whose Tweets are Surveilled for the Police: An Audit of a Social-Media Monitoring Tool via Log Files
Glencora Borradaile, Brett Burkhardt, Alexandria LeClerc
* FAT* 2020 (now FAccT)
[ arXiv ][ lay summary ]
Greedy spanners are optimal in doubling metrics
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen
* SODA 2019
[ arXiv ]
Designing practical PTASes for minimum feedback vertex set in planar graphs
Glencora Borradaile, Hung Le, Baigong Zheng
* SEA 2019
[ arXiv ]
Training the Motivated: Digital Security for Activists
Glencora Borradaile and Kelsy Kretschmer
* SOUPS’17
[ USENIX ]
Density decompositions of networks
Theresa Migler, Glencora Borradaile and Gordon Wilfong
* CompleNet’18
[ arXiv ] [ accompanying source code ]
Minor-free graphs have light spanners
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen
* FOCS 2017.
[ arXiv ]
Large induced acyclic and outerplanar subgraphs of 2-outerplanar graphs
Glencora Borradaile, Hung Le, Melissa Sherman-Bennett
* Graphs and Combinatorics, 2017
[ arXiv ]
A PTAS for three-edge connectivity in planar graphs
Glencora Borradaile, Baigong Zheng
* APPROX 2017
[ arXiv ]
Egalitarian Graph Orientations
Glencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon Wilfong, Lisa Zhang
* Journal of Graph Algorithms and Applications, Vol. 21, no. 4, 2017
[ arXiv ]
Light spanners for bounded treewidth graphs imply light spanners for H-minor-free graphs
Glencora Borradaile, Hung Le
[ arXiv ]
Embedded-width: A variant of treewidth for plane graphs
Glencora Borradaile, Jeff Erickson, Hung Le, Robbie Weber
[ arXiv ]
Minimum cycle and homology bases of surface embedded graphs
Glencora Borradaile, Erin Wolf Chambers, Kyle Fox and Amir Nayyeri
* SoCG 2016
* JoCG 2017, special issue for SoCG 2016
[ arXiv ]
Optimal dynamic program for r-domination problems over tree decompositions.
Glencora Borradaile and Hung Le.
* International Symposium on Parameterized and Exact Computation (IPEC), 2016.
[ arXiv ]
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs
* Entry in the Encyclopedia of Algorithms, 2nd Edition, edited by Ming-Yang Kao. 2016.
[ pdf ]
Maximum st-Flow in Planar Graphs
* Entry in the Encyclopedia of Algorithms, 2nd Edition, edited by Ming-Yang Kao. 2016.
[ pdf ]
All-pairs minimum cuts in near-linear time for surface-embedded graphs
Glencora Borradaile, David Eppstein, Amir Nayyeri and Christian Wulff-Nilsen
* SoCG 2016
[ arXiv ]
The two-edge connectivity survivable network problem in planar graphs.
Glencora Borradaile and Philip Klein.
* Transactions on Algorithms, Volume 12, Issue 3, June 2016
* Int’l Colloq. on Automata, Languages and Programming (ICALP), 2008.
[ arXiv ]
Towards single face shortest vertex-disjoint paths in undirected planar graphs
Glencora Borradaile, Amir Nayyeri and Farzad Zafarani
* ESA 2015
[ arXiv ]
Improving robustness of next-hop routing
Glencora Borradaile, W. Sean Kennedy, Gordon Wilfong and Lisa Zhang
* Journal of Combinatorial Optimization, pp. 1-15, doi 10.1007/s10878-014-9818-x December 2014.
[ arXiv ]
Planar induced subgraphs of sparse graphs
Glencora Borradaile, David Eppstein and Pingan Zhu
* Journal of Graph Algorithms and Applications, Vol. 19, no. 1, pp. 281-297, 2015.
* Graph Drawing 2014
[ arXiv ]
Covering nearly surface-embedded graphs with a fixed number of balls
Glencora Borradaile and Erin Wolf Chambers
* Discrete & Computational Geometry, pp. 979-996, volume 54, issue 4, 2014.
[ arXiv ]
A polynomial-time approximation scheme for Euclidean Steiner forest.
Glencora Borradaile, Philip Klein and Claire Mathieu.
* Transactions on Algorithms, Volume 11, Issue 3, Article 19, January 2015.
* Foundations of Computer Science (FOCS), 2008.
[ arXiv ]
Algorithms for Optimization Problems in Planar Graphs
Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu.
* Dagstuhl Reports, pp. 35–57, volume 3, number 10, 2014.
[ doi ]
Min st-cut oracle for planar graphs with near-linear preprocessing time.
Glencora Borradaile, Piotr Sankowski and Christian Wulff-Nilsen.
* Transactions on Algorithms, Volume 11, Issue 3, Article 16, January 2015.
* Foundations of Computer Science (FOCS), 2010.
[ arXiv ]
Maximum st-flow in directed planar graphs via shortest paths.
Glencora Borradaile and Anna Harutyunyan.
* International Workshop on Combinatorial Algorithms (IWOCA) 2013.
[ arXiv ]
Boundary-to-boundary flows in planar graphs.
Glencora Borradaile and Anna Harutyunyan.
* International Workshop on Combinatorial Algorithms (IWOCA) 2013.
[ arXiv ]
Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets
Glencora Borradaile and David Eppstein.
* Canadian Conference on Computational Geometry (CCCG), 2012.
* To appear in Computational Geometry: Theory and Applications special issue for CCCG 2012.
[ arXiv ]
Connectivity oracles for planar graphs
Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen.
* Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2012.
[ arXiv ]
Planted-model evaluation of algorithms for identifying differences between spreadsheets
Anna Harutyunyan, Glencora Borradaile, Christopher Chambers and Christopher Scaffidi.
* IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), 2012.
[ pdf ]
Batch active learning via coordinating matching
Javad Azimi, Alan Fern, Xiaoli Fern, Glencora Borradaile, and Brent Heeringa.
* International Conference on Machine Learning (ICML), 2012.
[ arXiv ]
Approximation algorithms for constrained knapsack problems
Glencora Borradaile, Brent Heeringa and Gordon Wilfong.
* Journal of Discrete Algorithms special issue for IWOCA 2011, 2012.
* International Workshop on Combinatorial Algorithms (IWOCA), 2011.
[ arXiv ]
Polynomial-time approximation schemes for connectivity problems in bounded-genus graphs.
Glencora Borradaile, Erik Demaine and Siamak Tazari.
* Algorithmica, 2012.
* Int’l Symp. on Theoretical Aspects of Computer Science (STACS), 2009.
[ arXiv ]
Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
Glencora Borradaile, Philip Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen.
* To appear: SIAM Journal on Computing.
* Foundations of Computer Science (FOCS), 2011.
[ arXiv ]
Multiple source, single sink maximum flow in a planar graph
Glencora Borradaile and Christian Wulff-Nilsen.
* Manuscript, 2010.
[ arXiv ]
Randomly removing g handles at once.
Glencora Borradaile, James Lee and Anastasios Sidiropoulos.
* Computational Geometry: Theory and Applications special issue for SoCG 2009, volume 43, 2010.
* Symposium on Computational Geometry (SoCG), 2009.
[ arXiv ]
A polynomial-time approximation scheme for Steiner tree in planar graphs.
Glencora Borradaile, Claire Mathieu, and Philip Klein.
* ACM Transactions on Algorithms special issue for SODA 2007, 5(3), 2009.
* Symposium on Discrete Algorithms (SODA), 2007.
[ pdf, full version ]
An O(n log n) algorithm for maximum st-flow in a directed planar graph.
Glencora Borradaile and Philip Klein.
* Journal of the ACM, 56(2), 2009.
* Symposium on Discrete Algorithms (SODA), 2006.
[ pdf, full version ]
Planarity Testing
* Entry in the Encyclopedia of Algorithms, edited by Ming-Yang Kao. 2008.
[ pdf ]
Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon.
Glencora Borradaile, Philip Klein and Claire Mathieu.
* Workshop of Algorithms and Data Structures (WADS), 2007.
[ incorporated into journal version listed above ]
Safe and tight linear estimators for global optimization.
Glencora Borradaile and Pascal Van Hentenryck.
* Mathematical Programming, 102(3), 2005.
[ pdf ]
Exploiting Planarity for Network Flow and Connectivity Problems
Glencora Borradaile.
Dissertation, Brown University, December 2007.
[ pdf ]
Publications by my students during their studies and funded by my research grants
A PTAS for subset TSP in minor-free graphs.
Hung Le.
SODA, 2020.
[ arXiv ]
Local Search is a PTAS for Feedback Vertex Set in Minor-free Graphs.
Hung Le and Baigong Zheng.
COCOON, 2019.
[ arVix ]
A better bound on the largest induced forests in triangle-free planar graphs.
Hung Le.
Graphs and Combinatorics, 34(6), 2018.
[ arXiv ]
