Joel Spencer

SODA Conference 2010 Conference Paper

Synchrony and Asynchrony in Neural Networks

• Fabian Kuhn
• Konstantinos Panagiotou
• Joel Spencer
• Angelika Steger

SODA Conference 2008 Conference Paper

Deterministic random walks on regular trees

• Joshua N. Cooper
• Benjamin Doerr
• Tobias Friedrich 0001
• Joel Spencer

TCS Journal 2004 Journal Article

A Halfliar's game

• Ioana Dumitriu
• Joel Spencer

In Ulam's game Paul tries to find one of n possibilities with q yes–no questions, while responder Carole is allowed to lie a fixed number k of times. We consider an asymmetric variant in which Carole must say yes when that is the correct answer (whence the halflie). We show that this variation allows Paul to distinguish between roughly 2 k as many possibilities as in Ulam's game.

FOCS Conference 2002 Conference Paper

On the (non)Universality of the One-Time Pad

• Yevgeniy Dodis
• Joel Spencer

Randomization is vital in cryptography: secret keys should be randomly generated and most cryptographic primitives (e. g. , encryption) must be probabilistic. We initiate the quantitative study concerning feasibility of building secure cryptographic primitives using imperfect random sources. Specifically, we concentrate on symmetric-key encryption and message authentication, where the shared secret key comes from an imperfect random source instead of being assumed truly random. In each case, we compare the class of "cryptographic" sources for the task at hand with the classes of "extractable" and "simulatable" sources, where: (1) "cryptographic" refers to sources for which the corresponding symmetric-key primitive can be built; (2) "extractable" refers to a very narrow class of sources from which one can extract nearly perfect randomness; and (3) "simulatable" refers to a very general class of weak random sources which are known to suffice for BPP simulation. For both encryption and authentication, we show that the corresponding cryptographic sources lie strictly in between extractable and simulatable sources, which implies that "cryptographic usage" of randomness is more demanding than the corresponding "algorithmic usage", but still does not require perfect randomness. Interestingly, cryptographic sources for encryption and authentication are also quite different from each other, which suggests that there might not be an elegant way to describe imperfect sources sufficient for "general cryptographic use". We believe that our initial investigation in this new area will inspire a lot of further research.

SODA Conference 1992 Conference Paper

The Probabilistic Method

• Joel Spencer

TCS Journal 1992 Journal Article

Ulam's searching game with a fixed number of lies

• Joel Spencer

Paul tries to find an unknown x from l to n by asking q Yes-No questions. In response Carole may lie up to k times. For k fixed and n, q sufficiently large, necessary and sufficient conditions are given for Paul to win.

STOC Conference 1987 Conference Paper

Threshold Spectra for Random Graphs

• Saharon Shelah
• Joel Spencer

STOC Conference 1978 Conference Paper

Coping with Errors in Binary Search Procedures (Preliminary Report)

• Ronald L. Rivest
• Albert R. Meyer
• Daniel J. Kleitman
• Karl Winklmann
• Joel Spencer

We consider the problem of identifying an unknown value xε{1,2,...,n} using only comparisons of x to constants when as many as E of 'the comparisons may receive erroneous answers. For a continuous analogue of this problem we show that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log 2 n+E.log 2 log 2 n+O(E.log 2 E) comparisons in the worst case. This number is shown to be optimal even if arbitrary “Yes-No” questions are allowed. We show that a modified version of this search problem with errors is equivalent to the problem of finding the minimal root of a set of increasing functions. The modified version is then also shown to be of complexity log 2 n+E.log 2 log 2 n+0(E.log 2 E).