{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T17:21:42Z","timestamp":1648660902737},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2002,3]]},"abstract":"<jats:p> We study the parallel approximability of computing the number of true gates and false gates for circuits with only NOR gates, we refer to these problems as Nor-False Gates and Nor-True Gates Problems, respectively. We show that the parallel approximability of these problems depends on restrictions on the topology of the circuit. More precisely, for circuits with fan-in and fan-out bounded by a constant and having a constant number of output gates both problems exhibit a threshold behavior in their parllel approximability. Bounding only the number of outputs gives threshold results for the Nor-False Gates Problem but non-approximability (for any constant) for the Nor-True Gates Problem. For the case of unbounded number of outputs we show that none of the two problems can be approximated in parallel within any constant. We use the threshold result of False Gates Problem to identify a subclass of linear programming that also presents a threshold behavior in its parallel approximability. <\/jats:p>","DOI":"10.1142\/s0129626402000872","type":"journal-article","created":{"date-parts":[[2012,9,1]],"date-time":"2012-09-01T09:07:47Z","timestamp":1346490467000},"page":"127-136","source":"Crossref","is-referenced-by-count":0,"title":["THE PARALLEL APPROXIMABILITY OF THE FALSE AND TRUE GATES PROBLEMS FOR NOR-CIRCUITS"],"prefix":"10.1142","volume":"12","author":[{"given":"MARIA","family":"SERNA","sequence":"first","affiliation":[{"name":"Departament de LSI, Universitat Polit\u00e8cnica de Catalunya, M\u00f2dul C6 - Campus Nord, Jordi Girona Salgado, 1-3, 08034-Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FATOS","family":"XHAFA","sequence":"additional","affiliation":[{"name":"Departament de LSI, Universitat Polit\u00e8cnica de Catalunya, M\u00f2dul C6 - Campus Nord, Jordi Girona Salgado, 1-3, 08034-Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"p_1","first-page":"5","volume":"4","author":"Arora S.","year":"1998","journal-title":"Journal of ACM."},{"key":"p_3","first-page":"7","volume":"5","author":"Barland I.","year":"1998","journal-title":"J. Gompui. System Sci."},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90152-2"},{"issue":"3","key":"p_7","first-page":"573","volume":"22","author":"Kirousis L.","year":"1993","journal-title":"The Parallel Complexity of the Subgraph Connectivity Problem. SIAM Journal of Computing"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90194-M"},{"key":"p_12","first-page":"488","author":"Serna M.","year":"1998","journal-title":"Springer Verlag"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009209"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010007"},{"issue":"4","key":"p_15","first-page":"527","volume":"8","author":"Trevisan L.","year":"1998","journal-title":"The Parallel Complexity of Positive Linear Programming. Parallel Processing Letters"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626402000872","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:19:59Z","timestamp":1565093999000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626402000872"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,3]]},"references-count":10,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2002,3]]}},"alternative-id":["10.1142\/S0129626402000872"],"URL":"https:\/\/doi.org\/10.1142\/s0129626402000872","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,3]]}}}