Zapman: one of the biggest myths out there is that you have to starve yourself to lose weight. This is simply not true; Andrew said something similar.
That's not just my say-so; there are literally thousands of experiments which have set out to prove that calorie-deficit high-carbohydrate dieting works, and every single one of them gives the same result: 10% or so get a good result, the majority lose nothing worth mentioning (a kilo over six months, say), and a few people actually gain weight. For some reason this surprises them every time, but there's no theoretical reason why it should work.
What you have to do - which should be fairly obvious - is to force your body to burn more fat than it stores over the long term. Eating fewer calories does not do that unless you literally starve yourself (<1200kcal/day). With a modest calorie deficit, your body just slows down your metabolism to conserve what it's got. The problem is that most people can't starve themselves. It's just too horrible.
It's a funny thing. Andrew obviously knows what he's talking about there - the results speak for themselves - but if you put him in a room with a bunch of registered dieticians, they'd all be arguing with him and telling him he's doing it wrong. There's a guy I work with who told me he's a qualified dietician and "eats healthy". He looks like any other middle-aged man: barrel-shaped with a belly flopping over his belt. I don't look like Andrew - mainly because I don't have his goals, but partly because I'm 20 years older than him. OTOH I can see my abs in outline if not in detail, and that's good enough for me.
When I'm deliberately losing fat, that's about what I aim for. I went from roughly 80kg to 70kg in four months. I don't care about yo-yo'ing; I fluctuate between maybe 69kg and 71kg depending on what mood I'm in. My opinion is that there is no 'ideal' diet. If we were eating what the seasons provide, we'd naturally eat more starches at certain times of year, which means extra bodyfat; at other times, we'd eat a lot more fat and green leaves because that's what's available. Yo-yo'ing, up to a point, is perfectly normal.
'complex carbs' have the same metabolic fate as 'bad sugar', although my personal experience is that you can eat a modest amount of the former (ie., without getting obsessed about it, as Andrew said) and still not get fat.
You don't need carbs. Nobody ever died of carbohydrate deficiency. Remove the fat or protein from your diet, though, and you'll be seriously ill, or worse.