Benjamin Rossman

Benjamin Rossman

Contact Information
Room G636
The Stata Center
32 Vassar St.
Cambridge, MA 02139

b(last name) at theory . csail . mit . edu

I am currently a postdoc at Tokyo Institute of Technology. Previously, I was graduate student in the Theory of Computation group in MIT's Computer Science and Artificial Intelligence Laboratory where I was advised by Madhu Sudan. My main research interests are circuit complexity and finite model theory.

Ph.D. Thesis

Average-Case Complexity of Detecting Cliques

Papers

The Monotone Complexity of k-Clique on Random Graphs, Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), 193-201.
On the Constant-Depth Complexity of k-Clique, Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC 2008), 721-730.
Homomorphism Preservation Theorems, Journal of the ACM, Volume 55, Issue 3 (July 2008), 1-53.
Successor-Invariant First-Order Logic on Finite Structures, Journal of Symbolic Logic, Volume 72, Issue 2 (2007), 601-618.
(with Swastik Kopparty) The Homomorphism Domination Exponent, European Journal of Combinatorics, Volume 32, Issue 7 (2011), 1097-1114.
Choiceless Computation and Symmetry, in "Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday", Springer-Verlag LNCS, vol. 6300, August 2010, 565-580.
(with Erik Demaine, Shay Mozes and Oren Weimann) An Optimal Decomposition Algorithm for Tree Edit Distance, ACM Transactions on Algorithms, Vol. 6 (1:2), December 2009, 1-19.
Ehrenfeucht-Fraisse Games on Random Graphs, Proceedings of the 16th Workshop on Logic, Language, Information and Computation (WoLLIC 2009), 350-364.
(with Anuj Dawar and David Richerby) Choiceless Polynomial Time, Counting and the Cai-Furer-Immerman Graphs, Annals of Pure and Applied Logic, 152 (2008), 31-50.
(with Andreas Blass, Yuri Gurevich and Dean Rosenzweig) Interactive Small-Step Algorithms I: Axiomatization, Logical Methods in Computer Science, Vol. 3 (4:3) 2007, 1-29.
(with Andreas Blass, Yuri Gurevich and Dean Rosenzweig) Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem, Logical Methods in Computer Science, Vol. 3 (4:4) 2007, 1-35.
(with Yuri Gurevich and Wolfram Schulte) Semantic Essence of AsmL, Theoretical Computer Science, Volume 343, Issue 3, October 2005, 370-412.
(with Andreas Blass) Explicit Graphs with Extension Properties, Bulletin of the European Association for Theoretical Computer Science, Number 86 (June 2005), 166-175.
Existential Positive Types and Preservation under Homomorphisms, Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 467-476.