Publications of Benjamin Rossman

Papers Published

  1. Rossman, B, Shrinkage of decision lists and DNF formulas, Leibniz International Proceedings in Informatics, Lipics, vol. 185 (February, 2021), ISBN 9783959771771
  2. 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
  3. 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
  4. 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
  5. 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
  6. Rossman, B, Criticality of regular formulas, Leibniz International Proceedings in Informatics, Lipics, vol. 137 (July, 2019), ISBN 9783959771160
  7. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Theory of Computing, vol. 15 (January, 2019)
  8. Rossman, B, Subspace-invariant AC0 formulas, Logical Methods in Computer Science, vol. 15 no. 3 (January, 2019), pp. 3:1-3:12
  9. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Computational Complexity, vol. 27 no. 2 (June, 2018), pp. 209-223
  10. 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
  11. Rossman, B, Formulas versus circuits for small distance connectivity, Siam Journal on Computing, vol. 47 no. 5 (January, 2018), pp. 1986-2028
  12. 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
  13. 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
  14. 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)
  15. 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
  16. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Leibniz International Proceedings in Informatics, Lipics, vol. 80 (July, 2017), ISBN 9783959770415
  17. Rossman, B, Subspace-invariant AC0 formulas, Leibniz International Proceedings in Informatics, Lipics, vol. 80 (July, 2017), ISBN 9783959770415
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. Rossman, B, Correlation bounds against monotone NC1, Leibniz International Proceedings in Informatics, Lipics, vol. 33 (June, 2015), pp. 392-411, ISBN 9783939897811
  24. 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
  25. Rossman, B, The monotone complexity of k-clique on random graphs, Siam Journal on Computing, vol. 43 no. 1 (January, 2014), pp. 256-279
  26. 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
  27. 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
  28. 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
  29. Kopparty, S; Rossman, B, The homomorphism domination exponent, European Journal of Combinatorics, vol. 32 no. 7 (October, 2011), pp. 1097-1114
  30. 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
  31. 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
  32. 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)
  33. 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
  34. Rossman, B, Homomorphism preservation theorems, Journal of the Acm, vol. 55 no. 3 (July, 2008)
  35. 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
  36. 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
  37. 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)
  38. 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)
  39. Rossman, B, Successor-invariant first-order logic on finite structures, Journal of Symbolic Logic, vol. 72 no. 2 (June, 2007), pp. 601-618
  40. 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
  41. 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
  42. Rossman, B, Existential positive types and preservation under homomorphisms, Proceedings Symposium on Logic in Computer Science (October, 2005), pp. 467-476
  43. Gurevich, Y; Rossman, B; Schulte, W, Semantic essence of AsmL, Theoretical Computer Science, vol. 343 no. 3 (October, 2005), pp. 370-412
  44. 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
  45. Rossman, B, Successor-invariance in the finite, Proceedings Symposium on Logic in Computer Science (January, 2003), pp. 148-157