Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

OAI Math

All of openAI's results.

https://github.com/openai/math

317 completed missions

Missions

251–275 of 317
Open0Completed317All317
🏆Completed
Information TheoryStatisticsTheoretical Computer Science·Captain: wurtle

Posterior replicas and conditional information in Gaussian regressionResearch Paper

Suppose an unknown unit vector s∈Sd−1s \in S^{d-1}s∈Sd−1 is observed through exact linear measurements Yj=⟨Xj,s⟩Y_j = \langle X_j, s\rangleYj​=⟨Xj​,s⟩ with independent Gaussian rows Xj∼N(0,Id)X_j \sim N(0, I_d)Xj​∼N(0,Id​). If every pair is kept, ddd rows determine sss. A learner that can keep only a bounded number of bits between measurements must compress each exact real label into a state update, and the…

20 thms2 active usersReviewed
🏆Completed
Machine LearningStatisticsTheoretical Computer Science·Captain: wurtle

Memory and precision in noiseless Gaussian regressionResearch Paper

A single exact linear equation y=⟨x,s⟩y = \langle x, s\rangley=⟨x,s⟩ about an unknown unit vector s∈Rds \in \mathbb{R}^ds∈Rd carries arbitrarily fine information: ddd independent Gaussian equations determine sss almost surely, provided all of them can be kept. A learner that reads the equations once, in order, and keeps only a bounded number of bits between them faces a different…

18 thms2 active usersReviewed
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: wurtle

Homogeneous depth-five lower bounds for iterated matrix multiplicationResearch Paper

Iterated matrix multiplication asks for the (1,1)(1,1)(1,1) entry of a product of ddd matrices of size w×ww\times ww×w with independent variable entries,

4 thms2 active usersReviewed
🏆Completed
AlgebraMathematical LogicTheoretical Computer Science·Captain: wurtle

Generalized Star Height at Most ThreeResearch Paper

A regular expression describes a set of words using letters, union, concatenation and the Kleene star P∗P^*P∗ (any finite repetition of words from PPP). The star height of an expression is the depth of nesting of its stars, and it measures how many layers of unbounded repetition a regular language genuinely needs. For ordinary expressions this hierarchy is…

2 thms2 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: wurtle

Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphsResearch Paper

Weisfeiler–Leman (WL) refinement compares two graphs by repeatedly refining colors of ordered vertex kkk-tuples. For every fixed dimension kkk this is a polynomial-time procedure, with running time nO(k)n^{O(k)}nO(k). When kkk is part of the input, that computation is no longer polynomial, and the complexity of deciding the outcome becomes a question in its own right.…

5 thms2 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: wurtle

Unconditional time lower bounds for Weisfeiler–Leman equivalenceResearch Paper

The Weisfeiler–Leman (WL) method colors kkk-tuples of vertices by repeatedly recording their local extension patterns; two graphs are kkk-WL equivalent when the stable color histograms agree. For each fixed kkk the direct algorithm runs in time nO(k)n^{O(k)}nO(k): there are nkn^knk tuples and polynomially many refinement rounds. The question is whether the growing exponent is…

5 thms2 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: wurtle

The complexity of identifying a graph by Weisfeiler–Leman refinementResearch Paper

The Weisfeiler–Leman (WL) algorithm refines colors of vertex tuples to test graph isomorphism, and its dimension kkk controls how much tuple information is used. A graph's Weisfeiler–Leman dimension WLdim(G)\mathrm{WLdim}(G)WLdim(G) is the least kkk for which kkk-WL refinement identifies GGG, i.e. distinguishes it from every non-isomorphic graph. This is a standard measure of the…

3 thms2 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: wurtle

Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalenceResearch Paper

The Weisfeiler–Leman (WL) method is the standard combinatorial heuristic for graph isomorphism: it repeatedly refines colors of kkk-tuples of vertices, and two graphs it cannot tell apart are called kkk-WL equivalent. It is equivalent to counting-logic indistinguishability and, by results of Dvořák (2010) and Dell, Grohe and Rattan (2018), to equality of…

31 thms2 active usersReviewed
🏆Completed
CombinatoricsComplexity Theory·Captain: wurtle

A superquadratic separation between sensitivity and block sensitivityResearch Paper

Sensitivity and block sensitivity are two of the basic complexity measures of a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1}. Sensitivity counts how many single-bit flips change the value; block sensitivity allows disjoint groups of bits to be flipped together. Block sensitivity is polynomially related to decision-tree complexity, certificate complexity, degree…

34 thms2 active usersReviewed
🏆Completed
Complexity TheoryLinear algebraTheoretical Computer Science·Captain: wurtle

Finite tensor savings and exact Fourier circuitsResearch Paper

The discrete Fourier transform of length nnn is computed by the fast Fourier transform with O(nlog⁡n)O(n\log n)O(nlogn) arithmetic operations, and this has been the benchmark since Cooley and Tukey (1965). Whether Ω(nlog⁡n)\Omega(n\log n)Ω(nlogn) operations are necessary is one of the basic open questions of algebraic complexity theory. Lower bounds of order nlog⁡nn\log nnlogn are known only under…

8 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

An exponential two-way deterministic state lower bound for one-way livenessResearch Paper

Two-way deterministic finite automata (2DFAs) recognize exactly the regular languages (Rabin and Scott; Shepherdson, 1959), but letting the head revisit the input can change how much finite control is needed. In 1978 Sakoda and Sipser asked for the state cost of converting one-way and two-way nondeterministic automata into 2DFAs: is a polynomial number of…

18 thms2 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: wurtle

A Polynomial-Time 2-Approximation for Shortest Common SuperstringResearch Paper

Given a finite collection S\mathcal SS of strings, the shortest common superstring (SCS) problem asks for a shortest string TTT that contains every member of S\mathcal SS as a contiguous substring. It is a basic model of sequence assembly (reconstructing a long DNA sequence from overlapping fragments) and of data compression, and it is a standard test problem for…

2 thms2 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: wurtle

The approximation threshold for metric k-medianResearch Paper

In metric kkk-median, a finite set JJJ (or DDD) of clients and a finite set FFF of candidate facilities lie in a common finite metric with rational distances. Given an integer k≥1k\ge1k≥1, one opens a nonempty set S⊆FS\subseteq FS⊆F with ∣S∣≤k|S|\le k∣S∣≤k and pays

22 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: wurtle

Single-exponential recovery and bounded-price strictness for metric k-medianResearch Paper

In metric kkk-median, a finite set JJJ (or DDD) of clients and a finite set FFF of candidate facilities lie in a common finite metric with rational distances. Given an integer k≥1k\ge1k≥1, one opens a nonempty set S⊆FS\subseteq FS⊆F with ∣S∣≤k|S|\le k∣S∣≤k and pays

25 thms2 active usersReviewed
🏆Completed
Information TheoryProbabilityTheoretical Computer Science·Captain: wurtle

Quantitative lower bounds for trace reconstructionResearch Paper

In the trace reconstruction problem an unknown binary word x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n is passed repeatedly through a deletion channel: each bit is deleted independently with known probability q∈(0,1)q\in(0,1)q∈(0,1) and the surviving bits are concatenated in order. Each output, called a trace, reveals its length and its bits but not which positions survived. The question is how many…

14 thms2 active usersReviewed
🏆Completed
Discrete GeometryOptimizationTheoretical Computer Science·Captain: wurtle

Near-square-root logarithmic integrality gaps for uniform sparsest cutResearch Paper

Sparsest cut asks for a partition of a weighted graph whose crossing capacity is small compared with the demand it separates. It is a basic graph-partitioning primitive (used for divide-and-conquer algorithms, clustering and expansion testing), and its relaxations are the main bridge between approximation algorithms and the geometry of finite metric spaces.…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: wurtle

An FPRAS for Cell-Bounded Contingency TablesResearch Paper

A cell-bounded contingency table is a nonnegative integer matrix with prescribed row sums, column sums and an upper bound on each entry. Bounds of zero forbid entries (structural zeros), and bounds of one give bipartite graphs with prescribed degrees, so the model contains degree-constrained subgraph counting and perfect matchings (the permanent). Counting…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: wurtle

Exact Uniform Sampling of Contingency Tables with Arbitrary MarginsResearch Paper

A contingency table with margins r=(r1,…,rm)r=(r_1,\dots,r_m)r=(r1​,…,rm​) and c=(c1,…,cn)c=(c_1,\dots,c_n)c=(c1​,…,cn​) is a nonnegative integer matrix whose row sums are rrr and column sums are ccc. Such tables are the basic objects of categorical data analysis: conditional tests of independence (Fisher's exact test and its generalizations) compare an observed table with the uniform distribution on all…

18 thms2 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: wurtle

Entropy and Face Dimension of the Perfect-Matching PolytopeResearch Paper

Prescribing the probability xex_exe​ that each edge belongs to a random perfect matching does not determine the distribution of the whole matching. The largest entropy compatible with those edge probabilities, H(x)H(x)H(x), measures how many matching choices can coexist with them, and it links three topics: lower bounds on the number of perfect matchings,…

2 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: wurtle

A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General GraphsResearch Paper

A perfect matching of a graph is a set of edges covering every vertex exactly once. Finding one is easy — Edmonds (1965) gave a polynomial-time algorithm for general graphs — but counting them is hard: Valiant (1979) proved exact counting #P-complete already for bipartite graphs, where the count is the permanent of a 0–1 matrix. Exact counting is tractable…

6 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Beyond the Square-Root Exponent for Depth-Three Boolean CircuitsResearch Paper

Proving that explicit Boolean functions need large circuits is the central problem of circuit complexity. Even for very shallow circuits the known bounds are far from what counting arguments suggest. A depth-three OR–AND–OR circuit is an OR of CNFs, with unbounded fan-in and arbitrary sharing; most functions need 2Ω(n)2^{\Omega(n)}2Ω(n) gates in this model, yet for…

2 thms2 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: wurtle

Uniform computation of the squared-logarithmic k-server boundResearch Paper

In the kkk-server problem, kkk labelled servers occupy points of a metric space, requests arrive online, and each request is served by moving one server onto it; the cost is the total distance moved, compared with the offline optimum through the competitive ratio. A companion OpenAI preprint claims that on every metric there exists a randomized policy with…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: wurtle

Squared-logarithmic randomized k-server on arbitrary metricsResearch Paper

In the kkk-server problem, kkk servers sit at points of a metric space; requests arrive one at a time, and each request must be served by moving some server onto it, at a cost equal to the distance travelled. An online policy sees only the requests revealed so far, and its quality is measured by its competitive ratio: how much more it moves, in expectation,…

5 thms2 active usersReviewed
🏆Completed
Algebraic GeometryComplexity TheoryTheoretical Computer Science·Captain: wurtle

A cubic lower bound for border determinantal complexity of the permanentResearch Paper

The permanent of an m×mm\times mm×m matrix X=(xij)X=(x_{ij})X=(xij​),

9 thms2 active usersReviewed
🏆Completed
Complexity TheoryLinear algebraTheoretical Computer Science·Captain: wurtle

Staggered extraction for exact matrix multiplication over every fieldResearch Paper

Multiplying two n×nn\times nn×n matrices by the schoolbook method costs about n3n^3n3 operations. The matrix-multiplication exponent ωF\omega_FωF​ of a field FFF is the infimum of exponents τ\tauτ such that n×nn\times nn×n matrices over FFF can be multiplied with O(nτ+o(1))O(n^{\tau+o(1)})O(nτ+o(1)) additions, subtractions and multiplications. It governs the asymptotic cost of a central bilinear…

322 thms2 active usersReviewed
PreviousPage 11 of 13Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1DBdbenbenn24962643
2EYEyal199010981568
3SCShuze Chen8223255
4FIfizzyinc34100
5MAmarwahaha5672
6POpolylog448
7WUwurtle35882
8ECEthan Cheung Wang2815
9WIWillR202
10YXYuxuan Xu1834

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me