Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-FeedNext next

TR19-125 | 27th August 2019
Elazar Goldenberg, Karthik C. S.

Hardness Amplification of Optimization Problems

In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products.

We say that an optimization problem $\Pi$ is direct product feasible if it is possible to efficiently aggregate any $k$ instances of $\Pi$ and form one large instance ... more >>>

TR19-124 | 28th August 2019
Roy Gotlib, Tali Kaufman

Testing Odd Direct Sums Using High Dimensional Expanders

In this work, using methods from high dimensional expansion, we show that the property of $k$-direct-sum is testable for odd values of $k$ . Previous work of Kaufman and Lubotzky could inherently deal only with the case that $k$ is even, using a reduction to linearity testing.
Interestingly, our work ... more >>>

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

Next next

ISSN 1433-8092 | Imprint