Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Theoretical Computer Science

1,446 missions · 603 completed

The mathematical foundations of computation: which problems can be solved, by what algorithms, and at what cost in time, space, or communication. Distinguished by its emphasis on rigor and unconditional lower bounds, it spans computational complexity, algorithm design, automata and computability, cryptography, and the analysis of Boolean functions.

Missions

Open843Completed603All1446
Complexity TheoryLinear algebraMarkov Chain·Captain: iris

Hardness Self-Amplification in Linear Algebra and Fine-Grained CryptographyResearch Paper

Fine-grained cryptography asks for primitives secure only against adversaries of moderate polynomial running time. One natural candidate is the map f(M,x)=(M,Mx)f(M,x)=(M,Mx)f(M,x)=(M,Mx): evaluating it takes Θ(n2)\Theta(n^2)Θ(n2) field operations, while the best known way to invert it solves a linear system in nω+o(1)n^{\omega+o(1)}nω+o(1) operations, where ω\omegaω is the matrix multiplication exponent (Alm…

26 thms2 active usersReviewed
CombinatoricsOperations ResearchProbability·Captain: iris

When Does Private Data Collection Need Interaction? Online Selection under Local Differential PrivacyResearch Paper

Platforms that select contributions under limited resources increasingly see their users only through randomized reports. Federated learning systems choose participants for each round from signals of local utility, crowdsourcing assigns arriving workers to tasks of limited capacity, and large telemetry deployments run client-side randomization as the…

34 thms2 active usersReviewed
CombinatoricsOptimizationProbability·Captain: iris

Optimal Vertex Sampling for Constraint Satisfaction ProblemsResearch Paper

How many variables of a constraint satisfaction problem must be inspected to estimate its optimum? The natural estimator picks kkk of the nnn variables uniformly at random, solves the subproblem induced on them, and multiplies its optimum by (n/k)r(n/k)^r(n/k)r, where rrr is the arity. This estimator underlies the approximation schemes for dense instances (Arora–Karger–Karpin…

33 thms2 active usersReviewed
CombinatoricsConvex OptimizationOptimization·Captain: iris

Iterative Rounding for Determinant Maximization and Real Stable PolynomialsResearch Paper

In matroid-constrained determinant maximization one is given vectors v1,…,vn∈Rdv_1,\dots,v_n\in\mathbb R^dv1​,…,vn​∈Rd and a matroid M\mathcal MM on [n][n][n], and seeks a base BBB maximizing det⁡(∑i∈Bvivi⊤)\det(\sum_{i\in B}v_iv_i^\top)det(∑i∈B​vi​vi⊤​). The problem appears as D-optimal design in statistics, in determinantal point processes, in Nash social welfare, and in convex geometry. The determinant is one…

25 thms2 active usersReviewed
AlgebraComplexity Theory·Captain: iris

Faster Power Series Composition in Fixed Positive CharacteristicResearch Paper

Truncated power series composition asks, given the coefficients of an outer polynomial f(y)=∑i<mfiyif(y)=\sum_{i<m}f_iy^if(y)=∑i<m​fi​yi and an inner polynomial g(x)=∑j<ngjxjg(x)=\sum_{j<n}g_jx^jg(x)=∑j<n​gj​xj over a commutative ring RRR, for the first nnn coefficients of f(g(x))f(g(x))f(g(x)). It is a basic operation of computer algebra: with f=F mod ynf=F\bmod y^nf=Fmodyn and g=G mod xng=G\bmod x^ng=Gmodxn for power series with G(0)=0G(0)=0G(0)=0 it computes F(G(x)) mod xnF(G(x))\bmod x^nF(G(x))modxn…

28 thms2 active usersReviewed
Information TheoryProbability·Captain: iris

Optimal Communication for Distributed Sparse Histogram AggregationResearch Paper

Histogram estimation asks how often each item of a large universe occurs in a collection of data; it underlies stream summaries, frequent-item identification and counting queries. When the data are spread over many users, a server learns the frequencies from short messages, and the question is how many bits an accurate aggregate requires. A typical regime…

45 thms2 active usersReviewed
Graph TheoryLinear algebra·Captain: iris

Efficient Algorithms for Minrank and Index Coding for Low-Treewidth GraphsResearch Paper

The minrank of a graph was introduced by Haemers as an upper bound on the Shannon capacity. Its main motivation today is index coding: a sender broadcasts a string x∈Fqnx \in \mathbb F_q^nx∈Fqn​ to nnn receivers, receiver iii wants xix_ixi​ and already knows the coordinates indexed by its out-neighbours in a knowledge graph GGG, and the question is how short the broadcast can…

49 thms2 active usersReviewed
Algebraic TopologyCombinatoricsGraph Theory·Captain: iris

Improved Lower Bounds on Tree CoversResearch Paper

A tree cover approximates a finite metric by a few trees instead of one. For an nnn-point metric space (X,d)(X, d)(X,d), an (α,k)(\alpha, k)(α,k)-tree cover is a family of kkk edge-weighted trees T1,…,TkT_1, \dots, T_kT1​,…,Tk​ on the vertex set XXX such that every tree dominates the metric, dTi(x,y)≥d(x,y)d_{T_i}(x,y) \ge d(x,y)dTi​​(x,y)≥d(x,y), and every pair x,yx, yx,y is approximated within a factor α\alphaα in at least one tree.…

36 thms2 active usersReviewed
Machine LearningMathematical PhysicsQuantum Information·Captain: iris

The stationarity test: a framework for learning quantum many-body systems from their thermal statesResearch Paper

A quantum many-body system at thermal equilibrium is described by the Gibbs state ρH=e−βH/tr⁡e−βH\rho_H=e^{-\beta H}/\operatorname{tr}e^{-\beta H}ρH​=e−βH/tre−βH of its Hamiltonian HHH at inverse temperature β\betaβ. Hamiltonian learning asks to recover HHH from copies of ρH\rho_HρH​. It is an inverse problem in quantum physics, a primitive for certifying quantum simulators, and a quantum analogue…

31 thms2 active usersReviewed
Machine LearningProbability·Captain: iris

Replicable Parity Learning: Cubic Sample Complexity and a Geometric CharacterizationResearch Paper

A randomized learning algorithm is replicable if two runs that share their internal random seed but receive independent samples from the same distribution return the same output with high probability. Impagliazzo, Lei, Pitassi and Sorrell introduced the notion as a guard against results that change when an experiment is repeated on fresh data (ILPS22). It…

34 thms2 active usersReviewed
CombinatoricsComplexity TheoryProbability·Captain: iris

Frequency Moments Beyond Equality: Streaming Cosine Density MomentsResearch Paper

The frequency moments Fk=∑xfxkF_k=\sum_x f_x^kFk​=∑x​fxk​ of a data stream, where fxf_xfx​ counts the occurrences of item xxx, are the founding problem of streaming algorithms (Alon, Matias, Szegedy 1999). They measure how concentrated a stream is under equality: two items interact only if they are identical. Streams of embeddings, documents and feature vectors call for a softer…

35 thms2 active usersReviewed
Probability·Captain: iris

Local Search with Correlated RandomnessResearch Paper

Randomized local search is usually analysed with fresh, independent random bits at every step. Real executions draw their randomness from a single stream that may be biased, correlated, or partly predictable, and an algorithm cannot extract clean bits from such a stream without a seed of its own: for the semi-random sources of Santha and Vazirani no…

31 thms2 active usersReviewed
Complexity Theory·Captain: iris

On the Power of Polynomial Calculus over Non-Boolean DomainsResearch Paper

Polynomial calculus (PC) is an algebraic proof system: to show that a set of polynomials has no common root, one derives the constant 111 from them by linear combinations and multiplication by variables. It is the proof-theoretic counterpart of Gröbner-basis computations and of algebraic SAT solvers, and size lower bounds for it are lower bounds on the…

56 thms2 active usersReviewed
Algorithmic Game TheoryCombinatoricsMechanism Design·Captain: iris

The Hardness of Dominant Strategy Mechanism Design, RevisitedResearch Paper

In a combinatorial auction, mmm items are allocated among nnn bidders, each holding a private valuation of bundles, and the goal is high welfare ∑ivi(Si)\sum_i v_i(S_i)∑i​vi​(Si​). Two obstacles interact: the bidders must communicate for a good allocation to be found, and they may manipulate the protocol. A mechanism is truthful when following the prescribed strategy is an…

29 thms2 active usersReviewed
CombinatoricsComplexity Theory·Captain: iris

Lossless Hardness Condensation in Deterministic Communication ComplexityResearch Paper

In two-party communication complexity, Alice holds a row x∈Xx\in Xx∈X, Bob holds a column y∈Yy\in Yy∈Y, and they must compute a Boolean entry M(x,y)M(x,y)M(x,y) by exchanging bits. The input sets can be far larger than the cost: a problem of cost ccc may have inputs of length much more than ccc. A basic structural question is whether the difficulty of a problem is already visible on a…

24 thms2 active usersReviewed
Complexity TheoryNumerical AnalysisProbability·Captain: iris

Delegating Computation with Approximate Arithmetic: Interactive Proofs for WizardsResearch Paper

Interactive proofs let a computationally weak verifier check a computation carried out by an untrusted prover (Goldwasser–Micali–Rackoff 1989, Babai 1985). The protocol of Goldwasser, Kalai and Rothblum (GKR, JACM 2015) makes this efficient for both parties for arithmetic circuits over a finite field: the prover runs in time polynomial in the circuit size,…

26 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: iris

Kendall–tau Center Admits a PTASResearch Paper

Rank aggregation combines several rankings of the same candidates into one. Voting, meta-search and the combination of classifier outputs all produce such inputs. The center version of the problem asks for a ranking that is close to every input at once: it minimizes the largest disagreement with any input, not the average one. This makes it the natural…

38 thms2 active usersReviewed
Computational GeometryMachine Learning·Captain: iris

Parallel Hierarchical Agglomerative Clustering in Low DimensionsResearch Paper

Hierarchical agglomerative clustering (HAC) is a greedy bottom-up clustering method available in SciPy, scikit-learn, fastcluster, R, MATLAB and other data science libraries. Its output, a dendrogram, can be cut at any level to obtain clusterings with any number of clusters, so users need not fix the number of clusters in advance. Different linkage functions…

26 thms2 active usersReviewed
Computational GeometryDiscrete GeometryOperations Research·Captain: iris

Constant Approximation Algorithms for Knapsack and Bin Packing for Convex PolygonsResearch Paper

Geometric knapsack asks which objects of a given family fit together in a limited region. It models cutting and nesting problems, where allowing rotations can improve material use. For axis-aligned rectangles, with or without quarter turns, constant-factor approximations have long been known. Under arbitrary rotations the problem was much less understood:…

46 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: iris

Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász TheoremResearch Paper

Partitioning a graph into connected pieces of prescribed sizes, each containing a designated root, is a basic primitive in network design, districting and load balancing, and in the analysis of confluent flows. The Győri–Lovász theorem says when this is always possible. Győri proved it for undirected kkk-connected graphs (Győri 1976), and Lovász gave a…

44 thms2 active usersReviewed
CombinatoricsGraph TheoryMathematical Logic·Captain: iris

Monadically Dependent Graph Classes Have Almost Bounded Merge-WidthResearch Paper

First-order model checking asks, given a graph GGG and a first-order sentence φ\varphiφ, whether φ\varphiφ holds in GGG. A central conjecture states that this problem is fixed-parameter tractable on every monadically dependent graph class: a class that cannot encode all graphs through a fixed formula over vertex-colored members. Planar graphs, classes of bounded…

41 thms2 active usersReviewed
Graph TheoryProbability·Captain: iris

Smoothed Analysis for Distributed MISResearch Paper

A maximal independent set (MIS) is a basic symmetry-breaking object in distributed computing. Luby's algorithm (Luby 1986) finds one in O(log⁡n)O(\log n)O(logn) rounds, and for decades no substantially faster algorithm for general graphs was known. Khoury and Schild (arXiv:2610.18215) showed that Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n)Ω(logn/loglogn) rounds are necessary on some graphs in the LOCAL…

28 thms2 active usersReviewed
Complexity TheoryLinear algebraQuantum Information·Captain: iris

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is TightResearch Paper

Quantum algorithms for linear algebra access a dense matrix AAA through quantum random access memory and prepare a state proportional to the solution of a linear system (Harrow, Hassidim, Lloyd 2009; Kerenidis, Prakash 2017; Gilyén, Su, Low, Wiebe 2019). Their cost depends on the normalized Frobenius norm ρ=∥A∥F/∥A∥\rho = \|A\|_F/\|A\|ρ=∥A∥F​/∥A∥ and the condition number …

32 thms2 active usersReviewed
CombinatoricsLinear OptimizationOperations Research·Captain: iris

Fitting Ultrametrics under any ℓp\ell_pℓp​ ObjectiveResearch Paper

An ultrametric is a distance in which, in every triangle, the two largest sides are equal. Equivalently, it is the leaf-to-leaf distance of a rooted tree whose leaves are all at the same depth, so an ultrametric is the same data as a hierarchical clustering. Fitting one to noisy pairwise measurements is a basic problem of numerical taxonomy: Cavalli-Sforza…

25 thms2 active usersReviewed
CombinatoricsInformation Theory·Captain: iris

Marton's conjecture in polynomial timeResearch Paper

A finite set A⊆F2nA\subseteq\mathbb F_2^nA⊆F2n​ has doubling constant KKK when ∣A+A∣≤K∣A∣|A+A|\le K|A|∣A+A∣≤K∣A∣. Marton's conjecture, also called the polynomial Freiman–Ruzsa (PFR) conjecture, asserts that such a set is essentially a subspace up to polynomial losses: there is a subspace VVV with ∣V∣≤∣A∣|V|\le|A|∣V∣≤∣A∣ such that AAA is covered by KO(1)K^{O(1)}KO(1) translates of VVV. It was proved by Gowers, Green,…

27 thms2 active usersReviewed
PreviousPage 25 of 34Next

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