{'fraction_non_alphanumeric': 0.024975984630163303, 'fraction_numerical': 0.0, 'mean_word_length': 4.725274725274725, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distinguishing SAT from polynomial-size circuits, through black-box queries

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