Search Results

Documents authored by Ghosh, Arijit

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}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.40
On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups

Authors: Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, and Swagato Sanyal

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given an Abelian group 𝒢, a Boolean-valued function f: 𝒢 → {-1,+1}, is said to be s-sparse, if it has at most s-many non-zero Fourier coefficients over the domain 𝒢. In a seminal paper, Gopalan et al. [Gopalan et al., 2011] proved "Granularity" for Fourier coefficients of Boolean valued functions over ℤ₂ⁿ, that have found many diverse applications in theoretical computer science and combinatorics. They also studied structural results for Boolean functions over ℤ₂ⁿ which are approximately Fourier-sparse. In this work, we obtain structural results for approximately Fourier-sparse Boolean valued functions over Abelian groups 𝒢 of the form, 𝒢: = ℤ_{p_1}^{n_1} × ⋯ × ℤ_{p_t}^{n_t}, for distinct primes p_i. We also obtain a lower bound of the form 1/(m²s)^⌈φ(m)/2⌉, on the absolute value of the smallest non-zero Fourier coefficient of an s-sparse function, where m = p_1 ⋯ p_t, and φ(m) = (p_1-1) ⋯ (p_t-1). We carefully apply probabilistic techniques from [Gopalan et al., 2011], to obtain our structural results, and use some non-trivial results from algebraic number theory to get the lower bound. We construct a family of at most s-sparse Boolean functions over ℤ_pⁿ, where p > 2, for arbitrarily large enough s, where the minimum non-zero Fourier coefficient is o(1/s). The "Granularity" result of Gopalan et al. implies that the absolute values of non-zero Fourier coefficients of any s-sparse Boolean valued function over ℤ₂ⁿ are Ω(1/s). So, our result shows that one cannot expect such a lower bound for general Abelian groups. Using our new structural results on the Fourier coefficients of sparse functions, we design an efficient sparsity testing algorithm for Boolean function, which tests whether the given function is s-sparse, or ε-far from any sparse Boolean function, and it requires poly((ms)^φ(m),1/ε)-many queries. Further, we generalize the notion of degree of a Boolean function over an Abelian group 𝒢. We use it to prove an Ω(√s) lower bound on the query complexity of any adaptive sparsity testing algorithm.
Cite as

Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, and Swagato Sanyal. On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.MFCS.2024.40,
  author =	{Chakraborty, Sourav and Datta, Swarnalipa and Dutta, Pranjal and Ghosh, Arijit and Sanyal, Swagato},
  title =	{{On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.40},
  URN =		{urn:nbn:de:0030-drops-205963},
  doi =		{10.4230/LIPIcs.MFCS.2024.40},
  annote =	{Keywords: Fourier coefficients, sparse, Abelian, granularity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.48
On the Complexity of Triangle Counting Using Emptiness Queries

Authors: Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra

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

Abstract
Beame et al. [ITCS'18 & TALG'20] introduced and used the Bipartite Independent Set (BIS) and Independent Set (IS) oracle access to an unknown, simple, unweighted and undirected graph and solved the edge estimation problem. The introduction of this oracle set forth a series of works in a short time that either solved open questions mentioned by Beame et al. or were generalizations of their work as in Dell and Lapinskas [STOC'18 and TOCT'21], Dell, Lapinskas, and Meeks [SODA'20 and SICOMP'22], Bhattacharya et al. [ISAAC'19 & TOCS'21], and Chen et al. [SODA'20]. Edge estimation using BIS can be done using polylogarithmic queries, while IS queries need sub-linear but more than polylogarithmic queries. Chen et al. improved Beame et al.’s upper bound result for edge estimation using IS and also showed an almost matching lower bound. Beame et al. in their introductory work asked a few open questions out of which one was on estimating structures of higher order than edges, like triangles and cliques, using BIS queries. In this work, we almost resolve the query complexity of estimating triangles using BIS oracle. While doing so, we prove a lower bound for an even stronger query oracle called Edge Emptiness (EE) oracle, recently introduced by Assadi, Chakrabarty, and Khanna [ESA'21] to test graph connectivity.
Cite as

Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. On the Complexity of Triangle Counting Using Emptiness Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 48:1-48:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bishnu_et_al:LIPIcs.APPROX/RANDOM.2023.48,
  author =	{Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath},
  title =	{{On the Complexity of Triangle Counting Using Emptiness Queries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{48:1--48:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.48},
  URN =		{urn:nbn:de:0030-drops-188739},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.48},
  annote =	{Keywords: Triangle Counting, Emptiness Queries, Bipartite Independent Set Query}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.8
Counting and Sampling from Substructures Using Linear Algebraic Queries

Authors: Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
For an unknown n × n matrix A having non-negative entries, the inner product (IP) oracle takes as inputs a specified row (or a column) of A and a vector 𝐯 ∈ ℝⁿ with non-negative entries, and returns their inner product. Given two input vectors x and y in ℝⁿ with non-negative entries, and an unknown matrix A with non-negative entries with IP oracle access, we design almost optimal sublinear time algorithms for the following two fundamental matrix problems: - Find an estimate 𝒳 for the bilinear form x^T A y such that 𝒳 ≈ x^T A y. - Designing a sampler 𝒵 for the entries of the matrix A such that ℙ(𝒵 = (i,j)) ≈ x_i A_{ij} y_j /(x^T A y), where x_i and y_j are i-th and j-th coordinate of 𝐱 and 𝐲 respectively. As special cases of the above results, for any submatrix of an unknown matrix with non-negative entries and IP oracle access, we can efficiently estimate the sum of the entries of any submatrix, and also sample a random entry from the submatrix with probability proportional to its weight. We will show that the above results imply that if we are given IP oracle access to the adjacency matrix of a graph, with non-negative weights on the edges, then we can design sublinear time algorithms for the following two fundamental graph problems: - Estimating the sum of the weights of the edges of an induced subgraph, and - Sampling edges proportional to their weights from an induced subgraph. We show that compared to the classical local queries (degree, adjacency, and neighbor queries) on graphs, we can get a quadratic speedup if we use IP oracle access for the above two problems. Apart from the above, we study several matrix problems through the lens of IP oracle, like testing if the matrix is diagonal, symmetric, doubly stochastic, etc. Note that IP oracle is in the class of linear algebraic queries used lately in a series of works by Ben-Eliezer et al. [SODA'08], Nisan [SODA'21], Rashtchian et al. [RANDOM'20], Sun et al. [ICALP'19], and Shi and Woodruff [AAAI'19]. Recently, IP oracle was used by Bishnu et al. [RANDOM'21] to estimate dissimilarities between two matrices.
Cite as

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Counting and Sampling from Substructures Using Linear Algebraic Queries. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bishnu_et_al:LIPIcs.FSTTCS.2022.8,
  author =	{Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi},
  title =	{{Counting and Sampling from Substructures Using Linear Algebraic Queries}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.8},
  URN =		{urn:nbn:de:0030-drops-174009},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.8},
  annote =	{Keywords: Query complexity, Bilinear form, Uniform sampling, Weighted graphs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.27
Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing

Authors: Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen

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

Abstract
The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently drawn samples from an oracle. The testing task is to distinguish a distribution that satisfies some property from a distribution that is far in some distance measure from satisfying it. The task of tolerant testing imposes a further restriction, that distributions close to satisfying the property are also accepted. This work focuses on the connection between the sample complexities of non-tolerant testing of distributions and their tolerant testing counterparts. When limiting our scope to label-invariant (symmetric) properties of distributions, we prove that the gap is at most quadratic, ignoring poly-logarithmic factors. Conversely, the property of being the uniform distribution is indeed known to have an almost-quadratic gap. When moving to general, not necessarily label-invariant properties, the situation is more complicated, and we show some partial results. We show that if a property requires the distributions to be non-concentrated, that is, the probability mass of the distribution is sufficiently spread out, then it cannot be non-tolerantly tested with o(√n) many samples, where n denotes the universe size. Clearly, this implies at most a quadratic gap, because a distribution can be learned (and hence tolerantly tested against any property) using 𝒪(n) many samples. Being non-concentrated is a strong requirement on properties, as we also prove a close to linear lower bound against their tolerant tests. Apart from the case where the distribution is non-concentrated, we also show if an input distribution is very concentrated, in the sense that it is mostly supported on a subset of size s of the universe, then it can be learned using only 𝒪(s) many samples. The learning procedure adapts to the input, and works without knowing s in advance.
Cite as

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 27:1-27:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2022.27,
  author =	{Chakraborty, Sourav and Fischer, Eldar and Ghosh, Arijit and Mishra, Gopinath and Sen, Sayantan},
  title =	{{Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{27:1--27:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.27},
  URN =		{urn:nbn:de:0030-drops-171497},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.27},
  annote =	{Keywords: Distribution Testing, Tolerant Testing, Non-tolerant Testing, Sample Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.69
Tolerant Bipartiteness Testing in Dense Graphs

Authors: Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser, and Ron. Though the non-tolerant version of bipartite testing has been extensively studied in the literature, the tolerant variant is not well understood. In this paper, we consider the following version of tolerant bipartite testing problem: Given two parameters ε, δ ∈ (0,1), with δ > ε, and access to the adjacency matrix of a graph G, we have to decide whether G can be made bipartite by editing at most ε n² entries of the adjacency matrix of G, or we have to edit at least δ n² entries of the adjacency matrix to make G bipartite. In this paper, we prove that for δ = (2+Ω(1))ε, tolerant bipartite testing can be decided by performing 𝒪̃(1/ε³) many adjacency queries and in 2^𝒪̃(1/ε) time complexity. This improves upon the state-of-the-art query and time complexities of this problem of 𝒪̃(1/ε⁶) and 2^𝒪̃(1/ε²), respectively, due to Alon, Fernandez de la Vega, Kannan and Karpinski, where 𝒪̃(⋅) hides a factor polynomial in log (1/ε).
Cite as

Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen. Tolerant Bipartiteness Testing in Dense Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 69:1-69:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.ICALP.2022.69,
  author =	{Ghosh, Arijit and Mishra, Gopinath and Raychaudhury, Rahul and Sen, Sayantan},
  title =	{{Tolerant Bipartiteness Testing in Dense Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{69:1--69:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.69},
  URN =		{urn:nbn:de:0030-drops-164101},
  doi =		{10.4230/LIPIcs.ICALP.2022.69},
  annote =	{Keywords: Tolerant Testing, Bipartite Testing, Query Complexity, Graph Property Testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.10
Faster Counting and Sampling Algorithms Using Colorful Decision Oracle

Authors: Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
In this work, we consider d-Hyperedge Estimation and d-Hyperedge Sample problem in a hypergraph H(U(H),F(H)) in the query complexity framework, where U(H) denotes the set of vertices and F(H) denotes the set of hyperedges. The oracle access to the hypergraph is called Colorful Independence Oracle (CID), which takes d (non-empty) pairwise disjoint subsets of vertices A₁,…, A_d ⊆ U(ℋ) as input, and answers whether there exists a hyperedge in H having (exactly) one vertex in each A_i, i ∈ {1,2,…,d}. The problem of d-Hyperedge Estimation and d-Hyperedge Sample with CID oracle access is important in its own right as a combinatorial problem. Also, Dell et al. [SODA '20] established that decision vs counting complexities of a number of combinatorial optimization problems can be abstracted out as d-Hyperedge Estimation problems with a CID oracle access. The main technical contribution of the paper is an algorithm that estimates m = |F(H)| with m̂ such that 1/(C_{d)log^{d-1} n) ≤ m̂/m ≤ C_{d} log ^{d-1} n. by using at most C_{d}log ^{d+2} n many CID queries, where n denotes the number of vertices in the hypergraph H and C_d is a constant that depends only on d}. Our result coupled with the framework of Dell et al. [SODA '21] implies improved bounds for the following fundamental problems: Edge Estimation using the Bipartite Independent Set (BIS). We improve the bound obtained by Beame et al. [ITCS '18, TALG '20]. Triangle Estimation using the Tripartite Independent Set (TIS). The previous best bound for the case of graphs with low co-degree (Co-degree for an edge in the graph is the number of triangles incident to that edge in the graph) was due to Bhattacharya et al. [ISAAC '19, TOCS '21], and Dell {et al.}’s result gives the best bound for the case of general graphs [SODA '21]. We improve both of these bounds. Hyperedge Estimation & Sampling using Colorful Independence Oracle (CID). We give an improvement over the bounds obtained by Dell et al. [SODA '21].
Cite as

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Faster Counting and Sampling Algorithms Using Colorful Decision Oracle. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.STACS.2022.10,
  author =	{Bhattacharya, Anup and Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath},
  title =	{{Faster Counting and Sampling Algorithms Using Colorful Decision Oracle}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.10},
  URN =		{urn:nbn:de:0030-drops-158205},
  doi =		{10.4230/LIPIcs.STACS.2022.10},
  annote =	{Keywords: Query Complexity, Subset Query, Hyperedge Estimation, and Colorful Independent Set oracle}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.59
Uniform Brackets, Containers, and Combinatorial Macbeath Regions

Authors: Kunal Dutta, Arijit Ghosh, and Shay Moran

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We study the connections between three seemingly different combinatorial structures - uniform brackets in statistics and probability theory, containers in online and distributed learning theory, and combinatorial Macbeath regions, or Mnets in discrete and computational geometry. We show that these three concepts are manifestations of a single combinatorial property that can be expressed under a unified framework along the lines of Vapnik-Chervonenkis type theory for uniform convergence. These new connections help us to bring tools from discrete and computational geometry to prove improved bounds for these objects. Our improved bounds help to get an optimal algorithm for distributed learning of halfspaces, an improved algorithm for the distributed convex set disjointness problem, and improved regret bounds for online algorithms against σ-smoothed adversary for a large class of semi-algebraic threshold functions.
Cite as

Kunal Dutta, Arijit Ghosh, and Shay Moran. Uniform Brackets, Containers, and Combinatorial Macbeath Regions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 59:1-59:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.ITCS.2022.59,
  author =	{Dutta, Kunal and Ghosh, Arijit and Moran, Shay},
  title =	{{Uniform Brackets, Containers, and Combinatorial Macbeath Regions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{59:1--59:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.59},
  URN =		{urn:nbn:de:0030-drops-156551},
  doi =		{10.4230/LIPIcs.ITCS.2022.59},
  annote =	{Keywords: communication complexity, distributed learning, emperical process theory, online algorithms, discrete geometry, computational geometry}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.6
Query Complexity of Global Minimum Cut

Authors: Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar

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

Abstract
In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like Degree, Neighbor, and Adjacency queries. Given ε ∈ (0,1), the algorithm with high probability outputs an estimate t̂ satisfying the following (1-ε) t ≤ t̂ ≤ (1+ε) t, where t is the size of minimum cut in the graph. The expected number of local queries used by our algorithm is min{m+n,m/t}poly(log n,1/(ε)) where n and m are the number of vertices and edges in the graph, respectively. Eden and Rosenbaum showed that Ω(m/t) local queries are required for approximating the size of minimum cut in graphs, {but no local query based algorithm was known. Our algorithmic result coupled with the lower bound of Eden and Rosenbaum [APPROX 2018] resolve the query complexity of the problem of estimating the size of minimum cut in graphs using local queries.} Building on the lower bound of Eden and Rosenbaum, we show that, for all t ∈ ℕ, Ω(m) local queries are required to decide if the size of the minimum cut in the graph is t or t-2. Also, we show that, for any t ∈ ℕ, Ω(m) local queries are required to find all the minimum cut edges even if it is promised that the input graph has a minimum cut of size t. Both of our lower bound results are randomized, and hold even if we can make Random Edge queries in addition to local queries.
Cite as

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Query Complexity of Global Minimum Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bishnu_et_al:LIPIcs.APPROX/RANDOM.2021.6,
  author =	{Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi},
  title =	{{Query Complexity of Global Minimum Cut}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.6},
  URN =		{urn:nbn:de:0030-drops-146992},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.6},
  annote =	{Keywords: Query complexity, Global mincut}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.34
Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds

Authors: Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen

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

Abstract
The graph isomorphism distance between two graphs G_u and G_k is the fraction of entries in the adjacency matrix that has to be changed to make G_u isomorphic to G_k. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in the query model. In other words, if G_k is a known graph and G_u is an unknown graph whose adjacency matrix has to be accessed by querying the entries, what is the query complexity for testing whether the graph isomorphism distance between G_u and G_k is less than γ₁ or more than γ₂, where γ₁ and γ₂ are two constants with 0 ≤ γ₁ < γ₂ ≤ 1. It is also called the tolerant property testing of graph isomorphism in the dense graph model. The non-tolerant version (where γ₁ is 0) has been studied by Fischer and Matsliah (SICOMP'08). In this paper, we prove a (interesting) connection between tolerant graph isomorphism testing and tolerant testing of the well studied Earth Mover’s Distance (EMD). We prove that deciding tolerant graph isomorphism is equivalent to deciding tolerant EMD testing between multi-sets in the query setting. Moreover, the reductions between tolerant graph isomorphism and tolerant EMD testing (in query setting) can also be extended directly to work in the two party Alice-Bob communication model (where Alice and Bob have one graph each and they want to solve tolerant graph isomorphism problem by communicating bits), and possibly in other sublinear models as well. Testing tolerant EMD between two probability distributions is equivalent to testing EMD between two multi-sets, where the multiplicity of each element is taken appropriately, and we sample elements from the unknown multi-set with replacement. In this paper, our (main) contribution is to introduce the problem of {(tolerant) EMD testing between multi-sets (over Hamming cube) when we get samples from the unknown multi-set without replacement} and to show that this variant of tolerant testing of EMD is as hard as tolerant testing of graph isomorphism between two graphs. {Thus, while testing of equivalence between distributions is at the heart of the non-tolerant testing of graph isomorphism, we are showing that the estimation of the EMD over a Hamming cube (when we are allowed to sample without replacement) is at the heart of tolerant graph isomorphism.} We believe that the introduction of the problem of testing EMD between multi-sets (when we get samples without replacement) opens an entirely new direction in the world of testing properties of distributions.
Cite as

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2021.34,
  author =	{Chakraborty, Sourav and Ghosh, Arijit and Mishra, Gopinath and Sen, Sayantan},
  title =	{{Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{34:1--34:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.34},
  URN =		{urn:nbn:de:0030-drops-147273},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.34},
  annote =	{Keywords: Graph Isomorphism, Earth Mover Distance, Query Complexity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.44
Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube

Authors: Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra

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

Abstract
Using geometric techniques like projection and dimensionality reduction, we show that there exists a randomized sub-linear time algorithm that can estimate the Hamming distance between two matrices. Consider two matrices A and B of size n × n whose dimensions are known to the algorithm but the entries are not. The entries of the matrix are real numbers. The access to any matrix is through an oracle that computes the projection of a row (or a column) of the matrix on a vector in {0,1}ⁿ. We call this query oracle to be an Inner Product oracle (shortened as IP). We show that our algorithm returns a (1± ε) approximation to {D}_M (A,B) with high probability by making O(n/(√{{D)_M (A,B)}}poly(log n, 1/(ε))) oracle queries, where {D}_M (A,B) denotes the Hamming distance (the number of corresponding entries in which A and B differ) between two matrices A and B of size n × n. We also show a matching lower bound on the number of such IP queries needed. Though our main result is on estimating {D}_M (A,B) using IP, we also compare our results with other query models.
Cite as

Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 44:1-44:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bishnu_et_al:LIPIcs.APPROX/RANDOM.2021.44,
  author =	{Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath},
  title =	{{Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{44:1--44:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.44},
  URN =		{urn:nbn:de:0030-drops-147378},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.44},
  annote =	{Keywords: Distance estimation, Property testing, Dimensionality reduction, Sub-linear algorithms}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.23
Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond

Authors: Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar

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

Abstract
The disjointness problem - where Alice and Bob are given two subsets of {1, … , n} and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be Θ(n), it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik–Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by d, we analyze how large can the deterministic and randomized communication complexities be, as a function of d and n. The d-sparse set disjointness problem, where the sets have size at most d, is one such set system with VC dimension d. The deterministic and the randomized communication complexities of the d-sparse set disjointness problem have been well studied and is known to be Θ (d log ({n}/{d})) and Θ(d), respectively, in the multi-round communication setting. In this paper, we address the question of whether the randomized communication complexity is always upper bounded by a function of the VC dimension of the set system, and does there always exist a gap between the deterministic and randomized communication complexity for set systems with small VC dimension. In this paper, we construct two natural set systems of VC dimension d, motivated from geometry. Using these set systems we show that the deterministic and randomized communication complexity can be Θ̃(dlog (n/d)) for set systems of VC dimension d and this matches the deterministic upper bound for all set systems of VC dimension d. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exists set systems of VC dimension d such that both deterministic and randomized (one-way and multi-round) complexities for the set intersection problem can be as high as Θ(dlog (n/d)), and this is tight among all set systems of VC dimension d.
Cite as

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.APPROX/RANDOM.2020.23,
  author =	{Bhattacharya, Anup and Chakraborty, Sourav and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi},
  title =	{{Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.23},
  URN =		{urn:nbn:de:0030-drops-126261},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.23},
  annote =	{Keywords: Communication complexity, VC dimension, Sparsity, and Geometric Set System}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.19
Triangle Estimation Using Tripartite Independent Set Queries

Authors: Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an approximate triangle counting algorithm using only polylogarithmic queries when the number of triangles on any edge in the graph is polylogarithmically bounded. Our query oracle Tripartite Independent Set (TIS) takes three disjoint sets of vertices A, B and C as input, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model generally belongs to the class of group queries (Ron and Tsur, ACM ToCT, 2016; Dell and Lapinskas, STOC 2018) and in particular is inspired by the Bipartite Independent Set (BIS) query oracle of Beame et al. (ITCS 2018). We extend the algorithmic framework of Beame et al., with TIS replacing BIS, for triangle counting using ideas from color coding due to Alon et al. (J. ACM, 1995) and a concentration inequality for sums of random variables with bounded dependency (Janson, Rand. Struct. Alg., 2004).
Cite as

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Triangle Estimation Using Tripartite Independent Set Queries. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ISAAC.2019.19,
  author =	{Bhattacharya, Anup and Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath},
  title =	{{Triangle Estimation Using Tripartite Independent Set Queries}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.19},
  URN =		{urn:nbn:de:0030-drops-115156},
  doi =		{10.4230/LIPIcs.ISAAC.2019.19},
  annote =	{Keywords: Triangle estimation, query complexity, sublinear algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.25
Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers

Authors: Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
In this paper, we study the query complexity of parameterized decision and optimization versions of Hitting-Set. We also investigate the query complexity of Packing. In doing so, we use generalizations to hypergraphs of an earlier query model, known as BIS introduced by Beame et al. in ITCS'18. The query models considered are the GPIS and GPISE oracles. The GPIS and GPISE oracles are used for the decision and optimization versions of the problems, respectively. We use color coding and queries to the oracles to generate subsamples from the hypergraph, that retain some structural properties of the original hypergraph. We use the stability of the sunflowers in a non-trivial way to do so.
Cite as

Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh. Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bishnu_et_al:LIPIcs.ISAAC.2018.25,
  author =	{Bishnu, Arijit and Ghosh, Arijit and Kolay, Sudeshna and Mishra, Gopinath and Saurabh, Saket},
  title =	{{Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.25},
  URN =		{urn:nbn:de:0030-drops-99735},
  doi =		{10.4230/LIPIcs.ISAAC.2018.25},
  annote =	{Keywords: Query complexity, Hitting set, Parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.35
FPT Algorithms for Embedding into Low Complexity Graphic Metrics

Authors: Arijit Ghosh, Sudeshna Kolay, and Gopinath Mishra

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
The Metric Embedding problem takes as input two metric spaces (X,D_X) and (Y,D_Y), and a positive integer d. The objective is to determine whether there is an embedding F:X - > Y such that the distortion d_{F} <= d. Such an embedding is called a distortion d embedding. In parameterized complexity, the Metric Embedding problem is known to be W-hard and therefore, not expected to have an FPT algorithm. In this paper, we consider the Gen-Graph Metric Embedding problem, where the two metric spaces are graph metrics. We explore the extent of tractability of the problem in the parameterized complexity setting. We determine whether an unweighted graph metric (G,D_G) can be embedded, or bijectively embedded, into another unweighted graph metric (H,D_H), where the graph H has low structural complexity. For example, H is a cycle, or H has bounded treewidth or bounded connected treewidth. The parameters for the algorithms are chosen from the upper bound d on distortion, bound Delta on the maximum degree of H, treewidth alpha of H, and the connected treewidth alpha_{c} of H. Our general approach to these problems can be summarized as trying to understand the behavior of the shortest paths in G under a low distortion embedding into H, and the structural relation the mapping of these paths has to shortest paths in H.
Cite as

Arijit Ghosh, Sudeshna Kolay, and Gopinath Mishra. FPT Algorithms for Embedding into Low Complexity Graphic Metrics. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.ESA.2018.35,
  author =	{Ghosh, Arijit and Kolay, Sudeshna and Mishra, Gopinath},
  title =	{{FPT Algorithms for Embedding into Low Complexity Graphic Metrics}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{35:1--35:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.35},
  URN =		{urn:nbn:de:0030-drops-94988},
  doi =		{10.4230/LIPIcs.ESA.2018.35},
  annote =	{Keywords: Metric spaces, metric embedding, FPT, dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.9
Local Criteria for Triangulation of Manifolds

Authors: Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.
Cite as

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. Local Criteria for Triangulation of Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2018.9,
  author =	{Boissonnat, Jean-Daniel and Dyer, Ramsay and Ghosh, Arijit and Wintraecken, Mathijs},
  title =	{{Local Criteria for Triangulation of Manifolds}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.9},
  URN =		{urn:nbn:de:0030-drops-87224},
  doi =		{10.4230/LIPIcs.SoCG.2018.9},
  annote =	{Keywords: manifold, simplicial complex, homeomorphism, triangulation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.25
Kernelization of the Subset General Position Problem in Geometry

Authors: Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh, and Sudeshna Kolay

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
In this paper, we consider variants of the Geometric Subset General Position problem. In defining this problem, a geometric subsystem is specified, like a subsystem of lines, hyperplanes or spheres. The input of the problem is a set of n points in \mathbb{R}^d and a positive integer k. The objective is to find a subset of at least k input points such that this subset is in general position with respect to the specified subsystem. For example, a set of points is in general position with respect to a subsystem of hyperplanes in \mathbb{R}^d if no d+1 points lie on the same hyperplane. In this paper, we study the Hyperplane Subset General Position problem under two parameterizations. When parameterized by k then we exhibit a polynomial kernelization for the problem. When parameterized by h=n-k, or the dual parameter, then we exhibit polynomial kernels which are also tight, under standard complexity theoretic assumptions. We can also exhibit similar kernelization results for d-Polynomial Subset General Position, where a vector space of polynomials of degree at most d are specified as the underlying subsystem such that the size of the basis for this vector space is b. The objective is to find a set of at least k input points, or in the dual delete at most h = n-k points, such that no b+1 points lie on the same polynomial. Notice that this is a generalization of many well-studied geometric variants of the Set Cover problem, such as Circle Subset General Position. We also study general projective variants of these problems. These problems are also related to other geometric problems like Subset Delaunay Triangulation problem.
Cite as

Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh, and Sudeshna Kolay. Kernelization of the Subset General Position Problem in Geometry. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.MFCS.2017.25,
  author =	{Boissonnat, Jean-Daniel and Dutta, Kunal and Ghosh, Arijit and Kolay, Sudeshna},
  title =	{{Kernelization of the Subset General Position Problem in Geometry}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.25},
  URN =		{urn:nbn:de:0030-drops-80863},
  doi =		{10.4230/LIPIcs.MFCS.2017.25},
  annote =	{Keywords: Incidence Geometry, Kernel Lower bounds, Hyperplanes, Bounded degree polynomials}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.38
Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning

Authors: Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The packing lemma of Haussler states that given a set system (X,R) with bounded VC dimension, if every pair of sets in R have large symmetric difference, then R cannot contain too many sets. Recently it was generalized to the shallow packing lemma, applying to set systems as a function of their shallow-cell complexity. In this paper we present several new results and applications related to packings: * an optimal lower bound for shallow packings, * improved bounds on Mnets, providing a combinatorial analogue to Macbeath regions in convex geometry, * we observe that Mnets provide a general, more powerful framework from which the state-of-the-art unweighted epsilon-net results follow immediately, and * simplifying and generalizing one of the main technical tools in [Fox et al. , J. of the EMS, to appear].
Cite as

Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa. Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.SoCG.2017.38,
  author =	{Dutta, Kunal and Ghosh, Arijit and Jartoux, Bruno and Mustafa, Nabil H.},
  title =	{{Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.38},
  URN =		{urn:nbn:de:0030-drops-71991},
  doi =		{10.4230/LIPIcs.SoCG.2017.38},
  annote =	{Keywords: Epsilon-nets, Haussler's packing lemma, Mnets, shallow-cell complexity, shallow packing lemma}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.96
Two Proofs for Shallow Packings

Authors: Kunal Dutta, Esther Ezra, and Arijit Ghosh

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let V be a finite set system defined over an n-point set X; we view V as a set of indicator vectors over the n-dimensional unit cube. A delta-separated set of V is a subcollection W, s.t. the Hamming distance between each pair u, v in W is greater than delta, where delta > 0 is an integer parameter. The delta-packing number is then defined as the cardinality of the largest delta-separated subcollection of V. Haussler showed an asymptotically tight bound of Theta((n / delta)^d) on the delta-packing number if V has VC-dimension (or primal shatter dimension) d. We refine this bound for the scenario where, for any subset, X' of X of size m <= n and for any parameter 1 <= k <= m, the number of vectors of length at most k in the restriction of V to X' is only O(m^{d_1} k^{d-d_1}), for a fixed integer d > 0 and a real parameter 1 <= d_1 <= d (this generalizes the standard notion of bounded primal shatter dimension when d_1 = d). In this case when V is "k-shallow" (all vector lengths are at most k), we show that its delta-packing number is O(n^{d_1} k^{d-d_1} / delta^d), matching Haussler's bound for the special cases where d_1=d or k=n. We present two proofs, the first is an extension of Haussler's approach, and the second extends the proof of Chazelle, originally presented as a simplification for Haussler's proof.
Cite as

Kunal Dutta, Esther Ezra, and Arijit Ghosh. Two Proofs for Shallow Packings. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 96-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.SOCG.2015.96,
  author =	{Dutta, Kunal and Ezra, Esther and Ghosh, Arijit},
  title =	{{Two Proofs for Shallow Packings}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{96--110},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.96},
  URN =		{urn:nbn:de:0030-drops-51493},
  doi =		{10.4230/LIPIcs.SOCG.2015.96},
  annote =	{Keywords: Set systems of bounded primal shatter dimension, delta-packing \& Haussler’s approach, relative approximations, Clarkson-Shor random sampling approach}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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