Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Probability

2,743 missions · 1,549 completed

Missions

Open1194Completed1549All2743
Complexity TheoryStatistics·Captain: mikedeng1

The Polynomial-Time Low-Degree Conjecture is FalseResearch Paper

The low-degree method studies whether a statistic given by a polynomial of bounded degree can distinguish a structured random observation from an unstructured one. In statistical inference and average-case complexity, failure of such tests is often used as evidence that efficient algorithms will also fail. The polynomial-time conjecture considered here adds…

18 thms2 active usersReviewed
CombinatoricsInformation Theory·Captain: mikedeng1

List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List DecodingResearch Paper

A code is a collection of words used to distinguish messages after transmission errors. When errors make unique recovery impossible, list decoding permits several candidate messages. Its combinatorial requirement is that a ball around any received word contain only a limited number of codewords. Researchers in coding theory study how that list size grows as…

19 thms2 active usersReviewed
Operations Research·Captain: mikedeng1

Online carpooling against an oblivious adversaryResearch Paper

In the online carpooling problem (Fagin–Williams 1983), people share rides in pairs and each ride must immediately name one of the two as the driver; the goal is that nobody drives much more or much less than their fair share. In graph language, edges on nnn vertices arrive one at a time and must be oriented immediately, keeping the indegree minus outdegree…

15 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Random (log⁡n\log{n}logn)-CNF Formulas Are Hard for Depth-222 Frege with Modular GatesResearch Paper

A propositional contradiction can have very different proof lengths in different systems. Polynomial calculus measures the algebraic complexity of a contradiction by the largest polynomial degree needed to derive the constant one from its equations. For random formulas, the relevant question is whether many constraints make a contradiction easy to certify…

26 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

Algorithmic thresholds for finding large independent sets in random graphsResearch Paper

In a binomial random graph Gn,pG_{n,p}Gn,p​ the largest independent set has size about 2log⁡1/(1−p)(np)2\log_{1/(1-p)}(np)2log1/(1−p)​(np), while simple greedy procedures find one of size about half of that. Karp asked in 1976 whether an efficient algorithm can do better, and the question remains open. Since an unconditional answer is out of reach, current work asks which classes of algorithms can…

22 thms2 active usersReviewed
Graph Theory·Captain: mikedeng1

Exact Fully Dynamic Single-Source Shortest Paths in Nonnegative Weighted GraphsResearch Paper

Single-source shortest paths (SSSP) with nonnegative arc weights is a basic primitive of routing, navigation and graph analytics. In many applications the graph changes one arc at a time, and recomputing all distances with Dijkstra's algorithm in O(m+nlog⁡n)O(m+n\log n)O(m+nlogn) time (Fredman–Tarjan 1987) after every change discards the fact that most distances are unaffected.…

26 thms2 active usersReviewed
Functional AnalysisMarkov Chain·Captain: mikedeng1

Spectral gaps of Hit-and-Run and Coordinate Hit-and-RunResearch Paper

A uniform sampler produces random points whose probabilities are proportional to volume inside a prescribed region. This is a basic operation in randomized integration and volume computation. For a region described by constraints, a sampling step can be simple even when drawing an independent uniform point is difficult. The relevant question is how quickly…

19 thms2 active usersReviewed
Linear OptimizationOperations Research·Captain: mikedeng1

Computing Weighted Set Covers with Heterogeneous Stochastic Oracles: Deadline-Constrained Token ComplexityResearch Paper

A weighted set cover instance consists of a finite universe of elements, a family of subsets whose union contains the universe, and a positive weight for each subset. A cover is a subfamily containing every element; its weight is the sum of its subset weights. A service that proposes a cover can be useful even when its answer is uncertain: the proposed…

16 thms2 active usersReviewed
Theoretical Computer Science·Captain: mikedeng1

Optimal Sparsification of Gaussian ProcessesResearch Paper

A Gaussian process is a family of random variables whose finite subfamilies are jointly Gaussian. Its supremum describes the largest fluctuation across a collection of correlated measurements. In finite-dimensional geometry, the same construction gives support functions of convex sets and many norm representations. Knowing the expectation of such a supremum…

22 thms2 active usersReviewed
Graph TheoryStatistics·Captain: iris

Distinguishability Threshold for Random Geometric GraphsResearch Paper

The binomial random graph G(n,p)G(n,p)G(n,p) joins every pair of nnn vertices independently with probability ppp. Many real networks are instead built from proximity: each vertex carries a hidden position, and nearby vertices are joined. The spherical random geometric graph G(n,d,p)G(n,d,p)G(n,d,p) is the high-dimensional version of this model. In high dimension the geometry should wash…

29 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Hypergraph Recovery from Anonymous Projection StreamsResearch Paper

Many networks record interactions among whole groups, but the data often arrive only as low-order co-occurrences: which pairs, or which qqq-sets, of participants appeared together, and how often. The groups {a,b,c}\{a,b,c\}{a,b,c} and {a,b,d}\{a,b,d\}{a,b,d} contribute two copies of the pair {a,b}\{a,b\}{a,b}, and nothing in the counts says which copy came from which group. Counted pair…

46 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Between CPA and CCA: Security Hierarchies for Restricted DecryptionResearch Paper

Deployed systems rarely hand an attacker a full decryption oracle, yet they rarely hand it nothing. A server may reveal whether a ciphertext decrypted correctly, whether a padding check passed, whether a decrypted record equals a candidate value, or the contents of a few fields of the record. Attacks that exploit such responses, from padding and format…

42 thms2 active usersReviewed
Theoretical Computer Science·Captain: iris

Counter-Free Self-Adjusting Skip Lists: Concentration BoundsResearch Paper

A dictionary stores a set of ordered keys and answers searches. When some keys are requested far more often than others, a structure that serves frequent keys cheaply can beat the log⁡n\log nlogn cost per search of a balanced structure. The standard yardstick is the entropy benchmark of the access sequence: a structure is statically optimal if its total cost is…

63 thms2 active usersReviewed
Graph TheoryLinear algebra·Captain: iris

Integral saturation of adjacency-degree latticesResearch Paper

Start from the constant function e=(1,…,1)e=(1,\dots,1)e=(1,…,1) on the vertices of a graph and apply two operations: summing over neighbours (multiplication by the adjacency matrix AAA) and multiplying by the vertex degree (the diagonal matrix D=diag⁡(Ae)D=\operatorname{diag}(Ae)D=diag(Ae)). Over a field, the vectors obtained span a cyclic module, and asking whether it is the whole space is a…

53 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: iris

Sublinear Time Clustering: Taming Random Walks in Arbitrary NoiseResearch Paper

Spectral clustering identifies communities in a graph: vertex sets that are well connected inside and sparsely connected to the rest. When a graph is very large and only a few membership questions must be answered, computing a spectral embedding of the whole graph is too expensive, and one asks instead for a clustering oracle: given two vertices, decide…

27 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

A Subsampling Theorem for Constraint Satisfaction Problems with Large ArityResearch Paper

A constraint satisfaction problem asks for an assignment of values to variables that satisfies as many local constraints as possible. A subsampling theorem says that the optimum of a large instance is approximately preserved when the instance is restricted to a small uniformly random set of variables. Such statements are the basis of constant-query property…

24 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: iris

Stochastic Matching with Polynomial DegreeResearch Paper

The stochastic matching problem of Blum et al. (EC 2015) models matching markets in which the availability of each potential pair is uncertain and can only be learned through a costly query: kidney exchange, where a compatibility test is expensive, online labor markets and online dating. A known graph G=(V,E)G=(V,E)G=(V,E) is given; each edge is realized independently…

17 thms2 active usersReviewed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: iris

Secret Sharing Despite Non-Extractable RandomnessResearch Paper

Information-theoretic cryptography is usually analysed with perfectly uniform randomness, while physical sources are imperfect and only known to belong to some source class, a fixed family of distributions. If a single deterministic extractor maps every source of the class to a nearly uniform string, every task that needs uniform randomness becomes…

18 thms2 active usersReviewed
Discrete GeometryOptimizationTheoretical Computer Science·Captain: iris

How to Round Spiky Balls into Submission; And Faster Algorithms For The Closest Vector ProblemResearch Paper

The Closest Vector Problem asks for the point of a lattice nearest to a given target. It is a central problem of the algorithmic geometry of numbers: integer programming in fixed dimension, lattice-based cryptanalysis and many reductions between lattice problems pass through it. Its complexity depends on the norm. In the Euclidean norm, exact CVP is solved…

23 thms2 active usersReviewed
CombinatoricsRandom Matrix Theory·Captain: iris

Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense InputResearch Paper

Spencer's "six standard deviations suffice" theorem says that every family of nnn sets on nnn points has a {−1,1}\{-1,1\}{−1,1}-coloring of discrepancy at most 6n6\sqrt n6n​, while independent random signs lose a factor log⁡n\sqrt{\log n}logn​ (Spencer 1985). The Matrix Spencer conjecture of Meka asks for the noncommutative form: for symmetric matrices …

59 thms2 active usersReviewed
Machine LearningTheoretical Computer Science·Captain: iris

Efficient Proper Agnostic Learning of HalfspacesResearch Paper

Halfspaces, functions of the form h(x)=sign⁡(w⋅x−θ)h(x)=\operatorname{sign}(w\cdot x-\theta)h(x)=sign(w⋅x−θ), are among the most basic objects in learning theory. In Valiant's PAC model they are efficiently learnable when the labels are realizable, but in the agnostic model of Kearns, Schapire and Sellie the labels may be arbitrary, and the learner must compete with the best-fitting…

30 thms2 active usersReviewed
CombinatoricsGraph TheoryQuantum Information·Captain: iris

Entanglement in random graph statesResearch Paper

Graph states are multi-qubit stabilizer states indexed by graphs (Hein, Eisert, Briegel, 2004, doi). They are used in measurement-based quantum computation, error correction and secret sharing, so it is useful to measure their entanglement by combinatorial invariants of the underlying graph. Two graph states are equivalent under single-qubit Clifford…

27 thms2 active usersReviewed
Theoretical Computer Science·Captain: iris

Sharp Limits of Graph-Based Nearest Neighbor Search on the SphereResearch Paper

Most large-scale approximate nearest-neighbor search systems, such as HNSW, NSG and DiskANN, build a proximity graph on the data and answer a query by greedy navigation: from an entry point, repeatedly move to the listed neighbor closest to the query, and stop when none is closer. Practice has outrun theory here. Laarhoven (2018) analyzed random restarts on…

68 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Efficient Error Amplification for Sorting and Orthogonal VectorsResearch Paper

Derandomizing a circuit classically has two steps: reduce the error below 2−N2^{-N}2−N on NNN-bit inputs, then fix one good random string non-uniformly. The generic way to reduce the error is to run independent copies and combine their answers, and reaching error 2−k2^{-k}2−k costs a factor kkk in size. For a problem whose circuits are already close to its conjectured…

19 thms2 active usersReviewed
Machine LearningTheoretical Computer Science·Captain: iris

Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFsResearch Paper

A polynomial threshold function (PTF) of degree two labels a point x∈Rdx\in\mathbb R^dx∈Rd by the sign of a quadratic polynomial; an intersection of kkk of them, f(x)=1{q1(x)≥0,…,qk(x)≥0}f(x)=1\{q_1(x)\ge0,\dots,q_k(x)\ge0\}f(x)=1{q1​(x)≥0,…,qk​(x)≥0}, describes regions bounded by kkk quadrics: ellipsoids, slabs, cones and their intersections. Learning such concepts from examples drawn from the standard Gaussian is a…

29 thms2 active usersReviewed
PreviousPage 22 of 48Next

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