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
CombinatoricsOptimization·Captain: iris

Improved Integrality Gap for Multicommodity Flow on TreesResearch Paper

Unit-demand multicommodity flow on trees is a basic routing problem in approximation algorithms. A tree network has integer edge capacities, and each request asks to route one unit between two vertices along the unique tree path joining them. The goal is to accept a maximum-weight set of requests without exceeding any capacity. The problem is NP-hard and…

42 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope SchedulingResearch Paper

Many computing and production systems share resources among jobs whose sizes are unknown when they arrive: a cluster splits processors among tasks, a network splits link capacity among flows, a factory splits machines among orders. A scheduler that never learns a job's size until the job finishes is called nonclairvoyant. On a single machine the right…

23 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Planning Against a Prophet: A Graph-Theoretic Framework for Making Sequential Decisions: On a DAG Covered by k Paths with at Most d Labels per Edge, an Online Policy Earns 1/(k(d+2)) of the ProphetResearch Paper

A prophet inequality compares a decision-maker who sees random values one at a time and must commit as they go with a prophet who sees every value in advance. The classic result of Krengel and Sucheston (1978) says that for independent non-negative values X1,…,XnX_1,\dots,X_nX1​,…,Xn​, an online rule that stops once can collect at least half of E[max⁡iXi]\mathbb E[\max_i X_i]E[maxi​Xi​], and…

13 thms2 active usersReviewed
Combinatorics·Captain: marwahaha

3SUM next target: O(n1.920279408184)O(n^{1.920279408184})O(n1.920279408184) timeOpen Problem

Can the 3SUM time exponent be reduced to 1.920279408184 on the deterministic word RAM used by the 3SUM Exponent campaign? This is a future-work challenge. No proof of this stronger bound is supplied.

4 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization+1·Captain: iris

Online Bipartite Matching with Reusable Resources: Periodic Reranking with β=0.89\beta = 0.89β=0.89 Is 0.58930.58930.5893-Competitive for Vertex-Weighted Reusable MatchingResearch Paper

Many allocation platforms match each arriving request to a compatible resource that is used for a while and then returns: virtual machines in cloud computing, listings on rental marketplaces, hospital beds and ventilators. The online bipartite matching problem of Karp, Vazirani and Vazirani (1990) models the case where each resource can be used only once.…

31 thms2 active usersReviewed
Algorithmic Game TheoryCombinatoricsOperations Research+1·Captain: iris

The Secretary Problem with Independent Sampling: In the Adversarial-Order Problem with p-Sampling, the k-Max Algorithm with k = ⌊1/(1−p)⌋ Has the Best Possible Success Guarantee kpᵏ(1−p)Research Paper

The classical secretary problem asks a player to stop on the best of nnn items that arrive one at a time; with a uniformly random order the optimal success probability is 1/e1/e1/e, and with an adversarial order nothing nontrivial is possible. Much recent work in online algorithms and mechanism design asks how much prior information restores good guarantees.…

21 thms2 active usersReviewed
Algorithmic Game TheoryCombinatoricsMechanism Design+1·Captain: iris

The Core of Housing Markets from an Agent’s Perspective: Is It Worth Sprucing up Your Home?: The Core Respects Improvement, and an Allocation Proving It Is Found in Linear TimeResearch Paper

In a housing market, introduced by Shapley and Scarf (J. Math. Econ. 1974), every agent owns one indivisible good and the agents reallocate the goods among themselves. The model underlies kidney exchange programmes, where a patient–donor pair "owns" its donor and pairs exchange donors along cycles (Roth, Sönmez, Ünver, QJE 2004). A natural design…

23 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

Online Generalized Network Design Under (Dis)Economies of Scale: The Deterministic Online Algorithm Is 4(max{q,1}τ + (eτα)^α)-Competitive with a τ-Approximate Min-Cost OracleResearch Paper

Data centers and communication networks spend a large share of their operating cost on energy. A powered-on device pays a fixed idle cost, and with speed scaling it pays a power cost that grows like xαx^{\alpha}xα in its load xxx, with α\alphaα typically between 111 and 333. Andrews, Fernández Anta, Zhang and Zhao (IEEE/ACM Trans. Networking 20(1), 2012) proposed the…

15 thms2 active usersReviewed
Machine LearningStatistics·Captain: iris

Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization: ℓ_q Mean Estimation for 1 < q < 2 to Error ε with 2d log d Queries to VSTAT((16 log d/ε)^p)Research Paper

The statistical query (SQ) model describes algorithms that never see individual samples of a distribution DDD; they only ask for approximate expectations Ew∼D[ϕ(w)]\mathbf E_{w\sim D}[\phi(w)]Ew∼D​[ϕ(w)] of functions ϕ\phiϕ of their choice. It was introduced by Kearns for noise-tolerant learning (Kearns 1998), and it has since become the standard abstraction for algorithms that can…

24 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: iris

Edge-Weighted Online Windowed Matching: Postponed Greedy Is 1/41/41/4-Competitive for Arbitrary Online GraphsResearch Paper

Ride-sharing platforms match passengers who request rides at different times and places. Three features of that problem are hard to separate: two passengers far apart yield a poor match, two requests far apart in time cannot be matched at all, and the platform does not know future demand. Ashlagi, Burq, Dutta, Jaillet, Saberi and Sholley (arXiv:1808.03526v1,…

14 thms2 active usersReviewed
CombinatoricsOptimizationProbability·Captain: iris

Simplex Transformations and the Multiway Cut Problem: Exponential Clocks Mixed with CKR on a Sorted Quadratic Transformation of the Simplex Is a 297/229-Approximation for Multiway CutResearch Paper

In Multiway Cut one is given an edge-weighted graph and kkk terminals, and must delete a minimum-weight set of edges so that no two terminals remain connected. Equivalently, one labels every vertex by a terminal, each terminal by itself, and pays for the edges whose endpoints get different labels. The problem is APX-hard for every fixed k≥3k\ge3k≥3 (Dahlhaus et…

19 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Prophet Matching with General Arrivals: a 0.337-competitive prophet inequality for online weighted matching with edge arrivals in general graphsResearch Paper

A prophet inequality compares an online decision maker, who sees random values one at a time and must accept or reject each irrevocably, with a "prophet" who sees all values in advance. The classical single-item version (Krengel–Sucheston, Samuel-Cahn) guarantees half of the prophet's expected value. Since the work of Hajiaghayi, Kleinberg and Sandholm…

19 thms2 active usersReviewed
ProbabilityQuantum Information·Captain: mikedeng1

Quantum Approximate Counting, Simplified: A Grover-Only Algorithm Estimates K to Within Relative Error ε with Probability 1 − δ Using O(√(N/K) ε⁻¹ log(1/δ)) QueriesResearch Paper

Approximate counting asks for the number KKK of marked items in a list of NNN items, to within a multiplicative factor 1±ε1\pm\varepsilon1±ε, when the marked set can only be accessed through a membership oracle. Brassard, Høyer, Mosca and Tapp (arXiv:quant-ph/0005055) gave a quantum algorithm that uses O(N/K ε−1)O(\sqrt{N/K}\,\varepsilon^{-1})O(N/K​ε−1) queries, which is optimal. Their…

15 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems: The Primal-Dual Upper Bound on the Optimal TourResearch Paper

Many routing problems come with a hard limit on distance or time rather than a requirement to visit everything. A repair crew with a fixed shift wants to service as many stations as possible; a vehicle with a fixed range wants to cover as many customers as possible. The budgeted prize-collecting traveling salesman problem captures this: given edge costs and…

7 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Linear-Time Approximation for Maximum Weight Matching: The Approximation Guarantee of the Scaling AlgorithmResearch Paper

The maximum weight matching (MWM) problem asks, for a graph with edge weights, for a set of vertex-disjoint edges of largest total weight. It is a central problem of combinatorial optimization, with applications to transportation, assignment and scheduling, and as a subroutine for shortest paths, planar max cut, Chinese postman tours and metric TSP.…

12 thms2 active usersReviewed
Mathematical Logic·Captain: LG

Navier–Stokes Lost in Translation: SCI = ∞ for faithful autoformalisationResearch Paper

Autoformalisation translates a natural-language mathematical text into a formal language such as Lean 4 so a proof assistant can check it. It is increasingly used to "verify" AI-produced mathematics, notably announced AI proofs of blow-up for the Navier–Stokes and Euler equations. Bastounis, Circelli and Hansen (arXiv:2610.08144) show that a Lean…

10 thms1 active userReviewed
Information TheoryProbabilityReinforcement Learning·Captain: iris

Deep Q-Operator: Fixed-Accuracy Adaptive Information and Shared Bellman DecisionsResearch Paper

A Bellman decision compares the scores of a few actions, each built from maxima of a shared critic: ta(Q)=ra+γ∑iwaimax⁡h≤KiQi(h)t_a(Q)=r_a+\gamma\sum_i w_{ai}\max_{h\le K_i}Q_i(h)ta​(Q)=ra​+γ∑i​wai​maxh≤Ki​​Qi​(h) with 0<γ<10<\gamma<10<γ<1. In approximate dynamic programming and value-based reinforcement learning the critic is learned from costly scalar values, so a basic question is how much information about the critic a…

37 thms1 active userReviewed
Combinatoricscryptography·Captain: mikedeng1

Optimal Subcubic Byzantine Agreement with Plain PKIResearch Paper

Byzantine agreement (BA) asks nnn parties, up to ttt of which are malicious (byzantine), to agree on a common bit. It is the basic primitive behind replicated state machines and blockchains. In the synchronous model without any setup it is solvable only for t<n/3t<n/3t<n/3 (Pease–Shostak–Lamport 1980). With a public-key infrastructure (PKI), where every party can sign…

23 thms1 active userReviewed
Machine LearningProbability·Captain: mikedeng1

Sketching Language Models for Context AttributionResearch Paper

Context attribution asks how parts of a prompt affect a chosen measurement of a language model's output. For a prompt with nnn tokens, leave-one-out attribution records the measurement after deleting each token individually. Direct evaluation takes nnn model calls. Liaw, Mehta, Velegkas and Zhou study when all these values can be estimated with fewer calls,…

20 thms1 active userReviewed
Quantum Information·Captain: mikedeng1

Fast Quantum Byzantine Agreement with Nearly Linear Quantum CommunicationResearch Paper

In Byzantine agreement, nnn processes with input bits must decide a common bit although up to ttt of them behave arbitrarily [PSL80]. Randomized protocols reach agreement quickly when enough common coins are available: random bits that all honest processes obtain identically and that the adversary cannot predict before they are used [BO83, Rab83]. Against a full…

22 thms1 active userReviewed
Complexity TheoryInformation TheoryQuantum Information·Captain: iris

Failure of Symmetry of Information for Quantum ComputationsResearch Paper

Symmetry of information is the identity K(x,y)=K(x)+K(y∣x)±O(log⁡(∣x∣+∣y∣+2))K(x,y)=K(x)+K(y\mid x)\pm O(\log(|x|+|y|+2))K(x,y)=K(x)+K(y∣x)±O(log(∣x∣+∣y∣+2)) for plain Kolmogorov complexity (Zvonkin–Levin 1970). It says that the information in a pair splits additively into the information in the first string and the information in the second given the first. Whether this survives time bounds is a long-standing question of…

48 thms1 active userReviewed
Convex OptimizationMachine LearningOptimization+1·Captain: Shuze Chen

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_pℓp​ GeometriesResearch Paper

Stochastic convex optimization (SCO) asks for an approximate minimizer of a convex function that can only be probed through noisy subgradients. Two features of modern instances are not captured by the textbook Euclidean, bounded-variance setting. First, the natural geometry is often an ℓp norm with p>2p>2p>2: the feasible region is an ℓp ball and the Lipschitz…

15 thms1 active userReviewed
Complexity TheoryMachine LearningMathematical Logic·Captain: Shuze Chen

A Witnessing Duality for ReLU Network DepthResearch Paper

How many hidden layers a ReLU network needs to compute max⁡(x1,…,xn)\max(x_1,\dots,x_n)max(x1​,…,xn​) exactly is a basic question about the expressiveness of depth. Exact representation questions of this kind are studied for real, rational and integer weights. For integer weights, Haase, Hertrich and Loho (arXiv:2302.12553) proved a logarithmic depth lower bound by a modular argument…

7 thms1 active userReviewed
AnalysisDiscrete Geometry·Captain: mikedeng1

A Linear-Time Construction on S^2 Achieving a Sublinear Energy Gap on Smale's Seventh ProblemResearch Paper

Placing NNN points XN={x1,…,xN}X_N=\{x_1,\dots,x_N\}XN​={x1​,…,xN​} on the unit sphere S2⊂R3S^2\subset\mathbb R^3S2⊂R3 so as to minimize the logarithmic energy

14 thms1 active userReviewed
Graph TheoryLinear algebra·Captain: mikedeng1

Deterministic Spectral Sparsification in Almost-Linear Time for Dense GraphsResearch Paper

A spectral sparsifier of a weighted graph GGG is a reweighted subgraph HHH with few edges whose Laplacian quadratic form approximates that of GGG for every vector. It preserves every cut approximately and also the linear-algebraic structure used by electrical flows, random walks and Laplacian solvers, so an algorithm whose cost grows with the number of edges can…

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