We introduce a new methodology for two-sample testing of high-dimensional linear regression coefficients without assuming that those coefficients are individually estimable. The procedure works by first projecting the matrices of covariates and response vectors along directions that are complementary in sign in a subset of the coordinates, a process which we call ‘complementary sketching’. The resulting projected covariates and responses are aggregated to form two test statistics. We show that our procedure has essentially optimal asymptotic power under Gaussian designs with a general class of design covariance matrices when the difference between the two regression coefficients is sparse and dense respectively. Simulations confirm that our methods perform well in a broad class of settings.