Publications of Benjamin Rossman

  1. He, W; Rossman, B, Symmetric Formulas for Products of Permutations, Leibniz International Proceedings in Informatics, LIPIcs, vol. 251 (January, 2023), ISBN 9783959772631
  2. Kush, D; Rossman, B, TREE-DEPTH AND THE FORMULA COMPLEXITY OF SUBGRAPH ISOMORPHISM, SIAM Journal on Computing, vol. 52 no. 1 (January, 2023), pp. 273-325
  3. Cavalar, BP; Kumar, M; Rossman, B, Monotone Circuit Lower Bounds from Robust Sunflowers., Algorithmica, vol. 84 no. 12 (January, 2022), pp. 3655-3685
  4. Rossman, B, Shrinkage of decision lists and DNF formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 185 (February, 2021), ISBN 9783959771771
  5. 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
  6. Kush, D; Rossman, B, Tree-depth and the formula complexity of subgraph isomorphism, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2020-November (November, 2020), pp. 31-42, ISBN 9781728196213
  7. 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
  8. 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
  9. Rossman, B, Criticality of regular formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 137 (July, 2019), ISBN 9783959771160
  10. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Theory of Computing, vol. 15 (January, 2019)
  11. Rossman, B, Subspace-invariant AC0 formulas, Logical Methods in Computer Science, vol. 15 no. 3 (January, 2019), pp. 3:1-3:12
  12. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Computational Complexity, vol. 27 no. 2 (June, 2018), pp. 209-223
  13. 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
  14. Rossman, B, Formulas versus circuits for small distance connectivity, SIAM Journal on Computing, vol. 47 no. 5 (January, 2018), pp. 1986-2028
  15. 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
  16. 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
  17. 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)
  18. 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
  19. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Leibniz International Proceedings in Informatics, LIPIcs, vol. 80 (July, 2017), ISBN 9783959770415
  20. Rossman, B, Subspace-invariant AC0 formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 80 (July, 2017), ISBN 9783959770415
  21. 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
  22. Robere, R; Pitassi, T; Rossman, B; Cook, SA, Exponential Lower Bounds for Monotone Span Programs, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2016-December (December, 2016), pp. 406-415, ISBN 9781509039333
  23. 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
  24. Rossman, B; Servedio, RA; Tan, LY, An Average-Case Depth Hierarchy Theorem for Boolean Circuits, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2015-December (December, 2015), pp. 1030-1048, ISBN 9781467381918
  25. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2015-December (December, 2015), pp. 424-430, ISBN 9781467381918
  26. Rossman, B, Correlation bounds against monotone NC1, Leibniz International Proceedings in Informatics, LIPIcs, vol. 33 (June, 2015), pp. 392-411, ISBN 9783939897811
  27. Li, Y; Razborov, A; Rossman, B, On the AC0 complexity of subgraph isomorphism, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (December, 2014), pp. 344-353, ISBN 9781479965175
  28. Rossman, B, The monotone complexity of k-clique on random graphs, SIAM Journal on Computing, vol. 43 no. 1 (January, 2014), pp. 256-279
  29. 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
  30. 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
  31. 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
  32. Kopparty, S; Rossman, B, The homomorphism domination exponent, European Journal of Combinatorics, vol. 32 no. 7 (October, 2011), pp. 1097-1114
  33. 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 9783642150241
  34. Rossman, B; Schwentick, T; Thérien, D; Vollmer, H, Circuits, Logic, and Games, Dagstuhl Seminar Proceedings, vol. 10061 (January, 2010)
  35. Rossman, B, The monotone complexity of k-clique on random graphs, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (January, 2010), pp. 193-201, ISBN 9780769542447
  36. 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)
  37. 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 9783642022609
  38. Rossman, B, Homomorphism preservation theorems, Journal of the ACM, vol. 55 no. 3 (July, 2008)
  39. 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
  40. 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
  41. 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)
  42. 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)
  43. Rossman, B, Successor-invariant first-order logic on finite structures, Journal of Symbolic Logic, vol. 72 no. 2 (June, 2007), pp. 601-618
  44. 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 9783540734192
  45. 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
  46. Rossman, B, Existential positive types and preservation under homomorphisms, Proceedings - Symposium on Logic in Computer Science (October, 2005), pp. 467-476
  47. Gurevich, Y; Rossman, B; Schulte, W, Semantic essence of AsmL, Theoretical Computer Science, vol. 343 no. 3 (October, 2005), pp. 370-412
  48. 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
  49. Rossman, B, Successor-invariance in the finite, Proceedings - Symposium on Logic in Computer Science (January, 2003), pp. 148-157