Negative weights make adversaries stronger.

Peter Hyer, Troy Lee, Robert Spalek

Browse the full STOC paper archive.