# Tight Hardness Results for Maximum Weight Rectangles

arXiv: https://arxiv.org/abs/1602.05837 · HTML: https://mlsanity.com/paper/1602.05837/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2016.

## Built on by (most cited first, 6 of 6)

- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Data-Driven Subgroup Identification for Linear Regression](https://mlsanity.com/paper/2305.00195/) (2023)
- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Enhancing binary classification: A new stacking method via leveraging computational geometry](https://mlsanity.com/paper/2410.22722/) (2024)
- [Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance](https://mlsanity.com/paper/2504.11299/) (2025)

## Abstract (arXiv)

Given n weighted points (positive or negative) in d dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? The best known algorithm for this problem is based on a reduction to a related problem, the Weighted Depth problem [T. M. Chan, FOCS'13], and runs in time O(nd). It was conjectured [Barbay et al., CCCG'13] that this runtime is tight up to subpolynomial factors. We answer this conjecture affirmatively by providing a matching conditional lower bound. We also provide conditional lower bounds for the special case when points are arranged in a grid (a well studied problem known as Maximum Subarray problem) as well as for other related problems. All our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially optimal.