Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

ACM STOC 2027

Formalizations of theorems from papers submitted to ACM STOC 2027 (the 59th Annual ACM Symposium on Theory of Computing). Paper list: https://sigact-stoc.github.io/stoc2027/ . Missions here state a main result of a STOC 2027 paper in Lean 4 with Mathlib; each mission's title begins with the paper title.

1496 missions

Missions

1301–1325 of 1496
Open1374Completed122All1496
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

An Explicit and Optimal Separation of BPP from NP in Number-on-Forehead Communication ComplexityResearch Paper

Communication complexity measures how many bits participants must exchange when each sees only part of an input. In the number-on-forehead model, there are kkk participants and kkk input blocks: participant iii sees every block except block iii. Their overlapping knowledge makes lower bounds difficult. A separation between randomness and nondeterminism asks whether…

13 thms1 active userReviewed
Computational GeometryDiscrete GeometryGraph Theory·Captain: iris

The Stretch Factor of Planar Delaunay Triangulations Is Nearly DeterminedResearch Paper

A Delaunay triangulation of a finite point set S⊂R2S\subset\mathbb R^2S⊂R2 is a triangulation in which the open circumdisk of every triangle contains no point of SSS. Its stretch factor is the worst ratio dD(u,v)/∥u−v∥d_D(u,v)/\|u-v\|dD​(u,v)/∥u−v∥ over pairs u≠vu\ne vu=v of SSS, where dD(u,v)d_D(u,v)dD​(u,v) is the length of a shortest path from uuu to vvv along the edges of DDD. A uniform bound ttt on this ratio makes…

32 thms1 active userReviewed
Computational ComplexityConvex OptimizationMachine Learning·Captain: iris

Universal Hardness From Masking ChannelsResearch Paper

Given a class C\mathcal CC of predictors (Boolean circuits of bounded size, models of a fixed architecture), why is a labeling fff hard to approximate by members of C\mathcal CC? The hardcore lemma of complexity theory answers this for Boolean labels and the 0-1 loss: if every c∈Cc\in\mathcal Cc∈C errs on a δ\deltaδ-fraction of inputs, then there is a measure μ\muμ of…

31 thms1 active userReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Asymptotically Optimal Weighted Edge Colorings via Local Bin PackingResearch Paper

In weighted edge coloring each edge of a graph carries a weight in (0,1](0,1](0,1], and a coloring is feasible when, at every vertex, the edges of each color have total weight at most one. The problem generalizes ordinary edge coloring (all weights one) and bin packing (a star). Its principal application is multirate routing in three-stage Clos networks, where…

20 thms1 active userReviewed
Information TheoryProbabilityStatistics·Captain: iris

Functional inequalities from the fundamental limits of Bayesian estimationResearch Paper

Functional inequalities bound how much a function can fluctuate under a probability measure by the size of its gradient. The two central examples are the Poincaré inequality, which bounds the variance, and the log-Sobolev inequality, which bounds the entropy [Gro75]. Their constants control the mixing times of Langevin diffusions and Markov chains, the…

26 thms1 active userReviewed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: iris

Polynomial Time Algorithms for the Kadison-Singer ProblemResearch Paper

The Kadison–Singer problem (Kadison and Singer, 1959) asks whether every pure state on the algebra of bounded diagonal operators on ℓ2\ell_2ℓ2​ extends uniquely to a pure state on all bounded operators. It has many equivalent forms; the one used here is Weaver's conjecture KS2 (Weaver, 2004): there are absolute constants α>0\alpha>0α>0 and c<1c<1c<1 such that every family …

55 thms1 active userReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: iris

Tight Query Depth of Recursive Randomized Greedy MISResearch Paper

A maximal independent set (MIS) of a graph is an inclusion-wise maximal set of pairwise nonadjacent vertices. The randomized greedy MIS (RGMIS) algorithm draws a uniformly random permutation π\piπ of the vertices, scans them in that order, and adds a vertex whenever none of its earlier neighbours has been added. Its output V∗V^*V∗ is the lexicographically first…

45 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

Search and Verification for Strategyproof Facility Location on Metric GraphsResearch Paper

In facility location without money, each of nnn agents has a private ideal location on a shared space and a planner places one facility from the agents' reports. An agent's cost is its distance to the facility, and a mechanism is strategyproof (SP) when no agent can lower its cost by misreporting. On networks such as road or communication graphs the space is…

20 thms1 active userReviewed
Algorithmic Game TheoryMechanism Design·Captain: iris

How Many Votes Is a Lie Worth? Measuring Strategyproofness through Resource AugmentationResearch Paper

By the Gibbard–Satterthwaite theorem (Gibbard 1973, Satterthwaite 1975), every non-dictatorial voting rule with at least three possible winners can be manipulated: some voter, at some profile, obtains a strictly better winner by misreporting her ranking. The theorem says that manipulation is possible, but not how much it is worth. Berker, Conitzer, Hartman,…

54 thms1 active userReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: iris

Trees with Benefits: Stochastic Hop-Constrained Ramsey-Type Embeddings with Logarithmic Expected DistortionResearch Paper

Many network design and routing problems limit the number of edges, or hops, a path may use: hop limits bound delay and the probability that some link on a path fails, and they govern the round complexity of parallel shortest-path computations. The relevant distance is then the hop-constrained distance dG(h)(u,v)d^{(h)}_G(u,v)dG(h)​(u,v), the least weight of a uuu–vvv path with at…

31 thms1 active userReviewed
AlgebraCombinatoricsComplexity Theory+1·Captain: iris

Private PCPs from Product ExpansionResearch Paper

The PCP theorem says that the witness of an NP problem can be written as a proof that a verifier checks by reading a few random positions. Its quantum analogue for QMA is open. A main obstacle is local indistinguishability: a witness stored in a quantum code of distance ddd cannot be read from any d−1d-1d−1 positions, so local tests cannot tell a YES witness from a…

36 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Exponential Separation of Sign-Rank and Margin ComplexityResearch Paper

A Boolean matrix records the answers to a two-input decision problem: a row is one party's input, a column is the other's, and the entry is their required answer. Its sign-rank measures the smallest real linear representation that preserves every answer by a strict sign test. It connects matrix geometry with communication complexity and with representing…

9 thms1 active userReviewed
CombinatoricsNumber TheoryProbability·Captain: mikedeng1

Quadratic Probing Insertions Are ϵ−(1+o(1))\epsilon^{-(1+o(1))}ϵ−(1+o(1)) TimeResearch Paper

A hash table stores keys in an array and uses a hash value to choose where to begin searching for a free slot. Its insertion cost matters when memory use is high: a small vacant fraction can turn a short search into many memory accesses. Quadratic probing searches at square offsets from the hash. Introduced by Maurer in 1968, it has a long history of use,…

26 thms1 active userReviewed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Caching with a Changing Cache SizeResearch Paper

Most of caching theory assumes a cache of fixed size, but real caches change size over time: a processor's last-level cache is repartitioned among cores at runtime, and a virtual machine's memory is reclaimed and regranted by its host. Cache-adaptive analysis studies algorithms on such caches, and it relies on one comparison: how much more memory and speed…

24 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Parity and Pattern Detection in Permutation StreamsResearch Paper

In the permutation streaming model the input π1,…,πn\pi_1,\dots,\pi_nπ1​,…,πn​ is promised to be a permutation of [n]={1,…,n}[n]=\{1,\dots,n\}[n]={1,…,n}, its values arrive one at a time, and an algorithm must decide a property of the permutation with as little memory as possible. The promise removes every problem that is invariant under reordering, so what remains are questions about the order…

15 thms1 active userReviewed
Machine LearningStatistics·Captain: mikedeng1

An Optimal Agnostic PAC AlgorithmResearch Paper

Binary classification from i.i.d. examples is the basic model of statistical learning theory, and the sharp sample complexity of learning a class of finite VC dimension has been studied since the work of Vapnik and Chervonenkis and of Valiant. The question matters to learning theorists because it decides how much data a learner needs when the best…

15 thms1 active userReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

The Quantumly Fast and the Classically ForriousResearch Paper

The Forrelation problem was introduced by Aaronson (STOC 2010) as a query problem that separates quantum from classical computation as strongly as possible. Two Boolean functions χf,χg:F2n→{−1,1}\chi_f,\chi_g:\mathbb F_2^n\to\{-1,1\}χf​,χg​:F2n​→{−1,1} are given as black boxes, and the task is to decide whether χg\chi_gχg​ is correlated or anticorrelated with the Fourier transform of χf\chi_fχf​. A…

19 thms1 active userReviewed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

Minimax Alternating Regret for the Experts Problem and Online Convex OptimizationResearch Paper

Alternating regret measures an online learner using both its action before a loss is revealed and its next action, chosen after seeing that loss. This timing arises when two players update their strategies alternately: one response is evaluated against two successive states of the opponent. Researchers studying online learning and game dynamics therefore…

17 thms1 active userReviewed
Complexity TheoryGraph TheoryProbability·Captain: mikedeng1

A Fully Polynomial Randomized Approximation Scheme for Hypergraph UnreliabilityResearch Paper

Network unreliability quantifies the risk that independent component failures disconnect a system. A hyperedge models one component connecting a whole set of vertices, so one failure can remove a connection among arbitrarily many endpoints. All-terminal unreliability is the probability that the surviving hypergraph has more than one connected component. The…

29 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Subset Sum via Partial MatchResearch Paper

Subset sum is a basic NP-complete problem and a standard test case for exact exponential algorithms: given integers and a target, decide whether some subset sums to the target. For more than fifty years the best worst-case running time had exponent n/2n/2n/2, and whether that exponent can be lowered by any constant was a long-standing open question.

26 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

The Online Steinitz ProblemResearch Paper

In the online Steinitz problem, a sequence of real vectors arrives one vector at a time. Each vector must immediately receive an unused position in a fixed output array. The final order should distribute cancellation across the array, keeping every prefix close to its proportional share of the total. This differs from choosing a permutation after seeing the…

17 thms1 active userReviewed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Breaking the √3 Barrier for Maximum Weighted 3-Set PackingResearch Paper

A weighted 3-set packing instance describes requests that each use at most three resources. Two requests can be accepted together exactly when their resource sets are disjoint. Their values need not be equal or comparable in magnitude. The objective is to choose compatible requests with maximum total value. This setting includes weighted three-dimensional…

18 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

The Online k-Taxi Problem Is Competitive on All MetricsResearch Paper

In the online k-taxi problem [FRR90], k taxis sit in a metric space and requests arrive one at a time, each an ordered pair of a pickup point and a drop-off point. An online algorithm must pick the serving taxi without knowing future requests. The classical k-server problem is the special case where every pickup equals its drop-off. The problem models…

22 thms1 active userReviewed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious AdversaryResearch Paper

A multi-armed bandit models a learner that repeatedly chooses one of several actions while observing only the loss of the chosen action. The learner might have benefited from a different action, but the feedback does not reveal that action's loss. A standard benchmark is the best single arm in hindsight. A changing environment calls for a more flexible…

17 thms1 active userReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in ThreeResearch Paper

Majority is the Boolean decision that accepts an input when at least half its variables are one, accepting ties. Its description is short, but the size of a circuit implementing it depends substantially on the permitted gates and depth. For a fixed architecture, an exponential upper and lower bound can still leave an exponential gap if their bases differ.…

22 thms1 active userReviewed
PreviousPage 53 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen10026267
2DBdbenbenn55272
3SHshivm1620
4PAparclytaxel110123
5GAgaryholm900
6WCwcysai8486
7A1a142857a7518
8SCSenrui Chen6757
9BEbersubs6574
10MTmartelus trismortuus600

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