Problems
No problem here has yet been reviewed by a person.
For n ≥ 4, the natural scalar Poisson-summation certificates cannot prove the Regev-Stephens-Davidowitz Gaussian mass conjecture: any such certificate saturates, so the whole approach is blocked.
For P_n(z) = ∑_k=0^n ε_k z^k with independent uniform signs, does the number R_n of roots in |z| ≤ 1 satisfy R_n/(n/2) → 1 almost surely? The manuscript proves the strong law with R_n = n/2 + O_ω(n^149/150).
For deterministically minimizing a convex 1-Lipschitz function on the d-dimensional ball using only exact function values, the query complexity sat between Ω(d) and O(d^2 log^2 d) since 1996. The paper proves a near-quadratic lower bound…
Can the k-distinct language - words over [n] of length at most k with no repeated symbol - be recognized by an acyclic NFA of size c^k n^O(1) for some c < 4? A construction of size 2^1.96992k n^O(1) < 3.918^k n^O(1) answers yes.
Erdos and Hajnal asked whether h_r(G) = maxχ(H) : H ⊆ G, girth(H) ≥ r tends to infinity as χ(G) does, for every fixed r ≥ 4. It does in every fixed polynomial edge-density regime.
A subset A of the pointwise-ordered cube [0,1]^n is a k-antichain when it meets every chain in at most k points. The conjecture concerns the largest possible (n-1)-dimensional Hausdorff measure of such a set; it is settled here, following…
How many nondegenerate equilibrium points can the potential of three positive point charges have? Gabrielov, Novikov and Shapiro had proved at most 12, and observed that their method would give 6 if an auxiliary polynomial system had at…
Does every instance of indivisible goods with additive valuations admit a balanced allocation (any two bundles differing in size by at most one) that is simultaneously envy-free up to one good (EF1) and fractionally Pareto optimal (fPO)?…
Aldroubi, Cabrelli, Krishtal and Molter conjectured that for a bounded normal operator T and any vector g, the normalized orbit T^k g / |T^k g| : k ≥ 0 is never a frame. It can be: an explicit construction produces a normalized orbit that…
Kotzig conjectured that for every even n ≥ 4 the complete graph K_n decomposes into n-1 perfect matchings such that every pair of them forms a Hamilton cycle. An asymptotic version holds: K_n decomposes into n-1 perfect matchings of which…
Englert and Rehacek conjectured which measurement is globally information-optimal for an ensemble of equiangular equiprobable pure states. Their conjecture holds, via the remaining entropy inequalities of Holevo and Utkin.
Can an S-decoding polynomial modulo a suitable product of k primes attain the lower-bound minimum of k + 1 nonzero coefficients? A construction matches the bound for special products of k primes, yielding exponentially fewer-server PIR.
Dittert's conjecture asserts that among nonnegative n× n matrices whose entries sum to n, the functional φ(A)=∏_i r_i+∏_j c_j-per(A) is uniquely maximized by J_n/n. The paper proves the case n=16 which, with Pang's result for n≥17,…
Does there exist a good pairwise-coprime sequence u_n with ∑ 1/u_n < ∞ and polynomial growth? What if one only requires u_n ≤ e^o(n)?
Anari, Charikar and Ramakrishnan asked whether every fractional perfect matching admits a perfect matching that is α-thin with respect to it, meaning it crosses every cut at most α times the fractional amount. Resolved up to…
For every connected graph, is the deviation of its adjacency eigenvalues at most its order divided by its average distance? Exact lollipop-graph certificates refute the inequality when deviation means population standard deviation, under…
An ℓ-Oddtown is a family of subsets of an n-element set whose set sizes are not divisible by ℓ while all pairwise intersection sizes are. Berlekamp and Graver showed the maximum size is n for prime ℓ, Babai and Frankl extended this to…
A tournament orients every pair in a round-robin (winner → loser). The score sequence is the sorted win-count list. Reversing a directed 3-cycle never changes scores, so score-equivalent tournaments can look structurally different.…
Do n point charges whose electrostatic potential has only non-degenerate critical points always have at most (n-1)^2 of them? A configuration of five charges - three at the vertices of an equilateral triangle plus two small central charges…
Godara and Sarkar proved d(H_27)=6 for the exponent-p Heisenberg group and posed d(H_p^3)=3p-3 for every odd prime p, leaving p≥5 open. The paper settles the first open case, d(H_125)=12, the upper bound reducing to a finite spread bound…