by Eric Byrd

A few years ago Slate's culture editor David Haglund posted a piece called “Marilynne Robinson, the Terrence Malick of the Literary World.” Malick and Robinson, he said, are kindred artists. They share a pattern of striking debuts, mid-career hiatus, and late fertility; also, an unfashionable theological seriousness, and a deep attention to the connectedness of all life, a view of nature as a “shining garment in which God is concealed and revealed.” After happening upon Robinson's 1989 polemic Mother Country: Britain, the Welfare State, and Nuclear Pollution at a time when I was obsessed with Malick's latest film (and his first set in the present of filming) To the Wonder, I would add that their similar preoccupation with wholeness means a similar horror at environmental pollution, and a desire to remind their audiences that, all being connected, those who exploit the environment exploit their fellow man; and that the immediate toxic aftermath, and the red-handed schemes of disposal, first harm the poor and powerless.

In Mother Country Robinson situates the blithe disposal of nuclear waste in the Irish sea and the contamination of Cumbria within Britain's tradition of “expropriation and immiseration” of its poor, from the Poor Laws, to the displacements of industrialization, to the contemptuous coercions of the welfare state. To the Wonder was filmed in Bartlesville, Oklahoma, a town in which Malick lived part of his childhood, a town on the edge of a contaminated zone that embraces northeastern Oklahoma, and parts of Kansas and Missouri. A century of unrestricted lead and zinc mining (privileged war industries, supplying lead shot for the Civil War and shell casings for the World Wars) resulted in generations of intellectually delayed or disabled schoolchildren, cancer-ridden adults, and a landscape undermined by excavations and dotted with “chat piles,” hillocks of granular lead-laced waste on which miner's families used to picnic. Ben Affleck's character, Neil, an environmental scientist, is shown climbing one. Within the zone, Picher, Oklahoma, was in 2009 entirely abandoned – its 1,600 residents paid to leave – and now stands as a ghost town. Robinson was born and raised in Sandpoint, Idaho, near the Coeur d'Alene Basin, another condemned zone of lead-zinc mines.

To the Wonder is so exciting a development because it is a masterful integration of the autobiographical past and the social present. On first viewing I thought it was about hydraulic fracturing, “fracking” – which it is. Past pollutions inform ours. In the United States, for the sake of “energy independence” state governments, with the tacit approval of the Federal, are knowingly poisoning hundreds of rural communities. One of the most striking sequences of To the Wonder is Neil's survey of an endangered neighborhood. His presence, and the invasive intimacy of his work – locks are snipped from young hair, and bagged as specimens; excavators claw the properties – draws a crowd, fearful, agitated, almost hostile. They are sick and want to know why. A priest played by Javier Bardem despairs before the diseased and immiserated flock.

Read more »

by Sabeen Mahmud

Twenty-four years ago, I fell in love for the first time—with a Macintosh Plus computer which profoundly altered the course of my life and was significant in shaping my anti-establishment, anti-war, pro-freedom worldview. It became an invaluable portal into myriad subcultures, from beat poetry to the Yippies, fuelled by the dark meanderings of Pink Floyd.

After college, I spent the next several years developing multimedia products, exploring the intersection between technology, art, literature, and music. But, by the mid-2000s, I was getting increasingly restless. Karachi was a cesspool of chaos. People were leaving in droves, our politicians continued to make promises they had no intention of fulfilling, and the country lurched from one military dictatorship to another. It was a depressing time and my first moment of existential crisis. Disillusioned, I agreed to an offer to move to Delhi.

Beginning to dream

Whilst waiting for my visa to come through, I started fantasizing. What would it take to create a space that espoused liberal, secular values through its programming and projects?

The next day, the conversation moved out of my head and onto a whiteboard. I sketched out a fantasy space: a large open courtyard for theatre, dance, spoken word and improv performances, readings, talks, and film screenings. All around the courtyard would be smaller rooms for workshops and events, a bookshop, a coffeehouse, studios for artists and designers, shops for artisans to showcase their work, and a bed-and-breakfast that would pull in some income to subsidize operations. With Rs. 12,000 (about US $113) in my bank account, I ran a check on the cost of land through my estate agent who gave a ridiculous, astronomical figure which paralyzed me into inaction for months.

Toward the end of 2006, I was walking up the stairs to my office and the penny dropped. I realized that the grownups were right: I should start small, test, and iterate. So, trained by those key people in my life – my mother Mahenaz and my mentor Zak, I took a leap of faith and relinquished my Dehli plan to cater to my lofty ambitions settling on an 1800 square feet office, with an open(ish) on the second floor of a building.

Finding some money

I had decided that this little social enterprise in the making was to be a not-for-profit venture and with that model, raising capital from investors or getting a bank loan approved was not an option. We had Rs. 1,000,000 (about US $9,400) stashed for my grandmother's health fund. With her consent, I used the money to get things going.

In January 2007, we christened The Second Floor (T2F). After some quick consultations and brainstorming, PeaceNiche was born and T2F became its first project.

The target launch date for T2F was set for May 2007.

Read more »

by Jonathan Kujawa

This spring I attended the annual meeting of the Mathematical Sciences Research Institute. While there I heard a fantastic talk by Dr. Holly Krieger about which I'd like to tell you. If you'd like to hear Dr. Krieger tell you herself, I highly recommend the Numberphile video she hosted. You can see it here.

Dr. Krieger works in the area of dynamic systems. Faithful 3QD readers will remember that we ran into this topic a few months ago when we talked about the Collatz conjecture and the mathematics of billiards (see here). Dynamical systems is the field which studies systems (the weather, the stock market, the hands on a clock, a ball ricocheting around a billiard table) which changes over time according to some rule.

A seemingly simple example of this is the Fibonacci sequence. You probably saw it as kid:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269,….

This is the sequence of numbers which starts with a 0 and 1, and then each subsequent number is the sum of the previous two: 0+1=1, 1+1=2, 1+2=3, 2+3=5, etc. To a mathematician this is a dynamical system. We can think of the nth number in the sequence as the state of the system after n seconds and the addition rule tells us how the system changes from one second to the next.

Last time we talked about dynamical systems we were interested in the question of whether such a system ever returns to its starting state. A properly working clock always ends up back where it was twenty-four hours ago. At the other extreme, the stock market will never end up back in the exact same state. Somewhere in the middle we have the billiard ball. It may or may not return, depending on the shape of the table and where you start the ball.

From this point of view the Fibonacci sequence is boring as all get out. It just gets bigger and bigger forever. But Dr. Krieger is the sort who isn't satisfied with such an answer. She asks questions like: You get a new number every time, but is it really “new” or “mostly old” [1]?

What do I mean? Well, we first need to recall the prime numbers. These are numbers like 2, 3, 5, and 7 which can't be evenly divided by another number (except 1 and itself, of course). On the other hand, 4, 6, 8, and 9 are not prime as they can be divided by 2's and 3's. That is, a non-prime can be written as a product of other numbers (like 24=4×6). If you keep subdividing you can eventually write any number as product of primes (like 24=2x2x2x3).

You should think of the prime numbers as the atoms of numbers: every number can be broken down into primes and you can't go any further. To stretch the analogy a little further, most folks are more excited when you discover a new atomic element than if you “just” discover a new combination of old elements. In the same spirit, you might think to ask if the Fibonacci sequence is made up of a few primes used over and over (like using 2 and 3 to make 6, 9, 12, 18, and 864), or if new primes are used as you go along.

Read more »

by Misha Lepetic

“A New Yorker is someone who longs for New York.”
~Anonymous

These days, when the inevitable question of “What do you do?” pops up at a cocktail party or some such, I now simply answer, “I live in New York.” A credulous follow-up might wish to clarify whether that is, in fact, how I make my living, at which point I try to steer the conversation to kinder, gentler topics. But after living in New York for 15 years, I feel my response is both perfunctory and justified. Anyone as deeply immersed in the city knows that living here really is its own, full-time occupation, since the city demands constant observation and reflection. And New York is especially amenable to this, given the breadth, density and accessibility of the city's neighborhoods, as well as New Yorkers' guileless embrace of real estate as a primary subject of conversation. It is perhaps the only city that I know of, where a stranger can walk into your apartment and ask, within the first 15 minutes, how much you rent pay for the privilege, and expect an answer.

In this vein, there has always been much talk about gentrification: where it is happening right now and where it will happen next, whether the desirability of the outcomes outweighs the costs, and, especially, who is being ousted. This last is not so much about the residents themselves, but rather the ongoing disappearance of beloved restaurants, bars and retail establishments, for example as documented by Jeremiah Moss's Vanishing New York. So what can be said about gentrification that has not already been said? Honestly, not a whole lot. There are still no good answers or responses, especially as New York reassesses its post-Bloomberg future.

However, gentrification has increasingly been treated as a monolithic concept, when in fact it is an umbrella term describing a continuum of variegated and uneven urban processes. The ‘improvement' of any neighborhood is the result of a bevy of actors, operating within a legal and social context that is unique to that neighborhood, and that itself sits within the larger context of the city and the state. Finally, even global financial circumstances play a role, for example, artificially low interest rates and the ease with which capital may travel. When gentrification is seen as a monolithic process, it is difficult to think about it as anything other than inevitable. But if we consider the different processes that are obscured into this single rubric, or more accurately, the different scales and velocities at which gentrification occurs, then we will be better equipped to engage the phenomenon itself, and not merely the label.

Read more »

The Simplicity of Objects or, How I learned to Love Kipple

by Tom Jacobs

They were the serious toys of the men who lived in the dead world of sunshine and rain he had left, the world that had condemned him guilty.

~ Richard Wright, “The Man Who Lived Underground” (1942)

Sometimes when I step from one room in my apartment into another room, I have the distinct sense that there is somehow more stuff than there was before. It’s as if a bunch of stuff has just magically appeared while I was gone for a few moments. Here is another book. There is another trinket or fossil or object of some small interest to me. Where did it all come from? I must have bought it. I suppose I did. Why? Hard to say. Loneliness? Personal fascination? What am I going to do with it? Not at all sure.

I will try to get around to reading the book but most of it is, in a purely technical sense, useless. It’s just stuff that I buy because I like to look at it and hold and feel the weight of it or because it gives me some small pleasure to be able to say I “own” it.

***

Kipple is useless objects, like junk mail or match folders after you use the last match or gum wrappers of yesterday's homeopape. When nobody's around, kipple reproduces itself. For instance, if you go to bed leaving any kipple around your apartment, when you wake up the next morning there's twice as much of it. It always gets more and more.

~ Philip K. Dick, Do Androids Dream of Electric Sheep

Back in the day when Don DeLillo was somewhat reclusive and not very public, I saw somewhere that he was going to give a talk about his new book, “Falling Man.” From the time I read “White Noise” in college, I realized this was a guy who got it. Or maybe it was just that I sensed that he was talking directly to me and that we shared a private sort of fraternity. I assume everyone has had this experience when an artist or a poet or a novelist seems to be speaking directly to you and without mediation. Even if they themselves weren’t aware of it, they are speaking directly and, slightly more dangerously for, you.

So I got to his speaking engagement about two hours early. In case you think ill of me, there was a dude who had gotten there even earlier than me, which I thought was crazy (who shows up two and a half hours early just to hear a dumb talk?). So we stood there, awkwardly together and alone. I don’t know why I didn’t engage him in conversation. I vaguely remember getting a strange vibe from him, though, and thinking, “how can DeLillo be speaking directly to both him and me both?” Then I noticed he had a paper bag full of first editions and realized that this guy was not someone who had read a passage of DeLillo’s and who had stared off the page with his mind boggling in recognition and admiration. This guy was a collector. Maybe that is why we didn’t speak to each other, although I am a kind of collector too.

Read more »

by Tamuira Reid

It is not important that you don't know why you cry anymore. That you just do. It is not important or monumental; just a part of your day like anything else. Like driving to the bank or picking up the dry cleaning.

It doesn't help to talk about it. To hear words slip out of your mouth like slow-running water. The geography of your body not a puzzle to solve.

It is not necessary to name names, to name the man that did it, to give first and last, age, occupation. To say he has blue eyes that can charm and pierce, soothe and destroy, make you shout out in anger, make you shrink and fold into yourself.

It is not necessary to pull it to the surface again, once more, all over. To sift through the memories like hands moving through soil.

It doesn't matter that you hurt then or you hurt now. That it started on a Tuesday. That he bought you a turtle. That he wasn't always bad. That the bedroom door was still open.

It doesn't matter what was on TV (was it the news?). That he was a drunk. That the sky was full of holes where birds should have been. That your hands were still child-like.

It is not necessary to point fingers. To wonder why you were the only one. It is not necessary to count the glow in the dark stars on your bedroom ceiling because they are gone now and you have your own apartment and there are no stars there.

The past is the past. It will stay there and you are here. You are moving forward in time. Those clothes don't fit you anymore. Your hair is longer. You had braces then and you don't now.

Read more »

by Jalees Rehman

Does morality depend on the time of the day? The study “The Morning Morality Effect: The Influence of Time of Day on Unethical Behavior” published in October of 2013 by Maryam Kouchaki and Isaac Smith suggested that people are more honest in the mornings, and that their ability to resist the temptation of lying and cheating wears off as the day progresses. In a series of experiments, Kouchaki and Smith found that moral awareness and self-control in their study subjects decreased in the late afternoon or early evening. The researchers also assessed the degree of “moral disengagement”, i.e. the willingness to lie or cheat without feeling much personal remorse or responsibility, by asking the study subjects to respond to questions such as “Considering the ways people grossly misrepresent themselves, it's hardly a sin to inflate your own credentials a bit” or “People shouldn't be held accountable for doing questionable things when they were just doing what an authority figure told them to do” on a scale from 1 (strongly disagree) to 7 (strongly agree). Interestingly, the subjects who strongly disagreed with such statements were the most susceptible to the morning morality effect. They were quite honest in the mornings but significantly more likely to cheat in the afternoons. On the other hand, moral disengagers, i.e. subjects who did not think that inflating credentials or following questionable orders was a big deal, were just as likely to cheat in the morning as they were in the afternoons.

Understandably, the study caused quite a bit of ruckus and became one of the most widely discussed psychology research studies in 2013, covered widely by blogs and newspapers such as the Guardian “Keep the mornings honest, the afternoons for lying and cheating” or the German Süddeutsche Zeitung “Lügen erst nach 17 Uhr” (Lying starts at 5 pm). And the findings of the study also raised important questions: Should organizations and businesses take the time of day into account when assigning tasks to employees which require high levels of moral awareness? How can one prevent the “moral exhaustion” in the late afternoon and the concomitant rise in the willingness to cheat? Should the time of the day be factored into punishments for unethical behavior?

Read more »

by Sue Hubbard

Read more »

by Yohan J. John

“Mine is a dizzying country in which the Lottery is a major element of reality; until this day, I have thought as little about it as about the conduct of the indecipherable gods or of my heart.”

–The Lottery in Babylon by Jorge Luis Borges

In his classic short story The Lottery in Babylon, Borges invites us to imagine a culture that valorizes randomness, institutionalizing it in an official lottery that entangles itself with every aspect of life, and even non-life. By situating this culture in Babylon, Borges frees himself to conjure up an alien way of life. And yet, as with all great speculative fiction, Borges also seems to be holding a mirror up to nature — a funhouse mirror that warps and amplifies features that we can discern even in our own culture. In his evocative and succinct way, Borges is perhaps hinting that we continue to live in that dizzying country in which randomness is a major component of reality.

The Indecipherable Gods

How long has randomness been an element in the periodic table of ideas? For ancient people, chance was wrapped up with the concepts of fate and divine will. “Divination” comes from the Latin for “to be inspired by a god”. For the Romans, chance or luck was personified by the goddess Fortuna. To tell a person's fortune was to determine the hidden intentions of Lady Luck. The ancient Chinese used yarrow stalks, coins, and dice when consulting the 4000-year-old I Ching, or Book of Changes. Divination either led to, or co-evolved with, games of chance. The earliest known board game is Senet, which was played by ancient Egyptians as early in the 30th century BCE. The game seems to have involved casting two-sided tokens. A 5000 year old backgammon set,complete with dice, was excavated at a site in Iran. Dice from 2000 BCE have also been found at sites that were part of the Indus Valley civilization [1].

Ancient peoples seem to have attached great meaning to chance events — even in the context of games. Confronted with the sheer unpredictability of nature, ancient people populated their pantheons with gods and demons who were capricious in the extreme. They seem to have believed that participating in chance events of their own invention could give them a glimpse into the otherwise inscrutable ways of divine beings [1]. Or perhaps they reasoned that they could become like gods through imitation of their ludicrous whims. The word “ludicrous”, incidentally, derives from the Latin root ludus,which means “game” or “play”. At some point in the past few hundred years,the word came to mean “ridiculous” — perhaps the Enlightenment made Europeans look unfavorably upon frivolity and play. There are streams within Hinduism, however, that preserve an echo of the ancient worldview — in some scriptures the universe is described as as lila, or divine play. The gods, according to this view, engage in creation and destruction for fun or sport. In India the term lila did not pick up any connotations of ridiculousness: it is a well-known theological concept, as well as a popular name given to girls.

In the modern world randomness typically connotes the very opposite of divine will — outside the world of gambling and gaming, a random event is often described as meaningless, and therefore only a source of inconvenience or tragedy. The ancients may have confronted chance with a more cheery attitude than is common today, but there is no suggestion that they were able to translate any intuitions derived from gambling (or fortune-telling) into a mathematical theory of chance. This hole in ancient knowledge is striking, because much of the mathematics required to begin the study randomness — simple arithmetic — was known to ancient cultures all over the world [2].

Order out of Chaos

The seeds of a mathematical approach to randomness were planted in the 16th century, when Europeans thinkers realized that chance events and processes were not completely devoid of order. This realization contributed to the emergence of two related but complementary mathematical approaches: probability and statistics. The theory of probability allowed people to uncover patterns in controlled settings, such as games of chance. Statistics allowed people to uncover patterns in more natural, uncontrolled settings, such as mortality tables compiled for insurance purposes.

Read more »

FIRE TREE

Tips of his mustache whip braided,
a turbaned invader four centuries ago
carried Persian saplings in a caravan
across the Himalayas to Kashmir.

“Our chinar will last a thousand years,”
my grandfather said as rustling boughs
reigned above the tin roof of the house
where I was born a Scorpio at midnight.

Every fall each leaf burst into a flower.
We gathered the remains of dyes
to create our rustic fuel for winter,
sprinkling water on burning leaves,

palms brushing light ashes together.
I packed fragile coal in a clay pot
matted in painted wicker, my kangri,
cloaking it between my knees

under a loose mantle, my pharun.
The ashes warmed my bag of bones.
I flew to the future of other worlds,
returning years later to see my father,

sun-withered, sipping his morning tea
alone beside an amputated trunk.
Last night I dreamt I went to Kashmir again.
I was being rowed in an embroidered shikara

to the Garden of Rajas who had vanished,
and the garden was a sea of hell; the tin roof
collapsed, our fire tree submerged, and
barrenness had become a thousand things.

by Rafiq Kathwari, Winner of the 2013 Patrick Kavanagh Poetry Award

by Ahmed Humayun

How should the West approach Islam? Sam Harris provides one answer in his book, The End of Faith (2004), a book ostensibly about the pernicious impact of religious faith. A bestseller, The End of Faith received glowing reviews in The New York Times and in many other publications. It has been characterized as a testament to the principles of liberalism, science, tolerance, and above all, reason. Over the last decade, Harris has made innumerable public appearances expounding on the threat posed by religion; in them, he tends to focus special attention on the threat posed by Islam to the West.

Let us examine what The End of Faith has to say on Islam [1]. Harris's overall argument is very clear and straightforward. According to him, the problem with the Muslim world is the ‘irrescindable militancy' of Islam [2], which has ‘all the makings of a thoroughgoing cult of death' [3]. Harris believes that the West is at war with Islam's core principles, a war it must win unless the religion is radically transformed (the latter possibility is highly improbable in his view).

Is Islam inescapably militant? How could one confirm one way or another? One way is to identify how many militants there are in the Muslim world. By one recent estimate, there are perhaps 106,000 militants around the world out of a population of 1.6 billion Muslims? [4]. Based on this simple metric, it would seem that the overwhelming majority of the world's Muslims want to live rather than join a cult of death, and seem to have chosen not to inflict crimes like terrorism and genocide.

How is it that the overwhelming majority of Muslims have been apparently unaffected by the inescapable militancy of their religion? Harris acknowledges that some moderates exist, but states that these Muslims are ignoring or overlooking their religion; in his public appearances, he sometimes calls them ‘nominal' Muslims. Their moderation, in his view, is in spite of their religion, not because of it. This response raises another question, however. How has Harris been able to distinguish ‘nominal' Islam from ‘genuine' Islam?

To see what I mean, consider an example that is dominating the news coming from the Middle East these days—the rise of the terrorist group ISIS, which has engaged in beheadings and slavery and conquered significant territory. Harris would say that ISIS is merely faithfully following Islam. Let us concede, for the sake of argument, that ISIS genuinely believes that its actions are fully justified by Islamic principles and Islamic law. What exactly would that prove? Not only are the overwhelming majority of Muslims not part of ISIS, but many Muslim clerics and scholars have denounced its actions as un-Islamic, and heavily cited the Islamic canon to make their case. [5] How does Harris know his view of Islam – which seems to be identical to the Islam of ISIS and of Al Qaeda and the rest of them—is the ‘correct' reading? The answer is simple: he does not know, but he wants us to accept on his authority that when Muslims commit crimes against humanity it is because of Islam, and when they don't, or when they condemn those crimes, it is because they ignore Islam.

Read more »

by Mara Jebsen

Woke up this morning, the moon wasn't right.

Woke up this morning, the moon wasn't right.

Sharp as a blade, and she slung to the right.

Woke up this morning, the moon wasn't right.

Carolina, I miss you, miss your crackle-whipped pines;

Miss your bread-rising breath, thick-sweet like old times;

And I miss your lying photographs, your freshly buried crimes.

Caroline, when the moon shines I miss you.

Shake loose the yam-dirt where the shadow lays down.

And wake the white girls in the colored gowns,

And wake the cruel and quiet towns,

Where the lace and knife lie mute.

And a long stare loops over miles of road

Faceless and numb as any old moon;

I don't want these dreams of blood and light;

Don't want this hanging in my doorless room.

Carolina. Carolina, stop all that howling,

Its getting too late–its a full, black morning–

You're strong, and you're safe–and you know

I can't fight you. But Carolina, tonight

Let me sleep without you.

by Lisa Lieberman

Hadn't there been something youthfully heartless in my enjoyment of the spectacle of Berlin in the early thirties, with its poverty, its political hatred and its despair?

Christopher Isherwood

The Weimar Republic is everybody's favorite example of liberalism gone wrong. Just a few days ago, The New Republic posted a reprint of Louis Mumford's essay, “The Corruption of Liberalism,” a call to arms first published in April 1940. “The isolationism that is preached by our liberals today means fascism tomorrow,” he warned.

Today liberals, by their unwillingness to admit the consequences of a victory by Hitler and Stalin, are emotionally on the side of “peace” — when peace, so-called, at this moment means capitulation to the forces that will not merely wipe out liberalism but will overthrow certain precious principles with which one element of liberalism has been indelibly associated: freedom of thought, belief in an objective reason, belief in human dignity.

Mumford attacked the complacency of American intellectuals who were blind to the “destruction, malice, violence” of the Nazi regime. He himself had been slow to recognize Hitler's barbarism, and chose to suspend judgement regarding the Soviet experiment for twenty years, but he now condemned liberal habits of mind for degrading America, sapping it of energy and the moral courage required to combat political extremism. By the end of the New Republic essay, he was advocating action, passion, and force as an alternative to the cold rationalism, tolerance, and open mindedness he blamed for “liberalism's deep-seated impotence.” In fact, this same accusation had already been leveled at the Weimar Republic by the Nazis, and in remarkably similar terms.

Exhibit A

Christopher Isherwood came to Germany in 1929 for one thing only: “Berlin meant Boys,” he confessed in his memoir. His friend Wystan (the poet W. H. Auden) had promised him that he would find the city liberating and so he did. Before the month was out, he'd gotten involved with a blond German boy, the very type he'd fantasized about meeting. In the stories he published in the mid to late 1930s, which would become the basis for the musical and film Cabaret, Isherwood was circumspect about his motivations, narrating events passively, as an outsider who observes but does not participate in the promiscuity he describes. Mind you, he did not judge his characters, at least, not for their sexual behavior. Some he found wanting for other reasons, for callousness or a lack of generosity toward others, for bad taste in clothes or furnishings.

By way of contrast, the Austrian writer Stefan Zweig was horrified by Weimar Germany.

Read more »

by Hari Balasubramanian

The Shortest Path

How does Google Maps figure out the best route between two addresses? The exact algorithm is known only to Google, but probably some variation of what is called the shortest path problem has to be solved [1]. Here is the simplified version. Suppose we have a network of nodes (cities, towns, landmarks etc.) connected by links (roads), and we know the time it takes to travel a particular link. Then what is the shortest path from a starting node A to a destination node D?

In the instance above, there are 4 nodes. The rectangles provide the link travel times. The B-C link takes 2 time units to travel; the A-D link takes 5; the C-D link takes 1; and so on. The five possible routes from A to D are: A-D; A-B-D; A-C-D; A-B-C-D; and A-C-B-D. The easily spotted shortest path is A-C-D, with a total length of 3. But what if a network has hundreds of nodes and links? It would be impossible to visually identify the shortest path. We would need an efficient algorithm. By that I mean an algorithm whose execution time on a computer stays reasonable even when the problem size – the number of nodes or links in the network – gets bigger.

In 1959, Edsger Djikstra published just such an algorithm. Djikstra's Algorithm doesn't simply look for all possible routes between the start and destination nodes and then choose the shortest. That kind of brute-force approach wouldn't work, given how dramatically the number of possible routes increases even with a slight increase in network size. Instead, Djikstra's Algorithm progressively explores the network in a simple yet intelligent way. It begins with the start node A, looks at all its immediate neighbors, then moves on to the closest neighbor, and from there updates travel times to all as yet unvisited nodes if new and shorter routes are discovered. I am fudging important details here, but this basic procedure of moving from a node to its nearest neighbor and updating travel times is repeated deeper and deeper in the network until the shortest path to the destination is confirmed. Wikipedia has a good animation illustrating this.

How fast does the algorithm run? Let's say there are V nodes. Then, in the worst case, Djikstra's Algorithm will take in the order of V x V steps to compute the optimal path. An algorithm like this that grows polynomially with the problem size is something we will call efficient (of course lower order polynomials, such as the square function, are preferable; V raised to the power 50 wouldn't be helpful at all). So a 10-node problem might take around 100 steps; a 1000-node problem will take 1000000 steps. This increase is something a modern day computer can easily handle. The algorithm might do much better in most instances, but the worst case is commonly used as a conservative measure of efficiency. There are faster variations of Djikstra's Algorithm, but for simplicity we'll stick to the original.

Read more »

Early Autumn Surf

…… it’s still

the birds have gone
knowing it’s time

but today is an anomalous summer day
which, breaking protocol,
has oozed into early fall
with temperate trappings
lulling me with spacious softness
and late brilliance,
being the last echo of July,
the final peal of August’s bell
expanding as I surf
down the hump of its luxurious waveform
under the comfort of its breaking curl
.

by Jim Culleny
9/27/14, 2:45

Photo and poem, shot
and jotted together