[BJWC2018] Longest Increasing Subsequence

The question

Can the source-listed reference complexity O(n × 2^n) or O(n p(n)) be substantially improved?

Algorithmic frontier

Reference frontier: $\mathcal{O}\!\left(n \times 2^{n}\right)\;\text{or}\;\mathcal{O}\!\left(n p(n)\right)$
Latest reported AI result: $\mathcal{O}\!\left(n^{23/12} \log^{2} n\right)$

Normalized growth proxy · not benchmark data

This compares source-reported bounds; it is not a correctness or novelty finding.

Results

2026-09-12

Claimed result: $\mathcal{O}\!\left(n^{23/12} \log^{2} n\right)$

AI / model: ChatGPT

Reported method

The linked transcript first turns the expected LIS length into a generating-function recurrence tied to Gessel's determinant, giving O(n^3) and O(n^2 log n); for large LIS bounds it compresses the state into a finite linear system via a sigma-Painleve III identity, then rewrites that as a degree-1 matrix recurrence and uses a product tree with fast multipoint evaluation to skip most intermediate coefficients, claiming O(n^(23/12) log^2 n). This is the source's account; P02 did not check correctness.

Verification

Source: Source reviewed
Theory: Theory not checked
Implementation: Theory only · code pending
Prior art: Prior art not reviewed

The result page was opened and compared with the collection claim. Legacy audit state: audited_public.

The result link is a ChatGPT share page and was read in full. Only the O(n^3) variant is present as inline code; the claimed O(n^(23/12) log^2 n) implementation is offered solely through dead sandbox:/mnt/data/ attachment links, so implementation status stays theory-only. The source itself reports local cross-checks and explicitly disclaims any online-judge submission.