We show that hard sets S for NP must have exponential density, i.e. |S_=n| ≥ 2^{n^ε} for some ε > 0 and infinitely many n, unless coNP ⊆ NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n^1-ε queries.

In addition we study the instance ... more >>>

Given a set of observed economic choices, can one infer
preferences and/or utility functions for the players that are
consistent with the data? Questions of this type are called {\em
rationalization} or {\em revealed preference} problems in the
economic literature, and are the subject of a rich body of work.

... more >>>

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>