Adam Klivans, Alexander A. Sherstov

We give the first representation-independent hardness results for

PAC learning intersections of halfspaces, a central concept class

in computational learning theory. Our hardness results are derived

from two public-key cryptosystems due to Regev, which are based on the

worst-case hardness of well-studied lattice problems. Specifically, we

prove that a polynomial-time ...
more >>>

Nir Bitansky, Omer Paneth, Alon Rosen

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which ... more >>>

Pavel Hubacek, Eylon Yogev

Local search proved to be an extremely useful tool when facing hard optimization problems (e.g. via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts the optimization ... more >>>