5
$\begingroup$

I have seen instances of how the technique of epsilon biased sets can be used to construct hard functions against a circuit class - like how in the recent paper of Kane-Williams this was used to construct a hard function for the class of circuits of the form Majority-of-two-layers-of-Threshold-gates.

I was wondering if there is any past work where this object epsilon-biased-sets have been used as a proof technique for showing circuit lower bounds. (..I would be happy to get any reference along these lines that may strike your mind in relation to this...)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.