5
$\begingroup$

I am currently exploring the application of the random restriction technique in proving lower bounds within the context of resolution proofs. I would like to know if there are any comprehensive tutorials, lecture notes, or survey papers that cover this topic specifically.

If you have any recommendations on foundational or recent resources that discuss how random restrictions have been used to establish lower bounds in resolution proofs, I would greatly appreciate it. Any pointers to key papers, authors, or specific techniques within this area would also be incredibly helpful.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Sections 5 and 6.3 of Paul Beame's Switching Lemma Primer (available e.g. here) covers the version of the switching lemma used in many proof complexity lower bounds (which is one way random restrictions are often used). It doesn't actually do the application to proof complexity, but it might still be a helpful resource.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.