Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Harmonic Analysis

87 missions · 46 completed

Missions

Open41Completed46All87
AlgebraAnalysisCombinatorics+3·Captain: LG

Formal Conjectures Portfolio: Bateman-Horn and CompanionsOpen Problem

Wikipedia's pages on open problems are, for many mathematicians, the first contact with a conjecture: a one-paragraph statement, a short history, a list of partial results. The Formal Conjectures library (Google DeepMind, Apache-2.0) turned a large part of that material into Lean 4 statements, so that the conjectures can be attacked — and, just as…

100 thms16 active usersReviewed
AnalysisMathematical PhysicsQuantum Information·Captain: iris

Sensing frequencies at the discrete Grover-Heisenberg limit using a single qubitResearch Paper

Quantum sensing uses a controlled quantum system to detect weak fields. In AC magnetometry a single qubit, such as a nitrogen-vacancy centre in diamond, feels a field Bcos⁡(ωt+ϕ)B\cos(\omega t+\phi)Bcos(ωt+ϕ) along its ZZZ axis. A conventional protocol needs evolution time Θ(1/B)\Theta(1/B)Θ(1/B) per candidate frequency, so scanning NNN candidates costs Θ(N/B)\Theta(N/B)Θ(N/B). Allen et al. ([AMC+25])…

23 thms5 active usersReviewed
CombinatoricscryptographyInformation Theory+1·Captain: Shuze Chen

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial IntersectionResearch Paper

In Shamir secret sharing over a prime field Fp\mathbb F_pFp​, a secret sss is shared among nnn parties by a uniformly random polynomial PPP of degree at most kkk with P(0)=sP(0)=sP(0)=s; party iii receives P(αi)P(\alpha_i)P(αi​) for distinct nonzero evaluation points αi\alpha_iαi​. Any k+1k+1k+1 parties recover the secret and any kkk learn nothing about it. Local leakage resilience (LLR) asks for more: if…

24 thms4 active usersReviewed
cryptographyTheoretical Computer Science·Captain: iris

Local Leakage Resilience of Multiplication-friendly Shamir Secret SharingResearch Paper

Shamir secret sharing splits a secret among mmm parties so that any d+1d+1d+1 of them can reconstruct it while any ddd learn nothing (Shamir 1979). Deployed systems run on physical devices, and devices leak. Local leakage resilience, introduced by Benhamouda, Degwekar, Ishai and Rabin (BDIR18, BDIR21), asks whether a small amount of leakage from every share — one bit…

32 thms4 active usersReviewed
Number TheoryProbabilityTheoretical Computer Science·Captain: iris

When Masks Leak Their Weight: From Additive Sharing to Learning with Physical RoundingResearch Paper

Masking protects a secret held by a physical device by splitting it into random additive shares that sum to the secret modulo NNN; each share alone is uniformly distributed. In practice the device leaks a noisy function of every share it touches, and the standard model of that leakage on CMOS hardware is the Hamming weight of the share: the number of ones in…

41 thms4 active usersReviewed
Information TheoryProbabilityTheoretical Computer Science·Captain: iris

A Nonadaptive Sparse Fourier Transform in Every DimensionResearch Paper

A sparse Fourier transform recovers the few large Fourier coefficients of a signal from far fewer samples than the signal's length, and in time polynomial in the number of coefficients rather than in the length. It is used whenever a spectrum is dominated by a small number of frequencies and reading the whole signal is expensive. The standard accuracy…

24 thms4 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: Shuze Chen

A Counting Lemma for Somewhat Restricted 3-APsResearch Paper

Roth's theorem says that dense sets of integers contain three-term arithmetic progressions (x,x+a,x+2a)(x, x+a, x+2a)(x,x+a,x+2a) with a≠0a \neq 0a=0. Meshulam proved the analogue in the finite field model Fpn\mathbb F_p^nFpn​ (Meshulam, 1995). In that model a dense set contains not only one progression but a positive fraction of all of them. This counting statement follows from the existence…

27 thms3 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: iris

Learning Mixtures with Unknown Scales: Sharp Dependence on SeparationResearch Paper

Finite mixture models describe a heterogeneous population as a weighted combination of component distributions. Recovering the locations, scales and weights of the components from samples is a central problem in statistics and learning theory, with a long line of work on Gaussian mixtures and other parametric families (Kalai, Moitra, Valiant 2010; Moitra,…

27 thms3 active usersReviewed
OptimizationProbabilityTheoretical Computer Science·Captain: iris

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation HierarchyResearch Paper

Maximizing a homogeneous polynomial PPP of degree ddd over the unit sphere, ∥P∥∞=max⁡x∈Sn−1∣P(x)∣\|P\|_\infty=\max_{x\in S^{n-1}}|P(x)|∥P∥∞​=maxx∈Sn−1​∣P(x)∣, is the spectral norm of a symmetric tensor. It is NP-hard already for order-three tensors (Hillar–Lim 2013), so the useful questions are approximation and certification: find a tractable upper bound and measure how far it can be from the truth.

49 thms3 active usersReviewed
Functional Analysis·Captain: mikedeng1

Isotropic Gaussian Random Fields on the Sphere: Regularity, Fast Simulation and Stochastic Partial Differential Equations I: u ∈ V^η(−1,1) iff Σ u_ℓ²(2ℓ+1)(1+ℓ^{2η}) < ∞Research Paper

A centered isotropic Gaussian random field TTT on the unit sphere S2\mathbb S^2S2 is determined by its angular power spectrum (Aℓ)ℓ≥0(A_\ell)_{\ell \ge 0}(Aℓ​)ℓ≥0​: its covariance is

11 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? 3: Low-Influence Functions Have Level-One Fourier Weight at Most 2/π + CδResearch Paper

Fourier analysis of functions on the discrete cube {−1,1}n\{-1,1\}^n{−1,1}n is the main tool behind tight inapproximability results under the Unique Games Conjecture. In the MAX-CUT reduction of Khot, Kindler, Mossel and O'Donnell (SIAM J. Comput. 2007), soundness rests on the Majority Is Stablest theorem: among bounded functions in which no coordinate has large…

7 thms3 active usersReviewed
Combinatorics·Captain: LG

Arithmetic Kakeya: constructible proofs below 1.6751.6751.675Open Problem

A Kakeya set in Rd\mathbb{R}^dRd is a bounded set that contains a unit line segment in every direction. Besicovitch showed that such sets can have Lebesgue measure zero, and the Kakeya conjecture asserts that they must nevertheless be as large as possible in a dimensional sense: every Kakeya set in Rd\mathbb{R}^dRd has Hausdorff and Minkowski dimension ddd. The…

16 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Sparsest Cut on Abelian Cayley GraphsResearch Paper

The sparsest cut problem asks for a set of vertices of a graph that is poorly connected to the rest. It is NP-hard to solve exactly, and the best polynomial-time guarantee for general graphs remains the O(log⁡n)O(\sqrt{\log n})O(logn​) approximation of Arora, Rao and Vazirani (ARV09); no subexponential-time constant-factor approximation is known for general graphs. This…

17 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: Shuze Chen

Efficient Non-Adaptive Sparse Fourier Learning on the Boolean Cube and Finite Abelian GroupsResearch Paper

Learning a real function on the Boolean cube from a few of its values is a basic task in computational learning theory, property testing and signal processing on {0,1}d\{0,1\}^d{0,1}d. Many functions in these areas are close to a combination of a few parities. When such a function is sampled only at chosen points, the natural goal is to find a short Fourier expansion…

15 thms2 active usersReviewed
Algorithmic Game TheoryMachine Learning·Captain: Shuze Chen

High-Dimensional Online Calibration from Harmonic WeightsResearch Paper

A calibrated forecaster is one whose forecasts can be taken at face value: among the rounds on which it announced a forecast ppp, the outcomes average to ppp. Calibration is what a downstream decision maker needs in order to best-respond to forecasts with vanishing regret, and in the vector-valued case it drives Blackwell approachability and swap-regret…

11 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Sharp Limits of Time Invariance in Private Continual CountingResearch Paper

Continual counting releases an estimate of a running sum whenever another stream element arrives. The same person’s contribution must remain protected across the entire sequence of releases. Streams without a known stopping time make this a distinct design problem: a mechanism chosen for one horizon does not automatically define one mechanism that works…

23 thms2 active usersReviewed
Graph TheoryProbabilityStatistics·Captain: iris

Sharp detection thresholds for random geometric graphs with polynomial average degreesResearch Paper

A random geometric graph (RGG) hides a latent geometry: each vertex carries a random point, and edges join nearby points. In high dimension the geometry washes out, and a basic question in probability, statistics and theoretical computer science is the dimension at which the graph becomes statistically indistinguishable from an Erdős–Rényi graph with the…

34 thms2 active usersReviewed
ProbabilityQuantum Information·Captain: iris

Robust quantum state certification and uncertainty principles for total influenceResearch Paper

State certification asks whether a laboratory state ρ\rhoρ is close to a pure target state ∣ψ⟩|\psi\rangle∣ψ⟩. It is a basic benchmark for quantum devices (Badescu, O'Donnell, Wright 2019; Kliesch, Roth 2021). The optimal test is the projective measurement {∣ψ⟩⟨ψ∣,1−∣ψ⟩⟨ψ∣}\{|\psi\rangle\langle\psi|,1-|\psi\rangle\langle\psi|\}{∣ψ⟩⟨ψ∣,1−∣ψ⟩⟨ψ∣}, but implementing it is in general as hard as…

40 thms2 active usersReviewed
Information TheoryProbabilityTheoretical Computer Science·Captain: iris

Quasipolynomial Trace ReconstructionResearch Paper

A deletion channel with retention probability ppp takes a binary string x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n, keeps each bit independently with probability ppp, and outputs the kept bits in order; the output is a trace. The trace reconstruction problem asks how many independent traces are needed to recover an unknown xxx with probability at least 2/32/32/3. It is a basic question about…

26 thms2 active usersReviewed
Functional AnalysisMathematical PhysicsQuantum Information·Captain: iris

Introduction to Quantum Noise, Measurement and Amplification: the quantum noise inequality gives the standard quantum limit on the added noise of a linear position detectorResearch Paper

A weak measurement of a quantum system, or the amplification of a weak signal, always adds noise. The review of Clerk, Devoret, Girvin, Marquardt and Schoelkopf (arXiv:0810.4729, Rev. Mod. Phys. 82, 1155, 2010) derives the size of this unavoidable noise in a linear-response framework that assumes almost nothing about the detector: some stationary quantum…

22 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

Information Design and Sharing in Supply Chains: with no information sharing, Σ²_NS(σ) = (σ_ε²/4)(5 − log(4σ²/σ_ε²)) for σ < σ_ε/2 and σ_ε² + ((σ_ε − σ)⁺)² for σ ≥ σ_ε/2Research Paper

In a two-tier supply chain a retailer orders from a supplier, and the supplier must forecast those orders. If the retailer shares its demand data, the supplier forecasts with full information. If not, the supplier sees only the order stream. A large literature (Lee, So and Tang 2000; Gavirneni, Kapuscinski and Tayur 1999; Giloni, Hurvich and Seshadri 2014)…

17 thms2 active usersReviewed
Functional AnalysisRepresentation Theory·Captain: mikedeng1

On the Characterization of Trace Class Representations and Schwartz Operators: A Unitary Lie Group Representation Is Trace Class iff Some (1 − dπ(Δ))⁻ᵏ Is Trace Class iff π(Cᵐ_c(G)) ⊆ B₁ for Some mResearch Paper

A strongly continuous unitary representation turns each group element into a unitary operator on a Hilbert space. Averaging those operators against a smooth, compactly supported function gives a bounded operator. When every such average is trace class, its trace defines a distribution character. The trace condition is therefore a bridge from an operator…

12 thms2 active usersReviewed
Linear algebraQuantum Information·Captain: mikedeng1

Product Decomposition of Periodic Functions in Quantum Signal Processing: Every SU(2)-Valued Laurent Polynomial of Degree n in E_n Is Uniquely a Product of n Primitive Matrices and a UnitaryResearch Paper

Quantum signal processing transforms the eigenphases of a unitary operator by a sequence of controlled operations and single qubit rotations. To know which transformations such a sequence can realize, one must characterize the matrix functions produced by the sequence. Haah's product decomposition theorem gives such a characterization without the…

10 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Optimal Hamiltonian Simulation by Quantum Signal Processing: Phases Realizing e^{ih(θ)} to Error 8ε With Success Probability at Least 1 − 16εResearch Paper

Simulating the time evolution of a quantum system is a standard task in quantum algorithms: given a Hamiltonian, the algorithm must reproduce the phase acquired by each of its energy eigenstates. The cost is often measured by how many times the algorithm queries an operator describing that system. Low and Chuang's 2016 preprint connects this task to quantum…

10 thms2 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Learning and Optimization with Seasonal Patterns 1: Regret Upper Bound for the Two-Stage Period-Estimation and Confidence-Bound PolicyResearch Paper

Many demand, traffic and click-through series are seasonal: their mean repeats after a fixed number of periods (a week of days, a year of months), while the length of that cycle is not known in advance. A retailer choosing among KKK promotions, or a platform choosing among KKK recommendations, then faces a multi-armed bandit whose arms have time-varying but…

17 thms2 active usersReviewed
PreviousPage 1 of 2Next

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