Arijit Ghosh

Research interests

Broadly my research interests are in Theoretical Computer Science and Combinatorics. I am currently looking into

Discrete and Computational Geometry and Topology
Polynomial Methods and Incidence Geometry
Sublinear Algorithms
Applications of Probability and Analytic Techniques in Theoretical Computer Science and Combinatorics

Recent papers

Faster Counting and Sampling Algorithms using a Colorful Decision Oracle
with Anup Bhattacharya, Arijit Bishnu, and  Gopinath Mishra
ACM Transactions on Computation Theory, accepted, 2024
(Featured in Oded Goldreich's Choices)

Testing of Index-Invariant Properties in the Huge Object Model
with Sourav Chakraborty, Eldar Fischer, Gopinath Mishra, and Sayantan Sen
COLT 2023: Annual Conference on Learning Theory
(Featured in Oded Goldreich's Choices)

Local Criteria for Triangulating General Manifolds
with Jean-Daniel Boissonnat, Ramsay Dyer, and Mathijs Wintraecken
Discrete & Computational Geometry, 69(1): 156 – 191, 2023

Covering almost all the layers of the hypercube with multiplicities
with Chandrima Kayal and Soumi Nandi
Discrete Mathematics, 346(7): 113397, 2023

On the Complexity of Triangle Counting using Emptiness Queries
with Arijit Bishnu and Gopinath Mishra
RANDOM 2023: International Conference on Randomization and Computation 

Uniform Brackets, Containers, and Combinatorial Macbeath Regions
with Kunal Dutta  and Shay Moran
ITCS 2022: Innovations in Theoretical Computer Science

Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond
with Anup Bhattacharya, Sourav Chakraborty, Gopinath Mishra, and Manaswi Paraashar
Computational Complexity, 31(2): 9, 2022 

Tolerant Bipartiteness Testing in Dense Graphs
with Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen
ICALP 2022: International Colloquium on Automata, Languages and Programming

Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
with Sourav Chakraborty, Eldar Fischer, Gopinath Mishra, and Sayantan Sen
RANDOM 2022: International Conference on Randomization and Computation

Local Conditions for Triangulating Submanifolds of Euclidean Space
with Jean-Daniel Boissonnat, Ramsay Dyer, André Lieutier, and Mathijs Wintraecken
Discrete & Computational Geometry, 66(2): 666 – 686, 2021

Distance Estimation between Unknown Matrices using Sublinear Projections on Hamming Cube
with Arijit Bishnu and Gopinath Mishra
RANDOM 2021: International Conference on Randomization and Computation

Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query
and Communication Worlds
with Sourav Chakraborty, Gopinath Mishra, and Sayantan Sen
RANDOM 2021: International Conference on Randomization and Computation

Query Complexity of Global Minimum Cut
with Arijit Bishnu, Gopinath Mishra, and Manaswi Paraashar
APPROX 2021: International Conference on Approximation Algorithms for
Combinatorial Optimization Problems