The discrepancy of a graph measures the maximum deviation of an induced subgraph from its expected size. I will talk about how to prove bounds on the discrepancy using semidefinite programming and spectral techniques.

With this, we:

(i) partially answer questions of Verstraete and Bollobás-Scott on positive and negative discrepancy;

(ii) greatly improve a result of Alon on the minimum bisection;

(iii) slightly improve Lovett’s bound on the log-rank conjecture.

Joint work with Eero Räty and Benny Sudakov.