| Name: | Emily Chin |
|---|---|
| Email: | echin@g.hmc.edu |
| Office: | Virtual |
| Home Institution: | Harvey Mudd College |
| Mentor: | Dr. Periklis Papakonstantinou |
| Project: | Machine Learning for SAT-solving Heuristics |
About My Project
3-SAT is a known NP-Hard problem in theoretical computer science. In other words, it takes exponential time to deterministically solve this problem. For my project, I will be using the SAT heuristic and machine learning.
Weekly Project Log
Week 1
During this first week, we had orientation, where all the REU participants were able to meet each other. I also got this website setup. I met with my mentor and we decided what the first few steps should be. Based on that, I started doing research on some algorithms.
Week 2
I read a paper my mentor recommended on an algorithm and its runtime. Next, I built a parser that will take in the SAT formulas in the DIMACS files and convert them into a csv file. I also wrote a program to solve the SAT formula while extracting some key features.
Week 3
This week, I worked on analyzing the data by creating bar graphs. I reported which features looked interesting to look further into.
Week 4
This week, I tried a different classification for SAT formulas based on its satisfiability.
Week 5
This week I wrote up a report for what I have done so far. I also watched some lectures on some machine learning techniques.
Week 6
I finished watched more lectures and did a practice tutorial using the machine learning tools.
Week 7
I started training and testing the machine learning tools for my project.
Week 8
I tried several different features and created graphs to show a trend.
Week 9
For the final week of the REU, I worked on the paper and presentation.
Acknowledgements
This work was carried out while the author, Emily Chin, was a participant in the 2021 DIMACS REU program at Rutgers University, supported by NSF grant CCF-1852215