Benjamin Rossman | Scholars@Duke

Benjamin Rossman
Associate Professor of Computer Science

Office Hours

Please email me for office hours.

Current Appointments & Affiliations

Associate Professor of Computer Science, Computer Science, Trinity College of Arts & Sciences 2020
Associate Professor of Mathematics, Mathematics, Trinity College of Arts & Sciences 2020

Contact Information

Room D110, LSRC, Durham, NC 27708
Room D110, LSRC, 308 Research Drive, Durham, NC 27708
benjamin.rossman@duke.edu
Personal website

Background
Education, Training, & Certifications
- Ph.D., Massachusetts Institute of Technology 2010
Research
Selected Grants
- NSF Student Travel Grant for 2023 Conference on Computational Complexity awarded by National Science Foundation 2023 - 2024
- Rossman Alfred P. Sloan Foundation Fellowship (transfer) awarded by Alfred P. Sloan Foundation 2020 - 2021
Publications & Artistic Works
Selected Publications
- Academic Articles
  - Kush, D., and B. Rossman. “TREE-DEPTH AND THE FORMULA COMPLEXITY OF SUBGRAPH ISOMORPHISM.” Siam Journal on Computing 52, no. 1 (January 1, 2023): 273–325. https://doi.org/10.1137/20M1372925.
    Full Text
  - Cavalar, Bruno Pasqualotto, Mrinal Kumar, and Benjamin Rossman. “Monotone Circuit Lower Bounds from Robust Sunflowers.” Algorithmica 84, no. 12 (January 2022): 3655–85. https://doi.org/10.1007/s00453-022-01000-3.
    Full Text
  - Kawarabayashi, K. I., and B. Rossman. “A polynomial excluded-minor approximation of treedepth.” Journal of the European Mathematical Society 24, no. 4 (January 1, 2021): 1449–70. https://doi.org/10.4171/JEMS/1133.
    Full Text
  - Rossman, B. “Subspace-invariant AC⁰ formulas.” Logical Methods in Computer Science 15, no. 3 (January 1, 2019): 3:1-3:12. https://doi.org/10.23638/LMCS-15(3:3)2019.
    Full Text
  - Rossman, B., and S. Srinivasan. “Separation of AC⁰[⊕] formulas and circuits.” Theory of Computing 15 (January 1, 2019). https://doi.org/10.4086/toc.2019.v015a017.
    Full Text
  - Rossman, B. “The Average Sensitivity of Bounded-Depth Formulas.” Computational Complexity 27, no. 2 (June 1, 2018): 209–23. https://doi.org/10.1007/s00037-017-0156-0.
    Full Text
  - Håstad, J., B. Rossman, R. A. Servedio, and L. Y. Tan. “An average-case depth hierarchy theorem for boolean circuits.” Journal of the Acm 64, no. 5 (August 1, 2017). https://doi.org/10.1145/3095799.
    Full Text
  - Kawachi, A., B. Rossman, and O. Watanabe. “The Query Complexity of Witness Finding.” Theory of Computing Systems 61, no. 2 (August 1, 2017): 305–21. https://doi.org/10.1007/s00224-016-9708-y.
    Full Text
  - Li, Y., A. Razborov, and B. Rossman. “On the AC⁰ complexity of subgraph isomorphism.” Siam Journal on Computing 46, no. 3 (January 1, 2017): 936–71. https://doi.org/10.1137/14099721X.
    Full Text
  - Kopparty, S., and B. Rossman. “The homomorphism domination exponent.” European Journal of Combinatorics 32, no. 7 (October 1, 2011): 1097–1114. https://doi.org/10.1016/j.ejc.2011.03.009.
    Full Text
  - Demaine, E. D., S. Mozes, B. Rossman, and O. Weimann. “An optimal decomposition algorithm for tree edit distance.” Acm Transactions on Algorithms 6, no. 1 (December 1, 2009). https://doi.org/10.1145/1644015.1644017.
    Full Text
  - Rossman, B. “Homomorphism preservation theorems.” Journal of the Acm 55, no. 3 (July 1, 2008). https://doi.org/10.1145/1379759.1379763.
    Full Text
  - Dawar, A., D. Richerby, and B. Rossman. “Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs.” Annals of Pure and Applied Logic 152, no. 1–3 (March 1, 2008): 31–50. https://doi.org/10.1016/j.apal.2007.11.011.
    Full Text
  - Blass, A., Y. Gurevich, D. Rosenzweig, and B. Rossman. “Interactive small-step algorithms I: Axiomatization.” Logical Methods in Computer Science 3, no. 4 (November 5, 2007). https://doi.org/10.2168/LMCS-3(4:3)2007.
    Full Text
  - Blass, A., Y. Gurevich, D. Rosenzweig, and B. Rossman. “Interactive small-step algorithms II: Abstract state machines and the characterization theorem.” Logical Methods in Computer Science 3, no. 4 (November 5, 2007). https://doi.org/10.2168/LMCS-3(4:4)2007.
    Full Text
  - Rossman, B. “Successor-invariant first-order logic on finite structures.” Journal of Symbolic Logic 72, no. 2 (June 1, 2007): 601–18. https://doi.org/10.2178/jsl/1185803625.
    Full Text
  - Gurevich, Y., B. Rossman, and W. Schulte. “Semantic essence of asml: Extended abstract.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3188 (January 1, 2004): 240–59. https://doi.org/10.1007/978-3-540-30101-1_11.
    Full Text
- Conference Papers
  - He, W., and B. Rossman. “Symmetric Formulas for Products of Permutations.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 251, 2023. https://doi.org/10.4230/LIPIcs.ITCS.2023.68.
    Full Text
  - Rossman, B. “Shrinkage of decision lists and DNF formulas.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 185, 2021. https://doi.org/10.4230/LIPIcs.ITCS.2021.70.
    Full Text
  - Kush, D., and B. Rossman. “Tree-depth and the formula complexity of subgraph isomorphism.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 2020-November:31–42, 2020. https://doi.org/10.1109/FOCS46700.2020.00012.
    Full Text
  - Cavalar, B. P., M. Kumar, and B. Rossman. “Monotone Circuit Lower Bounds from Robust Sunflowers.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12118 LNCS:311–22, 2020. https://doi.org/10.1007/978-3-030-61792-9_25.
    Full Text
  - Rossman, B. “Thresholds in the Lattice of Subspaces of Fqn.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12118 LNCS:504–15, 2020. https://doi.org/10.1007/978-3-030-61792-9_40.
    Full Text
  - Rossman, B. “Criticality of regular formulas.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 137, 2019. https://doi.org/10.4230/LIPIcs.CCC.2019.1.
    Full Text
  - Kawarabayashi, K. I., and B. Rossman. “A polynomial excluded-minor approximation of treedepth.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 234–46, 2018. https://doi.org/10.1137/1.9781611975031.17.
    Full Text
  - Rossman, B. “Formulas versus circuits for small distance connectivity.” In Siam Journal on Computing, 47:1986–2028, 2018. https://doi.org/10.1137/15M1027310.
    Full Text
  - Rossman, B. “Lower bounds for subgraph isomorphism.” In Proceedings of the International Congress of Mathematicians, Icm 2018, 4:3443–64, 2018.
  - Rossman, B. “An improved homomorphism preservation theorem from lower bounds in circuit complexity.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 67, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.27.
    Full Text
  - Rossman, B. “Subspace-invariant AC⁰ formulas.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 80, 2017. https://doi.org/10.4230/LIPIcs.ICALP.2017.93.
    Full Text
  - Rossman, B., and S. Srinivasan. “Separation of AC⁰[⊕] formulas and circuits.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 80, 2017. https://doi.org/10.4230/LIPIcs.ICALP.2017.50.
    Full Text
  - Robere, R., T. Pitassi, B. Rossman, and S. A. Cook. “Exponential Lower Bounds for Monotone Span Programs.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 2016-December:406–15, 2016. https://doi.org/10.1109/FOCS.2016.51.
    Full Text
  - Pitassi, T., B. Rossman, L. Y. Tan, and R. A. Servedio. “Poly-logarithmic Frege depth lower bounds via an expander switching lemma.” In Proceedings of the Annual Acm Symposium on Theory of Computing, 19-21-June-2016:644–57, 2016. https://doi.org/10.1145/2897518.2897637.
    Full Text
  - Rossman, B. “The Average Sensitivity of Bounded-Depth Formulas.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 2015-December:424–30, 2015. https://doi.org/10.1109/FOCS.2015.33.
    Full Text
  - Rossman, B., R. A. Servedio, and L. Y. Tan. “An Average-Case Depth Hierarchy Theorem for Boolean Circuits.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 2015-December:1030–48, 2015. https://doi.org/10.1109/FOCS.2015.67.
    Full Text
  - Rossman, B. “Correlation bounds against monotone NC¹.” In Leibniz International Proceedings in Informatics, Lipics, 33:392–411, 2015. https://doi.org/10.4230/LIPIcs.CCC.2015.392.
    Full Text
  - Li, Y., A. Razborov, and B. Rossman. “On the AC⁰ complexity of subgraph isomorphism.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 344–53, 2014. https://doi.org/10.1109/FOCS.2014.44.
    Full Text
  - Kawachi, A., B. Rossman, and O. Watanabe. “The query complexity of witness finding.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8476 LNCS:218–31, 2014. https://doi.org/10.1007/978-3-319-06686-8_17.
    Full Text
  - Rossman, B. “Formulas vs. circuits for small distance connectivity.” In Proceedings of the Annual Acm Symposium on Theory of Computing, 203–12, 2014. https://doi.org/10.1145/2591796.2591828.
    Full Text
  - Rossman, B. “The monotone complexity of k-clique on random graphs.” In Siam Journal on Computing, 43:256–79, 2014. https://doi.org/10.1137/110839059.
    Full Text
  - Rossman, B. “A tight upper bound on the number of variables for average-case k-clique on ordered graphs.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7456 LNCS:282–90, 2012. https://doi.org/10.1007/978-3-642-32621-9_21.
    Full Text
  - Rossman, B. “Choiceless computation and symmetry.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6300 LNCS:565–80, 2010. https://doi.org/10.1007/978-3-642-15025-8_28.
    Full Text
  - Rossman, B. “The monotone complexity of k-clique on random graphs.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 193–201, 2010. https://doi.org/10.1109/FOCS.2010.26.
    Full Text
  - Rossman, B. “Ehrenfeucht-Fraïssé Games on Random Structures.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5514 LNAI:350–64, 2009. https://doi.org/10.1007/978-3-642-02261-6_28.
    Full Text
  - Rossman, B. “On the constant-depth complexity of k-clique.” In Proceedings of the Annual Acm Symposium on Theory of Computing, 721–30, 2008. https://doi.org/10.1145/1374376.1374480.
    Full Text
  - Demaine, E. D., S. Mozes, B. Rossman, and O. Weimann. “An optimal decomposition algorithm for tree edit distance.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4596 LNCS:146–57, 2007. https://doi.org/10.1007/978-3-540-73420-8_15.
    Full Text
  - Dawar, A., D. Richerby, and B. Rossman. “Choiceless polynomial time, counting and the cai-fürer-immerman graphs: (Extended abstract).” In Electronic Notes in Theoretical Computer Science, 143:13–26, 2006. https://doi.org/10.1016/j.entcs.2005.05.024.
    Full Text
  - Rossman, B. “Existential positive types and preservation under homomorphisms.” In Proceedings Symposium on Logic in Computer Science, 467–76, 2005.
  - Gurevich, Y., B. Rossman, and W. Schulte. “Semantic essence of AsmL.” In Theoretical Computer Science, 343:370–412, 2005. https://doi.org/10.1016/j.tcs.2005.06.017.
    Full Text
  - Rossman, B. “Successor-invariance in the finite.” In Proceedings Symposium on Logic in Computer Science, 148–57, 2003.
Teaching & Mentoring
Recent Courses

Some information on this profile has been compiled automatically from Duke databases and external sources. (Our About page explains how this works.) If you see a problem with the information, please write to Scholars@Duke and let us know. We will reply promptly.

Education, Training, & Certifications

Selected Grants

Selected Publications

Academic Articles

Conference Papers

Recent Courses