Should it contain a detailed overview of my (recent?) publications?
NO. It should contain a detailed overview of your research program, including both your past accomplishments and your future plans/vision. Of course you have to describe your published results in technical detail, but as part of a larger narrative, not as stand-alone pieces. Focus on the big picture, not on the tiny technical details. Remember that your audience is not just other theoretical computer scientists.
If the answer to 1 is yes, should I highlight my specific contributions in multi-author papers - as opposed to "we proved this and that..." ?
NO. "My coauthors and I proved..." is fine. The public dogma in theoretical computer science is that in every paper, each of the authors contributed 100% of the work, which is why they are listed alphabetically. You own any paper that has your name on it. Your narrative will naturally focus on the parts of the paper that you are the most proud of, which are usually the parts that you worked on the most.
Of course, if you're writing papers with your advisor or other more senior coauthors, there is a natural tendency for people to wonder if your aren't really just riding their coattails. This is why you need a larger narrative in your statement—to convince the reader that you understand your results at a deeper level than someone who merely read the papers. This is also why you have papers with different sets of coauthors—so that the common thread through your work stands out as your contribution. In particular, you have at least one paper without your advisor. Right?
If the answer to 1 is yes, I must list the references here that I'm mentioning, which are also stated (in the full list of publications) in my CV, right?
The approach I always recommend is to treat your CV as your bibliography, and to include a footnote like "Numbered references indicate papers listed in my CV." Of course, this means that your research statement never cites anyone else's work, except in broad narrative strokes, but for a brief document intended to sell your research program, I think that's appropriate.
Assuming there's no page limit, what's an appropriate length for a research statement?
Aim for three pages. Less than two is too short. More than four is too long.
That may not seem like a lot of space, but that actually works in your favor. You want to give the impression that you've done just gobs of really amazingly cool stuff, but dammit there just isn't room to write about everything.
