The TCS Formalization Drive

A coordinated effort to formalize the mathematics of theoretical computer science in Lean 4.

Scope: missions in computational complexity, algorithms and optimization, data structures, automata and computability, randomized and approximation algorithms, cryptography, learning theory, information theory, algorithmic game theory, combinatorics, computational geometry, and distributed computing.

582 missions

Missions

301–325 of 582

Combinatorics Operations Research Optimization+1·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 3: First-Fit Decreasing and Best-Fit Decreasing Use at Most 11/9 L* + 4 BinsResearch Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models table formatting, the placement of program segments on pages, and the allocation of files to disc tracks, and it is NP-complete, so exact solutions require search in general. Johnson, Demers, Ullman, Garey and Graham (SIAM J. Comput. 3 (1974)) therefore…

12 thms3 active usersReviewed

Completed

Combinatorics Operations Research Optimization+2·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions I: A Uniformly Random Set Achieves 1/4 of the Optimum, and 1/2 for Symmetric FunctionsResearch Paper

Many combinatorial optimization problems ask for a subset of a finite ground set that maximizes a set function with diminishing returns: Max Cut and Max Directed Cut in graphs, facility location, maximum entropy sampling, and welfare problems in combinatorial auctions all fit this pattern. The common abstraction is the maximization of a submodular function,…

8 thms3 active usersReviewed

Completed

Combinatorics Operations Research Optimization+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling IV: List Scheduling from an Optimal One-Machine Schedule Is a 2-Approximation for In-TreesResearch Paper

Minimizing the sum of weighted completion times of jobs on identical parallel machines is one of the basic objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. When the jobs are subject to precedence constraints (a job may start only after certain other jobs have finished), the problem is…

6 thms3 active usersReviewed

Completed

Combinatorics Operations Research Optimization+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling III: From One Machine to Many with Delay ListResearch Paper

Minimizing the sum of weighted completion times $\sum_j w_jC_j$ is one of the standard objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. With release dates or precedence constraints the problem is NP-hard already on one machine, and on $m$ identical parallel machines it is harder still, so the…

12 thms3 active usersReviewed

Completed

Combinatorics Operations Research Optimization+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling II: A 2.83-Approximation for Parallel Machines with Release DatesResearch Paper

Minimizing the average completion time of jobs that arrive over time is a basic objective in machine scheduling. It measures how long a job spends in the system on average. With several identical machines, release dates and no preemption (written $P|r_j|\sum C_j$ ), the problem is strongly NP-hard already on one machine. Research has therefore looked for…

11 thms3 active usersReviewed

Completed

Combinatorics Operations Research Optimization+1·Captain: mikedeng1

Local Search Heuristics for k-Median and Facility Location Problems IV: Local Search with Multi-Copy Moves for Capacitated Facility Location Has Locality Gap 4Research Paper

Facility location asks where to open service points (warehouses, plants, servers) and how to connect customers to them so that the total opening cost plus the total connection cost is minimum. In the capacitated version each facility can serve only a limited number of customers, which is the situation in most applications: a warehouse has a floor area, a…

10 thms3 active usersReviewed

Completed

Combinatorics Operations Research Optimization+1·Captain: mikedeng1

Local Search Heuristics for k-Median and Facility Location Problems I: Single-Swap Local Search for k-Median Has Locality Gap 5Research Paper

The k-median problem asks where to open $k$ facilities so that the total distance from a set of clients to their nearest open facility is as small as possible. It is a basic model of facility location in operations research (placing depots, warehouses or servers) and of clustering with representative centres, and it is NP-hard, so the question of interest is…

8 thms3 active usersReviewed

Completed

Algorithmic Game Theory Operations Research Theoretical Computer Science·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach VI: Maximizing Ad-Auctions RevenueTextbook

Search-engine ad-auctions sell items (ad slots) to buyers who arrive with per-item bids and a fixed daily budget, online: each item must be allocated the moment it appears, with no ability to revisit past allocations, and no buyer may ever be charged more than its budget. Buchbinder and Naor's survey [1] models this as a generalization of online bipartite…

8 thms3 active users

Linear Optimization Operations Research Theoretical Computer Science·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach IV: Generalized CachingTextbook

Caching is a two-level memory-management problem — the fast level (cache) can hold only $k$ items, and the algorithm must decide, online, which item to evict whenever the current request misses — that is normally analyzed through the competitive ratio of ad hoc marking or LRU-style rules. Buchbinder and Naor's survey [1] instead recasts weighted caching…

14 thms3 active users

Completed

Machine Learning Operations Research Probability+2·Captain: mikedeng1

Foundations of Machine Learning XIV: Finite Markov Decision Processes and Bellman's EquationsTextbook

Reinforcement learning formalizes a scenario supervised learning cannot: an agent that actively interacts with an environment, choosing actions that change both the state it observes next and the reward it receives, rather than passively receiving an i.i.d. labeled sample. Every practical treatment of this scenario — from classical dynamic programming to…

13 thms3 active usersReviewed

Combinatorics Complexity Theory Theoretical Computer Science·Captain: Lucas

4-to-1 Games with Perfect CompletenessResearch Paper

Many approximation problems resist the standard PCP toolkit: the best known NP-hardness factors for Max-Cut, Vertex-Cover and approximate graph colouring are far from the best known polynomial-time algorithms. To explain this gap, Khot (CCC 2002) proposed the Unique-Games Conjecture and the family of $d$ -to-1 Games Conjectures. The $d$ -to-1 conjectures assert pe…

12 thms3 active usersReviewed

Completed

Mathematical Physics Quantum Information Theoretical Computer Science·Captain: Lucas

Undecidability of the Spectral GapResearch Paper

The spectral gap of a quantum many-body Hamiltonian is the difference between the energy of its ground state and the energy of its first excited state, in the limit of infinitely many particles. Whether a given microscopic interaction produces a gapped or a gapless system decides much of the macroscopic physics: gapped systems have exponentially decaying…

22 thms3 active usersReviewed

Completed

Mechanism Design Theoretical Computer Science·Captain: Shuze Chen

Algorithmic Game Theory IV: VCG and the Limits of TruthfulnessTextbook

Mission III of this series ends at an impossibility: without money, incentive compatibility over three or more alternatives means dictatorship. This mission formalizes the classical escape route — quasilinear utilities and payments — and the exact price of it. Vickrey (1961) discovered that a second-price auction makes truth-telling dominant; Clarke (1971)…

6 thms3 active usersReviewed

Completed

Theoretical Computer Science·Captain: marwahaha

Asymmetric Hashing Square Bound: omega < 2.3747Research Paper

AI generated, I think it's correct

131 thms3 active usersReviewed

Completed

Computational Geometry Theoretical Computer Science·Captain: wurtle

Generalization of Hinging PlanesResearch Paper

A continuous piecewise linear (CPWL) function is one assembled from finitely many flat pieces glued along flat seams. Every ReLU network computes such a function, and every such function is computed by some ReLU network. Questions about how deep a network must be are therefore questions about the internal structure of CPWL functions.

3 thms3 active users

Completed

Theoretical Computer Science·Captain: marwahaha

Sensitivity ConjectureResearch Paper

Nearly every measure of Boolean function complexity was known to be equivalent — except sensitivity. Proving the conjecture unified the whole picture.

49 thms3 active usersReviewed

Completed

Combinatorics Theoretical Computer Science·Captain: marwahaha

Weighted-cache 3SUM refinement in $O(n^{1.920279408185})$ timeResearch Paper

3SUM asks whether three distinct positions in an integer array hold values summing to zero. This mission imports Jionghan Wang's sharper weighted-cache refinement into the 3SUM Exponent campaign, improving the previously published exponent $1.92027942$ to $1.920279408185$ .

4 thms2 active usersReviewed

Completed

Combinatorics Machine Learning·Captain: iris

Deep Sets: Over a Countable Universe, a Function of a Finite Set Is Permutation Invariant iff It Has the Form $\rho(\sum_{x\in X}\phi(x))$ Research Paper

Many learning problems take a set as input rather than a vector: a point cloud, the collection of words in a document, a group of users in an audience, a sample from a distribution. A model for such data must give the same answer however the elements of the set are listed. Deep Sets (Zaheer, Kottur, Ravanbakhsh, Póczos, Salakhutdinov, Smola,…

6 thms2 active usersReviewed

Dynamic Programming Operations Research Probability+1·Captain: iris

Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is $\frac{1}{2-q}(1-\frac{1}{e})$ -CompetitiveResearch Paper

Nonprofit crowdsourcing platforms rely on volunteers to perform time-sensitive tasks. On Food Rescue U.S., for example, a task is a scheduled pickup of a perishable donation, and when a task goes unclaimed the platform can push a notification to a subset of volunteers. Notifying more volunteers raises the chance that the current task gets done, but…

19 thms2 active usersReviewed

Combinatorics Operations Research Optimization+2·Captain: iris

Online Bipartite Matching with Reusable Resources: Periodic Reranking with $\beta = 0.89$ Is $0.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

Convex Optimization Operations Research Optimization+1·Captain: iris

Batching and Optimal Multi-stage Bipartite Allocations: PR-MWM Is (1 − (1 − 1/K)^K)-Competitive for K-Stage Fractional Vertex-Weighted MatchingResearch Paper

Matching platforms rarely decide on one request at a time. A ride-hailing marketplace clears requests in short windows, an ad exchange serves a video session's slots together, and cloud and retail systems process demand in rounds. Between the fully offline problem and the online model of Karp, Vazirani and Vazirani (STOC 1990) lies a question with an…

18 thms2 active usersReviewed

Algorithmic Game Theory Combinatorics Operations Research+2·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 $n$ items that arrive one at a time; with a uniformly random order the optimal success probability is $1/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

Completed

Combinatorics Operations Research Optimization+1·Captain: iris

Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience: Greedy with a κ-Approximate Star-Graph Black Box Is κ/2-Competitive under Adversarial ArrivalsResearch Paper

Online bipartite matching, introduced by Karp, Vazirani and Vazirani (1990), models a platform that must assign arriving customers to a known stock of items, one customer at a time and irrevocably. In e-commerce, job search and online advertising, a recommendation is only a suggestion: a customer buys an offered item with some known probability, and after…

15 thms2 active usersReviewed

Graph Theory Operations Research Probability·Captain: iris

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs: a 0.474-Selectable Random-Order Contention Resolution Scheme for Every GraphResearch Paper

Contention resolution is a standard way to turn a fractional solution into an integral one while losing only a constant factor on every coordinate. For matchings on graphs it underlies guarantees for stochastic matching, prophet inequalities, and posted-price mechanisms (Feldman, Svensson and Zenklusen 2021; Ezra, Feldman, Gravin and Tang 2022). A scheme…

24 thms2 active usersReviewed

Completed

Mathematical Logic Theoretical Computer Science Type Theory·Captain: kmehltretter82

Type-Based Termination Checking in AgdaResearch Paper

A proof assistant based on type theory has to reject non-terminating definitions: a function that loops can inhabit any type, including the empty one, and so proves everything. Agda therefore checks every recursive definition for termination before accepting it. Purely syntactic checks, which require some argument to become structurally smaller at each…

30 thms2 active users

Top contributors

Rank	Contributor	Accepted solutions	Submitted problems
1	Eyal1990	5022	7705
2	fizzyinc3	1303	7
3	marwahaha	643	870
4	mrfancypants	629	0
5	dbenbenn	546	543
6	kmehltretter82	328	92
7	Nihal	296	0
8	Nickrobbins95	269	8
9	Shuze Chen	224	794
10	shivm	208	0

The TCS Formalization Drive

Missions

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 3: First-Fit Decreasing and Best-Fit Decreasing Use at Most 11/9 L* + 4 BinsResearch Paper

Maximizing Non-Monotone Submodular Functions I: A Uniformly Random Set Achieves 1/4 of the Optimum, and 1/2 for Symmetric FunctionsResearch Paper

Approximation Techniques for Average Completion Time Scheduling IV: List Scheduling from an Optimal One-Machine Schedule Is a 2-Approximation for In-TreesResearch Paper

Approximation Techniques for Average Completion Time Scheduling III: From One Machine to Many with Delay ListResearch Paper

Approximation Techniques for Average Completion Time Scheduling II: A 2.83-Approximation for Parallel Machines with Release DatesResearch Paper

Local Search Heuristics for k-Median and Facility Location Problems IV: Local Search with Multi-Copy Moves for Capacitated Facility Location Has Locality Gap 4Research Paper

Local Search Heuristics for k-Median and Facility Location Problems I: Single-Swap Local Search for k-Median Has Locality Gap 5Research Paper

The Design of Competitive Online Algorithms via a Primal-Dual Approach VI: Maximizing Ad-Auctions RevenueTextbook

The Design of Competitive Online Algorithms via a Primal-Dual Approach IV: Generalized CachingTextbook

Foundations of Machine Learning XIV: Finite Markov Decision Processes and Bellman's EquationsTextbook

4-to-1 Games with Perfect CompletenessResearch Paper

Undecidability of the Spectral GapResearch Paper

Algorithmic Game Theory IV: VCG and the Limits of TruthfulnessTextbook

Asymmetric Hashing Square Bound: omega < 2.3747Research Paper

Generalization of Hinging PlanesResearch Paper

Sensitivity ConjectureResearch Paper

Weighted-cache 3SUM refinement in O(n1.920279408185)O(n^{1.920279408185})O(n1.920279408185) timeResearch Paper

Deep Sets: Over a Countable Universe, a Function of a Finite Set Is Permutation Invariant iff It Has the Form ρ(∑x∈Xϕ(x))\rho(\sum_{x\in X}\phi(x))ρ(∑x∈X​ϕ(x))Research Paper

Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is 12−q(1−1e)\frac{1}{2-q}(1-\frac{1}{e})2−q1​(1−e1​)-CompetitiveResearch Paper

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

Batching and Optimal Multi-stage Bipartite Allocations: PR-MWM Is (1 − (1 − 1/K)^K)-Competitive for K-Stage Fractional Vertex-Weighted MatchingResearch Paper

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

Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience: Greedy with a κ-Approximate Star-Graph Black Box Is κ/2-Competitive under Adversarial ArrivalsResearch Paper

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs: a 0.474-Selectable Random-Order Contention Resolution Scheme for Every GraphResearch Paper

Type-Based Termination Checking in AgdaResearch Paper

Top contributors

Weighted-cache 3SUM refinement in $O(n^{1.920279408185})$ timeResearch Paper

Deep Sets: Over a Countable Universe, a Function of a Finite Set Is Permutation Invariant iff It Has the Form $\rho(\sum_{x\in X}\phi(x))$ Research Paper

Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is $\frac{1}{2-q}(1-\frac{1}{e})$ -CompetitiveResearch Paper

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