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
Probabilistic and Analytic Methods in Theoretical Computer Science and Combinatorics

Recent papers

Stabbing boxes with finitely many axis-parallel lines and flats
with Sutanoya Chakraborty and Soumi Nandi
Discrete Mathematics, 348 (2): 114269, 2025

Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
with Sourav Chakraborty, Eldar Fischer, Gopinath Mishra, and Sayantan Sen
IEEE Transactions on Information Theory, accepted, 2024

Improved Streaming Algorithm for Klee's Measure Problem  and Generalizations
with Sourav Chakraborty, Kuldeep Meel, Mridul Nandi, Soumit Pal, and N. V. Vinodchandran
APPROX 2024: International Conference on Approximation Algorithms for
Combinatorial Optimization Problems

Faster Counting and Sampling Algorithms using a Colorful Decision Oracle
with Anup Bhattacharya, Arijit Bishnu, and  Gopinath Mishra
ACM Transactions on Computation Theory, 16(2): 1 – 19, 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

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