We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with ... more >>>

We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a ... more >>>

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is ... more >>>