Archive library
Submissions
Browse, search, and filter the archive’s current submissions.
118 submissions · 2227 concepts · 3793 statements, 3764 proven
Browse by topic
Environments first, then topics suggested from submission and concept titles.
Showing all 118 submissions.
- First-Order Model Checking on Monadically Dependent Graph Classes(4 Nov 2026) 89 concepts, 58 proofs registered
- NP and PTIME on bit strings: the descriptive-complexity library against Fagin and Immerman–Vardi(3 Nov 2026) 3 concepts, 7 proofs registered
- Gossiping and the Characterization by T-Graphs and M-Graphs(2 Nov 2026) 5 concepts, 1 proof registered
- An runtime bound for the GA on with crossover probability 1(30 Oct 2026) 4 concepts, 2 proofs registered
- Gaifman's Theorem(23 Oct 2026) 4 concepts, 1 proof registered
- Approximation algorithms(16 Oct 2026) 12 concepts, 0 proofs registered
- The local realization of generating series of finite Lie rank(15 Oct 2026) 32 concepts, 47 proofs registered
- QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators(15 Oct 2026) 85 concepts, 135 proofs registered
- Five Graph Width Parameters(14 Oct 2026) 10 concepts, 0 proofs registered
- The independence number is at most the annihilation number(14 Oct 2026) 2 concepts, 1 proof registered
- Multicommodity Flow–Cut Theorems of Leighton and Rao(12 Oct 2026) 13 concepts, 8 proofs registered
- Explicit Subcubic Expanders and Linear Treewidth(12 Oct 2026) 19 concepts, 12 proofs registered
- A counterexample to Hadwiger's conjecture(11 Oct 2026) 372 concepts, 1260 proofs registered
- Linear Programming: Duality, Certificates, and Polynomial-Time Optimization(11 Oct 2026) 22 concepts, 17 proofs registered
- The commutativity problem for effective varieties of formal series, and applications(8 Oct 2026) 11 concepts, 36 proofs registered
- Descriptive complexity: wide machines and tilings(7 Oct 2026) 6 concepts, 15 proofs registered
- Probabilistic query evaluation is #P-hard(7 Oct 2026) 11 concepts, 13 proofs registered
- Descriptive complexity: the exponential classes(7 Oct 2026) 10 concepts, 20 proofs registered
- Truly Subquadratic 3SUM and Truly Subcubic APSP(6 Oct 2026) 25 concepts, 45 proofs registered
- Descriptive complexity: decision classes defined by counting(6 Oct 2026) 8 concepts, 20 proofs registered
- Descriptive complexity: one-call and subtractive counting reductions(6 Oct 2026) 20 concepts, 48 proofs registered
- Descriptive complexity: a catalog of parsimoniously #P-complete problems(6 Oct 2026) 33 concepts, 72 proofs registered
- Descriptive complexity: counting problems, #P, and FP(6 Oct 2026) 22 concepts, 31 proofs registered
- Descriptive complexity: games and inexpressibility(6 Oct 2026) 18 concepts, 26 proofs registered
- Descriptive complexity: degrees and graph isomorphism(6 Oct 2026) 10 concepts, 23 proofs registered
- Descriptive complexity: PSPACE, partial fixed points, and the Abiteboul–Vianu theorem(6 Oct 2026) 22 concepts, 39 proofs registered
- Descriptive complexity: AC⁰ as a logic(6 Oct 2026) 11 concepts, 14 proofs registered
- Descriptive complexity: coNP, DP and the polynomial hierarchy(6 Oct 2026) 23 concepts, 49 proofs registered
- Descriptive complexity: PTIME, fixed points and the Immerman–Vardi theorem(5 Oct 2026) 24 concepts, 29 proofs registered
- Descriptive complexity: L, NL and transitive closure(5 Oct 2026) 34 concepts, 42 proofs registered
- Graph Parameters and Functional Relations(5 Oct 2026) 22 concepts, 4 proofs registered
- ProvSQL: provenance-aware query rewriting and probabilistic query evaluation are correct(5 Oct 2026) 18 concepts, 41 proofs registered
- Finding Tree Decompositions of Small Treewidth(5 Oct 2026) 3 concepts, 2 proofs registered
- Conjunctive query evaluation and containment are NP-complete(3 Oct 2026) 12 concepts, 17 proofs registered
- Descriptive complexity: recursive enumerability, Trakhtenbrot and halting(3 Oct 2026) 26 concepts, 25 proofs registered
- Graph crawling is NP-complete(3 Oct 2026) 7 concepts, 10 proofs registered
- Descriptive complexity: a catalog of thirty NP-complete problems(3 Oct 2026) 21 concepts, 90 proofs registered
- Descriptive complexity: first-order reductions and the NP core(3 Oct 2026) 10 concepts, 14 proofs registered
- Håstad’s inapproximability of Max Clique(2 Oct 2026) 66 concepts, 170 proofs registered
- Arc Kayles is PSPACE-complete(2 Oct 2026) 14 concepts, 17 proofs registered
- Tight Inapproximability of Max Independent Set in Triangle-Free Graphs(2 Oct 2026) 5 concepts, 2 proofs registered
- The Immerman–Szelepcsényi Theorem(2 Oct 2026) 15 concepts, 10 proofs registered
- Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor(2 Oct 2026) 15 concepts, 8 proofs registered
- Large Finite Point Sets Have 4 Collinear Points or a 6-Clique(2 Oct 2026) 6 concepts, 4 proofs registered
- Constructive Lovász Local Lemma(2 Oct 2026) 4 concepts, 2 proofs registered
- Randomized Complexity Classes(2 Oct 2026) 9 concepts, 4 proofs registered
- Fair Repetitive Interval Scheduling(2 Oct 2026) 38 concepts, 84 proofs registered
- Just-in-Time Scheduling in Two-Stage Flexible Flow Shops(2 Oct 2026) 72 concepts, 133 proofs registered
- Interval Scheduling with Eligible Machine Sets(1 Oct 2026) 17 concepts, 27 proofs registered
- Feedback vertex and edge numbers(23 Sep 2026) 4 concepts, 2 proofs registered
- NP-Hardness of (3,4)-SAT and [2,3]-Bounded 3-SAT(21 Sep 2026) 4 concepts, 11 proofs registered
- Scheduling with Two Non-Unit Job Lengths Is NP-Complete(21 Sep 2026) 9 concepts, 19 proofs registered
- Compositional polynomial-time computation with black-box subroutines(19 Sep 2026) 5 concepts, 5 proofs registered
- The determinant of the least-common-multiple matrix(18 Sep 2026) 1 concept, 3 proofs registered
- Congruent number curves: the quadratic twist formula for a_p and the parity of Tunnell's representation counts(18 Sep 2026) 3 concepts, 3 proofs registered
- Smooth hypersurfaces: the Euler characteristic as a binomial tail, its parity, the Kodaira trichotomy, and the Noether–Lefschetz window as the sequence A005581(18 Sep 2026) 5 concepts, 14 proofs registered
- Panoptic Quality: exact rules for inclusion, removal and duplication, the sharpness of the matching threshold, and the annotator ceiling(18 Sep 2026) 7 concepts, 22 proofs registered
- Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors(18 Sep 2026) 29 concepts, 22 proofs registered
- Functional Equivalence of Twin-Width and Mixed Minor Number(15 Sep 2026) 5 concepts, 3 proofs registered
- Hadwiger's Conjecture for t = 7(15 Sep 2026) 2 concepts, 0 proofs registered
- Barnette's Conjecture(15 Sep 2026) 5 concepts, 0 proofs registered
- Graph Representations(15 Sep 2026) 11 concepts, 6 proofs registered
- Algorithmic Experiments on a Random Access Machine(15 Sep 2026) 7 concepts, 2 proofs registered
- The Word RAM(15 Sep 2026) 2 concepts, 0 proofs registered
- Almost Linear Neighborhood Complexity of Monadically Dependent Graph Classes(15 Sep 2026) 7 concepts, 3 proofs registered
- MSO and tree automata on finite ranked trees(15 Sep 2026) 10 concepts, 9 proofs registered
- Certified structural representations of finite data(15 Sep 2026) 12 concepts, 18 proofs registered
- Computability and polynomial-time equivalence of Turing machines and word RAMs(15 Sep 2026) 7 concepts, 4 proofs registered
- Fagin’s theorem(14 Sep 2026) 4 concepts, 4 proofs registered
- MSO-automata(14 Sep 2026) 7 concepts, 4 proofs registered
- The Immerman–Vardi theorem(14 Sep 2026) 8 concepts, 9 proofs registered
- Twin-width can be exponential in treewidth(14 Sep 2026) 3 concepts, 1 proof registered
- Sparsity Lectures: Nowhere Denseness, Quasi-Wideness, and Generalized Coloring Numbers(13 Sep 2026) 15 concepts, 7 proofs registered
- Finite Ramsey Theorems for Pairs and Tuples(13 Sep 2026) 4 concepts, 3 proofs registered
- Undecidability of positive first-order definability on words(10 Sep 2026) 7 concepts, 5 proofs registered
- The Cook–Levin Theorem(10 Sep 2026) 17 concepts, 11 proofs registered
- ETH, SETH, Weighted APSP, and 3SUM(9 Sep 2026) 18 concepts, 23 proofs registered
- Welzl Orders of Cographs(9 Sep 2026) 3 concepts, 2 proofs registered
- Classical Complexity Classes(9 Sep 2026) 19 concepts, 13 proofs registered
- Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity(8 Sep 2026) 6 concepts, 0 proofs registered
- An Introduction to Lax(7 Sep 2026) 4 concepts, 2 proofs registered
- Transducers(7 Sep 2026) 0 concepts, 0 proofs registered
- Transducers, Part D: Polyregular Functions(7 Sep 2026) 21 concepts, 15 proofs registered
- Transducers, Part C: Regular Functions in Terms of Combinators(7 Sep 2026) 4 concepts, 1 proof registered
- Transducers, Part C: Regular Functions in Terms of Logic(7 Sep 2026) 26 concepts, 22 proofs registered
- Transducers, Part C: Regular Functions, Two-Way Transducers and Streaming String Transducers(7 Sep 2026) 29 concepts, 23 proofs registered
- Transducers, Part B: Rational Functions(7 Sep 2026) 42 concepts, 29 proofs registered
- Transducers, Part A: Mealy Machines(7 Sep 2026) 22 concepts, 13 proofs registered
- Undecidability of the Post Correspondence Problem(7 Sep 2026) 9 concepts, 6 proofs registered
- Planar Graph Classes(3 Sep 2026) 38 concepts, 20 proofs registered
- A Refinement Framework for the Word RAM(2 Sep 2026) 0 concepts, 0 proofs registered
- Erdős–Hajnal for the five-vertex path(20 Aug 2026) 10 concepts, 9 proofs registered
- Erdős–Hajnal for graphs with no 5-hole(13 Aug 2026) 8 concepts, 7 proofs registered
- Szemerédi's Regularity Lemma(2 Aug 2026) 10 concepts, 5 proofs registered
- n Exponent Bound for the Grid-Minor Theorem(2 Aug 2026) 40 concepts, 27 proofs registered
- Graphs without a 3-Connected Subgraph are 4-Colourable(2 Aug 2026) 4 concepts, 2 proofs registered
- χ-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs(2 Aug 2026) 5 concepts, 2 proofs registered
- First-Order Model Checking on Nowhere Dense Graph Classes in Almost Linear Time(2 Aug 2026) 12 concepts, 6 proofs registered
- Depth Hierarchies for Symmetric Algebraic Circuits(2 Nov 2026) 38 concepts, 31 proofs draft
- Ten Graph Parameters(26 Oct 2026) 20 concepts, 0 proofs draft
- The equational theory of rational string-to-string functions(23 Oct 2026) 32 concepts, 21 proofs draft
- Scheduling problems assembled from constraint modules(19 Oct 2026) 89 concepts, 298 proofs draft
- Refined Near-Linear Computation of Welzl Orders(14 Oct 2026) 1 concept, 0 proofs draft
- Tree Nash Equilibria in the Network Creation Game(12 Oct 2026) 6 concepts, 1 proof draft
- Constructing the Oseledets decomposition with subspace growth estimates(4 Oct 2026) 65 concepts, 140 proofs draft
- Concept axioms: adversarial examples and dependency tracking(1 Oct 2026) 24 concepts, 21 proofs draft
- Graph Classes and Width Parameters(1 Oct 2026) 0 concepts, 0 proofs draft
- Direct proofs for planar graph classes(28 Sep 2026) 0 concepts, 6 proofs draft
- Constructing Welzl Orders: Algorithm and Correctness(25 Sep 2026) 0 concepts, 1 proof draft
- Proof network stress test(17 Sep 2026) 30 concepts, 57 proofs draft
- temporal-graphs(15 Sep 2026) 2 concepts, 1 proof draft
- Fagin’s theorem(9 Sep 2026) 4 concepts, 4 proofs draft
- The Immerman–Vardi theorem(8 Sep 2026) 8 concepts, 9 proofs draft
- Nagura's Theorem and the Interesting Numbers(31 Aug 2026) 2 concepts, 2 proofs draft
- Certified structural representations of finite data(31 Aug 2026) 12 concepts, 18 proofs draft
- MSO and tree automata on finite ranked trees(10 Aug 2026) 10 concepts, 15 proofs draft
- MSO-automata(10 Aug 2026) 7 concepts, 4 proofs draft
- Computability and polynomial-time equivalence of Turing machines and word RAMs(9 Aug 2026) 7 concepts, 4 proofs draft
- No submissions match.