18 problems

Can every fractional single-source unsplittable flow be rounded without increasing either edge congestion or total cost?

Can the total variation distance between two explicitly specified product distributions be multiplicatively approximated in time linear in the input size?

Can the minimum edge-outerplanarity of a finite loopless planar graph—minimized over all planar embeddings—be computed in polynomial time?

How many function-value queries are necessary for deterministic optimization of a Lipschitz convex function in high dimension?

Does the greedy algorithm for monotone submodular maximization over a $p$-system achieve a $(1-\varepsilon,\lceil\log_{p+1}(1/\varepsilon)\rceil)$ bicriteria approximation? If not,…

For fixed $d$, can every $d$-dimensional feasible solution of the triangle-strengthened Max-Cut SDP be rounded in polynomial time with ratio strictly larger than $\alpha_{GW}$?

Is the expected marginal gain from copying an item to the end of a random-order stream always at most the gain from moving its original occurrence there?

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

Given Manhattan terminals, a root, a total-length budget, and a source-radius budget, is deciding whether a spanning tree meets both bounds polynomial-time solvable?

Does the threshold-policy structure of the Lin–Kumar two-server queue remain optimal once a third heterogeneous server is introduced?

For well-conditioned symmetric quadratic losses, must the expected single-shuffle, random-reshuffle, and gradient-descent operators satisfy…

For a monotone $K$-Lipschitz saddle operator arising from a smooth convex–concave min–max problem, can anchored gradient descent–ascent be scheduled so that its exact last-iterate…

Does the proposed flip–repair Markov chain mix rapidly enough to yield a nearly uniform directed-Eulerian-tour sampler in $\widetilde O(m^{3/2})$ worst-case time?

Given online vectors $v_t\in\mathbb{R}^d$ with $\lVert v_t\rVert_2\leq1$, can signs $\varepsilon_t\in\{-1,1\}$ be chosen in $O(dT)$ time so that every prefix has $\ell_\infty$ disc…

For every finite training set, does exhaustive AdaBoost eventually converge to a finite cycle of weak classifiers and weight vectors?

Can the central equivalence and universality results connecting polynomial ODEs, chemical reaction networks, linear production protocols, and stochastic mean-field limits be assemb…

What is the optimal exponential approximation ratio achievable in deterministic polynomial time for the permanent of a Hermitian positive-semidefinite matrix?

Under the standard smoothness and bounded-variance assumptions, how fast can vanilla stochastic multi-gradient descent drive the squared Pareto-stationarity measure toward zero?