2 papers
cs.DS2024
Hardness Amplification for Dynamic Binary Search Trees
Shunhua Jiang, Victor Lecomte, Omri Weinstein +1
We prove direct-sum theorems for Wilber's two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the…
cs.LG2024
Backdoor defense, learnability and obfuscation
Paul Christiano, Jacob Hilton, Victor Lecomte +1
We introduce a formal notion of defendability against backdoors using a game between an attacker and a defender. In this game, the attacker modifies a function to behave differentl…