Benjamin Rossman
|
Contact Information:
Room G636 b(last name) at theory . csail . mit . edu |
Recent papers:
-
On the Constant-Depth Complexity of k-Clique, STOC 2008. (summary of the proof)
- Homomorphism Preservation Theorems, Journal of the ACM, July 2008.
Journal articles:
-
Successor-Invariant First-Order Logic on Finite
Structures,
Journal of Symbolic Logic, 72 (2007), pages 601-619.
-
An Optimal Decomposition Algorithm for Tree Edit Distance
with Erik Demaine, Shay Mozes and Oren Weimann, ACM Transactions on Algorithms, to appear.
-
Choiceless Polynomial Time, Counting and the
Cai-Furer-Immerman Graphs
with Anuj Dawar and David Richerby,
Annals of Pure and Applied Logic, 152 (2008), pages 31-50.
-
Explicit Graphs with Extension Properties
with Andreas Blass, Bulletin of the European Association for
Theoretical Computer Science, Number 86 (June 2005), pages 166-175.
-
Interactive Small-Step Algorithms I: Axiomatization
with Andreas Blass, Yuri Gurevich and Dean Rosenzweig,
Logical Methods in Computer Science, Volume 3, Issue 4, Paper 3.
-
Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem
with Andreas Blass, Yuri Gurevich and Dean Rosenzweig,
Logical Methods in Computer Science, Volume 3, Issue 4, Paper 4.
-
Semantic Essence of AsmL
with Yuri Gurevich and Wolfram Schulte, Theoretical Computer
Science, Volume 343, Issue 3, October 2005, pages 370-412.
(extended
abstract)
Conference papers:
-
An Optimal Decomposition Algorithm for Tree Edit Distance
with Erik Demaine, Shay Mozes and Oren Weimann, ICALP 2007.
-
Choiceless Polynomial Time, Counting and the
Cai-Fürer-Immerman Graphs (extended abstract)
with Anuj Dawar and David Richerby, Proceedings of the 12th
Workshop on Logic, Language, Information and Computation, pages 13-24, 2005.
(slides)
-
Existential Positive Types and Preservation under Homomorphisms
(extended abstract), Proceedings of the 20th IEEE Symposium on
Logic in Computer Science, pages 467-476, 2005. (slides)
-
Successor-Invariance in the Finite,
Proceedings of the 18th IEEE Symposium on Logic in Computer
Science, pages 148-157, 2003.
(slides 1,
slides 2)