---
res:
  bibo_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].@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: 'Faisal N. '
      foaf_name: 'Abu-Khzam, Faisal N. '
      foaf_surname: Abu-Khzam
  - foaf_Person:
      foaf_givenName: Shouwei
      foaf_name: Li, Shouwei
      foaf_surname: Li
  - foaf_Person:
      foaf_givenName: Christine
      foaf_name: Markarian, Christine
      foaf_surname: Markarian
      foaf_workInfoHomepage: http://www.librecat.org/personId=37612
  - foaf_Person:
      foaf_givenName: Friedhelm
      foaf_name: Meyer auf der Heide, Friedhelm
      foaf_surname: Meyer auf der Heide
      foaf_workInfoHomepage: http://www.librecat.org/personId=15523
  - foaf_Person:
      foaf_givenName: Pavel
      foaf_name: Podlipyan, Pavel
      foaf_surname: Podlipyan
  bibo_doi: 10.1007/978-3-319-42634-1_8
  dct_date: 2016^xs_gYear
  dct_language: eng
  dct_title: The Monotone Circuit Value Problem with Bounded Genus Is in NC@
...