Mikhail Rudoy

According to our database, Mikhail Rudoy authored at least 17 papers between 2015 and 2022.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2022

Circumscribing Polygons and Polygonizations for Disjoint Line Segments.

Hugo A. Akitaya, Matias Korman, Oliver Korten, Mikhail Rudoy, Diane L. Souvaine, Csaba D. Tóth

Discret. Comput. Geom., 2022

Hardness of Token Swapping on Trees.

Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Yin-Yang Puzzles are NP-complete.

Erik D. Demaine, Jayson Lynch, Mikhail Rudoy, Yushi Uno

Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

2020

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible.

Zachary Abel, Jeffrey Bosboom, Michael J. Coulombe, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy, Clemens Thielen

Theor. Comput. Sci., 2020

Cookie Clicker.

Erik D. Demaine, Hiro Ito, Stefan Langerman, Jayson Lynch, Mikhail Rudoy, Kai Xiao

Graphs Comb., 2020

New Results in Sona Drawing: Hardness and TSP Separation.

Man-Kwun Chiu, Erik D. Demaine, Yevhenii Diomidov, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada, Mikhail Rudoy

Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

2019

Circumscribing Polygons and Polygonizations for Disjoint Line Segments.

Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, Csaba D. Tóth

Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018

A simple proof that the (<i>n</i>² - 1)-puzzle is hard.

Erik D. Demaine, Mikhail Rudoy

Theor. Comput. Sci., 2018

Tree-Residue Vertex-Breaking: a new tool for proving hardness.

Erik D. Demaine, Mikhail Rudoy

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Solving the Rubik's Cube Optimally is NP-complete.

Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Computational Complexity of Motion Planning of a Robot through Simple Gadgets.

Erik D. Demaine, Isaac Grosof, Jayson Lynch, Mikhail Rudoy

Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Computational Complexity of Generalized Push Fight.

Jeffrey Bosboom, Erik D. Demaine, Mikhail Rudoy

Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible.

Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy

Proceedings of the 9th International Conference on Fun with Algorithms, 2018

2017

A simple proof that the $(n^2-1)$-puzzle is hard.

Erik D. Demaine, Mikhail Rudoy

CoRR, 2017

Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs.

Erik D. Demaine, Mikhail Rudoy

CoRR, 2017

2015

Dissection with the Fewest Pieces is Hard, Even to Approximate.

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, Anak Yodpinyanee

Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Computational complexity of numberless Shakashaka.

Aviv Adler, Michael Biro, Erik D. Demaine, Mikhail Rudoy, Christiane Schmidt

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015