Algorithms and proofs in combinatorial optimization, number theory, algebraic complexity, dynamic graphs, and sparsification. Each problem page gives the theorem, complexity, randomness, dependencies, and verification evidence.
58 problem families · 19 supporting results · Proof index · Review and verification · Citation
Selected deterministic algorithmic results, with conditional premises stated explicitly. The linked problem pages give the full statements, proof dependencies, executable coverage and review status.
Deterministic exact maximum matching in general graphs.
Here m_s counts distinct nonloop edge pairs. The proof supplies the uniform cycle-search construction and names its published prerequisites. A separate executable solver returns independently verifiable optimality certificates.
Exact decision and indexed witness.
Exact rational exponent on the card.
For n integers of total bit length L, including an indexed witness. The finite startup constant C is input-independent. The complete compiler proof and exact continuous certificates support the improved third-lookup exponent.
Deterministic black-box identity testing with unknown order and unknown invertible affine coordinates, in every characteristic.
Here K(w)=2^{O(w^2)}, the full finite direction-grid minimum is displayed. Arbitrary local ranks and entry degrees; known scalar total degree D and extension-field oracle access when needed. Polynomial query count for each fixed width, with a width-dependent exponent. Complete internally reconstructed proof; external peer review and priority certification are not claimed.
Complete prime factorization of every positive binary integer, assuming the stated Boolean tensor-contraction theorem.
n=bit_length(N). The external succinct Boolean tensor-contraction theorem is an explicit accepted premise, checked against its literal ring and entry interface. Uniform deterministic bit operations and polynomial space; at most one contraction for complete recovery. Distinct precision/recovery tradeoffs are proved on the card. This is subexponential, rather than polynomial, in input bit length; no practical or priority claim.
Categories follow the selected-result topics, then related methods and applications. Selected families lead each category; other titles are alphabetized. Each link opens its statement, proof and dependencies. Computational models and randomness contracts explain how to compare bounds.
- Deterministic general-graph maximum matching
- Degree-constrained subgraphs
- Dynamic minimum spanning forest
- Dynamic spanners
- Fully dynamic APSP
- Incremental directed SSSP
- Incremental strongly connected components
- Static and threshold min-cost flow
- Strong forests and Gomory–Hu trees
- Deterministic PIT for fixed-width affine ROABP orbits
- Integral ordered crossing circuits
- Uniform ordered subset contraction and rectangular permanent
- Boolean linear optimization compiler
- Colored and vertex-failure graph certificates
- Flow, matching and price sensitivity
- Matroid and submodular failure summaries
- Persistent-homology failure certificates
- Resource-constrained packing summaries
- Single-failure optimum preservers
- Correlated spectral, regression and seminorm summaries
- Exact-separation and non-Fano boundaries
- Finite groups, affine constraints and metrics
- Label and whole-block cut sparsification
- Pauli, qudit and stabilizer blocks
- Self-concordant cone sparsification
- Arbitrary-value allocation scheme
- Explicit-item matroid union
- Intrinsic two-value allocation
- Intrinsic values near factor two
- One-value allocation
- Recipient polymatroids
- Recipient-matroid configuration
- Unrelated values with a joint role
- Unrelated-value additive allocation
- Whole-ground selection and transfers
- Flow with shared setup budget
- Robust bounded-width certificates
- Robust selected flow
- Robust unrelated allocation
- Selected concurrent flow
- Two-scenario hardness
- Width-two robust unit allocation
- Activated-machine scheduling
- Arbitrary-processing scheme
- Commitment scheduling
- Many-size workload scheduling
- Per-machine two-time scheduling
- Processing-bucket tradeoff
- Six-profile scheduling
- Two-size scheduling
- Allocation and scheduling barriers
- Hypergraph matching and expander routing
- Independent transversals
The complete index also lists 19 supporting algorithms, structural theorems, and scoped lower bounds. Shared manuscripts collect reusable proofs and backend interfaces.
Within each problem: README.md → proof.md → sources.md → verify/README.md. The review registry distinguishes manuscript review from executable checks and identifies their exact scope.
python3 tools/check_repository.pySee Contributing for the full verification mode and maintenance conventions. No external peer review or proof-assistant verification is claimed.
icekylinx and GPT-6 Astra Pro. Algorithm Frontier (2026). Cite the relevant problem path and commit; the citation protocol and import provenance retain the applicable licenses and notices.