Karl Bringmann
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Karl Bringmann has a total of 65 co-authors. Here are the top co-authors by number of shared publications:
- Marvin Künnemann
KIT, Karlsruhe, Germany
5 shared publications - Amir Abboud
Weizmann Institute of Science, Rehovot, Israel
3 shared publications - Danny Hermelin
Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
3 shared publications - Dvir Shabtay
Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
3 shared publications - Johannes Lengler
Institute of Theoretical Computer Science ETH Zurich Switzerland
3 shared publications - Nofar Carmeli
Inria, LIRMM, University of Montpellier, CNRS, Montpellier, France
3 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 2094-2105
Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 2094-2105
Open AccessTight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 330-341
Fine-Grained Complexity of Continuous Euclidean k-Center
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 330-341
Open AccessFine-Grained Complexity of Continuous Euclidean k-Center
- Open Access
- 30 May 2026
- Published by Association for Computing Machinery (ACM)
- p. 18
Fine-grained Complexity of Database Queries
Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds. Starting from a popular conjecture about the time complexity of a core problem (e.g., the Strong Exponential Time Hypothesis for the Satisfiability problem), we can design fine-grained reductions to transfer the conjectured intractability to other problems, yielding conditional lower bounds. After initial results in the 90s, the field has matured over the last 15 years, demonstrating its usefulness across many areas of computer science including graph algorithms, optimization, computational geometry, and string processing. Naturally, fine-grained complexity has also found compelling applications in database theory, specifically for join queries and, more generally, conjunctive queries, which generalize graph pattern matching problems that are fundamental in graph algorithms. In this talk, we will discuss recent results on listing, enumeration, and direct access algorithms for join queries and conjunctive queries, thereby exploring the intersection of database theory and graph algorithms through the lens of fine-grained complexity. Specifically, we address the quest for optimal output-sensitive algorithms for join queries. For a fixed join query Q, we ask: what is the smallest exponent c(Q) such that the query can be answered in time O(nc(Q)+t), where n is the database size and t is the number of query answers? While algorithm design establishes upper bounds on c(Q), fine-grained complexity provides the complementary conditional lower bounds. Although the grand goal of determining a conditionally optimal c(Q) for every join query currently remains out of reach, we discuss significant recent progress. This includes a full classification of all graph queries with an exponent c(Q)<2 [3], alongside a complete resolution to the corresponding question for direct access [2]. Finally, extending this framework to conjunctive queries, we explore recent advances in applying output-sensitive fast matrix multiplication [1], and establishing the equivalence of listing and enumeration.
- 30 May 2026
- Published by Association for Computing Machinery (ACM)
- p. 18
Open AccessFine-grained Complexity of Database Queries
Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds. Starting from a popular conjecture about the time complexity of a core problem (e.g., the Strong Exponential Time Hypothesis for the Satisfiability problem), we can design fine-grained reductions to transfer the conjectured intractability to other problems, yielding conditional lower bounds. After initial results in the 90s, the field has matured over the last 15 years, demonstrating its usefulness across many areas of computer science including graph algorithms, optimization, computational geometry, and string processing. Naturally, fine-grained complexity has also found compelling applications in database theory, specifically for join queries and, more generally, conjunctive queries, which generalize graph pattern matching problems that are fundamental in graph algorithms. In this talk, we will discuss recent results on listing, enumeration, and direct access algorithms for join queries and conjunctive queries, thereby exploring the intersection of database theory and graph algorithms through the lens of fine-grained complexity. Specifically, we address the quest for optimal output-sensitive algorithms for join queries. For a fixed join query Q, we ask: what is the smallest exponent c(Q) such that the query can be answered in time O(nc(Q)+t), where n is the database size and t is the number of query answers? While algorithm design establishes upper bounds on c(Q), fine-grained complexity provides the complementary conditional lower bounds. Although the grand goal of determining a conditionally optimal c(Q) for every join query currently remains out of reach, we discuss significant recent progress. This includes a full classification of all graph queries with an exponent c(Q)<2 [3], alongside a complete resolution to the corresponding question for direct access [2]. Finally, extending this framework to conjunctive queries, we explore recent advances in applying output-sensitive fast matrix multiplication [1], and establishing the equivalence of listing and enumeration.
- Open Access
Dynamic and Streaming Algorithms for Union Volume Estimation
The union volume estimation problem asks to $(1\pm\varepsilon)$-approximate the volume of the union of $n$ given objects $X_1,\ldots,X_n \subset \mathbb{R}^d$. In their seminal work in 1989, Karp, Luby, and Madras solved this problem in time $O(n/\varepsilon^2)$ in an oracle model where each object $X_i$ can be accessed via three types of queries: obtain the volume of $X_i$, sample a random point from $X_i$, and test whether $X_i$ contains a given point $x$. This running time was recently shown to be optimal [Bringmann, Larsen, Nusser, Rotenberg, and Wang, SoCG'25]. In another line of work, Meel, Vinodchandran, and Chakraborty [PODS'21] designed algorithms that read the objects in one pass using polylogarithmic time per object and polylogarithmic space; this can be phrased as a dynamic algorithm supporting insertions of objects for union volume estimation in the oracle model. In this paper, we study algorithms for union volume estimation in the oracle model that support both insertions and deletions of objects. We obtain the following results: - an algorithm supporting insertions and deletions in polylogarithmic update and query time and linear space (this is the first such dynamic algorithm, even for 2D triangles); - an algorithm supporting insertions and suffix queries (which generalizes the sliding window setting) in polylogarithmic update and query time and space; - an algorithm supporting insertions and deletions of convex bodies of constant dimension in polylogarithmic update and query time and space.Open AccessDynamic and Streaming Algorithms for Union Volume Estimation
The union volume estimation problem asks to $(1\pm\varepsilon)$-approximate the volume of the union of $n$ given objects $X_1,\ldots,X_n \subset \mathbb{R}^d$. In their seminal work in 1989, Karp, Luby, and Madras solved this problem in time $O(n/\varepsilon^2)$ in an oracle model where each object $X_i$ can be accessed via three types of queries: obtain the volume of $X_i$, sample a random point from $X_i$, and test whether $X_i$ contains a given point $x$. This running time was recently shown to be optimal [Bringmann, Larsen, Nusser, Rotenberg, and Wang, SoCG'25]. In another line of work, Meel, Vinodchandran, and Chakraborty [PODS'21] designed algorithms that read the objects in one pass using polylogarithmic time per object and polylogarithmic space; this can be phrased as a dynamic algorithm supporting insertions of objects for union volume estimation in the oracle model. In this paper, we study algorithms for union volume estimation in the oracle model that support both insertions and deletions of objects. We obtain the following results: - an algorithm supporting insertions and deletions in polylogarithmic update and query time and linear space (this is the first such dynamic algorithm, even for 2D triangles); - an algorithm supporting insertions and suffix queries (which generalizes the sliding window setting) in polylogarithmic update and query time and space; - an algorithm supporting insertions and deletions of convex bodies of constant dimension in polylogarithmic update and query time and space. - Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2145-2156
A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2145-2156
Open AccessA Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
- Open Access
- 27 March 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
We study the enumeration of answers to Unions of Conjunctive Queries (UCQs) with optimal time guarantees. More precisely, we wish to identify the queries that can be solved with linear preprocessing time and constant delay. Despite the basic nature of this problem, it was shown only recently that UCQs can be solved within these time bounds if they admit free-connex union extensions, even if all individual CQs in the union are intractable with respect to the same complexity measure. Our goal is to understand whether there exist additional tractable UCQs, not covered by the currently known algorithms. As a first step, we show that some previously unclassified UCQs are hard using the classic 3SUM hypothesis, via a known reduction from 3SUM to triangle listing in graphs. As a second step, we identify a question about a variant of this graph task that is unavoidable if we want to classify all self-join-free UCQs: is it possible to decide the existence of a triangle in a vertex-unbalanced tripartite graph in linear time? We prove that this task is equivalent in hardness to some family of UCQs. Finally, we show a dichotomy for unions of two self-join-free CQs if we assume the answer to this question is negative. In conclusion, this paper pinpoints a computational barrier in the form of a single decision problem that is key to advancing our understanding of the enumeration complexity of many UCQs. Without a breakthrough for unbalanced triangle detection, we have no hope of finding an efficient algorithm for additional unions of two self-join-free CQs. On the other hand, a sufficiently efficient unbalanced triangle detection algorithm can be turned into an efficient algorithm for a family of UCQs currently not known to be tractable.
- 27 March 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Open AccessUnbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
We study the enumeration of answers to Unions of Conjunctive Queries (UCQs) with optimal time guarantees. More precisely, we wish to identify the queries that can be solved with linear preprocessing time and constant delay. Despite the basic nature of this problem, it was shown only recently that UCQs can be solved within these time bounds if they admit free-connex union extensions, even if all individual CQs in the union are intractable with respect to the same complexity measure. Our goal is to understand whether there exist additional tractable UCQs, not covered by the currently known algorithms. As a first step, we show that some previously unclassified UCQs are hard using the classic 3SUM hypothesis, via a known reduction from 3SUM to triangle listing in graphs. As a second step, we identify a question about a variant of this graph task that is unavoidable if we want to classify all self-join-free UCQs: is it possible to decide the existence of a triangle in a vertex-unbalanced tripartite graph in linear time? We prove that this task is equivalent in hardness to some family of UCQs. Finally, we show a dichotomy for unions of two self-join-free CQs if we assume the answer to this question is negative. In conclusion, this paper pinpoints a computational barrier in the form of a single decision problem that is key to advancing our understanding of the enumeration complexity of many UCQs. Without a breakthrough for unbalanced triangle detection, we have no hope of finding an efficient algorithm for additional unions of two self-join-free CQs. On the other hand, a sufficiently efficient unbalanced triangle detection algorithm can be turned into an efficient algorithm for a family of UCQs currently not known to be tractable.
- Open Access
- 10 January 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 50 (1) , 1-44
Tight Fine-Grained Bounds for Direct Access on Join Queries
We consider the task of lexicographic direct access to query answers. That is, we want to simulate an array containing the answers of a join query sorted in a lexicographic order chosen by the user. A recent dichotomy showed for which queries and orders this task can be done in polylogarithmic access time after quasilinear preprocessing, but this dichotomy does not tell us how much time is required in the cases classified as hard. We determine the preprocessing time needed to achieve polylogarithmic access time for all join queries and all lexicographical orders. To this end, we propose a decomposition-based general algorithm for direct access on join queries. We then explore its optimality by proving lower bounds for the preprocessing time based on the hardness of a certain online Set-Disjointness problem, which shows that our algorithm’s bounds are tight for all lexicographic orders on join queries. Then, we prove the hardness of Set-Disjointness based on the Zero-Clique Conjecture, which is an established conjecture from fine-grained complexity theory. Interestingly, while proving our lower bound, we show that self-joins do not affect the complexity of direct access (up to logarithmic factors). Our algorithm can also be used to solve queries with projections and relaxed order requirements, though in these cases, its running time is not necessarily optimal. We also show that similar techniques to those used in our lower bounds can be used to prove that, for enumerating answers to Loomis-Whitney joins, it is not possible to significantly improve upon trivially computing all answers at preprocessing. This, in turn, gives further evidence (based on the Zero-Clique Conjecture) to the enumeration hardness of self-join-free cyclic joins with respect to linear preprocessing and constant delay.
- 10 January 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 50 (1) , 1-44
Open AccessTight Fine-Grained Bounds for Direct Access on Join Queries
We consider the task of lexicographic direct access to query answers. That is, we want to simulate an array containing the answers of a join query sorted in a lexicographic order chosen by the user. A recent dichotomy showed for which queries and orders this task can be done in polylogarithmic access time after quasilinear preprocessing, but this dichotomy does not tell us how much time is required in the cases classified as hard. We determine the preprocessing time needed to achieve polylogarithmic access time for all join queries and all lexicographical orders. To this end, we propose a decomposition-based general algorithm for direct access on join queries. We then explore its optimality by proving lower bounds for the preprocessing time based on the hardness of a certain online Set-Disjointness problem, which shows that our algorithm’s bounds are tight for all lexicographic orders on join queries. Then, we prove the hardness of Set-Disjointness based on the Zero-Clique Conjecture, which is an established conjecture from fine-grained complexity theory. Interestingly, while proving our lower bound, we show that self-joins do not affect the complexity of direct access (up to logarithmic factors). Our algorithm can also be used to solve queries with projections and relaxed order requirements, though in these cases, its running time is not necessarily optimal. We also show that similar techniques to those used in our lower bounds can be used to prove that, for enumerating answers to Loomis-Whitney joins, it is not possible to significantly improve upon trivially computing all answers at preprocessing. This, in turn, gives further evidence (based on the Zero-Clique Conjecture) to the enumeration hardness of self-join-free cyclic joins with respect to linear preprocessing and constant delay.
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- Vol. 13, 259-270
Knapsack with Small Items in Near-Quadratic Time
The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research worked towards understanding the complexity of pseudopolynomial-time algorithms for Knapsack parameterized by the maximum item weight wmax and the number of items n. A conditional lower bound rules out that Knapsack can be solved in time O((n+wmax)2−δ) for any δ > 0 [Cygan, Mucha, Wegrzycki, Wlodarczyk’17, Künnemann, Paturi, Schneider’17]. This raised the question whether Knapsack can be solved in time Õ((n+wmax)2). This was open both for 0-1-Knapsack (where each item can be picked at most once) and Bounded Knapsack (where each item comes with a multiplicity). The quest of resolving this question lead to algorithms that solve Bounded Knapsack in time Õ(n3 wmax2) [Tamir’09], Õ(n2 wmax2) and Õ(n wmax3) [Bateni, Hajiaghayi, Seddighin, Stein’18], O(n2 wmax2) and Õ(n wmax2) [Eisenbrand and Weismantel’18], O(n + wmax3) [Polak, Rohwedder, Wegrzycki’21], and very recently Õ(n + wmax12/5) [Chen, Lian, Mao, Zhang’23]. In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time Õ(n + wmax2), which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- Vol. 13, 259-270
Open AccessKnapsack with Small Items in Near-Quadratic Time
The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research worked towards understanding the complexity of pseudopolynomial-time algorithms for Knapsack parameterized by the maximum item weight wmax and the number of items n. A conditional lower bound rules out that Knapsack can be solved in time O((n+wmax)2−δ) for any δ > 0 [Cygan, Mucha, Wegrzycki, Wlodarczyk’17, Künnemann, Paturi, Schneider’17]. This raised the question whether Knapsack can be solved in time Õ((n+wmax)2). This was open both for 0-1-Knapsack (where each item can be picked at most once) and Bounded Knapsack (where each item comes with a multiplicity). The quest of resolving this question lead to algorithms that solve Bounded Knapsack in time Õ(n3 wmax2) [Tamir’09], Õ(n2 wmax2) and Õ(n wmax3) [Bateni, Hajiaghayi, Seddighin, Stein’18], O(n2 wmax2) and Õ(n wmax2) [Eisenbrand and Weismantel’18], O(n + wmax3) [Polak, Rohwedder, Wegrzycki’21], and very recently Õ(n + wmax12/5) [Chen, Lian, Mao, Zhang’23]. In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time Õ(n + wmax2), which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.
- Open Access
A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
In an $m$-edge host graph $G$, all triangles can be listed in time $O(m^{1.5})$ [Itai, Rodeh '78], and all $k$-cycles can be listed in time $O(m^{2-1/{\lceil k/2 \rceil}} + t)$ where $t$ is the output size [Alon, Yuster, Zwick '97]. These classic results also hold for the colored problem variant, where the nodes of the host graph $G$ are colored by nodes in the pattern graph $H$, and we are only interested in subgraphs of $G$ that are isomorphic to the pattern $H$ and respect the colors. We study the problem of listing all $H$-subgraphs in the colored setting, for fixed pattern graphs $H$. As our main result, we determine all pattern graphs $H$ such that all $H$-subgraphs can be listed in subquadratic time $O(m^{2-\varepsilon} + t)$, where $t$ is the output size. Moreover, for each such subquadratic pattern $H$ we determine the smallest exponent $c(H)$ such that all $H$-subgraphs can be listed in time $O(m^{c(H)} + t)$. This is a vast generalization of the classic results on triangles and cycles. To prove this result, we design new listing algorithms and prove conditional lower bounds based on standard hypotheses from fine-grained complexity theory. In our algorithms, we use a new ingredient that we call hyper-degree splitting, where we split tuples of nodes into high degree and low degree depending on their number of common neighbors. We also show the same results for two related problems: finding an $H$-subgraph of minimum total edge-weight in time $O(m^{c(H)})$, and enumerating all $H$-subgraphs in $O(m^{c(H)})$ preprocessing time and constant delay. Again we determine all pattern graphs $H$ that have complexity $c(H) < 2$, and for each such subquadratic pattern we determine the optimal complexity $c(H)$.Open AccessA Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
In an $m$-edge host graph $G$, all triangles can be listed in time $O(m^{1.5})$ [Itai, Rodeh '78], and all $k$-cycles can be listed in time $O(m^{2-1/{\lceil k/2 \rceil}} + t)$ where $t$ is the output size [Alon, Yuster, Zwick '97]. These classic results also hold for the colored problem variant, where the nodes of the host graph $G$ are colored by nodes in the pattern graph $H$, and we are only interested in subgraphs of $G$ that are isomorphic to the pattern $H$ and respect the colors. We study the problem of listing all $H$-subgraphs in the colored setting, for fixed pattern graphs $H$. As our main result, we determine all pattern graphs $H$ such that all $H$-subgraphs can be listed in subquadratic time $O(m^{2-\varepsilon} + t)$, where $t$ is the output size. Moreover, for each such subquadratic pattern $H$ we determine the smallest exponent $c(H)$ such that all $H$-subgraphs can be listed in time $O(m^{c(H)} + t)$. This is a vast generalization of the classic results on triangles and cycles. To prove this result, we design new listing algorithms and prove conditional lower bounds based on standard hypotheses from fine-grained complexity theory. In our algorithms, we use a new ingredient that we call hyper-degree splitting, where we split tuples of nodes into high degree and low degree depending on their number of common neighbors. We also show the same results for two related problems: finding an $H$-subgraph of minimum total edge-weight in time $O(m^{c(H)})$, and enumerating all $H$-subgraphs in $O(m^{c(H)})$ preprocessing time and constant delay. Again we determine all pattern graphs $H$ that have complexity $c(H) < 2$, and for each such subquadratic pattern we determine the optimal complexity $c(H)$. - Open Access
Knapsack with Small Items in Near-Quadratic Time
The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research worked towards understanding the complexity of pseudopolynomial-time algorithms for Knapsack parameterized by the maximum item weight $w_{\mathrm{max}}$ and the number of items $n$. A conditional lower bound rules out that Knapsack can be solved in time $O((n+w_{\mathrm{max}})^{2-δ})$ for any $δ> 0$ [Cygan, Mucha, Wegrzycki, Wlodarczyk'17, Künnemann, Paturi, Schneider'17]. This raised the question whether Knapsack can be solved in time $\tilde O((n+w_{\mathrm{max}})^2)$. This was open both for 0-1-Knapsack (where each item can be picked at most once) and Bounded Knapsack (where each item comes with a multiplicity). The quest of resolving this question lead to algorithms that solve Bounded Knapsack in time $\tilde O(n^3 w_{\mathrm{max}}^2)$ [Tamir'09], $\tilde O(n^2 w_{\mathrm{max}}^2)$ and $\tilde O(n w_{\mathrm{max}}^3)$ [Bateni, Hajiaghayi, Seddighin, Stein'18], $O(n^2 w_{\mathrm{max}}^2)$ and $\tilde O(n w_{\mathrm{max}}^2)$ [Eisenbrand and Weismantel'18], $O(n + w_{\mathrm{max}}^3)$ [Polak, Rohwedder, Wegrzycki'21], and very recently $\tilde O(n + w_{\mathrm{max}}^{12/5})$ [Chen, Lian, Mao, Zhang'23]. In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time $\tilde O(n + w_{\mathrm{max}}^2)$, which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.Open AccessKnapsack with Small Items in Near-Quadratic Time
The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research worked towards understanding the complexity of pseudopolynomial-time algorithms for Knapsack parameterized by the maximum item weight $w_{\mathrm{max}}$ and the number of items $n$. A conditional lower bound rules out that Knapsack can be solved in time $O((n+w_{\mathrm{max}})^{2-δ})$ for any $δ> 0$ [Cygan, Mucha, Wegrzycki, Wlodarczyk'17, Künnemann, Paturi, Schneider'17]. This raised the question whether Knapsack can be solved in time $\tilde O((n+w_{\mathrm{max}})^2)$. This was open both for 0-1-Knapsack (where each item can be picked at most once) and Bounded Knapsack (where each item comes with a multiplicity). The quest of resolving this question lead to algorithms that solve Bounded Knapsack in time $\tilde O(n^3 w_{\mathrm{max}}^2)$ [Tamir'09], $\tilde O(n^2 w_{\mathrm{max}}^2)$ and $\tilde O(n w_{\mathrm{max}}^3)$ [Bateni, Hajiaghayi, Seddighin, Stein'18], $O(n^2 w_{\mathrm{max}}^2)$ and $\tilde O(n w_{\mathrm{max}}^2)$ [Eisenbrand and Weismantel'18], $O(n + w_{\mathrm{max}}^3)$ [Polak, Rohwedder, Wegrzycki'21], and very recently $\tilde O(n + w_{\mathrm{max}}^{12/5})$ [Chen, Lian, Mao, Zhang'23]. In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time $\tilde O(n + w_{\mathrm{max}}^2)$, which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.