Benjamin E. Rossman is an American mathematician and theoretical computer scientist, specializing in
computational complexity theory.[1] He is currently an associate professor of computer science and mathematics at
Duke University.
His research seeks to quantify the minimum resources required to solve basic problems in combinatorial models such as
Boolean circuits. Through creative techniques based in
logic and the probabilistic method, Ben has derived groundbreaking lower bounds on the
complexity of detecting
cliques and determining
connectivity in
random graphs. His other notable results include size and depth
hierarchy theorems for
bounded-depth circuits, answering longstanding questions.[6]
Demaine, Erik D.; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2007). "An Optimal Decomposition Algorithm for Tree Edit Distance". Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 4596. pp. 146–157.
doi:
10.1007/978-3-540-73420-8_15.
ISBN978-3-540-73419-2.
^Rossman, Benjamin (2010). Average-case complexity of detecting cliques (Doctoral dissertation, Massachusetts Institute of Technology) (Thesis). Massachusetts Institute of Technology.
hdl:
1721.1/62441.
^"Benjamin Rossman". Simons Institute for the Theory of Computing, U.C. Berkeley campus. 11 April 2014.