Can the postdoc adviser withdraw our paper against my will? I'm a postdoc in Computer Science. Recently submitted a paper, co-authored with my adviser. I'm the first author, corresponding author and am primarily responsible for the content.

Less than a day before submission deadline my adviser asked me to withdraw the paper. There was no sign that he disagrees with submission before that. I was keeping him updated with the progress and asking for reviews. Today he gave me a list of unconvincing arguments why we should withdraw. When I refused, he said he'll use his legal authority to withdraw it. Does he have any legal authority to do this?

No ethics policy that I'm aware of links authorship rights with employment status. From what I know a co-author may chose to withdraw his co-authorship, but cannot ask a conference to withdraw the paper against the will of other authors. Anyone encountered such situations?

I have not signed any legal agreements regarding publication policy.
Yes, an academic paper cannot be published without the consent of all its authors (as JeffE pointed out in the comments), so any one author can prevent publication for any reason, with no appeal or recourse.  Of course it would be unethical to do so for a bad reason, such as settling a personal grudge, but there's plenty of scope for good reasons.  For example, just feeling that it's not yet ready is a fine reason.

If your advisor withdraws the paper, then there's nothing you can do about it.  It can't be published in its current form with him as an author without his permission, and you can't remove him as an author if his contributions merit authorship.  (If they genuinely don't, then you can and should remove him, but you'll have to deal with serious questions about why he was listed in the first place.  Be very cautious with this, since if other people agree with him that he deserves authorship, then trying to remove him will be a disaster for you.)

In principle, you could try to extract your own contributions from the paper and publish them as a singly-authored paper without him.  However, this may be difficult, or even impossible if there was enough joint work that cannot solely be attributed to either author.

In practice, you'll probably have to work with your advisor to fix the paper, so that you are both happy to publish it.  He presumably feels it's worth publishing after some more work, since otherwise he would remove his own name from it and wouldn't care what happened to it after that.  Hopefully you are both reasonable people and can come to some agreement.

In the meantime, if you can't convince him to proceed with the submission, I'd recommend withdrawing it yourself, since it looks more awkward if he does.  (It can look like you screwed up and your advisor had to step in to fix it.)  If he withdraws it, then you shouldn't try to stop him, since there's nothing you can say to the program committee that would help.  All you can do at that point is to make it more awkward and embarrassing for everyone, without changing the outcome, and I don't think it's in your interest to make a fuss.

I'm sympathetic, since it sounds like your advisor has put you in a frustrating situation.  He should have reviewed the paper earlier, or asked you to hold off on submitting it because he needed more time to review it.  However, his failure to be a helpful coauthor doesn't justify publishing the paper without his consent.