Papers

(To see the list categorized by subjects click here)

1. A Hanani-Tutte Theorem for Cycles
   with Sutanoya Chakraborty
   Submitted
   [ArXiv]

2. Testing isomorphism of Boolean functions over certain families of Abelian Groups
   with Swarnalipa Datta, Chandrima Kayal, Manaswi Paraashar and Manmatha Roy
   Submitted

3. 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

4. Fourier Dimension of Boolean Function over Abelian Groups
   with Swagato Sanyal, Swarnalipa Datta, and Sourav Chakraborty
   Submitted

5. Countably Colorful Hyperplane Transversal
   with Sutanoya Chakraborty and Soumi Nandi
   Submitted
   [ArXiv]

6. Heterochromatic Geometric Transversals of Convex sets
   with Sutanoya Chakraborty and Soumi Nandi
   Submitted
   [ArXiv]

7. 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

8. Stabbing boxes with finitely many axis-parallel lines and flats
   with Sutanoya Chakraborty and Soumi Nandi
   Submitted
   [ArXiv]

9. Dimension Independent Helly Theorem for Lines and Flats
   with Sutanoya Chakraborty and Soumi Nandi
   Submitted
   [ArXiv]

10. Linear isomorphism testing of Boolean functions with small approximate spectral norm
    with Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy
    Submitted
    [ArXiv]

11. On higher multiplicity hyperplane and polynomial covers for symmetry preserving subsets of the hypercube
    with Chandrima Kayal, Soumi Nandi, and S. Venkitesh
    Submitted
    [ArXiv]

12. A new concentration inequality for ordered hypergraphs
    with Arijit Bishnu and  Gopinath Mishra
    Manuscript

13. 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

14. Near Uniform Triangle Sampling Over Adjacency List Graph Streams
    with Arijit Bishnu, Gopinath Mishra, and Sayantan Sen
    Submitted

15. Discrepancy of Sparse Geometric Set Systems with Low Shallow Cell Complexity
    with Kunal Dutta
    Submitted
    [ArXiv]

16. Colorful Helly Theorem for Piercing Boxes with Multiple Points
    with Sourav Chakraborty and Soumi Nandi
    [ArXiv]

17. 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

18. On the Complexity of Triangle Counting using Emptiness Queries
    with Arijit Bishnu and  Gopinath Mishra
    RANDOM 2023: International Conference on Randomization and Computation
    [ArXiv] [RANDOM'23] [Short Talk]

19. Testing of Index-Invariant Properties in the Huge Object Model
    COLT 2023: Annual Conference on Learning Theory
    with Sourav Chakraborty, Eldar Fischer, Gopinath Mishra, and Sayantan Sen
    [ECCC] [ArXiv] [COLT'23]
    
    Comment: Featured in Oded Goldreich's Choices

20. 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''

21. 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''

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

23. Local Criteria for Triangulating General Manifolds
    with Jean-Daniel Boissonnat, Ramsay Dyer, and Mathijs Wintraecken
    Discrete & Computational Geometry, 69: 156 – 191, 2023
    SoCG 2018: Symposium on Computational Geometry
    [ArXiv] [SoCG'18] [Journal version]
    
    Comments: The conference version of this paper that appeared in SoCG'18 was titled ``Local Criteria for Triangulation of Manifolds''

24. 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]

25. 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]

26. 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]

27. 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]

28. 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]

29. 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]

30. 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]

31. 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]

32. 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]

33. 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]

34. 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]

35. 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]

36. 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]

37. Hyperedge Estimation using Polylogarithmic Subset Queries
    with Anup Bhattacharya, Arijit Bishnu, and Gopinath Mishra
    Manuscript
    [ArXiv]

38. Delaunay simplices in diagonally distorted lattices
    with Aruni Choudhary
    Computational Geometry, 81: 33 – 44, 2019
    [ArXiv] [Journal version]

39. 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]

40. A Simple Proof of Optimal Epsilon Nets
    with Kunal Dutta and Nabil H. Mustafa
    Combinatorica, 38(5): 1269 – 1277, 2018
    [HAL] [Journal version]

41. Delaunay Triangulations of Manifolds
    with Jean-Daniel Boissonnat and Ramsay Dyer
    Foundations of Computational Mathematics, 18(2): 399 – 431, 2018
    [ArXiv] [HAL] [Journal version]

42. 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]

43. 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]

44. On the Streaming Complexity of Fundamental Geometric Problems
    with Arijit Bishnu, Gopinath Mishra, and Sandeep Sen
    Manuscript
    [ArXiv]

45. 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]

46. 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]

47. 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]

48. 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]

49. A New Asymmetric Correlation Inequality for Gaussian Measure
    with Kunal Dutta and Nabil H. Mustafa
    Manuscript
    [HAL]

50. 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]

51. On Subgraphs of Bounded Degeneracy in Hypergraphs
    with Kunal Dutta
    WG 2016: International Workshop on Graph-Theoretic Concepts in Computer Science
    [WG'16]

52. (1, j)-set problem in graphs
    with Arijit Bishnu, Kunal Dutta, and Subhabrata Paul
    Discrete Mathematics, 339(10): 2215 – 2225, 2016
    [ArXiv] [Journal version]

53. An elementary approach to tangent space variation on Riemannian submanifolds
    with Jean-Daniel Boissonnat and Ramsay Dyer
    Manuscript
    [ArXiv]
    
    Comments: Older version was titled ``Tangent space variation on submanifolds''

54. 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]

55. 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]

56. Constructing Intrinsic Delaunay Triangulations of Submanifolds
    with Jean-Daniel Boissonnat and Ramsay Dyer
    INRIA Research Report RR-8273, 2013
    [ArXiv] [HAL]

57. 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]

58. 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]

59. 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 

60. 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]

61. Triangulating Smooth Submanifolds with Light Scaffolding
    with Jean-Daniel Boissonnat
    Mathematics in Computer Science, 4(4): 431 – 461, 2010
    [HAL] [Journal version]

62. 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