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

Math @ Duke



Math HOME

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

Faculty

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

Publications of Benjamin Rossman    :chronological  alphabetical  combined  bibtex listing:

Papers Published

  1. 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 [doi]  [abs]
  2. He, W; Rossman, B, Symmetric Formulas for Products of Permutations, Leibniz International Proceedings in Informatics, LIPIcs, vol. 251 (January, 2023), ISBN 9783959772631 [doi]  [abs]
  3. Cavalar, BP; Kumar, M; Rossman, B, Monotone Circuit Lower Bounds from Robust Sunflowers., Algorithmica, vol. 84 no. 12 (January, 2022), pp. 3655-3685 [doi]  [abs]
  4. Rossman, B, Shrinkage of decision lists and DNF formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 185 (February, 2021), ISBN 9783959771771 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  9. Rossman, B, Criticality of regular formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 137 (July, 2019), ISBN 9783959771160 [doi]  [abs]
  10. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Theory of Computing, vol. 15 (January, 2019) [doi]  [abs]
  11. Rossman, B, Subspace-invariant AC0 formulas, Logical Methods in Computer Science, vol. 15 no. 3 (January, 2019), pp. 3:1-3:12 [doi]  [abs]
  12. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Computational Complexity, vol. 27 no. 2 (June, 2018), pp. 209-223 [doi]  [abs]
  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 [doi]  [abs]
  14. Rossman, B, Formulas versus circuits for small distance connectivity, SIAM Journal on Computing, vol. 47 no. 5 (January, 2018), pp. 1986-2028 [doi]  [abs]
  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  [abs]
  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 [doi]  [abs]
  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) [doi]  [abs]
  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 [doi]  [abs]
  19. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Leibniz International Proceedings in Informatics, LIPIcs, vol. 80 (July, 2017), ISBN 9783959770415 [doi]  [abs]
  20. Rossman, B, Subspace-invariant AC0 formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 80 (July, 2017), ISBN 9783959770415 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  26. Rossman, B, Correlation bounds against monotone NC1, Leibniz International Proceedings in Informatics, LIPIcs, vol. 33 (June, 2015), pp. 392-411, ISBN 9783939897811 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  32. Kopparty, S; Rossman, B, The homomorphism domination exponent, European Journal of Combinatorics, vol. 32 no. 7 (October, 2011), pp. 1097-1114 [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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) [doi]  [abs]
  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 [doi]  [abs]
  38. Rossman, B, Homomorphism preservation theorems, Journal of the ACM, vol. 55 no. 3 (July, 2008) [doi]  [abs]
  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 [doi]  [abs]
  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 [doi]  [abs]
  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) [doi]  [abs]
  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) [doi]  [abs]
  43. 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]
  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 [doi]  [abs]
  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 [doi]  [abs]
  46. Rossman, B, Existential positive types and preservation under homomorphisms, Proceedings - Symposium on Logic in Computer Science (October, 2005), pp. 467-476  [abs]
  47. Gurevich, Y; Rossman, B; Schulte, W, Semantic essence of AsmL, Theoretical Computer Science, vol. 343 no. 3 (October, 2005), pp. 370-412 [doi]  [abs]
  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 [doi]  [abs]
  49. Rossman, B, Successor-invariance in the finite, Proceedings - Symposium on Logic in Computer Science (January, 2003), pp. 148-157  [abs]

 

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

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
Mathematics Home | Arts & Sciences | Duke University