enter search term and/or author name
Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part II
Eric Allender, Shafi Goldwasser
Article No.: 10
We study the online decision problem in which the set of available actions varies over time, also called the sleeping experts problem. We consider the setting in which the performance comparison is made with respect to the...
We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed-degree polynomial functions are evolvable in...
(Leveled) Fully Homomorphic Encryption without Bootstrapping
Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan
Article No.: 13
We present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled, fully...
On the One-Way Function Candidate Proposed by Goldreich
James Cook, Omid Etesami, Rachel Miller, Luca Trevisan
Article No.: 14
Goldreich  proposed a candidate one-way function based on a bipartite graph of small right-degree d, where the vertices on the left (resp. right) represent input (resp. output) bits of the function. Each output bit is computed by...