Now showing items 1-4 of 4

    • Covers have structure 

      Arbeitspapier
      Wunderlich, Henning
      We establish a new connection between the theory of Berge graphs (perfect graphs) and communication complexity. We discover a new class of square-free Berge graphs, the class of beautiful graphs, and make progress towards ...
    • Implicit characterizations of FPTIME and NC revisited 

      Arbeitspapier
      Niggl, Karl-Heinz; Wunderlich, Henning
      Various simplified or improved and partly corrected well-known implicit characterizations of the complexity classes FPTIME and \NC are presented. Primarily, the interest is in simplifying the required simulations of various ...
    • On span-Pcc and related classes in structural communication complexity 

      Arbeitspapier
      Wunderlich, Henning
      The complexity classes #P, #NP, min-P, max-P, opt-P and span-P are well known in structural complexity. We define analogous classes in (structural) communication complexity and study some of their properties, e.g. establishing ...
    • On Toda’s Theorem in structural communication complexity 

      Arbeitspapier
      Wunderlich, Henning
      We prove Toda’s Theorem in the context of structural communication complexity, i.e. PHcc Í BP · ÅPcc Í Pcc (#Pcc) = Pcc (PPcc). The class PSPACEcc was defined via alternating protocols with O(log n) many alternations. We ...