Previous Conferences & Workshops

The computation of Nash equilibria has been a problem that spanned half a century that has attracted Economists, Operations Researchers, and most Recently, Computer Scientists. Intuitively, the complexity of a game grows along a few axes: the number...

I will present a result that shows hardness of weak PAC-learning intersection of two halfspaces using a hypothesis which is an intersection of k halfspaces for any (fixed) integer k. Specifically, for every integer k and an arbitrarily small...