If you can re-take the GREs without undue burden -- yes, re-take them. You'll feel better, knowing that you did everything you could have. (Why spend the rest of your life wondering about "what could have been"?) And, it might help you a little bit, by eliminating a potential red flag.
That said, even if you don't re-take the GREs, if you have great qualifications, you'll probably be fine. If you have great research experience, great letters, and the rest of your application package is strong, it's unlikely that the GREs will hurt you much. Great research experience and publications will almost always trump poor GREs.
What your bad GRE scores will do is raise the eyebrows of the reviewers. The reviewers may then read the rest of your application package (contact your references, etc.) that much more carefully, to try to understand why you bombed the GREs. For instance, if you bombed the verbal GREs, then reviewer might start wondering: can this person write? are they completely inarticulate? am I going to have to spend the next 5 years teaching them how to write and remedial English? And they'll peruse all available information to try to figure out what's going on. So, if you have any explanation (even if it's just "I screwed up and didn't take the GREs seriously; in retrospect, I know it was a dumb move"), it might not hurt to share this story with your letter-writers so one of them can slip that into their letter, to minimize that sort of speculation. The other approach is to mention it in your statement of purpose -- though for some people it may feel a bit less awkward if one of your letter-writers does it.
P.S. A 3.5 GPA is not a great GPA. It is very much on the low side, for PhD studies in a top-5 CS PhD program. Research experience that has led to publications, on the other hand, is great and a huge plus for your application file.