Currently viewing a development environment

An anonymous COVID-19 contact tracing app that warns you when your friends are sick

A different kind of contact tracing sounds an alarm when people in your social circle are falling ill

Dan Samorodnitsky


SUNY Buffalo

COVID-19 contract tracing apps are a bit of a rage right now. The UK National Health Service has one. So does Germany. Half the states in the US have their own; North Carolina's alone has almost 800,000 downloads. These apps mostly work the same way: if you were in close contact with someone who was later diagnosed with COVID-19, you get alerted and asked to quarantine. This approach has drawbacks. First, it requires some amount of people to have and use the app, to make it useful at all. The second is that it relies on users' ability or desire to comply with an app that asks them to stay home.

Last year, Carnegie Mellon University scientist Po-Shen Loh published a paper with a different idea. He proposed an approach that "inverts the incentives." Instead of telling people they'd been exposed and, for other people's good, quarantining themselves to stop further spread, warning people ahead of time that danger was near. This, hopefully, makes the decision less altruistic and more about self-preservation. An app using this approach, NOVID, is available on app stores. Massive spoke with Loh about the mathematics behind this different form of contract tracing, and what he hopes to see change. This conversation has been edited for clarity.

Dan Samorodnitsky: Can you tell me how you ended up working on this app?

Po-Shen Loh: I am a person who grew up with math competitions. So it was in middle school, when I suddenly discovered that there were math problems that were harder than what you normally do in school, and therefore they were interesting. I like people, I like helping people. I like working with people and things. I like challenges, I like working on things that are supposed to be hard or impossible, or the fewer people in the world who can achieve them, the more interesting they are to work on.

In say, January 2020, I heard there was some COVID thing, and I wondered why everyone was overreacting about it. I didn't know. But then on March 14, which I can remember, because it's Pi Day, I got an email. And the reason I got it is because I'm a Hertz Foundation fellow. This is an important part of my history. The Hertz Foundation is a group that signs about 15 people every year who are about to start their PhDs. And if you get it, you get free funding for a PhD. But you also sign a moral commitment that if there's ever a moment of national emergency, you'll go to help.

And the idea of the Hertz Foundation was if you ever needed another Manhattan Project, would there be people to do it? I got the Hertz fellowship in 2004. By then nobody expected to build more bombs. In fact, the joke was, we'll probably be called to respond to some kind of bioterror.

That’s a hilarious joke.

Yeah. So on March 14, there was this email, detailing how COVID-19 wasn't just like some fluke. And it wasn't just something that would get old people sick. But actually, there was all these different aspects of it. This was stuff that I hadn't known at the time and we ended up ended up saying, “remember, the moral commitment?”

I remember when I was supposed to be giving feedback [for a grad student’s thesis], I only got through the first sentence of the introduction, I suddenly realized, oh my gosh, our area of research is network/graph theory. It's something that could be extremely powerful in fighting COVID. Because now we have smartphones. It's possible to go and anonymously figure out which devices were around which other devices, and then you have a big network.

And since they’re smartphones, you could also even label some of them as having various symptoms or like “got sick” and when, and with all of this anonymous information where you don't need to know anything about the person, you could actually possibly control the virus. That was the insight.

Let's pretend that I'm bad at math. Can you explain what network theory is? And how it connects to this use of phones and labeling people?

You've probably heard [for COVID social distancing] six feet for 15 minutes. Network theory, or graph theory, is where you say, look, let's not focus on that. Let's instead do this: if two people live with each other, connect them by a line and consider them linked. If two people work in the same office regularly, consider them linked. Effectively consider people linked if it is quite possible for them to transmit to each other due to their extended behaviors. But if you were in the supermarket checkout line, standing behind someone for 10 minutes today? And you'll never see the person again in your life? Don't even bother connecting them.


Now here's how I'm going to measure how dangerous it is for you. If you spend a lot of time around someone, who spends a lot of time around someone else, who spends a lot of time around someone else who has COVID, that's three distances away from you in the network. And I would say that COVID is three relationships away from you. It's a different way of quantifying distance. It's not like that was 25 meters over there. And we were in the same place for an hour. Instead, it's how many of these long term repeated relationships away are you? It’s like six degrees of Kevin Bacon.

Every other app [like apps released by the German and British governments] works only after you have already been around somebody else who has COVID. It tells you, “Hey, you know what? You were around somebody else with COVID. Maybe you have it now, too,” because they’re measuring physical distance

This is the “inversion of incentives” that you talked about in the arXiv paper?

That's correct. Because at that point, what does that app do for you? The only thing that app does for you is say, “Oh, no, you have been around somebody who has COVID.” Well, in that case, all you can do is quarantine to go and protect everyone else from you. Here’s a question: suppose you were around somebody else, for six feet for 15 minutes? Suppose that they had COVID? What's the chance that you get it?

Oh lord you’re quizzing me. 

It actually turns out to be really low, less than 10%.

And 10% would be considered low in this kind of scenario?

So let's think about game theory and behavioral science here. Suppose that an app is asking you to quarantine voluntarily. And suppose that its threshold for triggering that command is when your chance of getting sick passes 10%. How many people will listen to that request?

A chart showing social circles intersecting with each other. The user is in the 1st circle, while someone with a COVID-19 infection three circles away

A chart showing social circles intersecting with each other. The user is in the 1st circle, while someone with a COVID-19 infection three circles away

Courtesy of NOVID

[hems and haws for a moment] Probably not that many.

So that's my, that's my point. There's a huge difference between trying to make an anonymous app to do contact tracing, which non forcibly tells you, “Hey, you should go and quarantine” versus manual contact tracing, which is where somebody calls you up and says, Hey, hey, Dan, I know who you are. I know where you live, stay there.” 

This is where a mathematician comes in. What breaks along the way, if there's a 10% chance that you're actually positive, is enforcement. Let's say non-anonymous changes to anonymous. Suddenly, as we know, on the internet, once people become anonymous, lots of different things happen. You know what I mean? Like, yeah, that's the entire thing about anonymous behavior.

Is “inverting people’s incentives” something that you identified at the beginning and then sought out? Or is it something that came out later?

It came out in the middle. At the beginning, we were making an app that was doing what every other app was doing. We were making a contact tracing app.

And then around the late summer and early fall [2020], I learned about the fact that if you are around somebody else who has COVID, the transmission probability is not extremely high. And then that raised some huge alarm bells of Wait a second. It's not compatible with human behavior.

This pandemic will have to end at some point. Do you see a use for this kind of technology down the road?

So what we've just invented is a new kind of feedback loop that will help humanity, forever. This could fundamentally affect how people avoid disease forever, they might not care to use this to avoid the common cold, because they're not afraid of it. But the moment that there is another bad disease, and there will only be more of these because of the interconnectivity of the human population.

My goal is that everyone says, you remember, you remember what happened with COVID, we learned that the radar was a way that you could just avoid getting sick. Will they use this app that I've made? Probably not. I mean, this is just one particular app that we've made. But will they use this paradigm? Yes.

NOVID’s user base is mostly around Georgia Tech in Atlanta and at CMU in Pittsburgh. Have you seen effects reducing COVID spread among people who are using the app?

There was actually a student who contacted me about almost two weeks ago. He said, “I saw on my radar that there was a case two away from me. I was going to hang out with my friend. He checked his radar. There was one away from him. My case was one away from him. So we chose not to hang out.”

Does this kind of technology have to have input from some governing body? Is there any way to avoid that?

Yes we avoid that. In some sense, Carnegie Mellon is not really a governing body, it's just a trusted entity. Whenever there's anyone who's actually sick, Carnegie Mellon gives that person a code, a password, if they use that password in their NOVID app to report positive, suddenly that shows up as a verified positive case.

But that person still has to take the initiative to report themselves.

So that’s a fundamental flaw, because maybe only about 10-20% of people will actually enter in voluntarily that they’re sick. That kills everything, that kind of a problem is a huge problem for all these apps. In our system, the person who's sick gets a passcode to enter that they’re sick, and every one of their contacts, traced contacts, gets another passcode that they can enter into the NOVID app to say “I was a contact.”

And if any one of those people enters in the passcode, that original person, the person who actually was exposed, gets verified?

Almost, but you're getting very close. This system is designed so that as long as one of these people does it, we're in good shape. But in order to protect privacy, they have no way actually of telling who that person was. Instead on the radar, it shows up as not a red, but as a pink. And so what happens is, you would find out on your radar, hey, somebody two relationships from you reported that they’re a contact of a positive case. Well, then there's a positive case within three of you. This is called the triangle inequality in graph theory.

What the triangle inequality says is, suppose that your radar tells you that four relationships away, there is a contact of a positive case, then the positive case is at most five relationships away, because four away from you is a contact of a positive case, at most one away from there. All that does is it shows up as a blip on the radar, where the blip might be off in its horizontal position, which is how many degrees away from you a positive COVID case is by at most one. But that's good enough.

Just seeing that there is a positive case no matter if it’s off by one degree of separation?

That's right. 

This is not an app designed to close things. This is an app designed to hopefully open things. The exciting thing here is that if you have this system, whenever a person is around sickness, they are more careful out of self defensive instincts. That feedback loop reduces the ability of the disease to propagate. 

Does the underlying mathematics change for different viruses if a virus is more infectious or less infectious?

If you think about what this is doing, it just makes a person more able to protect themselves against the disease the same way that radar on an aircraft carrier makes the aircraft carrier more able to protect itself.

If there were more dots on the radar, it doesn't really matter what the dots are, all you're doing is seeing the dots.


Is there anything that there's anything that you wanted to mention that I hadn't asked?

The breakthrough is that we've actually found a way to realign incentives, so that actually the app is something that you want to use. But the only problem is that at the beginning, maybe no one's using it. It could be really useful for you, but there's no one around you're using it. So you need to just pass over this very low hump. The low hump is if we were using this to, for example, reopen schools, that's a really important thing right now, schools, how do you reopen schools safely? Well, one of the best ways to reopen schools safely is if you could give everyone a long range radar so that they could know when to be more protective of themselves as we start mixing all of the networks of all of our people in the city. Okay, in a school environment, yeah, when you get like 10% of the school on it, then suddenly, suddenly, you're past that hump. And everyone sees that, oh, if I joined the app, I'll have 1000s of people connected to me. 

This is an app where the usage snowballs all the way down? And if I want to contrast that, the way that people were trying to do this before, it's uphill all the way.