34 Search Results for "Ghosh, Arijit"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.90
Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells

Authors: Jonathan Richard Shewchuk

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The restricted Delaunay triangulation of a closed surface Σ and a finite point set V ⊂ Σ is a subcomplex of the Delaunay tetrahedralization of V whose triangles approximate Σ. It is well known that if V is a sufficiently dense sample of a smooth Σ, then the union of the restricted Delaunay triangles is homeomorphic to Σ. We show that an ε-sample with ε ≤ 0.3245 suffices. By comparison, Dey proves it for a 0.18-sample; our improved sampling bound reduces the number of sample points required by a factor of 3.25. More importantly, we improve a related sampling bound of Cheng et al. for Delaunay surface meshing, reducing the number of sample points required by a factor of 21. The first step of our homeomorphism proof is particularly interesting: we show that for a 0.44-sample, the restricted Voronoi cell of each site v ∈ V is homeomorphic to a disk, and the orthogonal projection of the cell onto T_vΣ (the plane tangent to Σ at v) is star-shaped.
Cite as

Jonathan Richard Shewchuk. Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 90:1-90:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shewchuk:LIPIcs.SoCG.2026.90,
  author =	{Shewchuk, Jonathan Richard},
  title =	{{Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{90:1--90:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.90},
  URN =		{urn:nbn:de:0030-drops-258961},
  doi =		{10.4230/LIPIcs.SoCG.2026.90},
  annote =	{Keywords: Restricted Delaunay triangulation, restricted Voronoi diagram, surface sampling, surface mesh generation, surface reconstruction, \epsilon-sample, homeomorphism}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.93
Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations

Authors: Raphaël Tinarrage

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.
Cite as

Raphaël Tinarrage. Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tinarrage:LIPIcs.SoCG.2026.93,
  author =	{Tinarrage, Rapha\"{e}l},
  title =	{{Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{93:1--93:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.93},
  URN =		{urn:nbn:de:0030-drops-258991},
  doi =		{10.4230/LIPIcs.SoCG.2026.93},
  annote =	{Keywords: Triangulation of manifolds, Simplicial approximation, CW complexes, Delaunay complexes, List homomorphism problem, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.12
Dynamic and Streaming Algorithms for Union Volume Estimation

Authors: Sujoy Bhore, Karl Bringmann, Timothy M. Chan, and Yanheng Wang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The union volume estimation problem asks to (1±ε)-approximate the volume of the union of n given objects X₁,…,X_n ⊂ ℝ^d. In their seminal work in 1989, Karp, Luby, and Madras solved this problem in time O(n/ε²) 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: 1) 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); 2) an algorithm supporting insertions and suffix queries (which generalizes the sliding window setting) in polylogarithmic update and query time and space; 3) an algorithm supporting insertions and deletions of convex bodies of constant dimension in polylogarithmic update and query time and space.
Cite as

Sujoy Bhore, Karl Bringmann, Timothy M. Chan, and Yanheng Wang. Dynamic and Streaming Algorithms for Union Volume Estimation. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.12,
  author =	{Bhore, Sujoy and Bringmann, Karl and Chan, Timothy M. and Wang, Yanheng},
  title =	{{Dynamic and Streaming Algorithms for Union Volume Estimation}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.12},
  URN =		{urn:nbn:de:0030-drops-258180},
  doi =		{10.4230/LIPIcs.SoCG.2026.12},
  annote =	{Keywords: union volume estimation, dynamic algorithms, streaming algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.30
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions

Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Given Boolean functions f, g : 𝔽₂ⁿ → {-1,+1}, we say they are linearly isomorphic if there exists A ∈ GL_n(𝔽₂) such that f(x) = g(Ax) for all x. We study this problem in the tolerant property testing framework under the known-unknown model, where g is given explicitly and f is accessible only via oracle queries, meaning the algorithm may adaptively request the value of f(x) for inputs x ∈ 𝔽₂ⁿ of its choice. Given parameters ε ≥ 0 and ω > 0, the goal is to distinguish whether there exists A ∈ GL_n(𝔽₂) such that the normalized Hamming distance between f and g(Ax) is at most ε, or whether for every A ∈ GL_n(𝔽₂) the distance is at least ε+ω. Our main result is a tolerant tester making Õ ((m/ω) ⁴) queries to f, where m is an upper bound on the spectral norm of g, improving the previous Õ ((m/ω) ^{24}) bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of Ω(m²) for constant ω (for example, ω = 1/4), improving the prior Ω(log m) lower bound of Grigorescu, Wimmer and Xie. A key technical ingredient on the algorithmic side is a query-efficient local list corrector. For the lower bound, we give a reduction from communication complexity using a novel subclass of Maiorana-McFarland functions from symmetric-key cryptography.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2026.30,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.30},
  URN =		{urn:nbn:de:0030-drops-255194},
  doi =		{10.4230/LIPIcs.STACS.2026.30},
  annote =	{Keywords: Boolean Function, Isomorphism of Boolean Function, Fourier Analysis, Sublinear Algorithm, Property Testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.13
Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}
Document
Survey
DOI: 10.4230/TGDK.3.2.1
Resilience in Knowledge Graph Embeddings

Authors: Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo

Published in: TGDK, Volume 3, Issue 2 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 2

Abstract
In recent years, knowledge graphs have gained interest and witnessed widespread applications in various domains, such as information retrieval, question-answering, recommendation systems, amongst others. Large-scale knowledge graphs to this end have demonstrated their utility in effectively representing structured knowledge. To further facilitate the application of machine learning techniques, knowledge graph embedding models have been developed. Such models can transform entities and relationships within knowledge graphs into vectors. However, these embedding models often face challenges related to noise, missing information, distribution shift, adversarial attacks, etc. This can lead to sub-optimal embeddings and incorrect inferences, thereby negatively impacting downstream applications. While the existing literature has focused so far on adversarial attacks on KGE models, the challenges related to the other critical aspects remain unexplored. In this paper, we, first of all, give a unified definition of resilience, encompassing several factors such as generalisation, in-distribution generalization, distribution adaption, and robustness. After formalizing these concepts for machine learning in general, we define them in the context of knowledge graphs. To find the gap in the existing works on resilience in the context of knowledge graphs, we perform a systematic survey, taking into account all these aspects mentioned previously. Our survey results show that most of the existing works focus on a specific aspect of resilience, namely robustness. After categorizing such works based on their respective aspects of resilience, we discuss the challenges and future research directions.
Cite as

Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo. Resilience in Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 2, pp. 1:1-1:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{sharma_et_al:TGDK.3.2.1,
  author =	{Sharma, Arnab and Kouagou, N'Dah Jean and Ngomo, Axel-Cyrille Ngonga},
  title =	{{Resilience in Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:38},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.2.1},
  URN =		{urn:nbn:de:0030-drops-248117},
  doi =		{10.4230/TGDK.3.2.1},
  annote =	{Keywords: Knowledge graphs, Resilience, Robustness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.91
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

Authors: Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work. Specifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.
Cite as

Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 91:1-91:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dhulipala_et_al:LIPIcs.ESA.2025.91,
  author =	{Dhulipala, Laxman and Henzinger, Monika and Li, George Z. and Liu, Quanquan C. and Sricharan, A. R. and Zhu, Leqi},
  title =	{{Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{91:1--91:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.91},
  URN =		{urn:nbn:de:0030-drops-245601},
  doi =		{10.4230/LIPIcs.ESA.2025.91},
  annote =	{Keywords: differential privacy, abovethreshold, densest subgraph}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.66
Testing Isomorphism of Boolean Functions over Finite Abelian Groups

Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Let f and g be Boolean functions over a finite Abelian group 𝒢, where g is fully known and f is accessible via queries; that is, given any x ∈ 𝒢, we can obtain the value f(x). We study the problem of tolerant isomorphism testing: given parameters ε ≥ 0 and τ > 0, the goal is to determine, using as few queries as possible, whether there exists an automorphism σ of 𝒢 such that the fractional Hamming distance between f∘σ and g is at most ε, or whether for every automorphism σ, the distance is at least ε + τ. We design an efficient tolerant property testing algorithm for this problem over finite Abelian groups with constant exponent. The exponent of a finite group refers to the largest order of any element in the group. The query complexity of our algorithm is polynomial in s and 1/τ, where s bounds the spectral norm of the function g, and τ is the tolerance parameter. In addition, we present an improved algorithm in the case where g is Fourier sparse, meaning that its Fourier expansion contains only a small number of nonzero coefficients. Our approach draws on key ideas from Abelian group theory and Fourier analysis, including the annihilator of a subgroup, Pontryagin duality, and a pseudo inner product defined over finite Abelian groups. We believe that these techniques will be useful more broadly in the design of property testing algorithms.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Testing Isomorphism of Boolean Functions over Finite Abelian Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.APPROX/RANDOM.2025.66,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Testing Isomorphism of Boolean Functions over Finite Abelian Groups}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{66:1--66:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.66},
  URN =		{urn:nbn:de:0030-drops-244328},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.66},
  annote =	{Keywords: Analysis of Boolean functions, Abelian groups, Automorphism group, Function isomorphism, Spectral norm}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.44
Streaming Algorithms for Conflict-Free Coloring

Authors: Rogers Mathew, Fahad Panolan, and Seshikanth

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Conflict-free coloring of a hypergraph ℋ = (V,ℰ) using k colors is a function f:V → {1,2, …, k} such that for all E ∈ ℰ, there exists a vertex v ∈ E with a unique color. That is, f(v)≠ f(u) for all u ∈ E ⧵ {v}. The minimum k for which ℋ has a conflict-free coloring using k colors is called the conflict-free chromatic number of ℋ. For a simple graph G, a conflict-free coloring of the hypergraph with vertex set V(G) and edge set being the set of all closed neighborhoods of the vertices in G is called a conflict-free closed neighborhood (CFCN) coloring of G. CFCN chromatic number, denoted by χ_{CN}(G), is the minimum number of colors used in a conflict-free closed neighborhood coloring of G. Analogously, we define conflict-free open neighborhood (CFON) coloring and CFON chromatic number, χ_{ON}(G), of a graph G. There are various works on proving upper and lower bounds of χ_{ON}(G) and χ_{CN}(G). In this work, we develop streaming algorithms for CFCN and CFON coloring of a graph where the number of colors used matches the best-known upper bounds of χ_{ON}(G) and χi_{CN}(G). Our algorithms use as input an edge stream of the graph G in the insertion-only model. Our results and the best-known bounds for χ_{ON}(G) and χ_{CN}(G) are given below. 1. Pach and Tardos [Combinatorics, Probability and Computing, 2009] showed that, for any n vertex graph G, χ_{CN}(G) = O(ln² n). Glebov, Szabó and Tardos [Combinatorics, Probability and Computing, 2014] showed the existence of graphs G with χ_{CN}(G) = Ω(ln² n). We design a randomized single-pass semi-streaming algorithm (i.e., it uses O(n ln n) space that, given an n-vertex graph G, outputs a CFCN coloring of G using O(ln² n) colors with probability at least (1-2/n). 2. Bhyravarapu, Kalyanasundaram, Mathew [Journal of Graph Theory, 2021] showed that for a graph G with maximum degree Δ, χ_{CN}(G) = O(ln² Δ). The methods used by our algorithms give rise to a simpler, alternate proof for this bound. 3. It is known that χ_{ON}(G) ≤ 1/2 + √{2n + 1/4} (See Pach and Tardos [Combinatorics, Probability and Computing, 2009] and Ph.D. thesis of Cheilaris). This bound is asymptotically tight. - We design a deterministic single-pass O(n√n) space streaming algorithm that, given a graph G on n vertices, finds a CFON coloring using 2√n colors. - We design a randomized, single-pass, semi-streaming algorithm to find a CFON coloring of a graph G using O(√n ln² n) colors with success probability at least (1-2/n). 4. It is known that χ_{ON}(G) ≤ Δ+1, where Δ is the maximum degree of a vertex in G. Further, there are graphs G known with χ_{ON}(G) = Δ + 1. We design a randomized two-pass semi-streaming algorithm (uses O(1/(ε²) n ln³ n) space) that outputs a CFON coloring of G using (1+ε)Δ colors, for any ε > 0, with a probability at least (1-1/n).
Cite as

Rogers Mathew, Fahad Panolan, and Seshikanth. Streaming Algorithms for Conflict-Free Coloring. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mathew_et_al:LIPIcs.WADS.2025.44,
  author =	{Mathew, Rogers and Panolan, Fahad and Seshikanth},
  title =	{{Streaming Algorithms for Conflict-Free Coloring}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.44},
  URN =		{urn:nbn:de:0030-drops-242756},
  doi =		{10.4230/LIPIcs.WADS.2025.44},
  annote =	{Keywords: Streaming algorithm, conflict-free coloring, vertex coloring, randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.33
A Min-Entropy Approach to Multi-Party Communication Lower Bounds

Authors: Mi-Ying (Miryam) Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, and Jiapeng Zhang

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Information complexity is one of the most powerful techniques to prove information-theoretical lower bounds, in which Shannon entropy plays a central role. Though Shannon entropy has some convenient properties, such as the chain rule, it still has inherent limitations. One of the most notable barriers is the square-root loss, which appears in the square-root gap between entropy gaps and statistical distances, e.g., Pinsker’s inequality. To bypass this barrier, we introduce a new method based on min-entropy analysis. Building on this new method, we prove the following results. - An Ω(N^{∑_i α_i - max_i {α_i}}/k) randomized communication lower bound of the k-party set-intersection problem where the i-th party holds a random set of size ≈ N^{1-α_i}. - A tight Ω(n/k) randomized lower bound of the k-party Tree Pointer Jumping problems, improving an Ω(n/k²) lower bound by Chakrabarti, Cormode, and McGregor (STOC 08). - An Ω(n/k+√n) lower bound of the Chained Index problem, improving an Ω(n/k²) lower bound by Cormode, Dark, and Konrad (ICALP 19). Since these problems served as hard problems for numerous applications in streaming lower bounds and cryptography, our new lower bounds directly improve these streaming lower bounds and cryptography lower bounds. On the technical side, min-entropy does not have nice properties such as the chain rule. To address this issue, we enhance the structure-vs-pseudorandomness decomposition used by Göös, Pitassi, and Watson (FOCS 17) and Yang and Zhang (STOC 24); both papers used this decomposition to prove communication lower bounds. In this paper, we give a new breath to this method in the multi-party setting, presenting a new toolkit for proving multi-party communication lower bounds.
Cite as

Mi-Ying (Miryam) Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, and Jiapeng Zhang. A Min-Entropy Approach to Multi-Party Communication Lower Bounds. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 33:1-33:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.CCC.2025.33,
  author =	{Huang, Mi-Ying (Miryam) and Mao, Xinyu and Wang, Shuo and Yang, Guangxu and Zhang, Jiapeng},
  title =	{{A Min-Entropy Approach to Multi-Party Communication Lower Bounds}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{33:1--33:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.33},
  URN =		{urn:nbn:de:0030-drops-237273},
  doi =		{10.4230/LIPIcs.CCC.2025.33},
  annote =	{Keywords: communication complexity, lifting theorems, set intersection, chained index}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.11
When Alpha-Complexes Collapse onto Codimension-1 Submanifolds

Authors: Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a finite set of points P sampling an unknown smooth surface ℳ ⊆ ℝ³, our goal is to triangulate ℳ based solely on P. Assuming ℳ is a smooth orientable submanifold of codimension 1 in ℝ^d, we introduce a simple algorithm, Naive Squash, which simplifies the α-complex of P by repeatedly applying a new type of collapse called vertical relative to ℳ. Naive Squash also has a practical version that does not require knowledge of ℳ. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of ℳ. We provide a bound on the angle formed by triangles in the α-complex with ℳ, yielding sampling conditions on P that are competitive with existing literature for smooth surfaces embedded in ℝ³, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of P triangulates ℳ when ℳ is a smooth surface in ℝ³ under weaker conditions than existing ones.
Cite as

Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier. When Alpha-Complexes Collapse onto Codimension-1 Submanifolds. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2025.11,
  author =	{Attali, Dominique and Cl\'{e}mot, Matt\'{e}o and Dornelas, Bianca B. and Lieutier, Andr\'{e}},
  title =	{{When Alpha-Complexes Collapse onto Codimension-1 Submanifolds}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.11},
  URN =		{urn:nbn:de:0030-drops-231630},
  doi =		{10.4230/LIPIcs.SoCG.2025.11},
  annote =	{Keywords: Submanifold reconstruction, triangulation, abstract simplicial complexes, collapses, convexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.61
k-Dimensional Transversals for Fat Convex Sets

Authors: Attila Jung and Dömötör Pálvölgyi

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We prove a fractional Helly theorem for k-flats intersecting fat convex sets. A family ℱ of sets is said to be ρ-fat if every set in the family contains a ball and is contained in a ball such that the ratio of the radii of these balls is bounded by ρ. We prove that for every dimension d and positive reals ρ and α there exists a positive β = β(d,ρ, α) such that if ℱ is a finite family of ρ-fat convex sets in ℝ^d and an α-fraction of the (k+2)-size subfamilies from ℱ can be hit by a k-flat, then there is a k-flat that intersects at least a β-fraction of the sets of ℱ. We prove spherical and colorful variants of the above results and prove a (p,k+2)-theorem for k-flats intersecting balls.
Cite as

Attila Jung and Dömötör Pálvölgyi. k-Dimensional Transversals for Fat Convex Sets. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jung_et_al:LIPIcs.SoCG.2025.61,
  author =	{Jung, Attila and P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r},
  title =	{{k-Dimensional Transversals for Fat Convex Sets}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{61:1--61:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.61},
  URN =		{urn:nbn:de:0030-drops-232136},
  doi =		{10.4230/LIPIcs.SoCG.2025.61},
  annote =	{Keywords: discrete geometry, transversals, Helly, hypergraphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.19
Polychromatic Coloring of Tuples in Hypergraphs

Authors: Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Miloš Stojaković

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
A hypergraph H consists of a set V of vertices and a set E of hyperedges that are subsets of V. A t-tuple of H is a subset of t vertices of V. A t-tuple k-coloring of H is a mapping of its t-tuples into k colors. A coloring is called (t,k,f)-polychromatic if each hyperedge of E that has at least f vertices contains tuples of all the k colors. Let f_H(t,k) be the minimum f such that H has a (t,k,f)-polychromatic coloring. For a family of hypergraphs ℋ let f_H(t,k) be the maximum f_H(t,k) over all hypergraphs H in H. Determining f_H(t,k) has been an active research direction in recent years. This is challenging even for t = 1. We present several new results in this direction for t ≥ 2. - Let H be the family of hypergraphs H that is obtained by taking any set P of points in ℝ², setting V: = P and E: = {d ∩ P: d is a disk in ℝ²}. We prove that f_ H(2,k) ≤ 3.7^k, that is, the pairs of points (2-tuples) can be k-colored such that any disk containing at least 3.7^k points has pairs of all colors. We generalize this result to points and balls in higher dimensions. - For the family H of hypergraphs that are defined by grid vertices and axis-parallel rectangles in the plane, we show that f_H(2,k) ≤ √{ck ln k} for some constant c. We then generalize this to higher dimensions, to other shapes, and to tuples of larger size. - For the family H of shrinkable hypergraphs of VC-dimension at most d we prove that f_ H(d+1,k) ≤ c^k for some constant c = c(d). Towards this bound, we obtain a result of independent interest: Every hypergraph with n vertices and with VC-dimension at most d has a (d+1)-tuple T of depth at least n/c, i.e., any hyperedge that contains T also contains n/c other vertices. - For the relationship between t-tuple coloring and vertex coloring in any hypergraph H we establish the inequality 1/e⋅ tk^{1/t} ≤ f_H(t,k) ≤ f_H(1,tk^{1/t}). For the special case of k = 2, referred to as the bichromatic coloring, we prove that t+1 ≤ f_H(t,2) ≤ max{f_H(1,2), t+1}; this improves upon the previous best known upper bound. - We study the relationship between tuple coloring and epsilon nets. In particular we show that if f_H(1,k) = O(k) for a hypergraph H with n vertices, then for any 0 < ε < 1 the t-tuples of H can be partitioned into Ω((εn/t)^t) ε-t-nets. This bound is tight when t is a constant.
Cite as

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Miloš Stojaković. Polychromatic Coloring of Tuples in Hypergraphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.19,
  author =	{Biniaz, Ahmad and De Carufel, Jean-Lou and Maheshwari, Anil and Smid, Michiel and Smorodinsky, Shakhar and Stojakovi\'{c}, Milo\v{s}},
  title =	{{Polychromatic Coloring of Tuples in Hypergraphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.19},
  URN =		{urn:nbn:de:0030-drops-231718},
  doi =		{10.4230/LIPIcs.SoCG.2025.19},
  annote =	{Keywords: Hypergraph Coloring, Polychromatic Coloring, Geometric Hypergraphs, Cover Decomposable Hypergraphs, Epsilon Nets}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.26
Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model

Authors: Clément L. Canonne, Sayantan Sen, and Joy Qiping Yang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this work, we study the problem of testing m-grainedness of probability distributions over an n-element universe 𝒰, or, equivalently, of whether a probability distribution is induced by a multiset S ⊆ 𝒰 of size |S| = m. Recently, Goldreich and Ron (Computational Complexity, 2023) proved that Ω(n^c) samples are necessary for testing this property, for any c < 1 and m = Θ(n). They also conjectured that Ω(m/(log m)) samples are necessary for testing this property when m = Θ(n). In this work, we positively settle this conjecture. Using a known connection to the Distribution over Huge objects (DoHo) model introduced by Goldreich and Ron (TheoretiCS, 2023), we leverage our results to provide improved bounds for uniformity testing in the DoHo model.
Cite as

Clément L. Canonne, Sayantan Sen, and Joy Qiping Yang. Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.ITCS.2025.26,
  author =	{Canonne, Cl\'{e}ment L. and Sen, Sayantan and Yang, Joy Qiping},
  title =	{{Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.26},
  URN =		{urn:nbn:de:0030-drops-226543},
  doi =		{10.4230/LIPIcs.ITCS.2025.26},
  annote =	{Keywords: Distribution testing, Uniformity testing, Huge Object Model, Lower bounds}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.26
Improved Streaming Algorithm for the Klee’s Measure Problem and Generalizations

Authors: Mridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, and Sourav Chakraborty

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
Estimating the size of the union of a stream of sets S₁, S₂, …, S_M where each set is a subset of a known universe Ω is a fundamental problem in data streaming. This problem naturally generalizes the well-studied 𝖥₀ estimation problem in the streaming literature, where each set contains a single element from the universe. We consider the general case when the sets S_i can be succinctly represented and allow efficient membership, cardinality, and sampling queries (called a Delphic family of sets). A notable example in this framework is the Klee’s Measure Problem (KMP), where every set S_i is an axis-parallel rectangle in d-dimensional spaces (Ω = [Δ]^d where [Δ] := {1, … ,Δ} and Δ ∈ ℕ). Recently, Meel, Chakraborty, and Vinodchandran (PODS-21, PODS-22) designed a streaming algorithm for (ε,δ)-estimation of the size of the union of set streams over Delphic family with space and update time complexity O((log³|Ω|)/ε² ⋅ log 1/δ) and Õ((log⁴|Ω|)/ε² ⋅ log 1/(δ)), respectively. This work presents a new, sampling-based algorithm for estimating the size of the union of Delphic sets that has space and update time complexity Õ((log²|Ω|)/ε² ⋅ log 1/(δ)). This improves the space complexity bound by a log|Ω| factor and update time complexity bound by a log² |Ω| factor. A critical question is whether quadratic dependence of log|Ω| on space and update time complexities is necessary. Specifically, can we design a streaming algorithm for estimating the size of the union of sets over Delphic family with space and complexity linear in log|Ω| and update time poly(log|Ω|)? While this appears technically challenging, we show that establishing a lower bound of ω(log|Ω|) with poly(log|Ω|) update time is beyond the reach of current techniques. Specifically, we show that under certain hard-to-prove computational complexity hypothesis, there is a streaming algorithm for the problem with optimal space complexity O(log|Ω|) and update time poly(log(|Ω|)). Thus, establishing a space lower bound of ω(log|Ω|) will lead to break-through complexity class separation results.
Cite as

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/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 26:1-26:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{nandi_et_al:LIPIcs.APPROX/RANDOM.2024.26,
  author =	{Nandi, Mridul and Vinodchandran, N. V. and Ghosh, Arijit and Meel, Kuldeep S. and Pal, Soumit and Chakraborty, Sourav},
  title =	{{Improved Streaming Algorithm for the Klee’s Measure Problem and Generalizations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{26:1--26:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.26},
  URN =		{urn:nbn:de:0030-drops-210191},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.26},
  annote =	{Keywords: Sampling, Streaming, Klee’s Measure Problem}
}
  • Refine by Type
  • 34 Document/PDF
  • 14 Document/HTML

  • Refine by Publication Year
  • 5 2026
  • 9 2025
  • 2 2024
  • 1 2023
  • 5 2022
  • Show More...

  • Refine by Author
  • 21 Ghosh, Arijit
  • 12 Mishra, Gopinath
  • 7 Bishnu, Arijit
  • 5 Chakraborty, Sourav
  • 5 Paraashar, Manaswi
  • Show More...

  • Refine by Series/Journal
  • 33 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 12 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 7 Theory of computation → Computational geometry
  • 3 Mathematics of computing → Probabilistic algorithms
  • 3 Theory of computation
  • 2 Theory of computation → Boolean function learning
  • Show More...

  • Refine by Keyword
  • 3 Query Complexity
  • 3 Query complexity
  • 2 Tolerant Testing
  • 2 communication complexity
  • 2 discrete geometry
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact