We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs capture the common description of LOGSPACE algorithms as programs that take as input some structured data (e.g. a graph) and that store in memory only a constant number of pointers to the input (e.g. to the ... more >>>

Abstract. We study the decision theory of a maximally risk-averse investor | one whose objec-
tive, in the face of stochastic uncertainties, is to minimize the probability of ever going broke. With
a view to developing the mathematical basics of such a theory, we start with a very simple model
more >>>

We consider the task of testing properties of Boolean functions that
are invariant under linear transformations of the Boolean cube. Previous
work in property testing, including the linearity test and the test
for Reed-Muller codes, has mostly focused on such tasks for linear
properties. The one exception is a test ... more >>>