{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T17:43:31Z","timestamp":1648662211721},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> The notion of average-case hardness is a fundamental one in complexity theory. In particular, it plays an important role in the research on derandomization, as there are general derandomization results which are based on the assumption that average-case hard functions exist. However, to achieve a complete derandomization, one usually needs a function which is extremely hard against a complexity class, in the sense that any algorithm in the class fails to compute the function on 1\/2 - 2<jats:sup>-\u03a9(n)<\/jats:sup> fraction of its n-bit inputs. Unfortunately, lower bound results are very rare and they are only known for very restricted complexity classes, and achieving such extreme hardness seems even more difficult. Motivated by this, we study the hardness against linear-size circuits of constant depth in this paper. We show that the parity function is extremely hard for them: any such circuit must fail to compute the parity function on at least 1\/2 - 2<jats:sup>-\u03a9(n)<\/jats:sup> fraction of inputs. <\/jats:p>","DOI":"10.1142\/s1793830910000851","type":"journal-article","created":{"date-parts":[[2011,1,17]],"date-time":"2011-01-17T08:21:26Z","timestamp":1295252486000},"page":"515-526","source":"Crossref","is-referenced-by-count":0,"title":["ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS"],"prefix":"10.1142","volume":"02","author":[{"given":"CHI-JEN","family":"LU","sequence":"first","affiliation":[{"name":"Institute of Information Science, Academia Sinica, Taipei, Taiwan"},{"name":"Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HSIN-LUNG","family":"WU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taipei University, Taipei County 237, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.029"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00046-1"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:15:57Z","timestamp":1565111757000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":5,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S1793830910000851"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000851","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}