We provide a generic toolkit for sparsifying the constraint set of linear programs (LPs). To this end, we reduce solving a linear program with n constraints and d variables (n≫ d), to solving a sequence of LPs defined over only a small subset of the constraints, obtained by adaptively sub-sampling the original set. We provide results for both the low and high precision regimes. To achieve the former result, we streamline and generalize the techniques from [Assadi '25] for approximately computing maximum matchings in the semi-streaming setting to the case of general LPs. For the latter, we robustify the methods of [Clarkson '95], which were originally designed for exact LP solvers. As a consequence we obtain fast approximate LP solvers which reduce the dependence on width and error from quadratic to linear, compared to vanilla multiplicative-weights based approaches. Additionally, we leverage our findings to obtain fast LP solvers in the quantum query access model, where the running time scales with √n. This completely decouples the component responsible for quantum speed-ups, solely represented by a generalization of Grover’s search, from its classical algorithmic counterpart.

Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by $k$ shortest paths has pathwidth at most $O(3^k)$. In this paper, we improve this upper bound on the pathwidth to a polynomial one; namely, we show that every graph whose edge set can be covered by $k$ shortest paths has pathwidth $O(k^4)$, answering a question from the same paper. Moreover, we prove that when $k\leq 3$, every such graph has pathwidth at most $k$ (and this bound is tight). Finally, we show that even though there exist graphs with arbitrarily large treewidth whose vertex set can be covered by $2$ isometric trees, every graph whose set of edges can be covered by $2$ isometric trees has treewidth at most $2$.

We provide the first nearly-linear time algorithm for approximating 𝓁_{q → p}-norms of non-negative matrices, for q ≥ p ≥ 1. Our algorithm returns a (1-ε)-approximation to the matrix norm in time Õ(1/(q ε) ⋅ nnz(A)), where A is the input matrix, and improves upon the previous state of the art, which either proved convergence only in the limit [Boyd '74], or had very high polynomial running times [Bhaskara-Vijayraghavan, SODA '11]. Our algorithm is extremely simple, and is largely inspired from the coordinate-scaling approach used for positive linear program solvers. Our algorithm can readily be used in the [Englert-Räcke, FOCS '09] to improve the running time of constructing O(log n)-competitive 𝓁_p-oblivious routings.

Image noise can often be accurately fitted to a Poisson-Gaussian distribution. However, estimating the distribution parameters from a noisy image only is a challenging task. Here, we study the case when paired noisy and noise-free samples are accessible. No method is currently available to exploit the noise-free information, which may help to achieve more accurate estimations. To fill this gap, we derive a novel, cumulant-based, approach for Poisson-Gaussian noise modeling from paired image samples. We show its improved performance over different baselines, with special emphasis on MSE, effect of outliers, image dependence, and bias. We additionally derive the log-likelihood function for further insights and discuss real-world applicability.