= Alexander A. Razborov
{c}
<Alexander A. Razborov> coauthored <Natural Proofs by Alexander A. Razborov and Steven Rudich> with <Steven Rudich>. They analyzed why many successful restricted-model <circuit lower bounds> do not straightforwardly establish strong lower bounds for general <Boolean circuits>.<Natural Proofs by Alexander A. Razborov and Steven Rudich>[§§1 and4]{ref}
Their framework separates a <constructive property of Boolean functions>, a <large property of Boolean functions> and a <useful property against a circuit class>. Together these can provide a statistical test contradicting a quantitatively strong <pseudorandom function family> assumption. The test for a <constructive property of Boolean functions> is measured against <truth table> size, not merely the number of <input> <bit>[bits]; that distinction is essential when stating the cryptographic hypothesis precisely.
Back to article page
