On the Impossibility of Separating Intelligence from Judgment: the Computational Intractability of Filtering for AI Alignment

With the increased deployment of large language models LLMs, one concern is their potential misuse for generating harmful content. Our work studies the alignment challenge, with a focus on filters to prevent the generation of unsafe information. Two natural points of intervention are the filterin...

Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations

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$...

A Cryptographic Perspective on Mitigation Vs. Detection in Machine Learning

In this paper, we initiate a cryptographically inspired theoretical study of detection versus mitigation of adversarial inputs produced by attackers of Machine Learning algorithms during inference time. We formally define defense by detection DbD and defense by mitigation DbM. Our definitions com...