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, volume 98, October 2021, pages 101784.
- 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.
- Unlocking history through automated virtual unfolding of sealed documents imaged by X-ray microtomography
(joint work with Jana Dambrogio, Amanda Ghassaei, Daniel Starza Smith, Holly Jackson, Martin L. Demaine, Graham Davis, David Mills, Rebekah Ahrendt, Nadine Akkerman, and David van der Linden)
Nature Communications, volume 12, March 2021, Article 1184.
- 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 A. Akitaya, Cordelia Avery, Joseph Bergeron, Justin Kopinsky, and Jason S. 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.
- Yin-Yang Puzzles are NP-complete
(joint work with Jayson Lynch, Mikhail Rudoy, and Yushi Uno)
in Proceedings of the 33rd Canadian Conference in Computational Geometry (CCCG 2021), Halifax, Nova Scotia, Canada, August 10–12, 2021, to appear.
- Any Regular Polyhedron Can Transform to Another by O(1) Refoldings
(joint work with Martin L. Demaine, Yevhenii Diomidov, Tonan Kamata, Ryuhei Uehara, and Hanyu Alice Zhang)
in Proceedings of the 33rd Canadian Conference in Computational Geometry (CCCG 2021), Halifax, Nova Scotia, Canada, August 10–12, 2021, to appear.
- Edge-Unfolding Prismatoids: Tall or Rectangular Base
(joint work with Vincent Bian and Rachana Madhukara)
in Proceedings of the 33rd Canadian Conference in Computational Geometry (CCCG 2021), Halifax, Nova Scotia, Canada, August 10–12, 2021, to appear.
- Folding Points to a Point and Lines to a Line
(joint work with Hugo A. Akitaya, Brad Ballinger, Thomas C. Hull, and Christiane Schmidt)
in Proceedings of the 33rd Canadian Conference in Computational Geometry (CCCG 2021), Halifax, Nova Scotia, Canada, August 10–12, 2021, to appear.
- 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–25, 2011, pages 58–69.
- Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor
(joint work with Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers)
in Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Dortmund, Germany, March 10–12, 2011, pages 201–212.
- Embedding Stacked Polytopes on a Polynomial-Size Grid
(joint work with André Schulz)
in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, California, USA, January 22–25, 2011, pages 1177–1187.
- 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)
in Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010), Lecture Notes in Computer Science, volume 6509, The Big Island, Hawaii, USA, December 18–20, 2010, pages 627–652.
- Constant Price of Anarchy in Network Creation Games via Public Service Advertising
(joint work with Morteza Zadimoghaddam)
in Proceedings of the 7th International Workshop on Algorithms and Models for the Web-Graph (WAW 2010), edited by Ravi Kumar and Dandapani Sivakumar, Lecture Notes in Computer Science, volume 6516, Stanford, California, USA, December 13–14, 2010, pages 122–131.
- Making Polygons by Simple Folds and One Straight Cut
(joint work with Martin L. Demaine, Andrea Hawksley, Hiro Ito, Po-Ru Loh, Shelly Manber, and Omari Stephens)
in Revised Papers from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), Lecture Notes in Computer Science, Dalian, China, November 3–6, 2010, pages 27–43.
- Making Polygons by Simple Folds and One Straight Cut
(joint work with Martin L. Demaine, Andrea Hawksley, Hiro Ito, Po-Ru Loh, Shelly Manber, and Omari Stephens)
in Abstracts from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), Dalian, China, November 3–6, 2010, to appear.
- Common Unfoldings of Polyominoes and Polycubes
(joint work with Greg Aloupis, Prosenjit K. Bose, Sebastien Collette, Martin L. Demaine, Karim Douieb, Vida Dujmović, John Iacono, Stefan Langerman, and Pat Morin)
in Revised Papers from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), Lecture Notes in Computer Science, volume 7033, Dalian, China, November 3–6, 2010, pages 44–54.
- Common Unfoldings of Polyominoes and Polycubes
(joint work with Greg Aloupis, Prosenjit K. Bose, Sebastien Collette, Martin L. Demaine, Karim Douieb, Vida Dujmović, John Iacono, Stefan Langerman, and Pat Morin)
in Abstracts from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), Dalian, China, November 3–6, 2010, to appear.
- Any Monotone Boolean Function Can Be Realized by Interlocked Polygons
(joint work with Martin L. Demaine and Ryuhei Uehara)
in Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010), Winnipeg, Manitoba, Canada, August 9–11, 2010, pages 139–142.
- Ghost Chimneys
(joint work with David Charlton, Martin L. Demaine, Vida Dujmović, Pat Morin, and Ryuhei Uehara)
in Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010), Winnipeg, Manitoba, Canada, August 9–11, 2010, pages 63–66.
- Zipper Unfoldings of Polyhedral Complexes
(joint work with Martin L. Demaine, Anna Lubiw, Arlo Shallit, and Jonah L. Shallit)
in Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010), Winnipeg, Manitoba, Canada, August 9–11, 2010, pages 219–222.
- 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)
in Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010), Winnipeg, Manitoba, Canada, August 9–11, 2010, pages 99–102.
- Open Problems from CCCG 2009
(joint work with Joseph O'Rourke)
in Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010), Winnipeg, Manitoba, Canada, August 9–11, 2010, pages 83–86.
- Universal Hinge Patterns to Fold Orthogonal Shapes
(joint work with Nadia M. Benbernou, Martin L. Demaine, and Aviv Ovadya)
in Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, to appear.
- Folding Any Orthogonal Maze
(joint work with Martin L. Demaine and Jason Ku)
in Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, to appear.
- Reconstructing David Huffman's Legacy in Curved-Crease Folding
(joint work with Martin L. Demaine and Duks Koschitz)
in Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, to appear.
- Degenerative Coordinates in 22.5° Grid System
(joint work with Tomohiro Tachi)
in Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, to appear.
- On the Complexity of Origami Design
(joint work with Sándor P. Fekete and Robert J. Lang)
in Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), Singapore, July 13–17, 2010, to appear.
- Minimizing the Diameter of a Network using Shortcut Edges
(joint work with Morteza Zadimoghaddam)
in Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Lecture Notes in Computer Science, volume 6139, Bergen, Norway, June 21–23, 2010, pages 420–431.
- Basic Network Creation Games
(joint work with Noga Alon, MohammadTaghi Hajiaghayi, and Tom Leighton)
in Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010), Santorini, Greece, June 13–15, 2010, pages 21–29.
- Scheduling to Minimize Power Consumption using Submodular Functions
(joint work with Morteza Zadimoghaddam)
in Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010), Santorini, Greece, June 13–15, 2010, pages 21–29.
- Kaboozle is NP-complete, even in a Strip
(joint work with Tetsuo Asano, Martin L. Demaine, and Ryuhei Uehara)
in Proceedings of the 5th International Conference on Fun with Algorithms (FUN 2010), Lecture Notes in Computer Science, volume 6099, Ischia, Italy, June 2–4, 2010, pages 28–36.
- UNO is hard, even for a single player
(joint work with Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, and Yushi Uno)
in Proceedings of the 5th International Conference on Fun with Algorithms (FUN 2010), Lecture Notes in Computer Science, volume 6099, Ischia, Italy, June 2–4, 2010, pages 133–144.
- Matching Points with Things
(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)
in Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN 2010), Lecture Notes in Computer Science, volume 6034, Oaxaca, Mexico, April 19–23, 2010, pages 456–467.
- Reconfigurable Asynchronous Logic Automata
(joint work with Neil Gershenfeld, David Dalrymple, Kailiang Chen, Ara Knaian, Forrest Green, Scott Greenwald, and Peter Schmidt-Nielsen)
in Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2010), Madrid, Spain, January 17–23, 2010, pages 1–6.
- Shape Replication Through Self-Assembly and RNase Enzymes
(joint work with Zachary Abel, Nadia Benbernou, Mirela Damian, Martin L. Demaine, Robin Flatland, Scott Kominers, and Robert Schweller)
in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, Texas, January 17–19, 2010, pages 1045–1064.
- Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff
(joint work with Gerth Stølting Brodal, Jeremy T. Fineman, John Iacono, Stefan Langerman, and J. Ian Munro)
in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, Texas, January 17–19, 2010, pages 1448–1456.
- Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs
(joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, Texas, January 17–19, 2010, pages 329–344.
- Folding a Better Checkerboard
(joint work with Martin L. Demaine, Goran Konjevod, and Robert J. Lang)
in Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009), Lecture Notes in Computer Science, volume 5878, Hawaii, USA, December 16–18, 2009, pages 1074–1083.
- Algorithmic Folding Complexity
(joint work with Jean Cardinal, Martin L. Demaine, Shinji Imahori, Stefan Langerman, and Ryuhei Uehara)
in Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009), Lecture Notes in Computer Science, volume 5878, Hawaii, USA, December 16–18, 2009, pages 452–461.
- 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)
in Proceedings of the 5th Workshop on Internet & Network Economics (WINE 2009), Lecture Notes in Computer Science, volume 5929, Rome, Italy, December 14–18, 2009, pages 125–136.
- (Non)existence of Pleated Folds: How Paper Folds Between Creases
(joint work with Martin L. Demaine, Vi Hart, Gregory N. Price, and Tomohiro Tachi)
in Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009), Kanazawa, Ishikawa, Japan, November 11–13, 2009, to appear.
- Continuous Blooming of Convex Polyhedra
(joint work with Martin L. Demaine, Vi Hart, John Iacono, Stefan Langerman, and Joseph O'Rourke)
in Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009), Kanazawa, Ishikawa, Japan, November 11–13, 2009, pages 123–124.
- Matching Points with Things
(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)
in Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009), Kanazawa, Ishikawa, Japan, November 11–13, 2009, to appear.
- Algorithmic Folding Complexity
(joint work with Jean Cardinal, Martin L. Demaine, Shinji Imahori, Stefan Langerman, and Ryuhei Uehara)
in Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009), Kanazawa, Ishikawa, Japan, November 11–13, 2009, to appear.
- A Distributed Boundary Detection Algorithm for Multi-Robot Systems
(joint work with James McLurkin)
in Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009), St. Louis, Missouri, October 11–15, 2009, pages 4791–4798.
- Efficient Reconfiguration of Lattice-Based Modular Robots
(joint work with Greg Aloupis, Nadia Benbernou, Mirela Damian, Robin Flatland, John Iacono, and Stefanie Wuhrer)
in Proceedings of the 4th European Conference on Mobile Robots (ECMR 2009), Mlini/Dubrovnik, Croatia, September 23–25, 2009, pages 81–86.
- Minimizing Movement: Fixed-Parameter Tractability
(joint work with MohammadTaghi Hajiaghayi and Dániel Marx)
in Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009), Lecture Notes in Computer Science, volume 5757, Copenhagen, Denmark, September 7–9, 2009, pages 718–729.
- Algorithms Meet Art, Puzzles, and Magic
in Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009), Lecture Notes in Computer Science, volume 5664, Banff, Alberta, Canada, August 21–23, 2009, pages 193.
- Minimal Locked Trees
(joint work with Brad Ballinger, David Charlton, Martin L. Demaine, John Iacono, Ching-Hao Liu, and Sheung-Hung Poon)
in Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009), Lecture Notes in Computer Science, volume 5664, Banff, Alberta, Canada, August 21–23, 2009, pages 61–73.
- A pseudopolynomial algorithm for Alexandrov's Theorem
(joint work with Daniel Kane and Gregory N. Price)
in Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009), Lecture Notes in Computer Science, volume 5664, Banff, Alberta, Canada, August 21–23, 2009, pages 435–446.
- Reconfiguration of List Edge-Colorings in a Graph
(joint work with Takehiro Ito and Marcin Kamiński)
in Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009), Lecture Notes in Computer Science, volume 5664, Banff, Alberta, Canada, August 21–23, 2009, pages 375–386.
- Integer Point Sets Minimizing Average Pairwise ℓ_{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)
in Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009), Vancouver, British Columbia, Canada, August 17–19, 2009, pages 145–148.
- Open Problems from CCCG 2008
(joint work with Joseph O'Rourke)
in Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009), Vancouver, British Columbia, Canada, August 17–19, 2009, pages 75–78.
- Relaxed Gabriel Graphs
(joint work with Prosenjit Bose, Jean Cardinal, Sébastien Collette, Belén Palop, Perouz Taslakian, and Norbert Zeh)
in Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009), Vancouver, British Columbia, Canada, August 17–19, 2009, pages 169–172.
- Mathematics Is Art
(joint work with Martin L. Demaine)
in Proceedings of 12th Annual Conference of BRIDGES: Mathematics, Music, Art, Architecture, Culture (BRIDGES 2009), Banff, Alberta, Canada, July 26–29, 2009, pages 1–10.
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
(joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 316–327.
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
(joint work with MohammadTaghi Hajiaghayi and Philip Klein)
in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 328–340.
- On Cartesian Trees and Range Minimum Queries
(joint work with Gad Landau and Oren Weimann)
in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 341–353.
- Locked Thick Chains
(joint work with Martin L. Demaine, Stefan Langerman, and Jérôme Vervier)
in Abstracts from the 25th European Workshop on Computational Geometry (EuroCG 2009), Brussels, Belgium, March 16–18, 2009, pages 65–68.
- Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
(joint work with Glencora Borradaile and Siamak Tazari)
in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), Freiburg, Germany, February 26–28, 2009, pages 171–182.
- The Price of Anarchy in Cooperative Network Creation Games
(joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam)
in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), Freiburg, Germany, February 26–28, 2009, pages 301–312.
- The Geometry of Binary Search Trees
(joint work with Dion Harmon, John Iacono, Daniel Kane, and Mihai Pǎtraşcu)
in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, New York, January 4–6, 2009, pages 496–505.
- Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs
(joint work with Ken-ichi Kawarabayashi and MohammadTaghi Hajiaghayi)
in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, New York, January 4–6, 2009, pages 1166–1175.
- Realistic Reconfiguration of Crystalline (and Telecube) Robots
(joint work with Greg Aloupis, Sébastien Collette, Mirela Damian, Dania El-Khechen, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer)
in Proceedings of the 8th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2008), Springer Tracts in Advanced Robotics, volume 57, Guanajuato, México, December 7–9, 2008, pages 433–447.
- 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)
in Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008), Gold Coast, Australia, December 15–17, 2008, pages 28–39.
- Reconfiguration of Cube-Style Modular Robots Using O(log n) Parallel Moves
(joint work with Greg Aloupis, Sébastien Collette, Stefan Langerman, Vera Sacristán, and Stefanie Wuhrer)
in Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008), Gold Coast, Australia, December 15–17, 2008, pages 342–353.
- Curved Crease Origami
(joint work with Duks Koschitz and Martin L. Demaine)
in Abstracts from Advances in Architectural Geometry (AAG 2008), Vienna, Austria, September 13–16, 2008, pages 29–32.
- Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
(joint work with Mihai Bădoiu, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, and Morteza Zadimoghaddam)
in Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008), Boston, Massachusetts, August 25–27, 2008, pages 21–34.
- Computational Balloon Twisting: The Theory of Balloon Polyhedra
(joint work with Martin L. Demaine and Vi Hart)
in Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008), Montréal, Québec, Canada, August 13–15, 2008.
- Open Problems from CCCG 2007
(joint work with Joseph O'Rourke)
in Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008), Montréal, Québec, Canada, August 13–15, 2008, pages 183–190.
- Confluently Persistent Tries for Efficient Version Control
(joint work with Stefan Langerman and Eric Price)
in Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008), Lecture Notes in Computer Science, volume 5124, Gothenburg, Sweden, July 2–4, 2008, pages 160–172.
- Constraint Logic: A Uniform Framework for Modeling Computation as Games
(joint work with Robert A. Hearn)
in Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008), College Park, Maryland, June 23–26, 2008, pages 149–162.
- Hinged Dissections Exist
(joint work with Timothy G. Abbott, Zachary Abel, David Charlton, Martin L. Demaine, and Scott D. Kominers)
in Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), College Park, Maryland, June 9–11, 2008, pages 110–119.
- Moving-Baseline Localization
(joint work with Jun-geun Park and Seth J. Teller)
in Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN 2008), St. Louis, Missouri, April 22–24, 2008, pages 15–26.
- 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)
in Proceedings of the 18th Annual International Symposium on Algorithms and Computation (ISAAC 2007), December 17–19, 2007, pages 208–219.
- Vertex Pops and Popturns
(joint work with Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Martin L. Demaine, Robin Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian, and Godfried Toussaint)
in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 137–140.
- On Rolling Cube Puzzles
(joint work with Kevin Buchin, Maike Buchin, Martin L. Demaine, Dania El-Khechen, Sándor Fekete, Christian Knauer, André Schulz, and Perouz Taslakian)
in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007.
- Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs
(joint work with Nadia M. Benbernou, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth)
in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 13–16.
- Open Problems from CCCG 2006
(joint work with Joseph O'Rourke)
in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 277–280.
- The Stackelberg Minimum Spanning Tree Game
(joint work with Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, and Oren Weimann)
in Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), Lecture Notes in Computer Science, volume 4619, Halifax, Nova Scotia, Canada, August 15–17, 2007, pages 64–76.
- A Pseudopolynomial Time O(log n)-Approximation Algorithm for Art Gallery Problems
(joint work with Ajay Deshpande, Taejung Kim, and Sanjay E. Sarma)
in Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), Lecture Notes in Computer Science, volume 4619, Halifax, Nova Scotia, Canada, August 15–17, 2007, pages 163–174.
- The Price of Anarchy in Network Creation Games
(joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam)
in Proceedings of the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2007), Portland, Oregon, August 12–15, 2007, pages 292–298.
- Revising Quorum Systems for Energy Conservation in Sensor Networks
(joint work with Daniela Tulone)
in Proceedings of the International Conference on Wireless Algorithms, Systems and Applications (WASA 2007), Chicago, Illinois, August 1–3, 2007, pages 147–157.
- An Optimal Decomposition Algorithm for Tree Edit Distance
(joint work with Shay Mozes, Benjamin Rossman, and Oren Weimann)
in Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, July 9–13, 2007, pages 146–157.
- 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)
in Abstracts from the 12th Encuentros de Geometría Computacional (EGC 2007), June 25–27, 2007, pages 19–34.
- Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity
(joint work with Martin L. Demaine)
in Abstracts from the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007), Kyoto, Japan, June 11–15, 2007.
- Deflating The Pentagon
(joint work with Martin L. Demaine, Thomas Fevens, Antonio Mesa, Michael Soss, Diane L. Souvaine, Perouz Taslakian, and Godfried Toussaint)
in Revised Papers from the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007), Lecture Notes in Computer Science, volume 4535, Kyoto, Japan, June 11–15, 2007, pages 56–67.
- Scheduling to Minimize Gaps and Power Consumption
(joint work with Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S. Sayedi-Roshkhar, and Morteza Zadimoghaddam)
in Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007), San Diego, California, June 9–11, 2007, pages 46–54.
- Tight Bounds for Dynamic Convex Hull Queries (Again)
(joint work with Mihai Pǎtraşcu)
in Proceedings of the 23rd Annual ACM Symposium on Computational Geometry (SoCG 2007), Gyeongju, South Korea, June 6–8, 2007, pages 354–363.
- 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)
in Proceedings of the 13th International Meeting on DNA Computing (DNA 2007), Lecture Notes in Computer Science, volume 4848, Memphis, Tennessee, June 4–8, 2007, pages 1–14.
- Wrapping the Mozartkugel
(joint work with Martin L. Demaine, John Iacono, and Stefan Langerman)
in Abstracts from the 24th European Workshop on Computational Geometry (EuroCG 2007), Graz, Austria, March 19–21, 2007, pages 14–17.
- Deflating The Pentagon
(joint work with Martin L. Demaine, Diane L. Souvaine, and Perouz Taslakian)
in Abstracts from the 24th European Workshop on Computational Geometry (EuroCG 2007), Graz, Austria, March 19–21, 2007, pages 10–13.
- Computational Geometry through the Information Lens
in Abstracts from the 24th European Workshop on Computational Geometry (EuroCG 2007), Graz, Austria, March 19–21, 2007, pages 81.
- Approximation Algorithms via Contraction Decomposition
(joint work with MohammadTaghi Hajiaghayi and Bojan Mohar)
in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, January 7–9, 2007, pages 278–287.
- Minimizing Movement
(joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam)
in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, January 7–9, 2007, pages 258–267.
- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction
(joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
in Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), Lecture Notes in Computer Science, volume 4288, Calcutta, India, December 18–20, 2006, pages 3–15.
- Approximability for Partitioning Graphs with Supply and Demand
(joint work with Takehiro Ito, Xiao Zhou, and Takao Nishizeki)
in Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), Lecture Notes in Computer Science, volume 4288, Calcutta, India, December 18–20, 2006, pages 121–130.
- Origami, Linkages, and Polyhedra: Folding with Algorithms
in Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), Zürich, Switzerland, September 11–13, 2006, pages 1.
- Necklaces, Convolutions, and X + Y
(joint work with David Bremner, Timothy M. Chan, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian)
in Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), Zürich, Switzerland, September 11–13, 2006, pages 160–171.
- Curves in the Sand: Algorithmic Drawing
(joint work with Mirela Damian, Martin L. Demaine, Vida Dujmović, Dania El-Khechen, Robin Flatland, John Iacono, Stefan Langerman, Henk Meijer, Suneeta Ramaswami, Diane L. Souvaine, Perouz Taslakian, and Godfried T. Toussaint)
in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 11–14.
- Polygons Flip Finitely: Flaws and a Fix
(joint work with Blaise Gassend, Joseph O'Rourke, and Godfried T. Toussaint)
in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 109–112.
- Open Problems from CCCG 2005
(joint work with Joseph O'Rourke)
in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 75–80.
- Linkage Folding: From Erdős to Proteins
in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 1.
- Sand Drawings and Gaussian Graphs
(joint work with Martin L. Demaine, Perouz Taslakian, and Godfried T. Toussaint)
in Proceedings of the 9th Annual Conference of BRIDGES: Mathematical Connections in Art, Music, and Science (BRIDGES 2006), London, England, August 4–8, 2006, pages 79–88.
- 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)
in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006), Sedona, Arizona, June 5–7, 2006, pages 61–70.
- Plane Embeddings of Planar Graph Metrics
(joint work with MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Mohammad Moharrami)
in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006), Sedona, Arizona, June 5–7, 2006, pages 197–206.
- Refolding Planar Polygons
(joint work with Hayley N. Iben and James F. O'Brien)
in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006), Sedona, Arizona, June 5–7, 2006, pages 71–79.
- Voronoi game on graphs and its complexity
(joint work with Sachio Teramoto and Ryuhei Uehara)
in Proceedings of the 2nd IEEE Symposium on Computational Intelligence and Games (CIG 2006), Reno, Nevada, May 22–24, 2006, pages 265–271.
- De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space)
(joint work with Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai Pǎtraşcu)
in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20–24, 2006, pages 349–361.
- 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)
in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20–24, 2006, pages 80–92.
- Optimally Adaptive Integration of Univariate Lipschitz Functions
(joint work with Ilya Baran and Dmitriy A. Katz)
in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20–24, 2006, pages 142–153.
- Combination Can Be Hard: Approximability of the Unique Coverage Problem
(joint work with Uriel Feige, MohammadTaghi Hajiaghayi, and Mohammad R. Salavatipour)
in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, Florida, January 22–24, 2006, pages 162–171.
- Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding
(joint work with Micah Adler, Nicholas J. A. Harvey, and Mihai Pǎtraşcu)
in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, Florida, January 22–24, 2006, pages 251–260.
- 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)
in Abstracts from the 15th Annual Fall Workshop on Computational Geometry, Philadelphia, Pennsylvania, November 18–19, 2005, pages 51–52.
- Kinematics and Dynamics of Nanostructured Origami
(joint work with Paul Stellman, Will Arora, Satoshi Takahashi, and George Barbastathis)
in Proceedings of the ASME International Mechanical Engineering Congress and Exposition, Orlando, Florida, November 5–11, 2005, pages 541–548.
- Design and Control of Nanostructured Origami
(joint work with Paul Stellman, Will Arora, Satoshi Takahashi, and George Barbastathis)
in Proceedings of the 3rd International Symposium on Nanomanufacturing, Orlando, Florida, November 3–5, 2005, pages 4.
- PersiFS: A Versioned File System with an Efficient Representation
(joint work with Dan R. K. Ports and Austin T. Clements)
in Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP 2005), Brighton, United Kingdom, October 23–26, 2005.
- Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring
(joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Pittsburgh, PA, October 23–25, 2005, pages 637–646.
- Optimizing a 2D Function Satisfying Unimodality Properties
(joint work with Stefan Langerman)
in Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), Lecture Notes in Computer Science, volume 3669, Mallorca, Spain, October 3–6, 2005, pages 887–898.
- Realizing Partitions Respecting Full and Partial Order Information
(joint work with Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides)
in Proceedings of the 16th Australasian Workshop on Combinatorial Algorithms (AWOCA 2005), Victoria, Australia, September 18–21, 2005, pages 105–114.
- 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)
in Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 169–181.
- Subquadratic Algorithms for 3SUM
(joint work with Ilya Baran and Mihai Pǎtraşcu)
in Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 409–421.
- Hinged Dissection of Polypolyhedra
(joint work with Martin L. Demaine, Jeffrey F. Lindy, and Diane L. Souvaine)
in Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 205–217.
- Open Problems from CCCG 2004
(joint work with Joseph O'Rourke)
in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), Windsor, Ontario, Canada, August 10–12, 2005, pages 303–306.
- Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane
(joint work with Timothy Abbott, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung)
in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), Windsor, Ontario, Canada, August 10–12, 2005, pages 61–64.
- The Distance Geometry of Deep Rhythms and Scales
(joint work with Francisco Gomez-Martin, Henk Meijer, David Rappaport, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, and David R. Wood)
in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), Windsor, Ontario, Canada, August 10–12, 2005, pages 163–166.
- Deploying Sensor Networks with Guaranteed Capacity and Fault Tolerance
(joint work with Jonathan L. Bredin, MohammadTaghi Hajiaghayi, and Daniela Rus)
in Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC 2005), Urbana-Champaign, Illinois, May 25–28, 2005, pages 309–319.
- Mobile-Assisted Localization in Wireless Sensor Networks
(joint work with Nissanka B. Priyantha, Hari Balakrishnan, and Seth Teller)
in Proceedings of the 24th Annual Joint Conference of the IEEE Communications Society on Computer Communications (INFOCOM 2005), volume 1, Miami, Florida, March 13–17, 2005, pages 172–183.
- Bidimensionality: New Connections between FPT Algorithms and PTASs
(joint work with MohammadTaghi Hajiaghayi)
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23–25, 2005, pages 590–601.
- Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality
(joint work with MohammadTaghi Hajiaghayi)
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23–25, 2005, pages 682–689.
- 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)
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23–25, 2005, pages 650–659.
- Puzzles, Art, and Magic with Algorithms
(joint work with Martin L. Demaine)
in Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), Lecture Notes in Computer Science, volume 3341, Hong Kong, China, 2004, pages 1.
- Hinged Dissection of Polypolyhedra
(joint work with Martin L. Demaine, Jeffrey F. Lindy, and Diane L. Souvaine)
in Abstracts from the 14th Annual Fall Workshop on Computational Geometry, Cambridge, Massachusetts, November 19–20, 2004, pages 16–17.
- Folding Paper Shopping Bags
(joint work with Devin J. Balkcom and Martin L. Demaine)
in Abstracts from the 14th Annual Fall Workshop on Computational Geometry, Cambridge, Massachusetts, November 19–20, 2004, pages 14–15.
- EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management
(joint work with Ben Leong and Barbara Liskov)
in Proceedings of the IEEE International Conference on Networks (ICON 2004), volume 1, Singapore, November 16–19, 2004, pages 270–276.
- Dynamic Optimality—Almost
(joint work with Dion Harmon, John Iacono, and Mihai Pǎtraşcu)
in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), Rome, Italy, October 17–19, 2004, pages 484–490.
- Grid Vertex-Unfolding Orthostacks
(joint work with John Iacono and Stefan Langerman)
in Revised Selected Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2004), Lecture Notes in Computer Science, volume 3742, Tokyo, Japan, October 8–11, 2004, pages 76–82.
- Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth
(joint work with MohammadTaghi Hajiaghayi)
in Proceedings of the 12th International Symposium on Graph Drawing (GD 2004), Lecture Notes in Computer Science, volume 3383, Harlem, New York, September 29–October 2, 2004, pages 517–533.
- The Bidimensional Theory of Bounded-Genus Graphs
(joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
in Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Prague, Czech Republic, August 22–27, 2004, pages 191–203.
- Continuous Foldability of Polygonal Paper
(joint work with Satyan L. Devadoss, Joseph S. B. Mitchell, and Joseph O'Rourke)
in Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004), Montréal, Québec, Canada, August 9–11, 2004, pages 64–67.
- Unfolding Polyhedral Bands
(joint work with Greg Aloupis, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, and Godfried Toussaint)
in Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004), Montréal, Québec, Canada, August 9–11, 2004, pages 60–63.
- Open Problems from CCCG 2003
(joint work with Joseph O'Rourke)
in Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004), Montréal, Québec, Canada, August 9–11, 2004, pages 209–211.
- Refolding Planar Polygons
(joint work with Hayley N. Iben and James F. O'Brien)
in Technical Sketchs of the 31st International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH 2004), Los Angeles, California, August 8–12, 2004.
- Lower Bounds for Dynamic Connectivity
(joint work with Mihai Pǎtraşcu)
in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), Chicago, Illinois, June 13–15, 2004, pages 546–553.
- An Energy-Driven Approach to Linkage Unfolding
(joint work with Jason Cantarella, Hayley Iben, and James O'Brien)
in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 134–143.
- Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve
(joint work with Ilya Baran)
in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 220–229.
- Low-Dimensional Embedding with Extra Information
(joint work with Mihai Bădoiu, MohammadTaghi Hajiaghayi, and Piotr Indyk)
in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 320–329.
- Geodesic Ham-Sandwich Cuts
(joint work with Prosenjit Bose, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin)
in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 1–9.
- Separating point sets in polygonal environments
(joint work with Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, and Sue Whitesides)
in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 10–16.
- Morpion Solitaire
(joint work with Martin L. Demaine, Arthur Langerman, and Stefan Langerman)
in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 53–64.
- Finding a Divisible Pair and a Good Wooden Fence
(joint work with Stelian Ciurea, Corina E. Pǎtraşcu, and Mihai Pǎtraşcu)
in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 206–219.
- PushPush-k is PSPACE-Complete
(joint work with Michael Hoffmann and Markus Holzer)
in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 159–170.
- Puzzles, Art, and Magic with Algorithms
(joint work with Martin L. Demaine)
in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 7–15.
- A Simplified and Dynamic Unified Structure
(joint work with Mihai Bădoiu)
in Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004), Lecture Notes in Computer Science, volume 2976, Buenos Aires, Argentina, April 5–8, 2004, pages 466–473.
- Bidimensional Parameters and Local Treewidth
(joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
in Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004), Lecture Notes in Computer Science, volume 2976, Buenos Aires, Argentina, April 5–8, 2004, pages 109–118.
- Optimizing a 2D Function Satisfying Unimodality Properties
(joint work with Stefan Langerman)
in Abstracts from the 20th European Workshop on Computational Geometry (EuroCG 2004), Seville, Spain, March 24–26, 2004, pages 107–110.
- Retroactive Data Structures
(joint work with John Iacono and Stefan Langerman)
in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 274–283.
- Tight Bounds for the Partial-Sums Problem
(joint work with Mihai Pǎtraşcu)
in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 20–29.
- Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications
(joint work with MohammadTaghi Hajiaghayi)
in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 833–842.
- 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)
in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 823–832.
- Interpolation Search for Non-Independent Data
(joint work with Thouis Jones and Mihai Pǎtraşcu)
in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 522–523.
- Geometric Restrictions on Producible Polygonal Protein Chains
(joint work with Stefan Langerman and Joseph O'Rourke)
in Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), Lecture Notes in Computer Science, volume 2906, Kyoto, Japan, December 15–17, 2003, pages 395–404.
- Anchor-Free Distributed Localization in Sensor Networks
(joint work with Nissanka B. Priyantha, Hari Balakrishnan, and Seth Teller)
in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys 2003), Los Angeles, California, USA, November 5–7, 2003, pages 340–341.
- Identifying Frequent Items in Sliding Windows over On-Line Packet Streams
(joint work with Lukasz Golab, David DeHaan, Alejandro López-Ortiz, and J. Ian Munro)
in Proceedings of the ACM SIGCOMM Internet Measurement Conference (IMC 2003), Miami, Florida, October 27–29, 2003, pages 173–178.
- Planar Embeddings of Graphs with Specified Edge Lengths
(joint work with Sergio Cabello and Günter Rote)
in Proceedings of the 11th Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science, volume 2912, Perugia, Italy, September 21–24, 2003, pages 283–294.
- Optimal Dynamic Video-On-Demand using Adaptive Broadcasting
(joint work with Therese Biedl, Alexander Golynski, Joseph D. Horton, Alejandro López-Ortiz, Guillaume Poirier, and Claude-Guy Quimper)
in Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003), Lecture Notes in Computer Science, volume 2832, Budapest, Hungary, September 15–20, 2003, pages 90–101.
- Correlation Clustering with Partial Information
(joint work with Nicole Immorlica)
in Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM-APPROX 2003), Princeton, New Jersey, August 24–26, 2003, pages 1–13.
- Hinged Dissection of Polygons is Hard
(joint work with Robert A. Hearn and Greg N. Frederickson)
in Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003), Halifax, Nova Scotia, Canada, August 11–13, 2003, pages 98–102.
- On the Complexity of Halfspace Volume Queries
(joint work with Jeff Erickson and Stefan Langerman)
in Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003), Halifax, Nova Scotia, Canada, August 11–13, 2003, pages 159–160.
- Open Problems from CCCG 2002
(joint work with Joseph O'Rourke)
in Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003), Halifax, Nova Scotia, Canada, August 11–13, 2003, pages 178–181.
- 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)
in Proceedings of the 8th Workshop on Algorithms and Data Structures (WADS 2003), Lecture Notes in Computer Science, volume 2748, Ottawa, Ontario, Canada, July 30–August 1, 2003, pages 451–461.
- Tetris is Hard, Even to Approximate
(joint work with Susan Hohenberger and David Liben-Nowell)
in Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003), Big Sky, Montana, July 25–28, 2003, pages 351–363.
- 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ř)
in Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003), Big Sky, Montana, July 25–28, 2003, pages 182–191.
- Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs
(joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
in Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Eindhoven, The Netherlands, June 30–July 4, 2003, pages 829–844.
- Geometric Games on Triangulations
(joint work with Oswin Aichholzer, David Bremner, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia)
in Abstracts from the 19th European Workshop of Computational Geometry (EuroCG 2003), Bonn, Germany, March 24–26, 2003, pages 89–92.
- Quartering a Square Optimally
(joint work with Prosenjit Bose, John Iacono, and Stefan Langerman)
in Abstracts from the Japan Conference on Discrete and Computational Geometry (JCDCG 2002), Tokyo, Japan, December 6–9, 2002, pages 5–6.
- Playing with Triangulations
(joint work with Oswin Aichholzer, David Bremner, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia)
in Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2002), Lecture Notes in Computer Science, volume 2866, Tokyo, Japan, December 6–9, 2002, pages 22–37.
- Flat-State Connectivity of Linkages under Dihedral Motions
(joint work with Greg Aloupis, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark Overmars, Michael Soss, Ileana Streinu, and Godfried Toussaint)
in Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science, volume 2518, Vancouver, British Columbia, Canada, November 20–23, 2002, pages 369–380.
- Exponential Speedup of Fixed-Parameter Algorithms on K_{3,3}-minor-free or K_{5}-minor-free Graphs
(joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
in Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science, volume 2518, Vancouver, British Columbia, Canada, November 20–23, 2002, pages 262–273.
- An Energy-Driven Approach to Linkage Unfolding
(joint work with Jason Cantarella, Hayley Iben, and James O'Brien)
in Abstracts from the 12th Annual Fall Workshop on Computational Geometry, Piscataway, New Jersey, November 14–15, 2002.
- Tetris is Hard, Even to Approximate
(joint work with Susan Hohenberger and David Liben-Nowell)
in Abstracts from the 12th Annual Fall Workshop on Computational Geometry, Piscataway, New Jersey, November 14–15, 2002.
- Frequency Estimation of Internet Packet Streams with Limited Space
(joint work with Alejandro López-Ortiz and J. Ian Munro)
in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 348–360.
- Two Simplified Algorithms for Maintaining Order in a List
(joint work with Michael A. Bender, Richard Cole, Martin Farach-Colton, and Jack Zito)
in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 152–164.
- Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy
(joint work with Michael A. Bender, Richard Cole, and Martin Farach-Colton)
in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 139–151.
- Efficient Tree Layout in a Multilevel Memory Hierarchy
(joint work with Michael A. Bender and Martin Farach-Colton)
in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 165–173.
- 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
(joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
in Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2002), Lecture Notes in Computer Science, volume 2462, Rome, Italy, September 17–21, 2002, pages 67–80.
- 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)
in Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI 2002), Rome, Italy, September 17–21, 2002, pages 506–520.
- Open Problems from CCCG 2001
(joint work with Joseph O'Rourke)
in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002.
- Tighter Bounds on the Genus of Nonorthogonal Polyhedra Built from Rectangles
(joint work with Therese Biedl, Timothy M. Chan, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, and Ming-wei Wang)
in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 105–108.
- Push-2-F is PSPACE-Complete
(joint work with Robert A. Hearn and Michael Hoffmann)
in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 31–35.
- Computing Signed Permutations of Polygons
(joint work with Greg Aloupis, Prosenjit Bose, Stefan Langerman, Henk Meijer, Mark Overmars, and Godfried T. Toussaint)
in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002.
- Proximate Point Searching
(joint work with John Iacono and Stefan Langerman)
in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 1–4.
- Flat-State Connectivity of Chains with Fixed Acute Angles
(joint work with Greg Aloupis, Henk Meijer, Joseph O'Rourke, Ileana Streinu, and Godfried Toussaint)
in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 27–30.
- Solitaire Clobber
(joint work with Martin L. Demaine and Rudolf Fleischer)
in Proceedings of the 3rd International Conference on Computers and Games (CG 2002), Lecture Notes in Computer Science, volume 2883, Edmonton, Alberta, Canada, July 25–27, 2002, pages 188–200.
- The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications
(joint work with Robert A. Hearn)
in Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), Lecture Notes in Computer Science, volume 2380, Malaga, Spain, July 8–13, 2002, pages 401–413.
- Robot Localization without Depth Perception
(joint work with Alejandro López-Ortiz and J. Ian Munro)
in Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002), Lecture Notes in Computer Science, volume 2368, Turku, Finland, July 3–5, 2002, pages 249–259.
- Interlocked Open Linkages with Few Joints
(joint work with Stefan Langerman, Joseph O'Rourke, and Jack Snoeyink)
in Proceedings of the 18th Annual ACM Symposium on Computational Geometry (SoCG 2002), Barcelona, Spain, June 5–7, 2002, pages 189–198.
- Vertex-Unfolding of Simplicial Manifolds
(joint work with David Eppstein, Jeff Erickson, George W. Hart, and Joseph O'Rourke)
in Proceedings of the 18th Annual ACM Symposium on Computational Geometry (SoCG 2002), Barcelona, Spain, June 5–7, 2002, pages 237–243.
- Cache-Oblivious Priority Queue and Graph Algorithm Applications
(joint work with Lars Arge, Michael A. Bender, Bryan Holland-Minkley, and J. Ian Munro)
in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002), Montréal, Québec, Canada, May 19–21, 2002, pages 268–276.
- Tight Bounds on Maximal and Maximum Matchings
(joint work with Therese Biedl, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov)
in Proceedings of the 12th Annual International Symposium on Algorithms and Computation (ISAAC 2001), Lecture Notes in Computer Science, volume 2223, Christchurch, New Zealand, December 19–21, 2001, pages 308–319.
- Infinitesimally Locked Linkages with Applications to Locked Trees
(joint work with Robert Connelly and Günter Rote)
in Abstracts from the 11th Annual Fall Workshop on Computational Geometry, New York, New York, November 2–3, 2001.
- Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
in Proceedings of the 26th Symposium on Mathematical Foundations in Computer Science (MFCS 2001), Lecture Notes in Computer Science, volume 2136, Marianske Lazne, Czech Republic, August 27–31, 2001, pages 18–32.
- Open Problems from CCCG 2000
(joint work with Joseph O'Rourke)
in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), Waterloo, Ontario, Canada, August 13–15, 2001, pages 185–187.
- Pushing Blocks is NP-Complete for Noncrossing Solution Paths
(joint work with Michael Hoffmann)
in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), Waterloo, Ontario, Canada, August 13–15, 2001, pages 65–68.
- Reaching Folded States of a Rectangular Piece of Paper
(joint work with Joseph S. B. Mitchell)
in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), Waterloo, Ontario, Canada, August 13–15, 2001, pages 73–75.
- Short Interlocked Linkages
(joint work with Stefan Langerman and Joseph O'Rourke)
in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), Waterloo, Ontario, Canada, August 13–15, 2001, pages 69–72.
- The CCCG 2001 Logo
(joint work with Martin L. Demaine and Anna Lubiw)
in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), Waterloo, Ontario, Canada, August 13–15, 2001, iv–v.
- 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)
in Proceedings of the 7th Workshop on Algorithms and Data Structures (WADS 2001), Lecture Notes in Computer Science, volume 2125, Providence, Rhode Island, August 8–10, 2001, pages 401–413.
- Fun-Sort
(joint work with Therese Biedl, Timothy Chan, Rudolf Fleischer, Mordecai Golin, and J. Ian Munro)
in Proceedings of the 2nd International Conference on Fun with Algorithms (FUN 2001), Isola d'Elba, Italy, May 29–31, 2001, pages 15–26.
- 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)
in Abstracts from the 17th European Workshop on Computational Geometry (EuroCG 2001), Berlin, Germany, March 26–28, 2001.
- Recent Results in Computational Origami
(joint work with Martin L. Demaine)
in Origami^{3}: Proceedings of the 3rd International Meeting of Origami Science, Math, and Education (OSME 2001), Monterey, California, March 9–11, 2001, pages 3–16, A K Peters.
- A Disk-Packing Algorithm for an Origami Magic Trick
(joint work with Marshall Bern, David Eppstein, and Barry Hayes)
in Origami^{3}: Proceedings of the 3rd International Meeting of Origami Science, Math, and Education (OSME 2001), Monterey, California, March 9–11, 2001, pages 17–28, A K Peters.
- 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)
in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, January 7–9, 2001, pages 138–147.
- A Linear Lower Bound on Index Size for Text Retrieval
(joint work with Alejandro López-Ortiz)
in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, January 7–9, 2001, pages 289–294.
- On Universally Easy Classes for NP-complete Problems
(joint work with Alejandro López-Ortiz and J. Ian Munro)
in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, January 7–9, 2001, pages 910–911.
- Experiments on Adaptive Set Intersections for Text Retrieval Systems
(joint work with Alejandro López-Ortiz and J. Ian Munro)
in Proceedings of the 3rd Workshop on Algorithm Engineering and Experiments (ALENEX 2001), Lecture Notes in Computer Science, volume 2153, Washington, DC, January 5–6, 2001, pages 91–104.
- 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)
in Proceedings of the 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000), Lecture Notes in Computer Science, volume 1969, Taipei, Taiwan, December 18–20, 2000, pages 47–59.
- Enumerating Foldings and Unfoldings between Polygons and Polytopes
(joint work with Martin L. Demaine, Anna Lubiw, and Joseph O'Rourke)
in Abstracts from the Japan Conference on Discrete and Computational Geometry (JCDCG 2000), Tokyo, Japan, November 22–25, 2000, pages 9–12.
- Folding and Unfolding Linkages, Paper, and Polyhedra
in Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2000), Lecture Notes in Computer Science, volume 2098, Tokyo, Japan, November 22–25, 2000, pages 113–124.
- 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)
in Abstracts of the Japan Conference on Discrete and Computational Geometry (JCDCG 2000), Tokyo, Japan, November 22–25, 2000, pages 107–108.
- Cache-Oblivious B-Trees
(joint work with Michael A. Bender and Martin Farach-Colton)
in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, November 12–14, 2000, pages 399–409.
- Straightening Polygonal Arcs and Convexifying Polygonal Cycles
(joint work with Robert Connelly and Günter Rote)
in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, November 12–14, 2000, pages 432–442.
- 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)
in Abstracts from the 10th Annual Fall Workshop on Computational Geometry, Stony Brook, New York, October 27–28, 2000.
- Balanced k-Colorings
(joint work with Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Martin L. Demaine, Rudolf Fleischer, and Ming-Wei Wang)
in Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS 2000), Lecture Notes in Computer Science, volume 1893, Bratislava, Slovak Republic, August 28–September 1, 2000, pages 202–211.
- Polygons Cuttable by a Circular Saw
(joint work with Martin L. Demaine and Craig S. Kaplan)
in Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000), Fredericton, New Brunswick, Canada, August 16–18, 2000, pages 1–6.
- PushPush and Push-1 are NP-hard in 2D
(joint work with Martin L. Demaine and Joseph O'Rourke)
in Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000), Fredericton, New Brunswick, Canada, August 16–18, 2000, pages 211–219.
- Reconfiguring Convex Polygons
(joint work with Oswin Aichholzer, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, and Godfried T. Toussaint)
in Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000), Fredericton, New Brunswick, Canada, August 16–18, 2000, pages 17–20.
- Every Polygon Can Be Untangled
(joint work with Robert Connelly and Günter Rote)
in Abstracts from the 16th European Workshop on Computational Geometry (EuroCG 2000), Eilat, Israel, March 13–15, 2000, pages 62–65.
- Adaptive Set Intersections, Unions, and Differences
(joint work with Alejandro López-Ortiz and J. Ian Munro)
in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), San Francisco, California, January 9–11, 2000, pages 743–752.
- Convexifying Monotone Polygons
(joint work with Therese C. Biedl, Sylvain Lazard, Steven M. Robbins, and Michael A. Soss)
in Proceedings of the 10th Annual International Symposium on Algorithms and Computation (ISAAC'99), Lecture Notes in Computer Science, volume 1741, Chennai, India, December 16–18, 1999, pages 415–424.
- Fast Allocation and Deallocation with an Improved Buddy System
(joint work with J. Ian Munro)
in Proceedings of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FST & TCS'99), Lecture Notes in Computer Science, volume 1738, Chennai, India, December 13–15, 1999, pages 84–96.
- Ununfoldable Polyhedra with Triangular Faces
(joint work with Marshall Bern, David Eppstein, Eric Kuo, Andrea Mantler, and Jack Snoeyink)
in Abstracts from the 4th CGC Workshop on Computational Geometry (CGC'99), Baltimore, Maryland, October 15–16, 1999.
- Open Problems from CCCG'99
(joint work with Joseph O'Rourke)
in Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, British Columbia, Canada, August 15–18, 1999.
- Hinged Dissection of Polyominoes and Polyiamonds
(joint work with Martin L. Demaine, David Eppstein, and Erich Friedman)
in Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, British Columbia, Canada, August 15–18, 1999.
- Ununfoldable Polyhedra
(joint work with Marshall Bern, David Eppstein, and Eric Kuo)
in Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, British Columbia, Canada, August 15–18, 1999, pages 13–16.
- Resizable Arrays in Optimal Time and Space
(joint work with Andrej Brodnik, Svante Carlsson, J. Ian Munro, and Robert Sedgewick)
in Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99), Lecture Notes in Computer Science, volume 1663, Vancouver, British Columbia, Canada, August 11–14, 1999, pages 37–48.
- Representing Trees of Higher Degree
(joint work with David Benoit, J. Ian Munro, and Venkatesh Raman)
in Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99), Lecture Notes in Computer Science, volume 1663, Vancouver, British Columbia, Canada, August 11–14, 1999, pages 169–180.
- Polyhedral Sculptures with Hyperbolic Paraboloids
(joint work with Martin L. Demaine and Anna Lubiw)
in Proceedings of the 2nd Annual Conference of BRIDGES: Mathematical Connections in Art, Music, and Science (BRIDGES'99), Winfield, Kansas, July 30–August 1, 1999, pages 91–100.
- Metamorphosis of the Cube
(joint work with Martin Demaine, Anna Lubiw, Joseph O'Rourke, and Irena Pashchenko)
in 8th Annual Video Review of Computational Geometry, Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SoCG'99), Miami Beach, Florida, June 13–16, 1999, pages 409–410.
- Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami
(joint work with Martin L. Demaine and Joseph S. B. Mitchell)
in Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SoCG'99), Miami Beach, Florida, June 13–16, 1999, pages 105–114.
- Folding and One Straight Cut Suffice
(joint work with Martin L. Demaine and Anna Lubiw)
in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), Baltimore, Maryland, January 17–19, 1999, pages 891–892.
- Efficient Algorithms for Petersen's Matching Theorem
(joint work with Therese C. Biedl, Prosenjit Bose, and Anna Lubiw)
in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), Baltimore, Maryland, January 17–19, 1999, pages 130–139.
- Locked and Unlocked Polygonal Chains in 3D
(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)
in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), Baltimore, Maryland, January 17–19, 1999, pages 866–867.
- Folding and Cutting Paper
(joint work with Martin L. Demaine and Anna Lubiw)
in Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98), Lecture Notes in Computer Science, volume 1763, Tokyo, Japan, December 9–12, 1998, pages 104–117.
- Folding Any Silhouette from a Strip
(joint work with Martin L. Demaine and Joseph S. B. Mitchell)
in Abstracts from the 3rd CGC Workshop on Computational Geometry (CGC'98), Providence, Rhode Island, October 11–12, 1998.
- Planar Drawings of Origami Polyhedra
(joint work with Martin L. Demaine)
in Proceedings of the 6th Symposium on Graph Drawing (GD'98), Lecture Notes in Computer Science, volume 1547, Montréal, Québec, Canada, August 13–15, 1998, pages 438–440.
- Hiding Disks in Folded Polygons
(joint work with Therese C. Biedl, Martin L. Demaine, Anna Lubiw, and Godfried T. Toussaint)
in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.
- Unfolding Some Classes of Orthogonal Polyhedra
(joint work with Therese Biedl, Martin Demaine, Anna Lubiw, Mark Overmars, Joseph O'Rourke, Steve Robbins, and Sue Whitesides)
in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.
- 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)
in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.
- A Disk-Packing Algorithm for an Origami Magic Trick
(joint work with Marshall Bern, David Eppstein, and Barry Hayes)
in Proceedings of the International Conference on Fun with Algorithms (FUN'98), Isola d'Elba, Italy, June 18–20, 1998, pages 32–42.
- Protocols for Non-Deterministic Communication over Synchronous Channels
in Proceedings of the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing (IPPS/SPDP'98), Orlando, Florida, March 30–April 3, 1998, pages 24–30.
- Converting C Pointers to Java References
in Proceedings of the ACM 1998 Workshop on Java for High-Performance Network Computing (Java'98), Palo Alto, California, February 28–March 1, 1998.
- A Threads-Only MPI Implementation for the Development of Parallel Programs
in Proceedings of the 11th International Symposium on High Performance Computing Systems (HPCS'97), Winnipeg, Manitoba, Canada, July 10–12, 1997, pages 153–163.
- Higher-Order Concurrency in Java
in Proceedings of the Parallel Programming and Java Conference (WoTUG20), Enschede, the Netherlands, April 12–16, 1997, pages 34–47.
- Higher-Order Concurrency in PVM
in Proceedings of the Cluster Computing Conference (CCC'97), Atlanta, Georgia, March 9–12, 1997.
- First-Class Communication in MPI
in Proceedings of the 2nd MPI Developer's Conference, Notre Dame, Indiana, July 1–2, 1996, pages 189–194.
- Evaluating the Performance of Parallel Programs in a Pseudo-Parallel MPI Environment
in Proceedings of the 10th International Symposium on High Performance Computing Systems (HPCS'96), Ottawa, Ontario, Canada, June 5–7, 1996.
- Direction-First e-cube: A New Routing Algorithm for k-ary n-cube Networks
(joint work with Sampalli Srinivas)
in Proceedings of the 9th International Symposium on High Performance Computing Systems (HPCS'95), Montréal, Québec, Canada, July 10–12, 1995, pages 329–338.
- Tetris is Hard, Even to Approximate
(joint work with Susan Hohenberger and David Liben-Nowell)
Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, October 21, 2002.
- Frequency Estimation of Internet Packet Streams with Limited Space
(joint work with Alejandro López-Ortiz and J. Ian Munro)
Massachusetts Institute of Technology, August 2002.
- Solitaire Clobber
(joint work with Martin L. Demaine and Rudolf Fleischer)
Technical Report HKUST-TCSC-2002-05, Hong Kong University of Science and Technology, April 2002.
- Exponential Speedup of Fixed Parameter Algorithms on K_{3,3}-minor-free or K_{5}-minor-free Graphs
(joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
Technical Report MIT-LCS-TR-838, Massachusetts Institute of Technology, March 18, 2002.
- Straightening Polygonal Arcs and Convexifying Polygonal Cycles
(joint work with Robert Connelly and Günter Rote)
Technical Report B 02-02, Fachbereich Mathematik und Informatik, Serie B - Informatik, Freie Universität Berlin, February 2002.
- 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ř)
Technical Report 2001-26, Department of Computer Science, University of Waterloo, December 2001.
- Vertex-Unfoldings of Simplicial Manifolds
(joint work with David Eppstein, Jeff Erickson, George W. Hart, and Joseph O'Rourke)
Technical Report 072, Smith College, October 2001.
- Vertex-Unfoldings of Simplicial Polyhedra
(joint work with David Eppstein, Jeff Erickson, George W. Hart, and Joseph O'Rourke)
Technical Report 071, Smith College, July 2001.
- Optimal Arrangement of Leaves in the Tree Representing Hierarchical Clustering of Gene Expression Data
(joint work with Therese Biedl, Broňa Brejová, Angèle M. Hamel, and Tomáš Vinař)
Technical Report 2001-14, Department of Computer Science, University of Waterloo, April 2001.
- Fun-Sort
(joint work with Therese Biedl, Timothy Chan, Rudolf Fleischer, Mordecai Golin, and J. Ian Munro)
Technical Report HKUST-TCSC-2001-03, Hong Kong University of Science and Technology, February 2001.
- 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)
Technical Report SOCS-00.7, School of Computer Science, McGill University, September 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)
Technical Report UU-CS-2000-31, Universiteit Utrecht, July 2000.
- Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes
(joint work with Martin Demaine, Anna Lubiw, and Joseph O'Rourke)
Technical Report 069, Smith College, July 2000.
- Balanced k-Colorings
(joint work with Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Martin L. Demaine, Rudolf Fleischer, and Ming-Wei Wang)
Technical Report CS-2000-08, Department of Computer Science, University of Waterloo, March 2000.
- Open Problems from CCCG'99
(joint work with Joseph O'Rourke)
Technical Report 066, Smith College, March 2000.
- PushPush is NP-hard in 2D
(joint work with Martin L. Demaine and Joseph O'Rourke)
Technical Report 065, Smith College, January 2000.
- Locked and Unlocked Polygonal Chains in 3D
(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)
Technical Report 060, Smith College, October 1999.
- Ununfoldable Polyhedra
(joint work with Marshall Bern, David Eppstein, and Eric Kuo)
Technical Report CS-99-04, Department of Computer Science, University of Waterloo, August 1999.
- Resizable Arrays in Optimal Time and Space
(joint work with Andrej Brodnik, Svante Carlsson, J. Ian Munro, and Robert Sedgewick)
Technical Report CS-99-09, Department of Computer Science, University of Waterloo, 1999.
- Convexifying Monotone Polygons
(joint work with Therese C. Biedl, Sylvain Lazard, Steven M. Robbins, and Michael A. Soss)
Technical Report CS-99-03, Department of Computer Science, University of Waterloo, March 1999.
- Adaptive Set Intersections
(joint work with Alejandro López-Ortiz and J. Ian Munro)
Technical Report TR98-120, Faculty of Computer Science, University of New Brunswick, 1998.
- Planar Drawings of Origami Polyhedra
(joint work with Martin L. Demaine)
Technical Report CS-98-17, Department of Computer Science, University of Waterloo, August 1998.
- Adaptive Protocols for Negotiating Non-Deterministic Choice over Synchronous Channels
Technical Report CS-97-35, Department of Computer Science, University of Waterloo, September 1997.
- Computing Extreme Origami Bases
(joint work with Martin L. Demaine)
Technical Report CS-97-22, Department of Computer Science, University of Waterloo, May 1997.
- Origamizer: A Practical Algorithm for Folding Any Polyhedron
(joint work with Tomohiro Tachi)
Manuscript, 2017.
- Open Problems from Dagstuhl Seminar 09511: Parameterized Complexity and Approximation Algorithms
(joint work with MohammadTaghi Hajiaghayi and Dániel Marx)
Manuscript, December 2009.
- Open Problems from Dagstuhl Seminar 07281: Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs
(joint work with Gregory Gutin, Dániel Marx, and Ulrike Stege)
Manuscript, July 2007.
- De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space)
(joint work with Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai Pǎtraşcu)
Manuscript, December 2005.
- Bidimensionality, Map Graphs, and Grid Minors
(joint work with MohammadTaghi Hajiaghayi)
Manuscript, February 2005.
- Efficient Tree Layout in a Multilevel Memory Hierarchy
(joint work with Stephen Alstrup, Michael A. Bender, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, and Mikkel Thorup)
Manuscript, December 2003.
- Open Problems on Polytope Reconstruction
(joint work with Jeff Erickson)
Manuscript, July 1999.
These pages are generated automagically from a
BibTeX file.
Last updated September 2, 2021 by
Erik Demaine.