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

101–125 of 1496
Open1377Completed119All1496
Linear algebraProbabilityRandom Matrix Theory+2·Captain: Shuze Chen

Near-Optimal Bounds for Sketching the Schatten NormsResearch Paper

A linear sketch compresses a large object by storing a few linear measurements of it, chosen at random before the object is seen, and answers a query from those measurements alone. Linear sketches are the standard model behind turnstile streaming and distributed aggregation: measurements of a sum are sums of measurements, so updates and merges are free. The…

25 thms4 active usersReviewed
CombinatoricscryptographyHarmonic Analysis+2·Captain: Shuze Chen

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial IntersectionResearch Paper

In Shamir secret sharing over a prime field Fp\mathbb F_pFp​, a secret sss is shared among nnn parties by a uniformly random polynomial PPP of degree at most kkk with P(0)=sP(0)=sP(0)=s; party iii receives P(αi)P(\alpha_i)P(αi​) for distinct nonzero evaluation points αi\alpha_iαi​. Any k+1k+1k+1 parties recover the secret and any kkk learn nothing about it. Local leakage resilience (LLR) asks for more: if…

24 thms4 active usersReviewed
Complexity TheorycryptographyQuantum Information+1·Captain: Shuze Chen

Information Loss Is All You Need: TC^0 Pseudorandomness from Worst-Case LatticesResearch Paper

Learning with errors (LWE) is the standard source of post-quantum hardness: given many noisy inner products As+e mod qA s + e \bmod qAs+emodq of a secret sss, distinguish them from uniform. Regev showed in 2005 that this is as hard, for quantum algorithms, as worst-case approximate lattice problems (Reg05). Removing the random error makes the samples deterministic: learning…

52 thms4 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

(1+ϵ)(1+\epsilon)(1+ϵ)-Distortion Spanning Tree Covers of Minor-Free Graphs with Size O(log⁡log⁡n)O(\log \log n)O(loglogn)Research Paper

A tree cover of a weighted graph approximates all of its shortest-path distances by a small number of trees: for every pair of vertices, some tree in the collection keeps their distance within a factor α\alphaα, the distortion, and no tree shortens any distance. Tree covers are a standard device for transferring tree algorithms to general graphs, with…

25 thms4 active usersReviewed
cryptographyInformation TheoryTheoretical Computer Science·Captain: Shuze Chen

Access Cost Tradeoffs in Mixed-Mode Oblivious RAMResearch Paper

An oblivious RAM (ORAM) lets a client keep an array on an untrusted server without revealing which logical addresses it accesses (Goldreich–Ostrovsky 1996). When every access is private, the price is known: with polynomially sublinear client memory, logarithmic overhead is necessary even for computational security (Larsen–Nielsen 2018). Many computations…

19 thms4 active usersReviewed
cryptographyQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Quantum Security of XOR of Permutations via Fourier AnalysisResearch Paper

Block ciphers are modelled as pseudorandom permutations, but many symmetric-key schemes, among them Wegman–Carter MACs and counter mode, are more secure when instantiated with a pseudorandom function. Constructing a pseudorandom function from random permutations (the "Luby–Rackoff backward" problem) is a long-standing line of work. The XOR of permutations an…

41 thms4 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

A classical oracle separation between QMA and QMA(2)Research Paper

QMA is the quantum analogue of NP: a polynomial-time quantum verifier receives a quantum proof (a witness) from an all-powerful prover. QMA(2) is the variant in which the verifier receives two quantum proofs that are promised to be unentangled, i.e. the joint witness is a product state ∣ψ1⟩⊗∣ψ2⟩|\psi_1\rangle\otimes|\psi_2\rangle∣ψ1​⟩⊗∣ψ2​⟩ (KMY03). Whether this promise adds…

32 thms4 active usersReviewed
Computational GeometryConvex OptimizationFunctional Analysis·Captain: mikedeng1

Deterministic Terminal Embedding with Optimal Target Dimension for Euclidean SpaceResearch Paper

A database of points can be reduced to fewer coordinates while approximately preserving distances among its stored points. Many geometric applications also compare those points with centers or queries supplied later. A guarantee only about pairs already in the database does not cover every such comparison. A terminal embedding asks for one map that…

26 thms4 active usersReviewed
Complexity TheoryInformation TheoryNumber Theory·Captain: mikedeng1

NP-Hardness of Bounded Distance Decoding for Reed–Solomon CodesResearch Paper

A Reed–Solomon code stores a message as the values of a low-degree polynomial at distinct points of a finite field. Decoding asks whether a received word is close to some codeword. The complexity of this question depends on how many errors are allowed, the field and the evaluation set. Unique decoding up to half the minimum distance and Guruswami–Sudan list…

23 thms4 active usersReviewed
CombinatoricsOptimization·Captain: mikedeng1

Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and MoreResearch Paper

Many problems on graphs ask for a linear arrangement of the vertices that keeps some "frontier" small. In Cutwidth, the frontier of a prefix of the arrangement is the set of edges leaving it; in Pathwidth (equivalently, vertex separation, by Kinnersley 1992), it is the set of prefix vertices that still have a neighbour outside the prefix. Both are classical…

48 thms4 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: mikedeng1

The list size of random linear and LDPC codes at capacityResearch Paper

A code C≤FqnC\le\mathbb F_q^nC≤Fqn​ is list-decodable when every Hamming ball of relative radius ρ\rhoρ contains few codewords; the number allowed is the list size. List decoding is the regime in which a code corrects a ρ\rhoρ fraction of adversarial errors up to the information-theoretic limit, the list-decoding capacity 1−hq(ρ)1-h_q(\rho)1−hq​(ρ). Random linear codes are the standard…

14 thms4 active usersReviewed
Complexity TheoryGraph TheoryOptimization·Captain: mikedeng1

A Simple Subquadratic Cut Query Protocol for Directed ReachabilityResearch Paper

A directed reachability question asks whether a sequence of directed edges leads from a specified source vertex to a specified target. Ordinary graph search answers it when outgoing neighbours can be inspected. A different question arises when the graph is hidden and an oracle reports only how many edges leave a chosen vertex set. This outgoing-cut oracle re…

29 thms4 active usersReviewed
Information TheoryMachine LearningProbability+1·Captain: Shuze Chen

Lower Bounds for Memorization, Privacy and Replicability from Not-So-Strong Data Processing InequalitiesResearch Paper

Top-kkk selection asks an algorithm to look at nnn data records and name kkk of mmm candidate coordinates whose means are nearly the largest. It is a basic subroutine of private and reproducible data analysis: choosing features, hypotheses, or queries before answering them. Two stability requirements are central for it. Differential privacy (Dwork, McSherry,…

25 thms4 active usersReviewed
CombinatoricsProbabilityStatistical Mechanics+1·Captain: Shuze Chen

Zero-Freeness for Random Regular Graphs up to the Replica Symmetry Breaking ThresholdResearch Paper

The hardcore model weights the independent sets of a graph: a set III of pairwise non-adjacent vertices gets weight λ∣I∣\lambda^{|I|}λ∣I∣, and the partition function ZG,fug(λ)=∑Iλ∣I∣Z_{G,\mathrm{fug}}(\lambda)=\sum_I\lambda^{|I|}ZG,fug​(λ)=∑I​λ∣I∣ is the independence polynomial of GGG. Since Lee and Yang (1952), phase transitions of a spin system are located through the complex zeros of its partition…

93 thms4 active usersReviewed
Computational ComplexityQuantum InformationStochastic Systems·Captain: iris

Quantum algorithms for stochastic nonlinear differential equationsResearch Paper

Fault-tolerant quantum computers are usually discussed for problems that are hard for classical computers in the absence of any noise. Bravyi, Byrne, Zayats, Zhuk and Zlokapa (arXiv:2606.08349) study a different role for noise: random perturbations of the problem rather than of the hardware. Their example is the estimation of an observable at the final time…

38 thms4 active usersReviewed
Algorithmic Game TheoryComputational ComplexityOptimization+1·Captain: Shuze Chen

On the Role of Geometry in Solving Variational InequalitiesResearch Paper

A variational inequality (VI) asks for a point of a convex set at which an operator points "outward": it unifies constrained optimization, Nash equilibria of continuous games and complementarity problems. For general continuous operators, finding an approximate VI solution is a total search problem in PPAD, the class of fixed-point problems that contains…

35 thms4 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Node Differential Privacy via Node-Stable Graph ProjectionsResearch Paper

Node-level differential privacy protects every individual of a network together with all of their connections: an algorithm on graphs is (ε,δ)(\varepsilon,\delta)(ε,δ)-node-private if adding or removing one vertex, with any set of incident edges, changes the law of its output only slightly (Blocki, Blum, Datta, Sheffet 2013; Kasiviswanathan, Nissim, Raskhodnikova,…

25 thms4 active usersReviewed
Computational ComplexityLinear algebraProbability+1·Captain: Shuze Chen

Worst-Case to Average-Case Reductions for Linear Algebra: Optimal, Simple, and GeneralResearch Paper

A worst-case to average-case reduction for a computational problem shows that an algorithm which is correct only on a fraction of random inputs can be turned into one that is correct, with high probability, on every input, at a small cost in running time. Such reductions say that a problem has no easy instances to hide behind: if it is hard at all, it is…

19 thms4 active usersReviewed
Complexity TheoryOptimizationTheoretical Computer Science·Captain: Shuze Chen

Optimal Approximation Algorithms For Satisfiable Ordering CSPsResearch Paper

An ordering problem asks for a single ranking that satisfies many local requirements. A requirement might say that one variable precedes another, or that one lies between two others. Even when a perfect ranking is promised to exist, an efficient algorithm may have difficulty finding it. Approximation asks what fraction of the requirements can always be…

29 thms4 active usersReviewed
CombinatoricsComputational ComplexityTheoretical Computer Science·Captain: Shuze Chen

The Complexity of UnpredictabilityResearch Paper

Catalytic logspace (CL) was introduced by Buhrman, Cleve, Koucký, Loff and Speelman (BCK+14): a logarithmic-space machine is given, in addition, a polynomially long read-write catalytic tape that starts with an arbitrary string chosen by an adversary and must hold exactly that string again when the machine halts. They showed that CL contains TC1\mathsf{TC}^1TC1,…

23 thms4 active usersReviewed
Complexity TheoryGraph TheoryOptimization+1·Captain: Shuze Chen

An O(n0.1537)O(n^{0.1537})O(n0.1537)-Coloring Algorithm for 333-Colorable GraphsResearch Paper

A graph is 3-colorable if its vertices can be labelled with three colors so that adjacent vertices get different labels. Deciding 3-colorability is NP-complete, and finding a 3-coloring of a graph known to be 3-colorable is no easier. The natural algorithmic question is therefore approximate: given a 3-colorable graph on nnn vertices, how few colors suffice…

28 thms4 active usersReviewed
Complexity TheorycryptographyTheoretical Computer Science·Captain: Shuze Chen

PPAD Hardness from SISResearch Paper

PPAD is the class of total search problems whose solutions are guaranteed by a parity argument on a directed graph of in- and out-degree at most one: if a source exists, another endpoint must exist. Computing a Nash equilibrium of a finite game is complete for it (Daskalakis–Goldberg–Papadimitriou 2009; Chen–Deng–Teng 2009). Since every instance has a…

24 thms4 active usersReviewed
Computational ComplexityMachine LearningTheoretical Computer Science·Captain: Shuze Chen

Intractability of Continual Learning using Parametric Models with Unlimited Replay BufferResearch Paper

In continual learning a model is trained on a stream of tasks t=1,…,Tt = 1, \dots, Tt=1,…,T and must keep performing well on every task seen so far; losing accuracy on earlier tasks is called catastrophic forgetting. A common remedy is a replay buffer that stores past data. With an unlimited buffer every earlier dataset remains available, so forgetting can no longer be…

18 thms4 active usersReviewed
Algorithmic Game TheoryCombinatoricsInformation Theory·Captain: mikedeng1

Switching and Entropy Bounds for Stable MatchingsResearch Paper

A market can have several stable outcomes even when every participant has a strict preference list. Finding one outcome answers a different question from counting all of them. The extremal stable-matching count asks how many stable outcomes one market can admit in the worst case. It measures the possible size of the entire solution set, without selecting an…

34 thms4 active usersReviewed
CombinatoricsInformation TheoryProbability+1·Captain: mikedeng1

List Decoding, Linear Hashing, and Furstenberg over Fq\mathbb{F}_qFq​Research Paper

A linear code is a subspace C≤FqnC\le\mathbb F_q^nC≤Fqn​. It is (p,L)(p,L)(p,L)-list decodable if every Hamming ball of radius pnpnpn contains at most LLL codewords: a receiver that sees a word with at most a ppp fraction of corrupted symbols can narrow the sent codeword down to a list of at most LLL candidates. The list decoding capacity theorem says that codes of rate …

26 thms4 active usersReviewed
PreviousPage 5 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