OpenAI Math·Subject
Theoretical computer science
40 of the 372 results in OpenAI's maths catalogue are in theoretical computer science. Each page quotes OpenAI's own summary, links the preprints and embeds the animation once it is released. 1 of them have a video so far.
Watch
Videos in Theoretical computer science
All 40 results
- 102The Unique Games Conjecture and optimal approximation thresholdsLean
- 103Exact derandomization of logarithmic space: L=RL=BPLLean
- 104Quasipolynomial algorithms for mean-payoff, stochastic and parity gamesLean
- 105Perfect completeness for 2-to-1 gamesLean
- 106Hardness of coloring three-colorable graphsLean
- 107Matrix multiplication with exponent at most 9/4Lean
- 108A cubic permanent–determinant lower boundLean
- 109Integer multiplication below n log n
- 110Optimal-order randomized k-server on arbitrary metricsLean
- 111One-sample matroid prophet inequalities against an almighty adversaryLean
- 112Beyond the square-root exponent for depth-three circuitsLean
- 113Approximate counting and entropy of perfect matchingsLean
- 114Approximate counting of common integer polymatroid basesLean
- 115Sampling and counting contingency tables with arbitrary marginsLean
- 116Uniform black-box noncommutative identity testing across characteristicsLean
- 117Uniform sparsest cut: hardness and semidefinite gapsLean
- 118Bin packing and unbounded configuration-LP gapsLean
- 119The Courtade–Kumar and Hellinger conjecturesLean
- 120Almost-linear-time exact matching and prescribed-degree factors in general graphs
- 121Almost-linear approximation of edit distanceLean
- 122Quantitative trace-reconstruction bounds with a uniform decoderLean
- 124Polynomial-time scheduling on three identical machinesLean
- 125The metric k-median approximation threshold and recoveryLean
- 126Exponential semidefinite complexity of perfect matchingLean
- 127Average sensitivity of polynomial threshold functionsVideoLean
- 128A factor-two approximation for shortest common superstringLean
- 129Exponential state costs for two-way automataLean
- 130Exact Fourier transforms below n log nLean
- 131Rapid mixing of graph switches for every degree sequenceLean
- 132A superquadratic separation of sensitivity and block sensitivityLean
- 133The computational complexity of Weisfeiler–Leman refinementLean
- 134Generalized star height at most threeLean
- 135Homogeneous depth-five lower bounds for iterated matrix multiplicationLean
- 136A quasilinear PCP theorem for PPAD
- 137One-tape time simulation in two-fifths-power spaceLean
- 138Subset Sum in O(20.49n) time
- 139Subpolynomial query complexity for log-concave samplingLean
- 140Memory–sample lower bounds for noiseless Gaussian regressionLean
- 141Existential–universal real sentences in the counting hierarchy
- 142Deterministic polynomial factorization over prime fields
Other subjects
- Combinatorics 37
- Algebraic and complex geometry 36
- Number theory 31
- Differential geometry 29
- Probability and statistical mechanics 29
- Mathematical physics 25
- Operator algebras 19
- Algebra 18
- Topology 18
- Partial differential equations 16
- Real and complex analysis 16
- Convex and metric geometry 15
- Group theory 14
- Dynamical systems and ergodic theory 12
- Functional analysis 11
- Mathematical logic 6