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

Math @ Duke



Math HOME

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

Faculty

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

Publications of Benjamin Rossman    :chronological  by type  bibtex listing:

  1. 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]
  2. 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]
  3. 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]
  4. 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]
  5. 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]
  6. 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]
  7. 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]
  8. 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]
  9. 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]
  10. 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]
  11. 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]
  12. Rossman, B; Schwentick, T; Thérien, D; Vollmer, H, Circuits, Logic, and Games, Dagstuhl Seminar Proceedings, vol. 10061 (January, 2010)
  13. Rossman, B, Correlation bounds against monotone NC1, Leibniz International Proceedings in Informatics, LIPIcs, vol. 33 (June, 2015), pp. 392-411, ISBN 9783939897811 [doi]  [abs]
  14. Rossman, B, Criticality of regular formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 137 (July, 2019), ISBN 9783959771160 [doi]  [abs]
  15. 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]
  16. Rossman, B, Existential positive types and preservation under homomorphisms, Proceedings - Symposium on Logic in Computer Science (October, 2005), pp. 467-476  [abs]
  17. 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]
  18. Rossman, B, Formulas versus circuits for small distance connectivity, SIAM Journal on Computing, vol. 47 no. 5 (January, 2018), pp. 1986-2028 [doi]  [abs]
  19. 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]
  20. Rossman, B, Homomorphism preservation theorems, Journal of the ACM, vol. 55 no. 3 (July, 2008) [doi]  [abs]
  21. 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]
  22. 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]
  23. 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]
  24. 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]
  25. 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]
  26. 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]
  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, 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]
  29. 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]
  30. Gurevich, Y; Rossman, B; Schulte, W, Semantic essence of AsmL, Theoretical Computer Science, vol. 343 no. 3 (October, 2005), pp. 370-412 [doi]  [abs]
  31. 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]
  32. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Theory of Computing, vol. 15 (January, 2019) [doi]  [abs]
  33. Rossman, B; Srinivasan, S, Separation of AC0[⊕] formulas and circuits, Leibniz International Proceedings in Informatics, LIPIcs, vol. 80 (July, 2017), ISBN 9783959770415 [doi]  [abs]
  34. Rossman, B, Shrinkage of decision lists and DNF formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 185 (February, 2021), ISBN 9783959771771 [doi]  [abs]
  35. Rossman, B, Subspace-invariant AC0 formulas, Logical Methods in Computer Science, vol. 15 no. 3 (January, 2019), pp. 3:1-3:12 [doi]  [abs]
  36. Rossman, B, Subspace-invariant AC0 formulas, Leibniz International Proceedings in Informatics, LIPIcs, vol. 80 (July, 2017), ISBN 9783959770415 [doi]  [abs]
  37. Rossman, B, Successor-invariance in the finite, Proceedings - Symposium on Logic in Computer Science (January, 2003), pp. 148-157  [abs]
  38. 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]
  39. He, W; Rossman, B, Symmetric Formulas for Products of Permutations, Leibniz International Proceedings in Informatics, LIPIcs, vol. 251 (January, 2023), ISBN 9783959772631 [doi]  [abs]
  40. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Computational Complexity, vol. 27 no. 2 (June, 2018), pp. 209-223 [doi]  [abs]
  41. 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]
  42. Kopparty, S; Rossman, B, The homomorphism domination exponent, European Journal of Combinatorics, vol. 32 no. 7 (October, 2011), pp. 1097-1114 [doi]  [abs]
  43. 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]
  44. 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]
  45. 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]
  46. 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]
  47. 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]
  48. 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]
  49. 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]

 

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