dimacs logo color

REU

REU Participant Details

Elkins, Corbet

  • Corbet Elkins participant image
  • Corbet Elkins
  • University: Purdue University-Main Campus IN
  • Project Summary Page: 975 - Hardness of Rubiks Tables
  • Mentor: Jingjin Yu
  • Mentor Department: Computer Science
  • Project Site: https://archive.reu.dimacs.rutgers.edu/2025/ce383/public_html
  • Project Site - Original: http://reu.dimacs.rutgers.edu/~ce383
  • Personal Site: http://reu.dimacs.rutgers.edu/~ce383/
  • Participant Year: 2025
  • Acknowlegements:

    This work is supported by NSF grant CCF-2447342
  • Weekly Log:
    Week 1 (5/26-5/30)Log Description:

    Read through various proposed projects, ultimately deciding to work on the Rubiks Table problem. Tried several reductions to work towards the current goal. Worked on the initial presentation.

    Current Goal: Prove minimizing parallel shuffles for the Rubiks Table problem is NP-hard.

    Week 2 (6/2-6/6)Log Description:

    Continued working on showing NP-hardness of minimizing parallel shuffles. I believe I have a reduction after much trial and error.

    Current Goal: Prove minimizing shuffles for the Rubiks table is NP-hard in the general setting.

    Week 3 (6/9-6/13)Log Description:

    Finished the proof of NP-hardness of parallel Rubiks table shuffles.

    Current Goal: Work towards showing minimizing shuffles for the Rubiks table is NP-hard.

    Week 4 (6/16-6/20)Log Description:

    Got some minor results with regards to the Rubiks table problem. I started looking into some other related problems. One of which is a polyomino problem where we want to stack polyominoes such that we can always see at least one block from each.

    Current Goal: Think about the polyomino problem

    Week 5 (6/23-6/27)Log Description:

    Continued working on show NP-hardness of the Rubiks table problem. Read through this paper on NP-hardness of n x n x n Rubiks cube, which I think will be very helpful for proving NP-hardness of the labeled Rubiks table problem. I believe I have a reduction for showing the unlabeled Rubiks table is NP-hard, but the proof is still in the works.

    Current Goal: Try to show NP-hardness of labeled Rubiks table and finish proof of hardness of regular Rubiks Table.

    Week 6 (6/30-7/4)Log Description:

    Not much progress was made this week. I've still been working on proving hardness of the Rubik's table problem.

    Week 7 (7/7-7/11)Log Description:

    I started working on framing the optimal Rubiks table problem as an integer linear programming problem. I also started working on the final presentation and final report.

    Week 8 (7/14-7/18)Log Description:

    I finished up the final presentation slides, which can be found here. I also finished packing up since I leave for Prague Friday.

    Week 9 (7/21-7/25)Log Description:

    This week I am in Prague attending various lectures at Charles University. It has been a very enjoyable experience and is interesting being able to explore a variety of fields. I also finished writing my final report.
  • Presentations:
    final_presentation.pdf