Our paper “DEX: self-healing expanders” which was published in Distributed Computing is now piblicly available at https://rdcu.be/5mOp as part of the Springer Nature SharedIt initiative.
Here is the mial below from Springer:
Congratulations on publishing “DEX: self-healing expanders” in Distributed Computing. As part of the Springer Nature SharedIt initiative, you can now publicly share a full-text view-only version of your paper by using the link below. If you have selected an Open Access option for your paper, or where an individual can view content via a personal or institutional subscription, recipients of the link will also be able to download and print the PDF. All readers of your article via the shared link will also be able to use Enhanced PDF features such as annotation tools, one-click supplements, citation file exports and article metrics.
We encourage you to forward this link to your co-authors, as sharing your paper is a great way to improve the visibility of your work. There are no restrictions on the number of people you may share this link with, how many times they can view the linked article or where you can post the link online.
More information on Springer Nature’s commitment to content sharing is available here.
PODC 2018 is just around the corner i.e. coming up next week at RHUL, London! it has been a privelege to be the Workshops chair. In particular, it has been exciting to see a great program of workshops come together in a semi-distributed manner. Some of the workshops are well established and some are coming here for the first time. Either way, it feels like one is watching the evolution of stars in a galaxy from the timeline of origin – in the sense that some of these may evolve into full fledged conferences at some point and some may die out but each brings a perspective on a niche (possibly) and growing area of research. This is also the stage to experiment with ideas which are coming (or maybe not) but maybe not there yet!
The workshops are over two days – 23rd July and 27th July – a solid main course of 6 workshops interspersed with 4 lunch-time tutorials. The program has settled down such that we have Biological, Social networks and Blockchains on day 1 and Large scale distributed implementation, systems and Edge and fog computing on day 2.
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!
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 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!
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.
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: Safety Verification for Deep Neural Networks ) 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!
The prominent computer scientist John E. Hopcroft was the London Mathematical Society’s (LMS) invited speaker (talk: Research in Deep Learning ). 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.
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!
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!
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).
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!