Rajesh Chitnis

View Scopus Profile

Rajesh Chitnis

Dr.

 https://orcid.org/0000-0002-6098-7770

Accepting PhD Students

PhD projects

streaming algorithms, graph algorithms and complexity, FPT algorithms

20142023

Research activity per year

Filter
Conference contribution

Search results

  • 2023

    How Does Fairness Affect the Complexity of Gerrymandering?

    Banerjee, S., Chitnis, R. & Lahiri, A., 30 May 2023, AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. Association for Computing Machinery (ACM), p. 2869-2871 3 p. (Proceedings of International Conference on Autonomous Agents and Multiagent Systems).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    File
    39 Downloads (Pure)

  • Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs

    Chen, X., Chitnis, R., Eades, P. & Wirth, A., 28 Jul 2023, Algorithms and Data Structures: 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings. Morin, P. & Suri, S. (eds.). Springer, p. 247-261 15 p. (Lecture Notes in Computer Science; vol. 14079).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • 2022

    Refined Lower Bounds for Nearest Neighbor Condensation

    Chitnis, R., 1 Apr 2022, Proceedings of The 33rd International Conference on Algorithmic Learning Theory. Dasgupta, S. & Haghtalab, N. (eds.). Proceedings of Machine Learning Research, p. 262-281 20 p. (Proceedings of Machine Learning Research; vol. 167).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File
    26 Downloads (Pure)

  • Tight Lower Bounds for Approximate & Exact k-Center in ℝd

    Chitnis, R. & Saurabh, N., 1 Jun 2022, 38th International Symposium on Computational Geometry (SoCG 2022). Schloss Dagstuhl, p. 1-15 15 p. 28. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 224).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File
    11 Downloads (Pure)
  • 2019

    FPT inapproximability of directed cut and connectivity problems

    Chitnis, R. & Feldmann, A. E., 1 Dec 2019, 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019). Jansen, B. M. P. & Telle, J. A. (eds.). Schloss Dagstuhl, 20 p. 8. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 148).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File
    1 Citation (Scopus)
    80 Downloads (Pure)

  • Towards a theory of parameterized streaming algorithms

    Chitnis, R. & Cormode, G., 1 Dec 2019, 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019). Jansen, B. M. P. & Telle, J. A. (eds.). Schloss Dagstuhl, 15 p. 7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 148).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File
    1 Citation (Scopus)
    90 Downloads (Pure)
  • 2018

    Algorithms and hardness results for nearest neighbor problems in bicolored point sets

    Banerjee, S., Bhore, S. & Chitnis, R., 13 Mar 2018, LATIN 2018 -Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Mosteiro, M. A., Bender, M. A. & Farach-Colton, M. (eds.). Springer Verlag, p. 80-93 (Lecture Notes in Computer Science ; vol. 10807).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    3 Citations (Scopus)

  • A tight lower bound for steiner orientation

    Chitnis, R. & Feldmann, A. E., 25 Apr 2018, Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Podolskii, V. V. & Fomin, F. V. (eds.). Springer Verlag, p. 65-77 13 p. (Lecture Notes in Computer Science ; vol. 10846 ).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File
    1 Citation (Scopus)
    120 Downloads (Pure)

  • Can we create large k-cores by adding few edges?

    Chitnis, R. & Talmon, N., 25 Apr 2018, Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Podolskii, V. V. & Fomin, F. V. (eds.). Springer Verlag, p. 78-89 11 p. (Lecture Notes in Computer Science ; vol. 10846).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File
    5 Citations (Scopus)
    150 Downloads (Pure)

  • Parameterized approximation algorithms for bidirected steiner network problems

    Chitnis, R., Feldmann, A. E. & Manurangsi, P., 1 Aug 2018, 26th European Symposium on Algorithms, (ESA 2018).. Bast, H., Herman, G. & Azar, Y. (eds.). Schloss Dagstuhl, 16 p. 20. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 112).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File
    5 Citations (Scopus)
    70 Downloads (Pure)
  • 2016

    Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams

    Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M. & Vorotnikova, S., 10 Jan 2016, Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. Krauthgamer, R. (ed.). Society for Industrial and Applied Mathematics (SIAM), p. 1326-1344 19 p. (The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File
    49 Citations (Scopus)
    129 Downloads (Pure)

  • Tight bounds for Gomory-Hu-like cut counting

    Chitnis, R., Kamma, L. & Krauthgamer, R., 28 Sept 2016, Graph-Theoretic Concepts in Computer Science : 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers. Heggernes, P. (ed.). Springer Verlag, p. 133-144 (Lecture Notes in Computer Science ; vol. 9941).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    2 Citations (Scopus)
  • 2015

    Brief announcement: New streaming algorithms for parameterized maximal matching & beyond

    Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M. & Monemizadeh, M., 13 Jun 2015, SPAA 2015: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery , p. 56-58 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    4 Citations (Scopus)

  • Parameterized Streaming: Maximal Matching and Vertex Cover

    Chitnis, R., Cormode, G., Hajiaghayi, M. & Monemizadeh, M., 4 Jan 2015, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015). Indyk, P. (ed.). Association for Computing Machinery (ACM), p. 1234-1251 18 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    31 Citations (Scopus)
  • 2014

    A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

    Chitnis, R. H., Esfandiari, H., Hajiaghayi, M. T., Khandekar, R., Kortsarz, G. & Seddighin, S., 3 Dec 2014, Parameterized and Exact Computation : 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers. Cygan, M. & Heggernes, P. (eds.). Springer Verlag, p. 159-171 (Lecture Notes in Computer Science ; vol. 8894).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    5 Citations (Scopus)

  • Tight bounds for planar strongly connected steiner subgraph with fixed number of terminals (and extensions)

    Chitnis, R., Hajiaghayi, M. & Marx, D., 5 Jan 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Chekuri, C. (ed.). Association for Computing Machinery , p. 1782-1801 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    19 Citations (Scopus)