betaFeedback

WorksComputer Science

Estimating the Volume of a Union of Convex Bodies

Abstract

The Union Volume Estimation problem, i.e. yielding an (ε,δ)(\varepsilon, δ)-approximation of the volume of the union of convex bodies, is a classical problem in computational geometry and formal methods. In this paper, we first detect where and why the efficient union volume estimators with approximate sampling and PAC volume estimation oracles fail. Specifically, we show that having only TV-distance guarantees on the approximate sampler does not suffice, and demonstrate this bottleneck by constructing the sunflower families of convex bodies. In this context, we propose the concept of tail-controlled samplers that can yield with high-probability almost-ℓ∞\ell_{\infty} closeness. Secondly, we leverage this concept to propose a generic algorithmic framework Alpona that properly combines a PAC volume computation and approximate point sampling oracles with tail-controls to yield an (ε,δ)(\varepsilon, δ)-estimate of the union volume for any collection of convex bodies. We show that Alpona needs only linear (in number of convex bodies) oracle calls to be (ε,δ)(\varepsilon, δ)-correct. Finally, we provide a tail-controlled analysis of the Hit-and-Run sampler~\citep{lovasz2006fast}. We further provide a novel geometric analysis to improve the required walk length of Hit-and-Run. We further instantiate Alpona's correctness for the sparse frequency streams of convex bodies: a special case of the union volume estimation problem where no convex body intersects more than ττ many other bodies.

Introduction

Volume computation is a classical problem at the intersection of computational geometry, randomized algorithms, and approximate counting [12, 17, 22, 9]. The challenge is to yield an estimate V^\widehat{V} of the volume Vol⁡(K)\operatorname{Vol}(K) of a convex body K⊂RnK \subset\mathbb{R}^{n}, when we have only sampling access to it. Exact volume computation is #P-hard even for a single polytope [12, 17]. Thus, we retreat to randomized algorithms, and aim to yield an estimate V^\widehat{V} that is an (ε,δ)(\varepsilon,\delta)-approximation of Vol⁡(K)\operatorname{Vol}(K), i.e.,

Pr⁡[(1−ε)Vol⁡(K)≤V^≤(1+ε)Vol⁡(K)]≥1−δ,\Pr\left[(1-\varepsilon)\operatorname{Vol}(K) \le\widehat{V} \le(1+\varepsilon)\operatorname{Vol}(K)\right] \ge1-\delta,

for some ε>0\varepsilon> 0 and δ∈(0,1]\delta\in(0,1]. In this direction, a celebrated line of work beginning with Dyer, Frieze, and Kannan [ [11] established polynomial-time randomized approximation algorithms for convex bodies. A unifying theme across this extensive line of work is the central role of random walks and Markov Chain Monte Carlo (MCMC) methods. Specifically, rapidly mixing random walks have emerged as the predominant algorithmic paradigm for both volume approximation and approximately uniform sampling from high-dimensional convex bodies. These developments have led to powerful techniques based on geometric random walks, approximate sampling, and rapidly mixing Markov chains. Most notably, the recent work of Cousins and Vempala [ [9] solves (ε,δ)(\varepsilon,\delta)-approximate volume computation of (r,R)(r,R)-fat convex body1 in O(n3R2/r2)O(n^{3}R^{2}/r^{2}) by expanding upon the idea of generating sequences of interpolating convex bodies via resorting to Gaussian distributions: a technique referred to as Gaussian cooling.

In this paper, we take a step further, and study how to efficiently estimate the volume of a union of convex bodies with provable guarantees.

Problem 1 ((ε,δ\varepsilon,\delta)-Union Volume Estimation). Given MM convex bodies K1,…,KM⊂RnK_{1},\ldots,K_{M} \subset\mathbb{R}^{n} yield an estimate of the volume of their union

V:=Vol⁡(⋃i=1MKi)V := \operatorname{Vol}\left(\bigcup_{i=1}^{M} K_i\right)

within a multiplicative factor of 1±ε1 \pm\varepsilon, with probability at least 1−δ1-\delta.

Estimating the volume of a union of convex bodies presents additional difficulties. While each individual body is convex, their union need not be, and substantial overlaps can make the sum of the individual volumes a poor estimate of the volume of their union.

For discrete convex bodies, the Union Volume Estimation problem manifests to the enumeration of union size. Randomized approximation algorithms for union size, beginning with the classical work of Karp and Luby [ [15], provide a natural framework for addressing this problem. Subsequent works [16, 28, 39, 6] have extended this framework to realistic implementations with approximate size enumeration and sampling oracles. Thus, our central challenge is not proving only the existence of an efficient approximation algorithm, rather understanding which oracle guarantees suffice to provably solve the Union Volume Estimation problem, and how these guarantees can be realized efficiently for general convex bodies.

Motivations. Beyond its theoretical significance, the Union Volume Estimation problem naturally arises in automated reasoning and probabilistic verification [30]. If the convex bodies are axis-parallel hypercubes, the Union Volume Estimation reduces to the Klee’s measure problem, which was first proposed by Klee [ [18] in one dimension. Its multidimensional version is specifically useful for DNF (Disjunctive Normal Forms) counting and has been addressed by Meel et al. [ [29], when one has access to ‘exact’ sampling and size enumeration oracles for each hypercube (known as a Delphic set). But the algorithms used in practice are deployed with approximate samplers [39].

In a similar spirit, the satisfying assignments of a formula in Satisfiability Modulo Theories over Linear Real Arithmetic (SMT-LRA) can be represented as a union of convex polytopes. Estimating the volume of this union provides quantitative information about the space of satisfying assignments, with applications to reasoning about continuous systems. The recent work by Shaw et al. [ [38] introduced an algorithm for estimating the volume of regions represented by SMT-LRA formulas. The algorithm builds on randomized union-size estimation and demonstrates impressive empirical performance, significantly improving upon earlier approaches on the benchmarks considered. Their implementation uses, in the background, the volume and sampling oracles with sound theoretical guarantees assumed in their analysis. However none of these guarantees are retained in practice. In practice, the volume estimators (such as, discretize-and-count, Gaussian cooling [9]) and geometric random walks (in particular, Hit-and-Run [25])- run only up to a fixed walk length, since the walk lengths required by the theoretical guarantees are prohibitively long. Although these are natural and computationally effective choices, they do not satisfy the assumptions used in the analysis. This exposes a theory-to-practice gap in the Union Volume Estimation problem, which is not unique to the work of [38] but rather exhibited by any Union Volume Estimation algorithm using approximate samplers.

We aim to understand and algorithmically close this gap for general convex bodies that include all the aforementioned problems as special cases. To this end, we ask the following three questions.

  1. Does an Union Volume Estimation algorithm with an approximate sampler and a PAC volume computation oracle fail to be (ε,δ)(\varepsilon,\delta)-approximate for certain sets of convex bodies?

  1. Can we design a generic and efficient algorithmic framework that can incorporate the errors of the volume computation and approximate sampling oracles to provably yield an (ε,δ)(\varepsilon,\delta)-union volume estimate?

  1. Can this algorithmic framework be computationally efficient, i.e. what are the time and sample complexities of this algorithmic framework when instantiated with well-known and computationally-efficient approximate volume computation algorithms, like Gaussian cooling, and approximate samplers, like Hit-and-Run?

Overview of the Contributions

By addressing the aforementioned questions, our work establishes a generic framework and the necessary properties of sampling and volume computation oracles to ensure the reliability of Union Volume Estimation algorithms when the idealized volume and uniform sampling oracles are replaced by computationally efficient approximations. The contributions are fivefold.

(C1) Characterizing the limitations due to efficient but approximate samplers

We investigate the efficiency-correctness dilemma encountered by the Union Volume Estimation algorithms. First, we show that the approximate sampling guarantees for each convex body in terms of TV-distance does not suffice to control the total error accumulated over the union of convex bodies (Theorem 3). TV-distance based guarantees control the overall discrepancy between two distributions, but do not ensure that their probability densities are multiplicatively close at every point. In Union Volume Estimation, the locations of sampled points matter crucially: samples lying in overlapping regions between multiple bodies are treated differently from those lying in regions belonging to only one body. Consequently, distributional errors may interact with the geometry of the input in ways that are not captured by the TV distance. Motivated by this geometric insight, we construct the sunflower family (Lemma 4), where every convex body is of same size with a common overlapping region and individual petals, and show that any Union Volume Estimation algorithm with TV-distance close sampler would fail to be correct in this sunflower family.

A Tail-sensitive Distance for Approximate Samplers

Instead of TV-distance close approximate samplers, if we focus on only using ℓ∞\ell_{\infty}-close approximate samplers, we can design correct Union Volume Estimation algorithm but that becomes too restrictive as most of the efficient samplers are not provably ℓ∞\ell_{\infty}-close (e.g. Hit-and-Run, Ball walk [14], Billiard walk [34]). We propose a new (η,β)(\eta,\beta)-closeness measure to measure divergence between two distributions.

Definition 1 ((η,β)( \eta,\beta)-closeness). Given a probability space (S,π)(S,\pi), and a distribution D\mathcal{D} which is absolutely continuous with respect to the base measure π\pi, let h:=dDdπh := \frac{\mathrm{d}\mathcal{D}}{\mathrm{d}\pi} denote its relative density. We call D\mathcal{D} to be (η,β)(\eta,\beta)-close to π\pi, if we have

π(Badη)≤β and D(Badη)≤2β, where Badη:={x∈S:∣h(x)−1∣>η},\pi(\mathrm{Bad}_{\eta}) \le\beta\text{ and } \mathcal{D}(\mathrm{Bad}_{\eta}) \le2\beta, \text{ where } \mathrm{Bad}_{\eta} := \{x \in S : |h(x)-1| > \eta\},

for some (η,β)∈[0,1]2(\eta,\beta) \in[0,1]^2.

(0,0)(0,0)-closeness implies the distribution is exactly uniform, except possibly on a measure zero subset. The (η,β)(\eta,\beta)-tailed samplers are the approximate samplers that generate samples exhibiting empirical distributions differing from uniform distribution by β\beta, i.e. the support mass with ℓ∞\ell_{\infty} distance more than η\eta. Informally, the (η,β)(\eta,\beta)-tailed sampler produces samples whose density is multiplicatively close to the uniform density on a majority fraction of the set. Outside of this region (hereby referred as the exceptional region), we have no information as to how the density behaves.

We prove that Hit-and-Run, which is known to be an efficient approximate sampler, yields (η,β)(\eta,\beta)-close samples to uniform for any (r,R)(r,R)-fat convex body in polynomial number of steps.

Lemma 1 ((η,β)( \eta,\beta)-closeness of Hit-and-Run Samples, Informal version of Theorem 6). For any 1>β,η>01 > \beta,\eta> 0, if Hit-and-Run is run on a (r,R)(r,R)-fat convex body K⊂RnK \subset\mathbb{R}^n starting from any boundary point, we have πK(Badt,η)≤β\pi_K(\mathrm{Bad}_{t,\eta}) \le\beta if

t=ω(poly⁡(n,Rr,log⁡1β,log⁡1η)).t = \omega\left(\operatorname{poly}\left(n,\frac{R}{r},\log\frac{1}{\beta},\log\frac{1}{\eta}\right)\right).

Here, πK\pi_K denotes the uniform distribution over KK. Moreover, Dt(Badt,η)≤2β\mathcal{D}_t(\mathrm{Bad}_{t,\eta}) \le2\beta, i.e., a point sampled from Dt\mathcal{D}_t has density (1±η)(1 \pm\eta) close to that of π\pi with probability at least 1−2β1-2\beta.

Designing a correct and efficient framework for Union Volume Estimation

Now, we propose a provably correct algorithmic framework, Alpona, for Union Volume Estimation that access two oracles: (i) a PAC (Probably Approximately Correct) volume estimator for each convex body, and (ii) an (η,β)(\eta,\beta)-tailed sampler. Under appropriate choices of the oracle parameters, Alpona returns a multiplicative approximation to the union volume with high probability.

Theorem 2 (Informal version of Theorem 7). Let K1,…,KM⊂RnK_1,\ldots,K_M \subset\mathbb{R}^n be convex bodies satisfying the geometric assumptions required by the PAC volume estimation and approximate sampling oracles. For every ε,δ∈(0,1)\varepsilon,\delta\in(0,1), there is a randomized algorithm Alpona that, using PAC volume estimators and (η,β)(\eta,\beta)-tailed samplers, outputs an estimate V^\widehat{V} satisfying

Pr⁡[(1−ε)V≤V^≤(1+ε)V]≥1−δ,\Pr\left[(1-\varepsilon)V \le\widehat{V} \le(1+\varepsilon)V\right] \ge1-\delta,

where V:=Vol⁡(⋃i=1MKi)V := \operatorname{Vol}\left(\bigcup_{i=1}^{M} K_i\right). Alpona requires O(M)O(M) calls to the PAC volume estimation oracle and O~(M/ε2)\widetilde{O}(M/\varepsilon^2) calls to (η,β)(\eta,\beta)-tailed samplers.

The algorithm is a adaptive sampling based algorithm that aims to retain a Poisson number of representative points from each body proportional to its estimated volume. The main technical challenge is to analyse the interaction between three sources of uncertainty: errors in volume estimation, non-uniformity in the sampling distributions, and adaptive changes in the sampling intensity. Our analysis separates the regions where the sampling density is approximately uniform from the exceptional regions where this guarantee may fail. The former contribute a controlled approximation to the union volume, while the contribution from the latter is bounded using their small measure and sampling probability. Together with concentration arguments for the sampling procedure, this establishes the correctness guarantee.

Connecting geometric sampling guarantees to implementable algorithms

Finally, we propose a practically efficient instantiation of Alpona with Hit-and-Run as (η,β)(\eta,\beta)-tailed approximate sampler and Gaussian cooling as the PAC volume estimator. We show that space and time complexity of this algorithm are

O~(nε2log⁡Mδ), and O~(Mmax⁡{n3,n2(R/r)2}ε2).\widetilde{O}\left(\frac{n}{\varepsilon^2}\log\frac{M}{\delta}\right),\text{ and }\widetilde{O}\left(M\frac{\max\left\{n^3,n^2(R/r)^2\right\}}{\varepsilon^2}\right).

The resulting complexity analysis separates the number of oracle calls made by the main algorithm from the cost of implementing each oracle. This distinction is important: the number of bodies affects both the number of operations and the accuracy parameters required by the subroutines, while the geometry of each body influences the complexity of the individual approximate volume computation and sampling queries. Thus, the analysis provides a quantitative connection between the desired approximation guarantee, the number of convex bodies, their geometric parameters, and the computational resources required by the implementation.

In this process, we derive in Theorem 21 an improved walk length that Hit-and-Run needs to take to generate an (η,β)(\eta,\beta)-close sample is O~(n3R2r2)\widetilde{O}\left(n^3\frac{R^2}{r^2}\right) from O~(n4R2r2)\widetilde{O}\left(n^4\frac{R^2}{r^2}\right) [Lovász and Vempala, 2006]. The proof passes through two geometric claims:

  1. For any 0<η,β<10<\eta,\beta<1, Hit-and-Run taking at least

1+n2+O(nlog⁡(32R/d)+log⁡(1/(η2β))γHR)1+\frac{n}{2}+O\left(\frac{n\log(32R/d)+\log(1/(\eta^2\beta))}{\gamma_{\mathrm{HR}}}\right)

suffices to guarantee that π(Badt,η)≤β\pi(\mathrm{Bad}_{t,\eta})\le\beta and Dt(Badt,η)≤2β\mathcal{D}_t(\mathrm{Bad}_{t,\eta})\le2\beta, where γHR\gamma_{\mathrm{HR}} is the spectral gap for Hit-and-Run.

  1. We show contraction of Hit-and-Run’s sampling operator PP for functions ff with mean 00:

∥Psf∥L2(π)≤e−γHRs∥f∥2,\left\|P^s f\right\|_{L_2(\pi)} \le e^{-\gamma_{\mathrm{HR}}s}\|f\|_2,

for s>1+n2s>1+\frac{n}{2}.

(C5) Bounded Frequency Streams. Till now, we have worked with a pre-fixed number of convex bodies MM. But we can adapt Alpona further to streams of convex bodies with bounded frequency. Here, a bounded frequency stream of convex bodies means that each point of the union of these bodies has a bounded frequency 1≤τ≤M1 \le\tau\le M. In this case, we show Theorem 23 that time and space complexities of Alpona will be dependent on the frequency τ\tau instead of MM.

Organisation. Rest of the paper is organised as follows: in § 2, we demonstrate and highlight the weakness in sampling from distributions with only TV-control. In § 3, we propose the notion of tail-controlled distributions and discuss its properties. The paper’s algorithmic contribution is described in § 4, which also includes a short discussion on the related works. Correctness of the algorithm and it’s complexity requirements are discussed in § 5 and in § 6 respectively. We cover the special case of sparse streams in § 7. We finally conclude in § 8.

From Worst-Case Sampling Guarantees to Practical Performance

Estimating the volume of a union of convex bodies from approximate samples presents a subtle difficulty: a small sampling error for each body need not translate into a small error for the union. We first demonstrate this limitation through a sunflower construction. We then examine its relevance to the practical algorithm of Shaw et al. [ [38]. Although adversarial sampling errors can cause substantial failures, the practical performance of their algorithm is often considerably better than this pessimistic scenario suggests. Understanding this discrepancy motivates our study of more informative sampling guarantees.

A Fundamental Limitation of Approximate Sampling

Suppose an estimator has sampling-oracle access to convex bodies K1,…,KMK_1,\ldots,K_M. Denote by πi\pi_i the uniform distribution on KiK_i. For each ii, the oracle returns independent samples from a distribution DiD_i satisfying ∥Di−πi∥1≤θ\lVert D_i-\pi_i\rVert_1 \le\theta. We ask whether this assumption alone suffices for reliable estimation of the union volume. The following theorem gives a negative answer in the sampling-only oracle model. Here, ∥⋅∥1\lVert\cdot\rVert_1 denotes the ℓ1\ell_1 distance between probability distributions, which is twice their TV distance.

Theorem 3 (Limitations of approximate sampling). Fix ε,θ∈(0,1)\varepsilon,\theta\in(0,1), and let A\mathcal{A} be any randomized algorithm whose access to the input convex bodies is restricted to the following oracles:

  • A sampling oracle for each body KiK_i that returns independent samples from a distribution DiD_i satisfying

∥Di−πi∥1≤θ.\lVert D_i-\pi_i\rVert_1 \le\theta.
  • A volume oracle for each body KiK_i that returns a (1±θ)(1\pm\theta)-approximation to Vol⁡(Ki)\operatorname{Vol}(K_i).

Then there exists an instance consisting of K=Oε(1/θ)K = O_{\varepsilon}(1/\theta) convex bodies, together with oracles satisfying the above guarantees, on which A\mathcal{A} fails to return a (1±ε)(1\pm\varepsilon)-approximation to the volume of their union with probability at least 1/21/2.

Proof. Let a=θ/(2−θ)∈(0,1)a = \theta/(2-\theta) \in(0,1). By Lemma 4 (proved later), there exist MM convex bodies K1,…,KM⊆RM−1K_1,\ldots,K_M \subseteq\mathbb{R}^{M-1} forming a sunflower family with common core K∩K_{\cap} and pairwise disjoint petals C1,…,CMC_1,\ldots,C_M, such that

References

  1. [1]Luigi Ambrosio, Nicola Fusco, and Diego Pallara. Functions of Bounded Variation and Free Discontinuity Problems. Oxford Mathematical Monographs. Oxford University Press, 2000. ISBN 9780198502456. doi: 10.1093/oso/9780198502456.001.0001. URL https://doi.org/10.1093/oso/9780198502456.001.0001.
  2. [2]David Applegate and Ravi Kannan. Sampling and integration of near log-concave functions. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 156–163, 1991.DOI
  3. [3]Mario Bebendorf. A note on the poincaré inequality for convex domains. Zeitschrift für Analysis und ihre Anwendungen, 22(4):751–756, 2003.DOI
  4. [5]Karl Bringmann and Tobias Friedrich. Approximating the volume of unions and intersections of high-dimensional geometric objects. Comput. Geom., 43(6-7):601–610, 2010. doi: 10.1016/J.COMGEO.2010.03.004.DOI
  5. [6]Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, and Yanheng Wang. Approximating klee’s measure problem and a lower bound for union volume estimation. arXiv preprint arXiv:2410.09996, 2024.
  6. [7]Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, and Yanheng Wang. Approximating klee’s measure problem and a lower bound for union volume estimation. In 41st International Symposium on Computational Geometry, (SoCG), volume 332, pages 25:1–25:16, 2025. doi: 10.4230/LIPIcs.SOCG.2025.25.DOI
  7. [8]Martin Costabel. Inequalities of Babuška–Aziz and Friedrichs–Velte for Differential Forms, page 79–88. Springer International Publishing, 2017. ISBN 9783319470795. doi: 10.1007/978-3-319-47079-5_4. URL http://dx.doi.org/10.1007/978-3-319-47079-5_4.
  8. [9]Ben Cousins and Santosh Vempala. Gaussian cooling and o*(n3) algorithms for volume and gaussian volume. SIAM Journal on Computing, 47(3):1237–1273, January 2018. ISSN 0097-5397, 1095-7111. doi: 10.1137/15M1054250.
  9. [10]Frank Den Hollander. Probability theory: The coupling method. Lecture notes available online (http://websites. math. leidenuniv. nl/probability/lecturenotes/CouplingLectures. pdf), 3:60, 2012.
  10. [11]Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1–17, 1991.
  11. [12]Martin E. Dyer and Alan M. Frieze. On the complexity of computing the volume of a polyhedron. SIAM Journal on Computing, 17(5):967–974, 1988.DOI
  12. [13]Ravi Kannan and Hariharan Narayanan. Random walks on polytopes and an affine interior point method for linear programming. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 561–570, 2009.
  13. [14]Ravi Kannan, László Lovász, and Miklós Simonovits. Random walks and an o*(n5) volume algorithm for convex bodies. Random Structures & Algorithms, 11(1):1–50, 1997.
  14. [15]Richard M. Karp and Michael Luby. Monte-carlo algorithms for enumeration and reliability problems. In 24th Annual Symposium on Foundations of Computer Science, pages 56–64, 1983. doi: 10.1109/SFCS.1983.35.DOI
  15. [16]Richard M Karp, Michael Luby, and Neal Madras. Monte-carlo approximation algorithms for enumeration problems. Journal of algorithms, 10(3):429–448, 1989.DOI
  16. [17]Leonid Khachiyan. The problem of computing the volume of polytopes is #p-hard. Uspekhi Mat. Nauk, 44(3):199–200, 1989.
  17. [18]Victor Klee. Can the measure of be computed in less than o(n log n) steps? The American Mathematical Monthly, 84(4):284–285, 1977.DOI
  18. [19]Yunbum Kook and Santosh S Vempala. Sampling and integration of logconcave functions by algorithmic diffusion. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 924–932, 2025.arxiv.org/abs/2411.13462
  19. [20]Yunbum Kook and Santosh S. Vempala. Spectral gaps of hit-and-run and coordinate hit-and-run, 2026. URL https://arxiv.org/abs/2608.16878.
  20. [21]Aditi Laddha and Santosh S. Vempala. Convergence of gibbs sampling: Coordinate hit-and-run mixes fast. Discrete & Computational Geometry, 70(2):406–425, 2023.
  21. [22]László Lovász and Miklós Simonovits. The mixing rate of markov chains, an isoperimetric inequality, and computing the volume. In Proceedings [1990] 31st annual symposium on foundations of computer science, pages 346–354. IEEE, 1990.
  22. [24]László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms, 30(3):307–358, 2007.DOI
  23. [25]László Lovász and Santosh S. Vempala. Hit-and-run from a corner. SIAM Journal on Computing, 35(4):985–1005, 2006. doi: 10.1137/S009753970544727X. URL https://doi.org/10.1137/S009753970544727X.
  24. [26]Oren Mangoubi and Nisheeth K Vishnoi. Sampling from log-concave distributions over polytopes via a soft-threshold dikin walk. arXiv preprint arXiv:2206.09384, 2022.arxiv.org/abs/2206.09384
  25. [28]Kuldeep S Meel, Aditya A Shrotri, and Moshe Y Vardi. On hashing-based approaches to approximate dnf-counting. arXiv preprint arXiv:1710.05247, 2017.arxiv.org/abs/1710.05247
  26. [29]Kuldeep S. Meel, N.V. Vinodchandran, and Sourav Chakraborty. Estimating the size of union of sets in streaming models. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems PODS, PODS’21, page 126–137. Association for Computing Machinery, 2021. doi: 10.1145/3452021.3458333.DOI
  27. [30]Kuldeep S. Meel, Sourav Chakraborty, and N. V. Vinodchandran. Estimation of the size of union of delphic sets: Achieving independence from stream size. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems PODS, PODS ’22, page 41–52. Association for Computing Machinery, 2022. doi: 10.1145/3517804.3526222.DOI
  28. [31]Emanuel Milman. On the role of convexity in isoperimetry, spectral gap and concentration. Inventiones mathematicae, 177(1):1–43, 2009.arxiv.org/abs/0712.4092
  29. [32]Mridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, and Sourav Chakraborty. Improved streaming algorithm for the klee’s measure problem and generalizations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX, volume 317 of LIPIcs, pages 26:1–26:21, 2024. doi: 10.4230/LIPICS.APPROX/RANDOM.2024.26.DOI
  30. [33]Lawrence E Payne and Hans F Weinberger. An optimal poincaré inequality for convex domains. Archive for Rational Mechanics and Analysis, 5(1):286–292, 1960.DOI
  31. [34]Boris T Polyak and EN Gryazina. Billiard walk-a new sampling algorithm for control and optimization. IFAC Proceedings Volumes, 47(3):6123–6128, 2014.DOI
  32. [35]Sheldon M. Ross. Introduction to Probability Models. Academic Press, London, 13th edition, 2023. ISBN 978-0443187612.
  33. [36]Daniel Rudolf and Mario Ullrich. Positivity of hit-and-run and related algorithms. Electronic Communications in Probability, 18(none):1–8, January 2013. ISSN 1083-589X. doi: 10.1214/ecp.v18-2507. URL http://dx.doi.org/10.1214/ECP.v18-2507.
  34. [37]Rolf Schneider. Convex bodies: the Brunn-Minkowski theory, volume 151. Cambridge university press, Cambridge, 2 edition, 1993.DOI
  35. [38]Arijit Shaw, Uddalok Sarkar, and Kuldeep S. Meel. Efficient Volume Computation for SMT Formulas. In Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning, pages 544–554, 10 2025. doi: 10.24963/kr.2025/53. URL https://doi.org/10.24963/kr.2025/53.
  36. [39]Mate Soos, Uddalok Sarkar, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel, and Maciej Obremski. Engineering an efficient approximate DNF-counter. arXiv preprint, 2024. URL http://arxiv.org/abs/2407.19946.
  37. [40]Elias M Stein. Singular integrals and differentiability properties of functions, volume 2. Princeton university press, 1970.
  38. [42]Sándor Zsuppán. Connections between optimal constants in some norm inequalities for differential forms. Zeitschrift für Analysis und ihre Anwendungen, 39(2):171–184, 2020. doi: 10.4171/ZAA/1656. URL https://doi.org/10.4171/ZAA/1656.

Paper details

vlnc:W_daaqaqyt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents