# The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics

arXiv: https://arxiv.org/abs/2601.16849 · HTML: https://mlsanity.com/paper/2601.16849/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 22 references that are in the map.
- First posted on arXiv 23 Jan 2026.

## Builds on (most cited first, 7 of 7)

- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)
- [Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search](https://mlsanity.com/paper/2311.03583/) (2023)
- [Best Fit Bin Packing with Random Order Revisited](https://mlsanity.com/paper/2012.00511/) (2020)
- [The Alternating Stock Size Problem and the Gasoline Puzzle](https://mlsanity.com/paper/1511.09259/) (2015)
- [Smoothed Analysis of Pareto Curves in Multiobjective Optimization](https://mlsanity.com/paper/2010.11064/) (2020)
- [The Price of Hierarchical Clustering](https://mlsanity.com/paper/2205.01417/) (2022)

## Abstract (arXiv)

We demonstrate the power of human-LLM collaboration in tackling open problems in theoretical computer science. Focusing on combinatorial optimization, we refine outputs from the FunSearch algorithm [Romera-Paredes et al., Nature 2023] to derive state-of-the-art lower bounds for standard heuristics. Specifically, we target the generation of adversarial instances where these heuristics perform poorly. By iterating on FunSearch's outputs, we identify improved constructions for hierarchical k-median clustering, bin packing, the knapsack problem, and a generalization of Lov'asz's gasoline problem - some of these have not seen much improvement for over a decade, despite intermittent attention. These results illustrate how expert oversight can effectively extrapolate algorithmic insights from LLM-based evolutionary methods to break long-standing barriers. Our findings demonstrate that while LLMs provide critical initial patterns, human expertise is essential for transforming these patterns into mathematically rigorous and insightful constructions. This work highlights that LLMs are a strong collaborative tool in mathematics and computer science research.