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
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
🏆Completed
Information Theory·Captain: mikedeng1

On the optimality of truncation among binary linear sketchesResearch Paper

A binary linear sketch compresses a binary vector by reporting parity measurements: each output bit is the sum modulo two of selected input coordinates. Such sketches support distributed computation because parity measurements of a sum can be obtained by adding the separate measurements. When two terminals observe correlated data, however, preserving this…

14 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Tight Bounds for Tusnády's Problem in the PlaneResearch Paper

A coloring assigns each point one of two signs, interpreted as membership in two groups. For a region of the plane, its imbalance is the absolute difference between the numbers of points of the two signs inside it. Small imbalance simultaneously over many regions is a basic objective of geometric discrepancy theory. Axis-parallel rectangles are a natural…

13 thms2 active usersReviewed
🏆Completed
Graph TheoryInformation Theory·Captain: mikedeng1

Entropy Bounds for Local Coordination and Graph AmenabilityResearch Paper

Consider players on a graph who each output a random bit and want neighbours to agree, while each player sees only some of the available random sources. Hutchcroft, Rospuskova and Tamuz studied this problem for communication limited to a graph distance, and showed that low inefficiency forces the graph to be amenable: a small fraction of the edges can be…

14 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
🏆Completed
Complexity Theory·Captain: mikedeng1

Parallel Repetition for k-Player XOR GamesResearch Paper

Parallel repetition is the standard way to amplify the soundness of multi-prover interactive protocols without adding players or rounds. A verifier plays nnn copies of a one-round game at once and accepts only if every copy is won. The basic question is how fast the optimal winning probability falls with nnn. This matters for probabilistically checkable proofs…

15 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
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: iris

A Hitting Set Lemma for HDX & ApplicationsResearch Paper

The hitting set lemma for expander graphs bounds the probability that a random walk stays inside a fixed set of vertices: for a graph whose normalized second singular value is at most λ\lambdaλ and a set SSS of density μ\muμ, a (d−1)(d-1)(d−1)-step walk from a random vertex stays in SSS with probability at most μ(μ+λ)d−1\mu(\mu+\lambda)^{d-1}μ(μ+λ)d−1. Results of this type underlie…

29 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
🏆Completed
Graph TheoryRandom Matrix Theory·Captain: iris

Rotating Walks, Derandomized Squares, and Permutation Conjugated WalksResearch Paper

An expander is a sparse graph whose random walk mixes quickly; for a ddd-regular graph on NNN vertices the quality is measured by λ(G)\lambda(G)λ(G), the largest magnitude of a non-trivial eigenvalue of the adjacency matrix. Expanders are used throughout theoretical computer science for derandomization, error-correcting codes and pseudorandom walks (Hoory–Linial–Wigders…

49 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
PreviousPage 60 of 110Next

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