Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Whether perfectly complete quantum key agreement can be built from quantumly secure one-way functions in a black-box way. It cannot: for any protocol where Alice and Bob exchange only classical messages, make at most q_A and q_B quantum…
Can a Cohn-Elkies auxiliary function certify the best known sphere packing in dimension 36 as optimal? No. An explicit dual-feasible point for the Cohn-Elkies linear program, built from weight-18 modular forms for Γ_0(24), shows the…
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
For single-source unsplittable flow, every fractional flow can be rounded to an unsplittable flow whose cost is no higher than the fractional cost, while each arc's load is exceeded by at most the maximum demand. (The cost version of…
Let n_1<n_2<… be a lacunary sequence of integers and f∈ L^2([0,1]) with nth Fourier partial sum f_n. Is there an absolute constant C>0 such that if | f-f_n|_2 ≪ (logloglog n)^-C then 1/N∑_k≤ Nf(α n_k)→∫_0^1 f for almost every α? A preprint…
Let n_k be the least integer greater than 2k for which ∏_i=1^k (n_k - i) has no prime factor in (k, 2k). How rapidly must n_k grow?
A Banach space is primary if in every decomposition into two complemented subspaces one summand is isomorphic to the whole. Lechner, Motakis, Müller and Schlumprecht identified the primariness of L_p(L_1) as a prominent remaining open…
The realisation problem asks which unital Banach algebras arise as the Calkin algebra B(X)/K(X) of some Banach space. Recorded in Tarbard's thesis and studied by Horváth and Kania. The paper exhibits a unital Banach algebra that cannot be…
Vinzant conjectured, in a form later restated by Bandeira, that the 4M-4 threshold for injective complex phase retrieval is sharp. Part (1) holds: for A ∈ C^N × M with N = 4M-5 and i.i.d. standard complex Gaussian entries, the phase…
Must every sufficiently large node set admit bounded labels that force any polynomial fitting almost all labels at degree below (1+ε)n to have arbitrarily large uniform norm? Claimed via Beurling density for Bernstein spaces.
Let μ be a probability measure on the unit circle with Verblunsky coefficients α. Lukic conjectured that a weighted entropy condition with finitely many critical points is equivalent to a decomposition of α into components localized at…
How well can an arbitrary boolean constraint satisfaction problem of arity k be approximated in polynomial time? The paper gives a (k/2^k)-approximation, improving the previous best constant of 0.626612 k/2^k due to Makarychev and…
Steurer conjectured in 2010 that any family of n unit vectors with polynomially small average correlation E_i,j|⟨ v_i,v_j⟩| ≤ n^-ε contains linear-sized constant-separated sets. Refuted in a strong sense, using sparse high-dimensional…
Erdos and Graham asked whether a positive-density subset of 1,…,N can avoid having any two distinct elements a,b whose unit fractions average to a unit fraction. It can: there is a constant c>0 such that for all large N some A ⊆ 1,…,N of…
The unrestricted planar Berenstein conjecture holds that overdetermined Dirichlet-Neumann data characterize the disc. Disproved: a bounded simply connected domain with real-analytic Jordan boundary that is not a disc, carrying a nonzero…
Given online vectors v_t ∈ R^d with |v_t|_2 ≤ 1, can signs ε_t ∈ -1, 1 be chosen in O(dT) total time so that every prefix has ℓ_∞ discrepancy O(√log T) with high probability? The previous optimal algorithm ran in time exponential in T and…
The Exact Matching problem asks whether a bipartite graph with edges colored red and blue admits a perfect matching with exactly t red edges. Introduced by Papadimitriou and Yannakakis in 1982, it has been in randomized polynomial time…
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
Banks and Martin conjectured in 2013 that for a primitive set A and any set Q of primes, the Erdos sum of the members of A composed only of primes in Q is at most the corresponding sum over Q itself. The unrestricted form turned out to be…
Ziegler proved every simplicial d-dimensional 0/1-polytope has at most 2d vertices, and asked whether attaining 2d vertices forces central symmetry (i.e. a 0/1 cross-polytope). Known true for d ≤ 6; open since ~2000.