Edin Husić is a PhD student who joined the Department of Mathematics in October 2017. His supervisor is Dr László Végh and he works closely with a number of other PhD students within the Department. In this post, fellow PhD student Bento Natura catches up with Edin on his research and the impact of lockdown life…

Can you tell us a little bit about yourself?

I am third year PhD student here in the Department of Mathematics. Before, I spent four years in Slovenia at the University of Primorska, and a year at ENS Lyon in France where I finished my Master’s degree.

In layman’s terms, what are your main fields of research?

Very vaguely, this would be the theory of algorithms for optimisation problems. In such problems, given many possibilities, we want to find the best solution that you can possibly hope for. A simple example would be finding a shortest distance to a destination. An overreaching theme is finding fast and efficient algorithms that solve such a problem optimally. People tend to assume that computers are magical devices that solve all problems very quickly, but that is far from reality.

Most of the problems that we are care about cannot be solved with fast algorithms. We are interested in classifying the problems that are easy and can be solved with fast algorithms, and the hard problems which cannot. Of course, we will not give up on hard problems. For harder problems, the goal is to find efficient algorithms that produce solutions that are close to the optimum.

What kind of popular problem could be modelled as these algorithmic problems that you mentioned?

Recently we worked on social welfare problems. Imagine a set of items that we would like to divide among agents. For example, this problem can arise in divorces, or when deciding inheritance with items like houses, land, car, jewellery etc. We would like to share such indivisible items in a fair and efficient way to people who have a claim to it. As is the case with many interesting problems, we cannot design a fast algorithm that solves such a problem optimally, so we would like to find an algorithm that is still fast, not optimal, but at least satisfies some approximate notion of fairness and efficiency.

To illustrate some of the issues, suppose that there are two people (agents) and a single item that is indivisible. Obviously, there is no way to allocate the item such that both parties are satisfied. The problem becomes more complicated as the number of items increases. It is proved that you cannot find a fast algorithm such that both parties are satisfied (what we call envy-free), but we aim to find algorithms such that the envy is only small.

What impact do you expect or hope your research has in practice, and what impact did it already have?

It is yet to be seen whether this particular idea will have a lot of impact outside of the theory. The problem of fair division itself is very popular. There exist several software tools and websites in use today that help you to make decisions, say for your rent, utilities and similar things. One such website is spliddit.org/. Related algorithmic questions which concern finding optimal or provably approximate solutions appear everywhere from logistics, computer science, and even in biology or more precisely bioinformatics.

In a sense, DNA is a set of information encoded by four letters, that gets copied and changed over time. Similarly, the mutations and evolutionary history of an organism or species is easily mapped on a tree, a so-called phylogenetic tree. A population starts with a set of characteristics or mutations. As time progresses, parts of the population accumulate new mutations and form a slightly different sub-population and the process repeats. We can think of the original population as a node in a tree, and the different sub-populations as its “child”-nodes. The differences in characteristics or mutations can be succinctly represented as the set of new mutations present in the sub-population that were not present in the “parent” population.

A related project I have been working on concerns the evolutionary history of tumours. In short, tumours change quickly, and we are not able to observe mutations every time they occur, so we don’t know what the phylogenetic tree looks like. Rather, we take a snapshot of the tumours and its mutations at some point in time, and the goal is to work out the likely developmental history of the tumour. Or in the language of trees, we have some information only about the leaves of the tree and we need to determine what the whole phylogenetic tree looks like.

How did you first become interested in the area?

There are several aspects to it. Since I was a kid, I enjoyed mathematics and was interested in learning how things work. During my bachelors, mathematics seemed more about how things are, while algorithms are also “working” and describe how structures behave so I found them more fun.

On the other side, I always liked optimisation. It seems that so many things could be improved, and make our life easier and better, just by saving resources at the right points without making any cuts. Once I took a course in optimisation methods, where I first learned that most problems are not solvable efficiently, I was hooked.

How is your experience of collaborating exclusively online with colleagues so far?

It is not that bad at all. There are even some advantages. The scientific community immediately moved everything online. There are plenty of talks and conferences that are freely available online. Collaboration is impacted a bit but not too much. It’s still doable if you have the right equipment and hardware.

What’s the best part of LSE so far?

I quite like that LSE is not too big, and the mathematics department in particular is amazing and extremely supportive. Everyone makes you feel welcome and that you belong here from the first day. To use the official slogan, you feel the ‘part of LSE’ from the first day.

Imagine the world is back to normal. What would you make one of the highlights of your day?

What I really miss is being able to travel and see my family, my girlfriend and my friends. Not travel for the sake of travelling but travel to see dear people.