Benjamin Rossman, Associate Professor of Computer Science

My research interests lie in computational complexity and logic, specifically the areas of circuit complexity (the quest for lower bounds in combinatorial models of computation) and finite model theory (the study of logical definability on finite structures). My work is supported by NSERC Discovery and Accelerator Grants, the Ontario Early Researcher Award, and a Sloan Research Fellowship.

Contact Info:

Office Location:	Room D110, LSRC, 308 Research Drive, Durham, NC 27708
Email Address:
Web Page:	https://users.cs.duke.edu/~br148/

Teaching (Spring 2026):

• COMPSCI 531D.001, INTRODUCTION TO ALGORITHMS Synopsis

  Physics 128, TuTh 04:40 PM-05:55 PM

• COMPSCI 531D.01D, INTRODUCTION TO ALGORITHMS Synopsis

  Physics 128, W 04:40 PM-05:55 PM

Office Hours:

Please email me for office hours.

Education:

Ph.D.

Massachusetts Institute of Technology

2010

Recent Publications   (More Publications)

1. Rossman, B, Equi-Rank Homomorphism Preservation Theorem on Finite Structures, Leibniz International Proceedings in Informatics Lipics, vol. 326 (February, 2025) [doi]  [abs]
2. Rossman, B, Riffle Rank, Procedia Computer Science, vol. 273 (January, 2025), pp. 215-222 [doi]  [abs]
3. Rossman, B, Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication, Proceedings of the Annual ACM Symposium on Theory of Computing (June, 2024), pp. 1386-1395 [doi]  [abs]
4. Kush, D; Rossman, B, TREE-DEPTH AND THE FORMULA COMPLEXITY OF SUBGRAPH ISOMORPHISM, SIAM Journal on Computing, vol. 52 no. 1 (January, 2023), pp. 273-325 [doi]  [abs]
5. He, W; Rossman, B, Symmetric Formulas for Products of Permutations, Leibniz International Proceedings in Informatics Lipics, vol. 251 (January, 2023), ISBN 9783959772631 [doi]  [abs]

Recent Grant Support

• NSF Student Travel Grant for 2023 Conference on Computational Complexity, National Science Foundation, 2023/06-2025/05.