Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Adversarial Robustness:
TR19-123 | 12th September 2019
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell

On the Hardness of Robust Classification

It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. ... more >>>

TR21-096 | 8th July 2021
Boaz Menuhin, Moni Naor

Keep That Card in Mind: Card Guessing with Limited Memory

A card guessing game is played between two players, Guesser and Dealer. At the beginning of the game, the Dealer holds a deck of $n$ cards (labeled $1, ..., n$). For $n$ turns, the Dealer draws a card from the deck, the Guesser guesses which card was drawn, and then ... more >>>

ISSN 1433-8092 | Imprint