2 papers
cs.LO2024
Parallel Play Saves Quantifiers
Marco Carmosino, Ronald Fagin, Neil Immerman +4
The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear o…
cs.CC2024
What Juris Hartmanis taught me about Reductions
Neil Immerman
I was a student of Juris Hartmanis at Cornell in the late 1970's. He believed that there was great potential in studying restricted reductions. I describe here some of his influenc…