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
🏆Completed
Complexity TheoryInformation Theory·Captain: iris

Fourier Entropy Bounds via ApproximationsResearch Paper

A Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\}f:{−1,1}n→{−1,1} has a unique Fourier expansion f=∑S⊆[n]f^(S)χSf=\sum_{S\subseteq[n]}\widehat f(S)\chi_Sf=∑S⊆[n]​f​(S)χS​, and by Parseval's identity the squared coefficients {f^(S)2}S\{\widehat f(S)^2\}_S{f​(S)2}S​ form a probability distribution on subsets of [n][n][n]. Its Shannon entropy, the Fourier entropy H(f^2)\mathbb H(\widehat f^2)H(f​2), measures how spread out the spectrum of fff is.

21 thms2 active usersReviewed
CombinatoricsComplexity TheoryProbability·Captain: iris

A Deterministic Approximation Scheme for Counting Read-Twice CNF AssignmentsResearch Paper

A CNF formula is read-twice when every variable has at most two literal occurrences, with any signs and any clause lengths. Two classical counting problems are special cases. If the two occurrences of every repeated variable have the same sign, complementing variables gives the monotone edge-cover model; if they have opposite signs, the clauses describe sink…

26 thms2 active usersReviewed
Linear algebraQuantum Information·Captain: iris

Optimal Quantum de Finetti Theorems via Argmax RoundingResearch Paper

A quantum de Finetti theorem says that the few-site marginals of a permutation-symmetric many-site quantum state are close to mixtures of product states. Such theorems are the standard tool for reducing statements about symmetric or highly extendible states to statements about product states: they underlie the analysis of the Doherty–Parrilo–Spedalieri…

49 thms2 active usersReviewed
Graph TheoryProbabilityRandom Matrix Theory·Captain: iris

Bethe Hessian Recovery through the Kesten–Stigum RegimeResearch Paper

The stochastic block model (SBM) is the standard test case for graph partitioning: vertices carry hidden community labels, and edges appear independently with probabilities that depend on the labels. In the sparse regime, where every vertex has bounded expected degree ddd, exact recovery is impossible (some vertices are isolated), and the question is weak…

38 thms2 active usersReviewed
CombinatoricsProbability·Captain: iris

Temporal Aggregation: Maintaining Randomness against Adaptive AdversariesResearch Paper

Many dynamic algorithms keep a random object alive while the input changes: random walks used for routing in expanders, random palettes for graph coloring, random paths for oblivious routing. Their analysis is usually static: if every object is sampled once, at the same moment, from its current distribution, then some load (edge congestion, the number of…

14 thms2 active usersReviewed
Computational GeometryOperations ResearchOptimization·Captain: iris

Inapproximability of Euclidean Steiner TreeResearch Paper

The Euclidean Steiner Tree problem asks for a shortest network connecting nnn given points (terminals) in Rd\mathbb R^dRd, where additional Steiner points may be placed anywhere. It goes back to the Fermat–Torricelli problem, and it is NP-hard already in the plane (Garey, Graham and Johnson, 1977). In fixed dimension it admits a polynomial-time approximation…

30 thms2 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: iris

NP-hardness of additive approximation for generalized Turán problemsResearch Paper

Graph modification problems ask how far an input graph is from a property. For the property of being F\mathcal FF-free, Alon, Shapira and Sudakov proved that when no member of the family F\mathcal FF is bipartite, the minimum number of edge deletions that make a graph F\mathcal FF-free is NP-hard to compute, and even to approximate within an additive error …

34 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: iris

Online Beck–Fiala Down to Logarithmic SparsityResearch Paper

The Beck–Fiala problem asks how well the columns of a sparse matrix can be balanced by signs: given vectors a1,…,aT∈[−1,1]na_1,\dots,a_T\in[-1,1]^na1​,…,aT​∈[−1,1]n, each with at most ddd nonzero coordinates, choose εt∈{−1,1}\varepsilon_t\in\{-1,1\}εt​∈{−1,1} so that ∥∑tεtat∥∞\|\sum_t\varepsilon_ta_t\|_\infty∥∑t​εt​at​∥∞​ is small. The conjectured answer, O(d)O(\sqrt d)O(d​) independently of nnn and TTT, is one of the central questions of…

14 thms2 active usersReviewed
CombinatoricsProbability·Captain: iris

Testing Monotonicity of Real-Valued Functions on DAGsResearch Paper

Testing monotonicity is a standard problem in property testing: decide from a small number of function values whether a function respects a partial order or is far from every function that does. It was first studied on the Boolean hypercube and on product domains (Goldreich, Goldwasser, Lehman, Ron and Samorodnitsky, Combinatorica 2000), and later on…

38 thms2 active usersReviewed
Complexity TheoryMachine Learning·Captain: iris

New Gate, Weight and Wire Complexity Bounds for Sigmoid Neural NetworksResearch Paper

Neural networks with the sigmoid activation are real-valued circuits, and their expressive power can be compared directly with that of the Boolean threshold circuits studied in complexity theory. Parity is the classical test case. Threshold circuits of any constant depth need super-linearly many wires to compute it (Impagliazzo, Paturi, Saks 1997), even on…

34 thms2 active usersReviewed
Information TheoryProbability·Captain: iris

On the most informative Boolean function under noiseResearch Paper

A uniformly random string X∈{0,1}nX\in\{0,1\}^nX∈{0,1}n is sent through a binary symmetric channel: each coordinate is flipped independently with probability ppp, producing YYY. A single bit CCC is then computed from YYY. How much can one bit of the noisy output reveal about the input? Courtade and Kumar asked this in 2013 and conjectured that a dictator bit C=Y1C=Y_1C=Y1​ is optimal:

24 thms2 active usersReviewed
Complexity TheoryNumber Theory·Captain: iris

Doubly-Efficient Private Information Retrieval from Modular FormsResearch Paper

A private information retrieval (PIR) protocol lets a user read bit iii of an nnn-bit database held by sss servers, while each server learns nothing about iii (Chor, Goldreich, Kushilevitz, Sudan 1995). If the servers store only the database, every server must touch every bit: otherwise it learns which locations the user is not reading (Beimel, Ishai, Malkin 2004). …

30 thms2 active usersReviewed
Complexity TheoryNumber Theory·Captain: iris

Deterministic Construction of Primes in Subexponential TimeResearch Paper

With randomness, finding an nnn-bit prime is easy: sample O(n)O(n)O(n) integers and test each with the polynomial-time test of Agrawal, Kayal and Saxena. Deterministically, the problem is a standard example of an explicit construction: the property is dense and decidable in polynomial time, yet no fast procedure was known to produce a member of it. It is Open Problem…

38 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: iris

Lipschitz Stable Combinatorial AuctionsResearch Paper

Welfare-maximizing auctions are discontinuous. With two bidders and one item, the values (1+δ,1)(1+\delta,1)(1+δ,1) send the item to the first bidder and the values (1,1+δ)(1,1+\delta)(1,1+δ) send it to the second, however small δ\deltaδ is. Reports are often estimates, and sellers and buyers act on the probabilities of an allocation before it is realized, so such a jump makes plans…

57 thms2 active usersReviewed
Graph TheoryMarkov ChainProbability·Captain: iris

A simple proof of rapid mixing on random regular graphs beyond uniquenessResearch Paper

The hard-core model on a graph is the distribution on independent sets weighted by λ∣I∣\lambda^{|I|}λ∣I∣, and it is the central test case for sampling from distributions on combinatorial structures. Glauber dynamics, which resamples one vertex at a time, is the standard sampler. As surveyed in §1 of arXiv:2606.27545, on graphs of maximum degree Δ\DeltaΔ the…

31 thms2 active usersReviewed
Graph TheoryOperations ResearchOptimization·Captain: iris

Nearly Exact Length Bounds for Directed Steiner Tree and Forest in Planar GraphsResearch Paper

In length-constrained network design one buys arcs of a graph so that every demand can be routed along a short path. Each arc carries two separate numbers, a purchase cost and a travel length, and the bought arcs are shared: an arc used by many demands is paid once. The difficulty is that sharing and shortness pull in opposite directions. Buying each…

66 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

A tight approximation for metric k-means via squared tapered roundingResearch Paper

Metric k-means with candidate centers asks for kkk centers, chosen from a given finite set of candidates, that minimize the sum of squared distances from the clients to their nearest chosen center. It is the discrete, general-metric version of the k-means clustering objective, and a standard test case for LP rounding in approximation algorithms.

29 thms2 active usersReviewed
CombinatoricsComplexity Theory·Captain: iris

Optimal Shallow Circuits for MajorityResearch Paper

Constant-depth circuits (AND and OR gates of unbounded fan-in over input literals, arranged in a fixed number of layers) are the model in which complexity theory has its strongest unconditional lower bounds. Håstad's switching lemma (Håstad 1986) shows that Parity needs depth-ddd circuits of size 2Ω(n1/(d−1))2^{\Omega(n^{1/(d-1)})}2Ω(n1/(d−1)), and a divide-and-conquer construction (…

20 thms2 active usersReviewed
Information TheoryMachine Learning·Captain: iris

Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data SharingResearch Paper

Two organizations that each hold a labelled dataset often want to know, before any costly data-sharing agreement, whether their data are compatible: whether one classifier from a fixed class fits both datasets at once. Answering this question by exchanging the data defeats its purpose, since the records are private. Haghifam, Patel, Blum, Fanti and Ziani (ar…

30 thms2 active usersReviewed
CombinatoricsComplexity TheoryInformation Theory·Captain: iris

Low-Error ExtractorsResearch Paper

A randomness extractor turns a weak random source into nearly uniform bits. Since no deterministic function extracts from a single weak source, the two-source extractor takes two independent sources: a deterministic function 2Ext:{0,1}n×{0,1}n→{0,1}m\mathrm{2Ext}:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^m2Ext:{0,1}n×{0,1}n→{0,1}m such that, whenever X,Y\mathbf X,\mathbf YX,Y are independent with min-entropy at least kkk,…

45 thms2 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryProbability·Captain: iris

Discrepancy for Random Linear CodesResearch Paper

A random linear code of length nnn and dimension kkk over the finite field Fq\mathbb F_qFq​ is the column space of a uniformly random matrix G∈Fqn×kG\in\mathbb F_q^{n\times k}G∈Fqn×k​. Such codes serve as the default object against which explicit constructions in coding theory and pseudorandomness are measured. Many of their good properties are statements of the same kind: the…

28 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: iris

A Constant Approximation for Min-sum k-ClusteringResearch Paper

Clustering a finite metric space into kkk groups is a basic primitive of data analysis and operations research. Among the kkk-clustering objectives, min-sum kkk-clustering charges every cluster the sum of the pairwise distances inside it. Unlike kkk-median or kkk-means it uses no centers, so it is the natural objective when only pairwise dissimilarities are available…

40 thms2 active usersReviewed
🏆Completed
Complexity TheoryMathematical Logic·Captain: iris

Progress on AC0[2]-Frege Lower BoundsResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR, NOT and parity (MOD 2) gates. Proving superpolynomial lower bounds on the size of AC0[2]-Frege refutations of explicit unsatisfiable CNFs is one of the central open problems of proof complexity: the corresponding question for circuits was settled by…

36 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebraOperations Research·Captain: iris

The k-server conjecture is trueResearch Paper

The kkk-server problem, introduced by Manasse, McGeoch and Sleator in 1988 (MMS88), is the central problem of competitive analysis: kkk servers sit at points of a metric space, requests arrive one at a time at points of the space, and an online algorithm must move a server to each request before seeing the next one, minimizing the total distance travelled.…

31 thms2 active usersReviewed
CombinatoricsGraph TheoryLinear algebra·Captain: iris

Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with ApplicationsResearch Paper

A sensitivity oracle preprocesses a graph once so that, after a batch of at most fff edge failures or insertions arrives, a question about the modified graph is answered without recomputing from scratch. Networks fail a few links at a time, and the planner wants the new maximum throughput, the new bottleneck cut, or the new cheapest routing at once. For…

51 thms2 active usersReviewed
PreviousPage 37 of 58Next

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