The monotone circuit value problem with bounded genus is in NC

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Makarian, Chrisitne
dc.contributor.author Li, Shouwei
dc.contributor.author Podlipyan, Pavel
dc.date.accessioned 2017-03-22T12:42:17Z
dc.date.available 2017-03-22T12:42:17Z
dc.date.issued 2017-03-22
dc.identifier.uri http://hdl.handle.net/10725/5416
dc.description.abstract We present an efficient parallel algorithm for the general Monotone Circuit Value Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm generalizes a recent result by Limaye et al. who showed that MCVP with toroidal embedding (genus 1) is in NC when the input contains a toroidal embedding of the circuit. In addition to extending this result from genus 1 to any bounded genus k, and unlike the work reported by Limaye et al., we do not require a precomputed embedding to be given. Most importantly, our results imply that given a P-complete problem, it is possible to find an algorithm that makes the problem fall into NC by fixing one or more parameters. Hence, we deduce the interesting analogy: Fixed Parameter Parallelizable (FPP) is with respect to P-complete what Fixed Parameter Tractable (FPT) is with respect to NP-complete. Similar work that uses treewidth as parameter was also presented by Elberfeld et al. in [6]. This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Center “On-The-Fly Computing” (SFB 901) and the International Graduate School “Dynamic Intelligent Systems”. en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.title The monotone circuit value problem with bounded genus is in NC en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.doi http://dx.doi.org/10.1007/978-3-319-42634-1_8 en_US
dc.identifier.ctation Abu-Khzam, F. N., Li, S., Markarian, C., auf der Heide, F. M., & Podlipyan, P. (2016, August). The monotone circuit value problem with bounded genus is in NC. In International Computing and Combinatorics Conference (pp. 92-102). Springer International Publishing. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date August 2-4, 2016 en_US
dc.conference.pages 92-102 en_US
dc.conference.place Ho Chi Minh City, Vietnam en_US
dc.conference.title International Computing and Combinatorics Conference en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://link.springer.com/chapter/10.1007/978-3-319-42634-1_8 en_US
dc.author.affiliation Lebanese American University en_US
dc.title.volume Computing and Combinatorics en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account