Papers by topics
Papers by topics
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
[HAL]
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
Comment: The conference version of this paper that appeared in SoCG'18 was titled ``Local Criteria for Triangulation of Manifolds''
[ArXiv] [SoCG'18] [Journal version]
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]
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]
An elementary approach to tangent space variation on Riemannian submanifolds
with Jean-Daniel Boissonnat and Ramsay Dyer
Manuscript
Comment: Older version was titled ``Tangent space variation on submanifolds''
[ArXiv]
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]
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
Comment: Also see INRIA Research Reports RR-8276 and RR-8273
[SoCG'12]
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
Comment: Also see Chapters 3 and 4 from my Ph.D. Thesis
[HAL] [SoCG'10] [Journal version]
Covering Orthogonal Polygons with Orthogonal Line Segments
with Buddha Dev Das, Chandrima Kayal, Sudeshna Kolay and Soumi Nandi
Manuscript
About almost covering subsets of the hypercube
with Chandrima Kayal and Soumi Nandi
Submitted
[ArXiv]
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]
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]
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]
No Infinite (p,q)-Theorem for Piercing Compact Convex Sets with Lines in R3
with Sutanoya Chakraborty
Submitted
[ArXiv]
A Geometric Proof of the Infinite (p,q)-Theorem for Hyperplane Piercing
with Sutanoya Chakraborty and Soumi Nandi
Submitted
[ArXiv]
Dimension Independent Helly Theorem for Lines and Flats
with Sutanoya Chakraborty and Soumi Nandi
Submitted
[ArXiv]
Finite k-Transversals of Infinite Families of Fat Convex Sets
with Sutanoya Chakraborty and Soumi Nandi
Submitted
[ArXiv]
Colorful Helly Theorem for Piercing Boxes with Multiple Points
with Sourav Chakraborty and Soumi Nandi
[ArXiv]
Discrepancy of Sparse Geometric Set Systems with Low Shallow Cell Complexity
with Kunal Dutta
[ArXiv]
Stabbing boxes with finitely many axis-parallel lines and flats
with Sutanoya Chakraborty and Soumi Nandi
Discrete Mathematics, 348 (2): 114269, 2025
[ArXiv] [Journal]
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]
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]
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 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]
Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression
with Debabrota Basu, Sourav Chakraborty, Debarshi Chanda, Buddha Dev Das, and Arnab Ray
Submitted
[ArXiv]
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
with Sourav Chakraborty, Eldar Fischer, Amit Levi, Gopinath Mishra and Sayantan Sen
STOC 2025: Annual ACM Symposium on Theory of Computing
Comment: Featured in Oded Goldreich's Choices
[ArXiv] [ECCC] [STOC'25]
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
Comment: Featured in Oded Goldreich's Choices
[ECCC] [ArXiv] [COLT'23]
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, 71(2): 1153 – 1170, 2025
RANDOM 2022: International Conference on Randomization and Computation
HALG 2023: Highlights of Algorithms
[ArXiv] [RANDOM'22] [Journal version]
Optimal Non-Adaptive Algorithm for Edge Estimation
with Arijit Bishnu, Debarshi Chanda, Buddha Dev Das and Gopinath Mishra
Submitted
Improved Streaming Algorithm for Klee's Measure Problem and Generalizations
with Sourav Chakraborty, Kuldeep S. Meel, Mridul Nandi, Soumit Pal and N. V. Vinodchandran
APPROX 2024: International Conference on Approximation Algorithms for Combinatorial Optimization Problems
[APPROX'24]
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
Comment: Featured in Oded Goldreich's Choices
[ArXiv] [STACS'22] [Journal version] [Short Talk]
A new concentration inequality for ordered hypergraphs
with Anup Bhattacharya, Arijit Bishnu and Gopinath Mishra
Manuscript
Near Uniform Triangle Sampling Over Adjacency List Graph Streams
with Arijit Bishnu, Gopinath Mishra and Sayantan Sen
Submitted
[ArXiv]
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
Comment: An extended abstract of this paper that appeared in COCOON'20 was titled ``Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams''
[ArXiv] [COCOON'20] [Journal]
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
Comment: An extended abstract of this paper that appeared in ISAAC'18 was titled ``Parameterized Query Complexity of Hitting Set using Stability of Sunflowers''
[ArXiv] [ISAAC'18] [Journal version]
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]
No Vector Space? No Problem: Lifting Boolean Function Results to Abelian Groups
with Swagato Sanyal, Swarnalipa Datta and Sourav Chakraborty
Submitted
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
with Swarnalipa Datta, Chandrima Kayal, Manaswi Paraashar and Manmatha Roy
Submitted
Testing Fourier Sparsity via Implicit Sensing
with Subhamoy Maitra and Manmatha Roy
Submitted
Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
with Swarnalipa Datta, Chandrima Kayal, Manaswi Paraashar and Manmatha Roy
Submitted
Price of Parsimony: Complexity of Fourier Sparsity Testing
with Manmatha Ray
NeurIPS 2025: Annual Conference on Neural Information Processing Systems
Testing Isomorphism of Boolean Functions over Finite Abelian Groups
with Swarnalipa Datta, Chandrima Kayal, Manaswi Paraashar and Manmatha Roy
RANDOM 2025: International Conference on Randomization and Computation
[ArXiv] [RANDOM'25]
On Fourier analysis of sparse Boolean functions over certain Abelian groups
with Pranjal Dutta, Swagato Sanyal, Swarnalipa Datta and Sourav Chakraborty
MFCS 2024: International Symposium on Mathematical Foundations of Computer Science
[ArXiv] [MFCS'24]
A Hanani-Tutte Theorem for Cycles
with Sutanoya Chakraborty
Manuscript
[ArXiv]
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]
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]
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]