00:00:14.670
Okay, I know I have the afternoon slot, but it's like 2:50 and we have two more talks after this. I have 88 slides, so no pressure, no intimidation.
00:00:21.009
It's going to be fine. Hi everyone, let's do that again. My name is Vaidehi. You can find me most places on the internet as @vaidehijoshi.
00:00:34.590
I come to you from sunny Portland, Oregon, where I work at a company called Tilde. I think today is the last day I can say 'sunny Portland, Oregon,' because it's supposed to start raining tomorrow, and then it’s going to rain for six months.
00:00:48.010
But 'rainy Portland, Oregon' just doesn't have the same ring to it, so I prefer to say 'sunny Portland, Oregon.' At Tilde, I work on a product called Skylight, which is your favorite Rails profiler.
00:00:59.920
So, if you work on a Rails app and you're looking for a profiling service, come talk to me afterward. But when I'm not working on Skylight, I like to spend my free time writing. My background is not in computer science or tech; it's in writing.
00:01:19.330
I try to fuse the two together by doing a yearly project every year. I write once a week every year, and this is year three. This year, I decided I was going to teach myself computer science, which is a really big commitment.
00:01:46.180
I didn't know how big it would be in January, but the project is called Base CS, and it covers the basics of computer science. I write every Monday, which also leads me to think a lot about abstraction, theory, and applying it to practice.
00:02:09.670
Again, my background is not in CS, so I'm teaching myself as I go. The interesting thing is that if you come across a concept enough times, you start to see it everywhere. When Jeff asked me to talk about trust, I thought, 'Aha! I have to figure out how to connect this to computer science,' and I think I found a way.
00:02:48.150
The story of trust, as we know it in computer science and software, and in our entire tech industry, is actually a pretty old story. To tell this story, we have to go back in time to the year 1735, so I mean really back in time.
00:03:09.780
We need to go back to a town that was in medieval Prussia called Königsberg. It's not called Königsberg anymore, so you will have a hard time finding it on a map, but it used to be four different settlements.
00:03:22.560
The way the town was structured, there was a river called the Pregel River that ran through it. As time went on, those four settlements got turned into a single city. It became difficult for people in the city to cross from one side of the river to the other, so they built bridges.
00:03:47.270
They actually built seven bridges. I don't know why seven, but it ended up changing the course of history forever. The town of Königsberg eventually became the city of Königsberg. Residents would go on long walks in the evening and cross these bridges, which was probably a fun activity in 1735.
00:04:08.250
They came up with a really interesting game: you had to try to cross each of these seven bridges once and only once. The reason this game was so interesting was that no one in the town could seem to do it, and word spread to neighboring towns.
00:04:27.300
A mathematician from two towns away, named Carl Gottlieb Euler, heard about this game. He thought it was an interesting bridge problem, and he got a bit obsessed with it because he couldn’t solve it. As a mathematician, this drove him kind of mad.
00:04:52.990
He decided to rope his friend Leonard Euler into this. He wrote to Leonard, saying, 'Hey, this is a really interesting problem. Do you think you could solve it?' At first, Leonard thought it wasn’t worth his time, saying it was just a bridge problem.
00:05:19.270
But then, he also started thinking about it and realized he couldn't come up with an easy solution. He wrote back to Karl, saying, 'I know I said no, but this is really interesting. Why can’t I figure this out?'}.
00:05:52.630
Leonard Euler took his obsession and put it on paper, sketching out Königsberg, the land masses, and the bridges. He abstracted the problem of the bridges into something more mathematical, essentially laying the groundwork for the branch of mathematics we now know as graph theory.
00:06:45.620
Today, when we talk about graph theory, we're generally referring to two parts of a graph: nodes, which are points sometimes called vertices, and edges, which connect the nodes.
00:07:12.100
There are two types of edges: undirected edges, which allow movement between nodes in both directions, and directed edges, which have a defined flow—an origin and a destination.
00:07:51.960
The formal mathematical definition for a graph is G equals (V, E), where V is the set of vertices and E is the set of edges. For example, a simple graph with three nodes and three edges can be described in mathematical terms with a set of vertices like A, B, C.
00:08:09.610
The edges here would be unordered pairs if it's undirected; similarly, if it's directed, edges would have a directional flow. Another important concept in graph theory is the degree of a node, which tells you how many other nodes it is connected to.
00:09:04.420
For instance, if node A is connected to four other nodes, it has a degree of four; if another node is connected to only one other node, its degree is one.
00:09:30.529
Euler's main concern was finding paths between nodes. A path is essentially a way to get from an origin to a destination without repeating any vertices, which means crossing all the bridges and touching all the land masses without crossing any bridge twice.
00:09:50.310
Euler solved this problem cleverly by proving that it couldn’t be done, specifically by outlining the paths and the conditions under which they could be formed. Today, this is known as an Eulerian path.
00:10:33.180
The first rule for an Eulerian path is that all vertices must have a non-zero degree, meaning you must have connections. Secondly, in any graph, two vertices must have an odd degree because they can act as either the starting or ending point of your path.
00:11:08.589
Alternatively, all vertices could have an even degree, allowing the possibility to start and end at the same point. Euler proved that it was impossible to cross all the bridges without repeating them under these conditions.
00:12:02.100
His problem was significant not only for its complexity but also because it created a new branch of mathematics known today as graph theory. So what happened to Euler's findings? He paved the way for various applications in computer science.
00:12:41.340
For the past hundred years, graph theory has found some remarkable applications. One well-known example is the knight's tour on a chessboard, where the objective is to move a knight so that it touches every square without repeating a move.
00:13:21.020
Another interesting implementation can be seen in Rubik's Cube solutions. Every time you change a piece of the cube, you change its state. If you represent each state as a node in a graph, you can depict all possible states and transformations of the cube.
00:14:07.640
There have also been studies focusing on mapping all permutations of a 2x2 Rubik's Cube to find an optimal solution path, highlighting the enormity of advanced mathematical problems in computer science.
00:15:03.270
We can also look at Google's PageRank algorithm. This algorithm, responsible for Google's rise, analyzes and ranks web pages based on the number of links and the quality of those links.
00:15:55.030
What Google refers to as 'weighted graphs' evaluates how often a page is linked to, determining its importance. As you explore graph theory, you’ll notice its application in every click to a URL, as each link represents an edge in a graph.
00:16:32.460
Graph theory also permeates the field of bioinformatics, particularly in sequencing the human genome. To resolve the complexities of DNA sequencing—which often results in jumbled, overlapping segments of DNA—researchers applied concepts from graph theory.
00:17:21.010
They used a type of graph called the De Bruijn graph, pulling out overlaps while reconstructing the genome sequence. By employing graph theory, these researchers successfully sequenced the genome over two decades, proving its critical role in modern biology.
00:18:21.160
In a similar exploration, Harvard sociologist Nicholas Christakis studied how people influence each other within their social networks. He applied graph theory to measure connections and how they affect behaviors such as obesity and happiness.
00:19:13.790
His research revealed that individuals connected to others who were fit were also likelier to have a healthier lifestyle, demonstrating through a graph that human behavior is profoundly shaped by our networks.
00:19:59.640
Pop culture even intersects with this concept. The 'six degrees of Kevin Bacon' phenomenon stemmed from three college students joking about the idea of connecting actors back to Kevin Bacon, leading to an exploration of actor networks.
00:20:46.360
This notion highlights the concept of connectedness between people as it leads us to realize that when you add someone to your professional network, you're effectively creating a connection.
00:21:32.400
The sharing economy is a product of our interconnectedness, changing how humans transact with trust as the driving force. In instances such as Airbnb, evaluating measures of trust helps forge connections that might not have existed previously.
00:23:31.480
Interestingly, recent studies indicate a greater likelihood for job seekers in tech to secure employment through second and third-degree connections rather than directly through first-degree connections.
00:24:20.510
This phenomenon illustrates the fundamental impact that our networks have on our opportunities and lives, not just in personal relationships but also in how we choose governance, as reported in findings around election meddling.
00:25:18.790
In the context of Facebook's massive user database, algorithms play a role in connecting nodes—individuals—in conducts that affect society significantly. The reliance on mathematics can lead to difficulty discerning the presence of biases or inaccuracies, impacting how trust is placed.
00:26:09.300
Trust remains a complex mathematical problem, requiring human involvement to evaluate fairness, reliability, and potential biases in frameworks. Every time Euler faced a problem, he recognized that the necessary tools weren’t reliable enough, thus, creating innovative solutions that worked.
00:27:05.110
That leads to one last question—whatever happened to Königsberg? History has a humorous irony; after Prussia fell, Königsberg became part of Russia and endured destruction during World War II.
00:27:52.250
Following the destruction of many bridges during the bombings of World War II, what remains of Königsberg today is now known as Kaliningrad, and you’ll notice there are only five bridges. Ironically, now it is possible to form an Eulerian path within the city.
00:28:51.800
And for all the irony in history’s tale, I like to think that Euler would have gotten a kick out of that. Thank you.