3 papers
cs.CG2026
Overlapping Unfoldings of Cones and Convex Polyhedra
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +4
Research on Dürer's problem focuses on edge unfoldings of convex polyhedra that avoid overlap. We invert the goal and find unfoldings that overlap at some point to any given thickn…
cs.FL2025
Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
Karolina Drabik, Anita Dürr, Fabian Frei +2
In the field of computational logic, two classes of finite automata are considered fundamental: deterministic and nondeterministic automata (DFAs and NFAs). In a more fine-grained…
cs.DS2024
Tree Coloring: Random Order and Predictions
Fabian Frei, Matthias Gehnen, Dennis Komm +4
Coloring is a notoriously hard problem, and even more so in the online setting, where each arriving vertex has to be colored immediately and irrevocably. Already on trees, which ar…