mlsanityData to 7 Oct 2026

TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability

arXiv 2608.09538 ↗First posted 10 Aug 2026cs.CL cs.AIcited by 3

Not on the map. Why?

Abstract (arXiv)

We introduce TCS-Bench, a benchmark for evaluating Large Language Models (LLMs) on research-level Theoretical Computer Science (TCS) proof generation. TCS-Bench consists of theorem-proving tasks from papers published at top theoretical computer science venues (STOC, FOCS, and SODA). Each task provides the necessary context to derive a self-contained proof for a target result. We evaluate state-of-the-art models on this benchmark. We verify the correctness of generated proofs via a verification agent, and further benchmark the verifier against human-expert proof judgements on a set of target statements and generated proofs pairs. Our reference verifier achieves over 90% accuracy on the expert labeled set.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 166 of its 228 references that are in the map. First posted on arXiv 10 Aug 2026.

Builds on

166 of 228 references.

References · 166

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2023AGIEval: A Human-Centric Benchmark for Evaluating Foundation Modelscited by 701
  3. 2025GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learningcited by 449
  4. 2021AI and the Everything in the Whole Wide World Benchmarkcited by 340
  5. 2025PaperBench: Evaluating AI's Ability to Replicate AI Researchcited by 286
  6. 2025MathArena: Evaluating LLMs on Uncontaminated Math Competitionscited by 275
  7. 2025Gold-medalist Performance in Solving Olympiad Geometry with AlphaGeometry2cited by 95
  8. 2023GFlowNets for AI-Driven Scientific Discoverycited by 63
  9. 2024CHAMP: A Competition-level Dataset for Fine-Grained Analyses of LLMs' Mathematical Reasoning Capabilitiescited by 43
  10. 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
  11. 2025Near-Optimal Algorithms for Omnipredictioncited by 33
  12. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 30
38 more
  1. 2025CombiBench: Benchmarking LLM Capability for Combinatorial Mathematicscited by 28
  2. 2025The Open Proof Corpus: A Large-Scale Study of LLM-Generated Mathematical Proofscited by 27
  3. 2023The transformative potential of machine learning for experiments in fluid mechanicscited by 26
  4. 2025BrokenMath: A Benchmark for Sycophancy in Theorem Proving with LLMscited by 23
  5. 2023Learning quantum Hamiltonians at any temperature in polynomial timecited by 20
  6. 2025Proving Olympiad Inequalities by Synergizing LLMs and Symbolic Reasoningcited by 17
  7. 2025MathConstruct: Challenging LLM Reasoning with Constructive Proofscited by 16
  8. 2022Correlation Clustering with Sherali-Adamscited by 15
  9. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  10. 2021Pricing Query Complexity of Revenue Maximizationcited by 12
  11. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  12. 2021Double Coverage with Machine-Learned Advicecited by 10
  13. 2021Single-Sample Prophet Inequalities via Greedy-Ordered Selectioncited by 8
  14. 2022Deletion Robust Submodular Maximization over Matroidscited by 7
  15. 2024Certifying almost all quantum states with few single-qubit measurementscited by 7
  16. 2025Nearly Tight Regret Bounds for Profit Maximization in Bilateral Tradecited by 7
  17. 2026LemmaBench: A Live, Research-Level Benchmark to Evaluate LLM Capabilities in Mathematicscited by 7
  18. 2026Measuring Progress in Reasoning Toward Mathematical Discovery with Automatic Verificationcited by 7
  19. 2021Spectral Clustering Oracles in Sublinear Timecited by 6
  20. 2021Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsackcited by 6
  21. 2023Breaking the 3/4 Barrier for Approximate Maximin Sharecited by 6
  22. 2021The Reachability Problem for Petri Nets is Not Primitive Recursivecited by 5
  23. 2021On Classifying Continuous Constraint Satisfaction Problemscited by 5
  24. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  25. 2024Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Banditscited by 4
  26. 2024Learning the structure of any Hamiltonian from minimal assumptionscited by 4
  27. 2024Data-Driven Solution Portfolioscited by 4
  28. 2020Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simplercited by 3
  29. 2021Online Discrepancy with Recourse for Vectors and Graphscited by 3
  30. 2023New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithmscited by 3
  31. 2024Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matchingcited by 3
  32. 2024Fully Dynamic k-Median with Near-Optimal Update Time and Recoursecited by 3
  33. 2025A Case Study on the Effectiveness of LLMs in Verification with Proof Assistantscited by 3
  34. 2019Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphscited by 2
  35. 2021Algorithms and Hardness for Multidimensional Range Updates and Queriescited by 2
  36. 2021Small space and streaming pattern matching with k editscited by 2
  37. 2021Computational Hardness of the Hylland-Zeckhauser Schemecited by 2
  38. 2021Incremental SSSP for Sparse Digraphs Beyond the Hopset Barriercited by 2

50 most cited of 166 All 166 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026FormalTCS: Benchmarking End-to-End Frontier Formal Theoretical Computer Science Research of Large Language Modelscited by 2
  2. 2026Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Sciencecited by 0
  3. 2026TCSAlgBench: Benchmarking Automated Proving for Research-Level Theoretical Computer Sciencecited by 0