BCTCS 2018 : Day 3, Terminus!

Editor’s note: This is the second in a series of blog reports by my PhD student Gary Bennett who attended the annual British Colloquium for Theoretical Computer Science (BCTCS) 2018  at Royal Holloway University of London. Apparently, he really enjoyed himself!

On the third and final day of BTCS I was able to relax as I had already given my talk.

One of the talks that was particularly interesting was on Concurrent Kleene Algebra, aimed at incorporating concurrent composition. The talk showed how the toolkit for Kleene Algebra had been extended and what problems they had to overcome such as recursive forking.

In the afternoon there was a series of talks on stable matching. Stable matching is being used to find adoptive families for children in need of loving and permanent homes, and closer home for student projects allocation. Provided these matching instances are small enough they can be solved directly. However, for large instances the problem is intractable. In the talks given a number of approximation methods were presented to give high quality solutions in less time.

This marks the end of my journey at BCTCS. I have had a great time and met many great researchers!

Now it is time for me to relax over the Easter break in Hong Kong!



Stephen Hawking: A memoriam in time

Yesterday, for some unexplained reason, I spent £6 on the latest issue of National Geographic – £4 of those should go to Prof. Stephen Hawking! – Thoughts on losing one of my heroes and remembering a memorable 2001 evening where I stood in a mile-long queue to attend a superstar Hawking Lecture!

Stephen Hawking (and the Simpsons) in India circa 2001: He gave a series of lectures in india and used the Simpspons cartoon series featuring himself!
Stephen Hawking (and the Simpsons) in India circa 2001 (http://www.rediff.com/news/report/pix-when-hawking-visited-india/20180314.htm)

Yesterday, for some unexplained reason, I spent £6 on the latest issue of National Geographic – £4 of those should go to Prof. Stephen Hawking! Why? Because the main title cover is NEW VIEWS OF THE COSMOS and another smaller title is A BRIEF HISTORY OF LIFE. I conjecture this issue would sell much less if it was not for Hawking and his A BRIEF HISTORY OF TIME.

This takes me back to a somewhat balmy winter evening in India. It was January 15th. 2001 and I and a friend ventured out of our Indian Institute of Technology (IIT) Delhi students hostel to go to a show by a rockstar. The rockstar was Stephen Hawking and those were the days when poor grad students could still buy tickets for such events!

Hawking was going to give a public lecture interestingly titled From Astrology to Blackholes at the Siri Fort auditorium which is not very far from IIT. When we reached the auditorium the queue was a mile long running around two blocks of buildings.

You would have thought that this was for a big bollywood star like Amitabh Bachchan or Shah Rukh Khan and not for a physicist the details of whose work are beyond many physicists let alone the general public. But such was the power of his outreach and the magic of his writing that he sparked the interest of a whole generation into this `exotic’ object called Black Hole, the origin of life and the universe and the determination and power of the human mind to overcome life debilitating disabilities.

When we finally managed to get in, the auditorium was packed to the rafters (As this news story from the past recounts – We are thinking of putting up big screens outside the venue to allow more people to hear the lecture). We were lucky to find seats but there were people sitting on the stairs and in the aisles including some we could recognise as well known media figures. My friend had sneaked in his father’s mechanical film camera and was setup to sneakily take pictures of the occassion.

At some point, the president of India K R Narayanan walked in and sat at the front. Then, it was time and prof. Hawking wheeled in to a rapturous reception.

As it was with him, he was there seemingly completely still and his robotic voice spoke as slides on the large screen went by.  There was Hawking and the Simpsons cartoons on the screen and a number of funny anecdotes had the crowd literally and figuratively rolling in the aisles (remember the aisles were full too). This was till the physics began!!

A few minutes into the lecture, Prof. Hawking ventured into the cosmos, black holes and the present theories behind the structures and origins of our universe. For me, the lecture was absolutely fascinating and I went back with the same old question in my mind that why had I not become a cosmologist rather than the computer scientist I was becoming!

A curious phenomena however happened – what seemed like almost a third of (and seemingly mostly older) audience  started drooping and occassionally snoring.  In hind sight, this was not surprising and this will always be Hawking’s legacy – Who was more inspirational? Hawking the scientist or Hawking the man who in a life long battle with ALS kept ALS on the mat firmly with a wheel chair over its chest! Obviously, a number of the audience had come to pay homage to the strength of the human spirit.

Back in the student’s hostel, I gave a lecture on the lecture I had just heard to some fellow students, some of them physics students. That evening, it seemed that Cosmos had come to the table complete with black holes, branes and strings (If you didn’t get that refer to String theory)!

The point to remember is that this is the imagination that fires up brains and drives us towards knowledge and science. What we were not discussing was the mindbending rigour and extremely complex mathematics underlying Hawking’s work. He himself wrote in the introduction to A Brief History of Time that he put only one equation in the book (E=MC^2) since each additional equation would reduce the readership by half.

Probably the most beautiful example of his work (at least one which I understood a bit) was Hawking Radiation. Black holes are these extremely dense objects in the universe often found at the centre of galaxies that have such strong gravity that they devour everything including light itself. Black holes were thought to be absolutely black but Hawking showed they were gray! 

Particle physics dictates that energy and matter is made up of  particles and corresponding anti-particles coming together and breaking away in instantaneous time. Hawking thought about this phenomena at the edge of the black hole and came up with the brilliant theory that due to the extreme gravity, the edge of the black hole would leak the partner particle (or anti-particle) of the devoured anti-particle(particle) leading to what came to be known as the Hawking Radiation.

The only reason that Hawking Radiation (and other works of Hawking) has not won the Nobel prize for him is that the energy of the hawking radiation is calculated to be even lower than the background radiation around since the Big Bang and hence, so far, impossible to measure.

A few years later, I was fortunate to study  in a class taught by the Nobel Laureate and inventor of quark Prof. Murray Gell Mann at University of New Mexico, and, if I remember correctly, he mentioned that the genius of Stephen Hawking was to apply particle physics and quantum mechanics to the field of Cosmology. Long live the scientist and superman Stephen Hawking!

The Art of Sorting!

When Art is combined with Science and vice versa, it has a magical quality! I suppose if you are movie goer, you should be intensely aware of it, especially if you watched this year’s Oscars front runner – The shape of water.

People have done some wonderfully inspiring stuff around illustrating and promoting understanding of algorithmic (and mathematical) concepts.  Sorting algorithms, which deal with arranging objects (say, numbers) in ascending or descending order somehow lend themselves to a few such creative exercises. Here are two examples which I really enjoy using while teaching my Algorithms classes. The best quality they have is they  wake up students (with a bang, I should say) from the deep sleep induced by a tough lecture, and even infuse some with a love of algorithms (at least I fantasize so).

  1. Sound and Fury: The video below titled 15 sorting algorithms in 16 minutes, probably my favourite ‘cool-aid’, is by Timo Bingmann from Kalsruhe (KIT). It’s quite fascinating to see how he uses the numeric values to generate the plots and the relative difference of the compared values to generate the sound. The video has a mere 4.1 Million views so don’t stress if you add a bit more to the count!

The closest I came to doing something like this is when as a high school student, I wrote a program in the programming language Basica that plotted the initials of a girl I liked using a cosine function. Do try that some time!

Details about the above video and its companions, the algorithms behind their generation and the complete source code is available at http://panthema.net/2013/sound-of-sorting/ – if you like, download and have fun!!

2. Sorting Come Dancing: Now, on to the ‘sorting dances’. This group Algorhythmics from Sapentia University, Romania, seem to have a real affinity for dancing their algorithms! They have a number of well known folk dances which end up doing sorting or even other things such as linear and binary search. Watch the numbers Quick Sort themselves by doing a Hungarian dance!!

I wonder how another dance, say an Indian classical dance, effect quick sort! ;). Watch more of their dancing at their youtube channel: AlgoRythmics

I have issued a challenge to my UG year 1 Algorithms class to see if they can come up with something similarly creative. Considering that Loughborough University is ranked the number 1 sports university in the world, I wouldn’t be surprised if it had some sporty angle to it. Let’s wait and watch!

Inverted triangles and fake documentaries: stories from the Royal Society Media Skills Course

A team of motley researchers at the Royal Society’s residential  media skills course left gobsmacked, by the bizarre ways in which they can communicate their research (and by the candy collection at coffee break) – the previous line is the top of the inverted triangle of this blog post!

I recently came back from Chichester hall where the Royal society holds their residential communication and media skills course  where we were introduced to such blasphemies as inverted (i.e. downside-up) triangles.

Inverted triangles can give us researchers sleepless nights since that implies we write the conclusion of our article at the top and the introduction at the bottom! Moreover, we were assured of even stranger constructions with all kinds of combinations of triangles, trapeziums, circles and rhombuses – maybe even serpinski triangles –  Jon?



Serpinski Triangle: a fractal of triangles!

The rationale is that for mobile devices and millenials (..and shortening time spans) the punch should come right up and further, as you may have noticed – paragraphs should be very short (even one sentence each! – if you don’t believe me, go to BBC’s websites).

More to follow, of course ….

Dr. Jon Copley the deep sea marine biologist can be found at http://www.joncopley.com and Geoff Marsh (not the cricketer) can be found at https://www.geoffmarsh.com – you didn’t think I would give you their links at the top of page and let you get away from my post, eh!!

A week in Bergen!

…to try to fix a marriage between distributed computing and parametrised complexity!

uib Høyteknologisenteret: Unfortunately it is not at all as sunny in the picture (rain, rain everywhere!) 😉


This is ‘working day’ 2 of my week in Bergen! I was delighted to be invited by the incredible Saket Saurabh to visit their world leading research department. The aim of this week is for me to give a series of lectures (one per day (1.5 hrs)! – I am hoping that my new postdoc Jonas Lefevre will take one for me 😉 on distributed computing with the aim to find intersections and possible  influences between distributed algorithms and parametrized complexity. I hope I have only a fraction of the energy that Saket has in managing his 12+ PhD students and postdocs 🙂

It’s exciting being here and looking forward to a really productive week!




PhD studentship in algorithms/theory available again!

Funded PhD studentship in algorithms/theory at https://goo.gl/BfH7uP

A PhD studentship similar in description to the one advertised earlier is available. The application deadline is rather short: July 3rd! Details and an application link are available at http://www.jobs.ac.uk/job/BCG461/phd-studentship-graph-algorithms-and-foundations-for-networks-of-the-future/

We seek candidates with strong interest in and willing to explore topics from, but not restricted to the following:  i) Graph algorithms and theory, ii) Self-healing, byzantine and other forms of resilient algorithms, iii) Compact routing and memory limited algorithms, iv) Static and dynamic Leader election and consensus, v) Connections between distributed algorithms and research areas such as parameterised complexity, topology, combinatorics, communication complexity, spectral, algebraic tools, vi) Algorithmic game theory and decision making, vi) Modelling and application to modern networks such as IOT and SDN.

The successful candidate will work closely with active research groups centred around both CS theory and networks. In particular, the candidate can benefit from interaction with upcoming research on compact self-healing routing algorithms supported by EPSRC (EPSRC research grant EP/P021247/1).

Postdoc position: now accepting applications

Advertisement for postdoc position for working on distributed algorithms under the EPSRC project COSHER is now live at http://www.jobs.ac.uk/job/BBB561/research-associate/

Below is the message I have sent out to a few mailing lists!

Here are some related blog posts on this same blog related to the opening and the research:

Postdoc in distributed algorithms required

My exciting EPSRC first grant!

Belfast to Mexico City via Self-healing Compact Routing!


Applications are invited for a postdoctoral research associate position in the area of distributed algorithms in the research group of Dr. Amitabh Trehan at Loughborough University Computer Science.

The position is funded by an EPSRC first grant to work on an exciting new project called COSHER:  Compact Self-healing Routing (COSHER) (RCUK link) that aims to combine research on compact routing with resilience (self-healing) using the standard message-passing modelling of networks (as graphs) and mathematical analysis of proposed algorithms. The position is for a one-year fixed term in the present instance providing a competitive 12 month salary with standard benefits.  The expected start date is Fall 2017 (Available to begin as early as July 1, 2017).

The successful candidate should have a PhD in Computer Science, mathematics or related disciplines with knowledge and understanding of algorithms and CS theory and/or networks. Experience in designing distributed/network algorithms is highly desirable.


More details and a link to the application is available at http://www.jobs.ac.uk/job/BBB561/research-associate/

The application deadline is June 1st, 2017.

The (online) application should include (1) Education details, (2) Supporting information in the form of a brief cover letter and research interest statement, (3) Names and contact information of three referees, (4) CV and publications list.

Informal enquiries should be made to Dr. Amitabh Trehan by email at a.trehan@lboro.ac.uk or by telephone on +44 (0)1509 222564.

Please also refer to the blog www.huntforthetowel.wordpress.com for more pointers on the research.

Dr. Amitabh Trehan
Computer Sciece
Loughborough University
Loughborough, England.