We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = v} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources.
Our first method shows that ... more >>>

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky
[JACM'96] is a (possibly randomized) RAM, for which the memory access
pattern reveals no information about the operations
performed. The main performance metric of an ORAM is the bandwidth
overhead, i.e., the multiplicative factor extra memory blocks that must be
accessed ... more >>>

We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., ... more >>>