^November December – 2008

The study of ranking crosses many disciplines. Social choice theoreticians have been interested for centuries in finding a good way to rank a set of candidates. Econometricians have been asking for decades how people choose from (and more generally rank) alternative sets. More recently, information retrieval theoreticians and practitioners have been interested in ranking search query results. In verification, practitioners have been interested in ordering variable sets so as to reduce the time to detect software errors. These recent problems have been identified in both machine learning and combinatorial optimization communities. I will present my contribution on both fronts.

Randomized algorithms have been using measure concentration phenomena in countless cases, and in particular in dimension reduction and streaming. These tools have become a standard black box, and their computational aspects have been almost taken for granted. In recent work I have discovered an exciting and surprising new method for computing a standard dimension reduction algorithm (Johnson-Lindenstrauss) more efficiently than previously assumed. This method has been later used to speed up various standard high dimensional linear algebraic computations (such as SVD) and fueled increased collaboration between computer science and analysis. The main ingredient is the use of a Fast Fourier Transform and a type of uncertainty principle.

Getting the deterministic complexity closer to the best known randomized complexity is an important goal in algorithms and communication protocols. In this work, we investigate the case where instead of one input, the algorithmprotocol is given multiple inputs sampled independently from an arbitrary unknown distribution. We show that in this case a strong and generic derandomization result can be obtained by a simple argument.

Our method relies on extracting randomness from ``same-source'' product distributions, which are distributions generated from multiple independent samples from the same source. The extraction process succeeds even for arbitrarily low min-entropy, and is based on the order of the values and not on the values themselves (This may be seen as a generalization of the classical method of Von-Neumann extended by Elias for extracting randomness from a biased coin).

The tools developed in the paper are generic, and can be used elsewhere. We present applications to streaming algorithms, and to implicit probe search cite{FiatNaor93}. We also refine our method to handle product distributions, where the i'th sample comes from one of several arbitrary unknown distributions. This requires creating a new set of tools, which may also be of independent interest.

Joint work with Ariel Gabizon

The filesystem API of contemporary systems exposes programs to TOCTTOU (time of check to time of use) race-condition vulnerabilities, which occur between pairs of check/use system calls that involve a name of a file. Existing solutions either help programmers to detect such races (by pinpointing their location) or prevent them altogether (by altering the operating system). But the latter alternative is not prevalent, and the former is just the first step: programmers must still address TOCTTOU flaws within the limits of the existing API with which several important tasks cannot be safely accomplished in a portable straightforward manner. The recent "filesystem maze" attack further worsens the problem by allowing adversaries to deterministically win races and thus refuting the common perception that the risk is small. In the face of this threat, we develop a new algorithm that allows programmers to effectively aggregate a vulnerable pair of distinct system calls into a single operation that is executed "atomically". This is achieved by emulating one kernel functionality in user mode: the filepath resolution. The surprisingly simple resulting algorithm constitutes a portable solution to a large class of TOCTTOU vulnerabilities, without requiring modifications to the underlying operating system.

---

Joint work with Tomer Hertz (Microsoft Research), David Wagner (Berkeley), and Dilma Da Silva (IBM T.J. Watson Research Center). Based on http://www.usenix.org/events/fast08/tech/tsafrir.html USENIX File & Storage Technologies (FAST'08). Awarded best paper.