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!

Gary

Advertisements

BCTCS 2018 : Day 2, Ahoy fellow Distributors!

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!

Day 2 of BCTCS 2018: today is an important day as there is a series of Distributed Systems talks, I having the honour of delivering one of them.

The first talk on Distributed Systems was delivered by Thomas Sauerwald of Cambridge University and was on Randomised Distributed Algorithms; such algorithms use random bits to determine some steps in their execution. These algorithms are usually elegant in their design and implementation, while in some cases providing solutions that are impossible in the deterministic setting.

Thomas.jpg
Thomas Sauerwald, Cambridge.

Thomas presented two examples in his talk on randomised algorithms focusing on large distributed networks. The first algorithm used randomisation on a rounding step in a load balancing algorithm and the second used random sampling to reach consensus.

I was the second speaker in the distributed systems segment of the conference. In my talk, I gave a brief introduction to the classic problem of leader election and presented the direction of my current research on asynchronous leader election.

The final speaker for distributed systems was Radu Ștefan Mincu. Admittedly at the beginning of his talk he admitted that his work very centralised. However, it was still very interesting. His talk was on multi-channel Wireless Mesh Networks (WMN), where each node may use multiple non-overlapping frequency channels. He presented 3 heuristic approximation algorithms to solve this problem.

The second day of the conference ended with a banquet in the founders buildings picture gallery. It was an extremely pleasant evening with conversations ranging from education to European nobility!

BCTCS 2018 : Day 1, Is this really London?

Editor’s note: This is the first 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!

The British Colloquium for Theoretical Computer Science (BCTCS) is an annual event for UK-based researchers in theoretical computer science. The conference provides PhD students the opportunity to present and discuss their research will other PhDs as well as established researchers from all over the country.

Royal Holloway hosted BCTCS this year. Royal Holloway was founded in 1849, as one of the first colleges dedicated to providing women with access to higher education, by the victorian entrepreneur and philanthropist Thomas Holloway following the inspiration of his wife Jane. The college was officially opened by Queen Victoria in 1886. The campus grounds are particularly beautiful with the founders building being a very popular filming location for both TV and film.

RoyalHolloway
Royal Holloway University of London Founder’s Building

Deep neural networks were one of the big draw on the conference’s first day. Deep neural networks are unrivaled in the domain of image classification. However, they are particularly vulnerable to adversarial perturbations on their input, changing the value of a single pixel can cause a misclassification. With this technology being used in self driving cars, it is only fair to ask —

Are deep neural networks really safe?

To help put our minds at ease Marta Kwiatkowska of Oxford University (talk title: ) has developed a novel automated verification framework for neural networks that is able to provide some guarantees that an adversarial image will be found if it exists e.g. a self-driving car will be able to detect an object on the road that may cause a collision!

JohnEHopCroft.jpg
John E Hopcroft at BCTCS 2018. More pictures at http://bctcs18.cs.rhul.ac.uk/

The prominent computer scientist John E. Hopcroft was the London Mathematical Society’s (LMS) invited speaker (talk: ). John’s talk started with one of the recent major advancements in AI when in 2012 AlexNet won the ImageNet Challenge with a deep neural network that had a top-5 error of more than 10 percentage points better than the next runner up. However, we understand very little of why deep learning works. The questions being asked in deep learning are:

 Is the structure of the network more important than the training?

Can a network be trained much quicker than at present?

Do we even need a large training set?

After all when a child learns what an object is we do not need to teach them thousands of examples!

The first day of BCTCS has been fantastic! My turn tomorrow.

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!

Postdoc in distributed algorithms required

A postdoc position to work with me on an EPSRC research project at Loughborough University is available from July 2017.

I have a position for a 1 year (in the first instance) postdoctoral research associate to work with me at Loughborough University. The position, supported by the EPSRC first grant COSHER (Compact Self-Healing Routing), comes with a good salary (in the UK system) and other perks and trainings. The project is available here at the RCUK gateway. The related research question is described in my earlier post here.

The earliest (and expected) start date is July 1st, 2017, but a later start date may be possible. The formal advertisement will be out in the coming week but please get in touch with me for more details!

Funded PhD studentship in Graph Algorithms/Distributed Algorithms/Dynamic graphs

This slideshow requires JavaScript.

 

I am on the look out for an outstanding PhD student. Here is the advert! I will also be advertising soon for a postdoc position as I seek to grow my algorithms/distributed algorithms research group. The student will have the chance to work in the dynamic and fast growing Loughborough CS and one of the best campuses to be a student in the UK. For more on Lufbra, see my previous post.

In brief, you may create the next cutting edge graph algorithm for resilient networks or solve an open problem in graph theory! (..and add a figure from your research to those above!)

Here’s a more formal description of what I envisage the student could undertake (with guidance from me and my outstanding colleagues at Loughborough CS):

This project seeks to design and mathematically analyse distributed graph algorithms with an emphasis on resilience and dynamic scenarios and, in general, to explore decentralisation. Networks are pervasive and diverse and, with the upcoming Internet of Things, likely to be deeply integrated into our society. Networks often rely upon distributed protocols for their functioning. Failure of components and security also makes resilience a critical issue. Distributed graph algorithms allow us to model, explore and design solutions for all kinds of networks.

We seek candidates who have strong interest in and are willing to explore topics in this domain from, but not limited to the following: i) Self-healing, byzantine and other forms of resilient algorithms, ii) Compact routing and memory limited algorithms, iii) Static and dynamic Leader election and consensus, iv) Techniques such as topology, spectral and algebraic tools and communication complexity, v) Game theory applied to distributed algorithms and decision making, vi) Modelling and application to modern networks such as IOT and SDN.

Please apply via jobs.ac.uk at the link: http://www.jobs.ac.uk/job/AYE112/phd-studentship-distributed-and-resilient-graph-algorithms/  – the opening is fully funded for UK/EU students with a comfortable stipend, and is open for international (Non-EU) but the stipend will unfortunately be adjusted towards the higher international fees to begin with!