Seminar Upcoming

How can we generate a permutation of the numbers 1 through n so that it is hard to guess the next element given the history so far? The twist is that the generator of the permutation (the “Dealer”) has limited memory, while the “Guesser” has unlimited memory. With unbounded memory (actually n bits suffice), the Dealer can generate a truly random permutation where ln n is the expected number of correct guesses.

We will show tight bounds for the relationship between the guessing probability and the memory m required to generate the permutation. We suggest a method for an m-bit Dealer that operates in constant time per turn, and any Guesser can pick correctly only O(n/m + log m) cards in expectation. The method is fully transparent, requiring no hidden information from the Dealer (i.e., it is ”open book” or ”whitebox”).

We show that this bound is the best possible, even with secret memory. Specifically, for any m-bit Dealer, there is a (computationally powerful) Guesser that achieves Ω(n/m+log m) correct guesses in expectation. We point out that the assumption that the Guesser is computationally powerful is necessary: under cryptographic assumptions, there exists a low-memory Dealer that can fool any computationally bounded Guesser.

To appear in FOCS 2025.
https://arxiv.org/abs/2505.01287

Contrastive learning is a comparative-based learning paradigm in which labelers are given triplet queries (A,B,C) of data points, and answer whether in their opinion point A is “closer” to B than C, or vice versa. E.g. if a labeler is given three pictures (A = Lion, B = Tiger, C = Dog), they would say that a lion is closer to a tiger than to a dog. In this talk, we discuss the dimensionality of satisfying m contrastive learning constraints in an l_p metric. In particular, we answer the following question:

What is a sufficiently large dimension d, such that given any m (non-contradictory) constraints of the form “dist(A,B) < dist(A,C)", can we find an embedding into R^d such that all constraints are satisfied? (under the l_p distance). We show that e.g. for p=2 that d = Theta(sqrt(m)) is both necessary and sufficient. Relatedly, we use our techniques to answer the following natural question for the k-nearest neighbor problem: What is a sufficiently large dimension d, such that given any metric D on n points, can we find an embedding into R^d that preserves the k-nearest neighbors of each point of D? (under the l_p distance). We show that d = O~(poly(k)) is always sufficient. Our methods are a combination of combinatorial and algebraic techniques. At the heart of our algorithms is an analysis of a graph which we refer to as the constraint graph, whose properties are associated with the dimension bounds we obtain - and in particular, its arboricity (an important measure of density).