4 papers
#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
Max Bannach, Erik D. Demaine, Timothy Gomez +1
The canonical class in the realm of counting complexity is #P. It is well known that the problem of counting the models of a propositional formula in disjunctive normal form (#DNF)…
Continuous Flattening and Reversing of Convex Polyhedral Linkages
Erik D. Demaine, Martin L. Demaine, Markus Hecher +3
We prove two results about transforming any convex polyhedron, modeled as a linkage L of its edges. First, if we subdivide each edge of L in half, then L can be continuously flatte…
Folding One Polyhedral Metric Graph into Another
Lily Chung, Erik D. Demaine, Martin L. Demaine +4
We analyze the problem of folding one polyhedron, viewed as a metric graph of its edges, into the shape of another, similar to 1D origami. We find such foldings between all pairs o…
Strong Structural Bounds for MaxSAT: The Fine Details of Using Neuromorphic and Quantum Hardware Accelerators
Max Bannach, Jai Grover, Markus Hecher
Hardware accelerators like quantum annealers or neuromorphic chips are capable of finding the ground state of a Hamiltonian. A promising route in utilizing these devices is via met…