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.

1499 missions

Missions

1451–1475 of 1499
Open1321Completed178All1499
CombinatoricsQuantum InformationTheoretical Computer Science·Captain: iris

Quantum Copy Complexity of Testing Monotonicity and Other PropertiesResearch Paper

Property testing asks whether a small amount of information about an unknown object suffices to decide if it has a property or is far from having it. Monotonicity of Boolean functions on the hypercube is the standard test case of the field, studied with classical samples, classical queries and quantum queries (Goldreich et al. 2000; Khot–Minzer–Safra 2018; B…

24 thms1 active userReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

The Power of Test-Time Training for Approximate SamplingResearch Paper

A language model generates a sequence one token at a time, and a common way to improve it at inference time is to steer generation with a learned value function that scores partial sequences. Golowich, Moitra and Rohatgi model this as sampling: an unknown target distribution μ⋆\mu^\starμ⋆ on strings of length nnn is accessible only through an oracle μ^\hat\muμ^​ that…

32 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOptimization+1·Captain: iris

The Exact Welfare Guarantee of Fixed-Price Bilateral TradeResearch Paper

A seller owns one item and a buyer may want it; their values are private and independent. Myerson and Satterthwaite showed that no mechanism is at once efficient, incentive compatible, individually rational and budget balanced (MS83). The simplest mechanism that keeps every property but efficiency is a fixed price: post one price, and trade happens if both…

27 thms1 active userReviewed
CombinatoricsOptimizationTheoretical Computer Science·Captain: iris

Online and Fully-Dynamic SortingResearch Paper

Keeping data in order while it changes is a basic algorithmic task. In online sorting, introduced by Aamand, Abrahamsen, Beretta and Kleist (AABK23), real numbers arrive one at a time and must be placed immediately into an array of nnn cells; the aim is to keep the sum of absolute differences between neighbouring stored elements small compared with the sorted…

36 thms1 active userReviewed
AlgebraLinear algebraTheoretical Computer Science·Captain: iris

Burnside Problems for Matrix Semigroup Quotients with Applications to Border ComplexityResearch Paper

In 1902 Burnside asked whether a finitely generated group in which every element has finite order must be finite. The answer is negative in general (Novikov and Adian, 1968), but positive for groups of complex invertible matrices (Schur), for invertible matrices over any field (Kaplansky), and for finitely generated matrix semigroups over any field…

23 thms1 active userReviewed
Bandit AlgorithmsMachine LearningOperations Research·Captain: iris

Contextual Search and Bilateral Trade with a Trace-Square-Root PotentialResearch Paper

Contextual search models a seller who quotes a price for a product described by a feature vector and learns only whether the customer bought: a hidden vector determines a target value along each observed context, and the learner sees one bit per round, whether its guess was too high or too low. The problem arose from feature-based pricing and auctions…

18 thms1 active userReviewed
CombinatoricsComplexity TheoryProbability+1·Captain: iris

A dichotomy theorem for approximating CSPs in random-order streamsResearch Paper

A constraint satisfaction problem asks for an assignment of letters to variables satisfying as many given constraints as possible. In the single-pass streaming model, constraints arrive one at a time and an algorithm keeps limited memory between them. Classification results describe how approximation quality trades against memory when an adversary chooses…

37 thms1 active userReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: iris

Optimal High Probability Bounds for Random Order Online SortingResearch Paper

An online sorting algorithm receives nnn real numbers one at a time and must place each immediately and irrevocably into an empty cell of an array with exactly nnn cells. The objective is the total variation of the completed array. Offline, sorting gives the input range, so the natural measure is the competitive ratio. Related work allows more output cells than…

33 thms1 active userReviewed
Complexity TheoryQuantum InformationTheoretical Computer Science·Captain: iris

A Dichotomy for Boolean Complex Holant Problems with Conjugate-Closed Signature SetsResearch Paper

Computing output probabilities of a quantum circuit exactly, known as exact strong simulation, is a contraction of a tensor network that contains each gate tensor together with its entrywise complex conjugate. The natural counting framework for such contractions is the Holant problem: a signature grid assigns a tensor to each vertex of a graph, and the…

30 thms1 active userReviewed
CombinatoricsComplexity TheoryGraph Theory+1·Captain: iris

Real-to-Integer Reduction for All-Pairs Shortest PathsResearch Paper

All-Pairs Shortest Paths (APSP) asks, for a directed edge-weighted graph on nnn vertices with no negative cycles, for the length of a shortest path between every pair of vertices. The textbook Floyd–Warshall algorithm runs in time O(n3)O(n^3)O(n3) (Floyd 1962). APSP is one of the central problems of fine-grained complexity, and many problems are equivalent to it under…

25 thms1 active userReviewed
Quantum InformationTheoretical Computer Science·Captain: iris

Byzantine Agreement with Signature TokensResearch Paper

Byzantine agreement (BA) asks nnn parties, up to fff of them under an adversary's control, to decide a common bit. It is the core problem of fault-tolerant distributed systems and of blockchain consensus. In the partially synchronous model of Dwork, Lynch and Stockmeyer (JACM 1988), messages may be arbitrarily delayed until an unknown stabilization time, and…

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

Near-Optimal Almost-Ramsey Spanning Tree Covers, via Layered ClusteringsResearch Paper

A tree cover of a weighted graph replaces its shortest-path metric by a small collection of trees, so that every pair of vertices is well served by at least one of them. Tree covers underlie compact routing schemes, distance oracles and spanners, because a tree is far easier to store and to route on than a graph. The hardest variant asks for spanning trees,…

41 thms1 active userReviewed
Algorithmic Game TheoryOptimizationTheoretical Computer Science·Captain: iris

Arbitrarily Slow Polynomial Convergence of Fictitious PlayResearch Paper

Fictitious play (Brown, 1951) is one of the oldest dynamics for computing a Nash equilibrium of a two-player zero-sum game: at each step, each player best responds to the empirical distribution of the opponent's past actions. Robinson (1951) proved that the empirical strategies converge to the equilibrium set, and Shapiro (1958) extracted the upper bound …

31 thms1 active userReviewed
Complexity TheoryGraph TheoryProbability+1·Captain: iris

Connectivity in a New Bounded-Space Dynamic ModelResearch Paper

Undirected sss–ttt connectivity is a central test case for time–space tradeoffs on a read-only input. Breadth-first search takes linear time and Θ(n)\Theta(n)Θ(n) words. The random walk of Aleliunas et al. (1979) takes O(log⁡n)O(\log n)O(logn) bits and much longer. Feige (1997) and others charted the range in between, and Reingold (2008) showed that the problem is in deterministic…

32 thms1 active userReviewed
Complexity TheoryRepresentation TheoryTheoretical Computer Science·Captain: iris

Symmetric Circuits for Matrix MultiplicationResearch Paper

Fast matrix multiplication algorithms beat the n3n^3n3 operations of the schoolbook method by treating different parts of the input matrices differently. The schoolbook method, and the recursive four-block algorithm that splits each matrix into 2×22\times22×2 blocks, are instead invariant under simultaneously permuting the columns of AAA and the rows of BBB, or at least…

26 thms1 active userReviewed
Algorithmic Game TheoryCombinatoricsOperations Research+1·Captain: iris

Gross Substitutes Welfare in Random OrderResearch Paper

In the secretary problem a decision maker sees items one at a time in uniformly random order and must accept or reject each on arrival, irrevocably. Dynkin's rule (observe until a 1/e1/e1/e fraction has passed, then take the first record) selects the best of nnn items with probability 1/e1/e1/e, and no rule does better as n→∞n\to\inftyn→∞. The matroid secretary problem of…

27 thms1 active userReviewed
Graph TheoryTheoretical Computer Science·Captain: iris

Composable Content-Oblivious Leader Election on Eulerian GraphsResearch Paper

In a content-oblivious network every message may be corrupted arbitrarily, so a message carries no information beyond its arrival: communication reduces to pulses, and a node's behaviour may depend only on the ports at which pulses arrive. Censor-Hillel, Cohen, Gelles and Sela showed that any asynchronous algorithm can still be simulated on a…

32 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Optimal Dynamic Strings in Compressed SpaceResearch Paper

Many applications store large collections of highly repetitive strings: versioned documents, genome collections of one species, logs. Grammar compression represents a string by a small context-free grammar that derives only that string, and a dynamic strings data structure keeps a whole collection in such a form while supporting concatenation, splitting and…

19 thms1 active userReviewed
CombinatoricsLinear algebraRandom Matrix Theory+1·Captain: iris

A Walk from Free Probability to Matrix Discrepancy I: Matrix SpencerResearch Paper

Given real symmetric m×mm\times mm×m matrices A1,…,AnA_1,\dots,A_nA1​,…,An​ of operator norm at most one, how small can ∥∑iσiAi∥\|\sum_i\sigma_iA_i\|∥∑i​σi​Ai​∥ be made by a choice of signs σ∈{−1,1}n\sigma\in\{-1,1\}^nσ∈{−1,1}n? Random signs give 2nlog⁡(2m)\sqrt{2n\log(2m)}2nlog(2m)​ by the noncommutative Khintchine inequality. For diagonal matrices, which encode ordinary vector discrepancy, Spencer's theorem gives O(n)O(\sqrt n)O(n​) when …

41 thms1 active userReviewed
AlgebraAlgebraic GeometryComplexity Theory+1·Captain: iris

An Exponential Top Fan-In Hierarchy for Border Depth-4 CircuitsResearch Paper

A central question about constant-depth algebraic circuits is what one additional summand at the output gate buys. Deterministic identity testing for depth-3 circuits of top fan-in kkk runs in time polynomial in the size with an exponent that grows with kkk (Kayal and Saxena, 2007), so it is natural to ask whether the power of these circuits grows with kkk.…

41 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Counting and Sampling by Local Repair: From the Lovász Local Lemma to Random k-SATResearch Paper

The Lovász local lemma (Erdős–Lovász 1975) gives a condition under which rare, weakly dependent bad events can all be avoided: with probability at most ppp per event and at most DDD dependencies, ep(D+1)≤1ep(D+1)\le1ep(D+1)≤1 suffices. Existence is governed by the first-neighbourhood scale pDpDpD.

35 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Splay trees are almost dynamically optimalResearch Paper

Binary search trees maintain an ordered set under membership and predecessor queries. A balanced tree answers each query in Θ(log⁡n)\Theta(\log n)Θ(logn) time, which is optimal in the worst case, but on many access sequences far less time suffices: repeated, sequential or local accesses can be served at nearly constant cost per access. Dynamic optimality asks for a single…

24 thms1 active userReviewed
CombinatoricsComplexity TheoryLinear algebra+1·Captain: iris

A New Characterization of Streaming Decidability of Boolean CSPs Under DeletionsResearch Paper

A constraint satisfaction problem CSP(Γ)\mathrm{CSP}(\Gamma)CSP(Γ) asks whether nnn Boolean variables can satisfy a multiset of constraints drawn from a fixed finite set Γ\GammaΓ of relations. In the streaming model, constraints arrive one at a time and an algorithm keeps limited memory. With insertions only, the one-pass space of satisfiability is governed by…

32 thms1 active userReviewed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: iris

On the Cost of Set-Multilinearisation in Positive CharacteristicResearch Paper

An algebraic circuit computes a polynomial from variables and constants with additions and multiplications. Proving superpolynomial lower bounds against arbitrary circuits is the algebraic version of the central question of complexity theory, and depth reduction makes low-depth circuits a meaningful target: a strong enough bound for depth four would…

32 thms1 active userReviewed
Complexity TheoryLinear OptimizationTheoretical Computer Science·Captain: iris

Lifting Sherali-Adams Degree to Unary Sherali-Adams over Parities SizeResearch Paper

Proving superpolynomial lower bounds for AC0[2]\mathrm{AC}^0[2]AC0[2]-Frege, bounded-depth Frege with parity gates, is a long-standing open problem in proof complexity. Weaker systems that reason about parities are studied as steps towards it. Resolution over parities, Res(⊕), reasons with disjunctions of linear equations over F2\mathbb F_2F2​. Until recently its lower…

29 thms1 active userReviewed
PreviousPage 59 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23927601
2DBdbenbenn909166
3SHshivm1630
4PAparclytaxel150172
5LRlreyzin147148
6KMkmehltretter8212219
7MTmartelus trismortuus1050
8DUducloc990
9BOBoomShaKaLaaaKa93100
9IAI am wealthy935

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