Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications of Benjamin Rossman    :recent first  alphabetical  by type  bibtex listing:

  1. Rossman, B, Successor-invariance in the finite, Proceedings Symposium on Logic in Computer Science (January, 2003), pp. 148-157  [abs]
  2. Gurevich, Y; Rossman, B; Schulte, W, Semantic essence of asml: Extended abstract, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3188 (January, 2004), pp. 240-259 [doi]  [abs]
  3. Gurevich, Y; Rossman, B; Schulte, W, Semantic essence of AsmL, Theoretical Computer Science, vol. 343 no. 3 (October, 2005), pp. 370-412 [doi]  [abs]
  4. Rossman, B, Existential positive types and preservation under homomorphisms, Proceedings Symposium on Logic in Computer Science (October, 2005), pp. 467-476  [abs]
  5. Dawar, A; Richerby, D; Rossman, B, Choiceless polynomial time, counting and the cai-fürer-immerman graphs: (Extended abstract), Electronic Notes in Theoretical Computer Science, vol. 143 no. SPEC. ISS. (January, 2006), pp. 13-26 [doi]  [abs]
  6. Demaine, ED; Mozes, S; Rossman, B; Weimann, O, An optimal decomposition algorithm for tree edit distance, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4596 LNCS (January, 2007), pp. 146-157, ISBN 3540734198 [doi]  [abs]
  7. Rossman, B, Successor-invariant first-order logic on finite structures, Journal of Symbolic Logic, vol. 72 no. 2 (June, 2007), pp. 601-618 [doi]  [abs]
  8. Blass, A; Gurevich, Y; Rosenzweig, D; Rossman, B, Interactive small-step algorithms I: Axiomatization, Logical Methods in Computer Science, vol. 3 no. 4 (November, 2007) [doi]  [abs]
  9. Blass, A; Gurevich, Y; Rosenzweig, D; Rossman, B, Interactive small-step algorithms II: Abstract state machines and the characterization theorem, Logical Methods in Computer Science, vol. 3 no. 4 (November, 2007) [doi]  [abs]
  10. Rossman, B, On the constant-depth complexity of k-clique, Proceedings of the Annual Acm Symposium on Theory of Computing (January, 2008), pp. 721-730, ISBN 9781605580470 [doi]  [abs]
  11. Dawar, A; Richerby, D; Rossman, B, Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs, Annals of Pure and Applied Logic, vol. 152 no. 1-3 (March, 2008), pp. 31-50 [doi]  [abs]
  12. Rossman, B, Homomorphism preservation theorems, Journal of the Acm, vol. 55 no. 3 (July, 2008) [doi]  [abs]
  13. Rossman, B, Ehrenfeucht-Fraïssé Games on Random Structures, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5514 LNAI (August, 2009), pp. 350-364, ISBN 364202260X [doi]  [abs]
  14. Demaine, ED; Mozes, S; Rossman, B; Weimann, O, An optimal decomposition algorithm for tree edit distance, Acm Transactions on Algorithms, vol. 6 no. 1 (December, 2009) [doi]  [abs]
  15. Rossman, B, The monotone complexity of k-clique on random graphs, Annual Symposium on Foundations of Computer Science (Proceedings) (January, 2010), pp. 193-201, ISBN 9780769542447 [doi]  [abs]
  16. Rossman, B, Choiceless computation and symmetry, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6300 LNCS (September, 2010), pp. 565-580, ISBN 3642150241 [doi]  [abs]
  17. Kopparty, S; Rossman, B, The homomorphism domination exponent, European Journal of Combinatorics, vol. 32 no. 7 (October, 2011), pp. 1097-1114 [doi]  [abs]
  18. Rossman, B, A tight upper bound on the number of variables for average-case k-clique on ordered graphs, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7456 LNCS (September, 2012), pp. 282-290, ISBN 9783642326202 [doi]  [abs]
  19. Rossman, B, The monotone complexity of k-clique on random graphs, Siam Journal on Computing, vol. 43 no. 1 (January, 2014), pp. 256-279 [doi]  [abs]
  20. Rossman, B, Formulas vs. circuits for small distance connectivity, Proceedings of the Annual Acm Symposium on Theory of Computing (January, 2014), pp. 203-212, ISBN 9781450327107 [doi]  [abs]
  21. Kawachi, A; Rossman, B; Watanabe, O, The query complexity of witness finding, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8476 LNCS (January, 2014), pp. 218-231, ISBN 9783319066851 [doi]  [abs]
  22. Li, Y; Razborov, A; Rossman, B, On the AC0 complexity of subgraph isomorphism, Annual Symposium on Foundations of Computer Science (Proceedings) (December, 2014), pp. 344-353, ISBN 9781479965175 [doi]  [abs]
  23. Rossman, B, Correlation bounds against monotone NC1, Leibniz International Proceedings in Informatics, Lipics, vol. 33 (June, 2015), pp. 392-411, ISBN 9783939897811 [doi]  [abs]
  24. Rossman, B; Servedio, RA; Tan, LY, An Average-Case Depth Hierarchy Theorem for Boolean Circuits, Annual Symposium on Foundations of Computer Science (Proceedings), vol. 2015-December (December, 2015), pp. 1030-1048, ISBN 9781467381918 [doi]  [abs]
  25. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Annual Symposium on Foundations of Computer Science (Proceedings), vol. 2015-December (December, 2015), pp. 424-430, ISBN 9781467381918 [doi]  [abs]
  26. Pitassi, T; Rossman, B; Tan, LY; Servedio, RA, Poly-logarithmic Frege depth lower bounds via an expander switching lemma, Proceedings of the Annual Acm Symposium on Theory of Computing, vol. 19-21-June-2016 (June, 2016), pp. 644-657, ISBN 9781450341325 [doi]  [abs]
  27. Robere, R; Pitassi, T; Rossman, B; Cook, SA, Exponential Lower Bounds for Monotone Span Programs, Annual Symposium on Foundations of Computer Science (Proceedings), vol. 2016-December (December, 2016), pp. 406-415, ISBN 9781509039333 [doi]  [abs]
  28. Li, Y; Razborov, A; Rossman, B, On the AC0 complexity of subgraph isomorphism, Siam Journal on Computing, vol. 46 no. 3 (January, 2017), pp. 936-971 [doi]  [abs]
  29. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Leibniz International Proceedings in Informatics, Lipics, vol. 80 (July, 2017), ISBN 9783959770415 [doi]  [abs]
  30. Rossman, B, Subspace-invariant AC0 formulas, Leibniz International Proceedings in Informatics, Lipics, vol. 80 (July, 2017), ISBN 9783959770415 [doi]  [abs]
  31. Håstad, J; Rossman, B; Servedio, RA; Tan, LY, An average-case depth hierarchy theorem for boolean circuits, Journal of the Acm, vol. 64 no. 5 (August, 2017) [doi]  [abs]
  32. Kawachi, A; Rossman, B; Watanabe, O, The Query Complexity of Witness Finding, Theory of Computing Systems, vol. 61 no. 2 (August, 2017), pp. 305-321 [doi]  [abs]
  33. Rossman, B, An improved homomorphism preservation theorem from lower bounds in circuit complexity, Leibniz International Proceedings in Informatics, Lipics, vol. 67 (November, 2017), ISBN 9783959770293 [doi]  [abs]
  34. Kawarabayashi, KI; Rossman, B, A polynomial excluded-minor approximation of treedepth, Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms (January, 2018), pp. 234-246, ISBN 9781611975031 [doi]  [abs]
  35. Rossman, B, Formulas versus circuits for small distance connectivity, Siam Journal on Computing, vol. 47 no. 5 (January, 2018), pp. 1986-2028 [doi]  [abs]
  36. Rossman, B, Lower bounds for subgraph isomorphism, Proceedings of the International Congress of Mathematicians, Icm 2018, vol. 4 (January, 2018), pp. 3443-3464, ISBN 9789813272934  [abs]
  37. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Computational Complexity, vol. 27 no. 2 (June, 2018), pp. 209-223 [doi]  [abs]
  38. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Theory of Computing, vol. 15 (January, 2019) [doi]  [abs]
  39. Rossman, B, Subspace-invariant AC0 formulas, Logical Methods in Computer Science, vol. 15 no. 3 (January, 2019), pp. 3:1-3:12 [doi]  [abs]
  40. Rossman, B, Criticality of regular formulas, Leibniz International Proceedings in Informatics, Lipics, vol. 137 (July, 2019), ISBN 9783959771160 [doi]  [abs]
  41. Rossman, B, Thresholds in the Lattice of Subspaces of Fqn, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12118 LNCS (January, 2020), pp. 504-515, ISBN 9783030617912 [doi]  [abs]
  42. Cavalar, BP; Kumar, M; Rossman, B, Monotone Circuit Lower Bounds from Robust Sunflowers, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12118 LNCS (January, 2020), pp. 311-322, ISBN 9783030617912 [doi]  [abs]
  43. Kush, D; Rossman, B, Tree-depth and the formula complexity of subgraph isomorphism, Annual Symposium on Foundations of Computer Science (Proceedings), vol. 2020-November (November, 2020), pp. 31-42, ISBN 9781728196213 [doi]  [abs]
  44. Kawarabayashi, KI; Rossman, B, A polynomial excluded-minor approximation of treedepth, Journal of the European Mathematical Society, vol. 24 no. 4 (January, 2021), pp. 1449-1470 [doi]  [abs]
  45. Rossman, B, Shrinkage of decision lists and DNF formulas, Leibniz International Proceedings in Informatics, Lipics, vol. 185 (February, 2021), ISBN 9783959771771 [doi]  [abs]

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320