Tag: algorithms

O(log n) algorithm for education

The amount of time required to train a certain number of students in some skill is usually proportional to the number of students.

In this post, I wanted to talk about a process for training people using ‘social networks’ that can work much faster and better.

The method was developed by a social start-up called Digital Green from Bangalore.

Digital Green’s mission is to educate farmers and help them improve their farm yields.

There are about 263 million people in India who depend on farming and many of them are illiterate and uneducated.

Therefore, education for farmers, if done right, can make a real difference.

Government agricultural research institutes have, for a number of years, been evolving farming best-practices, and trying to educate farmers on the same.

The government’s method of choice for educational initiatives is rural field officers who do the rounds of the villages.

But the process is often ineffective in driving change on the ground.

Digital Green discovered the reason for that.

It turned out that farmers were hesitant to abandon or change practices that had worked for their ancestors for thousands of years.

They were finding it difficult to trade time-tested ways of doing things for new methods.

Digital Green discovered that what farmers found more convincing was recommendations from early adopters from nearby villages.

They were less resistant to ideas from persons they knew.

So, Digital Green went about using their insights to change how education was delivered to farmers.

They started by constructing a social network without computers.

They made video CDs of early adopters engaging in a farming practice that needed to be promoted.

They then mailed the CDs to nearby villages – in each of which television and video equipment had been installed – and showed the videos to people there.

The farmers watching the videos would see familiar faces, places, soils and crops, and might also be tempted to adopt the practice in order to be able to star in the next video.

So, the practice would spread virally, from one early adopter to his connections, and from them to their connections, and so on.

This model of training is very similar to the model of information dissemination in social networks. Like in many other forms of viral transmission, the amount of time it takes to reach out to a certain number of people grows logarithmically with the number of people. In other words, it scales very well.

So, Digital Green’s approach is an O(log n) algorithm for education.

The following BBC article on Digital Green contains an interview with its CEO Rikin Gandhi:  http://www.bbc.co.uk/news/technology-23867132

You might also like this article we wrote in 2012 on another O(log n) algorithm for educating large numbers of people:  Is there an algorithm to combat poverty?

Advertisements

How algorithms can ‘shape’ our world – Kevin Slavin

In our first blog post of the year, we’d like to share a talk by Kevin Slavin.

It is about how math (especially algorithms) has ‘transitioned from being something that we extract and derive from the world to something that actually starts to shape it.’

One of the posts we most enjoyed writing last year was related to this:

It was about algorithms to combat poverty.

We also wrote about how math might someday shape our values.

Can an algorithm identify the perpetrators of a bomb attack

On 13th July, 2011, there were simultaneous bomb attacks at different locations in Mumbai.  One day, while I was thinking about it, I suddenly realized that there was an algorithm that could be used to bring the perpetrators to book.

It’s almost a year since the attacks took place, and we thought we’d finally write about our work on the problem (which we’ve shared with many government organizations, including CAIR, though we frankly don’t know if they plan to implement it).

Introduction:

When multiple coordinated attacks take place (like the three bombs that were triggered simultaneously in three locations in Mumbai in 2011), if the attackers had used cell phones to coordinate their attacks, the phone numbers involved can be extracted mathematically from the call records linked to the cell towers in the vicinity of the attacks.

Our calculations indicate that in a city the size of Mumbai and a population of around 20 million people, you would need a minimum of only 3 simultaneous attacks to be able to pinpoint the attackers to within 1 person. If there were only 2 attacks, you would have a much higher uncertainty. The greater the number of coordinated attacks, the easier it is to identify the attackers.

The identification will only be possible if the attackers used their cell phones to coordinate with a central handler, or with each other, or a group of handlers who in turn communicated with each other. It would be possible to support different possible patterns of communication and usage of cell phones and SMS to coordinate between the attackers and confirm the attacks.

History:

A similar method might have already been used in Europe after the Madrid bombings to identify those responsible for the same.
Two years after the attacks, the EU mandated that carriers store some details for 6 months. The information that the carriers need to preserve contains all the details required to triangulate attackers in multiple simultaneous attacks.

Here is some information on the directive from the Wikipedia:

On 15 March 2006 the EU formally adopted Directive 2006/24/EC, on “the retention of data generated or processed in connection with the provision of publicly available electronic communications services or of public communications networks and amending Directive 2002/58/EC.”

The Directive requires Member States to ensure that communications providers must retain, for a period of between 6 months and 2 years, necessary data as specified in the Directive.

 to trace and identify the source of a communication;
 to trace and identify the destination of a communication;
 to identify the date, time and duration of a communication;
 to identify the type of communication;
 to identify the communication device;
 to identify the location of mobile communication equipment.

The data is required to be available to competent national authorities in specific cases, “for the purpose of the investigation, detection and prosecution of serious crime, as defined by each Member State in its national law”.

Information:

The minimum information that would be needed to obtain an effective fix on an attacker is the following:
a) FROM_NUMBER
b) TO_NUMBER
c) TIME_STAMP
d) CELL_TOWER

Indian carriers tend to store the FROM, TO and TIME information in call logs (used by the carriers for billing and for customer service) for SMS messages for 2 days and for phone calls for 30 days. These can be obtained easily from them by a simple request from police.
The location of the cell tower is determined from signaling logs.

Technology:

Messages used to coordinate teams have certain patterns. For example, a possible pattern in an attack is a confirmation – success/failure – to the central handler after an attack.

Each message would have to originate from a cell tower near the site of a blast and in a short time window after the blast and have the same destination.

Out of all the hundreds of millions of messages sent in a city, only some would satisfy all these constraints.
Simple graph analysis can identify these messages, to very high accuracies in a city of 20 million of the size of Mumbai, provided there were 3 or more coordinated attacks.

The algorithm is so simple that an undergraduate student could build it in a few months.

Acknowledgements:

There are many people I have to thank for their help with this study, including old mentors from other research firms in the area who helped me with suggestions for handling temporal queries, and students/interns who helped speed up the study, and my colleague Sumukh who works on graph/tree search himself.