Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
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)
@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} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra. Optimal (Degree+1)-Coloring in Congested Clique. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 46:1-46:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{coy_et_al:LIPIcs.ICALP.2023.46, author = {Coy, Sam and Czumaj, Artur and Davies, Peter and Mishra, Gopinath}, title = {{Optimal (Degree+1)-Coloring in Congested Clique}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {46:1--46:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.46}, URN = {urn:nbn:de:0030-drops-180987}, doi = {10.4230/LIPIcs.ICALP.2023.46}, annote = {Keywords: Distributed computing, graph coloring, parallel computing} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
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)
@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} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
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)
@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} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
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)
@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} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
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)
@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} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
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)
@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} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
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)
@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} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
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)
@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} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, and Anannya Upasana. Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 15:1-15:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhattacharya_et_al:LIPIcs.ITCS.2021.15, author = {Bhattacharya, Anup and Bishnu, Arijit and Mishra, Gopinath and Upasana, Anannya}, title = {{Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {15:1--15:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.15}, URN = {urn:nbn:de:0030-drops-135544}, doi = {10.4230/LIPIcs.ITCS.2021.15}, annote = {Keywords: Streaming, random ordering, graph coloring, estimation, lower bounds} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
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)
@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} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
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)
@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} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
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)
@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} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
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)
@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} }
Feedback for Dagstuhl Publishing