Halfspaces are hard to test with relative error.

Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang

Browse the full SODA paper archive.