Cris Moore on computational complexity

Posted on October 23, 2015 by Sarah Shugars

I am very excited that Northeastern is hosting a series of lectures by Cris Moore of the Santa Fe Institute. Moore has his background in physics, but he has also distinguished himself in the fields of mathematics, computer science, and network science.

Basically, he knows pretty much everything.

He began his lecture series yesterday with a talk on “computational complexity and landscapes.” Exploring qualitative differences between different types of algorithms, he essentially sought to answer the question: why are some problems “hard”?

Of course, “hard” is a relative term. In computer science, the word has a very specific meaning which requires some history to explain.

In 1971, Stephen Cook posed a question which remains open in computer science today: if a solution to a problem can be (quickly) verified by a computer can that problem also be (quickly) solved by a computer?

This question naturally sorts problems into two categories: those that can be solved in polynomial time (P) and those for which an answer can be can be checked in polynomial time (NP for ” nondeterministic polynomial time”).

Consider the famous Bridges of Königsberg problem. Euler, living in Königsberg in 1736, wanted to find a path that would allow him to cross each of the city’s bridges exactly once without ever crossing the same bridge twice.

Now you may start to appreciate the difference between finding a solution and checking a solution. Given a map of Königsberg, you might try a path and then try another path. If you find that neither of these paths work, you have accomplished exactly nothing: you still don’t have a solution but neither have you proven that none exists.

Only if you spent all day trying each and every possibility would you know for certain if a solution existed.

Now that is hard.

If, on the other hand, you were equipped with both a map of Königsberg and a Marauder’s map indicating the perfect route, it would be relatively easy to verify that you’d been handed a perfect solution. Once you have the right route it is easy to show that it works.

Of course, if the story were that simple, “P versus NP” wouldn’t have remained an open problem in computer science for forty years. Euler famously solved the Bridges of Königsberg problem without using the exhaustive technique described above. Instead, in a proof that laid the foundations of network science, Euler reduced the problem to one of vertices and edges. Since the connected path that he was looking for requires that you both enter and leave a land mass, an odd number of bridges meeting in one place poses problems. Eventually you will get stuck.

In this way, Euler was able to prove that there was no such path without having to try every possible solution. In computer science terms, we was able to solve it in polynomial time.

This is the fundamental challenge of the P versus NP dilemma: a problem which initially appears to be “NP” may be reducible to something that is simply “P.”

There are many problems which have not been successfully reduced, and there’s good reason to think that they never will be. But, of course, this is the typical NP problem: you can’t prove all NP problems can’t be reduced until you exhaust all of them.

As Cris Moore said, “the sky would fall” if it turned out that all NP problems are reducible to P.

To get a sense of the repercussions of such a discovery: a problem is defined as NP-hard if it is “at least as hard as the hardest problems in NP.” That is, other NP problems can be reduced, in polynomial time, to NP-hard problems.

That is to say, if you found a quick solution to an NP-hard problem it could also be applied as a quick solution to every NP problem. Thousands of problems which currently require exhaustive permutations to solve could suddenly be solved in polynomial time.

The sky would fall indeed.

His lecture series will continue on Thursdays through November 12.

St. Frances X. Cabrini Scituate parish

Posted on October 15, 2015 by Sarah Shugars

I heard a story this morning which I had somehow missed or accidentally ignored. But it seems a story worth telling, so I wanted to share it here.

In 2004, the Catholic Archdiocese closed the St. Frances X. Cabrini Scituate parish. The parish was one of many to be closed in the upheaval following the sexual abuse scandal that rocked the Catholic church.

In announcing the closures, Archbishop Sean O’Malley – then just 6 months into his tenure in Boston – tried to paint an optimistic picture of the reorganization.

Right now, the main task on the minds of most of us, clergy and laity, is the process of reconfiguration of parish resources. This is a process that will affect all 357 parishes in the Archdiocese. This process is not just about closing parishes; it is about building a framework to strengthen and revitalize as we go forward together as a faith community. Yes, some parishes will close. Others will welcome parishioners from nearby areas. Still others will work to renew themselves as places of spiritual renewal and evangelization.

I was living near Boston at the time, and I remember it as difficult and emotional period for Catholics in my community. Not only were they coming to grips with the grim reality of abuse in their church, the reorganization forced many parishioners to leave the congregations they called home.

Many were not happy. Some communities fought back. I have a vague recollection of protests and court cases, but I hadn’t given it any thought for some time.

But the parishioners of Scituate haven’t forgotten. They are still protesting, now almost exactly 11 years later.

When I first heard that, I imagined some half-hearted protests. A fence full of protest signs, perhaps, or an occasional gathering of organizers strategizing protest tactics.

I would be wrong.

The partitioners in Scituate have been maintaining a 24-hour a day vigil continuously since their parish was closed. They have not backed down.

And, importantly, they have been doing this while maintaining a steadfast commitment to the practice of their spiritual beliefs. They continue to help those in need, supporting the local food pantry, collecting funds for communities facing crisis, making gift baskets for the sick, and more.

This action, impressively sustained for over a decade, is everything that a protest should be: clear in its purpose and enhanced by its tactics. These partitioners aren’t just arguing for the kind of community they want – they are showing the kind of community they can be.

Highly Recommended: Capra & Mattei’s “The Ecology of Law”

Posted on October 9, 2015 by David Bollier

An important new book offering a vision of commons-based law has just arrived! The Ecology of Law: Toward a Legal System in Tune with Nature and Community, argues that we need to reconceptualize law itself and formally recognize commoning if we are going to address our many environmental problems.

The book is the work of two of the more venturesome minds in science and law – Fritjof Capra and Ugo Mattei, respectively. Capra is a physicist and systems thinker who first gained international attention in 1975 with his book The Tao of Physics, which drew linkages between modern physics and Eastern mysticism. Mattei is a well-known legal theorist of the commons, international law scholar and commons activist in Italy who teaches at Hastings College of the Law in San Francisco, and at the University of Turin. He is also deputy mayor of Chieri in the northern region of Italy.

The Law of Ecology is an ambitious, big-picture account of the history of law as an artifact of the scientific, mechanical worldview – a legacy that we must transcend if we are to overcome many contemporary problems, particularly ecological disaster. The book argues that modernity as a template of thought is a serious root problem in today’s world. Among other things, it privileges the individual as supreme agent despite the harm to the collective good and ecological stability. Modernity also sees the world as governed by simplistic, observable cause-and-effect, mechanical relationships, ignoring the more subtle dimensions of life such as subjectivity, caring and meaning.

As a corrective, Capra and Mattei propose a new body of commons-based institutions recognized by law (which itself will have a different character than conventional state law).

It’s quite a treat to watch two sophisticated dissenters outline their vision of a world based on commoning and protected by a new species of “ecolaw.” Capra and Mattei start their story by sketching important parallels between natural science and jurisprudence over the course of history. Both science and law, for example, reflect shared conceptualizations of humans and nature. We still live in the cosmological world articulated by John Locke, Francis Bacon, Rene Descartes, Hugo Grotius and Thomas Hobbes, all of whom saw the world as a rational, empirically knowable order governed by atomistic individuals and mechanical principles. This worldview continues to prevail in economics, social sciences, public policy and law.

Networks and the Rise of the Medici

Posted on September 29, 2015 by Sarah Shugars

So, here’s a fun thing. In 1993 John Padget and Cristopher Ansell explored the social network of the great Medici family. with specific attention to the rise of Cosimo de Medici in 15th century Florence.

The paper, published in the America Journal of Sociology, is intended as a historical case study in a theoretical contradiction of state building: that founders cannot be both judge and boss. That is, a regime’s legitimacy hinges on “the conviction that judges and rules are not motivated by self-interest. Yet, a founder doesn’t want to give up control of their “organized creation.”

Cosimo’s leadership led to three centuries of Medici rule in Florence, begging the question – how did that happen?

Drawing on the “thorough and impressive work” of many historians of Florence, Padget and Ansell carefully reconstructed a network of elite families in Florence. Their data set included 215 elite families – where “family” is more akin to clan than household, and their network accounted four nine different types of connections including kinship as well as political, economic, and personal ties.

After disproving may common arguments for the Medici’s rise to power – it turns out they were just as wealthy as the “oligarchs” they displaced – Padget and Ansell turn to the network for possible explanations.

Their finding are remarkable. Looking at the political turmoil of the day, Padget and Ansell make a bold claim: “Rather than parties being generated by social groups, we argue, both parties and social groups were induced conjointly by underlying networks.”

Their analysis of the network provides some interesting insights into that claim:

The Medici party was an extraordinarily centralized, and simple, “star” or “spoke” network system, with very few relations among Medici followers: the party consisted almost entirely of direct tied to the Medici family. One important consequence for central control was that Medici partisans were connected to other Medici partisans almost solely through the Medici themselves. In addition, Medici partisans were connected to the rest of the oligarchic elite only through the intermediation of the Medici family. Medici partisans in general possessed remarkably few intraelite network ties compared to oligarchs, they were structurally impoverished. In such an impoverished network context, it is easy to understand how a solo dependence on a powerful family would loom very large indeed.

Meanwhile, the rival oligarch party was densely interconnect. But rather than leading to cohesive collective action, this caused conflict. “The oligarchs were composed of too many status equals, each with plausible network claims to leadership.” they explain.

These network structures had deep consequences for politics and power. Ultimately, along with the capable leadership of Cosimo, it was this structure which allowed for the Medici rise.

Data-ism

Posted on September 16, 2015 by Sarah Shugars

I had the opportunity today to hear a talk by Steve Lohr, New York Times technology reporter and author of the recent book, Data-ism: The Revolution Transforming Decision Making, Consumer Behavior, and Almost Everything Else.

Lohr said that “big data” is more than just a large collection of digital information, it’s a philosophical framework – a way of approaching the world. Big data, he said, allows people to see patterns in the world and to make better sense of the world around them.

Ultimately, he argued, big data is a revolution in decision-making.

This revolution can have many positive implications, making our lives simpler, faster, and better.

For example, according to Lohr, in 1880 the U.S. census took eight years to conduct. While the population swelled in 1890, this census took only a few weeks to complete. The difference was due to a technological innovation: the creation of a machine-readable punch card by a company that later became IBM.

Of course there are also possible pitfalls – one can imagine using big data to determine who gets a loan going terribly wrong. And, yes, this is something that “data science lenders” do, claiming that their methodology is more accurate than more traditional approaches.

Lohr was somewhat weary of these big data, automated, decision making processes, arguing that when data is used to make decisions affecting people’s lives, that process needs to be transparent.

But, he was more casual about the change than I might have thought. Perhaps it’s because he has covered technology’s evolution for nearly a decade, but – he was somewhat skeptical of concerns about privacy and the de-humanization of our lives.

Technology evolves and our mores will evolve with it, he seemed to say.

Lohr commented that when the handheld Kodak camera was originally introduced, it was seen as a invasion of privacy. Banned from beaches and the Washington monument, it was seen as a danger, a possible corrupting force.

Until privacy expectations evolved to meet the new technology.

Perhaps it is just nostalgia that makes us fear this brave new world.

It’s an interesting argument, and I think it’s good to be skeptical of our instinctual reactions to things. But pointing to the mistakes of our past fears seems insufficient – perhaps we should be more concerned with privacy, but have simply become slowly accustomed to not having it.

That could be a natural evolution, or it could be a slow degradation – with serious and lasting consequences.

Community and Family

Posted on September 15, 2015 by Sarah Shugars

My mother, an avid genealogist, was recently telling me just how homogeneous people used to be in many US cities.

I’d had a general sense that European-settled communities used to be more the same, with occasional waves of immigrants slowly being integrated into the society, but my mother pointed out a detail I’d previously overlooked.

Many small towns were also small families.

Especially as the United States was being settled, many communities were large enough to have a diverse gene pool, but small enough that marrying a cousin was common. In some communities, people weren’t even always aware of how closely they and their spouse were actually related.

Before you think about this too much – just reflect on the consequences: a dispute in the community became a dispute in the family; a fracture in the family became a fracture in the community.

These identities of family and community were far more intimately linked then I’d previously thought of — and probably more intimately linked than I’d like to think!

Who May Use the King’s Forest? The Meaning of Magna Carta, Commons and Law in Our Time

Posted on September 14, 2015 by David Bollier

The relationship between law and the commons is very much on my mind these days. I recently posted a four-part serialization of my strategy memo, "Reinventing Law for the Commons." The following public talk, which I gave at the Heinrich Boell Foundation in Berlin on September 8, is a kind of companion piece. The theme: this year's celebration of the 800th anniversary of Magna Carta and its significance for commoners today.

A video version of my talk can be seen here -- along with a talk on P2P developments by my colleague Michel Bauwens, and general discussion with the audience moderated by Silke Helfrich.

Thank you for inviting me to speak tonight about the 800^th anniversary of the Magna Carta and the significance of law for the commons. It’s pretty amazing that anyone is still celebrating something that happened eight centuries ago! Besides our memory of this event, I think it is so interesting what we have chosen to remember about this history, and what we have forgotten.

This anniversary is essentially about the signing of peace treaty on the fields of Runnymede, England, in 1215. The treaty settled a bloody civil war between the much-despised King John and his rebellious barons eight centuries ago. What was intended as an armistice was soon regarded as a larger canonical statement about the proper structure of governance. Amidst a lot of archaic language about medieval ways of life, Magna Carta is now seen as a landmark statement about the limited powers of the sovereign, and the rights and liberties of ordinary people.

The King’s acceptance of Magna Carta after a long civil war seems unbelievably distant and almost forgettable. How could it have anything to do with us moderns? I think its durability and resonance have to do with our wariness about concentrated power, especially of the sovereign. We like to remind ourselves that the authority of the sovereign is restrained by the rule of law, and that this represents a new and civilizing moment in human history. We love to identify with the underdog and declare that even kings must respect something transcendent and universal called “law,” which is said to protect individual rights and liberties.

In this spirit, the American Bar Association celebrated Magna Carta in 1957 by erecting a granite memorial at Runnymede bearing the words “Freedom Under Law.” On grand public occasions – especially this year – judges, politicians, law scholars and distinguished gray eminences like to congregate and declare how constitutional government and representative democracy are continuing to uphold the principles of Magna Carta. More about that in a minute.

The Midnight Drink of Paul Revere

Posted on September 9, 2015 by Sarah Shugars

I recently went on a walking tour of Boston’s North End. The dense, historically Italian community is on some of the oldest land in Boston.

Like many coastal cities in the U.S., the Boston we now know is mostly landfill. It used to be practically an island, connected to the mainland only by a narrow peninsula.

Silversmith and agitator Paul Revere was one of many notable residents of the North End, and it was from here he took is famous “midnight ride” – first taking a boat to Charlestown, then riding up the Mystic through Somerville, Medford, and on to Lexington.

But on this walking tour I was told a detail of that ride I hadn’t heard before. Revere and his companion, William Dawes Jr., were arrested before they made it to Concord because they stopped to have a beer.

Now, of course I had to look into a salacious comment like that.

I’m afraid I haven’t found as much clarity on the subject as I would like, but this is what I know:

On the night of April 18, 1775, British troops set out to arrest patriots Samuel Adams and John Hancock, who were staying in Lexington at the home of Reverend Jonas Clarke. Revere and Dawes set out to warn them and raise an alarm, Revere taking the now-famous northern route and Dawes taking a southern route through the “Boston Neck” (now Roxbury).

After arriving in Lexington, Revere and Dawes were joined by a third rider, Dr. Samuel Prescott, and the three decided to carry on to Concord where arms and munitions were stored.

This is where things get particularly fuzzy.

On the road to Concord, the three were confronted by British soldiers. Prescott either evaded capture or very quickly escaped. Dawes also seems to have escaped after Prescott, leaving only Revere captured. He seems to have been released sometime the next day.

But what was that about a beer?

According to some accounts, before heading on to Concord Revere and friends stopped at a tavern to “refreshid” himself. This “refreshid” can indeed be found in a letter from Revere recounting the experience.

While I was originally told, though, that he was arrested while having a beer – it does seem that the arrest came slightly thereafter.

And it was almost certainly an ale that Revere “refreshid” himself with. After all, drinking was quite common in colonial times, with many believing ale could make you healthy while (contaminated) water had the effect of making you sick.

So all this leaves only one question: if Revere, Dawes, and Prescott were all participants in this midnight ride, why does Revere get all the glory?

Published in 1860, Henry Wadsworth Longfellow’s “Paul Revere’s Ride,” is what made that rider famous than the others. The poem, you may know, is “less a poem about the Revolutionary War than about the impending Civil War — and about the conflict over slavery that caused it.”

With the goal of of support the Abolitionist cause, Longfellow choose Revere as the rider to highlight for one simple reason: his name rhymed better.

Why Is Market Fundamentalism So Tenacious?

Posted on August 19, 2015 by David Bollier

One of the great economists of the twentieth century had the misfortune of publishing his magnum opus, The Great Transformation, in 1944, months before the inauguration of a new era of postwar economic growth and consumer culture. Few people in the 1940s or 1950s wanted to hear piercing criticisms of “free markets,” let alone consider the devastating impacts that markets tend to have on social solidarity and the foundational institutions of civil society. And so for decades Polanyi remained something of a curiosity, not least because he was an unconventional academic with a keen interest in the historical and anthropological dimensions of economics.

As the neoliberal revolution instigated by Reagan and Thatcher in the 1980 has spread, however, Polanyi has been rediscovered. His great book – now republished with a foreword by Joseph Stiglitz – has attracted a new generation of readers.

But how to make sense of Polanyi’s work with all that has happened in the past 70 years? Why does he still speak so eloquently to our contemporary problems? For answers, we can be grateful that we have The Power of Market Fundamentalism: Karl Polanyi’s Critique, written by Fred Block and Margaret R. Somers, and published last year. The book is a first-rate reinterpretation of Polanyi’s work, giving it a rich context and commentary. Polanyi focused on the deep fallacies of economistic thinking and its failures to understand society and people as they really are. What could be more timely?

The cult of free market fundamentalism has become so normative in our times, and economics as a discipline so hidebound and insular, that reading Polanyi today is akin to walking into a stiff gust of fresh air. We can suddenly see clear, sweeping vistas of social reality. Instead of the mandarin, quantitative and faux-scientific presumptions of standard economics – an orthodoxy of complex illusions about “autonomous” markets – Polanyi explains how markets are in fact embedded in a complex web of social, cultural and historical realities.

Delusions of Genocide & the Real Thing

Posted on August 16, 2015 by ETW

On returning home from Germany, I was startled to hear a voicemail from a white supremacist campaigning for President. It repeated the old trope that there is a genocide being perpetrated on the white race. In the United States, we often throw around words like “Nazi” and “genocide.” Seinfeld’s funny “Soup Nazi” story is one thing, but ridiculous demonizing of political opposition is another. The Iowa Tea Party offered one blatant example, but so do national commentators warning of “liberal fascism” or labeling conservatives “Nazis.” We should sober up and remember what real genocide looks like.

Some of the ovens made to dispose of bodies at the Dachau concentration camp.

In Democracy and Leadership, one of the key virtues of democratic leadership I wrote about is moderation. Today people so often dismiss moderation, seeing it as a weakness of will, as a lack of principled character. I find that view tragic, as it inspires such polarization that even the Federal government was shut down in 2013, despite the fact that the world is watching and the credit rating for U.S. debt was downgraded in 2011. Unstable societies are risky investments, as are unjust societies.

Moderation proves to be one of the deepest challenges for democratic societies, I argued more recently in my forthcoming Uniting Mississippi. Moderation is the virtue that aims to achieve unity. If you can’t moderate differences, unified groups tear apart and become several, rather than one. At the same time, of course, there can be delusional, hateful, or simply ridiculous ideas about unity. One of them is the white supremacist’s outlook.

The white supremacist thinks that there’s a need for greater unity among white people as a race. It is one thing when a group has systematically been targeted and oppressed, such as in slavery, the Holocaust, or Apartheid. Such group solidarity in those conditions is understandable, for people need to express pride and unity in their identities as survivors of horrible atrocities and continuing prejudice. Even in such cases, however, no reasonable group calls for purity of its race. Only white supremacists believe that interracial marriage is a threat to a race.

A little over a week ago, I had the sobering opportunity to visit a real genocidal institution. The Dachau concentration camp was built for holding around 5-6 thousand imprisoned workers. By the end of World War II, it held 32,000. To deal with the mass of people and to quell their number, the Germans had created gas chambers, which could kill large groups at once. To avoid resistance to entering the gas chamber at Dachau, the Germans had labeled the door “Brausebad” – “Shower.”

Once people were killed, they were moved to the ovens, photographed in the featured image above. Part of what was so disturbing in all of this was the thoughtful reasoning that went into controlling people and disposing of them. To convince people that the “Brausebad” really was a shower, and not a gas chamber, the Nazis had installed false shower heads. For the visitors like myself, the covers were removed from many of the shower heads, revealing a closed cone above. There was no water pipe. This was simply the illusion meant to make it easier to slaughter people. Here is a photo of the covered and uncovered shower heads, side by side:

Having visited the truly disturbing and sobering Dachau camp, all I could think was that the white supremacists campaigning for President are tragically misguided and absurd. Some people are so lacking in sense that they actually believe that white folks are under threat as a group. The level of such nonsense is deeply saddening.

The call I received was eerie, partly because the voice didn’t sound quite right. It was a woman’s voice, and it was somewhat realistic, but you could tell that the message was one of those recordings generated by a computer voice – just a pretty good one. It read a message that began with formulaic language I have received before from white supremacists. It said that there are countries for these kinds of people and those, so there should also be countries for white people.

Adding to the absurdity of the call is the fact that the United States is a highly religious country. In fact, the Ku Klux Klan now denies that it is a hate group. They have long called themselves Christians. It is long past time to remind people that such views call for seeing all people as kin, as children of the same God. Using the Christian religion in service of hate or disunity is a gross perversion, yet as I have argued, even in the most religious state in the U.S., Mississippians are recalcitrant even when religious leaders call for progress and unity.

We need to take the aim of unity seriously. We need to stop using demonizing language lightly and foolishly. We also need more people to see the effects of such crazy polarization and disunity, which have led even to campaigns for the Presidency from white supremacists. We don’t need delusions of genocide, when there are disturbing and tragic examples of the real thing.

To close, I thought about sharing with you a photo of a mountain of dead, skeleton-thin bodies. Instead, I’ll leave you with a photo I snapped at the Jewish memorial at Dachau, which was immensely beautiful and moving for me.

Civic Studies

An intellectual community of researchers and practitioners dedicated to building the emerging field of civic studies

Category Archives: history