Mark Bun (Boston University)
Calvin Lab Auditorium
A recent line of work has shown a qualitative equivalence between learnability in the differentially private PAC model and in Littlestone's online mistake-bound model. I will discuss this connection, highlighting a general compilation technique from binary classification to multiclass classification. Joint work with Marco Gaboardi and Satchit Sivakumar.