1"""Area theory: categories 18-19 (algorithms and data structures, computational complexity)."""23CATEGORIES = [4dict(5 id="algorithms", number=18, name="Algorithms and Data Structures", area="theory",6 definition=("Design and analysis of algorithms and data structures: graph, string, geometric, approximation, randomized, "7 "online, streaming, parallel and parameterized algorithms, combinatorial optimisation and metaheuristics, "8 "algorithmic game theory, algorithm engineering, and the combinatorics that underpins them. Lower bounds and "9 "hardness as such are computational_complexity; numerical algorithms are scientific_computing."),10 topics=[("T10720", 1.0, "complexity and algorithms in graphs (approximation, shortest paths, flows)"),11 ("T11269", 1.0, "algorithms and data compression (strings, sorting, succinct structures)"),12 ("T10374", 0.8, "advanced graph theory research"), ("T12292", 0.8, "graph theory and algorithms"),13 ("T10996", 0.7, "computational geometry and mesh generation"), ("T12541", 0.6, "graph labeling and dimension problems"),14 ("T12288", 0.6, "optimization and search problems"), ("T11596", 0.6, "constraint satisfaction and optimization"),15 ("T11476", 0.6, "graph theory and applications"), ("T11106", 0.6, "data management and algorithms"),16 ("T10100", 0.5, "metaheuristic optimization algorithms"), ("T11975", 0.5, "evolutionary algorithms"),17 ("T10948", 0.5, "advanced combinatorial mathematics"), ("T10551", 0.5, "scheduling and optimization algorithms"),18 ("T12176", 0.5, "optimization and packing problems"), ("T10792", 0.4, "matrix theory and algorithms"),19 ("T11329", 0.4, "limits and structures in graph theory"), ("T10963", 0.4, "advanced optimization algorithms"),20 ("T12401", 0.4, "scheduling and timetabling"), ("T10848", 0.3, "multi-objective optimization algorithms"),21 ("T10545", 0.3, "optimization and variational analysis"), ("T11697", 0.3, "numerical methods and algorithms"),22 ("T12162", 0.3, "cellular automata"), ("T12536", 0.3, "topological data analysis"),23 ("T10567", 0.3, "vehicle routing optimization"), ("T12709", 0.3, "optimization and mathematical programming"),24 ("T12303", 0.3, "tensor decomposition"), ("T11031", 0.3, "game theory and applications"),25 ("T10991", 0.3, "game theory and voting systems"), ("T11182", 0.2, "auction theory"),26 ("T10287", 0.2, "algebraic structures and combinatorial models"), ("T12056", 0.2, "Markov chains and Monte Carlo"),27 ("T11716", 0.2, "random matrices"), ("T12177", 0.2, "resource-constrained project scheduling"),28 ("T11252", 0.2, "evolutionary game theory and cooperation")],29 subfields=[(1703, 0.3)],30 arxiv=[("cs.DS", 1.0), ("cs.DM", 0.8), ("cs.CG", 0.8), ("cs.GT", 0.5), ("cs.CC", 0.2), ("math.OC", 0.3), ("cs.NE", 0.3)],31 streams=[("conf/soda", 1.0), ("conf/esa", 1.0), ("journals/algorithmica", 1.0), ("journals/talg", 1.0), ("conf/wads", 1.0),32 ("conf/isaac", 1.0), ("conf/swat", 1.0), ("conf/alenex", 1.0), ("conf/wea", 1.0), ("conf/icalp", 0.8),33 ("conf/latin", 0.8), ("journals/jco", 0.8), ("journals/algorithms", 0.8), ("journals/dmaa", 0.8), ("conf/cccg", 0.8),34 ("conf/stacs", 0.7), ("conf/mfcs", 0.7), ("journals/ipl", 0.7), ("journals/dam", 0.7), ("journals/dcg", 0.7),35 ("conf/approx", 0.7), ("conf/stoc", 0.6), ("conf/focs", 0.6), ("journals/siamcomp", 0.6), ("journals/tcs", 0.6),36 ("journals/siamdm", 0.6), ("conf/fsttcs", 0.6), ("conf/gecco", 0.6), ("conf/cec", 0.6), ("journals/tec", 0.6),37 ("journals/swevo", 0.6), ("journals/jcss", 0.5), ("conf/sofsem", 0.5), ("journals/jacm", 0.4), ("journals/dm", 0.4),38 ("journals/combinatorics", 0.4), ("journals/jgt", 0.4), ("journals/gc", 0.4), ("journals/cor", 0.4), ("journals/orl", 0.4),39 ("journals/mp", 0.4), ("conf/sigecom", 0.4), ("conf/cp", 0.4), ("journals/ejc", 0.3), ("journals/eor", 0.3),40 ("journals/siamjo", 0.3), ("journals/jgo", 0.3), ("journals/ol", 0.3), ("journals/jcta", 0.3), ("journals/jctb", 0.3),41 ("journals/jct", 0.3), ("journals/itor", 0.3), ("journals/rairo", 0.3), ("journals/jota", 0.2), ("journals/geb", 0.2),42 ("journals/anor", 0.2), ("journals/ior", 0.2), ("journals/jors", 0.2), ("journals/mansci", 0.1), ("journals/jet", 0.1),43 ("conf/sat", 0.2), ("journals/ffa", 0.2), ("journals/candie", 0.2), ("journals/asc", 0.2), ("journals/soco", 0.2),44 ("journals/evi", 0.4), ("journals/jossac", 0.2), ("journals/siamam", 0.1)],45 keywords=[46 (r"(?i)\b(approximation|randomi[sz]ed|online|streaming|sublinear|parameteri[sz]ed|exact|combinatorial|graph|geometric|parallel|distributed|dynamic|external[- ]memory|cache-?oblivious|greedy|divide-?and-?conquer|branch-?and-?bound|exponential-?time|polynomial-?time|efficient|fast|optimal|linear-?time|near-?linear|quantum|string|matching|sorting|search|enumeration|sampling|sketching|learning-?augmented) algorithms?\b", 1.0, "both"),47 (r"(?i)\bdata structures?\b|\balgorithm (design|analysis|engineering|theory)\b|\balgorithmic\b", 1.0, "both"),48 (r"(?i)\b(time complexity|running time|worst-?case|amorti[sz]ed|competitive ratio|approximation (ratio|factor|scheme)|PTAS|FPTAS|NP-?hard|NP-?complete|polynomial[- ]time|FPT\b|fixed-?parameter|kernelization|treewidth|lower bounds?|upper bounds?|O\(n (log|\^)|tight bounds?|conditional lower bounds?)\b", 0.7, "both"),49 (r"(?i)\b(shortest paths?|(maximum|max)[- ]flow|(minimum|min)[- ]cut|spanning trees?|vertex cover|independent sets?|dominating sets?|graph colou?ring|cliques?|Steiner trees?|knapsack|bin packing|TSP\b|travell?ing salesman|scheduling problems?|vehicle routing|facility location|set cover|matchings?|matroids?|submodular|(linear|integer|semidefinite) programming|cutting planes?|primal-?dual|LP (relaxation|rounding)|network flows?|spanners?|reachability|dynamic graphs?|distance oracles?)\b", 0.7, "both"),50 (r"(?i)\b(sorting|searching|hashing|hash (tables?|functions? for)|suffix (trees?|arrays?)|string (matching|algorithms?|indexing)|pattern matching|succinct|compressed (indexes?|data structures?)|sketch(es|ing)|locality[- ]sensitive hashing|Bloom filters?|priority queues?|heaps?|balanced (trees?|search)|B-?trees?|tries?|range (queries|searching|minimum)|nearest neighbou?r search|k-?d trees?|persistent data|dynamic (connectivity|trees)|union-?find|disjoint sets?|skip lists?|cuckoo hashing|streaming (algorithms?|model)|sketch(ing)? algorithms?|sublinear)\b", 0.8, "both"),51 (r"(?i)\b(metaheuristics?|evolutionary (algorithms?|computation)|genetic algorithms?|particle swarm|ant colony|simulated annealing|tabu search|local search|differential evolution|swarm intelligence|memetic|hyper-?heuristics?|combinatorial optimi[sz]ation|constraint (programming|satisfaction|propagation)|SAT-?based|MaxSAT|mixed-?integer|branch-?and-?(bound|cut|price)|column generation|Lagrangian relaxation|multi-?objective optimi[sz]ation|Pareto (front|optimal))\b", 0.6, "both"),52 (r"(?i)\b(computational geometry|Voronoi|Delaunay|convex hull|triangulations?|arrangements? of|range searching|point location|motion planning (complexity|algorithms)|polygon|visibility graphs?|geometric (optimi[sz]ation|intersection|approximation)|kinetic data)\b", 0.8, "both"),53 (r"(?i)\b(algorithmic game theory|mechanism design|price of anarchy|Nash equilibri(a|um)|equilibrium computation|fair division|cake cutting|matching markets|stable matching|auction (design|theory)|social choice|voting rules?|computational social choice|incentive compatib)\b", 0.7, "both"),54 (r"(?i)\b(graph theory|planar graphs?|chromatic|Hamiltonian|Ramsey|extremal (graph|combinatorics)|combinatorics|combinatorial (designs?|structures?)|enumerative|Latin squares?|permutations? (patterns?|statistics)|hypergraphs?|digraphs?|tournaments?|graph (minors?|decompositions?|embeddings?|homomorphisms?|isomorphism))\b", 0.6, "both"),55 (r"(?i)\balgorithms?\b|\bcomplexity\b|\bheuristics?\b|\boptimi[sz]ation\b|\bgraphs?\b", 0.3, "both"),56 ],57 exclusions=[],58 related=["computational_complexity", "ml_theory", "computer_graphics", "database_systems", "distributed_computing", "scientific_computing"],59 parent_of=[], child_of=[],60 provenance=("Core topics T10720/T11269 (1703, 1702) plus graph-theory, geometry, combinatorial-optimisation and metaheuristic "61 "topics of fields 17, 26 and 22; SODA/ESA/Algorithmica/TALG are the pure venues, STOC/FOCS shared with complexity."),62),63dict(64 id="computational_complexity", number=19, name="Computational Complexity", area="theory",65 definition=("The intrinsic difficulty of computational problems: complexity classes and their separations, hardness of "66 "approximation, circuit, proof, communication and query complexity, fine-grained and parameterized complexity, "67 "pseudorandomness and derandomization, computability and automata theory, algebraic complexity, and quantum "68 "complexity. Algorithm design is algorithms; cryptographic hardness assumptions are applied_cryptography."),69 topics=[("T12002", 0.8, "computability, logic and AI algorithms (Turing machines, Kolmogorov complexity)"),70 ("T11567", 0.7, "semigroups and automata theory"), ("T10720", 0.5, "complexity and algorithms in graphs (P vs NP, complexity classes)"),71 ("T11435", 0.5, "polynomial and algebraic computation"), ("T11727", 0.3, "advanced algebra and logic"),72 ("T11130", 0.2, "coding theory and cryptography"), ("T12162", 0.2, "cellular automata"),73 ("T10020", 0.1, "quantum information (quantum complexity)"), ("T12469", 0.1, "chaos, complexity and education")],74 subfields=[(1703, 0.2)],75 arxiv=[("cs.CC", 1.0), ("cs.FL", 0.5), ("cs.LO", 0.2), ("cs.DS", 0.2), ("quant-ph", 0.1), ("cs.IT", 0.1), ("math.IT", 0.1)],76 streams=[("journals/eccc", 1.0), ("journals/toct", 1.0), ("conf/stoc", 0.8), ("conf/focs", 0.8), ("conf/csr", 0.6),77 ("conf/dlt", 0.6), ("conf/icalp", 0.5), ("conf/stacs", 0.5), ("conf/mfcs", 0.5), ("journals/siamcomp", 0.5),78 ("journals/jcss", 0.5), ("journals/iandc", 0.5), ("journals/jacm", 0.4), ("conf/approx", 0.4), ("conf/fsttcs", 0.4),79 ("journals/tcs", 0.3), ("conf/sofsem", 0.3), ("journals/ipl", 0.2), ("conf/lics", 0.2), ("journals/lmcs", 0.2),80 ("conf/soda", 0.2), ("journals/apal", 0.2), ("journals/mscs", 0.2), ("journals/algorithmica", 0.1),81 ("journals/talg", 0.1), ("conf/csl", 0.1), ("journals/acta", 0.2), ("conf/sat", 0.2)],82 keywords=[83 (r"(?i)\b(computational|circuit|communication|proof|query|descriptive|parameteri[sz]ed|fine-?grained|average-?case|Kolmogorov|algorithmic|quantum|structural|space|time|arithmetic|algebraic|Boolean|counting|streaming|information) complexity\b", 1.0, "both"),84 (r"(?i)\bcomplexity (theory|class(es)?|lower bounds?|separations?|dichotom(y|ies)|hierarch(y|ies))\b|\bcomplexity-?theoretic\b", 1.0, "both"),85 (r"(?i)\b(P (vs\.?|versus|=|≠|!=) ?NP|NP-?complete(ness)?|NP-?hard(ness)?|coNP|PSPACE|EXPTIME|NEXP|#P\b|BPP\b|BQP\b|QMA\b|MIP\*?\b|PH\b|polynomial(-time)? hierarchy|AC\^?0|NC\^?[01]|TC\^?0|ACC\^?0|NL\b|L\b vs|P/poly|NP ∩ coNP|ZPP|RP\b|PP\b|PPAD|PLS\b|TFNP|W\[1\]|W\[2\]|XP\b|para-?NP)\b", 1.0, "both"),86 (r"(?i)\b(hardness of approximation|inapproximab|PCP theorem|probabilistically checkable|unique games|exponential[- ]time hypothesis|SETH\b|ETH\b|orthogonal vectors|3-?SUM|APSP (hardness|conjecture)|derandomi[sz]ation|pseudorandom(ness)? (generators?|functions?|for)|hardness (amplification|vs\.? randomness|magnification|escalation)|natural proofs|lifting theorems?|arithmetic circuits?|algebraic (complexity|circuits)|VP (vs|versus|≠) VNP|matrix multiplication exponent|omega \(ω\)|Boolean (circuits?|functions?) (lower|complexity|size)|circuit lower bounds?|formula (size|lower bounds?)|decision tree complexity|sensitivity conjecture|constraint satisfaction problems? dichotomy|CSP dichotomy|counting complexity|holographic algorithms|interactive proofs?|zero-?knowledge complexity|Arthur-?Merlin|relativi[sz]ation|oracle separations?|time-?space trade-?offs?|catalytic|meta-?complexity|MCSP|minimum circuit size)\b", 1.0, "both"),87 (r"(?i)\b(computability|decidability|undecidab|Turing machines?|halting problem|recursion theory|recursively enumerable|computably enumerable|Turing degrees|automata theory|formal languages?|regular languages?|context-?free (languages?|grammars?)|pushdown automata|finite automata|cellular automata|descriptional complexity|state complexity|Rice'?s theorem|reductions? (between|from|to)|Kolmogorov|algorithmic (randomness|information)|reverse mathematics|Büchi automata|tree automata|weighted automata|transducers?|ω-?regular)\b", 0.8, "both"),88 (r"(?i)\bproof complexity\b|\bresolution (lower bounds?|refutations?|width|size)\b|\bcutting planes proofs?\b|\bFrege\b|\bbounded arithmetic\b", 1.0, "both"),89 (r"(?i)\b(hardness|intractab(le|ility)|lower bounds?|reductions?|separations?)\b", 0.4, "both"),90 ],91 exclusions=[r"(?is)^(?!.*(complexity (class|theory)|NP|PSPACE|lower bound|hardness|computab|automata|Turing|circuit|reduction|decidab)).*\b(complexity of (care|disease|life|organi[sz]ations|the (world|environment|problem))|complex systems?|complexity science|chaos)\b"],92 related=["algorithms", "formal_verification", "quantum_computing", "applied_cryptography", "ml_theory"],93 parent_of=[], child_of=[],94 provenance=("OpenAlex has no pure complexity topic: it mixes classes into T10720 and computability into T12002/T11567. ECCC and "95 "ToCT are the pure streams; STOC/FOCS shared with algorithms; cs.CC alone suffices."),96),97]98