Dr Sudatta Bhattacharya: Studying at Matfyz Was a Lot of Fun

Dear Sudatta, you have just graduated from the Computer Science programme – Theory of Computing, Discrete Models and Optimization. Congratulations! Was it a challenging journey?

It was indeed challenging. But luckily, I like challenges, so it was really fun for me.

When did you decide to study Computer Science, and later specialize in Theory of Computing?

I have always loved mathematics; it was my favourite subject. In high school, I started getting interested in computer programming (initially with HTML and MS-DOS). At first, I chose Physics for my bachelor’s degree but soon realised that I missed the strong presence of mathematics. That led me to switch to Computer Science (actually Computer Engineering, after passing a national entrance exam).

During my bachelor’s studies, I wasn’t yet aware of Theoretical Computer Science as a distinct field. Only in my master’s studies was I formally introduced to it, and I quickly realised this was what I wanted to pursue long term.

As many students struggle with choosing their major, I’d like to ask you: what drove you to Theoretical Computer Science? What made you realise this was what you wanted to pursue?

I have always loved solving puzzles, whether it was a Rubik’s cube or some kind of game. Over time, I realized that working through math problems felt very similar to solving puzzles – challenging and rewarding – which is exactly what I enjoy. That was my first hint that I wanted to pursue something math-related. In fact, I initially wanted to study pure mathematics. However, my high school teachers advised against it, saying that a career in pure math isn’t very promising (at least in India), even though I had scored among the top in the subject.

Since I also enjoyed coding, I decided to go into computer engineering instead. Later, during my master’s, when I chose to pursue a PhD in theoretical computer science, I realized it was the closest field to pure math – and for me, that was the perfect balance. Looking back, I’d say I was fortunate to have found the right path.

Why did you choose to study at Matfyz in Prague?

One of my seniors, a PhD student while I was a master’s student at IIIT Delhi, introduced me to Charles University and encouraged me to contact Prof. Michal Koucký.¹

What happened next? What was the process after contacting Prof. Michal Koucký?

Prof. Koucký kindly replied to my email and suggested a Skype meeting for a brief introduction to my work. Two other professors also joined the call, and they asked me to give a short summary of my master’s thesis results. Following that meeting, they invited me to Prague for a short visit to present my thesis work. It was an incredible opportunity – after my talk, I had the chance to meet with Prof. Koucký and the other professors, where we discussed both their research and mine. It felt more like an informal interview, with the presentation being the central part. A few days later, I received an acceptance email. The acceptance was essentially confirmed at that point, but I still had to go through the formal application process at the university as a formality.

What did your time at Matfyz give you – academically and personally?

I had an amazing experience. The departments of IUUK² and KAM³ are fantastic, filled with brilliant yet humble people. I learned a lot from doctoral seminars, weekly seminars, and discussions with professors. My supervisor also taught me invaluable skills like how to approach problems, identify interesting questions, read papers efficiently, write research effectively, and write grant proposals. Personally, I made many friends, and I really enjoyed the retreats, summer schools, and workshops like KAMAK⁴ and HOMONOLO⁵. Spending time in nature with colleagues was a highlight that I will miss greatly.

How did you find studying at Matfyz overall? What was the most challenging part, and what came easiest to you?

It was a lot of fun. The most challenging part in the beginning was reading and writing complex papers. The easiest part was adapting to the department itself, because everyone was so welcoming.

Did you enjoy living in Prague? Do you have a favourite spot in the city?

Absolutely! I loved Prague. Some of my favourite places include Letná Park, Obora Hvězda, Ladronka, and, of course, Charles Bridge.

Coming from India, was there anything particularly challenging about living in a different culture, far from home?

It was very different, but I enjoyed it. I will really miss some aspects, like how polite people are, the lack of judgment, the super-efficient public transportation, and the overall smooth lifestyle in Prague.

Back to science – what was your thesis about, and how did you come up with your topic?

My thesis focused on metric embeddings for string distances. My supervisor first introduced me to edit distance, a very robust string distance measure. We obtained some results on sketching and streaming, then explored other string distances. Eventually, I realised all my results were connected through metric embeddings and their applications, which naturally came together as my thesis.

Could you briefly explain what string similarity measures are and why they are important in modern computational research?

Strings are sequences of symbols from an alphabet set, for example “computer” or “Prague”. To quantify how similar or different two strings are, we use distance measures such as Hamming distance and edit distance. These measures play a crucial role in many areas of computational research.

In many real-world applications, data is inherently noisy. Data is often represented as sequences (or strings) of bits (or characters), but it frequently contains errors. For example, some bits may be flipped, extra bits might be inserted, or some bits might be missing. As data size increases, the likelihood of such noise also grows. In machine learning, large datasets used for training may contain errors that degrade model performance. Similarly, in computational biology and bioinformatics, massive DNA or RNA sequences are prone to noise. Effective methods are needed to measure, detect, and correct these errors, and string similarity measures provide a way to quantify the extent of data corruption and compare noisy data.

What were the main conclusions of your thesis? What did you manage to prove, and what did you disprove?

My thesis examines metric embeddings between key string similarity measures – edit distance, Hamming distance, and Indel distance. We developed a new embedding from edit to Hamming distance with low distortion (meaning the distances are well preserved) that also maintains extra structural properties, and we proved that it can be used to design efficient sketching and streaming algorithms for edit distance.

We also studied embeddings in the reverse direction, from Hamming to edit distance, where we achieved an isometric embedding, and showed how optimal embeddings can be used to derive tight lower bounds. In addition, we explored the connections between edit and Indel distances and examined alphabet reduction as a type of internal metric embedding.

Do you plan to continue working on this topic in your future research?

Yes, I plan to continue in this area while also expanding into other topics within Theoretical Computer Science.

While studying, you also published other academic articles. What were they about, and how did these opportunities come about?

I have five papers in total: four published (STOC, ICALP, FSTTCS, EuroComb) and one currently under submission. Four of these are closely related to my thesis. My first two papers were co-authored solely with my supervisor. At HALG 2023 in Prague, I met two collaborators, and together with my supervisor, the four of us worked on a project that became a paper at FSTTCS.

The same team, later joined by three additional collaborators (including some I met during my visit to DIMACS), produced another paper that is now under submission. In addition, I co-authored a paper in structural graph theory (published in EuroComb), through a collaboration with my officemate and her supervisor.

What are your next steps? Do you plan to stay in research? Are there specific topics you’d like to explore further?

Yes, I plan to stay in academia. My goal is to secure a permanent position within a couple of years. For now, I will continue as a postdoctoral researcher for 1–2 years before applying for permanent roles. Besides string algorithms, I am also interested in space complexity and circuit complexity, which I hope to explore further.

Rumour has it that you have been offered a chance to study or work at Weizmann – is that correct?

Yes, I will be joining the Weizmann Institute as a postdoctoral researcher in January 2026. I visited Prof. Robert Krauthgamer in April 2025 for a week, and I really liked the campus and the department. Robert is a highly reputed researcher, and his work aligns closely with mine. Both my PhD supervisor and former advisors, as well as collaborators, strongly recommended Weizmann to me.

Is there a chance we might see you again in the Czech Republic?

Yes, definitely!

¹ Editor's note: Prof. Mgr. Michal Koucký, Ph.D. is a member and professor at the Computer Science Institute of Charles University majoring in theoretical computer science, especially in computational complexity, data structures, algorithms, and combinatorics. His past large projects were EPAC project supported by GA CR, and LBCAD project funded by ERC.

² Computer Science Institute of Charles University.

³ Department of Applied Mathematics of Charles University.

⁴ Problem solving seminar outside Prague.

⁵ Workshop focusing on structural properties, algebraic aspects, algorithmic complexity and other aspects of graph homomorphisms.