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

  • Journals

      Discrete and Computational Geometry


      1. J-D. Boissonnat, O. Devillers, K. Dutta, M. Glisse: Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets.
        Discrete and Computational Geometry (to appear).

      2. K. Dutta, A. Ghosh, B. Jartoux, N. Mustafa: Shallow packings, semialgebraic set systems, Macbeath regions and polynomial partitioning.
        Discrete & Computational Geometry for the Special Issue of SoCG-17, 2019.
        HAL

      3. N. H. Mustafa, K. Dutta, A. Ghosh: A simple proof of optimal epsilon nets.
        Combinatorica . (Online since: June 2017) DOI: 10.1007/s00493-017-3564-5 HAL

      4. K. Dutta, E. Ezra, A. Ghosh: Two Proofs of Shallow Packings.
        Discrete and Computational Geometry (Special Issue, SoCG 2015, Editors: Lars Arge and Janos Pach) December 2016, Volume 56, Issue 4, pp 910-939. ArXiv.

      Probabilistic Method and Random Graphs


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

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

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

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

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

      Combinatorics in Algebra and Representation Theory


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

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

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

    Conferences

    1. 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, (to appear).

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

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

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

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

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

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

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

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

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

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