Advancing the Free software movement

A few years ago, I thought the efforts regarding getting Linux to run really well on the desktop were not particularly interesting. I was wrong. It turned out a butterfly effect stemming from the OLPC and the MacBook Air (the former marginally related to Linux for everyday people, the latter completely unrelated) lead to the Asus Eee PC and netbooks all over, requiring an OS which was lightweight and useful, namely not Windows Vista. And thus Linux was brought to the mainstream, and with it (hopefully) the world-changing philosophy of the Free software movement. It turned out the key was not keeping-up-with-the-Joneses Mac Aqua or Windows Aero but something with low memory and CPU footprint.

I applaud everyone who called it right.

Inspiration: this article Windows 7: The Linux killer, by Preston Gralla

Security vulnerability regressions

Many security vulnerabilities do not have exploit code, so they cannot be added to a testsuite to ensure that they do not regress. One scenario is a security patch gets applied to the release branch for a quick patch release, but fails to be applied, or is misapplied, to the trunk.

A painstaking project would be to go back through every published vulnerability of a piece of software to see if it has regressed.

Nudity

Some people are nudist or exhibitionist. For others, public nudity is one of their most intense phobias. It's an extremely wide range of opinion, possibly not a bell curve. Why? Is it genetic? Environmental? If the latter, do parents have control over how the child will grow up to feel? If so, what parental actions induce each side? It's a little creepy that parents may define a such a profound psychological aspect of a child's personality. Which side leads a happier life? Intuitively, it would seem to be the side with one less phobia.

New operating systems

The hardest part of deploying a novel operating system is the zillion different combinations of hardware people want to run it on. This can be sidestepped for initial release by targeting a widely deployed single-hardware platform. The OLPC, game consoles (e.g., PS3) are two possibilities. The iPhone would be another, if it weren't locked.

JPEG interpolation

Re-sampling an image to make it larger is tricky. Use the JPEG DCT coefficients to construct a continuous function and sample that. It's not clear what to do in between 8-by-8 blocks.

Global cache

Many applications want to cache. Two are the web browser cache and the Freenet store. Others which want lower-than-regular-files priority to all available remaining disk space are virtual memory, scratch space (tmp), logs, and maybe the Apt cache and any other culprits in /var/cache.

It would be nice if these could all be managed globally and uniformly, with certain applications getting higher priority than others while still granting minima to those who need it. ionice as necessary.

A very large display

This idea was inspired by an art project: printing out (in lots of little sections to be pasted together) a satellite or aerial photograph image of an entire city and laying it out on a large flat surface like an aircraft hangar or (indoor) football field. Cover it with lamination or plexiglass. Walking over it makes people feel like a bird. Paper is still the most practical implementation of the idea.

On the other extreme in terms of price and practicality is a huge floor-sized display. Scaling 100 dpi to a 100 m by 100 m area is a 155 gigapixel display. A somewhat crude implementation could place lots of small displays next to each other, with ugly gaps between the displays, so not a continuous image.

Another implementation uses a few moveable or steerable projectors mounted above or below (better below to avoid shadows). The projectors track the person as they walk around the field and project the image just in the neighborhood where the person is.

With multiple people walking around, more projectors are needed.

Continuing the theme of locality, we can have a featureless arena and give each person a high resolution heads up display with head tracking. We want a heads up display that you can simultaneously see real reality and the projected virtual reality, rather than a completely immersive virtual reality. We want two people to be able to converge around the same spot, see each other, and be able to point and discuss a feature of the image.

The heads up display offers several advantages over previous ideas. The image may be projected to appear at waist or chest level rather than floor level. With sufficient resolution, we can maintain the illusion that the image continues far off rather than is just locally projected. The part of the image at a distance must be rendered to match the eye's focal distance, because you can see through the display to real people and objects in the "featureless" room.

The virtual environment has the additional feature that the image may be 3D, displaying building heights and topographical elevation. The initial physical (paper) model above can also do 3D with 3D printing, but it takes additional measures so that viewers will not crush the model or twist their ankles: load-bearing plexiglass, for example.

Network strace

Is there a tool like strace that instead logs all network activity on a per-application (per-process) basis? Monitoring at the network adapter requires separating out different streams.

What is my computer doing?

Is there a way I can get a running log of every process that is spawned (in Linux), and its parent process?

GNOME

GNOME is a horrible mess with security and privacy disasters waiting to happen. It is rare that I want applications to communicate with each other; and when I do, I'm satisfied with cut-and-paste or writing to a file from one application and reading from another. What's wrong with the "Recent Documents" menu item is not that it can't be turned off (it can't), but that it's possible even to engineer such a thing. I want to be able to insulate applications from the rest of the system.

Perhaps there is silver lining, though. If we force applications to go through GNOME to "do stuff", adding hooks into GNOME can monitor and sandbox applications to prevent them from doing bad stuff.

Hell and Heaven

What if one bit was flipped while transcribing a prophet, and our concepts of Heaven and Hell are actually reversed?

ark2 methuselah

This Conway game of Life pattern (probably) stabilizes at generation 8120878.

# ark2 -- 19 cells, stabilizes somewhere between 2^22 and 2^23 gens,
# found by Nick Gotts.
x = 53, y = 44, rule = B3/S23
50b3o28$12bo$12bo$13boo$15bo$15bo$15bo$15bo6$oo$bbo$bbo$3b4o!

The ark is a pair of switch engines leaving a considerable trail of debris. ("Two of everything"; perhaps that is why it is called "ark"?). It is a double-barreled backwards rake which continually perturbs the "tail" end of the debris trail.

A forward glider emitted by the debris "tail" collides with the ark at generation 4900986 in the neighborhood of (408454,408400). This kills half of the ark, converting it into a block-laying switch engine which (I think) escapes. Debris from this collision includes backwards gliders, one of which collides with another forward glider from the debris tail in the neighborhood of (401514, 401721) at generation 4932611 producing (via a pi heptomino) a small debris pile in that area. Another forward glider ("the last glider") from the tail collides with this small debris pile at generation 8120769 and everything stabilizes at 8120878.

There are other debris piles formed similarly, for example around (314700,314700) near generation 5700000, so there might be another glider bouncing up and down because of one, or another active debris pile, so I'm not completely sure that the pattern has stabilized.

Incidentally, the final "authentic" backward glider emitted by the ark rake reaches the tail at around generation 6526000.

? vector(30,j, matsolvemod(matrix(j,1,x,y,1), primes(j)~, vector(j,i,i-1)~)[1])

%55 = [0, -2, -8, 52, -788, -788, -210998, 4383592, -34415168, -703693778, 5765999452, 2211931390882, -138782093170508, -5006786309605868, -253579251611336438, -12551374903381164638, -142908008812141343558, 40235059344426324076912, -2891974474640747950504838, 169991099649125127278835142, -18242056294531940584645872728, -1443780877268247785856392194178, -85102544828125743391232590601558, -9165296078263504689482449202356418, 941584379775558526136539054851975982, -109725677889609325862012364017072315378, -1972624592757588213062518899061131219938, 861481022448550626004372260093860171043622, 67587260079918535402473915458935723029299842, 8739372161433421556929034933493037822954213972]

? vector(30,j, matsolvemod(matrix(j,1,x,y,1), primes(j)~, vector(j,i,i)~)[1])

%56 = [1, -1, -7, 53, -787, -787, -210997, 4383593, -34415167, -703693777, 5765999453, 2211931390883, -138782093170507, -5006786309605867, -253579251611336437, -12551374903381164637, -142908008812141343557, 40235059344426324076913, -2891974474640747950504837, 169991099649125127278835143, -18242056294531940584645872727, -1443780877268247785856392194177, -85102544828125743391232590601557, -9165296078263504689482449202356417, 941584379775558526136539054851975983, -109725677889609325862012364017072315377, -1972624592757588213062518899061131219937, 861481022448550626004372260093860171043623, 67587260079918535402473915458935723029299843, 8739372161433421556929034933493037822954213973]

Dense cluster of prime powers

[11^2, 5^3, 127, 2^7]

[121, 125, 127, 128]

Chinese remainder theorem

The Chinese Remainder Theorem provides an elegant way to uniquely "break down" a large integer into smaller integers by giving it modulo the first few primes. Here's everybody's favorite internet meme integer: 0 1 0 5 9 3 7 0 19 19 21 30 30 30 15 25 11 42 3 70 56 46 39 8 9 15

It's interesting that the product of the first 26 primes nearly equals 2¹²⁸. There are 26 letters in the alphabet, suggesting steganographic and mnemonic possibilities for a 128-bit key.

Using a denser set of 24 moduli, allowing prime powers:

matsolvemod(matrix(24,1,x,y,1), concat([2^6,3^4,5^2,7^2]~, vector(20,x,primes(24)[x+4])~), [0, 40, 15, 33, 9, 3, 7, 0, 19, 19, 21, 30, 30, 30, 15, 25, 11, 42, 3, 70, 56, 46, 39, 8]~)

Personal Server

With the proliferation of smart phones and netbooks, it's become more obvious that everybody needs his or her own personal server, serving two general purposes. The first purpose is to work around the limited capacity and power of the small mobile devices, for example, to hold your photo collection. Your netbook is often turned off, or out of network reception, so the second purpose is to maintain an online "presence" when you yourself are not actually online.

The oldest example is in fact e-mail, where it is desirable for someone to be able to send e-mail to you even if you are not online. Thus, your personal server acts as the recipient, holding the received message until you return online.

The lack of personal servers has resulted in privacy disasters such as Gmail and Facebook, which pay their bills by selling users' personal information to the highest bidder.

I believe that with technology and economies of scale, the price of these personal servers may be brought down to say $10.

There are many ways to build a personal server, ranging from an actual physical box that sits in your house to a virtual machine rented at a colo data center.

For a physical box, I'd recommend two things: offsite encrypted backups and two-port ethernet, one port to your modem, the other to your household router. It may be combined with the router, maybe wireless. This way, your personal router is directly accessible from the internet.

The key difference between a virtual machine in a colo and Gmail is in the former, you own and control your information, while in the latter, your private information is in the hands of someone else whom you don't know if you can trust to act in your best interests.

In these various implementations, most of the technology already exists, though it would be nice for prices to come down. One development I would still like to see is better process isolation in operating systems. Your personal server will have many daemons running. We need that if one daemon misbehaves, due to security compromise, or to resource contention, it will not affect other daemons or access unauthorized data on the server.

A large network of servers helps Tor. It is also necessary for some of the distributed applications I've proposed in this blog.

Game consoles are a good "entry point" for personal servers. Your personal server may do double duty as a game console.

Warn polymorphic

Give a list of all untyped polymorphic declarations.

Haskell

Reward the good banks, not the bad ones

The government shouldn't bail out failing financial institutions, for they deserve to face the consequences of their past actions. Instead, use the same money to shore up the financial institutions which are doing well -- hi, my name is Uncle Sam, and I'd like to open an account at your bank and make an initial deposit of $1 billion. These banks who are doing well (or doing better compared to the rest) are in such a state because of responsible lending and shrewd investment in the past which is the best indication available that they will continue such behavior on these new deposits. Even in the troubled economy, they are the ones most likely to figure out who to lend to and what to invest in, thawing the credit freeze in the market-optimal way.

The government may use its regulatory powers to discover which financial institutions are doing well.

Still image video compression

When compressing a video consisting of a constant image, i.e., a still image, which video codecs will eventually transmit enough information to reconstruct the image losslessly?

This is a desirable feature in a video codec. Compression is always a battle against the No Free Lunch Theorem, so there will always be something that any compression algorithm compresses poorly, either in quality or bitrate. This convergence-to-lossless feature allows a filmmaker a simple, albeit possibly awkward workaround at least for a still frame. I foresee one potential use being video which also encodes additional non-video digital data which may be extracted with a frame-grabber.

Free will

"Do we actually have free will?" is a stupid question.

The perception of free will is only what matters, because that will affect your actions. If you think you can make a difference in the world, then you will try. And it's pretty obvious that we perceive we have free will.

Inches and centimeters

Numerical curiosity

1/2.54 ≈ 393700/999999 ≈ sqrt(0.155)

sqrt(0.155)*999999 ≈ 393700.0000002

Noscript

Noscript is a fine Firefox extension, but the fact that such a byzantine (ever looked at its source code?) tool is needed indicates "something is wrong with the internet".

Four-color solitaire

I heard that part of the proof of the four-color theorem produced a set of maps which are fairly difficult (but of course still possible) to color. These can form a nice set of puzzles for humans. I'm imagining a mouse-clicking Flash or Java game.

If those don't work, three coloring is NP-complete, so challenging three-color puzzles may be designed. One may go to the extreme to design three-color map-coloring versions of various NP monetary prize problems: RSA factoring, Certicom ECC Diffie-Hellman, EFF Megaprimes, Eternity 2.

Cryptographic poker

Is it possible to play cryptograpically a game of imperfect and incomplete information without a trusted third party?

It is possible to flip a coin (incomplete information) over the phone.

Code show

A TV show based on the premise of some secret that the characters seek to discover through the entire course of the series. However, unlike similar shows such as Lost where the writers have plenty of leeway to make it up as they go along, in this show, the secret is, in principle, revealed to the protagonists and the audience at the beginning, but in code. The protagonists seek to uncover the secret directly via old-fashioned good-for-TV adventures, as well as another plot thread to try to crack the code by perhaps rubber-hose cryptanalysis, side-channel attacks, and other good-for-TV spy-versus spy-intrigue. In the process, other accessory coded messages also are discovered.

But the codes are real, and the keys get revealed in the series finale (or earlier for some accessory coded messages), so the audience is invited to play along to try to crack the codes and learn how the series will end before the end. Because the answer to the secrets are theoretically "out there" from the very beginning, the show's writers are constrained to remain consistent with the originally planned ending. I think this might prevent the show from becoming too outrageous.

Of course, it will take a lot of skill to encode a secret so it seems easy enough for the audience to try to decode it, but hard enough that it probably won't be decoded. The codes must also be a compelling enough part of the plot that the audience will be inspired to try to decode them.

I suggest modern ciphers and other cryptographic primitives just barely of reach at present, either theoretically or practically: SHA-1, reduced-round AES, RSA-800, elliptic curve cryptography, and all of the just-submitted entries for NIST's new hash function competition. Perhaps the desire to learn the fate of a pretty hero or heroine will inspire a significant cryptanalytic breakthrough. It would be interesting if a rival network manages to harness thousands of computers in order to ruin the ending and hurt the ratings of its competition.

Like plenty of other TV shows, it can have a web site. The web site may include an interface for online attacks, such as Adaptive Chosen Ciphertext. The characters in the show may break the fourth wall, stating that they are out of ideas, and they'll try posting the code on the internet in hopes someone will be able to break it.

The audience participation code breaking is only an ancillary part of the show. To the casual watcher it is simply an exciting mystery-adventure show that whenever they mention codes, the codes happen to be real.

Christmas lights crystal

A refractive and multiply beam splitting crystal that when a laser is shined into it, it projects a pretty design onto the facade of your house. You might get one custom-made so it matches outlines your windows and doors. Maybe three (RGB) lasers so all colors are possible.

Antidepressants

What can you learn from the percentage of a population or certain sub-population being prescribed antidepressants?

In prisons?

A cop show with a twist

Half the time it turns out a bad guy did it. The other half it turns out to be a crooked cop. Suspense until the very end. I'm not sure how easy it is to write plots like this.

x = 1/exp(x)

x=0.56714329040978

Found by idly bouncing between the e^x and 1/x buttons on a calculator.

Why buy American

The Chinese melamine and lead paint on toys fiascoes bring to light why Americans should buy American-made products.

American-manufactured products face American regulations, and those regulators are agents of "We The People" so they are theoretically acting in consumers' best interest. In practice, this may not be completely true, but there is hope of regulatory reform through our own elected Congress. In contrast, a foreign regulator of a foreign manufacturer, especially of a product primarily for export to the United States, has no perogative to look out for the best interests of American consumers. Furthermore, Americans have no recourse to change the foreign regulator's behavior.

The second reason to buy American is you can sue the manufacturer in American court if the need arises. We have a functioning justice system, complete with a jury of our peers, and a history of judgments against manufacturers when they deserve it. We have laws for class-action lawsuits and punitive damages. The threat of lawsuits induces American manufacturers to be careful not to poison their consumers.

In contrast, you could sue a foreign manufacturer in American court, but even if you win, the foreign manufacturer may never pay and there is nothing you can do about it, consequently the foreign manufacturer has no incentive to engage in practices that avoid lawsuits. You could sue the foreign manufacturer in foreign court and face a myriad of problems, including that a jury of THEIR peers might in fact find the manufacturer's behavior acceptable.

Other reasons I've heard for buying American have been for patriotic and altruistic reasons: save American jobs, for example. These annoy me as a free marketeer, but more importantly, it's hard for consumers to internalize such reasons to actually induce them into buying American.

The two reasons I have outlined above are internalizable by the consumer. The designation "Made in USA" is a designation of safety, that the manufacturer was under the auspices of American regulators, and faces lawsuits in American court if their product is unsafe. Thus, as a mark of safety, the consumer may decide whether the "Made in USA" product is worth the extra cost compared to a similar foreign-made product. "Is your baby going to ingest or lick this?" may be a relevant reason for a consumer to prefer a safer product.

Stopping botnets at home

A dongle, physically like a surge protecter, with two plugs: one plug is for the ethernet cable to the wall, the other to your computer. Or you can set it up with one plug going to your cable modem and the other going to your wireless router.

The dongle watches for botnet-like activity going across it; that is, it is checking if your computer is part of a botnet. For example, it sees if you are sending or posting spam, or are rapidly probing many other IP addresses for a vulnerability. Or the dongle calls home (be careful to avoid a DDOS attack -- use P2P) to see if your IP address is on any known botnet lists.

On detecting "bad" traffic, it notifies you only, perhaps by sounding an alarm, so there are no privacy problem, apart from the optional "calling home" feature.

Dongles should be government subsidized, and distributed by your ISP, because you using one causes a beneficial externality that benefits everyone else.

Wal-Mart

You would think that Wal-Mart, with all its supply-chain wizardry, could pull off not having supplies run out on Black Friday, thus shoppers need not stampede so ferociously to get in. One idea is simply to poll the shoppers in line before opening, and start deploying trucks even before opening to restock any anticipated undersupply.

And it's in Wal-Mart's best interest not to run out, to keep shoppers coming in all day. If they slightly overshoot on supply, they can still sell the product the rest of the holiday season.

Semi-market solution to the credit freeze

We dip a little into an authoritarian world: simply mandate that banks must lend a certain amount, perhaps a percentage of deposits.

It is up to them, i.e., the market, to discover the least risky borrowers to comply with the mandate.

The government must determine how much lending to mandate.

We might need to prevent banks from all lending to each other in a circle, although I've heard that the lack of interbank lending is part of the problem, so maybe this is not such a bad thing.

Technically, buying U.S. Treasuries counts as lending (lending to the very unrisky U.S. government). It might take some thought to assure ourselves that the market will sort itself out about this, via the price of Treasuries, or additional regulation might be necessary.

Presidents and postage

The price of first-class postage in cents and the number of Presidents we've had have intersected.

Nobel Prizes

You have to be alive to win the Nobel Prize, but until exactly what moment in time? When the Committee records its final vote? Or when the phone call from Sweden rings? What if time-of-death cannot be determined to sufficient precision? Perhaps you must be presumed to be alive just before the committee casts its final vote, but then, how diligently beforehand does the committee check?

...

In keeping with tradition, it would be funny if the medal itself for Chemistry were always presented in the form of a solution in aqua regia. When else do you get the opportunity to award a chemist a hunk of gold?

New adventures of Superman

No plot, just lots of special effects of an indestructible man of unlimited strength. The irreverence of Discovery Channel "blow shit up" type programing, except with Superman. "This week, we crash two semi-trailers head on, with Superman in the middle." "This week we drop Superman onto a neutron star. "

Limits of human experience

What are the limits of human experience? Pleasure (including sexual), pain, physical or mental exertion, intellectual or sensual novelty.

Hair in foam

It's interesting how hair can become embedded in foam so deeply that it can't be pulled out without breaking.

Earth-Moon tide system

The tides cause the day to become longer. The longer day causes the tides to happen less and less, so the rate at which the day gets longer itself slows down.

The energy lost on tides also causes the Moon to recede (this doesn't make sense to me: it should cost energy to boost the Moon to a higher orbit.) The farther Moon makes the tides weaker and also the moon orbital period increases, which changes the frequency of the tides.

All these effects are coupled. What are the dynamics and equilibrium solution, ignoring other external effects (Sun, Jupiter)?

Curve that bullet

The most natural Wii game ever would be one based on the movie "Wanted". The controller has an accelerometer (for curve) and trigger button. The IR position sensor can tell if the trigger was pulled at the right moment, when you aimed it correctly. Hopefully, the IR camera on the controller has a very fast shutter, or can interpolate from the blur it sees.

Computer statistician

You describe in natural language, ideally speech, what kind of data you have, and what you want to learn or test about it, and the computer gives you advice about what statistical tests you should try, or Google for to learn more about.

Circles game

A game based on drawing concentric circles with a stylus. Each new circle must be completely inside the previous. You get points for area, lose points for perimeter or some other measures of non-circularity, lose points for area you could have gotten but didn't, and get points for drawing the last successful small circle. This can be a two-player, multi-player, or solitaire game.

Bittorrent web browser

It seems very straightforward to add a Bittorrent client directly into a web browser. The OBJECT element in HTML provides enough rope to use Bittorrent. I'm imagining the most common use case to be embedding video into a web page.

We do need a new URI to invoke Bittorrent. I'm proposing btp1://URL#file, where "1" is the version number of the protocol to allow for future improvements, "URL" is the location of the .torrent file, with any pound signs and percent signs escaped (with percent hex) and "file" is the optional file within a multi-file torrent.

For truly huge torrents, recursive torrents may be specified with a btp1 URL for the inner URL, e.g., btp1://btp1://etc, with percent escaping as necessary.

Of course, the hard part is in the implementation in the browser. I imagine all the recent downloaded torrent contents are saved in the browser's LRU cache, and the torrents still in cache are all turned back on when the browser starts. The torrents get paused whenever the user is actively downloading something else.

It would be nice if the internet, both within your home and the internet as a whole, had voluntary Quality Of Service implemented, so you could mark your background torrents as lesser priority.

Leading is a language

Leading, communicating dance moves in a partner dance, is a language, but not a spoken or written one. What is the syntax, and other linguistically important features?

64-bit Zobrist hashes insufficient?

As computers get faster, I worry that 64-bit Zobrist hashing may have too many collisions.

To be clear, there are two types of hash collisions. After calculating a 64-bit Zobrist hash, of course one does not use a full 2^64 entry hash table. Instead, one truncates, for example using "mod" to the size of the hash table, and collisions may result from the truncation. Such hash collisions may be detected by storing the key (the original 64-bit hash) at the hash table location.

The second, more fundamental collision, the one I am worried about, is that two different positions may have the same 64-bit Zobrist hash. This kind of collision will not be detected by the method above. Because of the Birthday Paradox, these collisions become likely after "only" 2^32 (four billion) positions, a number that fast computers these days are approaching (and surpassing) for the number of position evaluations per move. This is especially true in analysis, where you might leave your computer on all night evaluating a position, and it will rack up way more than 2^32 nodes evaluated.

The simple solution is to use a wider Zobrist hash, for example 128-bit.

Consultation Blitz

Yet another chess variant: Consultation blitz. Two teams of players play a rapid or blitz chess game. Effective team communication is key as the clock is ticking ticking ticking... is what you are about to say really worth the seconds it will take to express it? Furthermore, your opponents are just across the board and can hear what you say. (Another variant would have the teams in separate rooms submitting moves electronically.)