My research interests are in several areas related to combinatorics (especially probabilistic combinatorics) and its applications to theoretical computer science. Some of my early work was on using combinatorial ideas to solve problems in algebra, particularly representation theory. My PhD was on random graphs, digraphs and probabilistic and extremal combinatorics. Most of my work since then has been on aspects of randomization in computational geometry, relating to VC dimension, shallow cell complexity, Delaunay triangulations, etc. Recently I have also become interested in topological data analysis.

Submitted


  • K. Dutta: On Limit Constants in Last Passage Percolation in Transitive Tournaments. ArXiv

  • K. Dutta, A. Ghosh: Sparse Geometric Set Systems and the Beck Fiala Conjecture. ArXiv

    • Journals (Area-wise)

      Discrete and Computational Geometry


      1. S. Arya, J.-D. Boissonnat, K. Dutta, M. Lotz: Dimensionality Reduction for k-Distance Applied to Persistent Homology.
        Journal of Applied and Computational Topology, 2021, 5, pg. 671-691.

      2. J-D. Boissonnat, O. Devillers, K. Dutta, M. Glisse: Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets.
        Discrete and Computational Geometry, 2020, 66 pp. 236-268.

      3. K. Dutta, A. Ghosh, B. Jartoux, N. Mustafa: Shallow packings, semialgebraic set systems, Macbeath regions and polynomial partitioning.
        Discrete and Computational Geometry 2019, 61(4) pp. 756-777.         HAL

      4. N. H. Mustafa, K. Dutta, A. Ghosh: A simple proof of optimal epsilon nets.
        Combinatorica 2018, 38 pp. 1269-1277. HAL

      5. K. Dutta, E. Ezra, A. Ghosh: Two Proofs of Shallow Packings.
        Discrete and Computational Geometry 2016, 56(4), pp 910-939. ArXiv.

        6. Probabilistic Method and Random Graphs


      6. K. Dutta, C. R. Subramanian: On Induced Paths, Holes and Trees in Random Graphs.
        SIAM Journal of Discrete Mathematics. 2023, 37(1)

      7. K. Dutta, C. R. Subramanian: Improved bounds on induced acyclic subgraphs in random digraphs.
        SIAM Journal of Discrete Mathematics. 2016, 30(3), 1848-1865.

      8. A. Bishnu, K. Dutta, A. Ghosh, S. Paul: (1,j)-set problem in graphs.
        Discrete Mathematics (Oct 2016) 339(10), pp 2515-2525. ArXiv.

      9. J. Cooper, K. Dutta, D. Mubayi: Counting independent sets in hypergraphs.
        Combinatorics, Probability and Computing. 23(4) (2014) 539-550. ArXiv.

      10. K. Dutta, D. Mubayi, C. R. Subramanian: New lower bounds for the independence number of sparse graphs and hypergraphs.
        SIAM Journal of Discrete Mathematics (2012) 26 (3) 1134-1147. ArXiv.

      11. K. Dutta, C. R. Subramanian: Induced acyclic tournaments in random digraphs: Sharp concentration, thresholds and algorithms.
        Discussiones Mathematicae Graph Theory 34 (2014) 467-495. Online.

        12. Combinatorics in Algebra and Representation Theory


      12. K. Dutta, A. Prasad: Combinatorics of finite abelian groups and Weil representations.
        Pacific Journal of Mathematics. 275(2) (2015) 295-324. ArXiv.

      13. W. Calvert, K. Dutta, A. Prasad: Degenerations and orbits of tuples and subgroups in an Abelian group.
        Journal of Group Theory 16 (2013) 221-233. ArXiv.

      14. K. Dutta, A. Prasad: Degenerations and orbits in finite abelian groups.
        Journal of Combinatorial Theory, Series A 118 (2011) 1685-1694. ArXiv.

    Conferences

    1. J.-D. Boissonnat, K. Dutta: A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels.
      European Symposium on Algorithms 2024, September 2- September 4, 2024, London, U.K.

    2. J.-D. Boissonnat, K. Dutta, S. Dutta, S. Pritam: On Edge Collapse of Random Simplicial Complexes.
      40th Symposium on Computational Geometry 2024, June 11- June 14, 2024, Athens, Greece.

    3. P. Shukla, G. R. Gupta, K. Dutta: DiffRed: Dimensionality Reduction Guided by Stable Rank.
      International Conference on Artificial Intelligence and Statistics (AISTATS) 2024, May 02- May 04, 2024, Valencia, Spain.

    4. K. Dutta, A. Ghosh, S. Moran: Uniform Brackets, Containers and Combinatorial Macbeath Regions.
      13th Innovations in Theoretical Computer Science (ITCS) 2022, January 31- February 3, 2022, Berkeley, CA, USA.

    5. S. Arya, J.-D. Boissonnat, K. Dutta, M. Lotz: Dimensionality Reduction for k-Distance Applied to Persistent Homology.
      36th International Symposium on Computational Geometry (SoCG) 2020.

    6. J-D. Boissonnat, O. Devillers, K. Dutta, M. Glisse: Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets.
      European Symposium on Algorithms, (ESA) 2019 Munich, Germany.

    7. J-D. Boissonnat, K. Dutta, A. Ghosh, S. Kolay: Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set.
      Latin American Theoretical Informatics, Buenos Aires, Argentina, LATIN 2018.

    8. K. Dutta, C. R. Subramanian: On induced paths, holes and trees in random graphs.
      Meeting on Analytic Algorithms and Combinatorics, New Orleans (USA), ANALCO 2018.

    9. J.-D. Boissonnat, K. Dutta, A. Ghosh, S. Kolay: Kernelization of the Subset General Position problem in Geometry.
      42nd International Symposium on Mathematical Foundations of Computer Science, Aalborg (Denmark), MFCS 2017.

    10. K. Dutta, A. Ghosh, B. Jartoux, N. Mustafa: Shallow packings, semialgebraic set systems, Macbeath regions and polynomial partitioning.
      Proc. 33rd International Symposium on Computational Geometry (SoCG), 2017.
      (Invited to Discrete & Computational Geometry for the Special Issue of SoCG-17).

    11. K. Dutta, A. Ghosh: On Subgraphs of Bounded Degeneracy in Hypergraphs
      42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2016), June 2016, Istanbul, Turkey.

    12. K. Dutta, E. Ezra, A. Ghosh: Two Proofs for Shallow Packings.
      Proceedings of SoCG 2015 (31st International Symposium on Computational Geometry), Eindhoven, Netherlands, June 2015.

    13. K. Dutta, C. R. Subramanian: On induced acyclic subgraphs in sparse random digraphs,
      Proceedings of EuroComb'11 (European Conference on Combinatorics, Graph Theory and Applications), Budapest, Hungary, August 2011.

    14. K. Dutta, C. R. Subramanian: Induced acyclic subgraphs in random digraphs: Improved bounds.
      Proceedings of AofA'10 (21st International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms), Vienna, Austria, June 2010.

    15. K. Dutta, C. R. Subramanian: Largest Induced Acyclic Tournament in Random Digraphs: A 2-point concentration.
      Proceedings of LATIN 2010 (9th Latin American Theoretical Informatics Symposium), Oaxaca, Mexico, April 2010.