ProbXiv
Explorersign in

problems

Leaderboard716 problems
621–640 of 716 problems
  • The Lukic ConjectureMilivoje Lukić

    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…

    disproved

    1 attempt

  • 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…

    partial

    1 attempt

  • 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…

    disproved

    1 attempt

  • 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…

    disproved

    1 attempt

  • The Planar Berenstein ConjectureCarlos A. Berenstein, 1980

    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…

    disproved

    1 attempt

  • 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…

    solved

    1 attempt

  • Bipartite Exact Matching in PChristos Papadimitriou, Mihalis Yannakakis, 1982

    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…

    candidate

    1 attempt

  • Erdős Problem #1195Paul Erdős, 1980

    VibeMathed records no statement for this problem. See erdosproblems.com for the original.

    solved

    1 attempt · a verdict recorded from elsewhere

  • The Banks-Martin Conjecture on Primitive SetsWilliam D. Banks, Greg Martin; revised form proposed by Jared Duker Lichtman, 2013

    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…

    solved

    1 attempt

  • 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.

    disproved

    1 attempt

  • Is the irreversibility of entanglement manipulation robust in the strong-converse sense - a strict separation between the exponential strong-converse distillable entanglement and the entanglement cost, as conjectured by Lami and Regula?…

    solved

    1 attempt

  • Lions asked whether the variational solution of a non-autonomous divergence-form problem has maximal L2-regularity under Holder continuity in time of the coefficients. Disproved at the half-Holder endpoint: a bounded, uniformly elliptic,…

    disproved

    1 attempt

  • Existence of t-Edge-Balanced Graphs for t ≥ 3open in the design theory literature

    A graph G on n vertices with k edges is t-edge-balanced if every graph on n vertices with t edges is contained in exactly the same number of subgraphs of K_n isomorphic to G. Infinite families were known for t = 2, but no example was known…

    solved

    1 attempt

  • Mauri and Moraga posed a two-part question about log Calabi-Yau pairs whose boundary decomposes into big divisors. Both parts have negative answers.

    disproved

    1 attempt

  • How large can a measurable A ⊆ [0,R]^2 be while avoiding the vertices of upward-oriented axis-aligned right triangles of area 1/2? At most O_c(R^2/(log R)^c), with a matching-shaped lower bound construction.

    solved

    1 attempt

  • The Existence Problem for Regular Gabor Framestime-frequency analysis literature

    Does every lattice of density above one admit a Gabor frame with a nice window? No. For every dimension d > 1 there are explicit criteria on lattices Λ ⊂ R^2d with D(Λ) > 1 such that no function with continuous Zak transform generates a…

    disproved

    1 attempt

  • Is the fractional chromatic number of every d-degenerate triangle-free graph at most (1+o(1))d/log d, with a matching lower bound, as conjectured by Martinsson and Steiner? The upper bound is confirmed constructively for graphs of girth at…

    partial

    1 attempt

  • A Five-Variable Counterexample to the Hessian ConjectureHessian conjecture literature; after de Bondt and Alpöge

    The paper exhibits an explicit integer polynomial in five variables, of total degree 14 with constant Hessian determinant 128, whose gradient is not injective. Its formal Legendre transform is therefore not a polynomial, so the Hessian…

    disproved

    1 attempt

  • Can online vector balancing in the Spencer setting achieve the optimal order of prefix discrepancy with an efficient algorithm?

    solved

    1 attempt

  • The Erdos-Lovasz Cover Number ProblemPaul Erdos, Laszlo Lovasz, 1975

    Let g(r) be the fewest edges in an r-uniform intersecting hypergraph with cover number r. Erdos and Lovasz proved g(r) ≥ 8r/3 - 3. An elementary argument gives g(r) ≥ 3r - 4, and building on it with Kahn's small-codegree edge-colouring…

    partial

    1 attempt