enter search term and/or author name
Introduction to the special issue on innovations in theoretical computer science 2012
Eric Allender, Shafi Goldwasser
Article No.: 8
We present a simple algorithm that approximates the product of n-by-n real matrices A and B. Let ‖AB‖F denote the Frobenius norm of AB, and b be a parameter determining the...
Sipser and Spielman (IEEE IT, ) showed that any c,d)-regular expander code with expansion parameter >¾ is decodable in linear time from a constant fraction of errors. Feldman et al. (IEEE IT, ) proved that...
Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann  and has many applications in classical computing. We...
High-confidence predictions under adversarial uncertainty
Article No.: 12
We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of...