Erik Demaine's Papers
Papers are grouped into
Books, Journal articles, Book chapters, Conference papers, Technical reports, Manuscripts, PhD thesis, and Master's thesis.
- Games, Puzzles, and Computation
(joint work with Robert A. Hearn)
A K Peters, July 2009.
- A Lifetime of Puzzles
(edited with Martin Demaine and Tom Rodgers)
A K Peters, October 2008.
- Geometric Folding Algorithms: Linkages, Origami, Polyhedra
(joint work with Joseph O'Rourke)
Cambridge University Press, July 2007.
- Tribute to a Mathemagician
(edited with Barry Cipra, Martin L. Demaine, and Tom Rodgers)
A K Peters, November 2004.
- Snipperclips: Cutting Tools into Desired Polygons using Themselves
(joint work with Zachary Abel, Hugo Akitaya, Man-Kwun Chiu, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jayson Lynch, André van Renssen, and Marcel Roeloffzen)
Computational Geometry: Theory and Applications, to appear.
- Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers
(joint work with Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Vida Dujmović, Robin Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, and Vera Sacristán)
Algorithmica, volume 83, number 5, 2021, pages 1316–1351.
- Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases
(joint work with Zachary Abel, Martin L. Demaine, Jason S. Ku, Jayson Lynch, Jin-ichi Itoh, and Chie Nara)
Computational Geometry: Theory and Applications, volume 98, October 2021, Article 101773.
- Folding Polyominoes with Holes into a Cube
(joint work with Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, Irina Kostitsyna, Maarten Löffler, Zuzana Masárová, Klara Mundilova, and Christiane Schmidt)
Computational Geometry: Theory and Applications, volume 93, February 2021, Article 101700.
- Tetris is NP-hard even with O(1) rows or columns
(joint work with Sualeh Asif, Michael Coulombe, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, and Mihir Singhal)
Journal of Information Processing, volume 28, 2020, pages 942–958.
- PSPACE-completeness of Pulling Blocks to Reach a Goal
(joint work with Joshua Ani, Sualeh Asif, Yevhenii Diomidov, Dylan Hendrickson, Jayson Lynch, Sarah Scheffler, and Adam Suhl)
Journal of Information Processing, volume 28, 2020, pages 929–941.
- Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
(joint work with Jeffrey Bosboom, Charlotte Chen, Lily Chung, Spencer Compton, Michael Coulombe, Martin L. Demaine, Ivan Tadeu Ferreira Antunes Filho, Dylan Hendrickson, Adam Hesterberg, Calvin Hsu, William Hu, Oliver Korten, Zhezheng Luo, and Lillian Zhang)
Journal of Information Processing, volume 28, 2020, pages 987–1007.
- Adventures in Maze Folding Art
(joint work with Martin L. Demaine)
Journal of Information Processing, volume 28, 2020, pages 745–749.
- Existence and Hardness of Conveyor Belts
(joint work with Molly Baird, Sara C. Billey, Martin L. Demaine, David Eppstein, Sándor Fekete, Graham Gordon, Sean Griffin, Joseph S. B. Mitchell, and Joshua P. Swanson)
The Electronic Journal of Combinatorics, volume 27, number 4, 2020, Article P4.25.
- Polyhedral Characterization of Reversible Hinged Dissections
(joint work with Jin Akiyama and Stefan Langerman)
Graphs and Combinatorics, volume 36, number 2, 2020, pages 221–229.
- Symmetric assembly puzzles are hard, beyond a few pieces
(joint work with Matias Korman, Jason S. Ku, Joseph S. B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, and Yushi Uno)
Computational Geometry: Theory and Applications, volume 90, October 2020, Article 101648.
- Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
(joint work with Zachary Abel, Jeffrey Bosboom, Michael Coulombe, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy, and Clemens Thielen)
Theoretical Computer Science, volume 839, November 2020, pages 41–102.
- Rigid Foldability is NP-hard
(joint work with Hugo A. Akitaya, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, and Tomohiro Tachi)
Journal of Computational Geometry, volume 11, number 1, 2020, pages 93–124.
- Infinite All-Layers Simple Foldability
(joint work with Hugo Akitaya, Cordelia Avery, Joseph Bergeron, Justin Kopinsky, and Jason Ku)
Graphs and Combinatorics, volume 36, 2020, pages 231–244.
- Cookie Clicker
(joint work with Hiro Ito, Stefan Langerman, Jayson Lynch, Mikhail Rudoy, and Kai Xiao)
Graphs and Combinatorics, volume 36, 2020, pages 269–302.
- Path Puzzles: Discrete Tomography with a Path Constraint is Hard
(joint work with Jeffrey Bosboom, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, and Justin Kopinsky)
Graphs and Combinatorics, volume 36, 2020, pages 251–267.
- Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron
(joint work with Nadia M. Benbernou, Martin L. Demaine, and Anna Lubiw)
Computational Geometry: Theory and Applications, volume 89, August 2020, Article 101633.
- Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
(joint work with Jean Cardinal, David Eppstein, Robert A. Hearn, and Andrew Winslow)
Theoretical Computer Science, volume 806, number 2, February 2020, pages 332–343.
- Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs
(joint work with Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, and Blair D. Sullivan)
Journal of Computer and System Sciences, volume 105, November 2019, pages 199–241.
- Sequentially Swapping Colored Tokens on Graphs
(joint work with Katsuhisa Yamanaka, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno)
Journal of Graph Algorithms and Applications, volume 23, number 1, 2019, pages 3–27.
- Particle computation: complexity, algorithms, and logic
(joint work with Aaron T. Becker, Sándor P. Fekete, Jarrett Lonsford, and Rose Morris-Wright)
Natural Computing, volume 18, number 1, December 2019, pages 181–201.
- The Fewest Clues Problem
(joint work with Fermi Ma, Erik Waingarten, Ariel Schvartzman, and Scott Aaronson)
Theoretical Computer Science, volume 748, November 2018, pages 28–39.
- A simple proof that the (n^{2} − 1)-puzzle is hard
(joint work with Mikhail Rudoy)
Theoretical Computer Science, volume 732, July 2018, pages 80–84.
- Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
(joint work with Zachary Abel, Martin L. Demaine, David Eppstein, Anna Lubiw, and Ryuhei Uehara)
Journal of Computational Geometry, volume 9, number 1, 2018, pages 74–93.
- Folding Polyominoes into (Poly)Cubes
(joint work with Oswin Aichholzer, Michael Biro, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Adam Hesterberg, Irina Kostitsyna, and Christiane Schmidt)
International Journal of Computational Geometry and Applications, volume 28, number 3, 2018, pages 197–226.
- Pachinko
(joint work with Hugo A. Akitaya, Martin L. Demaine, Adam Hesterberg, Ferran Hurtado, Jason S. Ku, and Jayson Lynch)
Computational Geometry: Theory and Applications, volume 68, March 2018, pages 226–242. In memory of our friend Ferran Hurtado
- Bumpy pyramid folding
(joint work with Zachary Abel, Martin L. Demaine, Hiro Ito, Jack Snoeyink, and Ryuhei Uehara)
Computational Geometry: Theory and Applications, volume 75, December 2018, pages 22–31.
- An End-To-End Approach to Self-Folding Origami Structures by Uniform Heat
(joint work with Byoungkwon An, Shuhei Miyashita, Aaron Ong, Daniel M. Aukes, Michael T. Tolley, Martin L. Demaine, Robert J. Wood, and Daniela Rus)
IEEE Transactions on Robotics, volume 34, number 6, December 2018, pages 1409–1424.
- Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
(joint work with Boris Aronov, Prosenjit Bose, Joachim Gudmundsson, John Iacono, Stefan Langerman, and Michiel Smid)
Algorithmica, volume 80, number 11, 2018, pages 3316–3334.
- Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares
(joint work with Zachary Abel, Brad Ballinger, Martin L. Demaine, Jeff Erickson, Adam Hesterberg, Hiro Ito, Irina Kostitsyna, Jayson Lynch, and Ryuhei Uehara)
Journal of Information Processing, volume 25, August 2017, pages 610–615.
- Folded Structures Satisfying Multiple Conditions
(joint work with Jason S. Ku)
Journal of Information Processing, volume 25, 2017, pages 601–609.
- Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, …
(joint work with Martin L. Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, and Y. William Yu)
Journal of Information Processing, volume 25, 2017, pages 515–527. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games
- Folding and Punching Paper
(joint work with Yasuhiko Asao, Martin L. Demaine, Hideaki Hosaka, Akitoshi Kawamura, Tomohiro Tachi, and Kazune Takahashi)
Journal of Information Processing, volume 25, 2017, pages 590–600. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games
- Even 1 × n Edge Matching and Jigsaw Puzzles are Really Hard
(joint work with Jeffrey Bosboom, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, and Anak Yodpinyanee)
Journal of Information Processing, volume 25, 2017, pages 682–694. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games
- Simple Folding is Really Hard
(joint work with Hugo A. Akitaya and Jason S. Ku)
Journal of Information Processing, volume 25, 2017, pages 580–589. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games
- Arboral satisfaction: Recognition and LP approximation
(joint work with Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, and Daniel Ziegler)
Information Processing Letters, volume 127, November 2017, pages 1–5.
- Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement
(joint work with Mirela Damian, Robin Flatland, and Joseph O'Rourke)
Graphs and Combinatorics, volume 33, number 5, 2017, pages 1357–1379.
- Embedding Stacked Polytopes on a Polynomial-Size Grid
(joint work with André Schulz)
Discrete & Computational Geometry, volume 57, number 4, June 2017, pages 782–809.
- New Geometric Algorithms for Fully Connected Staged Self-Assembly
(joint work with Sándor Fekete, Christian Scheffer, and Arne Schmidt)
Theoretical Computer Science, volume 671, April 2017, pages 4–18.
- Folding Flat Crease Patterns With Thick Materials
(joint work with Jason S. Ku)
Journal of Mechanisms and Robotics, volume 8, number 3, June 2016, pages 031003-1–6.
- The Two-Handed Tile Assembly Model is not Intrinsically Universal
(joint work with Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods)
Algorithmica, volume 74, number 2, February 2016, pages 812–850.
- Rigid Origami Vertices: Conditions and Forcing Sets
(joint work with Zachary Abel, Jason Cantarella, David Eppstein, Thomas C. Hull, Jason S. Ku, Robert J. Lang, and Tomohiro Tachi)
Journal of Computational Geometry, volume 7, number 1, 2016, pages 171–184.
- Folding a Paper Strip to Minimize Thickness
(joint work with David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, and Yushi Uno)
Journal of Discrete Algorithms, volume 36, January 2016, pages 18–26.
- Linear-time algorithm for sliding tokens on trees
(joint work with Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada)
Theoretical Computer Science, volume 600, 2015, pages 132–142.
- A review on curved creases in art, design and mathematics
(joint work with Martin Demaine, Duks Koschitz, and Tomohiro Tachi)
Symmetry: Culture and Science, volume 26, number 2, 2015, pages 145–161.
- A system for generating paper sliceform artwork
(joint work with Yongquan Lu)
Symmetry: Culture and Science, volume 26, number 2, 2015, pages 203–215.
- Fun with Fonts: Algorithmic Typography
(joint work with Martin L. Demaine)
Theoretical Computer Science, volume 586, June 2015, pages 111–119.
- Worst-Case Optimal Tree Layout in External Memory
(joint work with John Iacono and Stefan Langerman)
Algorithmica, volume 72, number 2, 2015, pages 369–378.
- Zig-Zag Numberlink is NP-Complete
(joint work with Aaron B. Adcock, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sanchez Villaamil, and Blair D. Sullivan)
Journal of Information Processing, volume 23, number 3, 2015, pages 239–245.
- Swapping Labeled Tokens on Graphs
(joint work with Katsuhisa Yamanaka, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno)
Theoretical Computer Science, volume 586, 2015, pages 81–94.
- Classic Nintendo Games are (Computationally) Hard
(joint work with Greg Aloupis, Alan Guo, and Giovanni Viglietta)
Theoretical Computer Science, volume 586, 2015, pages 135–160.
- You Should Be Scared of German Ghost
(joint work with Fermi Ma, Matthew Susskind, and Erik Waingarten)
Journal of Information Processing, volume 23, number 3, 2015, pages 293–298.
- On Cartesian Trees and Range Minimum Queries
(joint work with Gad Landau and Oren Weimann)
Algorithmica, volume 68, number 3, 2014, pages 610–625.
- Necklaces, Convolutions, and X + Y
(joint work with David Bremner, Timothy M. Chan, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Pǎtraşcu, and Perouz Taslakian)
Algorithmica, volume 69, number 2, 2014, pages 294–314.
- Minimizing Movement: Fixed-Parameter Tractability
(joint work with MohammadTaghi Hajiaghayi and Dániel Marx)
ACM Transactions on Algorithms, volume 11, number 2, November 2014, Paper 14.
- Approximability of the Subset Sum Reconfiguration Problem
(joint work with Takehiro Ito)
Journal of Combinatorial Optimization, volume 28, number 3, October 2014, pages 639–654.
- Computational Complexity of Piano-Hinged Dissections
(joint work with Zachary Abel, Martin L. Demaine, Takashi Horiyama, and Ryuhei Uehara)
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, volume E97-A, number 6, 2014, pages 1206–1212.
- Computational complexity and an integer programming model of Shakashaka
(joint work with Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno)
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, volume E97-A, number 6, 2014, pages 1213–1219.
- Covering Folded Shapes
(joint work with Oswin Aichholzer, Greg Aloupis, Martin L. Demaine, Sándor P. Fekete, Michael Hoffmann, Anna Lubiw, Jack Snoeyink, and Andrew Winslow)
Journal of Computational Geometry, volume 5, number 1, 2014.
- A method for building self-folding machines
(joint work with S. Felton, M. Tolley, D. Rus, and R. Wood)
Science, volume 345, number 6197, August 8, 2014, pages 644–646.
- Picture-Hanging Puzzles
(joint work with Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, and Mihai Pǎtraşcu)
Theory of Computing Systems, volume 54, number 4, May 2014, pages 531–550.
- UNO is hard, even for a single player
(joint work with Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, and Yushi Uno)
Theoretical Computer Science, volume 521, February 2014, pages 51–61.
- Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
(joint work with Glencora Borradaile and Siamak Tazari)
Algorithmica, volume 68, number 2, February 2014, pages 287–311.
- Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm
(joint work with Mirela Damian and Robin Flatland)
Graphs and Combinatorics, volume 30, number 1, 2014, pages 125–140.
- Folding Equilateral Plane Graphs
(joint work with Zachary Abel, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, and Isaac Shapiro-Ellowitz)
International Journal of Computational Geometry and Applications, volume 23, number 2, April 2013, pages 75–92.
- Efficient Reconfiguration of Lattice-Based Modular Robots
(joint work with Greg Aloupis, Nadia Benbernou, Mirela Damian, Robin Flatland, John Iacono, and Stefanie Wuhrer)
Computational Geometry: Theory and Applications, volume 46, number 8, October 2013, pages 917–928.
- Refold Rigidity of Convex Polyhedra
(joint work with Martin L. Demaine, Jin-ichi Itoh, Anna Lubiw, Chie Nara, and Joseph O'Rourke)
Computational Geometry: Theory and Applications, volume 46, number 8, October 2013, pages 979–989.
- Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
(joint work with Zachary Abel, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl)
Journal of Information Processing, volume 21, number 3, July 2013, pages 368–377.
- One-Dimensional Staged Self-Assembly
(joint work with Sarah Eisenstat, Mashhood Ishaque, and Andrew Winslow)
Natural Computing, volume 12, number 2, 2013, pages 247–258.
- Basic Network Creation Games
(joint work with Noga Alon, MohammadTaghi Hajiaghayi, and Tom Leighton)
SIAM Journal on Discrete Mathematics, volume 27, number 2, 2013, pages 656–668.
- Reconstructing David Huffman's Origami Tessellations
(joint work with Eli Davis, Martin L. Demaine, and Jennifer Ramseyer)
Journal of Mechanical Design, volume 135, number 11, November 2013, pages 111010-1–111010-7.
- Joining Unfoldings of 3-D Surfaces
(joint work with Cynthia Sung, Martin L. Demaine, and Daniela Rus)
Journal of Mechanical Design, volume 135, number 11, November 2013, pages 111001-1–111001-9.
- PCB Origami: A material-based design approach to computer-aided foldable electronic devices
(joint work with Yoav Sterman and Neri Oxman)
Journal of Mechanical Design, volume 135, number 11, November 2013, pages 114502-1–114502-4.
- Self-folding with shape memory composites
(joint work with Samuel M. Felton, Michael T. Tolley, ByungHyun Shin, Cagdas D. Onal, Daniela Rus, and Robert J. Wood)
Soft Matter, volume 9, number 32, 2013, pages 7688–7694.
- Scheduling to Minimize Gaps and Power Consumption
(joint work with Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S. Sayedi-Roshkhar, and Morteza Zadimoghaddam)
Journal of Scheduling, volume 16, number 2, April 2013, pages 151–160.
- Bounded-Degree Polyhedronization of Point Sets
(joint work with Gill Barequet, Nadia Benbernou, David Charlton, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint, and Andrew Winslow)
Computational Geometry: Theory and Applications, volume 46, number 2, February 2013, pages 917–928.
- Constructing Points through Folding and Intersection
(joint work with Steve Butler, Ron Graham, and Tomohiro Tachi)
International Journal of Computational Geometry and Applications, volume 23, number 1, February 2013, pages 49–64.
- Coverage with k-Transmitters in the Presence of Obstacles
(joint work with Brad Ballinger, Nadia Benbernou, Prosenjit Bose, Mirela Damian, Vida Dujmović, Robin Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristán, Diane Souvaine, and Ryuhei Uehara)
Journal of Combinatorial Optimization, volume 25, number 2, February 2013, pages 208–233.
- Non-crossing matchings of points with geometric objects
(joint work with Greg Aloupis, Jean Cardinal, Sébastien Collette, Martin L. Demaine, Muriel Dulieu, Ruy Fabila-Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara, and Perouz Taslakian)
Computational Geometry: Theory and Applications, volume 46, number 1, January 2013, pages 78–92.
- The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs
(joint work with Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Ilan Newman, and Oren Weimann)
Journal of Combinatorial Optimization, volume 25, number 1, January 2013, pages 19–46.
- Reconfiguration of List Edge-Colorings in a Graph
(joint work with Takehiro Ito and Marcin Kamiński)
Discrete Applied Mathematics, volume 160, number 15, October 2012, pages 2199–2207.
- Constant Price of Anarchy in Network-Creation Games via Public-Service Advertising
(joint work with Morteza Zadimoghaddam)
Internet Mathematics, volume 8, number 1–2, 2012, pages 29–45.
- Hinged Dissections Exist
(joint work with Timothy G. Abbott, Zachary Abel, David Charlton, Martin L. Demaine, and Scott Duke Kominers)
Discrete & Computational Geometry, volume 47, number 1, 2012, pages 150–186.
- On k-convex polygons
(joint work with Oswin Aichholzer, Franz Aurenhammer, Ferran Hurtado, Pedro Ramos, and Jorge Urrutia)
Computational Geometry: Theory and Applications, volume 45, number 3, 2012, pages 73–87.
- NP-completeness of generalized Kaboozle
(joint work with Tetsuo Asano, Martin L. Demaine, and Ryuhei Uehara)
Journal of Information Processing, volume 20, number 3, July 2012, pages 713–718.
- Ghost Chimneys
(joint work with David Charlton, Martin L. Demaine, Vida Dujmović, Pat Morin, and Ryuhei Uehara)
International Journal of Computational Geometry and Applications, volume 22, number 3, June 2012, pages 207–214.
- The Price of Anarchy in Network Creation Games
(joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam)
ACM Transactions on Algorithms, volume 8, number 2, April 2012, Paper 13.
- Any Monotone Boolean Function Can Be Realized by Interlocked Polygons
(joint work with Martin L. Demaine and Ryuhei Uehara)
Algorithms, volume 5, number 1, March 2012, pages 148–157.
- Voronoi game on graphs and its complexity
(joint work with Sachio Teramoto and Ryuhei Uehara)
Journal of Graph Algorithms and Applications, volume 15, number 4, 2011, pages 485–501.
- The Stackelberg Minimum Spanning Tree Game
(joint work with Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, and Oren Weimann)
Algorithmica, volume 59, number 2, 2011, pages 129–144.
- Covering points by disjoint boxes with outliers
(joint work with Hee-Kap Ahn, Sang Won Bae, Martin L. Demaine, Sang-Sub Kim, Matias Korman, Iris Reinbacher, and Wanbin Son)
Computational Geometry: Theory and Applications, volume 44, number 3, 2011, pages 178–190.
- On the Complexity of Reconfiguration Problems
(joint work with Takehiro Ito, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno)
Theoretical Computer Science, volume 412, number 12-14, 2011, pages 1054–1065.
- Computing Signed Permutations of Polygons
(joint work with Greg Aloupis, Prosenjit Bose, Stefan Langerman, Henk Meijer, Mark Overmars, and Godfried T. Toussaint)
International Journal of Computational Geometry and Applications, volume 21, number 1, 2011, pages 87–100.
- Programmable Assembly With Universally Foldable Strings (Moteins)
(joint work with Kenneth C. Cheung, Jonathan Bachrach, and Saul Griffith)
IEEE Transactions on Robotics, volume 27, number 4, 2011, pages 718–729.
- Algorithmic Folding Complexity
(joint work with Jean Cardinal, Martin L. Demaine, Shinji Imahori, Tsuyoshi Ito, Masashi Kiyomi, Stefan Langerman, Ryuhei Uehara, and Takeaki Uno)
Graphs and Combinatorics, volume 27, number 3, 2011, pages 341–351.
- Continuous Blooming of Convex Polyhedra
(joint work with Martin L. Demaine, Vi Hart, John Iacono, Stefan Langerman, and Joseph O'Rourke)
Graphs and Combinatorics, volume 27, number 3, 2011, pages 363–376.
- (Non)existence of Pleated Folds: How Paper Folds Between Creases
(joint work with Martin L. Demaine, Vi Hart, Gregory N. Price, and Tomohiro Tachi)
Graphs and Combinatorics, volume 27, number 3, 2011, pages 377–397.
- Efficient constant-velocity reconfiguration of crystalline robots
(joint work with Greg Aloupis, Sébastien Collette, Mirela Damian, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer)
Robotica, volume 29, number 1, 2011, pages 59–71. Special issue on Robotic Self-X Systems.
- Planning to Fold Multiple Objects from a Single Self-Folding Sheet
(joint work with Byoungkwon An, Nadia Benbernou, and Daniela Rus)
Robotica, volume 29, number 1, 2011, pages 87–102. Special issue on Robotic Self-X Systems.
- Integer Point Sets Minimizing Average Pairwise L_{1} Distance: What is the Optimal Shape of a Town?
(joint work with Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, and Mariano Zelke)
Computational Geometry: Theory and Applications, volume 44, number 2, February 2011, pages 82–94.
- Confluently Persistent Tries for Efficient Version Control
(joint work with Stefan Langerman and Eric Price)
Algorithmica, volume 57, number 3, 2010, pages 462–483. Special issue of selected papers from 11th Scandinavian Workshop on Algorithm Theory, 2008.
- Approximation Algorithms via Contraction Decomposition
(joint work with MohammadTaghi Hajiaghayi and Bojan Mohar)
Combinatorica, volume 30, number 5, 2010, pages 533–552.
- Locked and Unlocked Chains of Planar Shapes
(joint work with Robert Connelly, Martin L. Demaine, Sándor Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, and Günter Rote)
Discrete & Computational Geometry, volume 44, number 2, 2010, pages 439–462.
- Grid Vertex-Unfolding Orthostacks
(joint work with John Iacono and Stefan Langerman)
International Journal of Computational Geometry and Applications, volume 20, number 3, 2010, pages 245–254.
- Recreational Computing: Puzzles and tricks from Martin Gardner inspire math and science
American Scientist, volume 98, number 6, November–December, 2010, pages 452–456.
- Programmable matter by folding
(joint work with E. Hawkes, B. An, N. M. Benbernou, H. Tanaka, S. Kim, D. Rus, and R. J. Wood)
Proceedings of the National Academy of Sciences of the United States of America, volume 107, number 28, 2010, pages 12441–12445.
- Deploying Sensor Networks with Guaranteed Fault Tolerance
(joint work with Jonathan L. Bredin, MohammadTaghi Hajiaghayi, and Daniela Rus)
IEEE/ACM Transactions on Networking, volume 18, number 1, February 2010, pages 216–228.
- Generalized D-Forms Have No Spurious Creases
(joint work with Gregory N. Price)
Discrete & Computational Geometry, volume 43, number 1, 2009, pages 179–186.
- Wrapping Spheres with Flat Paper
(joint work with Martin L. Demaine, John Iacono, and Stefan Langerman)
Computational Geometry: Theory and Applications, volume 42, number 8, 2009, pages 748–757. Special issue of selected papers from the 20th European Workshop on Computational Geometry, 2007.
- The Price of Anarchy in Cooperative Network Creation Games
(joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam)
ACM SIGecom Exchanges, volume 8, number 2, December 2009.
- Linear Reconfiguration of Cube-Style Modular Robots
(joint work with Greg Aloupis, Sébastien Collette, Mirela Damian, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer)
Computational Geometry: Theory and Applications, volume 42, number 6–7, August 2009, pages 652–663.
- The Distance Geometry of Music
(joint work with Francisco Gomez-Martin, Henk Meijer, David Rappaport, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, and David R. Wood)
Computational Geometry: Theory and Applications, volume 42, number 5, July 2009, pages 429–454. Special issue of selected papers from the 17th Canadian Conference on Computational Geometry, 2005.
- Minimizing Movement
(joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam)
ACM Transactions on Algorithms, volume 5, number 3, July 2009, Article 30.
- Dynamic Ham-Sandwich Cuts in the Plane
(joint work with Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Martin L. Demaine, John Hugg, Daniel Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, and Vincent Yeung)
Computational Geometry: Theory and Applications, volume 42, number 5, July 2009, pages 419–428. Special issue of selected papers from the 17th Canadian Conference on Computational Geometry, 2005.
- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction
(joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
Algorithmica, volume 54, number 2, June 2009, pages 142–180. Special issue of selected papers from the 17th Annual International Symposium on Algorithms and Computation, 2006.
- Refolding Planar Polygons
(joint work with Hayley N. Iben and James F. O'Brien)
Discrete & Computational Geometry, volume 41, number 3, April 2009, pages 444–460. Special issue of selected papers from the 22nd Annual ACM Symposium on Computational Geometry, 2006.
- Approximability of Partitioning Graphs with Supply and Demand
(joint work with Takehiro Ito, Xiao Zhou, and Takao Nishizeki)
Journal of Discrete Algorithms, volume 6, number 4, December 2008, pages 627–650.
- Realizing Partitions Respecting Full and Partial Order Information
(joint work with Jeff Erickson, Danny Krizanc, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides)
Journal of Discrete Algorithms, volume 6, 2008, pages 51–58. Special issue of selected papers from the 16th Australasian Workshop on Combinatorial Algorithms, 2005.
- The Bidimensionality Theory and Its Algorithmic Applications
(joint work with MohammadTaghi Hajiaghayi)
The Computer Journal, volume 51, number 3, 2008, pages 292–302.
- Combination Can Be Hard: Approximability of the Unique Coverage Problem
(joint work with Uriel Feige, MohammadTaghi Hajiaghayi, and Mohammad R. Salavatipour)
SIAM Journal on Computing, volume 38, number 4, September 2008, pages 1464–1483.
- Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
(joint work with Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine)
Natural Computing, volume 7, number 3, September 2008, pages 347–370. Special issue of selected papers from the 13th International Meeting on DNA Computing, 2007.
- Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics
(joint work with Noga Alon, Mihai Bădoiu, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos)
ACM Transactions on Algorithms, volume 4, number 4, August 2008, Article 46.
- Subquadratic Algorithms for 3SUM
(joint work with Ilya Baran and Mihai Pǎtraşcu)
Algorithmica, volume 50, number 4, April 2008, pages 584–596. Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.
- Communication-Aware Processor Allocation for Supercomputers
(joint work with Michael A. Bender, David P. Bunde, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, and Cynthia A. Phillips)
Algorithmica, volume 50, number 2, February 2008, pages 279–298. Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.
- Optimally Adaptive Integration of Univariate Lipschitz Functions
(joint work with Ilya Baran and Dmitriy A. Katz)
Algorithmica, volume 50, number 2, February 2008, pages 255–278. Special issue of selected papers from the 7th Latin American Symposium on Theoretical Informatics, 2006.
- Linearity of Grid Minors in Treewidth with Applications through Bidimensionality
(joint work with MohammadTaghi Hajiaghayi)
Combinatorica, volume 28, number 1, January 2008, pages 19–36.
- Edge-Unfolding Nested Polyhedral Bands
(joint work with Greg Aloupis, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, and Godfried Toussaint)
Computational Geometry: Theory and Applications, volume 39, number 1, January 2008, pages 30–42. Special issue of selected papers from the 16th Canadian Conference on Computational Geometry, 2004.
- A Unified Access Bound on Comparison-Based Dynamic Dictionaries
(joint work with Mihai Bădoiu, Richard Cole, and John Iacono)
Theoretical Computer Science, volume 382, number 2, August 2007, pages 86–96. Special issue of selected papers from the 6th Latin American Symposium on Theoretical Informatics, 2004.
- Planar Embeddings of Graphs with Specified Edge Lengths
(joint work with Sergio Cabello and Günter Rote)
Journal of Graph Algorithms and Applications, volume 11, number 1, 2007, pages 259–276.
- Plane Embeddings of Planar Graph Metrics
(joint work with MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Mohammad Moharrami)
Discrete & Computational Geometry, volume 38, 2007, pages 615–637.
- Sand Drawings and Gaussian Graphs
(joint work with Martin L. Demaine, Perouz Taslakian, and Godfried T. Toussaint)
Journal of Mathematics and the Arts, volume 1, number 2, June 2007, pages 125–132.
- Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity
(joint work with Martin L. Demaine)
Graphs and Combinatorics, volume 23 (Supplement), June 2007, pages 195–208. Special issue on Computational Geometry and Graph Theory: The Akiyama-Chvatal Festschrift.
- Retroactive Data Structures
(joint work with John Iacono and Stefan Langerman)
ACM Transactions on Algorithms, volume 3, number 2, May 2007, Article 13.
- Dynamic Optimality—Almost
(joint work with Dion Harmon, John Iacono, and Mihai Pǎtraşcu)
SIAM Journal on Computing, volume 37, number 1, May 2007, pages 240–251. Special issue of selected papers from the 45th Annual IEEE Symposium on Foundations of Computer Science.
- An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms
(joint work with Lars Arge, Michael A. Bender, Bryan E. Holland-Minkley, and J. Ian Munro)
SIAM Journal on Computing, volume 36, number 6, March 2007, pages 1672–1695.
- Geodesic Ham-Sandwich Cuts
(joint work with Prosenjit Bose, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin)
Discrete & Computational Geometry, volume 37, number 3, March 2007, pages 325–339.
- Quickly Deciding Minor-Closed Parameters in General Graphs
(joint work with MohammadTaghi Hajiaghayi)
European Journal of Combinatorics, volume 28, number 1, January 2007, pages 311–314.
- Low-Dimensional Embedding with Extra Information
(joint work with Mihai Bădoiu, MohammadTaghi Hajiaghayi, and Piotr Indyk)
Discrete & Computational Geometry, volume 36, number 4, December 2006, pages 609–632. Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry.
- Logarithmic Lower Bounds in the Cell-Probe Model
(joint work with Mihai Pǎtraşcu)
SIAM Journal on Computing, volume 35, number 4, 2006, pages 932–963. Special issue of selected papers from the 36th ACM Symposium on Theory of Computing, 2004.
- The Bidimensional Theory of Bounded-Genus Graphs
(joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
SIAM Journal on Discrete Mathematics, volume 20, number 2, 2006, pages 357–371.
- Online Searching with Turn Cost
(joint work with Sándor P. Fekete and Shmuel Gal)
Theoretical Computer Science, volume 361, number 2–3, September 2006, pages 342–355. Special issue on approximation and online algorithms.
- Correlation Clustering in General Weighted Graphs
(joint work with Dotan Emanuel, Amos Fiat, and Nicole Immorlica)
Theoretical Computer Science, volume 361, number 2–3, September 2006, pages 172–187. Special issue on approximation and online algorithms.
- Puzzles, Art, and Magic with Algorithms
(joint work with Martin L. Demaine)
Theory of Computing Systems, volume 39, number 3, June 2006, pages 473–481. Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.
- Morpion Solitaire
(joint work with Martin L. Demaine, Arthur Langerman, and Stefan Langerman)
Theory of Computing Systems, volume 39, number 3, June 2006, pages 439–453. Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.
- The Helium Stockpile: A Collaboration in Mathematical Folding Sculpture
(joint work with Martin L. Demaine and A. Laurie Palmer)
Leonardo, volume 39, number 3, June 2006, pages 233–235.
- Geometric Restrictions on Producible Polygonal Protein Chains
(joint work with Stefan Langerman and Joseph O'Rourke)
Algorithmica, volume 44, number 2, February 2006, pages 167–181. Special issue of selected papers from the 14th Annual International Symposium on Algorithms and Computation, 2003.
- Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs
(joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
Journal of the ACM, volume 52, number 6, 2005, pages 866–893.
- Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve
(joint work with Ilya Baran)
International Journal of Computational Geometry and Applications, volume 15, number 4, 2005, pages 327–350. Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry, 2004.
- Optimal Covering Tours with Turn Costs
(joint work with Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia)
SIAM Journal on Computing, volume 35, number 3, 2005, pages 531–566.
- Cache-Oblivious B-Trees
(joint work with Michael A. Bender and Martin Farach-Colton)
SIAM Journal on Computing, volume 35, number 2, 2005, pages 341–358.
- Representing Trees of Higher Degree
(joint work with David Benoit, J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao)
Algorithmica, volume 43, number 4, December 2005, pages 275–292.
- PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation
(joint work with Robert A. Hearn)
Theoretical Computer Science, volume 343, number 1–2, October 2005, pages 72–96. Special issue “Game Theory Meets Theoretical Computer Science”.
- Games on Triangulations
(joint work with Oswin Aichholzer, David Bremner, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia)
Theoretical Computer Science, volume 343, number 1–2, October 2005, pages 42–71. Special issue “Game Theory Meets Theoretical Computer Science”.
- Separating point sets in polygonal environments
(joint work with Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, and Sue Whitesides)
International Journal of Computational Geometry and Applications, volume 15, number 4, August 2005, pages 403–419. Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry, 2004.
- Fixed-Parameter Algorithms for (k, r)-Center in Planar Graphs and Map Graphs
(joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
ACM Transactions on Algorithms, volume 1, number 1, July 2005, pages 33–47.
- Hinged Dissection of Polyominoes and Polyforms
(joint work with Martin L. Demaine, David Eppstein, Greg N. Frederickson, and Erich Friedman)
Computational Geometry: Theory and Applications, volume 31, number 3, June 2005, pages 237–262. Special issue of selected papers from the 11th Canadian Conference on Computational Geometry, 1999.
- Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries
(joint work with David Bremner, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint)
Discrete & Computational Geometry, volume 33, number 4, April 2005, pages 593–604.
- Fast Allocation and Deallocation with an Improved Buddy System
(joint work with Gerth Stølting Brodal and J. Ian Munro)
Acta Informatica, volume 41, number 4–5, March 2005, pages 273–291.
- Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors
(joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
Algorithmica, volume 41, number 4, February 2005, pages 245–267.
- Building Blocks and Excluded Sums
(joint work with Martin L. Demaine, Alan Edelman, Charles E. Leiserson, and Per-Olof Persson)
SIAM News, volume 38, number 1, January 2005, pages 1, 4, 6.
- Tetris is Hard, Even to Approximate
(joint work with Ron Breukelaar, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, and David Liben-Nowell)
International Journal of Computational Geometry and Applications, volume 14, number 1–2, 2004, pages 41–68.
- Bidimensional Parameters and Local Treewidth
(joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
SIAM Journal on Discrete Mathematics, volume 18, number 3, 2004, pages 501–511.
- Fun-Sort—or the Chaos of Unordered Binary Search
(joint work with Therese Biedl, Timothy Chan, Rudolf Fleischer, Mordecai Golin, James A. King, and J. Ian Munro)
Discrete Applied Mathematics, volume 144, number 3, December 2004, pages 231–236.
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
(joint work with MohammadTaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos)
Journal of Computer and System Sciences, volume 69, number 2, September 2004, pages 166–195.
- When Can You Fold a Map?
(joint work with Esther M. Arkin, Michael A. Bender, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven S. Skiena)
Computational Geometry: Theory and Applications, volume 29, number 1, September 2004, pages 23–46. Special issue of selected papers from the 10th Annual Fall Workshop on Computational Geometry, 2000.
- Finding a Divisible Pair
(joint work with Stelian Ciurea, Corina E. Pǎtraşcu, and Mihai Pǎtraşcu)
ACM SIGSAM Bulletin, volume 38, number 3, September 2004, pages 98–100.
- Tight Bounds on Maximal and Maximum Matchings
(joint work with Therese Biedl, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov)
Discrete Mathematics, volume 285, number 1–3, August 2004, pages 7–15.
- Diameter and Treewidth in Minor-Closed Graph Families, Revisited
(joint work with MohammadTaghi Hajiaghayi)
Algorithmica, volume 40, number 3, August 2004, pages 211–215.
- Proximate Point Searching
(joint work with John Iacono and Stefan Langerman)
Computational Geometry: Theory and Applications, volume 28, number 1, May 2004, pages 29–40. Special issue of selected papers from the 14th Canadian Conference on Computational Geometry, 2002.
- Open Problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory
(joint work with Rudolf Fleischer, Aviezri S. Fraenkel, and Richard J. Nowakowski)
Theoretical Computer Science, volume 313, number 3, February 2004, pages 539–543. Special issue on algorithmic combinatorial game theory.
- Solitaire Clobber
(joint work with Martin L. Demaine and Rudolf Fleischer)
Theoretical Computer Science, volume 313, number 3, February 2004, pages 325–338. Special issue of selected papers presented at the Schloss Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, 2002.
- What is the optimal shape of a city?
(joint work with Carl M. Bender, Michael A. Bender, and Sándor P. Fekete)
Journal of Physics A: Mathematical and General, volume 37, number 1, January 2004, pages 147–159.
- Finding Hidden Independent Sets in Interval Graphs
(joint work with Therese Biedl, Broňa Brejová, Angèle M. Hamel, Alejandro López-Ortiz, and Tomáš Vinař)
Theoretical Computer Science, volume 310, number 1–3, January 2004, pages 287–307.
- Straightening Polygonal Arcs and Convexifying Polygonal Cycles
(joint work with Robert Connelly and Günter Rote)
Discrete & Computational Geometry, volume 30, number 2, September 2003, pages 205–239.
- A Linear Lower Bound on Index Size for Text Retrieval
(joint work with Alejandro López-Ortiz)
Journal of Algorithms, volume 48, number 1, August 2003, pages 2–15. Special issue of selected papers from the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001.
- Pushing Blocks is Hard
(joint work with Martin L. Demaine, Michael Hoffmann, and Joseph O'Rourke)
Computational Geometry: Theory and Applications, volume 26, number 1, August 2003, pages 21–36. Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.
- Interlocked Open and Closed Linkages with Few Joints
(joint work with Stefan Langerman, Joseph O'Rourke, and Jack Snoeyink)
Computational Geometry: Theory and Applications, volume 26, number 1, August 2003, pages 37–45. Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.
- On Universally Easy Classes for NP-complete Problems
(joint work with Alejandro López-Ortiz and J. Ian Munro)
Theoretical Computer Science, volume 304, number 1–3, July 2003, pages 471–476.
- Palindrome Recognition Using a Multidimensional Tape
(joint work with Therese C. Biedl, Jonathan F. Buss, Martin L. Demaine, Mohammadtaghi Hajiaghayi, and Tomáš Vinař)
Theoretical Computer Science, volume 302, number 1–3, June 2003, pages 475–480.
- Long Proteins with Unique Optimal Foldings in the H-P Model
(joint work with Oswin Aichholzer, David Bremner, Henk Meijer, Vera Sacristán, and Michael Soss)
Computational Geometry: Theory and Applications, volume 25, number 1–2, May 2003, pages 139–159. Special issue of selected papers from the 17th European Workshop on Computational Geometry, 2001.
- Ununfoldable Polyhedra with Convex Faces
(joint work with Marshall Bern, David Eppstein, Eric Kuo, Andrea Mantler, and Jack Snoeyink)
Computational Geometry: Theory and Applications, volume 24, number 2, February 2003, pages 51–62. Special issue of selected papers from the 4th CGC Workshop on Computational Geometry, 1999.
- K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data
(joint work with Ziv Bar-Joseph, David K. Gifford, Angèle M. Hamel, Tommi S. Jaakkola, and Nathan Srebro)
Bioinformatics, volume 19, number 9, 2003, pages 1070–1078. Special issue on Microarray Analysis.
- Hinged Dissection of the Alphabet
(joint work with Martin L. Demaine)
Journal of Recreational Mathematics, volume 31, number 3, 2003, pages 204–207.
- Online Routing in Convex Subdivisions
(joint work with Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Rudolf Fleischer, Alejandro López-Ortiz, Pat Morin, and J. Ian Munro)
International Journal of Computational Geometry and Applications, volume 12, number 4, August 2002, pages 283–295. Special issue of selected papers from the 11th Annual International Symposium on Algorithms and Computation, 2000.
- Flipturning Polygons
(joint work with Oswin Aichholzer, Carmen Cortés, Vida Dujmović, Jeff Erickson, Henk Meijer, Mark Overmars, Belén Palop, Suneeta Ramaswami, and Godfried T. Toussaint)
Discrete & Computational Geometry, volume 28, number 2, August 2002, pages 231–253.
- Enumerating Foldings and Unfoldings between Polygons and Polytopes
(joint work with Martin L. Demaine, Anna Lubiw, and Joseph O'Rourke)
Graphs and Combinatorics, volume 18, number 1, 2002, pages 93–104.
- Balanced k-Colorings
(joint work with Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Martin L. Demaine, Rudolf Fleischer, and Ming-Wei Wang)
Discrete Mathematics, volume 254, 2002, pages 19–32.
- A Note on Reconfiguring Tree Linkages: Trees can Lock
(joint work with Therese Biedl, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, and Sue Whitesides)
Discrete Applied Mathematics, volume 117, number 1–3, 2002, pages 293–297.
- Locked and Unlocked Polygonal Chains in Three Dimensions
(joint work with T. Biedl, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides)
Discrete & Computational Geometry, volume 26, number 3, October 2001, pages 269–281.
- Polygons Cuttable by a Circular Saw
(joint work with Martin L. Demaine and Craig S. Kaplan)
Computational Geometry: Theory and Applications, volume 20, number 1–2, October 2001, pages 69–84. Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.
- Reconfiguring Convex Polygons
(joint work with Oswin Aichholzer, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, and Godfried T. Toussaint)
Computational Geometry: Theory and Applications, volume 20, number 1–2, October 2001, pages 85–95. Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.
- Generalized Communicators in the Message Passing Interface
(joint work with Ian Foster, Carl Kesselman, and Marc Snir)
IEEE Transactions on Parallel and Distributed Systems, volume 12, number 6, June 2001, pages 610–616.
- Efficient Algorithms for Petersen's Matching Theorem
(joint work with Therese C. Biedl, Prosenjit Bose, and Anna Lubiw)
Journal of Algorithms, volume 38, 2001, pages 110–134. Special issue of selected papers from the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000.
- Computational Geometry Column 37
(joint work with Joseph O'Rourke)
International Journal of Computational Geometry and Applications, volume 10, number 1, February 2000, pages 103–107. Also appears in SIGACT News, volume 30, number 3, issue #112, September 1999, pages 39–42.
- Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami
(joint work with Martin L. Demaine and Joseph S. B. Mitchell)
Computational Geometry: Theory and Applications, volume 16, number 1, 2000, pages 3–21. Special issue of selected papers from the 3rd CGC Workshop on Computational Geometry, 1998.
- C to Java: Converting Pointers into References
Concurrency: Practice and Experience, volume 10, number 11–13, 1998, pages 851–861.
- Routing Algorithms on Static Interconnection Networks: A Classification Scheme
(joint work with Sampalli Srinivas)
International Journal of Computer Systems Science and Engineering, volume 12, number 6, November 1997, pages 359–367.
- A Novel Routing Algorithm for k-ary n-cube Interconnection Networks
(joint work with Sampalli Srinivas)
International Journal of High Speed Computing, volume 8, number 1, 1996, pages 81–92.
- Losing at Checkers is Hard
(joint work with Jeffrey Bosboom, Spencer Congero, Martin L. Demaine, and Jayson Lynch)
in The Mathematics of Various Entertaining Subjects (MOVES 2017), volume 3, 2019, pages 103–118, Princeton University Press.
- Spiral Galaxies Font
(joint work with Walker Anderson and Martin L. Demaine)
in The Mathematics of Various Entertaining Subjects (MOVES 2017), edited by Jennifer Beineke and Jason Rosenhouse, volume 3, 2019, pages 24–30, Princeton University Press.
- Juggling and Card Shuffling Meet Mathematical Fonts
(joint work with Martin L. Demaine)
in Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham, edited by Steve Butler, Joshua Cooper, and Glenn Hurlbert, 2018, pages 297–304, Cambridge University Press.
- Conic Crease Patterns with Reflecting Rule Lines
(joint work with Martin L. Demaine, David A. Huffman, Duks Koschitz, and Tomohiro Tachi)
in Origami^{7}: Proceedings of the 7th International Meeting on Origami in Science, Mathematics and Education (OSME 2018), volume 2, Oxford, England, September 5–7, 2018, pages 573–590, Tarquin.
- Fast, Interactive Origami Simulation using GPU Computation
(joint work with Amanda Ghassaei and Neil Gershenfeld)
in Origami^{7}: Proceedings of the 7th International Meeting on Origami in Science, Mathematics and Education (OSME 2018), volume 4, Oxford, England, September 5–7, 2018, pages 1151–1166, Tarquin.
- Efficient Origami Construction of Orthogonal Terrains using Cross-Section Evolution
(joint work with Amartya Shankha Biswas and Jason S. Ku)
in Origami^{7}: Proceedings of the 7th International Meeting on Origami in Science, Mathematics and Education (OSME 2018), volume 2, Oxford, England, September 5–7, 2018, pages 631–646, Tarquin.
- Efficient Foldings of Triangular and Hexagonal Mazes
(joint work with Jason S. Ku and Madonna Yoder)
in Origami^{7}: Proceedings of the 7th International Meeting on Origami in Science, Mathematics and Education (OSME 2018), volume 2, Oxford, England, September 5–7, 2018, pages 647–652, Tarquin.
- 2,664 Coin-Sliding Font Puzzles
(joint work with Martin L. Demaine)
in Exchange Book of the 13th Gathering for Gardner (G4G13), Atlanta, Georgia, April 12–25, 2018, to appear.
- Geometry and Topology of Polygonal Linkages
(joint work with Robert Connelly)
in CRC Handbook of Discrete and Computational Geometry, Third Edition, November 2017, chapter 9, pages 233–256.
- Clickomania is Hard Even With Two Colors and Columns
(joint work with Aviv Adler, Adam Hesterberg, Quanquan Liu, and Mikhail Rudoy)
in The Mathematics of Various Entertaining Subjects (MOVES 2015), volume 2, 2017, pages 325–363, Princeton University Press.
- Tangled Tangles
(joint work with Martin L. Demaine, Adam Hesterberg, Quanquan Liu, Ron Taylor, and Ryuhei Uehara)
in The Mathematics of Various Entertaining Subjects (MOVES 2015), volume 2, 2017, pages 141–152, Princeton University Press.
- Computational Complexity of Arranging Music
(joint work with William S. Moses)
in The Mathematics of Various Entertaining Subjects (MOVES 2015), volume 2, 2017, pages 364–378, Princeton University Press.
- Secret Messages in Juggling and Card Shuffling
(joint work with Martin L. Demaine)
in Exchange Book of the 12th Gathering for Gardner (G4G12), Atlanta, Georgia, March 31–April 3, 2016, to appear.
- Narrow Misère Dots-and-Boxes
(joint work with Sébastien Collette, Martin L. Demaine, and Stefan Langerman)
in Games of No Chance 4, edited by Richard J. Nowakowski, 2015, pages 57–64, Cambridge University Press.
- Bidimensionality
(joint work with Fedor Fomin, MohammadTaghi Hajiaghayi, and Dimitrios Thilikos)
in Encyclopedia of Algorithms, 2015, pages 1–5, Springer.
- Rigid Flattening of Polyhedra with Slits
(joint work with Zachary Abel, Robert Connelly, Martin Demaine, Thomas Hull, Anna Lubiw, and Tomohiro Tachi)
in Origami^{6}: Proceedings of the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), volume 1, Tokyo, Japan, August 10–13, 2014, pages 109–118, American Mathematical Society.
- Scaling a Surface down to Any Fraction by Twist Folding
(joint work with Martin L. Demaine and Kayhan F. Qaiser)
in Origami^{6}: Proceedings of the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), volume 1, Tokyo, Japan, August 10–13, 2014, pages 201–208, American Mathematical Society.
- Characterization of Curved Creases and Rulings: Design and Analysis of Lens Tessellations
(joint work with Martin L. Demaine, David A. Huffman, Duks Koschitz, and Tomohiro Tachi)
in Origami^{6}: Proceedings of the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), volume 1, Tokyo, Japan, August 10–13, 2014, pages 209–230, American Mathematical Society.
- Filling a Hole in a Crease Pattern: Isometric Mapping of a Polygon given a Folding of its Boundary
(joint work with Jason Ku)
in Origami^{6}: Proceedings of the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), Tokyo, Japan, August 10–13, 2014, pages 177–188, American Mathematical Society.
- Weaving a Uniformly Thick Sheet from Rectangles
(joint work with Eli Davis, Martin L. Demaine, and Jennifer Ramseyer)
in Origami^{6}: Proceedings of the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), Tokyo, Japan, August 10–13, 2014, pages 177–188, American Mathematical Society.
- Linkage Puzzle Font
(joint work with Martin L. Demaine)
in Exchange Book of the 11th Gathering for Gardner (G4G11), Atlanta, Georgia, March 19–23, 2014, to appear.
- Balloon Polyhedra
(joint work with Martin L. Demaine and Vi Hart)
in Shaping Space: A Polyhedral Approach, edited by Marjorie Senechal, Second Edition, 2013, pages 33–40.
- Variations on Instant Insanity
(joint work with Martin L. Demaine, Sarah Eisenstat, Thomas D. Morgan, and Ryuhei Uehara)
in Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (Ianfest-66), edited by Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, Lecture Notes in Computer Science, volume 8066, August 15–16, 2013, pages 33–47.
- Reconstructing David Huffman's Legacy in Curved-Crease Folding
(joint work with Martin L. Demaine and Duks Koschitz)
in Origami^{5}: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, pages 39–52, A K Peters.
- Degenerative Coordinates in 22.5° Grid System
(joint work with Tomohiro Tachi)
in Origami^{5}: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, to appear, A K Peters.
- Folding Any Orthogonal Maze
(joint work with Martin L. Demaine and Jason Ku)
in Origami^{5}: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, pages 449–454, A K Peters.
- Circle Packing for Origami Design Is Hard
(joint work with Sándor P. Fekete and Robert J. Lang)
in Origami^{5}: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, pages 609–626, A K Peters.
- Universal Hinge Patterns to Fold Orthogonal Shapes
(joint work with Nadia M. Benbernou, Martin L. Demaine, and Aviv Ovadya)
in Origami^{5}: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, pages 405–420, A K Peters.
- Conveyer-Belt Alphabet
(joint work with Martin L. Demaine and Belén Palop)
in Findings in Elasticity, edited by Hester Aardse and Astrid van Baalen, April 2010, pages 86–89, Pars Foundation, Lars Müller Publishers.
- Conveyer Belt Puzzle Font
(joint work with Martin L. Demaine and Belén Palop)
in Exchange Book of the 9th Gathering for Gardner (G4G9), Atlanta, Georgia, March 24–28, 2010, to appear.
- Origami Maze Puzzle Font
(joint work with Martin L. Demaine and Jason Ku)
in Exchange Book of the 9th Gathering for Gardner (G4G9), Atlanta, Georgia, March 24–28, 2010, to appear.
- Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
(joint work with Robert A. Hearn)
in Games of No Chance 3, edited by Michael H. Albert and Richard J. Nowakowski, Mathematical Sciences Research Institute Publications, volume 56, 2009, pages 3–56, Cambridge University Press.
- The Complexity of Dyson Telescopes
(joint work with Martin L. Demaine, Rudolf Fleischer, Robert A. Hearn, and Timo von Oertzen)
in Games of No Chance 3, edited by Michael H. Albert and Richard J. Nowakowski, Mathematical Sciences Research Institute Publications, volume 56, 2009, pages 271–285, Cambridge University Press.
- Bidimensionality (2004; Demaine, Fomin, Hajiaghayi, Thilikos)
(joint work with MohammadTaghi Hajiaghayi)
in Encyclopedia of Algorithms, 2008, pages 88–90, Springer-Verlag.
- Approximation Schemes for Planar Graph Problems (1983, 1984; Baker)
(joint work with MohammadTaghi Hajiaghayi)
in Encyclopedia of Algorithms, 2008, pages 59–62, Springer-Verlag.
- All Polygons Flip Finitely… Right?
(joint work with Blaise Gassend, Joseph O'Rourke, and Godfried T. Toussaint)
in Surveys on Discrete and Computational Geometry: Twenty Years Later, edited by J. Goodman, J. Pach, and R. Pollack, Contemporary Mathematics, volume 453, 2008, pages 231–255, American Mathematical Society. Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, June 18–22, 2006, Snowbird, Utah.
- Coin-Flipping Magic
(joint work with Nadia Benbernou, Martin L. Demaine, and Benjamin Rossman)
in Exchange Book of the 8th Gathering for Gardner (G4G8), Atlanta, Georgia, March 2008.
- A Survey of Folding and Unfolding in Computational Geometry
(joint work with Joseph O'Rourke)
in Combinatorial and Computational Geometry, edited by Jacob E. Goodman, János Pach, and Emo Welzl, Mathematical Sciences Research Institute Publications, volume 52, August 2005, pages 167–211, Cambridge University Press.
- Facet Ordering and Crease Assignment in Uniaxial Bases
(joint work with Robert J. Lang)
in Origami^{4}: Proceedings of the 4th International Meeting of Origami Science, Math, and Education (OSME 2006), Pasadena, California, September 8–10, 2006, pages 189–205, A K Peters.
- Folding Paper Shopping Bags
(joint work with Devin J. Balkcom, Martin L. Demaine, John A. Ochsendorf, and Zhong You)
in Origami^{4}: Proceedings of the 4th International Meeting of Origami Science, Math, and Education (OSME 2006), Pasadena, California, September 8–10, 2006, pages 315–334, A K Peters.
- Sliding-Coin Puzzles
(joint work with Martin L. Demaine)
in Tribute to a Mathemagician, 2004, pages 63–72, A K Peters.
- Fold-and-Cut Magic
(joint work with Martin L. Demaine)
in Tribute to a Mathemagician, 2004, pages 23–30, A K Peters.
- Geometry and Topology of Polygonal Linkages
(joint work with Robert Connelly)
in CRC Handbook of Discrete and Computational Geometry, Second Edition, 2004, chapter 9, pages 197–218.
- Vertex-Unfolding of Simplicial Manifolds
(joint work with David Eppstein, Jeff Erickson, George W. Hart, and Joseph O'Rourke)
in Discrete Geometry: In Honor of W. Kuperberg's 60th Birthday, 2003, pages 215–228, Marcer Dekker Inc..
- Infinitesimally Locked Self-Touching Linkages with Applications to Locked Trees
(joint work with Robert Connelly and Günter Rote)
in Physical Knots: Knotting, Linking, and Folding of Geometric Objects in R^{3}, edited by Jorge Calvo, Kenneth Millett, and Eric Rawdon, 2002, pages 287–311, American Mathematical Society. Collection of papers from the Special Session on Physical Knotting and Unknotting at the AMS Spring Western Section Meeting, Las Vegas, Nevada, April 21–22, 2001.
- Cache-Oblivious Algorithms and Data Structures
in Lecture Notes from the EEF Summer School on Massive Data Sets, BRICS, University of Aarhus, Denmark, June 27–July 1, 2002.
- The Complexity of Clickomania
(joint work with Therese C. Biedl, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, and J. Ian Munro)
in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 389–404, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.
- Phutball Endgames are Hard
(joint work with Martin L. Demaine and David Eppstein)
in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 351–360, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.
- Coin-Moving Puzzles
(joint work with Martin L. Demaine and Helena A. Verrill)
in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 405–431, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.
- Approximating the Canadian Traveller Problem with Online Randomization
(joint work with Yamming Huang, Chung-Shou Liao, and Kunihiko Sadakane)
volume 83, number 5, 2021, pages 1524–1543.
- Characterizing Universal Reconfigurability of Modular Pivoting Robots
(joint work with Hugo A. Akitaya, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán)
in Proceedings of the 37th International Symposium on Computational Geometry (SoCG 2021), edited by Kevin Buchin and \'Eric Colin de Verdière, 2021, 10:1–10:20.
- Scalable Equilibrium Computation in Multi-agent Influence Games on Networks
(joint work with Fotini Christia, Michael Curry, Constantinos Daskalakis, John P. Dickerson, MohammadTaghi Hajiaghayi, Adam Hesterberg, Marina Knittel, and Aidan Milliff)
in Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), February 2021, pages 5277–5285.
- Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
(joint work with Josh Brunner, Dylan Hendrickson, and Julian Wellman)
in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Hong Kong, December 14–18, 2020, 33:1–33:14.
- Recursed Is Not Recursive: A Jarring Result
(joint work with Justin Kopinsky and Jayson Lynch)
in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Hong Kong, December 14–18, 2020, 35:1–35:15.
- Arithmetic Expression Construction
(joint work with Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, and Lillian Zhang)
in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Hong Kong, December 14–18, 2020, 41:1–41:15.
- Tatamibari is NP-complete
(joint work with Aviv Adler, Jeffrey Bosboom, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch)
in Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020), La Maddalena, Italy, September 28–30, 2020, 1:1–1:24.
- Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
(joint work with Joshua Ani, Jeffrey Bosboom, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch)
in Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020), La Maddalena, Italy, September 28–30, 2020, 3:1–3:23.
- 1 × 1 Rush Hour with Fixed Blocks is PSPACE-complete
(joint work with Josh Brunner, Lily Chung, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff)
in Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020), La Maddalena, Italy, September 28–30, 2020, 7:1–7:14.
- Folding Small Polyominoes into a Unit Cube
(joint work with Kingston Yao Czajkowski, Martin L. Demaine, Kim Eppling, Robby Kraft, Klara Mundilova, and Levi Smith)
in Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020), Saskatchewan, Saskatoon, Canada, August 5–7, 2020.
- 2048 Without Merging
(joint work with Hugo Akitaya, Jason S. Ku, Jayson Lynch, Mike Paterson, and Csaba D. Tóth)
in Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020), Saskatchewan, Saskatoon, Canada, August 5–7, 2020.
- New Results in Sona Drawing: Hardness and TSP Separation
(joint work with Man-Kwun Chiu, Yevhenii Diomidov, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada, and Mikhail Rudoy)
in Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020), Saskatchewan, Saskatoon, Canada, August 5–7, 2020.
- Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra
(joint work with Martin L. Demaine and David Eppstein)
in Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020), Saskatchewan, Saskatoon, Canada, August 5–7, 2020.
- Some Polycubes Have No Edge-Unzipping
(joint work with Martin L. Demaine, David Eppstein, and Joseph O'Rourke)
in Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020), Saskatchewan, Saskatoon, Canada, August 5–7, 2020.
- Finding Closed Quasigeodesics on Convex Polyhedra
(joint work with Adam C. Hesterberg and Jason S. Ku)
in Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020), June 23–26, 2020, 33:1–33:13.
- Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
(joint work with Dylan Hendrickson and Jayson Lynch)
in Proceedings of the 11th Conference on Innovations in Theoretical Computer Science (ITCS 2020), Seattle, Washington, January 12–14, 2020, 62:1–62:42.
- Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
(joint work with Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel)
in Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), edited by Michael A. Bender, Ola Svensson, and Grzegorz Herman, Leibniz International Proceedings in Informatics, volume 144, Munich, Germany, September 9–13, 2019, 37:1–37:15.
- Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers
(joint work with Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Vida Dujmović, Robin Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, and Vera Sacristán)
in Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), edited by Michael A. Bender, Ola Svensson, and Grzegorz Herman, Leibniz International Proceedings in Informatics, volume 144, Munich, Germany, September 9–13, 2019, 3:1–3:14.
- Minimal Ununfoldable Polyhedron
(joint work with Hugo A. Akitaya, David Eppstein, Tomohiro Tachi, and Ryuhei Uehara)
in Abstracts from the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2019), Tokyo, Japan, September 6–9, 2019, pages 27–28.
- PSPACE-completeness of Pulling Blocks to Reach a Goal
(joint work with Joshua Ani, Sualeh Asif, Yevhenii Diomidov, Dylan Hendrickson, Jayson Lynch, Sarah Scheffler, and Adam Suhl)
in Abstracts from the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2019), Tokyo, Japan, September 6–9, 2019, pages 31–32.
- Tetris is NP-hard even with O(1) Columns
(joint work with Sualeh Asif, Jayson Lynch, and Mihir Singhal)
in Abstracts from the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2019), Tokyo, Japan, September 6–9, 2019, pages 37–38.
- Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
(joint work with Jeffrey Bosboom, Charlotte Chen, Lily Chung, Spencer Compton, Michael Coulombe, Martin L. Demaine, Ivan Tadeu Ferreira Antunes Filho, Dylan Hendrickson, Adam Hesterberg, Calvin Hsu, William Hu, Oliver Korten, Zhezheng Luo, and Lillian Zhang)
in Abstracts from the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2019), Tokyo, Japan, September 6–9, 2019, pages 47–48.
- Folding Polyominoes with Holes into a Cube
(joint work with Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, Irina Kostitsyna, Maarten Löffler, Zuzana Masárová, Klara Mundilova, and Christiane Schmidt)
in Proceedings of the 31st Canadian Conference in Computational Geometry (CCCG 2019), Edmonton, Alberta, Canada, August 8–10, 2019, pages 164–170.
- Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly
(joint work with John Calvin Alumbaugh, Joshua J. Daymude, Matthew J. Patitz, and Andréa W. Richa)
in Proceedings of the 25th International Conference on DNA Computing and Molecular Programming, edited by Chris Thachuk and Yan Liu, Lecture Notes in Computer Science, volume 11648, Seattle, Washington, August 5–9, 2019, pages 140–158.
- Reconfiguring Undirected Paths
(joint work with David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, and Yushi Uno)
in Proceedings of the 17th International Symposium on Algorithms and Data Structures (WADS 2019), August 5–7, 2019, pages 353–365.
- Impossible Folding Font
(joint work with Martin L. Demaine, Tomoko Taniguchi, and Ryuhei Uehara)
in Proceedings of 22nd Annual Conference of BRIDGES: Mathematics, Music, Art, Architecture, Culture (BRIDGES 2019), Linz, Austria, July 16–20, 2019, pages 51–58.
- Belga B-Trees
(joint work with John Iacono, Grigorios Koumoutsos, and Stefan Langerman)
in Proceedings of the 14th International Computer Science Symposium in Russia (CSR 2019), edited by René van Bevern and Gregory Kucherov, Lecture Notes in Computer Science, volume 11532, Novosibirsk, Russia, July 1–5, 2019, pages 93–105.
- Negative Instance for the Edge Patrolling Beacon Problem
(joint work with Zachary Abel, Hugo A. Akitaya, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jason S. Ku, and Jayson Lynch)
in Abstracts from the 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2018), Manila, Philippines, September 1–3, 2018, to appear.
- How Efficiently Can Nets of Polycubes Pack a Rectangle?
(joint work with Martin L. Demaine, Ryuhei Uehara, Yushi Uno, and Andrew Winslow)
in Abstracts from the 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2018), Manila, Philippines, September 1–3, 2018, to appear.
- Toward Unfolding Doubly Covered n-Stars
(joint work with Hugo A. Akitaya, Brad Ballinger, Mirela Damian, Martin L. Demaine, Robin Flatland, Irina Kostitsyna, Jason S. Ku, Stefan Langerman, Joseph O'Rourke, and Ryuhei Uehara)
in Abstracts from the 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2018), Manila, Philippines, September 1–3, 2018, to appear.
- Tetramonohedron Development with Minimum Cut Length
(joint work with Martin L. Demaine and Ryuhei Uehara)
in Abstracts from the 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2018), Manila, Philippines, September 1–3, 2018, to appear.
- Know When to Fold 'Em: Self-assembly of Shapes by Folding in Oritatami
(joint work with Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Nicolas Schabanel, Shinnosuke Seki, and Hadley Thomas)
in Proceedings of the 24th International Conference on DNA Computing and Molecular Programming (DNA 2018), Jinan, China, October 8–12, 2018.
- Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers
(joint work with Quanquan C. Liu)
in Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), Vienna, Austria, July 16–18, 2018, pages 195–204.
- Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
(joint work with Jean Cardinal, David Eppstein, Robert A. Hearn, and Andrew Winslow)
in Proceedings of the 24th International Conference on Computing and Combinatorics (COCOON 2018), Qing Dao, China, July 2–4, 2018, pages 365–377.
- Tree-Residue Vertex-Breaking: a new tool for proving hardness
(joint work with Mikhail Rudoy)
in Proceedings of the 20th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), Malmö, Sweden, June 18–20, 2018, 32:1–32:14.
- Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
(joint work with Lijie Chen, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu)
in Proceedings of the 20th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), Malmö, Sweden, June 18–20, 2018, 33:1–33:12.
- Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
(joint work with Zachary Abel, Jeffrey Bosboom, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy)
in Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy, June 13–15, 2018, 3:1–3:21.
- Computational Complexity of Motion Planning of a Robot through Simple Gadgets
(joint work with Isaac Grosof, Jayson Lynch, and Mikhail Rudoy)
in Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy, June 13–15, 2018, 18:1–18:21.
- The Computational Complexity of Portal and Other 3D Video Games
(joint work with Joshua Lockhart and Jayson Lynch)
in Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy, June 13–15, 2018, 19:1–19:22.
- Computational Complexity of Generalized Push Fight
(joint work with Jeffrey Bosboom and Mikhail Rudoy)
in Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy, June 13–15, 2018, 11:1–11:21.
- Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
(joint work with Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer)
in Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), June 11–14, 2018, 29:1–29:15.
- Solving the Rubik's Cube Optimally is NP-complete
(joint work with Sarah Eisenstat and Mikhail Rudoy)
in Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France, February 28–March 3, 2018.
- Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy
(joint work with Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams)
in Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Cambridge, Massachusetts, January 11–14, 2018, 34:1–34:23.
- Cookie Clicker
(joint work with Hiro Ito, Stefan Langerman, Jayson Lynch, Mikhail Rudoy, and Kai Xiao)
in Abstracts from the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2017), Tokyo, Japan, August 29–September 1, 2017, pages 29–30.
- Infinite All-Layers Simple Foldability
(joint work with Hugo Akitaya, Cordelia Avery, Joseph Bergeron, Justin Kopinsky, and Jason Ku)
in Abstracts from the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2017), Tokyo, Japan, August 29–September 1, 2017, pages 61–62.
- Path Puzzles: Discrete Tomography with a Path Constraint is Hard
(joint work with Jeffrey Bosboom, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, and Justin Kopinsky)
in Abstracts from the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2017), Tokyo, Japan, August 29–September 1, 2017, pages 102–103.
- Polyhedral Characterization of Reversible Hinged Dissections
(joint work with Jin Akiyama and Stefan Langerman)
in Abstracts from the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2017), Tokyo, Japan, August 29–September 1, 2017, pages 102–103.
- Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron
(joint work with Nadia M. Benbernou, Martin L. Demaine, and Anna Lubiw)
in Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2017), July 31–August 2, 2017, pages 109–120.
- Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
(joint work with Quanquan C. Liu)
in Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2017), July 31–August 2, 2017, pages 313–324.
- Snipperclips: Cutting Tools into Desired Polygons using Themselves
(joint work with Matias Korman, André van Renssen, and Marcel Roeloffzen)
in Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), Ottawa, Ontario, Canada, July 26–28, 2017, to appear.
- Computing 3SAT on a Fold-and-Cut Machine
(joint work with Byoungkwon An, Martin L. Demaine, and Jason S. Ku)
in Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), Ottawa, Ontario, Canada, July 26–28, 2017, to appear.
- Common Development of Prisms, Anti-Prisms, Tetrahedra, and Wedges
(joint work with Amartya Shankha Biswas)
in Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), Ottawa, Ontario, Canada, July 26–28, 2017, to appear.
- Origamizer: A Practical Algorithm for Folding Any Polyhedron
(joint work with Tomohiro Tachi)
in Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia, July 4–7, 2017, 34:1–34:15.
- Push-Pull Block Puzzles are Hard
(joint work with Isaac Grosof and Jayson Lynch)
in Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017), Lecture Notes in Computer Science, volume 10236, Athens, Greece, May 24–26, 2017, pages 177–195.
- Sequentially Swapping Colored Tokens on Graphs
(joint work with Katsuhisa Yamanaka, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno)
in Proceedings of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017), Hsinchu, Taiwan, March 29–31, 2017, pages 435–447.
- Three Colors Suffice: Conflict-Free Coloring of Planar Graphs
(joint work with Zachary Abel, Victor Alvarez, Sándor Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, and Christian Scheffer)
in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, January 16–19, 2017, pages 1951–1963.
- Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces
(joint work with Cameron Chalk, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, and Tim Wylie)
in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, January 16–19, 2017, pages 225–238.
- A New File Standard to Represent Folded Structures
(joint work with Jason S. Ku and Robert J. Lang)
in Abstracts from the 26th Fall Workshop on Computational Geometry, October 27–28, 2016, to appear.
- Zero-Area Reciprocal Diagram of Origami
(joint work with Martin L. Demaine, David A. Huffman, Thomas C. Hull, Duks Koschitz, and Tomohiro Tachi)
in Proceedings of the IASS Annual Symposium 2016, edited by K. Kawaguchi, M. Ohsaki, and T. Takeuchi, Tokyo, Japan, September 26–30, 2016.
- Folding and Punching Paper
(joint work with Yasuhiko Asao, Martin L. Demaine, Hideaki Hosaka, Akitoshi Kawamura, Tomohiro Tachi, and Kazune Takahashi)
in Abstracts from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2016), Tokyo, Japan, September 2–4, 2016, to appear.
- Even 1 × n Edge Matching and Jigsaw Puzzles are Really Hard
(joint work with Jeffrey Bosboom, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, and Anak Yodpinyanee)
in Abstracts from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2016), Tokyo, Japan, September 2–4, 2016, to appear.
- Simple Folding is Really Hard
(joint work with Hugo Akitaya and Jason S. Ku)
in Abstracts from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2016), Tokyo, Japan, September 2–4, 2016, to appear.
- Satisfying Multiple Boundary Conditions
(joint work with Jason S. Ku)
in Abstracts from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2016), Tokyo, Japan, September 2–4, 2016, to appear.
- Unfolding and Dissection of Multiple Cubes
(joint work with Zachary Abel, Brad Ballinger, Martin L. Demaine, Jeff Erickson, Adam Hesterberg, Hiro Ito, Irina Kostitsyna, Jayson Lynch, and Ryuhei Uehara)
in Abstracts from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2016), Tokyo, Japan, September 2–4, 2016, to appear.
- The Complexity of Hex and the Jordan Curve Theorem
(joint work with Aviv Adler and Constantinos Daskalakis)
in Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Rome, Italy, July 12–15, 2016, 24:1–24:14.
- Cache-Adaptive Analysis
(joint work with Michael A. Bender, Roozbeh Ebrahimi, Jeremy T. Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch, and Samuel McCauley)
in Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), Pacific Grove, California, 2016, pages 135–144.
- Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms
(joint work with Nirvan Tyagi and Jayson Lynch)
in Proceedings of the 8th International Conference on Reversible Computation (RC 2016), Lecture Notes in Computer Science, volume 9720, Bologna, Italy, July 7–8, 2016, pages 121–136.
- A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting
(joint work with MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Dániel Marx)
in Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), Cambridge, Massachusetts, 2016, pages 570–583.
- Who Needs Crossings? Hardness of Plane Graph Rigidity
(joint work with Zachary Abel, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl)
in Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), Boston, Massachusetts, June 14–18, 2016, 3:1–3:15.
- The Fewest Clues Problem
(joint work with Fermi Ma, Erik Waingarten, Ariel Schvartzman, and Scott Aaronson)
in Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016), La Maddalena, Italy, June 8–10, 2016, 12:1–12:12.
- Super Mario Bros. is Harder/Easier than We Thought
(joint work with Giovanni Viglietta and Aaron Williams)
in Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016), La Maddalena, Italy, June 8–10, 2016, 13:1–13:14.
- Energy-Efficient Algorithms
(joint work with Jayson Lynch, Geronimo J. Mirano, and Nirvan Tyagi)
in Proceedings of the 7th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016), Cambridge, Massachusetts, January 14–16, 2016, pages 321–332.
- Dissection with the Fewest Pieces is Hard, Even to Approximate
(joint work with Jeffrey Bosboom, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, and Anak Yodpinyanee)
in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 37–48.
- Symmetric assembly puzzles are hard, beyond a few pieces
(joint work with Matias Korman, Jason S. Ku, Joseph S. B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, and Yushi Uno)
in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 180–192.
- Box pleating is hard
(joint work with Hugo A. Akitaya, Kenneth C. Cheung, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi, and Ryuhei Uehara)
in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 167–179.
- Mario Kart is Hard
(joint work with Jeffrey Bosboom, Adam Hesterberg, Jayson Lynch, and Erik Waingarten)
in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 49–59.
- Bust-A-Move/Puzzle Bobble is NP-complete
(joint work with Stefan Langerman)
in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 94–104.
- Single-player and two-player Buttons & Scissors games
(joint work with Kyle Burke, Robert Hearn, Adam Hesterberg, Michael Hoffmann, Hiro Ito, Irina Kostitsyna, Maarten Löffler, Yushi Uno, Christiane Schmidt, Ryuhei Uehara, and Aaron Williams)
in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 60–72.
- Continuous flattening of orthogonal polyhedra
(joint work with Martin L. Demaine, Jin-Ichi Itoh, and Chie Nara)
in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 85–93.
- k-piece dissection is NP-hard
(joint work with Jeffrey Bosboom, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, and Anak Yodpinyanee)
in Abstracts from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Kyoto, Japan, September 14–16, 2015, to appear.
- Symmetric assembly puzzles are hard, beyond a few pieces
(joint work with Matias Korman, Jason S. Ku, Joseph S. B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, and Yushi Uno)
in Abstracts from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Kyoto, Japan, September 14–16, 2015, to appear.
- Box pleating is hard
(joint work with Hugo A. Akitaya, Kenneth C. Cheung, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi, and Ryuhei Uehara)
in Abstracts from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Kyoto, Japan, September 14–16, 2015, to appear.
- Mario Kart is Hard
(joint work with Jeffrey Bosboom, Adam Hesterberg, Jayson Lynch, and Erik Waingarten)
in Abstracts from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Kyoto, Japan, September 14–16, 2015, to appear.
- Bust-A-Move/Puzzle Bobble is NP-complete
(joint work with Stefan Langerman)
in Abstracts from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Kyoto, Japan, September 14–16, 2015, to appear.
- Single-player and two-player Buttons & Scissors games
(joint work with Kyle Burke, Robert Hearn, Adam Hesterberg, Michael Hoffmann, Hiro Ito, Irina Kostitsyna, Maarten Löffler, Yushi Uno, Christiane Schmidt, Ryuhei Uehara, and Aaron Williams)
in Abstracts from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Kyoto, Japan, September 14–16, 2015, to appear.
- Continuous flattening of orthogonal polyhedra
(joint work with Martin L. Demaine, Jin-Ichi Itoh, and Chie Nara)
in Abstracts from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Kyoto, Japan, September 14–16, 2015, to appear.
- New Geometric Algorithms for Fully Connected Staged Self-Assembly
(joint work with Sándor Fekete, Christian Scheffer, and Arne Schmidt)
in Proceedings of the 21st International Conference on DNA Computing and Molecular Programming (DNA 2015), Cambridge, Massachusetts, August 17–21, 2015, pages 104–116.
- Folding Polyominoes into (Poly)Cubes
(joint work with Oswin Aichholzer, Michael Biro, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Adam Hesterberg, Irina Kostitsyna, and Christiane Schmidt)
in Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), Kingston, Ontario, Canada, August 10–12, 2015.
- Computational complexity of numberless Shakashaka
(joint work with Aviv Adler, Michael Biro, Mikhail Rudoy, and Christiane Schmidt)
in Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), Kingston, Ontario, Canada, August 10–12, 2015.
- Cache-Oblivious Iterated Predecessor Queries via Range Coalescing
(joint work with Vineet Gopal and William Hasenplaugh)
in Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015), Victoria, British Columbia, Canada, August 5–7, 2015, pages 249–262.
- Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing
(joint work with Tim Kaler, Quanquan Liu, Aaron Sidford, and Adam Yedidia)
in Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015), Victoria, British Columbia, Canada, August 5–7, 2015, pages 263–275.
- Matching regions in the plane using non-crossing segments
(joint work with Greg Aloupis, Esther M. Arkin, David Bremner, Sándor P. Fekete, Bahram Kouhestani, and Joseph S. B. Mitchell)
in Abstracts from the 16th Spanish Meeting on Computational Geometry (EGC 2015), Barcelona, Spain, July 1–3, 2015, to appear.
- Tilt: The Video – Designing Worlds to Control Robot Swarms with Only Global Signals
(joint work with Aaron T. Becker, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright)
in 24th Multimedia Exposition in Computational Geometry, Proceedings of the 31st International Symposium on Computational Geometry (SoCG 2015), Eindhoven, The Netherlands, June 22–25, 2015, pages 16–18.
- Particle computation: Device fan-out and binary memory
(joint work with Hamed Mohtasham Shad, Rose Morris-Wright, Sándor P. Fekete, and Aaron Becker)
in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2015), Seattle, Washington, May 26–30, 2015, pages 5384–5389.
- New Geometric Algorithms for Staged Self-Assembly
(joint work with Sándor Fekete and Arne Schmidt)
in Abstracts from the 31st European Workshop on Computational Geometry (EuroCG 2015), Ljubljana, Slovenia, March 15–18, 2015, to appear.
- Folding a Paper Strip to Minimize Thickness
(joint work with David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, and Yushi Uno)
in Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM 2015), Lecture Notes in Computer Science, volume 8973, Dhaka, Bangladesh, February 26–28, 2015, pages 113–124.
- A Dissimilarity Measure for Comparing Origami Crease Patterns
(joint work with Seung Man Oh, Godfried T. Toussaint, and Martin L. Demaine)
in Proceedings of the 4th International Conference on Pattern Recognition Applications and Methods (ICPRAM 2015), volume 1, Lisbon, Portugal, January 10–12, 2015, pages 386–393.
- Linear-time algorithm for sliding tokens on trees
(joint work with Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada)
in Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), Lecture Notes in Computer Science, volume 8889, December 15–17, 2014, pages 389–400.
- Simple Folding is Strongly NP-Complete
(joint work with Hugo A. Akitaya and Jason S. Ku)
in Abstracts from the 24th Annual Fall Workshop on Computational Geometry, Storrs, Connecticut, October 31–November 1, 2014.
- On Streaming and Communication Complexity of the Set Cover Problem
(joint work with Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian)
in Proceedings of the 28th International Symposium on Distributed Computing (DISC 2014), Austin, Texas, October 12–15, 2014, pages 484–498.
- Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
(joint work with Zachary Abel, Martin L. Demaine, David Eppstein, Anna Lubiw, and Ryuhei Uehara)
in Proceedings of the 22nd International Symposium on Graph Drawing (GD 2014), Würzburg, Germany, September 24–26, 2014, pages 272–283.
- Rigid Flattening of Polyhedra with Slits
(joint work with Zachary Abel, Robert Connelly, Martin Demaine, Thomas Hull, Anna Lubiw, and Tomohiro Tachi)
in Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), Tokyo, Japan, August 10–13, 2014, to appear.
- Scaling a Surface down to Any Fraction by Twist Folding
(joint work with Martin L. Demaine and Kayhan F. Qaiser)
in Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), Tokyo, Japan, August 10–13, 2014, to appear.
- Designing Curved-Crease Tessellations of Lenses: Qualitative Properties of Rulings
(joint work with Martin L. Demaine, David A. Huffman, Duks Koschitz, and Tomohiro Tachi)
in Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), Tokyo, Japan, August 10–13, 2014, to appear.
- Filling a Hole in a Crease Pattern: Isometric Mapping of a Polygon given a Folding of its Boundary
(joint work with Jason Ku)
in Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), Tokyo, Japan, August 10–13, 2014, to appear.
- Weaving a Uniformly Thick Sheet from Rectangles
(joint work with Eli Davis, Martin L. Demaine, and Jennifer Ramseyer)
in Abstracts from the 6th International Meeting on Origami in Science, Mathematics and Education (OSME 2014), Tokyo, Japan, August 10–13, 2014, to appear.
- One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
(joint work with Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, and Damien Woods)
in Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), edited by J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, Lecture Notes in Computer Science, volume 8572, 2014, pages 368–379.
- Canadians Should Travel Randomly
(joint work with Yamming Huang, Chung-Shou Liao, and Kunihiko Sadakane)
in Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), edited by J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, Lecture Notes in Computer Science, volume 8572, 2014, pages 380–391.
- Fun with Fonts: Algorithmic Typography
(joint work with Martin L. Demaine)
in Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Italy, July 1–3, 2014, pages 16–27.
- Swapping Labeled Tokens on Graphs
(joint work with Katsuhisa Yamanaka, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno)
in Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Italy, July 1–3, 2014, pages 364–375.
- Playing Dominoes is Hard, Except by Yourself
(joint work with Fermi Ma and Erik Waingarten)
in Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Italy, July 1–3, 2014, pages 137–146.
- Classic Nintendo Games are (Computationally) Hard
(joint work with Greg Aloupis, Alan Guo, and Giovanni Viglietta)
in Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Italy, July 1–3, 2014, pages 40–51.
- Continuously Flattening Polyhedra Using Straight Skeletons
(joint work with Zachary Abel, Martin L. Demaine, Jin-Ichi Itoh, Anna Lubiw, Chie Nara, and Joseph O'Rourke)
in Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), Kyoto, Japan, June 8–11, 2014, pages 396–405.
- Particle Computation: Designing Worlds to Control Robot Swarms with Only Global Signals
(joint work with Aaron Becker, Sándor Fekete, and James McLurkin)
in Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA 2014), Hong Kong, China, May 31–June 7, 2014, pages 6751–6756.
- An End-To-End Approach to Making Self-Folded 3D Surface Shapes by Uniform Heating
(joint work with Byoungkwon An, Shuhei Miyashita, Michael T. Tolley, Daniel M. Aukes, Laura Meeker, Martin L. Demaine, Robert J. Wood, and Daniela Rus)
in Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA 2014), Hong Kong, China, May 31–June 7, 2014, pages 1466–1473.
- How to Influence People with Partial Incentives
(joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, and Morteza Zadimoghaddam)
in Proceedings of the 23rd International World Wide Web Conference (WWW 2014), Seoul, Korea, April 7–11, 2014, pages 937–948.
- On Wrapping Spheres and Cubes with Rectangular Paper
(joint work with Alex Cole and Eli Fox-Epstein)
in Revised Papers from the 12th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2013), Lecture Notes in Computer Science, Tokyo, Japan, September 17–19, 2013, to appear.
- On Wrapping Spheres and Cubes with Rectangular Paper
(joint work with Alex Cole and Eli Fox-Epstein)
in Abstracts from the 12th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2013), Tokyo, Japan, September 17–19, 2013, to appear.
- Reconfiguring Massive Particle Swarms with Limited, Global Control
(joint work with Aaron Becker, Sándor Fekete, Golnax Habibi, and James McLurkin)
in Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2013), Lecture Notes in Computer Science, volume 8243, Sophia Antipolis, France, September 5–6, 2013, pages 51–66.
- Reconstructing David Huffman's Origami Tessellations
(joint work with Eli Davis, Martin L. Demaine, and Jennifer Ramseyer)
in Proceedings of the 37th Mechanisms and Robotics Conference (MR 2013), Portland, Oregon, August 4–7, 2013.
- Joining Unfoldings of 3-D Surfaces
(joint work with Cynthia Sung, Martin L. Demaine, and Daniela Rus)
in Proceedings of the 37th Mechanisms and Robotics Conference (MR 2013), Portland, Oregon, August 4–7, 2013.
- PCB Origami: A material-based design approach to computer-aided foldable electronic devices
(joint work with Yoav Sterman and Neri Oxman)
in Proceedings of the 37th Mechanisms and Robotics Conference (MR 2013), Portland, Oregon, August 4–7, 2013.
- Blame Trees
(joint work with Pavel Panchekha, David Wilson, and Edward Z. Yang)
in Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013), Lecture Notes in Computer Science, volume 8037, London, Ontario, Canada, August 12–14, 2013, pages 280–290.
- Computational complexity and an integer programming model of Shakashaka
(joint work with Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno)
in Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, to appear.
- Zipper Unfolding of Domes and Prismoids
(joint work with Martin L. Demaine and Ryuhei Uehara)
in Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, to appear.
- Covering Folded Shapes
(joint work with Oswin Aichholzer, Greg Aloupis, Martin L. Demaine, Sándor P. Fekete, Michael Hoffmann, Anna Lubiw, Jack Snoeyink, and Andrew Winslow)
in Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, to appear.
- Combining Binary Search Trees
(joint work with John Iacono, Stefan Langerman, and Özgür Özkan)
in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Riga, Latvia, July 8–12, 2013, pages 388–399.
- The two-handed tile assembly model is not intrinsically universal
(joint work with Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods)
in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Riga, Latvia, July 8–12, 2013, pages 400–412.
- Computational Complexity of Piano-Hinged Dissections
(joint work with Zachary Abel, Martin L. Demaine, Takashi Horiyama, and Ryuhei Uehara)
in Abstracts from the 29th European Workshop on Computational Geometry (EuroCG 2013), Braunschweig, Germany, March 17–20, 2013, pages 147–150.
- Algorithms for Designing Pop-Up Cards
(joint work with Zachary Abel, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane Souvaine, Giovanni Viglietta, and Andrew Winslow)
in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Kiel, Germany, February 27–March 2, 2013, pages 269–280.
- Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM
(joint work with Sarah Cannon, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, and Andrew Winslow)
in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Kiel, Germany, February 27–March 2, 2013, pages 172–184.
- Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Know's”
(joint work with Morteza Zadimoghaddam)
in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, Louisiana, January 6–8, 2013, pages 1369–1379.
- Picture-Hanging Puzzles
(joint work with Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, and Mihai Pǎtraşcu)
in Proceedings of the 6th International Conference on Fun with Algorithms (FUN 2012), Lecture Notes in Computer Science, Venice, Italy, June 4–6, 2012, pages 81–93.
- Refold Rigidity of Convex Polyhedra
(joint work with Martin L. Demaine, Jin-ichi Itoh, Anna Lubiw, Chie Nara, and Joseph O'Rourke)
in Abstracts from the 28th European Workshop on Computational Geometry (EuroCG 2012), Assisi, Italy, March 19–21, 2012, pages 101–104.
- Folding Equilateral Plane Graphs
(joint work with Zachary Abel, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, and Isaac Shapiro-Ellowitz)
in Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), Lecture Notes in Computer Science, volume 7074, December 5–8, 2011, pages 574–583.
- Curved Crease Folding: a Review on Art, Design and Mathematics
(joint work with Martin L. Demaine, Duks Koschitz, and Tomohiro Tachi)
in Proceedings of the IABSE-IASS Symposium: Taller, Longer, Lighter (IABSE-IASS 2011), London, England, September 20–23, 2011, to appear.
- One-Dimensional Staged Self-Assembly
(joint work with Sarah Eisenstat, Mashhood Ishaque, and Andrew Winslow)
in Proceedings of the 17th International Conference on DNA Computing and Molecular Programming (DNA 2011), Lecture Notes in Computer Science, volume 6937, Pasadena, California, September 19–23, 2011, pages 100–114.
- Algorithms for Solving Rubik's Cubes
(joint work with Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow)
in Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), September 5–9, 2011, pages 689–700.
- O(1)-Approximations for Maximum Movement Problems
(joint work with Piotr Berman and Morteza Zadimoghaddam)
in Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2011), Princeton, New Jersey, August 17–19, 2011, pages 62–74.
- Lossless Fault-Tolerant Data Structures with Additive Overhead
(joint work with Paul Christiano and Shaunak Kishore)
in Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), Brooklyn, New York, August 15–17, 2011, pages 243–254.
- Flattening Fixed-Angle Chains Is Strongly NP-Hard
(joint work with Sarah Eisenstat)
in Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), Brooklyn, New York, August 15–17, 2011, pages 314–325.
- Edge-guarding Orthogonal Polyhedra
(joint work with Nadia M. Benbernou, Martin L. Demaine, Anastasia Kurdia, Joseph O'Rourke, Godfried Toussaint, Jorge Urrutia, and Giovanni Viglietta)
in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
- Expansive Motions for d-Dimensional Open Chains
(joint work with Sarah Eisenstat)
in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
- Convexifying Polygons Without Losing Visibilities
(joint work with Oswin Aichholzer, Greg Aloupis, Martin L. Demaine, Vida Dujmović, Ferran Hurtado, Anna Lubiw, Günter Rote, André Schulz, Diane L. Souvaine, and Andrew Winslow)
in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
- Common Developments of Several Different Orthogonal Boxes
(joint work with Zachary Abel, Martin Demaine, Hiroaki Matsui, Günter Rote, and Ryuhei Uehara)
in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
- Edge-Unfolding Orthogonal Polyhedra is Strongly NP-Complete
(joint work with Zachary Abel)
in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
- A Topologically Convex Vertex-Ununfoldable Polyhedron
(joint work with Zachary Abel and Martin L. Demaine)
in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
- Open Problems from CCCG 2010
(joint work with Joseph O'Rourke)
in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
- Remarks on Separating Words
(joint work with Sarah Eisenstat, Jeffrey Shallit, and David A. Wilson)
in Proceedings of the 13th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2011), Lecture Notes in Computer Science, volume 6808, Giessen, Germany, July 25–27, 2011, pages 147–157.
- A generalization of the source unfolding of convex polyhedra
(joint work with Anna Lubiw)
in Revised Papers from the 14th Spanish Meeting on Computational Geometry (EGC 2011), edited by Alberto Márquez, Pedro Ramos, and Jorge Urrutia, Lecture Notes in Computer Science, volume 7579, Alcalá de Henares, Spain, June 27–30, 2011, pages 185–199.
- A generalization of the source unfolding of convex polyhedra
(joint work with Anna Lubiw)
in Abstracts from the 14th Spanish Meeting on Computational Geometry (EGC 2011), Alcalá de Henares, Spain, June 27–30, 2011, pages 91–94.
- Meshes preserving minimum feature size
(joint work with Greg Aloupis, Martin L. Demaine, Vida Dujmović, and John Iacono)
in Revised Papers from the 14th Spanish Meeting on Computational Geometry (EGC 2011), edited by Alberto Márquez, Pedro Ramos, and Jorge Urrutia, Lecture Notes in Computer Science, volume 7579, Alcalá de Henares, Spain, June 27–30, 2011, pages 258–273.
- Meshes preserving minimum feature size
(joint work with Greg Aloupis, Martin L. Demaine, Vida Dujmović, and John Iacono)
in Proceedings of the 14th Spanish Meeting on Computational Geometry (EGC 2011), Alcalá de Henares, Spain, June 27–30, 2011, pages 205–208.
- Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications
(joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
in Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011), June 6–8, 2011, pages 441–450.
- Approximability of the Subset Sum Reconfiguration Problem
(joint work with Takehiro Ito)
in Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Lecture Notes in Computer Science, volume 6648, Tokyo, Japan, May 23&