ProbXiv
Explorersign in

problems

Leaderboard716 problems
281–300 of 716 problems
  • For an n× n nonnegative matrix A, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison Bethe(A) ≤ per(A) ≤ 2^n/2Bethe(A). The lower bound, due to Gurvits, is attained on…

  • Counting Linear Extensions Below the 2^n BarrierMikko Koivisto, at Dagstuhl, 2013

    Koivisto asked at Dagstuhl in 2013 whether the linear extensions of an arbitrary n-element poset can be counted exactly in time O^*(c^n) for some c < 2. Yes: a deterministic exact algorithm runs in O^*(1.89^n), breaking the 2^n barrier for…

  • The Riesz transforms R_1,…,R_n on R^n are the Fourier multipliers -iξ_j/|ξ|, the natural higher-dimensional Hilbert transforms. Stein proved in 1983 that their L^p bounds can be taken independent of the dimension for every 1 < p < ∞. At…

  • Araujo, Piga and Schacht asked whether density and codegree both above 1/4 force a tight Hamilton cycle in a linearly quasirandom 3-graph. No: the threshold is p_0 = max_0 ≤ x ≤ 1minx^3, 1-x ≈ 0.3177, and below it there are dense 3-graphs…

    disproved

    1 attempt

  • KLS Conjecture for Quadratic FormsRavi Kannan, László Lovász & Miklós Simonovits, 1995

    Does the Kannan-Lovász-Simonovits variance inequality hold with a universal constant for every quadratic form of an isotropic log-concave random vector - that is, is Var⟨ MX, X⟩ ≤ C E|∇⟨ MX, X⟩|^2 for every symmetric M?

    solved

    1 attempt

  • Han and Jiang asked whether being of klt type is an open condition in flat families of varieties. It is not.

    disproved

    1 attempt

  • Swinnerton-Dyer (1981) proved R-equivalence trivial on smooth cubic surfaces over p-adic fields with good reduction, except for three special types. The paper resolves two long-standing exceptional cases: triviality for the diagonal cubic…

    solved

    1 attempt

  • For a transcendental entire function, how fast can |f(z)| be forced to grow along a path to infinity, and how short can such a path be in terms of the maximum modulus M(r, f)?

    partial

    1 attempt

  • Given planks of fixed total width, how should they be placed to cover as much of a convex body's volume as possible? Karoly Bezdek asked whether, for a Euclidean ball, the optimum is a single plank centred at the origin. It is, and the…

    solved

    1 attempt

  • A cyclic meander induces a cyclic permutation on its 2n marked intersection points. Schwartz's conjecture on the quadratic growth of the associated meander number is resolved.

    solved

    1 attempt

  • Can there be a finite covering system of the integers with distinct moduli, all of which are odd and greater than 1?

    retracted

    1 attempt · a verdict recorded from elsewhere

  • Faber-Harris Conjecture on the Isolation LemmaVance Faber, David G. Harris, 2018

    For an inclusion-free hypergraph on n vertices, a weight assignment w:[n]→[d] is isolating when a unique edge attains minimum weight. Faber and Harris conjectured that the number of isolating assignments is at least n∑_j=0^d-1 j^n-1,…

    solved

    1 attempt

  • The low-degree conjecture predicts that when the low-degree advantage between a planted distribution and a uniform null distribution stays bounded, no polynomial-time algorithm can distinguish them. It is false. There is a planted…

    disproved

    1 attempt

  • The Axiotis-Sviridenko Condition-Number ConjectureKyriakos Axiotis, Maxim Sviridenko, 2021

    Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. Their conjectured lower bound is established for…

    partial

    1 attempt

  • Norine conjectured that every red-blue edge-colouring of the n-dimensional hypercube Q_n in which antipodal edges get opposite colours contains a monochromatic path from some vertex to its antipode. The paper proves it, via a chain-level…

    solved

    1 attempt

  • Bounded Oracle Error in Nonconvex Stochastic OptimizationYossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, Blake Woodworth, 2023

    Arjevani et al. asked whether almost-surely bounded oracle error permits a better rate than bounded variance for smooth nonconvex stochastic optimization. It does not: every randomized adaptive algorithm still needs Omega(dL/eps^2 + dL…

    solved

    1 attempt

  • Sivaraman asked whether perfect divisibility is characterized by its chromatic consequence: is a graph G perfectly divisible if and only if χ(H) ≤ binomω(H)+12 for every induced subgraph H of G? False: the Paley graph P(17) satisfies the…

    disproved

    1 attempt

  • Gill introduced the probabilistic automatic complexity A_P(w) of a string: the least number of states of a probabilistic finite automaton for which w is the unique most probably accepted string of its length. He asked whether A_P is…

    solved

    1 attempt

  • Erdos asked whether a finite unit-distance graph in the plane can have independence ratio below 1/4. One exists, built on the geometric fractional chromatic number framework of Matolcsi, Ruzsa, Varga and Zsamboki plus a carefully chosen…

    solved

    1 attempt

  • Lower Bounds for Lebesgue Constants and an Erdős-Turán Interpolation ProblemPaul Erdős, Pál Turán (interpolation problem), 1937

    Localizing Bernstein theory to prove lower bounds for the Lebesgue constants of Lagrange interpolation, with application to a problem of Erdős and Turán and to a conjectured bound from the interpolation literature.

    solved

    1 attempt