Papers

(For a subject-wise list of papers with links, click here)

• Robust Certification of Spectral Norm of Boolean Function
  with Manmatha Roy
  Manuscript

• Unlocking Fractional Moments in Delphic Set Streams
  with Aranya Kumar Bal, Sourav Chakraborty, and Rudrayan Kundu
  Manuscript

• From Decision to Random Certificates: Faster Edge Estimation with Independent Set Queries
  with Debarshi Chanda, Buddha Dev Das, and Gopinath Mishra
  Submitted

• Hunting the Spectre of Heavy Fourier Biases
  with Subhamoy Maitra and Manmatha Roy
  Submitted

• Distribution Free Fourier Sparsity Testing
  with Manmatha Roy
  Submitted

• A Dense Coset Decomposition Theorem for Boolean Functions with Bounded Spectral Norm
  with Manmatha Roy
  Submitted

• Counting Triangles in Graph Streams with Repeatable and Forgettable Edges
  with Sourav Chakraborty, Debarshi Chanda, Pavan Aduri, Chhaya Trehan, and Vinodchandran Variyam
  Submitted

• No Infinite (p,q)-Theorem for Piercing Compact Convex Sets with Lines in R3
  with Sutanoya Chakraborty
  Submitted

• From Cubes to Groups: Fourier Structure, Character Decision Tree, and Learning on Abelian Groups
  with Swagato Sanyal, Swarnalipa Datta, and Sourav Chakraborty
  Submitted

• Structure of sparse Boolean functions over Abelian groups, and its application to testing
  with Pranjal Dutta, Swagato Sanyal, Swarnalipa Datta, and Sourav Chakraborty

• Optimal Non-Adaptive Algorithm for Edge Estimation
  with Arijit Bishnu, Debarshi Chanda, Buddha Dev Das, and Gopinath Mishra
  Submitted

• 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

• Covering Orthogonal Polygons with Orthogonal Line Segments
  with Buddha Dev Das, Chandrima Kayal, Sudeshna Kolay, and Soumi Nandi
  Manuscript

• A Hanani-Tutte Theorem for Cycles
  with Sutanoya Chakraborty
  Submitted

• About almost covering subsets of the hypercube
  with Chandrima Kayal and Soumi Nandi
  Submitted

• A geometric proof of the infinite (p,q)-theorem for hyperplane piercing
  with Sutanoya Chakraborty and Soumi Nandi
  Submitted

• Finite k-Transversals of Infinite Families of Fat Convex Sets
  with Sutanoya Chakraborty and Soumi Nandi
  Submitted

• 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

• Helly theorem for affine spaces without dimensions
  with Sutanoya Chakraborty and Soumi Nandi
  Submitted

• Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
  with Swarnalipa Datta, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy
  Submitted

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

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

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

• Discrepancy of Sparse Geometric Set Systems with Low Shallow Cell Complexity
  with Kunal Dutta
  Manuscript

• Testing Fourier Sparsity via Implicit Sensing
  with Subhamoy Maitra and Manmatha Roy
  ICLR 2026: International Conference on Learning Representations

• Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
  with Swarnalipa Datta, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy
  STACS 2026: 43rd International Symposium on Theoretical Aspects of Computer Science

• Colorful two-piercing theorem for boxes
  with Sourav Chakraborty and Soumi Nandi
  Discrete Applied Mathematics, 382: 301 – 309, 2026

• 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

• 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

• 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

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

• 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

• 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

• 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

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

• 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

• 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

• 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

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

• 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

• 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

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

• 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

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

• 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

• 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

• 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

• Grid Obstacle Representation of Graphs
  with Arijit Bishnu, Gopinath Mishra, Rogers Mathew, and Subhabrata Paul
  Discrete Applied Mathematics, 296: 39 – 51, 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

• 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

• 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

• Hyperedge Estimation using Polylogarithmic Subset Queries
  with Anup Bhattacharya, Arijit Bishnu, and Gopinath Mishra
  Manuscript

• Delaunay simplices in diagonally distorted lattices
  with Aruni Choudhary
  Computational Geometry, 81: 33 – 44, 2019

• 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
  SoCG 2017: Symposium on Computational Geometry

• A Simple Proof of Optimal Epsilon Nets
  with Kunal Dutta and Nabil H. Mustafa
  Combinatorica, 38(5): 1269 – 1277, 2018

• Delaunay Triangulations of Manifolds
  with Jean-Daniel Boissonnat and Ramsay Dyer
  Foundations of Computational Mathematics, 18(2): 399 – 431, 2018

• 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

• 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

• On the Streaming Complexity of Fundamental Geometric Problems
  with Arijit Bishnu, Gopinath Mishra, and Sandeep Sen
  Manuscript

• 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

• 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

• Only distances are required to reconstruct submanifolds
  with Jean-Daniel Boissonnat, Ramsay Dyer, and Steve Y. Oudot
  Computational Geometry, 66: 32 – 67, 2017

• 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

• A New Asymmetric Correlation Inequality for Gaussian Measure
  with Kunal Dutta and Nabil H. Mustafa
  Manuscript

• Two proofs for Shallow Packings
  with Kunal Dutta and Esther Ezra
  Discrete & Computational Geometry, 56(4): 910 – 939, 2016
  SoCG 2015: Symposium on Computational Geometry

• On Subgraphs of Bounded Degeneracy in Hypergraphs
  with Kunal Dutta
  WG 2016: International Workshop on Graph-Theoretic Concepts in Computer Science

• (1, j)-set problem in graphs
  with Arijit Bishnu, Kunal Dutta, and Subhabrata Paul
  Discrete Mathematics, 339(10): 2215 – 2225, 2016

• An elementary approach to tangent space variation on Riemannian submanifolds
  with Jean-Daniel Boissonnat and Ramsay Dyer
  Manuscript

• A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations
  with Jean-Daniel Boissonnat and Ramsay Dyer
  ESA 2015: European Symposium on Algorithms

• Delaunay Stability via Perturbations
  with Jean-Daniel Boissonnat and Ramsay Dyer
  International Journal of Computational  Geometry & Applications, 24(2): 125 – 152, 2014

• Constructing Intrinsic Delaunay Triangulations of Submanifolds
  with Jean-Daniel Boissonnat and Ramsay Dyer
  INRIA Research Report RR-8273, 2013

• The Stability of Delaunay Triangulations
  with Jean-Daniel Boissonnat and Ramsay Dyer
  International Journal of Computational  Geometry & Applications, 23(4-5): 303 – 334, 2013

• Piecewise linear reconstruction and meshing of submanifolds of Euclidean space
  PhD Thesis, INRIA Sophia Antipolis - Méditerranée, May 2012
  Supervisor: Jean-Daniel Boissonnat

• Stability of Delaunay-type Structures for Manifolds
  with Jean-Daniel Boissonnat and Ramsay Dyer
  SoCG 2012: Symposium on Computational Geometry

• Equating the Witness and Restricted Delaunay Complexes
  with Jean-Daniel Boissonnat, Ramsay Dyer, and Steve Y. Oudot
  EWCG 2012: European Workshop on Computational Geometry

• Triangulating Smooth Submanifolds with Light Scaffolding
  with Jean-Daniel Boissonnat
  Mathematics in Computer Science, 4(4): 431 – 461, 2010

• Manifold Reconstruction Using Tangential Delaunay Complexes
  with Jean-Daniel Boissonnat
  Discrete & Computational Geometry, 51(1): 221 – 267, 2014
  SoCG 2010: Symposium on Computational Geometry