Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT) - Special issue on innovations in theoretical computer science 2012 - Part II, Volume 6 Issue 3, July 2014

Introduction to the Special Issue on Innovations in Theoretical Computer Science 2012 - Part II
Eric Allender, Shafi Goldwasser
Article No.: 10
DOI: 10.1145/2638595

Learning Hurdles for Sleeping Experts
Varun Kanade, Thomas Steinke
Article No.: 11
DOI: 10.1145/2505983

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...

Evolvability of Real Functions
Paul Valiant
Article No.: 12
DOI: 10.1145/2633598

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
DOI: 10.1145/2633600

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
DOI: 10.1145/2633602

Goldreich [2000] 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...