Laboratory of Mathematical Logic at PDMI

Пятница, 30 декабря, комната 106. Начало в 17:30.

Докладчик: А. Куликов.

Тема: Non-uniform Hardness for NP via Black-Box Adversaries.

Abstract

Доклад по статье: Albert Atserias, ``Non-uniform Hardness for NP via Black-Box Adversaries''.

We may believe SAT does not have small Boolean circuits. But is it possible that some language with small circuits looks indistinguishable from SAT to every polynomial-time bounded adversary? We rule out this possibility. More precisely, assuming SAT does not have small circuits, we show that for every language A with small circuits, there exists a probabilistic polynomial-time algorithms that makes *black-box* queries to A, and produces, for a given input length, a Boolean formula on which A differs from SAT. A key step for obtaining this result is a new proof of the main result by Gutfreund, Shaltiel, and Ta-Shma reducing average-case hardness to worst-case hardness via uniform adversaries that know the algorithm they fool. The new adversary we construct has the feature of being black-box on the algorithm it fools, so it makes sense in the non-uniform setting as well. Our proof makes use of a refined analysis of the learning algorithm of Bshouty et al.