1. 7

I tried to submit this with the time-offset, but that got stripped somehow. The talk itself starts at 113 seconds.

  1. 3

    disclaimer: I’ve only watched the video but haven’t read any of the presenter’s work.

    this idea of setting up “circuits” in graph coloring problems is neat, but I’m curious what the research angle is. 4-coloring planar graphs is polynomial time on classical computers [1], so if we encode any of these NP-complete problems into a coloring circuit, the circuit itself must be exponential in the size of the problem. otherwise, we’d have a polynomial time solution.

    so, improving algorithms for coloring graphs won’t lead to a breakthrough, since the input size is already exponential. perhaps there’s some way of encoding graph coloring as a physical process?

    [1] https://en.wikipedia.org/wiki/Four_color_theorem#Simplification_and_verification

    1. 3

      The circuits that you create need not be planar, that’s why we make the change from colouring maps to colouring networks. That’s mentioned early in the video where we have the complete network on five nodes.

      So you are mistaken, the network size is only polynomial in the size of the instance of the problem, and a breakthrough in colouring would be important.

      1. 2

        ah, it’s not clear to me from the video that it’s necessary to go beyond planar graphs for completeness. the two examples given, AND and adder gates, are both planar. but perhaps NAND gates cannot be made into a planar circuit? or maybe there’s an issue with “circuit layout,” where even though each gate is planar, encoding an arbitrary boolean circuit requires sacrificing planarity?

        if planar graphs suffice, then my point still holds, where this construction would imply a polynomial time algorithm for NP problems. but if not, it’d be cool to see a “lower bound” result that shows how planarity doesn’t end up working out.

        1. 2

          The relevant observation here is that the inputs for the adder (say) are in the interior of the network, so getting “signals” into them requires crossing lines.

          There are results about trying to create planar equivalents, and they do (in some circumstances) grow exponentially.

    2. 2

      From the headline I had assumed this was going to be about Wang tiles.