% Key papers for Computational thresholds in graphs and structure (scime atlas, https://atlas.scime.ai). Authors are not included: add them from the paper pages.

@inproceedings{aaai2023_from_3731,
  title = {{From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2023},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/26462},
}

@inproceedings{icml2016_exact_35826,
  title = {{Exact Exponent in Optimal Rates for Crowdsourcing}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2016},
  url = {https://proceedings.mlr.press/v48/gaoa16.html},
}

@inproceedings{icml2020_linear_38423,
  title = {{Linear Lower Bounds and Conditioning of Differentiable Games}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2020},
  url = {https://icml.cc/virtual/2020/poster/6357},
}

@inproceedings{neurips2016_achieving_55557,
  title = {{Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2016},
  url = {https://nips.cc/virtual/2016/poster/7414},
}

@inproceedings{neurips2022_the_66278,
  title = {{The Query Complexity of Cake Cutting}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2022},
  url = {https://nips.cc/virtual/2022/poster/52840},
}

@inproceedings{aaai2017_phase_106120,
  title = {{Phase Transitions for Scale-Free SAT Formulas}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2017},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/11133},
}

@inproceedings{icml2016_optimality_35938,
  title = {{Optimality of Belief Propagation for Crowdsourced Classification}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2016},
  url = {https://proceedings.mlr.press/v48/ok16.html},
}

@inproceedings{neurips2018_sequential_57621,
  title = {{Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2018},
  url = {https://nips.cc/virtual/2018/poster/11613},
}

@inproceedings{aaai2016_closing_105372,
  title = {{Closing the Gap Between Short and Long XORs for Model Counting}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2016},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/10430},
}

@inproceedings{icml2017_lost_36277,
  title = {{Lost Relatives of the Gumbel Trick}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2017},
  url = {https://icml.cc/virtual/2017/poster/463},
}

@inproceedings{aaai2017_approximation_100934,
  title = {{Approximation and Parameterized Complexity of Minimax Approval Voting}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2017},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/10575},
}

@inproceedings{aaai2016_alternative_105376,
  title = {{Alternative Filtering for the Weighted Circuit Constraint: Comparing Lower Bounds for the TSP and Solving TSPTW}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2016},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/10434},
}

@inproceedings{neurips2017_statistical_56685,
  title = {{Statistical Cost Sharing}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2017},
  url = {https://nips.cc/virtual/2017/poster/9393},
}

@inproceedings{aaai2017_new_101085,
  title = {{New Lower Bound for the Minimum Sum Coloring Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2017},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/10661},
}

@inproceedings{aaai2017_query_102729,
  title = {{Query Complexity of Tournament Solutions}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2017},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/10702},
}

@inproceedings{aaai2017_number_101427,
  title = {{Number Restrictions on Transitive Roles in Description Logics with Nominals}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2017},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/10678},
}

@inproceedings{aaai2021_proportional_1204,
  title = {{Proportional Representation under Single-Crossing Preferences Revisited}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2021},
  url = {https://aaai.org/papers/05286-proportional-representation-under-single-crossing-preferences-revisited/},
}

@inproceedings{icml2017_improving_36230,
  title = {{Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2017},
  url = {https://icml.cc/virtual/2017/poster/728},
}

@inproceedings{icml2021_online_39737,
  title = {{Online Unrelated Machine Load Balancing with Predictions Revisited}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2021},
  url = {https://icml.cc/virtual/2021/poster/10465},
}

@inproceedings{aaai2021_new_1065,
  title = {{New Length Dependent Algorithm for Maximum Satisfiability Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2021},
  url = {https://aaai.org/papers/03634-new-length-dependent-algorithm-for-maximum-satisfiability-problem/},
}

@inproceedings{aaai2024_identification_6261,
  title = {{Identification for Tree-Shaped Structural Causal Models in Polynomial Time}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2024},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/30023},
}

@inproceedings{neurips2024_low_70375,
  title = {{Low Degree Hardness for Broadcasting on Trees}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2024},
  url = {https://neurips.cc/virtual/2024/poster/96725},
}

@inproceedings{neurips2024_lookback_73022,
  title = {{Lookback Prophet Inequalities}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2024},
  url = {https://neurips.cc/virtual/2024/poster/94401},
}

@inproceedings{aaai2024_sampling_7255,
  title = {{Sampling for Beyond-Worst-Case Online Ranking}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2024},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/30051},
}

@inproceedings{aaai2025_consistent_8506,
  title = {{Consistent Query Answering over Existential Rules with Open and Closed Predicates}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2025},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/33654},
}

@inproceedings{aaai2025_exact_9042,
  title = {{Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2025},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/33514},
}

@inproceedings{aaai2025_parameterized_10267,
  title = {{Parameterized Complexity of Caching in Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence (AAAI)},
  year = {2025},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/33221},
}

@inproceedings{icml2024_on_45673,
  title = {{On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2024},
  url = {https://icml.cc/virtual/2024/poster/32779},
}

@inproceedings{icml2026_matroid_49997,
  title = {{Matroid Algorithms Under Size-Sensitive Independence Oracles}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2026},
  url = {https://openreview.net/forum?id=80Job2F5eb},
}

@inproceedings{icml2026_asymptotically_52691,
  title = {{Asymptotically Optimal Sequential Testing with Markovian Data}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2026},
  url = {https://openreview.net/forum?id=YEckWPoS09},
}

@inproceedings{icml2026_optimal_52737,
  title = {{Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2026},
  url = {https://openreview.net/forum?id=Yd1jFl0jBt},
}

@inproceedings{icml2026_learning_53233,
  title = {{Learning Unanimously Acceptable Lotteries via Queries}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2026},
  url = {https://openreview.net/forum?id=daiccpXZfU},
}

@inproceedings{icml2026_why_53619,
  title = {{Why Agentic Theorem Prover Works: A Statistical Provability Theory of Mathematical Reasoning Models}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2026},
  url = {https://openreview.net/forum?id=hAQZl57Nvx},
}

@inproceedings{icml2026_hallucination_55020,
  title = {{Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing}},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2026},
  url = {https://openreview.net/forum?id=uuD1rE5KU5},
}

@inproceedings{neurips2024_cryptographic_72383,
  title = {{Cryptographic Hardness of Score Estimation}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2024},
  url = {https://neurips.cc/virtual/2024/poster/94969},
}

@inproceedings{neurips2024_on_74179,
  title = {{On the Expressive Power of Tree-Structured Probabilistic Circuits}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2024},
  url = {https://neurips.cc/virtual/2024/poster/93366},
}

@inproceedings{neurips2025_reconstruction_74760,
  title = {{Reconstruction and Secrecy under Approximate Distance Queries}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2025},
  url = {https://openreview.net/forum?id=0vJJdEiXOb},
}

@inproceedings{neurips2025_on_75307,
  title = {{On Union-Closedness of Language Generation}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2025},
  url = {https://openreview.net/forum?id=6h7HLx1kbH},
}

@inproceedings{neurips2025_tight_75350,
  title = {{Tight Bounds for Answering Adaptively Chosen Concentrated Queries}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2025},
  url = {https://openreview.net/forum?id=79GwCnXYej},
}

@inproceedings{neurips2025_list_76166,
  title = {{List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression}},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year = {2025},
  url = {https://openreview.net/forum?id=GJbrk55Bt8},
}