Krdytkyu

I have just received my reviews for a paper I submitted to a CS conference. I would like to address the concerns of the reviewers, but doing so would require adding new results. For example, if Reviewer 2 says, "This method looks great, but it lacks X and Y evaluations", am I allowed to perform that evaluation and say, "Thank you for this feedback. We totally agree. We have run X and Y evaluations and can include it in the final copy."

I can do this extra work, but adding such evaluations would represent a modification to the final paper—in my case, probably adding one plot and one table of evaluations.

I've only submitted to journals before, in which case the above was the norm. In the context of a CS conference, it is not clear whether or not I can modify the paper in this way.

You should check the conference's policy on rebuttals.
In general, you can add results in the rebuttal, but they may or may not be ignored. A rebuttal should be equivalent to a minor revision, not a major revision. That said, there is not much harm in trying as an author to promise more in the rebuttal.

The problem is that rebuttals sometimes promise amazing improvements to the paper, but there is no way for the conference program committee to evaluate the promised improvements before making an accept/reject decision. So the general policy is that authors should ensure that the original submission is up to scratch and not rely on the rebuttal to make major improvements. Reviewers are instructed to evaluate the submitted paper on its own merits.

In your case, the reviewer has explicitly asked for something -- that is a clear license to provide it. If space allows, you can include that in the rebuttal and promise to add that to the final version of the paper.

This may depend on the conference. You can contact the program or conference chair for guidance. However, I suspect that the answer will be yes. They want high quality papers presented in the conference and in the proceedings, which is why you get reviewer feedback not just an acceptance/rejection decision.

But don't expand the length of the paper too much or change its structure more than necessary. If you do, it may need additional review, and then you run up against conference deadlines which might result in rejection.

But it is the committee that decides these things, not consensus here. Ask.

And it is probably best not to think of the changes as a "rebuttal". Disputing the referees is a bad choice to include in a paper, though I realize you aren't suggesting that. Revisions is a better way to think of it than rebuttal.

But note that the referees are offering advice, not instructions. You are free to accept or reject that advice. But you should neither just ignore it, nor dispute it (in the paper). Just use the advice to improve the paper as you see fit.