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

How to Round Spiky Balls into Submission; And Faster Algorithms For The Closest Vector ProblemResearch Paper

The Closest Vector Problem asks for the point of a lattice nearest to a given target. It is a central problem of the algorithmic geometry of numbers: integer programming in fixed dimension, lattice-based cryptanalysis and many reductions between lattice problems pass through it. Its complexity depends on the norm. In the Euclidean norm, exact CVP is solved…

23 thms2 active usersReviewed
Quantum Information·Captain: iris

Private Information Retrieval from Two Entangled ServersResearch Paper

Private information retrieval (PIR) lets a client read one record of a database without revealing which record. Over one server with classical communication and information-theoretic privacy, the client must essentially download the database; with two non-communicating classical servers, the best known schemes still communicate subpolynomially many but…

40 thms2 active usersReviewed
Computational GeometryMachine Learning·Captain: iris

Learning Partition Trees for Nearest Neighbor SearchResearch Paper

Nearest neighbor search asks for a data structure on a dataset P⊂RdP\subset\mathbb R^dP⊂Rd of nnn points that, given a query qqq, returns a point of PPP closest to qqq. In high dimension, worst-case guarantees are known only with a multiplicative approximation to the distance (Andoni, Indyk 2006; Andoni, Laarhoven, Razenshteyn, Waingarten 2017). Practical systems are…

26 thms2 active usersReviewed
CombinatoricsComplexity Theory·Captain: iris

An Improved Streaming Algorithm for Exact Pattern MatchingResearch Paper

Given a pattern PPP of length mmm followed by a text TTT of length nnn, one character at a time, can an algorithm report each occurrence of PPP in TTT as soon as it ends, while remembering very little? Exact Pattern Matching in the streaming model is the basic problem of a large area: it is used as a black box in streaming algorithms for kkk-mismatch, matching with…

34 thms2 active usersReviewed
Machine LearningProbability·Captain: iris

Efficient Proper Agnostic Learning of HalfspacesResearch Paper

Halfspaces, functions of the form h(x)=sign⁡(w⋅x−θ)h(x)=\operatorname{sign}(w\cdot x-\theta)h(x)=sign(w⋅x−θ), are among the most basic objects in learning theory. In Valiant's PAC model they are efficiently learnable when the labels are realizable, but in the agnostic model of Kearns, Schapire and Sellie the labels may be arbitrary, and the learner must compete with the best-fitting…

30 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Quantum Approximate Pattern Matching with Wildcards and Weighted Edits: Provable Baselines and Sparse-Defect VerificationResearch Paper

Approximate pattern matching asks whether some substring of a text is close to a pattern under edit operations. For the unit-cost model, quantum algorithms are near optimal: Gibney, Jin, Kociumaka and Thankachan (arXiv:2311.01793) give O~(nk)\tilde O(\sqrt{nk})O~(nk​) queries for bounded edit distance, and Kociumaka, Nogler and Wellnitz (arXiv:2410.06808) give…

24 thms2 active usersReviewed
Probability·Captain: iris

Sharp Limits of Graph-Based Nearest Neighbor Search on the SphereResearch Paper

Most large-scale approximate nearest-neighbor search systems, such as HNSW, NSG and DiskANN, build a proximity graph on the data and answer a query by greedy navigation: from an entry point, repeatedly move to the listed neighbor closest to the query, and stop when none is closer. Practice has outrun theory here. Laarhoven (2018) analyzed random restarts on…

68 thms2 active usersReviewed
Complexity TheoryProbability·Captain: iris

Efficient Error Amplification for Sorting and Orthogonal VectorsResearch Paper

Derandomizing a circuit classically has two steps: reduce the error below 2−N2^{-N}2−N on NNN-bit inputs, then fix one good random string non-uniformly. The generic way to reduce the error is to run independent copies and combine their answers, and reaching error 2−k2^{-k}2−k costs a factor kkk in size. For a problem whose circuits are already close to its conjectured…

19 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: iris

Parallel Edge Ranking of TreesResearch Paper

An edge ranking of a tree assigns positive integer ranks to its edges so that the path between any two distinct edges of equal rank contains an edge of higher rank. The edge ranking number er(T)\mathrm{er}(T)er(T) is the least possible maximum rank. This number gives the minimum worst-case number of edge queries needed to locate a target element in a tree, the…

27 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: iris

A Near-Optimal Generalized Sorting AlgorithmResearch Paper

Ordinary comparison sorting assumes that any two elements can be compared. In many settings only some comparisons are possible or affordable: in the nuts and bolts problem a nut can only be compared with a bolt, and in pairwise preference or ranking problems only certain pairs are ever presented together. Generalized sorting, introduced by Huang, Kannan and…

51 thms2 active usersReviewed
Computational GeometryOperations Research·Captain: iris

Exact Euclidean TSP with Few Interior Points: A Square-Root ExponentResearch Paper

The Euclidean traveling salesman problem asks for a shortest closed tour through nnn given points of the plane, with costs the true Euclidean distances. It is NP-hard (Papadimitriou, 1977), and the subset dynamic program of Bellman and of Held and Karp (1962) solves it in time exponential in nnn. De Berg, Bodlaender, Kisfaludi-Bak and Kolay (SICOMP 2023) showed…

31 thms2 active usersReviewed
Machine LearningProbability·Captain: iris

Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFsResearch Paper

A polynomial threshold function (PTF) of degree two labels a point x∈Rdx\in\mathbb R^dx∈Rd by the sign of a quadratic polynomial; an intersection of kkk of them, f(x)=1{q1(x)≥0,…,qk(x)≥0}f(x)=1\{q_1(x)\ge0,\dots,q_k(x)\ge0\}f(x)=1{q1​(x)≥0,…,qk​(x)≥0}, describes regions bounded by kkk quadrics: ellipsoids, slabs, cones and their intersections. Learning such concepts from examples drawn from the standard Gaussian is a…

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

The Role of Diagonal Lines in Quantum Low-Degree TestingResearch Paper

A low-degree test checks that answers to local questions come from a single global polynomial. Low-degree tests go back to the multilinearity and low-individual-degree tests of Babai, Fortnow and Lund (1991) and became central to the PCP theorem. Against provers who share entanglement the situation changes, because answers to different questions come from…

27 thms2 active usersReviewed
Graph TheoryOperations Research·Captain: iris

Tight Bounds for Sublinear Metric Steiner TreeResearch Paper

The metric Steiner tree problem asks for a cheapest tree connecting a prescribed set of terminals in a metric space, possibly through additional points. It is one of Karp's original NP-complete problems, with a best known polynomial-time ratio of ln⁡4+ε≈1.39\ln 4+\varepsilon\approx1.39ln4+ε≈1.39 (Byrka, Grandoni, Rothvoß, Sanità, J. ACM 2013).

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

Truthful-in-Expectation Mechanism with Constant Maximin-Share GuaranteeResearch Paper

Dividing indivisible goods among agents with private additive valuations is a basic problem of algorithmic game theory: the agents' reports are the only input, so a rule that rewards misreporting cannot be fair with respect to the true values. A randomized mechanism is truthful in expectation (TIE) if no agent can raise her expected true value by…

43 thms2 active usersReviewed
Computational GeometryGraph Theory·Captain: iris

Tight Bounds for (1+ϵ)(1+\epsilon)(1+ϵ)-Approximation for Minimum Spanning Trees in Doubling MetricsResearch Paper

A minimum spanning tree (MST) of a finite metric space (X,d)(X,d)(X,d) is a spanning tree of the complete graph on XXX of least total edge length. Computing it exactly from a distance oracle takes Θ(n2)\Theta(n^2)Θ(n2) distance queries even in metrics of constant doubling dimension (Andoni et al., 2014), so the question is how fast a (1+ϵ)(1+\epsilon)(1+ϵ)-approximate MST, a spanning tree…

54 thms2 active usersReviewed
Graph TheoryOperations ResearchOptimization·Captain: iris

Polylog Pairwise Poise: Approximating Multicommodity MulticastResearch Paper

In the synchronous telephone model, each vertex of a graph can exchange any number of messages with at most one neighbor per round. Multicommodity multicast asks, given source–sink pairs (s1,t1),…,(sk,tk)(s_1, t_1), \dots, (s_k, t_k)(s1​,t1​),…,(sk​,tk​), to deliver each source's message to its sink within the minimum number of rounds. It generalizes the single-source problems known as…

51 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: iris

Lower Bounds for the Weisfeiler-Leman Algorithm via Implicit Parity SystemsResearch Paper

The kkk-dimensional Weisfeiler–Leman algorithm (kkk-WL) is the central combinatorial heuristic for graph isomorphism. It refines a coloring of kkk-tuples of vertices round by round, and two graphs are told apart when their color statistics differ. The number of rounds is a natural measure in several fields: it equals the quantifier depth in the logic Ck+1C^{k+1}Ck+1 with…

38 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: iris

Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree AlgorithmsResearch Paper

An induced matching (or strong matching) of a graph is a set of pairwise vertex-disjoint edges whose endpoints span no other edges. Induced matchings appear in strong edge colouring (each colour class of a strong edge colouring is an induced matching), in the Ruzsa–Szemerédi problem, and in the analysis of graph algorithms and interference-free scheduling.…

23 thms2 active usersReviewed
Machine LearningProbabilityStatistics·Captain: iris

Linear Regression with Self-Selection Bias in Polynomial TimeResearch Paper

In many data sets the recorded response is not the outcome of one fixed model but the largest of several. Workers choose among occupations and only the earnings from the chosen one are observed (Roy, 1951); auction data may reveal only the transaction price, not the winning bidder or the losing bids (Athey–Haile, 2002); the model of Fair and Jaffee (1972)…

38 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: iris

Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SATResearch Paper

A strong backdoor of a CNF formula φ\varphiφ into a tractable class is a set XXX of variables such that every assignment to XXX turns φ\varphiφ into a formula of that class. Once a small backdoor is known, satisfiability is decided by trying all 2∣X∣2^{|X|}2∣X∣ assignments and solving each reduct in the class. The size of a smallest backdoor is therefore a parameter that…

32 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: iris

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest PathsResearch Paper

In the k vertex-disjoint paths problem (k-DP) the input is a directed graph with nnn vertices, mmm edges and kkk terminal pairs (si,ti)(s_i,t_i)(si​,ti​), and the task is to connect every pair by a path so that the paths are pairwise vertex-disjoint. In the k disjoint shortest paths problem (k-DSP) every path must in addition be a shortest path between its terminals. Already for…

24 thms2 active usersReviewed
Complexity TheoryMachine Learning·Captain: iris

One-Way Functions and Local Descriptions of Random DataResearch Paper

A one-way function is a map that is easy to evaluate and hard to invert on a random input. Its existence is the minimal assumption of private-key cryptography, and it is not known to follow from P≠NP\mathrm{P}\neq\mathrm{NP}P=NP. A line of work started by Liu and Pass (arXiv:2009.11514) characterizes one-way functions by meta-complexity: the average-case hardness…

51 thms2 active usersReviewed
Complexity TheoryProbability·Captain: iris

Sampling Tools and the Power of AC0Research Paper

A sampler is a device that turns uniform random bits into a sample of a target distribution. Asking which distributions a restricted class of devices can sample, exactly or approximately, is the sampling analogue of asking which functions it can compute. The two questions behave differently: some distributions that look hard can be sampled by very weak…

27 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
PreviousPage 23 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