tag:blogger.com,1999:blog-3722233.post526942839734075745..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: Fooling Constant-Depth CircuitsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-60486921264624416142009-01-26T11:28:00.000-06:002009-01-26T11:28:00.000-06:00What are consequences and applications of this res...What are consequences and applications of this result?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78711053173210958202009-01-25T00:27:00.000-06:002009-01-25T00:27:00.000-06:00Dear Lance, here is a problem (perhaps silly) that...Dear Lance, here is a problem (perhaps silly) that comes to mind: Is the conclusion of the Linial-Nisan conjecture (=Braverman’s result) holds for monotone threshold circuits, namely for bounded depth circuits with (monotone) threshold gates?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15737868507123003502009-01-24T12:23:00.000-06:002009-01-24T12:23:00.000-06:00Should this result now be known as "Braverman's Th...Should this result now be known as "Braverman's Theorem"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19309062079559250062009-01-23T10:30:00.000-06:002009-01-23T10:30:00.000-06:00Thanks. Fixed.Thanks. Fixed.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60258727682425481932009-01-23T10:17:00.000-06:002009-01-23T10:17:00.000-06:00Actually the result requires r = (log m) to the O(...Actually the result requires r = (log m) to the O(d^2) independence for depth d.Anonymousnoreply@blogger.com