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
Computational Complexity·Captain: mikedeng1

Polynomial-time Tensor Decomposition under the Kruskal Condition and the Lovitz–Petrov GeneralizationResearch Paper

A tensor decomposition expresses a multidimensional array as a sum of outer products of vectors. Its factors describe separate contributions in each coordinate direction. In applications such as latent-variable estimation and spectral data analysis, a decomposition is useful when those contributions can be distinguished from other explanations of the same…

17 thms1 active userReviewed
ProbabilityRandom Matrix TheoryTheoretical Computer Science·Captain: Shuze Chen

Random tensor isomorphism under orthogonal and unitary actions: Smoothed and average-case analysisResearch Paper

Two 3-tensors A,B∈Cn×n×nA,B\in\mathbb C^{n\times n\times n}A,B∈Cn×n×n are unitarily isomorphic when a change of orthonormal basis in each of the three modes turns one into the other. Deciding this, and its robust version (is BBB close to some basis change of AAA?), is the tensor analogue of comparing two matrices up to unitary equivalence. It arises in quantum information, where a…

19 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

A Fast Algorithm for Subspace ConvolutionResearch Paper

Subset summation asks, given a value f(A)f(A)f(A) for every subset A⊆[n]A\subseteq[n]A⊆[n], for all sums (Zf)(B)=∑A⊆Bf(A)(Zf)(B)=\sum_{A\subseteq B}f(A)(Zf)(B)=∑A⊆B​f(A). The fast zeta transform does this in O(n2n)O(n2^n)O(n2n) additions, and with its inverse, the Möbius transform, it underlies the fastest known algorithms for chromatic number, Hamiltonian path and covering products (Björklund–Husfeldt–Koivisto 2009; Bj…

33 thms1 active userReviewed
Theoretical Computer Science·Captain: Shuze Chen

An Algebraic Semantic Framework for Nondeterministic ComputationResearch Paper

Zheng, Zheng, Wang and Huang, in An Algebraic Semantic Framework for Nondeterministic Computation (July 2026, a STOC 2027 submission), propose to study nondeterminism through algebraic structure attached to tape symbols: two nondeterministic branches are regarded as genuinely independent when the algebraic numbers that encode them are linearly independent…

9 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Polynomial Time Algorithms for the Kadison-Singer ProblemResearch Paper

The Kadison–Singer problem (Kadison and Singer, 1959) asks whether every pure state on the algebra of bounded diagonal operators on ℓ2\ell_2ℓ2​ extends uniquely to a pure state on all bounded operators. It has many equivalent forms; the one used here is Weaver's conjecture KS2 (Weaver, 2004): there are absolute constants α>0\alpha>0α>0 and c<1c<1c<1 such that every family …

55 thms1 active userReviewed
Mathematical PhysicsOptimizationQuantum Information·Captain: mikedeng1

Improved classical optimization of fermionic Hamiltonians beyond Gaussian statesResearch Paper

Finding the largest eigenvalue of an interacting fermionic Hamiltonian is a basic optimization problem in quantum chemistry and many-body physics. Even when the Hamiltonian is a low-degree polynomial in Majorana operators, it acts on a space of dimension 2n2^n2n, and computing its extremal eigenvalue to inverse-polynomial precision is QMA-hard. Classical…

15 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·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
Complexity TheoryQuantum Information·Captain: mikedeng1

Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed PointsResearch Paper

A fixed point is a state unchanged by a function. Fixed-point formulations occur in program analysis, verification and equilibrium computation. Their existence alone does not say how much information an algorithm must obtain to find one. This mission concerns the information required when a function is accessible only through queries on a finite grid. The…

29 thms1 active userReviewed
AlgebraComplexity Theory·Captain: mikedeng1

Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed CyclesResearch Paper

A permutation monomial of a square matrix chooses one entry from each row and each column. The determinant adds these monomials with signs recording permutation parity. In a field of characteristic two, adding an element to itself gives zero, so minus one equals one. The determinant therefore gives the sum of all permutation monomials, but its signs no…

30 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: iris

A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic StreamsResearch Paper

A massive set of points in high-dimensional Euclidean space arrives as a sequence of insertions and deletions, and a small-memory algorithm must estimate how far apart the two farthest surviving points are. This is one of the basic questions of geometric streaming, a model introduced by Indyk (STOC 2004), in which the data is a dynamic multiset rather than…

22 thms1 active userReviewed
AlgebraTheoretical Computer Science·Captain: iris

Subquadratic Time Matrix Multiplication Data Structures Beyond the Dual Exponent, with ApplicationsResearch Paper

The matrix multiplication data structure problem asks to preprocess an N×DN\times DN×D matrix AAA and a D×ND\times ND×N matrix BBB so that any entry of ABABAB can be returned quickly. Computing the product outright takes about N2N^2N2 time at best, and reading one entry from scratch takes 2D2D2D reads of the input. A solution is nontrivial if its preprocessing takes …

47 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Vector Balancing in Polynomial TimeResearch Paper

Given vectors a1,…,an∈Rma_1,\dots,a_n\in\mathbb R^ma1​,…,an​∈Rm, vector balancing asks for signs εj∈{−1,1}\varepsilon_j\in\{-1,1\}εj​∈{−1,1} that make the signed sum ∑jεjaj\sum_j\varepsilon_ja_j∑j​εj​aj​ small. Writing A=[a1⋯an]A=[a_1\cdots a_n]A=[a1​⋯an​], the ℓ∞\ell_\inftyℓ∞​ discrepancy is

33 thms1 active userReviewed
AlgebraTheoretical Computer Science·Captain: iris

Burnside Problems for Matrix Semigroup Quotients with Applications to Border ComplexityResearch Paper

In 1902 Burnside asked whether a finitely generated group in which every element has finite order must be finite. The answer is negative in general (Novikov and Adian, 1968), but positive for groups of complex invertible matrices (Schur), for invertible matrices over any field (Kaplansky), and for finitely generated matrix semigroups over any field…

23 thms1 active userReviewed
CombinatoricsRandom Matrix TheoryTheoretical Computer Science·Captain: iris

A Walk from Free Probability to Matrix Discrepancy I: Matrix SpencerResearch Paper

Given real symmetric m×mm\times mm×m matrices A1,…,AnA_1,\dots,A_nA1​,…,An​ of operator norm at most one, how small can ∥∑iσiAi∥\|\sum_i\sigma_iA_i\|∥∑i​σi​Ai​∥ be made by a choice of signs σ∈{−1,1}n\sigma\in\{-1,1\}^nσ∈{−1,1}n? Random signs give 2nlog⁡(2m)\sqrt{2n\log(2m)}2nlog(2m)​ by the noncommutative Khintchine inequality. For diagonal matrices, which encode ordinary vector discrepancy, Spencer's theorem gives O(n)O(\sqrt n)O(n​) when …

41 thms1 active userReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

A New Characterization of Streaming Decidability of Boolean CSPs Under DeletionsResearch Paper

A constraint satisfaction problem CSP(Γ)\mathrm{CSP}(\Gamma)CSP(Γ) asks whether nnn Boolean variables can satisfy a multiset of constraints drawn from a fixed finite set Γ\GammaΓ of relations. In the streaming model, constraints arrive one at a time and an algorithm keeps limited memory. With insertions only, the one-pass space of satisfiability is governed by…

32 thms1 active userReviewed
Convex OptimizationOptimization·Captain: iris

Necessary and Sufficient Conditions for Rank-One-Generated Cones: Two LMIs Are ROG iff a Nonzero Combination of M1,M2M_1, M_2M1​,M2​ Is PSD or M1=Sym(ac⊤)M_1 = \mathrm{Sym}(ac^\top)M1​=Sym(ac⊤), M2=Sym(bc⊤)M_2 = \mathrm{Sym}(bc^\top)M2​=Sym(bc⊤)Research Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic constraints. Binary integer programs, max-cut, and many robust and polynomial optimization problems can be written this way. Any QCQP has a lifted form in which the vector variable xxx is replaced by the matrix X=xx⊤X = xx^\topX=xx⊤; dropping the rank constraint on XXX…

26 thms1 active userReviewed
Differential GeometryOptimization·Captain: mikedeng1

On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization: Gradient and Hessian Connections for Fixed-rank PSD Matrices via YYᵀResearch Paper

Many estimation problems in statistics, signal processing and machine learning ask for a low-rank positive semidefinite matrix: phase retrieval, matrix sensing, PCA-type problems and the Burer–Monteiro approach to semidefinite programs. A standard formulation is

14 thms1 active userReviewed
Mathematical PhysicsQuantum Information·Captain: mikedeng1

Quantum computation, quantum state engineering, and quantum phase transitions driven by dissipation: The DQC Liouvillian Has a Unique Steady State Encoding the Circuit and a Gap Above 1/T²Research Paper

A quantum circuit normally applies a sequence of gates to a prepared state. Verstraete, Wolf and Cirac proposed a different physical route: couple a quantum system to a memoryless environment so that dissipation drives it toward a state recording the circuit's computation. Their dissipative quantum computation construction places a clock beside the…

9 thms1 active userReviewed
Information TheoryQuantum Information·Captain: mikedeng1

Classical capacity of fermionic product channels: An Explicit Formula for the Gaussian Capacity, Which Equals the One-Shot Capacity for n ≤ 2Research Paper

Sending classical messages through a quantum device requires choosing input states that remain distinguishable after noise. The one-shot classical capacity measures the best information rate when each channel use is signaled with a separate input state. For many channels the optimization is difficult because it ranges over all ensembles of quantum states.…

13 thms1 active userReviewed
Computational GeometryMachine Learning·Captain: mikedeng1

Turning Big Data into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering II: An SVD Coreset of at Most 2(j + ⌈j/ε⌉ − 1) Weighted Points for Affine j-SubspacesResearch Paper

Principal component analysis (PCA) asks for the jjj-dimensional affine subspace that best fits a cloud of nnn points in Rd\mathbb R^dRd in the least-squares sense. When nnn is very large, or the points arrive as a stream or are spread over many machines, one wants to replace the data by a small summary on which the cost of every candidate subspace can still be…

7 thms1 active userReviewed
ProbabilityRandom Matrix Theory·Captain: mikedeng1

User-Friendly Tail Bounds for Sums of Random Matrices III: The Matrix Chernoff Inequality for Sums of Independent Positive-Semidefinite Random MatricesResearch Paper

The classical Chernoff bound controls the probability that a sum of independent, nonnegative, uniformly bounded random variables deviates from its mean, with exponentially small tails governed by the Kullback–Leibler divergence between two Bernoulli laws. Many problems in numerical linear algebra, graph sparsification, compressed sensing and randomized…

8 thms1 active userReviewed
ProbabilityRandom Matrix Theory·Captain: mikedeng1

Random Matrices: Universality of ESDs and the Circular Law 2: The ESD of A_n/√n Converges to μ iff the Normalized Log-Determinants of A_n/√n − zI Converge to μ's Log-Potential for a.e. zResearch Paper

The eigenvalues of a large non-Hermitian random matrix are hard to study directly. For Hermitian matrices, the empirical spectral distribution (ESD) is controlled by the resolvent and the Stieltjes transform, both stable under small perturbations. For non-Hermitian matrices no such tool exists: eigenvalues can move a long way under tiny perturbations, and…

10 thms1 active userReviewed
Numerical AnalysisOptimization·Captain: mikedeng1

The Primal-Dual Active Set Strategy as a Semismooth Newton Method III: Global Convergence under the Norm and Cone ConditionsResearch Paper

Obstacle problems, contact problems and control-constrained optimal control problems lead, after discretization, to complementarity systems of the form "find y≤ψy \le \psiy≤ψ and λ≥0\lambda \ge 0λ≥0 with Ay+λ=fAy + \lambda = fAy+λ=f and λi(yi−ψi)=0\lambda_i(y_i - \psi_i) = 0λi​(yi​−ψi​)=0". The primal-dual active set strategy solves such systems by guessing which constraints are active, solving one linear…

10 thms1 active userReviewed
ProbabilityRandom Matrix Theory·Captain: mikedeng1

Random Matrices: Universality of ESDs and the Circular Law 1: For i.i.d. Zero-Mean Unit-Variance Entries, the ESD of (M_n + X_n)/√n Does Not Depend on the Entry Distribution in the LimitResearch Paper

The eigenvalues of a large random matrix with independent entries follow deterministic limiting laws. For non-Hermitian matrices with i.i.d. entries of mean zero and variance one, the circular law asserts that the eigenvalues of 1nXn\frac1{\sqrt n}X_nn​1​Xn​ become uniformly distributed on the unit disk. These laws are used across statistics (covariance and…

17 thms1 active userReviewed
Numerical AnalysisOptimization·Captain: mikedeng1

Projection-like Retractions on Matrix Manifolds IV: Within σ_r(X̄)/2 of a Rank-r Matrix, the Truncated SVD Is the Unique Nearest Matrix of Rank Exactly rResearch Paper

Optimization over sets of matrices of fixed rank comes up in low-rank matrix completion, model reduction, and the low-rank approximation of solutions of large matrix equations. A standard approach treats the constraint set as a Riemannian manifold and runs gradient or Newton-type methods on it (Absil, Mahony & Sepulchre 2008). Each iteration takes a step in…

8 thms1 active userReviewed
PreviousPage 5 of 5Next

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