Summary of Hardcore Generation: Generating Hard Unsat Problems For Data Augmentation, by Joseph Cotnareanu et al.
HardCore Generation: Generating Hard UNSAT Problems for Data Augmentation
by Joseph Cotnareanu, Zhanguang Zhang, Hui-Ling Zhen, Yingxue Zhang, Mark Coates
First submitted to arxiv on: 27 Sep 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Artificial Intelligence (cs.AI)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary The paper proposes a novel approach to generating realistic datasets for solving Boolean satisfiability (SAT) problems using deep learning methods. The authors highlight the limitations of existing public datasets, which are often randomly generated or contain only a few examples from unrelated problem families. To address this issue, they introduce a fast core detection procedure that uses a graph neural network to identify and manipulate the key contributors to a problem’s hardness, known as cores. This enables the efficient generation of synthetic SAT problems that retain key attributes of the original example problems. The authors demonstrate the effectiveness of their approach through experiments, showing that the generated datasets can be used for data augmentation to improve solver runtime prediction. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper helps us solve a big problem in computer science called Boolean satisfiability (SAT). Right now, we don’t have enough good examples to train our computers to get better at solving SAT problems. The authors found a way to make more realistic examples using deep learning methods. They developed a special tool that can quickly find the most important parts of an SAT problem, which they call “cores.” This lets them create lots of new examples that are hard to solve and look like real problems. The authors tested their approach and showed that it works well. This is important because we need more good data to train our computers to get better at solving SAT problems. |
Keywords
» Artificial intelligence » Data augmentation » Deep learning » Graph neural network
