Tyson Williams

  1. Gadgets and Anti-gadgets Leading to a Complexity Dichotomy.

    Authors: Michael Kowalczyk, Jin-Yi Cai, Tyson Williams
    Subjects: Computational Complexity
    Abstract

    We introduce an idea called anti-gadgets in complexity reductions. These
    combinatorial gadgets have the effect of erasing the presence of some other
    graph fragment, as if we had managed to include a negative copy of a graph
    gadget.

Syndicate content