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
CombinatoricsGraph Theory·Captain: mikedeng1

A Tight Space Lower Bound for Pivot-Based Distance OraclesResearch Paper

A distance oracle stores information about a graph so that later queries can estimate the distance between two vertices. Storing a separate answer for every pair can require quadratic space, even when the input graph itself has only linearly many edges. Allowing a multiplicative error creates a space–accuracy trade-off. The question addressed here concerns…

17 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Testing Implies Distance Estimation with Polynomial LossResearch Paper

An adjacency query reveals one bit of a graph: whether two specified vertices share an edge. When the graph is large, even reading its entire adjacency matrix can be prohibitive. Property testing asks whether a graph satisfies a specified condition or requires a substantial fraction of its adjacencies to be changed. Distance estimation asks for that…

16 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Breaking the Parity Barrier for Constant-Depth CircuitsResearch Paper

A Boolean circuit computes a bit by combining input bits through logical gates. Circuit complexity asks how many gates a specified function needs when its depth is restricted. Lower bounds separate computational resources even when the function itself is easy to evaluate. For circuits using AND and OR gates with unrestricted fan-in, parity has long provided…

36 thms1 active userReviewed
cryptography·Captain: mikedeng1

Byzantine Broadcast in O~(n2)\widetilde{O}(n^2)O(n2) CommunicationResearch Paper

A replicated service needs a precise rule for turning one participant's proposed bit into a common decision. Byzantine broadcast asks for such a rule even when faulty participants can send inconsistent messages, omit messages, or change their behavior after being corrupted. The receiver of a message cannot infer that other parties received the same message.…

26 thms1 active userReviewed
Graph TheoryProbability·Captain: mikedeng1

LOCAL LLL in poly(loglog n) RoundsResearch Paper

The variable Lovász Local Lemma concerns systems of constraints whose individual failures are rare and whose interactions are local. A variable may describe a color, a choice of a neighbor, or a random decision in another algorithm. Each constraint inspects its own variables. The aim is to select their values so that every constraint holds simultaneously.…

20 thms1 active userReviewed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

A QPTAS for Stochastic Scheduling of Bernoulli JobsResearch Paper

Scheduling systems often know a job's processing-time distribution before they know its realized duration. An adaptive policy chooses the next job after observing previous outcomes. For Bernoulli jobs, a job either completes immediately or occupies a machine for its full positive size. This isolates the scheduling risk created by a small probability of a…

25 thms1 active userReviewed
Complexity TheoryDiscrete GeometryOperations Research+1·Captain: mikedeng1

4-Block Integer Programming is in FPTResearch Paper

An integer program chooses integer values for variables subject to linear equations and bounds, while minimizing a specified objective. Models with repeated local constraints occur in scheduling, allocation and stochastic optimization. Their size can grow with the number of local blocks even when the form of each block stays small. A useful algorithm must…

14 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

An Ω~(log⁡nlog⁡m)\tilde \Omega(\log n \log m)Ω~(lognlogm) Information-Theoretic Lower Bound for Randomized Online Set CoverResearch Paper

A set cover selects sets whose union contains every required element, while minimizing the number selected. In its online version, requirements arrive over time and each must be covered immediately. A choice that looks economical on one prefix may prove unnecessary once more requirements arrive, but purchases cannot be reversed. The problem therefore…

10 thms1 active userReviewed
CombinatoricsProbability·Captain: mikedeng1

Distributed Lower Bounds via Automatic Self-ReductionResearch Paper

Round elimination is the main technique for proving lower bounds on the number of communication rounds that distributed algorithms need to solve local graph problems. Its core is a lifting theorem: from a TTT-round algorithm for a problem Π\PiΠ it builds a (T−1)(T-1)(T−1)-round algorithm for a derived problem R(Π)R(\Pi)R(Π). When R(Π)R(\Pi)R(Π) is Π\PiΠ again (a fixed point), iterating…

10 thms1 active userReviewed
Information Theory·Captain: mikedeng1

A Spectral Theory of Local-to-Global LeakageResearch Paper

Additive secret sharing splits a secret into random shares whose sum is the secret. It underlies linear secret sharing in cryptography (Ben-Or, Goldwasser, Wigderson 1988; Benhamouda et al. 2018) and masking in side-channel protection of hardware. In both fields the question is how much a physical observer learns about the secret from noisy observations of…

25 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Polylogarithmic Collective Tree ExplorationResearch Paper

A team exploring an unknown tree must decide how to divide its work while paying for travel between branches. Collective tree exploration models this coordination problem with mobile agents, unrestricted communication, and edges revealed when an agent visits an endpoint. Fraigniaud, Gąsieniec, Kowalski and Pelc introduced the synchronous problem and an…

22 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Associativity of Multiplication Is Hard for ResolutionResearch Paper

SAT and SMT solvers handle bit-vector arithmetic by bit-blasting: every bit becomes a Boolean variable and every multiplication a multiplier circuit, encoded as a CNF formula. Formulas that require reasoning about multiplication remain a known weak point of this approach in bounded model checking, arithmetic hardware verification and the verification of…

28 thms1 active userReviewed
Operations ResearchProbability·Captain: mikedeng1

Metric Facility Location under Batched Random OrderResearch Paper

Online metric facility location was introduced by Meyerson [Mey01]: clients of a metric space arrive one at a time, each must be connected irrevocably to an open facility on arrival, opening a facility at a permitted site yyy costs f(y)f(y)f(y), and connecting a client costs its distance. The arrival order decides what can be guaranteed. Under a uniformly random…

25 thms1 active userReviewed
Computational GeometryProbability·Captain: mikedeng1

Optimal Zonotope Containment via Adaptive Gaussian SamplingResearch Paper

A zonotope represents every sum of a finite collection of vectors when each vector's coefficient may vary independently between minus one and one. Such representations occur in reachability analysis and verification, where a geometric set describes a family of possible states. A basic question is whether all of those states belong to a prescribed outer…

13 thms1 active userReviewed
Complexity TheoryLinear algebra·Captain: mikedeng1

A Degree–Size Relation for Resolution over PolynomialsResearch Paper

Propositional proof complexity asks how long a proof that a formula is unsatisfiable must be in a given proof system. Lower bounds for stronger systems bear on the limits of SAT solvers built on those systems, and algebraic proof systems were connected early on to bounded-depth Frege systems with modular counting (Buss et al., 1996). For ordinary…

18 thms1 active userReviewed
CombinatoricsComplexity Theory·Captain: iris

A Full Complexity Dichotomy for Complex-Valued Boolean Holant ProblemsResearch Paper

A counting problem asks for the weighted number of global configurations satisfying local constraints; a complexity dichotomy decides, for every choice of local rules, whether the problem is computable in polynomial time or #P-hard. Boolean Holant problems are the most general Boolean framework in which such classifications are pursued: they contain…

48 thms1 active userReviewed
CombinatoricsProbability·Captain: iris

Approximation Algorithms for Satisfiable Phylogenetic CSPsResearch Paper

A phylogenetic constraint satisfaction problem asks for a rooted binary tree whose leaves are given variables and which satisfies as many local constraints as possible, each constraint prescribing the shape of the subtree induced on a few leaves. Such problems formalize the reconstruction of an evolutionary tree from information about small groups of…

43 thms1 active userReviewed
Graph Theory·Captain: iris

Reading between the levels: new tools for the Thorup–Zwick hierarchy and their applicationsResearch Paper

An approximate distance oracle (ADO) is a data structure built once from a graph that, given two vertices u,vu, vu,v, returns an estimate d^(u,v)\hat d(u, v)d^(u,v) of their distance. It has stretch α\alphaα if d(u,v)≤d^(u,v)≤α d(u,v)d(u, v) \le \hat d(u, v) \le \alpha\, d(u, v)d(u,v)≤d^(u,v)≤αd(u,v) for every pair. Oracles trade space, query time and stretch against each other.

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

Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed–Solomon CodesResearch Paper

A Reed–Solomon code of rate R=k/nR=k/nR=k/n consists of the evaluation vectors of polynomials of degree below kkk at nnn distinct points of a finite field Fq\mathbb F_qFq​ [RS60]. List decoding asks for every codeword within a given relative Hamming distance ρ\rhoρ of a received word. Information-theoretically, a code of rate RRR over a large alphabet can be list decoded up to…

26 thms1 active userReviewed
Complexity TheoryQuantum Information·Captain: iris

Improved Separations between Quantum and Classical Communication Complexity of Total FunctionsResearch Paper

Quantum communication complexity asks how much two parties gain by exchanging qubits instead of bits. For total Boolean functions f:{0,1}n×{0,1}n→{0,1}f:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}f:{0,1}n×{0,1}n→{0,1} the gap was long believed to be at most polynomial. Polynomial separations between randomized and quantum complexity were known, the largest being R(f)≥Q(f)3−o(1)R(f)\ge Q(f)^{3-o(1)}R(f)≥Q(f)3−o(1) (Bansal–Sinha;…

30 thms1 active userReviewed
CombinatoricsProbability·Captain: iris

A Nearly Linear-Time FPRAS for Counting KnapsackResearch Paper

Given nonnegative integer weights w1,…,wnw_1,\dots,w_nw1​,…,wn​ and a capacity TTT, the counting knapsack problem (#Knapsack) asks how many subsets of the items fit: the size of the family of feasible subsets Ω\OmegaΩ. The problem is the counting version of 0/1 knapsack and, equivalently, counts the points of the Boolean cube below a halfspace, an object studied in learning…

16 thms1 active userReviewed
Complexity TheoryInformation TheoryProbability·Captain: iris

Non-Interactive Cryptography over Noisy Channels from Indistinguishability ObfuscationResearch Paper

A noisy channel produces randomness that no party chose and no party fully observes. Wyner's wiretap channel (Wyner 1975) used this to send a message confidentially without a shared key, and a long line of work showed that noise is a resource for secure computation as well. One-way communication is the setting where this resource matters most: a sender…

57 thms1 active userReviewed
CombinatoricsQuantum Error CorrectionQuantum Information·Captain: iris

Asymptotically Good Quantum Locally Testable CodesResearch Paper

A quantum locally testable code (qLTC) is a quantum error-correcting code whose membership can be checked by measuring a few qubits at a time, with a rejection probability proportional to the distance from the code. Classical locally testable codes underlie the PCP theorem and property testing; their quantum analogue was proposed by Aharonov and Eldar (AE15)…

48 thms1 active userReviewed
Complexity TheoryQuantum InformationRandom Matrix Theory·Captain: iris

Lower Bounds for Preprocessing Attacks on Quantum CryptographyResearch Paper

Cryptographic hash functions are analysed in the random oracle model, where the hash is a uniformly random function RRR that every party may query. An attacker who knows the hash function in advance may spend unbounded time precomputing advice about RRR before it sees its challenge; security against such preprocessing attacks (non-uniform security) is what…

36 thms1 active userReviewed
Complexity Theorycryptography·Captain: iris

From Degree Three to Degree Two: Statistical Randomized Encodings for All FunctionsResearch Paper

A randomized encoding of a function fff replaces f(x)f(x)f(x) by a randomized value f^(x;r)\hat f(x;r)f^​(x;r) from which f(x)f(x)f(x) can be decoded and which reveals nothing else about xxx. Encodings are useful when f^\hat ff^​ is much simpler than fff, and in secure multiparty computation the relevant measure of simplicity is the algebraic degree of f^\hat ff^​ over F2\mathbb F_2F2​, jointly in the input…

31 thms1 active userReviewed
PreviousPage 31 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