Krishnamoorthy Dinesh

About

Hello ! I am an Assistant Professor in the Computer Science and Engineering department of Indian Institute of Technology Palakkad.

Prior to joining IIT Palakkad, I was a Post Doctoral Fellow at the Institute of Theoretical Computer Science and Communications (2019-2021) of The Chinese University of Hong Kong working with Andrej Bogdanov. Before joining CUHK, I was a visiting student at the Faculty of Computer Science, Technion - Israel Institute of Technology hosted by Yuval Filmus.

I completed my doctoral degree from the Dept. of Computer Science and Engineering, IIT Madras (2013-2019) advised by Jayalal Sarma. I completed my masters degree from CSE, IIT Madras (2011-2013) advised by Jayalal. Earlier, I did my undergraduate degree at the Dept. of CSE, NIT Calicut (2007-2011) under K Muralikrishnan

Teaching

Regular courses

(Jan-May 2025) CS5647 Communication Complexity
(Jan-May 2025) CS5634 Computational Algebra and Number Theory
(Aug-Nov 2024) CS3050 Theory of Computation

(Jan-May 2024) CS5616 Computational Complexity
(Jan-May 2024) CS5638 Quantum Computing (co-taught with Srimanta Bhattacharya)

(Aug-Nov 2023) CS5017/CS3050 Theory of Computation
(Aug-Nov 2023) CS3110 Operating Systems Lab (co-taught with Jasine Babu)

(Jan-May 2023) CS5616 Computational Complexity
(Jan-May 2023) CS2180 Artificial Intelligence Lab (co-taught with Krithika R)

(Aug-Nov 2022) CS5017/CS3050 Theory of Computation
(Aug-Nov 2022) CS5107 Programming Lab (co-taught with Deepak R)

(Jan-May 2022) CS5616 Computational Complexity
(Mar-Jun 2022) CS1020 Introduction to Programming (lab)

Contact/Reading courses

(Aug-Nov 2022 Reading) CS6601 Advanced Computational Complexity
(Jun-Jul 2022 Contact) CS1020 Introduction to Programming (contact mode)

For courses handled as teaching assistant, see this page.

Research Interests

Circuit Complexity Theory, Complexity measures on Boolean Functions

Research Work [arXiv][DBLP]

• Almost-catalytic Computation
  Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Deep Rai and Jayalal Sarma
  [Manuscript]
• Bounded Simultaneous Messages
  Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan and Sruthi Sekhar
  (appeared in FSTTCS 2023 | slides)
  [Full version] [Conference] [Video of the talk @ FSTTCS 2023]
• Classical simulation of one-query quantum distinguishers
  Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh and John C.S. Lui
  (appeared in RANDOM 2023 | slides )
  [Full version] [Conference] [Video of the talk @ RANDOM 2023]
• On Quantum versus Classical query complexity
  Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Tsun Ming Cheung and Krishnamoorthy Dinesh
  [Manuscript]
• Bounded Indistinguishability for Simple Sources
  Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan and Akshayaram Srinivasan (appeared in ITCS 2022 |slides, slides (by Yuval F) )
  [Full version] [Conference] [Video of the talk @ ITCS 2022]
• On Pure Space vs Catalytic Space
  Sagar Bisoyi, Krishnamoorthy Dinesh and Jayalal Sarma (appeared in TAMC 2020 | slides)
  Accepted to Theoretical Computer Science
  Volume 921, pages. 112-126, 2022 [DOI]
  [Full Version] [Conference]
• Alternation, Transforms and New Bounds on Boolean Function Complexity Measures
  Doctoral Thesis (IIT Madras). Guide: Jayalal Sarma
• Sensitivity, Affine Transforms and Quantum Communication Complexity
  Krishnamoorthy Dinesh and Jayalal Sarma (appeared in COCOON 2019 | slides)
  Accepted to Theoretical Computer Science
  Volume 838, pages. 68-80, 2020 [DOI]
  [Full Version] [Conference]
• New Bounds for Energy Complexity of Boolean Functions
  Krishnamoorthy Dinesh, Samir Otiv and Jayalal Sarma (appeared in COCOON 2018 | slides)
  Accepted to Theoretical Computer Science
  Volume 845, pages. 59-75, 2020 [DOI]
  [Full Version] [Conference]
• Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps
  Krishnamoorthy Dinesh and Jayalal Sarma (appeared in CALDAM 2018 | slides)
  Accepted to Theoretical Computer Science
  Volume 771, pages. 71-82, 2019 [DOI]
  [Full Version] [Conference]
• Characterization and Lower Bounds for Branching Program Size using Projective Dimension
  Krishnamoorthy Dinesh, Sajin Koroth and Jayalal Sarma (appeared in FSTTCS 2016 | slides, slides (by Sajin))
  Accepted to ACM Transactions of Computing Theory
  Volume 11 Issue 2, pages. 8:1 - 8:22, 2019 [DOI]
  [Full version] [Conference]
• Circuit Complexity and Geometric Representation of Graphs
  Masters Thesis (IIT Madras). Guide: Jayalal Sarma