Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Varun Kanade:

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

TR11-115 | 8th August 2011
Varun Kanade, Thomas Steinke

Learning Hurdles for Sleeping Experts

We study the online decision problem where the set of available actions varies over time, also called the sleeping experts problem. We consider the setting where the performance comparison is made with respect to the best ordering of actions in hindsight. In this paper, both the payoff function and the ... more >>>

TR11-114 | 8th August 2011
Varun Kanade

Computational Bottlenecks for Evolvability

Valiant (2007) proposed a computational model for evolution and suggested that evolvability be studied in the framework of computational learning theory. Feldman (2008) showed that Valiant’s evolution model is equivalent to the correlational statistical query (CSQ) learning model, which is a restricted setting of the statistical query (SQ) model. Evolvability ... more >>>

ISSN 1433-8092 | Imprint