Dr Rajesh Chitnis

Dr Rajesh Chitnis

School of Computer Science
Lecturer of Computer Science

Contact details

Address
School of Computer Science
University of Birmingham
Edgbaston
Birmingham
B15 2TT
UK

Dr Chitnis received his PhD in Computer Science from University of Maryland, College Park, USA in 2014. Afterwards, he was a postdoctoral fellow at Weizmann Institute of Science, Israel (2014-17) and at the University of Warwick, UK (2017-19) before joining the University of Birmingham in October 2019.

Please follow the link below to find out more about Rajesh's work:

Dr Rajesh Chitnis-personal homepage

Qualifications

  • PhD in Computer Science, University of Maryland College Park, 2014

  • MSc in Computer Science, University of Maryland, College Park, 2013

  • BSc in Mathematics and Computer Science, Chennai Mathematical Institute, India, 2010

Teaching

  • Logic and Computation

Research

  • Parameterized Algorithms and Complexity
  • Streaming Algorithms
  • Algorithmic Graph Theory

Publications

Recent publications

Article

Chitnis, R, Feldmann, AE, Hajiaghayi, M & Marx, D 2020, 'Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)', SIAM Journal on Computing, vol. 49, no. 2, pp. 318–364. https://doi.org/10.1137/18M122371X

Chitnis, R, Feldmann, AE & Suchý, O 2019, 'A tight lower bound for planar Steiner Orientation', Algorithmica, vol. 81, no. 8, pp. 3200-3216. https://doi.org/10.1007/s00453-019-00580-x

Chitnis, R, Esfandiari, H, Hajiaghayi, MT, Khandekar, R, Kortsarz, G & Seddighin, S 2017, 'A tight algorithm for Strongly Connected Steiner Subgraph on two terminals with demands', Algorithmica, vol. 77, no. 4, pp. 1216-1239. https://doi.org/10.1007/s00453-016-0145-8

Chitnis, R, Fomin, FV, Lokshtanov, D, Misra, P, Ramanujan, MS & Saurabh, S 2017, 'Faster exact algorithms for some terminal set problems', Journal of Computer and System Sciences, vol. 88, no. September, pp. 195-207. https://doi.org/10.1016/j.jcss.2017.04.003

Chitnis, R, Egri, L & Marx, D 2017, 'List H-coloring a graph by removing few vertices', Algorithmica, vol. 78, no. 1, pp. 110-146. https://doi.org/10.1007/s00453-016-0139-6

Chitnis, R, Cygan, M, Hajiaghayi, M, Pilipczuk, M & Pilipczuk, M 2016, 'Designing FPT algorithms for cut problems using randomized contractions', SIAM Journal on Computing, vol. 45, no. 4, pp. 1171-1229. https://doi.org/10.1137/15M1032077

Chitnis, R, Fomin, FV & Golovach, PA 2016, 'Parameterized complexity of the anchored k-core problem for directed graphs', Information and Computation, vol. 247, pp. 11-22. https://doi.org/10.1016/j.ic.2015.11.002

Conference contribution

Chitnis, R & Feldmann, AE 2019, FPT inapproximability of directed cut and connectivity problems. in BMP Jansen & JA Telle (eds), 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019)., 8, Leibniz International Proceedings in Informatics, LIPIcs, vol. 148, Schloss Dagstuhl, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Munich, Germany, 11/09/19. https://doi.org/10.4230/LIPIcs.IPEC.2019.8

Chitnis, R & Cormode, G 2019, Towards a theory of parameterized streaming algorithms. in BMP Jansen & JA Telle (eds), 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019)., 7, Leibniz International Proceedings in Informatics, LIPIcs, vol. 148, Schloss Dagstuhl, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Munich, Germany, 11/09/19. https://doi.org/10.4230/LIPIcs.IPEC.2019.7

Chitnis, R & Feldmann, AE 2018, A tight lower bound for steiner orientation. in VV Podolskii & FV Fomin (eds), Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Lecture Notes in Computer Science , vol. 10846 , Springer Verlag, pp. 65-77, 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russian Federation, 6/06/18. https://doi.org/10.1007/978-3-319-90530-3_7

Banerjee, S, Bhore, S & Chitnis, R 2018, Algorithms and hardness results for nearest neighbor problems in bicolored point sets. in MA Mosteiro, MA Bender & M Farach-Colton (eds), LATIN 2018 -Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Lecture Notes in Computer Science , vol. 10807, Springer Verlag, pp. 80-93, 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018, Buenos Aires, Argentina, 16/04/18. https://doi.org/10.1007/978-3-319-77404-6_7

Chitnis, R & Talmon, N 2018, Can we create large k-cores by adding few edges? in VV Podolskii & FV Fomin (eds), Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Lecture Notes in Computer Science , vol. 10846, Springer Verlag, pp. 78-89, 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russian Federation, 6/06/18. https://doi.org/10.1007/978-3-319-90530-3_8

Chitnis, R, Feldmann, AE & Manurangsi, P 2018, Parameterized approximation algorithms for bidirected steiner network problems. in H Bast, G Herman & Y Azar (eds), 26th European Symposium on Algorithms, (ESA 2018).., 20, Leibniz International Proceedings in Informatics, LIPIcs, vol. 112, Schloss Dagstuhl, 26th European Symposium on Algorithms, ESA 2018, Helsinki, Finland, 20/08/18. https://doi.org/10.4230/LIPIcs.ESA.2018.20

Chitnis, R, Cormode, G, Esfandiari, H, Hajiaghayi, M, McGregor, A, Monemizadeh, M & Vorotnikova, S 2016, Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. in R Krauthgamer (ed.), Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings, Society for Industrial and Applied Mathematics (SIAM), pp. 1326-1344, Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, United States, 10/01/16. https://doi.org/10.1137/1.9781611974331.ch92

Chitnis, R, Kamma, L & Krauthgamer, R 2016, Tight bounds for Gomory-Hu-like cut counting. in P Heggernes (ed.), Graph-Theoretic Concepts in Computer Science : 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers. Lecture Notes in Computer Science , vol. 9941, Springer Verlag, pp. 133-144, 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016, Istanbul, Turkey, 22/06/16. https://doi.org/10.1007/978-3-662-53536-3_12

View all publications in research portal