1 citations · 1 across the 4 of their papers we have counts for
5 papers
Who Wins the Multi-Structural Game?
Ronald Fagin, Neil Immerman, Phokion Kolaitis +2
Combinatorial games played between two players, called Spoiler and Duplicator, have often been used to capture syntactic properties of formal logical languages. For instance, the w…
On the Number of Quantifiers Needed to Define Boolean Functions
Marco Carmosino, Ronald Fagin, Neil Immerman +3
The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binar…
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…
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…
A Characterization of the Complexity of Resilience and Responsibility for Self-join-free Conjunctive Queries
Cibele Freire, Wolfgang Gatterbauer, Neil Immerman +1
Several research thrusts in the area of data management have focused on understanding how changes in the data affect the output of a view or standing query. Example applications ar…