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.

Advertisements

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!

COSHER: journal paper published

TCS-Front

The final version of the paper Compact Routing Messages in Self-Healing Trees has now been published in the journal Theoretical Computer Science. The paper is now available at the following link: https://authors.elsevier.com/a/1WFCI15DaHr7c2 till February 07, 2018 without any registration or fees 🙂 (Thanks, Elsevier!).

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?

 

 

sierpinski.clear
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!

UIBInformatics
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).