Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Linear algebra

332 missions · 207 completed

Missions

Open125Completed207All332
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: Shuze Chen

New lower bounds on tensor rank of (n,2,m)(n,2,m)(n,2,m) matrix multiplication with GPT-6 AstraResearch Paper

Every fast matrix multiplication algorithm starts from an identity that computes a fixed-shape product with few multiplications. Strassen's 1969 algorithm (Str69) multiplies two 2×22\times 22×2 matrices with 7 instead of 8 multiplications, and applying such an identity recursively turns RRR multiplications for a k×lk\times lk×l by l×ml\times ml×m product into an …

12 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Uniform adjacency-degree probes from differential rigidityResearch Paper

A tree can be described without vertex names by asking which matrix quantities survive relabelling. Its adjacency matrix records which vertices are joined, while its degree matrix places each vertex's number of neighbours on the diagonal. The trace of any polynomial in these two matrices is unchanged by relabelling. The question is how much information one…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·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
🏆Completed
Quantum Information·Captain: iris

Towards Large-Scale Quantum Computation IV: the phase-insensitive gate distance sqrt((m − |tr(U†V)|)/m) satisfies the triangle inequality on the unitary group U(m)Textbook

A quantum computer protected by an error-correcting code can apply only a small set of gates fault-tolerantly, so every other gate must be approximated by a sequence from that set. The existence of short approximating sequences is the content of the Solovay–Kitaev theorem (Kitaev 1997; Nielsen and Chuang 2000). A practical search for the best sequence needs…

5 thms2 active usersReviewed
🏆Completed
Mathematical PhysicsProbabilityQuantum Gravity+1·Captain: iris

Towards Quantum Gravity: A Framework for Probabilistic Theories with Non-Fixed Causal Structure: The Causaloid Decides and Computes Every Conditional ProbabilityResearch Paper

General relativity has a dynamical causal structure: whether one event can influence another depends on the metric, which is itself a physical variable. Quantum theory, in its standard formulations, presupposes a fixed causal structure: states evolve in a given time, and systems are composed in a given order. A theory of quantum gravity is expected to…

17 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Decomposition of Games: Some Strategic Considerations: Duplicating a Strategy Commutes with the (μ,γ)-Decomposition into Potential, Harmonic and Nonstrategic ComponentsResearch Paper

A finite game can be split into simpler pieces. Candogan, Menache, Ozdaglar and Parrilo (Math. Oper. Res. 36 (2011)) showed that the space of finite games is the direct sum of potential, harmonic and nonstrategic games: potential games have pure equilibria and well-behaved learning dynamics, harmonic games generalize matching pennies, and nonstrategic games…

18 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Analytical Solution to a Discrete-Time Model for Dynamic Learning and Decision Making: the two-action frontier difference equations have a unique closed-form solution with explicit det YResearch Paper

Many sequential decisions trade off immediate reward against information: a firm prices without knowing which demand regime it faces, a clinician treats without knowing a patient's type, a bandit player pulls a risky arm to learn its mean. Formally these are partially observed Markov decision problems (POMDPs) with a hidden but fixed state. Their value…

10 thms2 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization+1·Captain: Shuze Chen

Modeling, Measuring and Managing Risk XI: The Mean-Variance Efficient Portfolio in Closed FormTextbook

An investor who splits a budget across MMM risky assets faces a trade-off between expected return and risk. Markowitz proposed measuring risk by the variance of the portfolio return and selecting, for each required expected return, the portfolio of least variance (Markowitz 1952). Tobin added a risk-free asset (Tobin 1958), and Sharpe, Lintner and Mossin…

4 thms2 active usersReviewed
🏆Completed
Graph TheoryMachine Learning·Captain: mikedeng1

Geometric Deep Learning V: A Degree-r Polynomial Filter Σ αₖΔᵏX of a Graph Laplacian Is Localised in r-Hop NeighbourhoodsTextbook

Graph neural networks and geometric learning on meshes rely on operators that combine the features of a node with those of its neighbours. The graph Laplacian is the oldest such operator: it is the discrete analogue of the Laplace–Beltrami operator of a surface, and its eigenvectors play the role of a Fourier basis on a graph. Early spectral graph networks (…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: mikedeng1

Geometric Deep Learning II: Every Linear Permutation-Equivariant Map on ℝⁿ Is a Linear Combination of the Identity and the Averaging Map (1/n)𝟙𝟙ᵀTextbook

Many learning problems take an unordered collection as input: the points of a point cloud, the particles of a physical system, the atoms of a molecule, the nodes of a graph. Storing such data in memory fixes an order of the elements, but the order carries no information, and a model whose output changes when the rows of its input are shuffled is answering a…

7 thms2 active usersReviewed
🏆Completed
Markov ChainNumerical AnalysisOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling XI: First Passage Times by Reduction and BisectionTextbook

In a quasi-birth-and-death process (QBD) a queue length or buffer content (the level) moves up or down by at most one per step while an auxiliary Markov environment (the phase) modulates the rates. When buffers are bounded the level lives in {0,1,…,M}\{0,1,\dots,M\}{0,1,…,M}, and a basic performance question is how long it takes, on average, for an initially empty buffer to…

8 thms2 active usersReviewed
🏆Completed
Markov ChainNumerical AnalysisOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling VIII: The Logarithmic Reduction Series for GTextbook

Quasi-birth-and-death processes (QBDs) are Markov chains on pairs (level, phase) in which the level moves by at most one at each step. They model queues in random environments, priority queues, and many other systems treated by matrix-analytic methods (Latouche & Ramaswami 1999). Their stationary distribution, when it exists, is matrix-geometric, and…

8 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling IX: The Roots of det(x²A₀ + x(A₁ − I) + A₂) and the Eigenvalues of GTextbook

A quasi-birth-and-death process (QBD) is the matrix generalization of a birth-and-death chain: a Markov chain on pairs (level, phase) that moves at most one level per step. QBDs model queues in random environments, multi-server and priority systems, and communication links with correlated traffic, and their analysis rests on two matrices: the first-passage…

12 thms2 active usersReviewed
🏆Completed
Markov ChainNumerical AnalysisOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling X: Linear Level Reduction for Finite QBDsTextbook

In a queue with a finite buffer, a multi-server system with a capacity limit, or a communication link with a bounded number of packets in transit, the number of customers is a level that takes only finitely many values, and the rest of the state (service phase, arrival phase, environment) is a phase. The resulting Markov chain is a finite…

6 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling IV: The Censored Markov Chain and Its Stationary DistributionTextbook

Matrix analytic methods compute the stationary distribution of structured Markov chains (quasi-birth-and-death processes, M/G/1- and GI/M/1-type chains) by working on one block of states at a time. Every such computation rests on one device: watch the chain only while it is in a subset TTT of the state space, and describe what happens in between through…

10 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling II: The Renewal Function of a PH Renewal ProcessTextbook

Renewal processes model ordered sequences of events on [0,∞)[0,\infty)[0,∞): arrivals to a queue, service completions, equipment failures. Their defining feature is that successive intervals between events are independent and identically distributed. Two quantities answer most practical questions about such a process: the renewal function R(x)R(x)R(x), the expected number of…

9 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling I: PH Distributions and the Absorption CriterionTextbook

Phase-type (PH) distributions are the distributions of absorption times of finite Markov chains. Introduced by Neuts in the 1970s (the book follows his framework, Latouche–Ramaswami, §2.3), they are the standard way to put non-exponential service times, interarrival times and lifetimes into a model while keeping it Markovian: a PH random variable is a walk…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: Shuze Chen

Lectures on Modern Convex Optimization XI: Primal-Dual Path-Following for Semidefinite ProgrammingTextbook

Semidefinite programming (SDP), the optimization of a linear function over the intersection of an affine subspace with the cone of positive semidefinite matrices, is the workhorse behind relaxations in combinatorial optimization, robust optimization and control. Its practical and theoretical tractability rests on interior point methods: algorithms that…

9 thms2 active usersReviewed
🏆Completed
OptimizationStatisticsTheoretical Computer Science·Captain: mikedeng1

Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design: Sampling with an α-Approximate (d−1, d)-Wise Independent Measure Gives an α-ApproximationResearch Paper

In linear regression with a budget, an experimenter holds nnn candidate experiments, each described by a vector vi∈Rdv_i\in\mathbb R^dvi​∈Rd, and may run only kkk of them. If the experiments in S⊆[n]S\subseteq[n]S⊆[n] are run and the unknown parameter is estimated by least squares, the covariance of the estimate is proportional to (∑i∈Svivi⊤)−1\big(\sum_{i\in S}v_iv_i^\top\big)^{-1}(∑i∈S​vi​vi⊤​)−1. A-optimal…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

A Theory of Statistical Inference for Ensuring the Robustness of Scientific Results: Closed-Form Tethered Hacking Interval for the Least Squares Average Treatment EffectResearch Paper

Scientific conclusions based on a fitted model can move when an analyst changes the model while keeping its fit to the observed data nearly as good. Coker, Rudin, and King call the resulting range of conclusions a tethered hacking interval. The range measures the sensitivity of a reported statistic to the choice among models under a fixed loss tolerance.…

7 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Controlling Epidemic Spread: Reducing Economic Losses with Targeted Closures: The Effective Reproduction Rate Is Below One if and only if a Linear Matrix Inequality in the Activity Levels HoldsResearch Paper

A city can reduce contacts by limiting activity in selected neighborhoods. Such a policy affects more than the residents of the closed neighborhood: people travel across neighborhood boundaries, meet there, and carry infection back to their home neighborhoods. A citywide closure ignores these differences in movement and economic cost. Birge, Candogan, and…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Market Efficient Portfolios in a Systemic Economy: f-Efficient Bank Holdings Exist, Attain Mean Squared Deviation (bᵀv)²/(1ᵀG⁻¹1), and Are Unique if and only if There Are Exactly Two BanksResearch Paper

When banks are hit by losses they sell assets to restore their leverage targets, and these fire sales depress prices for every other holder of the same assets. The resulting deviation of market capitalization from its fundamental value is a systemic externality: it depends not on any single bank's portfolio but on how the stock of each asset is distributed…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

When Is Society Susceptible to Manipulation?: Under Any Principal Interference, Beliefs in a Mixed DeGroot–Bayesian Network Converge Almost Surely to (I − W)⁻¹(BU∞ ⊙ θ)Research Paper

Misinformation campaigns target specific people in a social network and rely on the network to spread what they plant. Whether such a campaign can succeed depends on how people combine what they see themselves with what their neighbours believe. Mostagir, Ozdaglar and Siderius (SSRN 3474643; Management Science, 2022, doi:10.1287/mnsc.2021.4265) model a…

6 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers 2: Spectral Rounding Without Outliers Gives Σ|S_k|/n_k ≤ 64(2+ε)‖X⁰ − X̂‖₁/n²minResearch Paper

Spectral clustering recovers group labels from a similarity matrix: compute its leading eigenvectors, embed each point as a row of the eigenvector matrix, and cluster the rows with k-means. It is a standard last step of convex-relaxation methods for clustering, which first estimate a clustering matrix XXX (with Xij=1X_{ij} = 1Xij​=1 when iii and jjj belong to the same…

8 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers 3: Binary PSD Rank-r Lifting (4) Is Equivalent to Robust Cluster Assignment (3)Research Paper

Clustering separates observations into groups whose members resemble one another. In kernel clustering, a matrix KKK records a similarity score for each pair of observations, and an assignment seeks groups with high total within-group similarity. Real data can also contain outliers, observations that should not be assigned to any cluster. Srivastava, Sarkar,…

7 thms2 active usersReviewed
PreviousPage 6 of 9Next

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