Gopinath Mishra

80 papers A* 9A 7B 4C 1Misc 1Journal 51Unranked 7

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Parallel derandomization for coloring. Theor. Comput. Sci. Sam Coy, Artur Czumaj, Peter Davies-Peck, Gopinath Mishra
2026	J	`jnl`	The Complexity of Distributed Minimum Weight Cycle Approximation. CoRR Yi-Jun Chang, Yanyu Chen, Dipan Dey, Yonggang Jiang, Gopinath Mishra, Hung Thuan Nguyen, Mingyang Yang
2025	J	`jnl`	Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries. CoRR Arijit Bishnu, Debarshi Chanda, Gopinath Mishra
2025	A*	`conf`	Brief Announcement: The Complexity Landscape of Dynamic Distributed Subgraph Finding. PODC Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, Mingyang Yang
2025	J	`jnl`	Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing. IEEE Trans. Inf. Theory Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2025	J	`jnl`	Log-Diameter MST Verification and Sensitivity in MPC. Algorithmica Sam Coy, Artur Czumaj, Gopinath Mishra, Anish Mukherjee
2025	A*	`conf`	Optimal Distributed Replacement Paths. PODC Yi-Jun Chang, Yanyu Chen, Dipan Dey, Gopinath Mishra, Hung Thuan Nguyen, Bryce Sanchez
2025	J	`jnl`	Optimal Distributed Replacement Paths. CoRR Yi-Jun Chang, Yanyu Chen, Dipan Dey, Gopinath Mishra, Hung Thuan Nguyen, Bryce Sanchez
2025	J	`jnl`	Optimal non-adaptive algorithm for edge estimation. CoRR Arijit Bishnu, Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, Gopinath Mishra
2025	—	`conf`	Overlay Network Construction: Improved Overall and Node-Wise Message Complexity. FSTTCS Yi-Jun Chang, Yanyu Chen, Gopinath Mishra
2025	A*	`conf`	Round and Communication Efficient Graph Coloring. PODC Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, Farrel D. Salim
2025	J	`jnl`	Streaming Graph Algorithms in the Massively Parallel Computation Model. CoRR Artur Czumaj, Gopinath Mishra, Anish Mukherjee
2025	A*	`conf`	Testing vs Estimation for Index-Invariant Properties in the Huge Object Model. STOC Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen
2025	A	`conf`	The Complexity Landscape of Dynamic Distributed Subgraph Finding. DISC Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, Mingyang Yang
2025	J	`jnl`	Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models. CoRR Arijit Bishnu, Debarshi Chanda, Gopinath Mishra
2024	A*	`conf`	A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model. PODC Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, Mingyang Yang, Yu-Cheng Yeh
2024	J	`jnl`	Faster Counting and Sampling Algorithms using Colorful Decision Oracle. ACM Trans. Comput. Theory Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2024	B	`conf`	Log Diameter Rounds MST Verification and Sensitivity in MPC. SPAA Sam Coy, Artur Czumaj, Gopinath Mishra, Anish Mukherjee
2024	J	`jnl`	Log Diameter Rounds MST Verification and Sensitivity in MPC. CoRR Sam Coy, Artur Czumaj, Gopinath Mishra, Anish Mukherjee
2024	J	`jnl`	Near Uniform Triangle Sampling Over Adjacency List Graph Streams. CoRR Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2024	J	`jnl`	Overlay Network Construction: Improved Overall and Node-Wise Message Complexity. CoRR Yi-Jun Chang, Yanyu Chen, Gopinath Mishra
2024	—	`conf`	Parallel Derandomization for Coloring (Abstract). HOPC@SPAA Sam Coy, Artur Czumaj, Peter Davies-Peck, Gopinath Mishra
2024	A	`conf`	Parallel Derandomization for Coloring. IPDPS Sam Coy, Artur Czumaj, Peter Davies-Peck, Gopinath Mishra
2024	J	`jnl`	Round and Communication Efficient Graph Coloring. CoRR Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, Farrel D. Salim
2024	A*	`conf`	Streaming Graph Algorithms in the Massively Parallel Computation Model. PODC Artur Czumaj, Gopinath Mishra, Anish Mukherjee
2024	J	`jnl`	Testing vs Estimation for Index-Invariant Properties in the Huge Object Model. CoRR Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen
2024	J	`jnl`	Testing vs Estimation for Index-Invariant Properties in the Huge Object Model. Electron. Colloquium Comput. Complex. Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen
2024	J	`jnl`	The Complexity Landscape of Dynamic Distributed Subgraph Finding. CoRR Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, Mingyang Yang
2023	J	`jnl`	A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model. CoRR Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, Mingyang Yang, Yu-Cheng Yeh
2023	J	`jnl`	Almost optimal query algorithm for hitting set using a subset query. J. Comput. Syst. Sci. Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh
2023	J	`jnl`	Fast Parallel Degree+1 List Coloring. CoRR Sam Coy, Artur Czumaj, Peter Davies, Gopinath Mishra
2023	B	`conf`	On Parallel k-Center Clustering. SPAA Sam Coy, Artur Czumaj, Gopinath Mishra
2023	J	`jnl`	On Parallel k-Center Clustering. CoRR Sam Coy, Artur Czumaj, Gopinath Mishra
2023	A	`conf`	On the Complexity of Triangle Counting Using Emptiness Queries. APPROX/RANDOM Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2023	A*	`conf`	Optimal (Degree+1)-Coloring in Congested Clique. ICALP Sam Coy, Artur Czumaj, Peter Davies, Gopinath Mishra
2023	J	`jnl`	Optimal (degree+1)-Coloring in Congested Clique. CoRR Sam Coy, Artur Czumaj, Peter Davies, Gopinath Mishra
2023	J	`jnl`	Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams. Theory Comput. Syst. Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh
2023	A*	`conf`	Testing of Index-Invariant Properties in the Huge Object Model. COLT Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2022	—	`conf`	Counting and Sampling from Substructures Using Linear Algebraic Queries. FSTTCS Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2022	J	`jnl`	Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. Comput. Complex. Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2022	A	`conf`	Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing. APPROX/RANDOM Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2022	A	`conf`	Faster Counting and Sampling Algorithms Using Colorful Decision Oracle. STACS Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2022	J	`jnl`	Faster Counting and Sampling Algorithms using Colorful Decision Oracle. CoRR Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2022	J	`jnl`	Testing of Index-Invariant Properties in the Huge Object Model. CoRR Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2022	J	`jnl`	Testing of Index-Invariant Properties in the Huge Object Model. Electron. Colloquium Comput. Complex. Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2022	A*	`conf`	Tolerant Bipartiteness Testing in Dense Graphs. ICALP Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, Sayantan Sen
2022	J	`jnl`	Tolerant Bipartiteness Testing in Dense Graphs. CoRR Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, Sayantan Sen
2021	J	`jnl`	Bipartite Independent Set Oracles and Beyond: Can it Even Count Triangles in Polylogarithmic Queries? CoRR Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2021	—	`conf`	Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube. APPROX-RANDOM Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2021	J	`jnl`	Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube. CoRR Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2021	A	`conf`	Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! ITCS Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, Anannya Upasana
2021	J	`jnl`	Exploring the Gap between Tolerant and Non-tolerant Distribution Testing. CoRR Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2021	J	`jnl`	Grid obstacle representation of graphs. Discret. Appl. Math. Arijit Bishnu, Arijit Ghosh, Rogers Mathew, Gopinath Mishra, Subhabrata Paul
2021	—	`conf`	Interplay Between Graph Isomorphism and Earth Mover's Distance in the Query and Communication Worlds. APPROX-RANDOM Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2021	J	`jnl`	On Triangle Estimation Using Tripartite Independent Set Queries. Theory Comput. Syst. Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2021	—	`conf`	Query Complexity of Global Minimum Cut. APPROX-RANDOM Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2020	—	`conf`	Disjointness Through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. APPROX-RANDOM Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2020	J	`jnl`	Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. CoRR Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2020	J	`jnl`	Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. Electron. Colloquium Comput. Complex. Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2020	J	`jnl`	Estimation of Graph Isomorphism Distance in the Query World. Electron. Colloquium Comput. Complex. Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
2020	J	`jnl`	Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming! CoRR Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, Anannya Upasana
2020	J	`jnl`	Existence of planar support for geometric hypergraphs using elementary techniques. Discret. Math. Arijit Bishnu, Sameer Desai, Arijit Ghosh, Gopinath Mishra, Subhabrata Paul
2020	J	`jnl`	FPT Algorithms for Embedding into Low-Complexity Graphic Metrics. ACM Trans. Comput. Theory Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra
2020	Misc	`conf`	Fixed Parameter Tractability of Graph Deletion Problems over Data Streams. COCOON Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh
2020	J	`jnl`	Query Complexity of Global Minimum Cut. CoRR Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2020	J	`jnl`	Query Complexity of Global Minimum Cut. Electron. Colloquium Comput. Complex. Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2019	J	`jnl`	Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams. CoRR Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh
2019	J	`jnl`	Hyperedge Estimation using Polylogarithmic Subset Queries. CoRR Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2019	J	`jnl`	Inner Product Oracle can Estimate and Sample. CoRR Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
2019	B	`conf`	Triangle Estimation Using Tripartite Independent Set Queries. ISAAC Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2018	A	`conf`	FPT Algorithms for Embedding into Low Complexity Graphic Metrics. ESA Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra
2018	J	`jnl`	FPT algorithms for embedding into low complexity graphic metrics. CoRR Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra
2018	J	`jnl`	Improved algorithms for the evacuation route planning problem. J. Comb. Optim. Gopinath Mishra, Subhra Mazumdar, Arindam Pal
2018	J	`jnl`	On the streaming complexity of fundamental geometric problems. CoRR Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Sandeep Sen
2018	B	`conf`	Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers. ISAAC Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh
2018	J	`jnl`	Parameterized Query Complexity of Hitting Set using Stability of Sunflowers. CoRR Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh
2018	J	`jnl`	Triangle Estimation using Polylogarithmic Queries. CoRR Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
2017	J	`jnl`	Grid obstacle representation of graphs. CoRR Arijit Bishnu, Arijit Ghosh, Rogers Mathew, Gopinath Mishra, Subhabrata Paul
2016	J	`jnl`	Improved Algorithms for the Evacuation Route Planning Problem. CoRR Gopinath Mishra, Subhra Mazumdar, Arindam Pal
2015	C	`conf`	Improved Algorithms for the Evacuation Route Planning Problem. COCOA Gopinath Mishra, Subhra Mazumdar, Arindam Pal