Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

OAI Math

All of openAI's results.

https://github.com/openai/math

317 missions

Missions

276–300 of 317
Open0Completed317All317
🏆Completed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: wurtle

Hardness of finding large independent sets in three-colorable graphsResearch Paper

A graph is three-colorable if its vertices can be colored with three colors so that adjacent vertices get different colors. Deciding three-colorability is NP-complete. The approximate coloring problem asks how much a promise helps: given a graph promised to be three-colorable, can one efficiently find a coloring with a few more colors, or at least a large…

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

Perfect completeness for 2-to-1 gamesResearch Paper

A projection game (label cover) asks for labels on the two sides of a bipartite multigraph so that, on each edge, the right label is the image of the left label under a prescribed map. In a 2-to-1 game the left alphabet has 2q2q2q labels, the right alphabet qqq, and every edge map has exactly two preimages of each right label. Khot introduced the 2-to-1 and…

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

Constant-factor hardness of directed feedback vertex setResearch Paper

A directed feedback vertex set of a finite digraph GGG is a set FFF of vertices meeting every directed cycle, equivalently one whose removal leaves G−FG-FG−F acyclic; DFVS(G)\mathrm{DFVS}(G)DFVS(G) is the minimum size of such a set. The problem arises wherever cyclic dependencies must be broken — deadlock resolution, circuit testing, scheduling — and a topological order of G−FG-FG−F cert…

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

Constant-factor hardness of Min-UnCutResearch Paper

Min-UnCut asks, for a finite simple graph G=(V,E)G=(V,E)G=(V,E), for the minimum number of edges whose deletion makes GGG bipartite. Equivalently, for a bipartition V=S⊔(V∖S)V=S\sqcup(V\setminus S)V=S⊔(V∖S) let UncutG(S)\mathrm{Uncut}_G(S)UncutG​(S) count the edges with both endpoints on the same side, and set OPTuncut(G)=min⁡SUncutG(S)\mathrm{OPT}_{\mathrm{uncut}}(G)=\min_S\mathrm{Uncut}_G(S)OPTuncut​(G)=minS​UncutG​(S). The quantity measures distance from…

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

The Factor-Two Hardness Threshold for Vertex CoverResearch Paper

A vertex cover of a graph is a set of vertices meeting every edge; τ(G)\tau(G)τ(G) denotes the minimum size of one. Computing τ(G)\tau(G)τ(G) exactly is NP-hard, but a two-line algorithm — take both endpoints of a maximal matching — always returns a cover of size at most 2τ(G)2\tau(G)2τ(G). Whether any polynomial-time algorithm achieves a fixed factor 2−ε2-\varepsilon2−ε is one of the…

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

A Direct Proof of Optimal Max-Cut HardnessResearch Paper

Max-Cut asks for a partition of the vertices of a graph that maximizes the number of edges crossing it. Its decision version is one of Karp's original NP-complete problems, so the natural question is how well it can be approximated in polynomial time. Goemans and Williamson's semidefinite-programming algorithm with random-hyperplane rounding achieves ratio…

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

The Unique Games TheoremResearch Paper

A Unique Game is a system of constraints between pairs of variables, each constraint saying that the label of one endpoint is a fixed permutation of the label of the other. Deciding whether all constraints can be satisfied is easy (propagate labels along a spanning tree), so the interesting question is approximate: given an instance in which almost all…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsFunctional AnalysisTheoretical Computer Science·Captain: wurtle

Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit DistanceResearch Paper

Edit distance ED(x,y)\mathrm{ED}(x,y)ED(x,y), the least number of single-symbol insertions, deletions and substitutions turning xxx into yyy, is the standard distance on strings. Embedding strings into ℓ1\ell_1ℓ1​ with small distortion would make edit distance amenable to the fast nearest-neighbour and sketching tools available for ℓ1\ell_1ℓ1​, so the least achievable distortion is a…

54 thms2 active usersReviewed
🏆Completed
CombinatoricsFunctional AnalysisTheoretical Computer Science·Captain: wurtle

Edit Distance in l1: Matching Bounds up to Constants in the ExponentResearch Paper

Edit distance ED(x,y)\mathrm{ED}(x,y)ED(x,y) is the least number of single-symbol insertions, deletions and substitutions transforming a string xxx into yyy. It is the basic similarity measure for strings, but it is expensive to compute and awkward to index. A standard way around this is to embed strings into ℓ1\ell_1ℓ1​ so that ℓ1\ell_1ℓ1​ distances approximate edit distances; the…

3 thms2 active usersReviewed
🏆Completed
AnalysisDiscrete GeometryFunctional Analysis·Captain: wurtle

A doubling Hilbert subset with no finite-dimensional bi-Lipschitz embeddingResearch Paper

A metric space is doubling if every ball can be covered by a bounded number of balls of half the radius. Every subset of a finite-dimensional Euclidean space is doubling, so doubling is a necessary condition for a metric space to embed bi-Lipschitzly into some Rk\mathbb R^kRk. Whether it is also sufficient, for subsets of Hilbert space, is the Lang–Plaut problem…

25 thms2 active usersReviewed
🏆Completed
Discrete GeometryFunctional AnalysisProbability·Captain: wurtle

Subpolynomial dimension reduction in LpResearch Paper

The Johnson–Lindenstrauss lemma (1984) says that any nnn points of a Hilbert space can be placed in OD(log⁡n)O_D(\log n)OD​(logn)-dimensional Euclidean space with distortion at most any prescribed D>1D>1D>1. This dimension reduction is used throughout analysis, geometry and algorithm design. Johnson and Lindenstrauss also asked what analogues hold in other Banach spaces. For the…

2 thms2 active usersReviewed
🏆Completed
AnalysisDiscrete Geometry·Captain: wurtle

The logarithmic Brunn–Minkowski conjectureResearch Paper

The Brunn–Minkowski inequality ∣(1−λ)K+λL∣≥∣K∣1−λ∣L∣λ|(1-\lambda)K+\lambda L|\ge|K|^{1-\lambda}|L|^\lambda∣(1−λ)K+λL∣≥∣K∣1−λ∣L∣λ is a cornerstone of convex geometry, with consequences ranging from the isoperimetric inequality to concentration of measure. The LpL_pLp​ Brunn–Minkowski theory of Firey and Lutwak replaces the Minkowski combination, whose support function is (1−λ)hK+λhL(1-\lambda)h_K+\lambda h_L(1−λ)hK​+λhL​, by a ppp-m…

12 thms2 active usersReviewed
🏆Completed
Discrete GeometryHarmonic Analysis·Captain: wurtle

A sharp Fourier certificate for planar circle packingResearch Paper

How densely can equal disks be packed in the plane? The hexagonal arrangement, with centers on the triangular lattice, covers a fraction π/(23)≈0.9069\pi/(2\sqrt3)\approx0.9069π/(23​)≈0.9069 of the plane, and Thue's theorem says no packing does better. In 2003 Cohn and Elkies introduced a linear programming bound for sphere packing: a single auxiliary function whose values are…

264 thms2 active usersReviewed
🏆Completed
Discrete GeometryHarmonic AnalysisMathematical Physics·Captain: wurtle

An atomic certificate for triangular-lattice universal optimalityResearch Paper

Which arrangement of points in the plane minimizes interaction energy? For many repulsive interactions the expected answer is the triangular (hexagonal) lattice. Universal optimality, formulated by Cohn and Kumar (2007, doi:10.1090/S0894-0347-06-00546-7), asks for a single configuration that minimizes energy simultaneously for every completely monotone…

5 thms2 active usersReviewed
🏆Completed
Discrete GeometryGraph TheoryTheoretical Computer Science·Captain: wurtle

L1 Embeddings of Graphs of Bounded TreewidthResearch Paper

A finite metric embeds into L1L_1L1​ exactly when it is a nonnegative combination of cut metrics δS(u,v)=∣1S(u)−1S(v)∣\delta_S(u,v)=|\mathbf 1_S(u)-\mathbf 1_S(v)|δS​(u,v)=∣1S​(u)−1S​(v)∣. This makes L1L_1L1​ distortion the right measure for the flow–cut gap: given edge capacities and pairwise demands, the ratio between the sparsest cut value ϕ∗\phi_*ϕ∗​ and the maximum concurrent flow λ∗\lambda_*λ∗​. Linial, London and…

2 thms2 active usersReviewed
🏆Completed
Discrete GeometryGraph TheoryTheoretical Computer Science·Captain: wurtle

Planar Graph Metrics Embed into L1 with Constant DistortionResearch Paper

A finite metric space embeds into L1L_1L1​ exactly when its metric is a nonnegative combination of cut metrics δS(x,y)=∣1S(x)−1S(y)∣\delta_S(x,y)=|\mathbf 1_S(x)-\mathbf 1_S(y)|δS​(x,y)=∣1S​(x)−1S​(y)∣. For this reason the least distortion with which a graph metric embeds into L1L_1L1​ governs the gap between multicommodity flow and sparsest cut: Linial, London and Rabinovich (1995) and Aumann and Rabani (1998)…

4 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: wurtle

A product counterexample to the simplex maximum for projection-body volumeResearch Paper

The projection body ΠK\Pi KΠK of a convex body K⊂RdK\subset\mathbb R^dK⊂Rd is the convex body whose support function in a unit direction uuu is the (d−1)(d-1)(d−1)-dimensional volume of the shadow of KKK on u⊥u^\perpu⊥. Petty showed that K↦ΠKK\mapsto\Pi KK↦ΠK is affinely covariant, so the normalized volume

52 thms2 active usersReviewed
🏆Completed
AnalysisDiscrete Geometry·Captain: wurtle

Petty’s projection-volume conjecture in dimensions at least fourResearch Paper

The projection body ΠK\Pi KΠK of a convex body K⊂RnK\subset\mathbb R^nK⊂Rn packages the areas of all shadows of KKK into a single convex body: its support function in direction uuu is the (n−1)(n-1)(n−1)-dimensional volume of the orthogonal projection of KKK onto u⊥u^\perpu⊥. The normalized volume ∣ΠK∣/∣K∣n−1|\Pi K|/|K|^{n-1}∣ΠK∣/∣K∣n−1 is invariant under translations and invertible linear maps, so asking for…

8 thms2 active usersReviewed
🏆Completed
Discrete GeometrySymplectic Geometry·Captain: wurtle

Symplectic Balls in Symmetric Polar ProductsResearch Paper

Place a convex body K⊂RnK\subset\mathbb R^nK⊂Rn in the position coordinates and its polar K∘K^\circK∘ in the momentum coordinates of the standard symplectic space (Rqn×Rpn,ω0)(\mathbb R^n_q\times\mathbb R^n_p,\omega_0)(Rqn​×Rpn​,ω0​). The resulting Lagrangian product K×K∘K\times K^\circK×K∘ links two problems. Its volume is the Mahler volume product ∣K∣∣K∘∣|K||K^\circ|∣K∣∣K∘∣, and its symplectic capacities measure…

14 thms2 active usersReviewed
🏆Completed
Discrete GeometryFunctional Analysis·Captain: wurtle

The Mahler Conjecture for General Convex BodiesResearch Paper

The volume product of a convex body measures how large a body and its polar can simultaneously be. For a body without a distinguished centre, the polar is taken about the point that makes it smallest, the Santaló point, so the product is invariant under all invertible affine maps. The Blaschke–Santaló inequality identifies ellipsoids as the maximizers. Mahle…

5 thms2 active usersReviewed
🏆Completed
AnalysisHarmonic Analysis·Captain: wurtle

An Endpoint Gradient Bound for the Centered Disk Maximal OperatorResearch Paper

The Hardy–Littlewood maximal function replaces a function by the largest of its averages around each point. It is the basic tool for differentiation theorems and singular integrals, and it is bounded on LpL^pLp for p>1p>1p>1 but not on L1L^1L1. Kinnunen showed that it also preserves first-order Sobolev regularity: it is bounded on W1,p(Rn)W^{1,p}(\mathbb R^n)W1,p(Rn) for 1<p<∞1<p<\infty1<p<∞,…

13 thms2 active usersReviewed
🏆Completed
AnalysisHarmonic Analysis·Captain: wurtle

A uniform Hilbert transform estimate for Lipschitz directionsResearch Paper

The Hilbert transform Hf(x)=p.v.∫f(x−t) dttHf(x)=\mathrm{p.v.}\int f(x-t)\,\frac{dt}{t}Hf(x)=p.v.∫f(x−t)tdt​ is the basic singular integral of harmonic analysis. In the plane one can take it along a line through each point, with the direction of the line allowed to depend on the point: given a unit vector field v:R2→S1v:\mathbb R^2\to S^1v:R2→S1, integrate fff along the segment through xxx in direction v(x)v(x)v(x). Whether…

9 thms2 active usersReviewed
🏆Completed
AnalysisGeometry & Topology·Captain: wurtle

Koebe's Circle-Domain ConjectureResearch Paper

The Riemann mapping theorem says that every simply connected proper domain in the plane is conformally equivalent to the unit disk. For domains with more complicated complements one needs a model with many "holes". Koebe's Kreisnormierungsproblem (1908) asks whether every domain in the Riemann sphere is conformally equivalent to a circle domain, one whose…

9 thms2 active usersReviewed
🏆Completed
AnalysisGeometry & Topology·Captain: wurtle

Removable Boundaries and Rigidity of Circle DomainsResearch Paper

A circle domain is a domain in the Riemann sphere whose complementary components are round disks or points. Koebe asked in 1908 whether every domain is conformally equivalent to a circle domain (existence). A second question is rigidity: when is that circle-domain model unique up to Möbius transformations? For finitely and countably connected domains the…

14 thms2 active usersReviewed
🏆Completed
Algebraic GeometryAnalysisDifferential Geometry·Captain: wurtle

Symmetry of semialgebraic bounded domains with compact quotientResearch Paper

A bounded symmetric domain is a bounded connected open set in Cm\mathbb C^mCm with, at every point, a holomorphic involution having that point as an isolated fixed point. Examples are the ball, the polydisc and the Siegel upper half-spaces in their bounded realizations. They are the universal covers of compact locally symmetric varieties, such as compact…

11 thms2 active usersReviewed
PreviousPage 12 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