tag:blogger.com,1999:blog-3722233.post3605342482545718950..comments2024-11-08T03:41:35.200-06:00Comments on Computational Complexity: Instance CompressionLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-44051092020448624792012-08-14T15:44:26.510-05:002012-08-14T15:44:26.510-05:00I've written some revised/expanded notes respo...I've written some revised/expanded notes responding to Lance's post and describing/motivating my work, which you can find here in pdf: http://bit.ly/comp_notes <br /><br />Main points:<br />1) I'm grateful for Lance's kind words; OTOH, contra Lance, the quantum part of the paper is also interesting!<br /><br />2) The lemma on stability of distributions is not hard; also, there are similar earlier results from which it can be derived (as colleagues helped me understand).<br /><br />3) The use of SZK is not needed for my main result on hardness of compression for an AND of SAT instances. I do use properties of SZK to get improved hardness of (probabilistic) compression for OR-SAT, however.<br /><br />4) Since Lance posted, I found a proof of my "basic" result on AND-SAT that avoids using any information theory terms or results, and also avoids the minimax theorem. This modified proof is based on my original (though weaker quantitatively), but it also bears an interesting resemblance to Fortnow and Santhanam's work on OR-SAT.<br /><br />5) For readers of previous drafts: in my general result, I've also significantly simplified the way I handle the case of compression reductions with "large output size", i.e., output length O(t log t) for an input AND of t length-n SAT instances. I now use a unified proof that works for this and the "small-output case."Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.com