Papers by topics

(To see the list in chronological order click here)

Computational Topology

Simplicial subdivision of simplices of arbitrary dimension in a space of constant non-zero curvature with bounded quality
with Jean-Daniel Boissonnat, Florestan Brunck, Hana Dal Poz Kouřimská, and Mathijs Wintraecken
Manuscript
Local Criteria for Triangulating General Manifolds
with Jean-Daniel Boissonnat, Ramsay Dyer, and Mathijs Wintraecken
Discrete & Computational Geometry, 69(1): 156 – 191, 2023
SoCG 2018: Symposium on Computational Geometry
[ArXiv] [SoCG'18] [Journal version]

Comment: The conference version of this paper that appeared in SoCG'18 was titled ``Local Criteria for Triangulation of Manifolds''
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
[HAL] [Journal version]
Delaunay Triangulations of Manifolds
with Jean-Daniel Boissonnat and Ramsay Dyer
Foundations of Computational Mathematics, 18(2): 399 – 431, 2018
[ArXiv] [HAL] [Journal version]
An Obstruction to Delaunay Triangulations in Riemannian Manifolds
with Jean-Daniel Boissonnat, Ramsay Dyer, and Nikolay Martynchuk
Discrete & Computational Geometry, 59(1): 226 – 237, 2018
[ArXiv] [HAL] [Journal version]
Only distances are required to reconstruct submanifolds
with Jean-Daniel Boissonnat, Ramsay Dyer, and Steve Y. Oudot
Computational Geometry, 66: 32 – 67, 2017
[ArXiv] [HAL] [Journal version]
An elementary approach to tangent space variation on Riemannian submanifolds
with Jean-Daniel Boissonnat and Ramsay Dyer
Manuscript
[ArXiv]

Comment: Older version was titled ``Tangent space variation on submanifolds''
Constructing Intrinsic Delaunay Triangulations of Submanifolds
with Jean-Daniel Boissonnat and Ramsay Dyer
INRIA Research Report RR-8273, 2013
[ArXiv] [HAL]
The Stability of Delaunay Triangulations
with Jean-Daniel Boissonnat and Ramsay Dyer
International Journal of Computational Geometry & Applications, 23(4-5): 303 – 334, 2013
(Special Issue for SoCG 2012)
[ArXiv] [HAL] [Journal version]
Piecewise linear reconstruction and meshing of submanifolds of Euclidean space
PhD Thesis, INRIA Sophia Antipolis - Méditerranée, May 2012
Supervisor: Jean-Daniel Boissonnat
[PhD Thesis]
Stability of Delaunay-type Structures for Manifolds
with Jean-Daniel Boissonnat and Ramsay Dyer
SoCG 2012: Symposium on Computational Geometry
[SoCG'12]

Comments: Also see INRIA Research Reports RR-8276 and RR-8273
Equating the Witness and Restricted Delaunay Complexes
with Jean-Daniel Boissonnat, Ramsay Dyer, and Steve Y. Oudot
EWCG 2012: European Workshop on Computational Geometry
[HAL] [EWCG'12]
Triangulating Smooth Submanifolds with Light Scaffolding
with Jean-Daniel Boissonnat
Mathematics in Computer Science, 4(4): 431 – 461, 2010
[HAL] [Journal version]
Manifold Reconstruction Using Tangential Delaunay Complexes
with Jean-Daniel Boissonnat
Discrete & Computational Geometry, 51(1): 221 – 267, 2014
SoCG 2010: Symposium on Computational Geometry
[HAL] [SoCG'10] [Journal version]

Comment: Also see Chapters 3 and 4 from my Ph.D. Thesis

Polynomial Method & Incidence Geometry

On higher multiplicity hyperplane and polynomial covers for symmetry preserving subsets of the hypercube
with Chandrima Kayal, Soumi Nandi, and S. Venkitesh
Submitted
[ArXiv]
Covering almost all the layers of the hypercube with multiplicities
with Chandrima Kayal and Soumi Nandi
Discrete Mathematics, 346(7): 113397, 2023
[ArXiv] [Journal]
Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning
with Bruno Jartoux, Kunal Dutta, and Nabil H. Mustafa
Discrete & Computational Geometry, 61(4): 756 – 777, 2019
(Special Issue for SoCG 2017)
SoCG 2017: Symposium on Computational Geometry
[HAL] [SoCG'17] [Journal version]
Kernelization of the Subset General Position Problem in Geometry
with Jean-Daniel Boissonnat, Kunal Dutta, and Sudeshna Kolay
MFCS 2017: International Symposium on Mathematical Foundations of Computer Science
[HAL] [MFCS'17]

Discrete Geometry

A Hanani-Tutte Theorem for Cycles
with Sutanoya Chakraborty
Submitted
[ArXiv]
Countably Colorful Hyperplane Transversal
with Sutanoya Chakraborty and Soumi Nandi
Submitted
[ArXiv]
Dimension Independent Helly Theorem for Lines and Flats
with Sutanoya Chakraborty and Soumi Nandi
Submitted
[ArXiv]
Heterochromatic Geometric Transversal of Convex Sets
with Sutanoya Chakraborty and Soumi Nandi
Submitted
[ArXiv]
Stabbing boxes with finitely many axis-parallel lines and flats
with Sutanoya Chakraborty and Soumi Nandi
Submitted
[ArXiv]
Discrepancy of Sparse Geometric Set Systems with Low Shallow Cell Complexity
with Kunal Dutta
Submitted
[ArXiv]
Colorful Helly Theorem for Piercing Boxes with Multiple Points
with Sourav Chakraborty and Soumi Nandi
[ArXiv]
Uniform Brackets, Containers, and Combinatorial Macbeath Regions
with Kunal Dutta and Shay Moran
ITCS 2022: Innovations in Theoretical Computer Science
HALG 2023: Highlights of Algorithms
[ArXiv] [ITCS'22] [Conference Talk]
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
RANDOM 2020: International Conference on Randomization and Computation
[ECCC] [ArXiv] [RANDOM'20] [Conference Talk] [Journal version]
Grid Obstacle Representation of Graphs
with Arijit Bishnu, Gopinath Mishra, Rogers Mathew, and Subhabrata Paul
Discrete Applied Mathematics, 296: 39 – 51, 2021
[ArXiv] [Journal version]
Existence of Planar Support for Geometric Hypergraphs using Elementary Techniques
with Arijit Bishnu, Sameer Desai, Gopinath Mishra, and Subhabrata Paul
Discrete Mathematics, 343(6): 111853, 2020
[Journal version]
Delaunay simplices in diagonally distorted lattices
with Aruni Choudhary
Computational Geometry, 81: 33 – 44, 2019
[ArXiv] [Journal version]
A Simple Proof of Optimal Epsilon Nets
with Kunal Dutta and Nabil H. Mustafa
Combinatorica, 38(5): 1269 – 1277, 2018
[HAL] [Journal version]
A New Asymmetric Correlation Inequality for Gaussian Measure
with Kunal Dutta and Nabil H. Mustafa
Manuscript
[HAL]
Two proofs for Shallow Packings
with Kunal Dutta and Esther Ezra
Discrete & Computational Geometry, 56(4): 910 – 939, 2016
(Special Issue for SoCG 2015)
SoCG 2015: Symposium on Computational Geometry
[HAL] [SoCG'15] [Journal version]

Distribution Testing

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
[ECCC] [ArXiv] [COLT'23]

Comment: Featured in Oded Goldreich's Choices
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
HALG 2023: Highlights of Algorithms
[ArXiv] [RANDOM'22]

Sublinear Algorithms

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
STACS 2022: International Symposium on Theoretical Aspects of Computer Science
HALG 2022: Highlights of Algorithms
[ArXiv] [STACS'22] [Journal version] [Short Talk]

Comment: Featured in Oded Goldreich's Choices
A new concentration inequality for ordered hypergraphs
with Anup Bhattacharya, Arijit Bishnu and Gopinath Mishra
Manuscript
Streaming Klee’s Measure Problem in High Dimension and its Generalizations
with Sourav Chakraborty, Kuldeep S. Meel, Mridul Nandi, Soumit Pal, and N. V. Vinodchandran
Manuscript
Near Uniform Triangle Sampling Over Adjacency List Graph Streams
with Arijit Bishnu, Gopinath Mishra, and Sayantan Sen
Submitted
On the Complexity of Triangle Counting using Emptiness Queries
with Arijit Bishnu and Gopinath Mishra
RANDOM 2023: International Conference on Randomization and Computation
[RANDOM'23] [Short Talk]
Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams
with Arijit Bishnu, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh
Theory of Computing Systems, 67(6): 1241 – 1267, 2023
COCOON 2020: International Computing and Combinatorics Conference
[ArXiv] [COCOON'20] [Journal]

Comments: An extended abstract of this paper that appeared in COCOON'20 was titled ``Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams''
Almost optimal query algorithm for hitting set using a subset query
with Arijit Bishnu, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh
Journal of Computer and System Sciences, 137: 50 – 65, 2023
ISAAC 2018: International Symposium on Algorithms and Computation
[ArXiv] [ISAAC'18] [Journal version]

Comments: An extended abstract of this paper that appeared in ISAAC'18 was titled ``Parameterized Query Complexity of Hitting Set using Stability of Sunflowers''
Counting and Sampling from Substructures using Linear Algebraic Queries
with Arijit Bishnu, Gopinath Mishra, and Manaswi Paraashar
FSTTCS 2022: Foundations of Software Technology and Theoretical Computer Science
[ArXiv] [FSTTCS'22]
Tolerant Bipartiteness Testing in Dense Graphs
with Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen
ICALP 2022: International Colloquium on Automata, Languages and Programming
HALG 2023: Highlights of Algorithms
[ArXiv] [ICALP]
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
[ArXiv] [RANDOM'21] [Conference Talk]
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
HALG 2022: Highlights of Algorithms
[ECCC] [RANDOM'21] [Conference Talk]
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
[ECCC] [ArXiv] [APPROX'21] [Conference Talk]
Hyperedge Estimation using Polylogarithmic Subset Queries
with Anup Bhattacharya, Arijit Bishnu, and Gopinath Mishra
Manuscript
[ArXiv]
On Triangle Estimation using Tripartite Independent Set Queries
with Anup Bhattacharya, Arijit Bishnu, and Gopinath Mishra
Theory of Computing Systems, 65: 1165 – 1192, 2021
ISAAC 2019: International Symposium on Algorithms and Computation
[ArXiv] [ISAAC'19] [Journal version]
On the Streaming Complexity of Fundamental Geometric Problems
with Arijit Bishnu, Gopinath Mishra, and Sandeep Sen
Manuscript
[ArXiv]

Analysis of Boolean functions

Testing isomorphism of Boolean functions over certain families of Abelian Groups
with Swarnalipa Datta, Chandrima Kayal, Manaswi Paraashar and Manmatha Roy
Submitted
Fourier Dimension of Boolean Function over Abelian Groups
with Swagato Sanyal, Swarnalipa Datta, and Sourav Chakraborty
Submitted
Linear isomorphism testing of Boolean functions with small approximate spectral norm
with Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy
Manuscript
[ArXiv]
On Fourier analysis of sparse Boolean functions over certain Abelian groups
with Pranjal Dutta, Swagato Sanyal, Swarnalipa Datta, and Sourav Chakraborty
Submitted

Computational Geometry

FPT Algorithms for Embedding into Low-Complexity Graphic Metrics
with Sudeshna Kolay and Gopinath Mishra
ACM Transactions on Computation Theory, 12(1): 1:1 – 1:41, 2020
ESA 2018: European Symposium on Algorithms
[ArXiv] [ESA'18] [Journal version]
Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set
with Jean-Daniel Boissonnat, Kunal Dutta, and Sudeshna Kolay
LATIN 2018: Latin American Theoretical Informatics Symposium
[HAL] [LATIN'18]
Uniformity of Point Samples in Metric Spaces Using Gap Ratio
with Arijit Bishnu, Sameer Desai, Mayank Goswami, and Subhabrata Paul
SIAM Journal on Discrete Mathematics, 31(3): 2138 – 2171, 2017
TAMC 2015: Conference on Theory and Applications of Models of Computation
[ArXiv] [TAMC'15] [Journal version]
A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations
with Jean-Daniel Boissonnat and Ramsay Dyer
ESA 2015: European Symposium on Algorithms
[ArXiv] [ESA'15]
Delaunay Stability via Perturbations
with Jean-Daniel Boissonnat and Ramsay Dyer
International Journal of Computational Geometry & Applications, 24(2): 125 – 152, 2014
[ArXiv] [HAL] [Journal version]

Misc. Algorithms & Combinatorics

Linear kernels for k-tuple and liar's domination in bounded genus graphs
with Arijit Bishnu, Kunal Dutta, and Subhabrata Paul
Discrete Applied Mathematics, 231: 67 – 77, 2017
[ArXiv] [Journal version]
On Subgraphs of Bounded Degeneracy in Hypergraphs
with Kunal Dutta
WG 2016: International Workshop on Graph-Theoretic Concepts in Computer Science
[WG'16]
(1, j)-set problem in graphs
with Arijit Bishnu, Kunal Dutta, and Subhabrata Paul
Discrete Mathematics, 339(10): 2215 – 2225, 2016
[ArXiv] [Journal version]