Darren Strash

About Me

I am a technophile who is committed to open science and equality in education. My goal is to produce innovative high-quality research, and use my extensive research and practical experience to effectively teach and mentor the next generation of computer scientists.

In 2011, I received a PhD in Computer Science from University of California, Irvine under the advisement of David Eppstein and Mike Goodrich. From there, I worked in research and development in Intel's Computational Lithography Group until 2014. I then worked as a postdoctoral researcher with Peter Sanders at Karlsruhe Institute of Technology from 2014 to 2016, and as a Visiting Assistant Professor at Colgate University from 2016 to 2018. I am now an Assistant Professor at Hamilton College.

If you are looking for more information, here is my CV, my research statement, and my teaching statement.

Research

My passion is to reveal and resolve the mismatch between the theory and practice of algorithms, with applications in large scale network analysis and computational geometry. My work often involves first understanding real-world properties of data sets, then designing algorithms that exploit these properties to gain efficiency that is not possible otherwise. This includes both theoretical efficiency and efficiency of algorithms in practice (algorithm engineering). Some specific areas that interest me are combinatorial optimization, subgraph counting/listing, network visualization, shortest paths, range searching, and dynamic data structures.

Publications

Papers in Refereed Journals

[5] Finding Near-Optimal Independent Sets at Scale
S. Lamm, P. Sanders, C. Schulz, D. Strash, and R.F. Werneck
Journal of Heuristics 23(4), 2017, pp. 207-229.
doi:10.1007/s10732-017-9337-x
The code is freely available under GPL v2.0.

[4] Listing All Maximal Cliques in Large Sparse Real-World Graphs in Near-Optimal Time
D. Eppstein, M. Löffler, and D. Strash
ACM Journal of Experimental Algorithmics 18(3): 3.1, ACM, 2013. Special issue for SEA 2011.
doi:10.1145/2543629
The code and data sets are freely available under GPL v3.0.

[3] Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon
D. Eppstein, M.T. Goodrich, M. Löffler, D. Strash, and L. Trott
Theoretical Computer Science 514, 2013, pp. 96-104. Special issue for GA 2011.
doi:10.1016/j.tcs.2013.04.027
arXiv:1110.4499

[2] Extended Dynamic Subgraph Statistics using h-index Parametrized Data Structures
D. Eppstein, M.T. Goodrich, D. Strash, and L. Trott
Theoretical Computer Science 447, 2012, pp. 44-52. Special issue for COCOA 2010.
doi:10.1016/j.tcs.2011.11.034

[1] Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings
D. Eppstein, M.T. Goodrich, and D. Strash
SIAM Journal on Computing 39 (8), 2010, pp. 3814-3829.
doi:10.1137/090759112

Papers in Peer-Reviewed Conference Proceedings

[17] Reconstructing Generalized Staircase Polygons with Uniform Step Length
N. Sitchinava and D. Strash
Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017), LNCS, Springer, 2017 (to appear).
arXiv:1708.09842

[16] Distributed Evolutionary k-way Node Separators
P. Sanders, C. Schulz, D. Strash, and R. Williger
Proceedings of the Conference on Genetic and Evolutionary Computing and Combinatorial Optimization (GECCO 2017), pp. 345-352, ACM, 2017.
doi:10.1145/3071178.3071204
arXiv:1702.01692

[15] Shared Memory Parallel Subgraph Enumeration
R. Kimmig, H. Meyerhenke, and D. Strash
Proceedings of the 31st IEEE International Parallel and Distributed Processing Symposium Workshops (IEEE IPDPSW 2017), pp. 519-529, IEEE, 2017.
doi:10.1109/IPDPSW.2017.133
arXiv:1705.09358

[14] Temporal Map Labeling: A New Unified Framework with Experiments
L. Barth, B. Niedermann, M. Nöllenburg, and D. Strash
Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2016), pp. 23:1-23:10, ACM, 2016.
doi:10.1145/2996913.2996957
arXiv:1609.06327

[13] On the Power of Simple Reductions for the Maximum Independent Set Problem
D. Strash
Proceedings of the 22nd International Computing and Combinatorics Conference (COCOON 2016), LNCS vol. 9797, pp. 345-356.
doi:10.1007/978-3-319-42634-1_28
arXiv:1608.00724

[12] Accelerating Local Search for the Maximum Independent Set Problem
D. Dahlum, S. Lamm, P. Sanders, C. Schulz, D. Strash, and R.F. Werneck
Proceedings of the 15th International Symposium on Experimental Algorithms (SEA 2016), LNCS vol. 9685, pp. 118-133.
doi:10.1007/978-3-319-38851-9_9
arXiv:1602.01659

[11] Finding Near-Optimal Independent Sets at Scale
S. Lamm, P. Sanders, C. Schulz, D. Strash, and R.F. Werneck
Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX 2016), pp. 138-150.
doi:10.1137/1.9781611974317.12
arXiv:1509.00764
The code is freely available under GPL v2.0.

[10] On Minimizing Crossings in Storyline Visualizations
I. Kostitsyna, M. Nöllenburg, V. Polishchuk, A. Schulz, and D. Strash
Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), LNCS vol. 9411, pp. 192-198.
doi:10.1007/978-3-319-27261-0_16
arXiv:1509.00442

[9] On the Complexity of Barrier Resilience for Fat Regions
M. Korman, M. Löffler, R.I. Silveira, and D. Strash
Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2013), LNCS vol. 8243, pp. 201-216.
doi:10.1007/978-3-642-45346-5_15
arXiv:1302.4707

[8] Dynamic Planar Point Location with Sub-logarithmic Local Updates
M. Loffler, J.A. Simons, and D. Strash
Proceedings of the 13th International Symposium on Algorithms and Data Structures (WADS 2013), LNCS vol. 8037, pp. 499-511.
doi:10.1007/978-3-642-40104-6_43
arXiv:1204.4714

[7] Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon
D. Eppstein, M.T. Goodrich, M. Löffler, D. Strash, and L. Trott
Proceedings of the 3rd International Conference on Computational Aspects of Social Networks (CASoN 2011), pp. 102--107.
doi:10.1109/CASON.2011.6085926
arXiv:1108.4675

[6] Listing All Maximal Cliques in Large Sparse Real-World Graphs
D. Eppstein and D. Strash
Proceedings of the 10th International Conference on Experimental Algorithms (SEA 2011), LNCS vol. 6630, pp. 403-414.
doi:10.1007/978-3-642-20662-7_31
arXiv:1103.0318
The code and data sets are freely available under GPL v3.0.

[5] Extended Dynamic Subgraph Statistics using h-index Parametrized Data Structures
D. Eppstein, M.T. Goodrich, D. Strash, and L. Trott
Proceedings of the 4th International Conference on Combinatorial Optimization and Applications (COCOA 2010), LNCS vol. 6508, pp. 128-141.
doi:10.1007/978-3-642-17458-2_12
arXiv:1009.0783

[4] Priority Range Trees
M.T. Goodrich and D. Strash
Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS vol. 6506, pp. 97-108.
doi:10.1007/978-3-642-17517-6_11
arXiv:1009.3527

[3] Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
D. Eppstein, M. Löffler, and D. Strash
Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS vol. 6506, pp. 403-413.
doi:10.1007/978-3-642-17517-6_36
arXiv:1006.5440

[2] Succinct Greedy Geometric Routing in the Euclidean Plane
M.T. Goodrich and D. Strash
Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), LNCS vol. 5878, pp. 781-791.
doi:10.1007/978-3-642-10631-6_79
arXiv:0812.3893

[1] Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings
D. Eppstein, M.T. Goodrich, and D. Strash
Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp 150-159.
doi:10.1137/1.9781611973068.18
arXiv:0812.0893

Other Publications

[4] Reconstructing a Unit-Length Orthogonally Convex Polygon from its Visibility Graph
N. Sitchinava and D. Strash
32nd European Workshop on Computational Geometry (EuroCG 2016), July 2011.

[3] Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon
D. Eppstein, M.T. Goodrich, M. Löffler, D. Strash, and L. Trott
Workshop on Graph Algorithms and Applications (GA 2011), July 2011.

[2] Extending Garbage Collection to Complex Data Structures
L. Effinger-Dean, C. Erickson, M. O'Neill, and D. Strash
Proceedings of the 3rd Workshop on Semantics, Program Analysis and Computing Environments for Memory Management (SPACE 2006), pp 91-97.

[1] Garbage Collection for Trailer Arrays
L. Effinger-Dean, C. Erickson, M. O'Neill, and D. Strash
Proceedings of the 3rd Workshop on Semantics, Program Analysis and Computing Environments for Memory Management (SPACE 2006), pp 83-90.

Software and Data Sets

Teaching

Theses Supervised

Bachelor's Theses

How to Partition a Graph when You Think Like a Vertex, Dec. 2015
Jan Ebbing
Supervised with Peter Sanders and Christian Schulz

Boosting Local Search for the Maximum Independent Set Problem, Nov. 2015
Jakob Dahlum
Supervised with Peter Sanders and Christian Schulz

Contact Me

Hamilton College
Department of Computer Science
198 College Hill Road
Clinton, NY 13323

Office: Taylor Science Center 2015A
Phone: (315) 859-4188
E-mail: first initial last name AT hamilton DOT edu