Pith. sign in

REVIEW 3 major objections 6 minor 236 references

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

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read TCS-Bench measures whether LLMs can prove 300 research-level theorems from top TCS venues, and the paper reports a verifier that matches human experts on over 90 percent of a labeled proof set.

desk verdict The benchmark design is genuinely useful, but the reported scores rest on a verifier that is calibrated in-sample and anchored to the ground-truth proof; fix that and this becomes a standard resource. read the letter →

arxiv 2608.09538 v2 pith:YXZBOYLO submitted 2026-08-10 cs.CL cs.AI

Vincent Cohen-Addad , Dimitris Paparas , Ernest van Wijland , Max Springer , Julien Canitrot-Paradis , Honghao Lin , David Woodruff , Adarsh Kumarappan
show 8 more authors
Rajesh Jayaram Rudrajit Das Lalit Jain Ola Svensson Silvio Lattanzi Mislav Balunovic Theophane Weber Vahab Mirrokni
This is my paper · ORCID
classification cs.CLcs.AI
keywords TCS-BenchtheoremprovinglargelanguagemodelsproofverificationtheoreticalcomputersciencebenchmarkdesigndependencygraphLLMevaluation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

TCS-Bench is a benchmark built from 300 theorem-proving tasks extracted from papers at STOC, FOCS, and SODA, where each task gives a model a self-contained context of definitions and prior lemmas and asks it to prove a target result whose original proof is withheld. The paper's central claim is that an automated verification agent can grade the resulting proofs reliably: it reports over 90 percent agreement with human expert judgments on a 100-proof labeled set, which is what makes the benchmark's model scores meaningful. With that verifier, reported accuracy ranges from about 30 percent to 68 percent across public frontier models, with an agentic harness that combines two models via cross-model selection reaching 67.7 percent. If the verifier accuracy holds, TCS-Bench offers a repeatable, contamination-resistant way to track progress in research-level mathematical reasoning.

What carries the argument

The central machinery is the dependency-graph pipeline. A deterministic parser identifies all theorem-like environments in a paper's LaTeX source, an LLM pass maps proofs to statements and draws dependency edges, acyclicity is checked programmatically, and each statement receives a rank equal to the longest directed path ending at it; task contexts hide all statements of rank at least the target's rank, and optional masking of intermediate lemmas produces a difficulty curriculum. The evaluation machinery is the verifier: four independent calls to a cheap language model, each given the context, target statement, candidate proof, and ground-truth proof, with a majority of three or more 'correct' verdicts producing a pass. Its prompt was tuned on a 100-proof human-labeled set through a prompt-evolution pipeline, and the reported result is over 90 percent agreement with human experts.

What would settle it

Take 100 model-generated proofs that were never used in the verifier-prompt optimization, have human experts label each proof correct or incorrect, and run the reference verifier on the same proofs; if its agreement falls materially below the reported 90 percent, the benchmark's model scores are not calibrated measurements.

Watch

Extended reading notes

Core claim

The paper introduces TCS-Bench and claims that the difficulty of real theoretical-computer-science research can be measured. Each task is generated from the LaTeX source of a published paper by extracting the dependency graph of its statements and hiding all statements of rank at least the target's rank, so the solver must reconstruct the proof from provided definitions and intermediate lemmas, with more intermediate results masked to create harder variants. The load-bearing discovery is the automated proof verifier: a cheap language model is called four times on the context, target statement, candidate proof, and ground-truth proof, and the candidate passes if at least three calls mark it correct. The paper reports that this verifier matches human expert labels on over 90 percent of the 100-proof calibration set, and on that basis presents the benchmark's model accuracy scores as trustworthy measurements.

Load-bearing premise

The load-bearing assumption is that the verifier's over-90-percent agreement with human experts, measured on a 100-proof calibration set whose prompt was tuned by an automated prompt optimizer, transfers to all 300 tasks and to every proof a model produces—including correct proofs that are structured very differently from the ground-truth proof the verifier receives as a reference.

Editorial extensions

If this is right

  • If the verifier accuracy holds, the reported model scores become comparable, reproducible measurements of research-level proof-generation ability rather than informal judgments.
  • The difficulty curriculum from dependency masking ensures the benchmark is informative across the full capability spectrum instead of saturating at easy or impossible tasks.
  • Because tasks are drawn from papers that can postdate training cutoffs and can be added continuously, the benchmark can be refreshed in a way that resists contamination from memorized training data.
  • The cross-model selection results show that routing between two independent proof-producing runs, using a second model's critiques, lifts accuracy from 54.0 percent to 67.7 percent, a gain the paper attributes to self-rejection being informative while self-acceptance is not.
  • The 32-point gap between the strongest model (68 percent) and perfect performance (100 percent) is presented as the current frontier of context-dependent automated mathematical reasoning.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the verifier's accuracy generalizes beyond the 100-proof calibration set, the same dependency-graph recipe could produce proof-generation benchmarks in any mathematical field with available LaTeX sources, since nothing in the construction is specific to theoretical computer science.
  • Because the verifier is given the ground-truth proof as an input, its judgments may be biased toward proofs that resemble that reference; a held-out evaluation with correct proofs that are structurally different would settle whether the 90 percent figure transfers.
  • The cross-model selection finding suggests a general recipe for improving proof reliability without retraining: pair a generator with an independent critic and trust the critic when the generator's self-verification accepts too easily; whether the reported asymmetry holds for other model pairs is an open question.
  • The rank-based difficulty stratification offers a ready test: mask progressively more intermediate lemmas and measure whether model accuracy degrades smoothly, which would quantify how much proof scaffolding a model can reconstruct from context.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper introduces TCS-Bench, a benchmark of 300 theorem-proving tasks extracted from papers published at STOC, FOCS, and SODA between 2020 and 2026. For each task, the authors construct a self-contained context from the source paper's dependency graph, hide a target statement's proof, and optionally mask intermediate lemmas to create a curriculum of difficulty levels. The paper then evaluates several frontier LLMs (and an agentic harness called Colosseum) on the benchmark, scoring generated proofs with an automated verifier agent built from Gemini 3.1 Flash. The central methodological claim is that this verifier achieves over 90% accuracy against 100 human-expert proof judgments, which the paper uses to justify the trustworthiness of the reported model accuracies in Tables 1 and 2. The manuscript also reports that a cross-model selection rule within Colosseum improves accuracy from 54.0% to 67.7% on the benchmark.

Significance. If the verifier-accuracy claim were properly supported, TCS-Bench would be a genuinely valuable contribution: it addresses a real gap in research-level mathematical reasoning benchmarks, offers a transparent and reproducible construction pipeline, and provides a scalable way to grade natural-language proofs. The paper's strengths include the public release of tasks, the dependency-DAG-based difficulty scaling, the explicit quality-filtering checks, and the detailed prompts in Appendix A.1. However, the entire empirical contribution — including all model rankings and the Colosseum selection results — rests on the verifier's reliability. Because the current evidence for that reliability is an in-sample calibration after prompt tuning on the same small set of human-labeled proofs, the central claim is not yet established.

major comments (3)
  1. [Section 4.2; Section 1.1] The >90% accuracy figure is an in-sample estimate, not a held-out evaluation. Section 4.2 states that GEPA was run on the 100-example expert-labeled set to produce the prompt, and the same set is then used to report accuracy; no separate test split, no confidence interval, and no cross-validation are described. The contribution bullet in Section 1.1 calls this a "held-out set of 100 human-labeled proofs," which is contradicted by Section 4.2. Since every score in Tables 1 and 2 is produced by this verifier, the paper's central quantitative claim — that the reported model accuracies are trustworthy measurements of proof-generation ability — is not supported by the evidence as written. The authors should report accuracy on a held-out human-labeled set that was not used for GEPA tuning, with a confidence interval, and should clarify the relationship between the development and evaluation sets.
  2. [Section 4.1; Appendix A.1] The verifier receives the ground-truth proof as an input and is instructed to compare the student's logic, variable tracking, and case-splitting against it. In particular, the Case Integrity criterion says that if the ground_truth_proof relies on a specific case split, the student must address those exact boundaries, and the prompt explicitly requires matching the logical depth and cases of the ground truth. This design systematically penalizes correct proofs that establish the target through a different but valid route, which is a core failure mode for a proof verifier. The 50 correct calibration proofs were generated by the same solver and human-reviewed, so they likely share a limited structural family; the paper provides no evidence that the verifier accepts correct proofs outside that family. The authors should test the verifier on a set of correct proofs that are intentionally structurally diverse — e.g., human-written proofs from different authors, proofs from different models, and proofs that use alternative case splits — and report the acceptance rate on that set.
  3. [Section 5.2] The cross-model selection results in Table 2 and the associated AUC values (0.854 and 0.637) are computed on TCS-Bench itself, and the accuracy gains are graded by the same unvalidated verifier. The text states that the stronger critique direction was selected using "cross-model critique accuracy measured on TCS-Bench." If the verifier is biased toward ground-truth-similar proofs of the kind described in the previous comment, then the apparent improvement from 54.0% to 67.7% may reflect selection for verifier-approved style rather than mathematical correctness. These results should be re-reported after the verifier is validated on held-out, structurally diverse proofs, and the selection rule should be tuned on a set disjoint from the final evaluation set.
minor comments (6)
  1. [Section 1.1] The bullet claiming a "held-out set of 100 human-labeled proofs" is inconsistent with Section 4.2, which describes using that same set for GEPA prompt tuning; please revise the wording to describe the actual data split.
  2. [Section 5.1] Table 1 has a stray formatting artifact in the header ("Accuracy()"), and the heading "Results & Analysis" appears twice in Section 5.1; these should be cleaned up.
  3. [Section 5.2] There are several typographical issues in Section 5.2, including "AUC of 0 .854" (spurious space), "0 .637", and "47problems" missing a space; please proofread the numerical expressions.
  4. [Section 3.3] The paper states that the context is compressed to fit a standard context window of 10,000 tokens, but Section 5.1 describes models with 128K token budgets; please clarify whether the 10,000-token limit is a fixed benchmark design choice or an artifact of the evaluation setup.
  5. [Section 4.2] The GEPA tuning procedure is described only as "the GEPA improvement pipeline"; for reproducibility, please report the number of GEPA iterations, the prompt search space, the number of candidate prompts evaluated, and the final prompt selection criterion.
  6. [Figures 2 and 3] The example tasks in Figures 2 and 3 are internally inconsistent: the target statement about Algorithm 2 does not match the lemma about bounded sequences (u_n). Please replace these with a coherent running example or remove the illustrative statements.

Circularity Check

3 steps flagged · score 6.0 of 10

Verifier '90% accuracy' is the GEPA-tuned prompt's score on its own calibration set, not a held-out prediction; reported model scores inherit this in-sample bias.

  1. fitted input called prediction [Section 4.2 (Verifier Calibration); contrast with Section 1.1 bullet]
    "To design the verifier prompt, we generated proofs by running the solver on a set of tasks, disjoint from the benchmark. Then, human experts reviewed them, and produced a set of 50 correct proofs and 50 incorrect proofs. Finally, we ran the GEPA [3] improvement pipeline on this alignment task to produce a prompt that achieves an accuracy of more than 90%."

    The reported >90% figure is the accuracy of the GEPA-optimized prompt on the exact 100 proof-label pairs used to tune it. This is training-set accuracy, not a held-out estimate, yet the paper presents it as validation of the verifier and one bullet even calls it 'a held-out set of 100 human-labeled proofs.' Because every model accuracy in Tables 1 and 2 is produced by this same verifier, the central reliability claim reduces to the fit on the calibration data rather than an independent measurement of verifier generalization.

  2. fitted input called prediction [Section 5, 'Why cross-model' paragraph]
    "The direction of cross-model critique matters more than the precise threshold. Gemini 3.6 Flash judging Gemini 3.1 Pro achieves an AUC of 0.854, whereas Gemini 3.1 Pro judging Gemini 3.6 Flash provides a weaker signal, with an AUC of 0.637. We therefore fix the stronger direction, selected using cross-model critique accuracy measured on TCS-Bench."

    The headline cross-model accuracy of 67.7% is reported after the critique direction is chosen using the same benchmark on which that accuracy is measured. This is a model-selection step fitted to the test set, so the reported number is an in-sample, optimistically biased estimate rather than a prediction on new tasks. The paper acknowledges the selection was made 'on TCS-Bench' but still reports the resulting accuracy as a general benchmark result.

1 more flagged steps
  1. self definitional [Appendix A.1, verifier prompt]
    "Your task is to evaluate whether a provided 'student_answer' correctly and rigorously proves the 'Target Problem' ... You must compare the student's logic, variable tracking, and quantitative derivations against the 'ground_truth_proof'."

    The verifier's notion of 'correctly and rigorously proves' is operationally defined as matching the ground-truth proof, including its case structure and derivations, rather than as independent logical validity. A correct proof that reaches the target through a genuinely different route can be rejected, and the 50 calibration 'correct' proofs came from one solver family, so the 90% number chiefly measures template similarity to published proofs. This makes the claimed verification accuracy, and hence the benchmark scores built on it, a comparison-to-given-proof score presented as a measure of mathematical correctness.

full rationale

The benchmark is not a purely self-referential derivation: the 300 tasks come from published FOCS/STOC/SODA papers, the calibration labels are human-expert judgments, and the reported model accuracies are external empirical measurements. No load-bearing uniqueness theorem or self-citation chain is involved. However, the central validity claim of the paper—'Our reference verifier achieves over 90% accuracy on the expert labeled set'—is a fitted input called a prediction. Section 4.2 states that GEPA was run on the same 100-example set used to compute the accuracy, with no described train/test split, while the Section 1.1 bullet calls the set 'held-out.' In addition, the verifier prompt defines correctness as agreement with the supplied ground-truth proof, so the calibration score measures structural matching to a particular proof family rather than verified mathematical equivalence of arbitrary valid proofs. The cross-model selection in Section 5 similarly chooses its direction using TCS-Bench itself, inflating the reported 67.7%. These are concrete, quotable reductions of the paper's claimed validations to in-sample or by-construction quantities, which is why the circularity score is 6 rather than 0-2. The underlying task construction and benchmark content remain externally grounded, but the reliability of every reported model score rests on a verifier whose headline accuracy is its own calibration-set accuracy.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numeric free parameters are used in the sense of parameterized equations; the central empirical claim rests on the verifier, whose prompt was fitted via GEPA on the calibration set. The benchmark also assumes the reliability of LLM-based graph construction, compression, and semantic checks, and the correctness of published proofs and human labels.

assumptions (4)
  • domain assumption The 100 human expert labels (50 correct, 50 incorrect) are accurate and representative of the benchmark's task distribution.
    Used in Section 4.2 to validate the verifier; if the labels are wrong or non-representative, the 90% accuracy claim is invalid.
  • domain assumption The ground-truth proofs extracted from the source papers are correct.
    The benchmark assumes peer-reviewed proofs are valid; Section 3.4 uses the ground-truth proof as the correctness standard.
  • domain assumption The LLM-based dependency graph extraction and context compression preserve all logical prerequisites needed to prove each target.
    Sections 3.2 and 3.3 rely on an LLM analysis pass to build dependency edges and compress context; errors would make tasks unsolvable or leak proof content.
  • domain assumption The three LLM semantic checks (well-definedness, uniqueness, coherence) can reliably detect broken tasks.
    Section 3.4 uses LLM calls for quality filtering with no human verification of the filtered set.

how reviews work

0 comments
Cite this review

Pith. "Pith review of TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability." pith.science (2026). https://pith.science/paper/YXZBOYLO

@misc{pith2026260809538,
  author       = {Pith},
  title        = {Pith review of: TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YXZBOYLO}},
  note         = {Machine review of arXiv:2608.09538}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2608.09538 by the authors.

Figure 1
Figure 1. DAG example Scalable Difficulty Tasks. To create tasks spanning a range of difficulties, we exploit the dependency structure to generate multiple variants of each proof task. Starting from a base task where all dependencies are provided in the context, we systematically withhold intermediate results, requiring the model to discover and prove them on the way to the main target. Example. Consider proving Theorem T fro… view at source ↗
Figure 2
Figure 2. Base difficulty task (all dependencies provided) [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Task with omitted intermediary results to increase complexity. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

236 extracted references · 62 canonical work pages

  1. [1]

    The jacobian conjecture is false

    Claude Fable 5. The jacobian conjecture is false. https://x.com/__alpoge__/status/ 2079028340955197566, 2026. Accessed: 2026-08-07

    2026

  2. [2]

    GPT-4 technical report.arXiv preprint arXiv:2303.08774, 2023

    Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report.arXiv preprint arXiv:2303.08774, 2023

    arXiv 2023

  3. [3]

    Gepa: Reflective prompt evolution can outperform reinforcement learning.arXiv preprint arXiv:2507.19457, 2025

    Lakshya A Agrawal, Shangyin Tan, Dilara Soylu, Noah Ziems, Rishi Khare, Krista Opsahl-Ong, Arnav Singhvi, Herumb Shandilya, Michael J Ryan, Meng Jiang, et al. Gepa: Reflective prompt evolution can outperform reinforcement learning.arXiv preprint arXiv:2507.19457, 2025

    arXiv 2025

  4. [4]

    AI achieves silver-medal standard solving international 178 mathematical olympiad problems.DeepMind blog, 179:45, 2024

    Team AlphaProof and Team AlphaGeometry. AI achieves silver-medal standard solving international 178 mathematical olympiad problems.DeepMind blog, 179:45, 2024

    2024

  5. [5]

    MathArena: Evaluating LLMs on Uncontaminated Math Competitions.arXiv preprint arXiv:2505.23281, 2025

    Mislav Balunović, Jasper Dekoninck, Ivo Petrov, Nikola Jovanović, and Martin Vechev. MathArena: Evaluating LLMs on Uncontaminated Math Competitions.arXiv preprint arXiv:2505.23281, 2025

    arXiv 2025

  6. [6]

    A Case Study on the Effectiveness of LLMs in Verification with Proof Assistants.arXiv preprint arXiv:2508.18587, 2025

    Barış Bayazıt, Yao Li, and Xujie Si. A Case Study on the Effectiveness of LLMs in Verification with Proof Assistants.arXiv preprint arXiv:2508.18587, 2025

    arXiv 2025

  7. [7]

    Autonomous chemical research with large language models.Nature, 624(7992):570–578, 2023

    Daniil A Boiko, Robert MacKnight, Ben Kline, and Gabe Gomes. Autonomous chemical research with large language models.Nature, 624(7992):570–578, 2023

    2023

  8. [8]

    Gold-medalist performance in solving olympiad geometry with alphageometry2.arXiv preprint arXiv:2502.03544, 2025

    Yuri Chervonyi, Trieu H Trinh, Miroslav Olšák, Xiaomeng Yang, Hoang Nguyen, Marcelo Mene- gali, Junehyuk Jung, Vikas Verma, Quoc V Le, and Thang Luong. Gold-medalist performance in solving olympiad geometry with alphageometry2.arXiv preprint arXiv:2502.03544, 2025

    arXiv 2025

Show all 236 references
  1. [9]

    Math- Construct: Challenging LLM reasoning with constructive proofs

    Jasper Dekoninck, Mislav Balunovic, Nikola Jovanović, Ivo Petrov, and Martin Vechev. Math- Construct: Challenging LLM reasoning with constructive proofs. InICLR 2025 Workshop: VerifAI: AI Verification in the Wild, 2025

    2025

  2. [10]

    The Open Proof Corpus: A Large-Scale Study of LLM-Generated Mathematical Proofs.arXiv preprint arXiv:2506.21621, 2025

    Jasper Dekoninck, Ivo Petrov, Kristian Minchev, Mislav Balunovic, Martin Vechev, Miroslav Marinov, Maria Drencheva, Lyuba Konova, Milen Shumanov, Kaloyan Tsvetkov, et al. The Open Proof Corpus: A Large-Scale Study of LLM-Generated Mathematical Proofs.arXiv preprint arXiv:2506....

    2025

  3. [11]

    Trinh, Garrett Bingham, Dawsen Hwang, Yuri Chervonyi, Junehyuk Jung, Joonkyung Lee, Carlo Pagano, Sang hyun Kim, Federico Pasqualotto, Sergei Gukov, Jonathan N

    Tony Feng, Trieu H. Trinh, Garrett Bingham, Dawsen Hwang, Yuri Chervonyi, Junehyuk Jung, Joonkyung Lee, Carlo Pagano, Sang hyun Kim, Federico Pasqualotto, Sergei Gukov, Jonathan N. Lee, Junsu Kim, Kaiying Hou, Golnaz Ghiasi, Yi Tay, YaGuang Li, Chenkai Kuang, Yuan Liu, Hanzhao...

    2026

  4. [12]

    Towards an ai co-scientist.arXiv preprint arXiv:2502.18864, 2025

    Juraj Gottweis, Wei-Hung Weng, Alexander Daryin, Tao Tu, Anil Palepu, Petar Sirkovic, Artiom Myaskovsky, Felix Weissenberger, Keran Rong, Ryutaro Tanno, et al. Towards an ai co-scientist.arXiv preprint arXiv:2502.18864, 2025

    2025 arXiv

  5. [13]

    CRISPR-GPT: An LLM agent for automated design of gene-editing experiments.arXiv preprint arXiv:2404.18021, 2024

    Kaixuan Huang, Yuanhao Qu, Henry Cousins, William A Johnson, Di Yin, Mihir Shah, Denny Zhou, Russ Altman, Mengdi Wang, and Le Cong. CRISPR-GPT: An LLM agent for automated design of gene-editing experiments.arXiv preprint arXiv:2404.18021, 2024

    2024 arXiv

  6. [14]

    Gemini 2.5 pro capable of winning gold at imo 2025.arXiv preprint arXiv:2507.15855, 2025

    Yichen Huang and Lin F Yang. Gemini 2.5 pro capable of winning gold at imo 2025.arXiv preprint arXiv:2507.15855, 2025

    2025

  7. [15]

    Chemformer: a pre- trained transformer for computational chemistry.Machine Learning: Science and Technology, 3(1):015022, 2022

    Ross Irwin, Spyridon Dimitriadis, Jiazhen He, and Esben Jannik Bjerrum. Chemformer: a pre- trained transformer for computational chemistry.Machine Learning: Science and Technology, 3(1):015022, 2022

    2022

  8. [16]

    Gflownets for ai-driven scientific discovery.Digital Discovery, 2(3):557–577, 2023

    Moksh Jain, Tristan Deleu, Jason Hartford, Cheng-Hao Liu, Alex Hernandez-Garcia, and Yoshua Bengio. Gflownets for ai-driven scientific discovery.Digital Discovery, 2(3):557–577, 2023

    2023

  9. [17]

    Perfor- mance of chatgpt on usmle: potential for ai-assisted medical education using large language models.PLoS digital health, 2(2):e0000198, 2023

    Tiffany H Kung, Morgan Cheatham, Arielle Medenilla, Czarina Sillos, Lorie De Leon, Camille Elepaño, Maria Madriaga, Rimel Aggabao, Giezel Diaz-Candido, James Maningo, et al. Perfor- mance of chatgpt on usmle: potential for ai-assisted medical education using large language mod...

    2023

  10. [18]

    Benchmarking automated theorem proving with large language models

    Vanessa Lama, Catherine Ma, and Tirthankar Ghosal. Benchmarking automated theorem proving with large language models. InProceedings of the 1st Workshop on NLP for Science (NLP4Science), pages 208–218, 2024

    2024

  11. [19]

    Proving Olympiad Inequalities by Synergizing LLMs and Symbolic Reasoning

    Zenan Li, Zhaoyu Li, Wen Tang, Xian Zhang, Yuan Yao, Xujie Si, Fan Yang, Kaiyu Yang, and Xiaoxing Ma. Proving Olympiad Inequalities by Synergizing LLMs and Symbolic Reasoning. arXiv preprint arXiv:2502.13834, 2025

    2025 arXiv

  12. [20]

    CombiBench: Benchmarking LLM capability for combinatorial mathematics.arXiv preprint arXiv:2505.03171, 2025

    Junqi Liu, Xiaohan Lin, Jonas Bayer, Yael Dillies, Weijie Jiang, Xiaodan Liang, Roman Soletskyi, Haiming Wang, Yunzhou Xie, Beibei Xiong, et al. CombiBench: Benchmarking LLM capability for combinatorial mathematics.arXiv preprint arXiv:2505.03171, 2025

    2025 arXiv

  13. [21]

    CHAMP: A Competition-level Dataset for Fine-Grained Analyses of LLMs’ Mathematical Reasoning Capabilities.arXiv preprint arXiv:2401.06961, 2024

    Yujun Mao, Yoon Kim, and Yilun Zhou. CHAMP: A Competition-level Dataset for Fine-Grained Analyses of LLMs’ Mathematical Reasoning Capabilities.arXiv preprint arXiv:2401.06961, 2024

    2024 arXiv

  14. [22]

    An openai model has disproved a central conjecture in discrete geometry.https: //openai.com/index/model-disproves-discrete-geometry-conjecture/ , 2026

    OpenAI. An openai model has disproved a central conjecture in discrete geometry.https: //openai.com/index/model-disproves-discrete-geometry-conjecture/ , 2026. Accessed: 2026-08-07

    2026

  15. [23]

    Ten advances in mathematics and theoretical computer science.https://openai

    OpenAI. Ten advances in mathematics and theoretical computer science.https://openai. com/index/ten-advances-in-mathematics/, 2026. Accessed: 2026-08-07

    2026

  16. [24]

    Astroclip: a cross-modal foundation model for galaxies.Monthly Notices of the Royal Astronomical Society, 531(4):4990–5011, 2024

    Liam Parker, Francois Lanusse, Siavash Golkar, Leopoldo Sarra, Miles Cranmer, Alberto Bietti, Michael Eickenberg, Geraud Krawezik, Michael McCabe, Rudy Morel, et al. Astroclip: a cross-modal foundation model for galaxies.Monthly Notices of the Royal Astronomical Society, 531(4...

    2024

  17. [25]

    BrokenMath: A Benchmark for Sycophancy in Theorem Proving with LLMs.arXiv preprint arXiv:2510.04721, 2025

    Ivo Petrov, Jasper Dekoninck, and Martin Vechev. BrokenMath: A Benchmark for Sycophancy in Theorem Proving with LLMs.arXiv preprint arXiv:2510.04721, 2025

    2025

  18. [26]

    LemmaBench: A Live, Research-Level Benchmark to Evaluate LLM Capabilities in Mathematics.arXiv preprint arXiv:2602.24173, 2026

    Antoine Peyronnet, Fabian Gloeckle, and Amaury Hayat. LemmaBench: A Live, Research-Level Benchmark to Evaluate LLM Capabilities in Mathematics.arXiv preprint arXiv:2602.24173, 2026

    2026 arXiv

  19. [27]

    Ai and the everything in the whole wide world benchmark.arXiv preprint arXiv:2111.15366, 2021

    Inioluwa Deborah Raji, Emily M Bender, Amandalynne Paullada, Emily Denton, and Alex Hanna. Ai and the everything in the whole wide world benchmark.arXiv preprint arXiv:2111.15366, 2021

    2021 arXiv

  20. [28]

    Paperbench: Evaluating ai’s ability to replicate ai research

    Giulio Starace, Oliver Jaffe, Dane Sherburn, James Aung, Jun Shern Chan, Leon Maksin, Rachel Dias, Evan Mays, Benjamin Kinsella, Wyatt Thompson, et al. Paperbench: Evaluating ai’s ability to replicate ai research. InForty-second International Conference on Machine Learning

  21. [29]

    Solving olympiad geometry without human demonstrations.Nature, 625(7995):476–482, 2024

    Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations.Nature, 625(7995):476–482, 2024

    2024

  22. [30]

    Gpt-4 can ace the bar, but it only has a decent chance of passing the cfa exams

    Lakshmi Varanasi. Gpt-4 can ace the bar, but it only has a decent chance of passing the cfa exams. here’sa list of difficult exams the chatgpt and gpt-4 have passed.Business Insider, 5, 2023

    2023

  23. [31]

    The transformative potential of machine learning for experiments in fluid mechanics.Nature Reviews Physics, 5(9):536–545, 2023

    Ricardo Vinuesa, Steven L Brunton, and Beverley J McKeon. The transformative potential of machine learning for experiments in fluid mechanics.Nature Reviews Physics, 5(9):536–545, 2023

    2023

  24. [32]

    Horizon- math: Measuring ai progress toward mathematical discovery with automatic verification.arXiv preprint arXiv:2603.15617, 2026

    Erik Y Wang, Sumeet Motwani, James V Roggeveen, Eliot Hodges, Dulhan Jayalath, Charles London, Kalyan Ramakrishnan, Flaviu Cipcigan, Philip Torr, and Alessandro Abate. Horizon- math: Measuring ai progress toward mathematical discovery with automatic verification.arXiv preprint...

    2026

  25. [33]

    Scientific discovery in the age of artificial intelligence.Nature, 620(7972):47–60, 2023

    Hanchen Wang, Tianfan Fu, Yuanqi Du, Wenhao Gao, Kexin Huang, Ziming Liu, Payal Chandak, Shengchao Liu, Peter Van Katwyk, Andreea Deac, et al. Scientific discovery in the age of artificial intelligence.Nature, 620(7972):47–60, 2023

    2023

  26. [34]

    Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, Mohammad- Hossein Bateni, Simina Branzei, Michael P

    David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, Mohammad- Hossein Bateni, Simina Branzei, Michael P. Brenner, Lin Chen, Ying Feng, Lance Fortnow, Gang Fu, Ziyi Guan, Zahra Hadizadeh, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Adel Javanmard, Karthik ...

    2026

  27. [35]

    Exploring the role of large language models in the scientific method: from hypothesis to discovery.npj Artificial Intelligence, 1(1):14, 2025

    Yanbo Zhang, Sumeer A Khan, Adnan Mahmud, Huck Yang, Alexander Lavin, Michael Levin, Jeremy Frey, Jared Dunnmon, James Evans, Alan Bundy, et al. Exploring the role of large language models in the scientific method: from hypothesis to discovery.npj Artificial Intelligence, 1(1)...

    2025

  28. [36]

    Agieval: A human-centric benchmark for evaluating foundation models.arXiv preprint arXiv:2304.06364, 2023

    Wanjun Zhong, Ruixiang Cui, Yiduo Guo, Yaobo Liang, Shuai Lu, Yanlin Wang, Amin Saied, Weizhu Chen, and Nan Duan. Agieval: A human-centric benchmark for evaluating foundation models.arXiv preprint arXiv:2304.06364, 2023. 15 A Omitted Details A.1 Full Prompt Details We present ...

    2023 arXiv

  29. [37]

    safety margins

    **Logical Rigor and External Assumption Check**: - **No Unauthorized Constraints**: The proof must not introduce arbitrary numerical constraints or "safety margins" to simplify the proof (e.g., assumingk≥ 2, assumingϵis sufficiently small, or assuming sets are non-empty) when ...

  30. [38]

    outer queries

    **Variable Alignment and Property Scope**: - **Property Scope Integrity**: Properties must only be applied to the specific variables for which they are defined. If the proof generalizes a property of a subset to a larger set then this constitutes a failure (e.g., applying au-u...

  31. [39]

    mapping limits matching identical parameters constraints mapping

    **Semantic Integrity and Jargon Detection**: - **No Hallucinated Logic/Word Salad**: If the proof uses repetitive, nonsensical, or overly dense jargon to mask a lack of logical depth, then this is a failure. The proof must be linguistically coherent. If a paragraph consists of...

  32. [40]

    - **Boundary and Floor/Ceiling Precision**: Bounds must be exactly supported

    **Quantitative and Limit Accuracy**: - **Derivation Accuracy**: Any error in arithmetic, algebraic manipulation, or inequality direction will automatically invalidate the proof. - **Boundary and Floor/Ceiling Precision**: Bounds must be exactly supported. For example, if a flo...

  33. [41]

    **Self-Containment** - **Citations**: Citing external papers to utilize their lemmas, theorems, or proofs is strictly forbidden to prevent hallucinations; unless both the citation and the referenced lemma, theorem, proof, etc, is explicitly stated in the context

  34. [42]

    This is for your own benefit, to maximize the chances that your proof is correct so 17 that you can pass the benchmark

    **Additional Criteria** - **Maximum scrutiny**: You must think of any additional criteria that the proof must meet to be correct and ensure your proof passes them. This is for your own benefit, to maximize the chances that your proof is correct so 17 that you can pass the benc...

  35. [43]

    0" if the student introduces arbitrary numerical constraints or

    **Logical Rigor and External Assumption Check**: - **No Unauthorized Constraints**: Mark as "0" if the student introduces arbitrary numerical constraints or "safety margins" to simplify the proof (e.g., assumingk≥ 2, assumingϵis sufficiently small, or assuming sets are non-emp...

  36. [44]

    0" if the student generalizes a property of a subset to a larger set (e.g., applying a u-uniformity property defined for

    **Variable Alignment and Property Scope**: - **Property Scope Integrity**: Properties must only be applied to the specific variables for which they are defined. Mark as "0" if the student generalizes a property of a subset to a larger set (e.g., applying a u-uniformity propert...

  37. [45]

    mapping limits matching identical parameters constraints mapping

    **Semantic Integrity and Jargon Detection**: - **No Hallucinated Logic/Word Salad**: Mark as "0" if the student uses repetitive, nonsensical, or overly dense jargon to mask a lack of logical depth. The proof must be linguistically coherent. If a paragraph consists of technical...

  38. [46]

    0". - Do not provide any explanation, feedback, or additional text. Your response must be only

    **Quantitative and Limit Accuracy**: - **Derivation Accuracy**: Mark as "0" for any error in arithmetic, algebraic manipulation, or inequality direction. - **Boundary and Floor/Ceiling Precision**: Bounds must be exactly supported. For example, if a floor function⌊k −ϵ⌋is used...

  39. [47]

    Siu-Wing Cheng, Haoqiang Huang, Shuo Zhang.https://arxiv.org/abs/2503.12746

    Constant Approximation of Fréchet Distance in Strongly Subquadratic Time. Siu-Wing Cheng, Haoqiang Huang, Shuo Zhang.https://arxiv.org/abs/2503.12746

    arXiv

  40. [48]

    Padraig Condon, Alberto Espuny Díaz, António Girão, Daniela Kühn, Deryk Osthus.https://arxiv.org/abs/2007.02891

    Hamiltonicity of random subgraphs of the hypercube. Padraig Condon, Alberto Espuny Díaz, António Girão, Daniela Kühn, Deryk Osthus.https://arxiv.org/abs/2007.02891

    2007 arXiv

  41. [49]

    Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang.https://arxiv.org/abs/2310.02243

    Learning quantum Hamiltonians at any temperature in polynomial time. Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang.https://arxiv.org/abs/2310.02243

    arXiv

  42. [50]

    Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn.https://arxiv.org/abs/2509.22563

    Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade. Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn.https://arxiv.org/abs/2509.22563

    arXiv

  43. [51]

    Greg Bodwin, Michael Dinitz, Yasamin Nazari.https: //arxiv.org/abs/2109.08042

    Vertex Fault-Tolerant Emulators. Greg Bodwin, Michael Dinitz, Yasamin Nazari.https: //arxiv.org/abs/2109.08042

    arXiv

  44. [52]

    Daniel M

    Locally Sampleable Uniform Symmetric Distributions. Daniel M. Kane, Anthony Ostuni, Kewen Wu.https://arxiv.org/abs/2411.08183

    arXiv

  45. [53]

    Yanlin Chen, András Gilyén, Ronald de Wolf.https://arxiv.org/abs/2405.14765

    A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix. Yanlin Chen, András Gilyén, Ronald de Wolf.https://arxiv.org/abs/2405.14765

    arXiv

  46. [54]

    Yuchen He, Zichun Ye, Chihao Zhang.https://arxiv.org/abs/2405.19752

    Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits. Yuchen He, Zichun Ye, Chihao Zhang.https://arxiv.org/abs/2405.19752

    arXiv

  47. [55]

    Johan Håstad, Kilian Risse.https://arxiv.org/abs/2209.05839

    On bounded depth proofs for Tseitin formulas on the grid; revisited. Johan Håstad, Kilian Risse.https://arxiv.org/abs/2209.05839

  48. [56]

    Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi.https://arxiv.org/abs/2409.04786

    Subexponential Parameterized Algorithms for Hitting Subgraphs. Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi.https://arxiv.org/abs/2409.04786

    arXiv

  49. [57]

    John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen.https://arxiv.org/abs/2311.10681

    An efficient quantum parallel repetition theorem and applications. John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen.https://arxiv.org/abs/2311.10681

    arXiv

  50. [58]

    Cameron Seth.https://arxiv.org/abs/2503.21441

    A Tolerant Independent Set Tester. Cameron Seth.https://arxiv.org/abs/2503.21441

    arXiv

  51. [59]

    Edin Husić, Georg Loho, Ben Smith, László A

    On complete classes of valuated matroids. Edin Husić, Georg Loho, Ben Smith, László A. Végh.https://arxiv.org/abs/2107.06961 20

    arXiv

  52. [60]

    Wenyu Jin, Xiaorui Sun, Mikkel Thorup.https://arxiv.org/abs/2401.09700

    Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time. Wenyu Jin, Xiaorui Sun, Mikkel Thorup.https://arxiv.org/abs/2401.09700

    arXiv

  53. [61]

    Antonios Anto- niadis, Ruben Hoeksma, Kevin Schewior, Marc Uetz.https://arxiv.org/abs/2505.03349

    Stochastic scheduling with Bernoulli-type jobs through policy stratification. Antonios Anto- niadis, Ruben Hoeksma, Kevin Schewior, Marc Uetz.https://arxiv.org/abs/2505.03349

    arXiv

  54. [62]

    Maximilian Probst Gutenberg, Christian Wulff-Nilsen.https://arxiv.org/abs/2001.10809

    Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler. Maximilian Probst Gutenberg, Christian Wulff-Nilsen.https://arxiv.org/abs/2001.10809

    2001 arXiv

  55. [63]

    Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov.https://arxiv.org/abs/2411.14268

    Supercritical Tradeoffs for Monotone Circuits. Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov.https://arxiv.org/abs/2411.14268

    arXiv

  56. [64]

    Parikshit Gopalan, Roie Levin, Udi Wieder

    Finding Skewed Subcubes Under a Distribution. Parikshit Gopalan, Roie Levin, Udi Wieder. https://arxiv.org/abs/1911.07378

    1911 arXiv

  57. [65]

    Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya.https://arxiv.org/ abs/2111.02336

    An Improved Algorithm for Thek-Dyck Edit Distance Problem. Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya.https://arxiv.org/ abs/2111.02336

    arXiv

  58. [66]

    Gleb Kalachev, Pavel Panteleev.https://arxiv.org/abs/2501.01411

    Maximally Extendable Product Codes are Good Coboundary Expanders. Gleb Kalachev, Pavel Panteleev.https://arxiv.org/abs/2501.01411

  59. [67]

    Amir Abboud, Karl Bringmann, Nick Fischer.https://arxiv.org/abs/2211.07058

    Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. Amir Abboud, Karl Bringmann, Nick Fischer.https://arxiv.org/abs/2211.07058

    arXiv

  60. [68]

    Karl Bringmann, Egor Gorbachev.https://arxiv.org/abs/2404.04369

    A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends. Karl Bringmann, Egor Gorbachev.https://arxiv.org/abs/2404.04369

    arXiv

  61. [69]

    Hsin-Yuan Huang, John Preskill, Mehdi Soleimanifar.https://arxiv.org/abs/2404.07281

    Certifying almost all quantum states with few single-qubit measurements. Hsin-Yuan Huang, John Preskill, Mehdi Soleimanifar.https://arxiv.org/abs/2404.07281

    arXiv

  62. [70]

    Mikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen Zhang.https://arxiv.org/abs/2311.10631

    Minimum Star Partitions of Simple Polygons in Polynomial Time. Mikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen Zhang.https://arxiv.org/abs/2311.10631

  63. [71]

    Susanna F

    Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients. Susanna F. de Rezende, Aaron Potechin, Kilian Risse.https://arxiv.org/abs/2404.16722

    arXiv

  64. [72]

    Som- nath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf.https://arxiv.org/abs/2504.08063

    Deterministic factorization of constant-depth algebraic circuits in subexponential time. Som- nath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf.https://arxiv.org/abs/2504.08063

    arXiv

  65. [73]

    Miranda Christ, Mihalis Yannakakis.https://arxiv.org/abs/2212.00083

    The Smoothed Complexity of Policy Iteration for Markov Decision Processes. Miranda Christ, Mihalis Yannakakis.https://arxiv.org/abs/2212.00083

    arXiv

  66. [74]

    Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka.https://arxiv

    New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka.https://arxiv. org/abs/2311.09095

    arXiv

  67. [75]

    Kevin Pratt.https://arxiv.org/abs/ 2309.03878 21

    On generalized corners and matrix multiplication. Kevin Pratt.https://arxiv.org/abs/ 2309.03878 21

    arXiv

  68. [76]

    Arnold Filtser, Michael Kapralov, Mikhail Makarov.https://arxiv.org/abs/2211.11384

    Expander Decomposition in Dynamic Streams. Arnold Filtser, Michael Kapralov, Mikhail Makarov.https://arxiv.org/abs/2211.11384

    arXiv

  69. [77]

    Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, Sergei Vassilvitskii.https://arxiv.org/abs/2412.00717

    Data-Driven Solution Portfolios. Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, Sergei Vassilvitskii.https://arxiv.org/abs/2412.00717

    arXiv

  70. [78]

    Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, Maris Ozols.https://arxiv.org/abs/2211.11729

    Quantum majority vote. Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, Maris Ozols.https://arxiv.org/abs/2211.11729

    arXiv

  71. [79]

    Romain Bourneuf, Pierre Charbit, Stéphan Thomassé

    A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number. Romain Bourneuf, Pierre Charbit, Stéphan Thomassé. https: //arxiv.org/abs/2504.02992

    arXiv

  72. [80]

    Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu, Tamalika Mukherjee.https://arxiv.org/abs/2407.07262

    Differential privacy and Sublinear time are incompatible sometimes. Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu, Tamalika Mukherjee.https://arxiv.org/abs/2407.07262

    arXiv

  73. [81]

    Peter Davies-Peck.https://arxiv.org/abs/ 2502.11690

    On the Locality of the Lovász Local Lemma. Peter Davies-Peck.https://arxiv.org/abs/ 2502.11690

    arXiv

  74. [82]

    Sudatta Bhattacharya, Michal Koucký.https://arxiv.org/abs/2302.04475

    Locally consistent decomposition of strings with applications to edit distance sketching. Sudatta Bhattacharya, Michal Koucký.https://arxiv.org/abs/2302.04475

    arXiv

  75. [83]

    Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu.https://arxiv.org/abs/2111.09250

    Sum-of-Squares Lower Bounds for Sparse Independent Set. Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu.https://arxiv.org/abs/2111.09250

    arXiv

  76. [84]

    Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn

    Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k- Median. Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn. https://arxiv.org/abs/2207.05150

  77. [85]

    Mohsen Ghaffari, Christoph Grunau.https://arxiv.org/abs/2303.16043

    Faster Deterministic Distributed MIS and Approximate Matching. Mohsen Ghaffari, Christoph Grunau.https://arxiv.org/abs/2303.16043

    arXiv

  78. [86]

    Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler.https://arxiv.org/abs/2101.05549

    Spectral Clustering Oracles in Sublinear Time. Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler.https://arxiv.org/abs/2101.05549

    arXiv

  79. [87]

    Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan.https://arxiv.org/abs/2404.13446

    New Structures and Algorithms for Length-Constrained Expander Decompositions. Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan.https://arxiv.org/abs/2404.13446

    arXiv

  80. [88]

    Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, Prasad Tetali.https://arxiv.org/abs/2207.04318

    Determinant Maximization via Matroid Intersection Algorithms. Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, Prasad Tetali.https://arxiv.org/abs/2207.04318

    arXiv

  81. [89]

    Cameron Musco, Christopher Musco, David P

    Active Linear Regression forℓp Norms and Beyond. Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda.https://arxiv.org/abs/2111.04888

    arXiv

  82. [90]

    Sándor Kisfaludi-Bak, Jesper Nederlof, Karol Węgrzycki.https://arxiv.org/abs/2011.03778

    A Gap-ETH-Tight Approximation Scheme for Euclidean TSP. Sándor Kisfaludi-Bak, Jesper Nederlof, Karol Węgrzycki.https://arxiv.org/abs/2011.03778

    2011 arXiv

  83. [91]

    Henry Fleischmann, Surya Teja Gavva, Karthik C

    On Approximability of Steiner Tree inℓp-metrics. Henry Fleischmann, Surya Teja Gavva, Karthik C. S.https://arxiv.org/abs/2306.02189

    arXiv

  84. [92]

    Shashank Srivas- tava, Madhur Tulsiani.https://arxiv.org/abs/2504.20333 22

    List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. Shashank Srivas- tava, Madhur Tulsiani.https://arxiv.org/abs/2504.20333 22

    arXiv

  85. [93]

    Ivan Hu, Dieter van Melkebeek, Andrew Morgan.https://arxiv.org/abs/2211.12441

    Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees. Ivan Hu, Dieter van Melkebeek, Andrew Morgan.https://arxiv.org/abs/2211.12441

    arXiv

  86. [94]

    Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic

    Hop-Constrained Oblivious Routing. Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic. https://arxiv.org/abs/2011.10446

    2011 arXiv

  87. [95]

    Xiaolin Bu, Biaoshuai Tao.https://arxiv.org/abs/2407.13634

    Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness. Xiaolin Bu, Biaoshuai Tao.https://arxiv.org/abs/2407.13634

  88. [96]

    Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang.https://arxiv.org/abs/2510.20456

    Parallel(1 + ϵ)-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work. Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang.https://arxiv.org/abs/2510.20456

  89. [97]

    Amir Abboud, Ron Safier, Nathan Wallheimer.https: //arxiv.org/abs/2511.17224

    Triangle Detection in H-Free Graphs. Amir Abboud, Ron Safier, Nathan Wallheimer.https: //arxiv.org/abs/2511.17224

  90. [98]

    Benjamin Aram Berendsohn, László Kozma, Michal Opler.https://arxiv.org/abs/2310.04236

    Optimization with pattern-avoiding input. Benjamin Aram Berendsohn, László Kozma, Michal Opler.https://arxiv.org/abs/2310.04236

  91. [99]

    Vishesh Jain, Will Perkins, Ashwin Sah, Mehtaab Sawhney.https://arxiv.org/abs/2108.01161

    Approximate counting and sampling via local central limit theorems. Vishesh Jain, Will Perkins, Ashwin Sah, Mehtaab Sawhney.https://arxiv.org/abs/2108.01161

    arXiv

  92. [100]

    Elaine Shi, Hao Chung, Ke Wu.https://arxiv.org/abs/2209.14462

    What Can Cryptography Do For Decentralized Mechanism Design. Elaine Shi, Hao Chung, Ke Wu.https://arxiv.org/abs/2209.14462

    arXiv

  93. [101]

    Radu Curticapean.https://arxiv.org/ abs/2102.04340

    A full complexity dichotomy for immanant families. Radu Curticapean.https://arxiv.org/ abs/2102.04340

    arXiv

  94. [102]

    Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi.https://arxiv.org/abs/2304.06552

    Beyond the Quadratic Time Barrier for Network Unreliability. Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi.https://arxiv.org/abs/2304.06552

    arXiv

  95. [103]

    Michał Dereziński, Jiaming Yang.https://arxiv.org/abs/2312.08893

    Solving Dense Linear Systems Faster Than via Preconditioning. Michał Dereziński, Jiaming Yang.https://arxiv.org/abs/2312.08893

    arXiv

  96. [104]

    Eric Blais, Cameron Seth.https: //arxiv.org/abs/2308.03289

    Testing Graph Properties with the Container Method. Eric Blais, Cameron Seth.https: //arxiv.org/abs/2308.03289

  97. [105]

    Adam Karczmarz, Piotr Sankowski.https://arxiv.org/abs/2308.08870

    Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form. Adam Karczmarz, Piotr Sankowski.https://arxiv.org/abs/2308.08870

    arXiv

  98. [106]

    Maximilian Probst Gutenberg, Christian Wulff-Nilsen.https://arxiv.org/abs/2001.10801

    Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds. Maximilian Probst Gutenberg, Christian Wulff-Nilsen.https://arxiv.org/abs/2001.10801

    2001 arXiv

  99. [107]

    Gianluca Curzi, Anupam Das.https: //arxiv.org/abs/2211.16104

    Non-uniform complexity via non-wellfounded proofs. Gianluca Curzi, Anupam Das.https: //arxiv.org/abs/2211.16104

    arXiv

  100. [108]

    Merav Parter, Asaf Petruschka, Shay Sapir, Elad Tzalik.https://arxiv.org/abs/2410.07844

    Parks and Recreation: Color Fault-Tolerant Spanners Made Local. Merav Parter, Asaf Petruschka, Shay Sapir, Elad Tzalik.https://arxiv.org/abs/2410.07844

    arXiv

  101. [109]

    Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman.https://arxiv.org/abs/2207.10889 23

    Correlation Clustering with Sherali-Adams. Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman.https://arxiv.org/abs/2207.10889 23

    arXiv

  102. [110]

    Yunbum Kook, Matthew S

    Rényi-infinity constrained sampling withd3 membership queries. Yunbum Kook, Matthew S. Zhang.https://arxiv.org/abs/2407.12967

    arXiv

  103. [111]

    Julia Chuzhoy, Zihan Tan.https://arxiv.org/abs/2202.06827

    A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs. Julia Chuzhoy, Zihan Tan.https://arxiv.org/abs/2202.06827

    arXiv

  104. [112]

    Xi Chen, Anindya De, Chin Ho Lee, Rocco A

    Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha.https://arxiv.org/abs/2107. 11530

  105. [113]

    Igor Balla, Lianna Hambardzumyan, István Tomon.https://arxiv.org/abs/2506.23989

    Factorization norms and an inverse theorem for MaxCut. Igor Balla, Lianna Hambardzumyan, István Tomon.https://arxiv.org/abs/2506.23989

    arXiv

  106. [114]

    Julia Chuzhoy.https://arxiv.org/abs/2211.10556

    A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems. Julia Chuzhoy.https://arxiv.org/abs/2211.10556

    arXiv

  107. [115]

    Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha.https://arxiv.org/abs/ 2302.04229

    Weighted Edit Distance Computation: Strings, Trees and Dyck. Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha.https://arxiv.org/abs/ 2302.04229

    arXiv

  108. [116]

    Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao.https://arxiv.org/abs/ 2205.02168

    Separations in Proof Complexity and TFNP. Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao.https://arxiv.org/abs/ 2205.02168

    arXiv

  109. [117]

    Binghui Peng, Aviad Rubinstein

    Near Optimal Memory-Regret Tradeoff for Online Learning. Binghui Peng, Aviad Rubinstein. https://arxiv.org/abs/2303.01673

    arXiv

  110. [118]

    Moshe Babaioff, Uriel Feige.https:// arxiv.org/abs/2405.14575

    Share-Based Fairness for Arbitrary Entitlements. Moshe Babaioff, Uriel Feige.https:// arxiv.org/abs/2405.14575

    arXiv

  111. [119]

    Sumegha Garg, Madhu Sudan, Gabriel Wu

    Testing Tensor Products of Algebraic Codes. Sumegha Garg, Madhu Sudan, Gabriel Wu. https://arxiv.org/abs/2410.22606

  112. [120]

    Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim.https://arxiv.org/abs/2411.04418

    Fully Dynamic(∆ + 1)Coloring Against Adaptive Adversaries. Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim.https://arxiv.org/abs/2411.04418

    arXiv

  113. [121]

    Etienne Bamas, Sarah Morell, Lars Rohwedder

    The Submodular Santa Claus Problem. Etienne Bamas, Sarah Morell, Lars Rohwedder. https://arxiv.org/abs/2407.04824

    arXiv

  114. [122]

    Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang.https://arxiv.org/abs/2410.05240

    Vizing’s Theorem in Near-Linear Time. Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang.https://arxiv.org/abs/2410.05240

  115. [123]

    Itai Ashlagi, Jiale Chen, Mohammad Roghani, Amin Saberi

    Stable Matching with Interviews. Itai Ashlagi, Jiale Chen, Mohammad Roghani, Amin Saberi. https://arxiv.org/abs/2501.12503

    arXiv

  116. [124]

    James Bartusek, Zvika Brakerski, Vinod Vaikuntanathan.https://arxiv.org/abs/2401.10200

    Quantum State Obfuscation from Classical Oracles. James Bartusek, Zvika Brakerski, Vinod Vaikuntanathan.https://arxiv.org/abs/2401.10200

    arXiv

  117. [125]

    Sepehr Assadi, Gary Hoppenworth, Nicole Wein.https://arxiv.org/abs/2504.11256 24

    Covering Approximate Shortest Paths with DAGs. Sepehr Assadi, Gary Hoppenworth, Nicole Wein.https://arxiv.org/abs/2504.11256 24

    arXiv

  118. [126]

    Da Qi Chen, Lin An, Aidin Niaparast, R

    Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models. Da Qi Chen, Lin An, Aidin Niaparast, R. Ravi, Oleksandr Rudenko.https://arxiv.org/ abs/2111.05450

    arXiv

  119. [127]

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen.https://arxiv.org/abs/2111.08131

    Quantum soundness of testing tensor codes. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen.https://arxiv.org/abs/2111.08131

    arXiv

  120. [128]

    Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V

    The Message Complexity of Distributed Graph Optimization. Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Peter Robinson.https://arxiv.org/abs/2311. 14811

  121. [129]

    Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D Ellis Hershkowitz, Rajmohan Rajaraman

    One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree. Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D Ellis Hershkowitz, Rajmohan Rajaraman. https://arxiv.org/abs/2308.01199

    arXiv

  122. [130]

    Jiangqi Dai, Mohsen Ghaffari, Julian Portmann.https://arxiv.org/abs/2512.18416

    Constant Approximation of Arboricity in Near-Optimal Sublinear Time. Jiangqi Dai, Mohsen Ghaffari, Julian Portmann.https://arxiv.org/abs/2512.18416

  123. [131]

    Matthias Bentert, Fedor V

    Packing Short Cycles. Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, William Lochet, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Kirill Simonov.https: //arxiv.org/abs/2410.18878

    arXiv

  124. [132]

    Princewill Okoroafor, Robert Kleinberg, Michael P

    Near-Optimal Algorithms for Omniprediction. Princewill Okoroafor, Robert Kleinberg, Michael P. Kim.https://arxiv.org/abs/2501.17205

  125. [133]

    Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam.https://arxiv.org/abs/ 2201.13128

    Deletion Robust Submodular Maximization over Matroids. Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam.https://arxiv.org/abs/ 2201.13128

    arXiv

  126. [134]

    Mohsen Ghaffari, Christoph Grunau.https://arxiv.org/abs/2504.15700

    Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set. Mohsen Ghaffari, Christoph Grunau.https://arxiv.org/abs/2504.15700

    arXiv

  127. [135]

    Greg Bodwin, Gary Hoppenworth.https://arxiv.org/abs/2207.11832

    New Additive Spanner Lower Bounds by an Unlayered Obstacle Product. Greg Bodwin, Gary Hoppenworth.https://arxiv.org/abs/2207.11832

    arXiv

  128. [136]

    Alexandr Andoni, Hengjie Zhang.https://arxiv.org/abs/2310.05315

    Sub-quadratic(1 + ϵ)-approximate Euclidean Spanners, with Applications. Alexandr Andoni, Hengjie Zhang.https://arxiv.org/abs/2310.05315

    arXiv

  129. [137]

    Karl Bringmann.https://arxiv.org/ abs/2308.03075

    Knapsack with Small Items in Near-Quadratic Time. Karl Bringmann.https://arxiv.org/ abs/2308.03075

    arXiv

  130. [138]

    Hadley Black, Eric Blais, Nathaniel Harms.https://arxiv.org/abs/2305.03194

    Testing and Learning Convex Sets in the Ternary Hypercube. Hadley Black, Eric Blais, Nathaniel Harms.https://arxiv.org/abs/2305.03194

    arXiv

  131. [139]

    Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta.https://arxiv.org/abs/2504.14729

    Rank Bounds and PIT forΣ3ΠΣΠd circuits via a non-linear Edelstein-Kelly theorem. Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta.https://arxiv.org/abs/2504.14729

    arXiv

  132. [140]

    Nick Gravin, Zhiqi Wang.https://arxiv.org/abs/2409.08547

    On Robustness tok-wise Independence of Optimal Bayesian Mechanisms. Nick Gravin, Zhiqi Wang.https://arxiv.org/abs/2409.08547

    arXiv

  133. [141]

    Julia Chuzhoy, Merav Parter.https://arxiv.org/abs/2601.20718 25

    Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition. Julia Chuzhoy, Merav Parter.https://arxiv.org/abs/2601.20718 25

  134. [142]

    Robbie King, David Gosset, Robin Kothari, Ryan Babbush

    Triply efficient shadow tomography. Robbie King, David Gosset, Robin Kothari, Ryan Babbush. https://arxiv.org/abs/2404.19211

    arXiv

  135. [143]

    Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, David X

    Fast Mixing in Sparse Random Ising Models. Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, David X. Wu.https://arxiv.org/abs/2405.06616

    arXiv

  136. [144]

    Tillmann Miltzow, Reinier F

    On Classifying Continuous Constraint Satisfaction Problems. Tillmann Miltzow, Reinier F. Schmiermann.https://arxiv.org/abs/2106.02397

    arXiv

  137. [145]

    Vladimir Lysikov, Michael Walter.https://arxiv.org/abs/ 2411.04639

    Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness. Vladimir Lysikov, Michael Walter.https://arxiv.org/abs/ 2411.04639

  138. [146]

    Dor Minzer, Kai Zhe Zheng

    Near Optimal Alphabet-Soundness Tradeoff PCPs. Dor Minzer, Kai Zhe Zheng. https: //arxiv.org/abs/2404.07441

    arXiv

  139. [147]

    George Giakkoupis, Marcos Kiwi, Dimitrios Los.https://arxiv.org/abs/2404.08162

    Naively Sorting Evolving Data is Optimal and Robust. George Giakkoupis, Marcos Kiwi, Dimitrios Los.https://arxiv.org/abs/2404.08162

    arXiv

  140. [148]

    Binghui Peng, Aviad Rubinstein.https://arxiv.org/abs/2310.19647

    Fast swap regret minimization and applications to approximate correlated equilibria. Binghui Peng, Aviad Rubinstein.https://arxiv.org/abs/2310.19647

    arXiv

  141. [149]

    Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan.https://arxiv.org/ abs/2405.15084

    Efficient Certificates of Anti-Concentration Beyond Gaussians. Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan.https://arxiv.org/ abs/2405.15084

    arXiv

  142. [150]

    Neekon Vafa, Vinod Vaikun- tanathan.https://arxiv.org/abs/2501.16517

    Symmetric Perceptrons, Number Partitioning and Lattices. Neekon Vafa, Vinod Vaikun- tanathan.https://arxiv.org/abs/2501.16517

    arXiv

  143. [151]

    Noel Arteche, Albert Atserias, Susanna F

    The Proof Analysis Problem. Noel Arteche, Albert Atserias, Susanna F. de Rezende, Erfan Khaniki.https://arxiv.org/abs/2506.16956

    arXiv

  144. [152]

    Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos.https://arxiv.org/abs/2202.08066

    Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime. Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos.https://arxiv.org/abs/2202.08066

    arXiv

  145. [153]

    Alexander A

    The Communication Complexity of Approximating Matrix Rank. Alexander A. Sherstov, Andrey A. Storozhenko.https://arxiv.org/abs/2410.20094

    arXiv

  146. [154]

    Mohsen Ghaffari, Christoph Grunau.https://arxiv.org/abs/2311.13771

    Work-EfficientParallelDerandomizationII:OptimalConcentrationsviaBootstrapping. Mohsen Ghaffari, Christoph Grunau.https://arxiv.org/abs/2311.13771

    arXiv

  147. [155]

    Elfarouk Harb.https://arxiv

    New Prophet Inequalities via Poissonization and Sharding. Elfarouk Harb.https://arxiv. org/abs/2307.00971

    arXiv

  148. [156]

    Arnold Filtser, Hung Le

    Low Treewidth Embeddings of Planar and Minor-Free Metrics. Arnold Filtser, Hung Le. https://arxiv.org/abs/2203.15627

    arXiv

  149. [157]

    Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir.https://arxiv.org/ abs/2204.10465 26

    Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond. Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir.https://arxiv.org/ abs/2204.10465 26

    arXiv

  150. [158]

    Anders Aamand, Jakob Bæk Tejs Knudsen, Mikkel Thorup.https://arxiv.org/abs/2104.05093

    Load Balancing with Dynamic Set of Balls and Bins. Anders Aamand, Jakob Bæk Tejs Knudsen, Mikkel Thorup.https://arxiv.org/abs/2104.05093

    arXiv

  151. [159]

    Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah.https://arxiv.org/abs/2111.03158

    Pricing Query Complexity of Revenue Maximization. Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah.https://arxiv.org/abs/2111.03158

    arXiv

  152. [160]

    Siu-Wing Cheng, Haoqiang Huang.https://arxiv.org/abs/2207.07809

    Curve Simplification and Clustering under Fréchet Distance. Siu-Wing Cheng, Haoqiang Huang.https://arxiv.org/abs/2207.07809

    arXiv

  153. [161]

    Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski.https://arxiv.org/abs/2305.15738

    Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski.https://arxiv.org/abs/2305.15738

  154. [162]

    John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, Henry Yuen.https://arxiv.org/abs/ 2306.13073

    Unitary Complexity and the Uhlmann Transformation Problem. John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, Henry Yuen.https://arxiv.org/abs/ 2306.13073

    arXiv

  155. [163]

    Moses Charikar, Spencer Compton, Chirag Pabbaraju.https://arxiv.org/abs/ 2312.02435

    Embedding Probability Distributions into Low Dimensionalℓ1: Tree Ising Models via Truncated Metrics. Moses Charikar, Spencer Compton, Chirag Pabbaraju.https://arxiv.org/abs/ 2312.02435

    arXiv

  156. [164]

    Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang.https://arxiv.org/abs/2210.12495

    Quartic Samples Suffice for Fourier Interpolation. Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang.https://arxiv.org/abs/2210.12495

    arXiv

  157. [165]

    Andrew Zhao.https: //arxiv.org/abs/2410.21635

    Learning the structure of any Hamiltonian from minimal assumptions. Andrew Zhao.https: //arxiv.org/abs/2410.21635

    arXiv

  158. [166]

    Matan Levi, Jonathan Mosheiff, Nikhil Shagrithaya.https://arxiv.org/abs/2406.02238

    Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent. Matan Levi, Jonathan Mosheiff, Nikhil Shagrithaya.https://arxiv.org/abs/2406.02238

  159. [167]

    Zongbo Bao, Philippe van Dordrecht, Jonas Helsen.https://arxiv.org/abs/2410.21811

    Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation. Zongbo Bao, Philippe van Dordrecht, Jonas Helsen.https://arxiv.org/abs/2410.21811

    arXiv

  160. [168]

    Evangelos Kosinas.https: //arxiv.org/abs/2311.04865

    Computing the5-Edge-Connected Components in Linear Time. Evangelos Kosinas.https: //arxiv.org/abs/2311.04865

    arXiv

  161. [169]

    Yumou Fei, Dor Minzer, Shuo Wang.https://arxiv.org/abs/2503.23404

    Multi-Pass Streaming Lower Bounds for Approximating Max-Cut. Yumou Fei, Dor Minzer, Shuo Wang.https://arxiv.org/abs/2503.23404

    arXiv

  162. [170]

    Benjamin Rossman.https://arxiv.org/abs/2406.16015

    Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication. Benjamin Rossman.https://arxiv.org/abs/2406.16015

    arXiv

  163. [171]

    Talya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld.https://arxiv.org/abs/2503.09810

    Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time. Talya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld.https://arxiv.org/abs/2503.09810

    arXiv

  164. [172]

    Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun.https://arxiv.org/abs/2401.12604

    On Pigeonhole Principles and Ramsey in TFNP. Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun.https://arxiv.org/abs/2401.12604

    arXiv

  165. [173]

    Jun-Ting Hsieh, Pravesh K

    New SDP Roundings and Certifiable Approximation for Cubic Optimization. Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan.https://arxiv.org/abs/2310.00393 27

    arXiv

  166. [174]

    Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu.https: //arxiv.org/abs/2307.15871

    Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques. Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu.https: //arxiv.org/abs/2307.15871

    arXiv

  167. [175]

    Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla.https://arxiv.org/ abs/2111.06308

    Online Discrepancy with Recourse for Vectors and Graphs. Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla.https://arxiv.org/ abs/2111.06308

    arXiv

  168. [176]

    Max Gläser, Marc E

    Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpo- lation. Max Gläser, Marc E. Pfetsch.https://arxiv.org/abs/2308.04320

    arXiv

  169. [177]

    Hiroshi Hirai, Keiya Sakabe.https://arxiv.org/abs/2404.09746

    Gradient descent for unbounded convex functions on Hadamard manifolds and its applications to scaling problems. Hiroshi Hirai, Keiya Sakabe.https://arxiv.org/abs/2404.09746

  170. [178]

    Omar Fawzi, Alexander Müller-Hermes, Ala Shayeghi.https://arxiv.org/abs/2202.00119

    A lower bound on the space overhead of fault-tolerant quantum computation. Omar Fawzi, Alexander Müller-Hermes, Ala Shayeghi.https://arxiv.org/abs/2202.00119

    arXiv

  171. [179]

    Karl Bringmann, Nick Fischer, Vasileios Nakos

    Beating Bellman’s Algorithm for Subset Sum. Karl Bringmann, Nick Fischer, Vasileios Nakos. https://arxiv.org/abs/2410.21942

    arXiv

  172. [180]

    Jiashuo Jiang, Will Ma, Jiawei Zhang.https://arxiv.org/abs/2107.02058

    Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack. Jiashuo Jiang, Will Ma, Jiawei Zhang.https://arxiv.org/abs/2107.02058

    arXiv

  173. [181]

    Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay.https://arxiv.org/abs/2208.13920

    Fitting Metrics and Ultrametrics with Minimum Disagreements. Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay.https://arxiv.org/abs/2208.13920

    arXiv

  174. [182]

    Sujoy Bhore, Timothy M

    Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching. Sujoy Bhore, Timothy M. Chan. https://arxiv.org/abs/2407.20659

    arXiv

  175. [183]

    Sukanya Pandey, Erik Jan van Leeuwen

    Planar Multiway Cut with Terminals on Few Faces. Sukanya Pandey, Erik Jan van Leeuwen. https://arxiv.org/abs/2506.23399

    arXiv

  176. [184]

    Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K

    Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan.https: //arxiv.org/abs/2407.21005

    arXiv

  177. [185]

    Joshua Lau, Angus Ritossa.https://arxiv.org/abs/2101.02003

    Algorithms and Hardness for Multidimensional Range Updates and Queries. Joshua Lau, Angus Ritossa.https://arxiv.org/abs/2101.02003

    arXiv

  178. [186]

    Arkadev Chattopadhyay, Nikhil S

    Lifting to Parity Decision Trees Via Stifling. Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif.https://arxiv.org/abs/2211.17214

    arXiv

  179. [187]

    Marvin Künnemann, André Nusser.https://arxiv

    Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. Marvin Künnemann, André Nusser.https://arxiv. org/abs/2111.02544

    arXiv

  180. [188]

    Yaowei Long, Thatchaphol Saranurak.https://arxiv.org/abs/2205.03930

    Near-Optimal Deterministic Vertex-Failure Connectivity Oracles. Yaowei Long, Thatchaphol Saranurak.https://arxiv.org/abs/2205.03930

    arXiv

  181. [189]

    Alexander Lindermayr, Nicole Megow, Bertrand Simon.https://arxiv.org/abs/2103.01640 28

    Double Coverage with Machine-Learned Advice. Alexander Lindermayr, Nicole Megow, Bertrand Simon.https://arxiv.org/abs/2103.01640 28

    arXiv

  182. [190]

    Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé.https://arxiv.org/abs/1907.04585

    Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé.https://arxiv.org/abs/1907.04585

    1907 arXiv

  183. [191]

    Pan Peng, Yuichi Yoshida.https://arxiv.org/abs/2210.12601

    Sublinear-Time Algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on Expanders. Pan Peng, Yuichi Yoshida.https://arxiv.org/abs/2210.12601

    arXiv

  184. [192]

    Alireza AmaniHamedani, Ali Aouad, Amin Saberi.https://arxiv.org/abs/2501.08775

    Adaptive Approximation Schemes for Matching Queues. Alireza AmaniHamedani, Ali Aouad, Amin Saberi.https://arxiv.org/abs/2501.08775

    arXiv

  185. [193]

    Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi.https://arxiv.org/abs/2506.20017

    All-Pairs Shortest Paths with Few Weights per Node. Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi.https://arxiv.org/abs/2506.20017

    arXiv

  186. [194]

    Eric Blais, Cameron Seth.https://arxiv.org/abs/2403.18777

    New Graph and Hypergraph Container Lemmas with Applications in Property Testing. Eric Blais, Cameron Seth.https://arxiv.org/abs/2403.18777

    arXiv

  187. [195]

    Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell.https://arxiv.org/abs/2303.12921

    Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell.https://arxiv.org/abs/2303.12921

    arXiv

  188. [196]

    Eduard Eiben, Tomohiro Koana, Magnus Wahlström.https://arxiv

    Determinantal Sieving. Eduard Eiben, Tomohiro Koana, Magnus Wahlström.https://arxiv. org/abs/2304.02091

  189. [197]

    Moses Ganardi, Paweł Gawrychowski.https://arxiv.org/abs/2111.05016

    Pattern Matching on Grammar-Compressed Strings in Linear Time. Moses Ganardi, Paweł Gawrychowski.https://arxiv.org/abs/2111.05016

    arXiv

  190. [198]

    Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov.https://arxiv.org/abs/2304.02555

    Top-Down Lower Bounds for Depth-Four Circuits. Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov.https://arxiv.org/abs/2304.02555

    arXiv

  191. [199]

    Julia Chuzhoy, Sanjeev Khanna.https://arxiv.org/abs/2405.20861

    Maximum Bipartite Matching inn2+o(1) Time via a Combinatorial Algorithm. Julia Chuzhoy, Sanjeev Khanna.https://arxiv.org/abs/2405.20861

    arXiv

  192. [200]

    Michał Włodarczyk, Meirav Zehavi.https: //arxiv.org/abs/2307.06792

    Planar Disjoint Paths, Treewidth, and Kernels. Michał Włodarczyk, Meirav Zehavi.https: //arxiv.org/abs/2307.06792

    arXiv

  193. [201]

    SoheilBehnezhad, Mohammad Roghani, Aviad Rubinstein.https://arxiv.org/abs/2311.09359

    LocalComputationAlgorithmsforMaximumMatching: NewLowerBounds. SoheilBehnezhad, Mohammad Roghani, Aviad Rubinstein.https://arxiv.org/abs/2311.09359

    arXiv

  194. [202]

    Single-Sample Prophet Inequalities via Greedy-Ordered Selection. Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Pa- padigenopoulos, Emmanouil Pountourakis, Rebecca Reiffenhäuser.https://arxiv.org/abs/ 2111.03174

    arXiv

  195. [203]

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu.https://arxiv.org/abs/2310.12051

    Simpler and Higher Lower Bounds for Shortcut Sets. Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu.https://arxiv.org/abs/2310.12051

    arXiv

  196. [204]

    Dean Doron, João Ribeiro.https: //arxiv.org/abs/2411.07473

    Nearly-Linear Time Seeded Extractors with Short Seeds. Dean Doron, João Ribeiro.https: //arxiv.org/abs/2411.07473

  197. [205]

    Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz.https: //arxiv.org/abs/2104.06576 29

    Dimension-Preserving Reductions Between SVP and CVP in Differentp-Norms. Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz.https: //arxiv.org/abs/2104.06576 29

    arXiv

  198. [206]

    Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira, Igor Zablotchi.https://arxiv.org/abs/2402.10059

    Partial Synchrony for Free? New Upper Bounds for Byzantine Agreement. Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira, Igor Zablotchi.https://arxiv.org/abs/2402.10059

    arXiv

  199. [207]

    Yichuan Wang

    Tight Streaming Lower Bounds for Deterministic Approximate Counting. Yichuan Wang. https://arxiv.org/abs/2406.12149

    arXiv

  200. [208]

    Nick Fischer.https://arxiv.org/abs/2410

    Sumsets, 3SUM, Subset Sum: Now for Real!. Nick Fischer.https://arxiv.org/abs/2410. 21953

  201. [209]

    Zeyu Guo, Chaoping Xing, Chen Yuan, Zihan Zhang.https://arxiv.org/abs/2404.13230

    Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric. Zeyu Guo, Chaoping Xing, Chen Yuan, Zihan Zhang.https://arxiv.org/abs/2404.13230

    arXiv

  202. [210]

    Johannes Carmesin, Jan Kurkofka.https: //arxiv.org/abs/2304.00945

    Canonical Decompositions of 3-Connected Graphs. Johannes Carmesin, Jan Kurkofka.https: //arxiv.org/abs/2304.00945

    arXiv

  203. [211]

    Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, Linda Kleist.https://arxiv.org/abs/2112.03791

    Online Sorting and Translational Packing of Convex Polygons. Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, Linda Kleist.https://arxiv.org/abs/2112.03791

    arXiv

  204. [212]

    Jérôme Leroux.https: //arxiv.org/abs/2104.12695

    The Reachability Problem for Petri Nets is Not Primitive Recursive. Jérôme Leroux.https: //arxiv.org/abs/2104.12695

    arXiv

  205. [213]

    Arnaud Casteigts, Michael Raskin, Malte Renken, Viktor Zamaraev.https://arxiv.org/abs/2011.03738

    Sharp Thresholds in Random Simple Temporal Graphs. Arnaud Casteigts, Michael Raskin, Malte Renken, Viktor Zamaraev.https://arxiv.org/abs/2011.03738

    2011 arXiv

  206. [214]

    Shir Peleg, Amir Shpilka, Ben Lee Volk

    Tensor Reconstruction Beyond Constant Rank. Shir Peleg, Amir Shpilka, Ben Lee Volk. https://arxiv.org/abs/2209.04177

    arXiv

  207. [215]

    Maximilian Gorsky, Michał T

    Polynomial Bounds for the Graph Minor Structure Theorem. Maximilian Gorsky, Michał T. Seweryn, Sebastian Wiederrecht.https://arxiv.org/abs/2504.02532

    arXiv

  208. [216]

    Barak Nehoran, Mark Zhandry.https://arxiv.org/abs/2302.01858

    A Computational Separation Between Quantum No-cloning and No-telegraphing. Barak Nehoran, Mark Zhandry.https://arxiv.org/abs/2302.01858

    arXiv

  209. [217]

    Yotam Dikstein, Irit Dinur.https://arxiv.org/abs/2312.15325

    Swap cosystolic expansion. Yotam Dikstein, Irit Dinur.https://arxiv.org/abs/2312.15325

    arXiv

  210. [218]

    Andrea Coladangelo, Sam Gunn

    How to Use Quantum Indistinguishability Obfuscation. Andrea Coladangelo, Sam Gunn. https://arxiv.org/abs/2311.07794

    arXiv

  211. [219]

    Yu Chen, Zihan Tan.https://arxiv.org/abs/ 2310.07857

    On(1 + ε)-Approximate Flow Sparsifiers. Yu Chen, Zihan Tan.https://arxiv.org/abs/ 2310.07857

    arXiv

  212. [220]

    Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen.https://arxiv

    The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen.https://arxiv. org/abs/2311.10204

    arXiv

  213. [221]

    Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion. Bart M. P. Jansen, Michał Włodarczyk.https://arxiv.org/abs/2202.02174

    arXiv

  214. [222]

    Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck.https://arxiv.org/ abs/2408.10014 30

    Improved Distance (Sensitivity) Oracles with Subquadratic Space. Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck.https://arxiv.org/ abs/2408.10014 30

    arXiv

  215. [223]

    Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer.https://arxiv.org/abs/2410.18661

    Recognizing Sumsets is NP-Complete. Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer.https://arxiv.org/abs/2410.18661

    arXiv

  216. [224]

    Andreas Emil Feldmann, Arnold Filtser

    Highway Dimension: a Metric View. Andreas Emil Feldmann, Arnold Filtser. https: //arxiv.org/abs/2412.20490

  217. [225]

    Even-hole-free Graphs

    Tree Independence Number IV. Even-hole-free Graphs. Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl.https://arxiv.org/abs/2407.08927

    arXiv

  218. [226]

    Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick.https://arxiv.org/abs/2206.07750

    Good Quantum LDPC Codes with Linear Time Decoders. Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick.https://arxiv.org/abs/2206.07750

    arXiv

  219. [227]

    Shimon Kogan, Merav Parter.https://arxiv.org/abs/2211.06920

    Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets. Shimon Kogan, Merav Parter.https://arxiv.org/abs/2211.06920

    arXiv

  220. [228]

    Bernhard Haeupler, D Ellis Hershkowitz, Thatchaphol Saranurak.https://arxiv.org/abs/ 2111.01422

    Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast. Bernhard Haeupler, D Ellis Hershkowitz, Thatchaphol Saranurak.https://arxiv.org/abs/ 2111.01422

    arXiv

  221. [229]

    Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis.https://arxiv.org/abs/2107.05746

    Computational Hardness of the Hylland-Zeckhauser Scheme. Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis.https://arxiv.org/abs/2107.05746

    arXiv

  222. [230]

    Hannaneh Akrami, Jugal Garg

    Breaking the3 /4Barrier for Approximate Maximin Share. Hannaneh Akrami, Jugal Garg. https://arxiv.org/abs/2307.07304

    arXiv

  223. [231]

    Nikhil Kumar, Chaitanya Swamy

    Almost Tight Additive Guarantees fork-Edge-Connectivity. Nikhil Kumar, Chaitanya Swamy. https://arxiv.org/abs/2506.20906

  224. [232]

    Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad.https://arxiv.org/abs/2411.03121

    Fully Dynamick-Median with Near-Optimal Update Time and Recourse. Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad.https://arxiv.org/abs/2411.03121

    arXiv

  225. [233]

    Stefan Göller, Nathan Grosshans

    The AC0-Complexity Of Visibly Pushdown Languages. Stefan Göller, Nathan Grosshans. https://arxiv.org/abs/2302.13116

    arXiv

  226. [234]

    Eric Price, Zhiyang Xun.https:// arxiv.org/abs/2408.10332

    Spectral Guarantees for Adversarial Streaming PCA. Eric Price, Zhiyang Xun.https:// arxiv.org/abs/2408.10332

    arXiv

  227. [235]

    Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg.https://arxiv.org/abs/2110.11712

    Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier. Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg.https://arxiv.org/abs/2110.11712

    arXiv

  228. [236]

    Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya.https://arxiv.org/abs/2106.06037 31

    Small space and streaming pattern matching with k edits. Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya.https://arxiv.org/abs/2106.06037 31

    arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.