Month: December 2006

Infotopia

new research on GFN, information markets and bias amplification. a lot of it seems applicable to ed’s argumentarium, if it ever leaves the utopia it is at now.

if we can choose our own media, it’s possible we will use this power to insulate ourselves in an information cocoon, where we systematically avoid dissenting voices and have increasingly less common experience with our fellow citizens. Sunstein worries that a society of these isolated individuals will have difficulty participating in a democracy because citizens need a) some exposure to materials they would not have sought out and b) some common experience as a precursor for joint decision making.

SkySails

Putting a harness on ocean winds, a German shipping company plans to unfurl a giant high-tech kite over a cargo ship next year to boost the vessel’s propulsion and to conserve fuel.

the price is still too high, and too complicated to maintain, but how awesome is that? makes me wonder why they don’t put huge sails on the ship itself.

Friends, friendsters, and top 8

technology is sometimes an enabler for whole new levels of awkward.

“Are you my friend? Yes or no?” This question, while fundamentally odd, is a key component of social network sites. Participants must select who on the system they deem to be ‘Friends.’ Their choice is publicly displayed for all to see and becomes the backbone for networked participation. By examining what different participants groups do on social network sites, this paper investigates what Friendship means and how Friendship affects the culture of the sites. I will argue that Friendship helps people write community into being in social network sites. Through these imagined egocentric communities, participants are able to express who they are and locate themselves culturally. In turn, this provides individuals with a contextual frame through which they can properly socialize with other participants. Friending is deeply affected by both social processes and technological affordances. I will argue that the established Friending norms evolved out of a need to resolve the social tensions that emerged due to technological limitations. At the same time, I will argue that Friending supports pre-existing social norms yet because the architecture of social network sites is fundamentally different than the architecture of unmediated social spaces, these sites introduce an environment that is quite unlike that with which we are accustomed.

P != NP

can NP-complete problems be solved efficiently in the physical universe? All hunches would say no, but then we only discovered polynomial time factorization using quantum algorithms 10 years ago.

2011-08-12: Markets being efficient and P != NP can’t both be true, it turns out. So either you can compute fast or make money on the stock market. It remains unclear whether you can MAKE MONEY FAST or not.
2017-01-04: The history of P != NP

In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2017, for a broad audience of mathematicians, scientists, and engineers. I offer a personal perspective on what it’s about, why it’s important, why it’s reasonable to conjecture that P≠NP is both true and provable, why proving it is so hard, the landscape of related problems, and crucially, what progress has been made in the last half-century toward solving those problems. The discussion of progress includes diagonalization and circuit lower bounds; the relativization, algebrization, and natural proofs barriers; and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithms.

2022-12-03: Why are there complete problems, really?

This, then, is how universality of computation explains the existence of complete problems. For virtually any class we might define there will be a way of handicapping the universal computer such that it is still able to solve all of the problems in the class while at the same time not breaking the class specific resource constraint.

We can now see that the existence of complete problems is a direct result of one of the core features of computers that also makes them relevant to the real world.