Monday, July 21, 2014

[ylklffys] Manipulating 2D images in 3D

Create an image manipulation tool that allows assigning 3 dimensional geometry to objects in the 2D image, manipulating those objects in 3D, then re-rendering the image.

For small manipulations, the assignment of geometry does not need to be very accurate.  Computer vision tools could give suggestions.  Not only geometry but also BRDF of materials and locations of light sources.

Designing the UI seems very challenging.

[sskskjas] Anti-hero as hero

Consider the anti-hero in the Deadpool, not Willy Loman, sense.  If such an anti-hero becomes popular in entertainment, what does it say about society?

There is a discrepancy between society's ideals of what it is supposed to want to be (the hero) and what it really wants to be (as reflected in the entertainment people like to consume).  Possibly a form of doublethink.

One can measure the size of the discrepancy by the amount of popular anti-heroes.  What is going on in a society with large discrepancy?  Is it unstable?

Sunday, July 20, 2014

[yetfzqgx] Chess with more pieces

On a regular chess board, the pieces initially occupy 1/4 of the squares, filling the first 2 ranks for each player.

To maintain the same initial density on a 12x12 board, there should be 3 full ranks of pieces per player.  4 ranks for 16x16 board, perhaps doubled pawns for everyone.  In general n=4k. (Though the pieces need not start on the back ranks.)

However, after exchanges and very low piece density on large boards, I suspect games become very difficult to win.  Shogi (dropping captured pieces as your own) maintains density.

[uzlnygdb] Fuzzy Run Length Encoding

Run length encoding seems like a hack in the context of data compression algorithms with probabilistic models underlying them, for example arithmetic or Huffman coding.  Is there an alternative which smoothly handles both streaky and not-so-streaky data?

Inspired by RLE as a preprocessing step in bzip2.

[zugbxeex] Compensating an externality

An entity wants to do an action that causes a negative externality.  The action is taxed at the precise amount of externality, causing a socially optimal amount of the action.  So far, so good.

The difficult problem is redistributing the tax revenues to compensate those negatively affected by the externality.  Moral hazard arises as the victims may choose not to take other actions themselves to minimize their negative effect.  Adverse selection arises when those who have the most to gain from compensation become, or remain, members of the victim class.  Corruption arises whenever there is a resource to be allocated.

A seemingly somewhat attractive solution is not to attempt to compensate the victims at all: the socially optimal amount of action has been induced, and that's good enough; contribute the tax revenue to the general fund.  However, I think the difficulty theoretically remains: in order to calculate the optimal tax rate, in order to calculate the value of the negative externality, we must determine who the victims are and how much they are hurt.

Friday, July 18, 2014

[gggpgqye] Narrow type signatures which can be widened

Create a tool to find type signatures that are less polymorphic than would be inferred by type inference.

This is a solution in search of a problem.

[qjdocsii] Child asking more questions

Give a person some information.  Under what conditions will the person discover the inconsistency within it, the paradox, the contradiction?

Will a child discover the inconsistency?

Adults tend not to question things, instead simultaneously holding contradictory things in their head: doublethink.

Thursday, July 17, 2014

[honvujwb] Three dimensional chess pieces

A color bound bishop in 3 dimensional chess can travel in 12 different directions, which ostensibly makes it more powerful than the rook, which can travel orthogonally in only 6 possible directions.  There then remains the 8 space diagonal directions.  Possibly assign them to the rook to increase its power beyond the bishop to keep the relative strengths in line with 2D chess.  We can't assign the space diagonals to the bishop or else the piece will no longer be color bound.

In higher dimensions more directions are possible.  I think it remains possible to assign color bound directions to the bishop and color changing directions to the rook.

In 2 dimensions, the knight can jump to the 5^2-2*3^2+1 = 8 squares in a 5x5 neighborhood that a queen cannot reach.  Extending to 3 dimensions, the knight can jump to 5^3-2*3^3+1 = 72 different cubes, making it a very powerful piece. In higher dimensions, the knight becomes relatively more powerful.

Wednesday, July 16, 2014

[rtgoouco] Preventing the recovery of widely disseminated information

A newspaper receives an important leak, so encrypts it then widely disseminates the encrypted leak over, say, Bittorrent as insurance against a raid confiscating the information.

A powerful adversarial agency raids the newspaper, confiscating all of its hard drives.  But we assume the decryption key is not lost.

Can a sufficiently powerful adversary realistically prevent the newspaper from ever reacquiring encrypted data?  At first glance, the adversary's task seems impossible -- that was the point of widely disseminating it -- but maybe it isn't.  Or at least, it might not be trivial for the newspaper to reacquire the data.

There remains a vague problem of defining just how much power the adversary has: let's say the adversary acts within U.S. Constitutional law providing freedom to the press to publish, but it is otherwise illegal for anyone else (e.g. couriers, ISPs) to transport the information, so it is grounds for seizure or filtering.

As a first step, we assume the adversary has enough power over the internet to shut down all the torrent seeders of the encrypted data.  It also shuts down anyone publishing the data over other public channels.

We also assume that the adversary has the ability to monitor and filter all communication channels to the newspaper, including private channels such as physical mail and couriers.

Steganography seems initially the most promising solution.  However, the abstract problem is, how can two parties who have never met agree on a steganographic scheme in the presence of an adversary trying to thwart such agreement?  The adversary eavesdropping on the negotiation of steganography could gain enough information to decode the steganography.  Furthermore, the recipient (the newspaper) doesn't know who the sender is, and the sender will probably be taking steps to remain anonymous.

One key piece, I think, is that the original encrypted data should also include a public key with which the sender can reencrypt the data (it becomes doubly encrypted).  This way, the adversary cannot easily tell if any data it intercepts is the encrypted blob it has authority to block.  It also provides a way for senders to securely communicate with the newspaper.

Tuesday, July 15, 2014

[ykvcpuku] Battlefront chess

Consider chess on a large square board.  Pawns are lined up near the middle of the board, separated by 4 ranks as in orthodox chess.  Immediately behind the pawns are the pieces of unspecified types.  Behind that is a large initially empty "back court".

A square board (in contrast to Capablanca's 10x8 board) preserves the particular geometry of corresponding corners: for example, rook pawns racing to promotion on opposite sides: the first pawn to promote to queen immediately attacks the promotion square of the other.

Initially placing the pieces quite forward instead of the back two ranks preserves the feeling of rapid engagement from orthodox chess.  The back court suggests a battlefield strategy of breaking through enemy lines.

The original inspiration was the long battle fronts of World War I.  Consider a huge square board with two large armies lined up almost toe to toe along an extremely long front stretching across the entire board.

We lose the feeling of a king remaining protected in the corner by a back rank and a shield of pawns.

Should pawns be permitted to move backwards to allow the formation of salients?

Previously vaguely similar.

[lefbbqna] Querying gender identity

Amongst the few or many choices given when asking for someone's gender identity is often a missing choice: "I do not consider gender an important part of my identity."

Of course, this is just the tip of an iceberg: what aspects of gender do you consider important or not important to your identity?  What likely matters is why the gender was being queried in the first place.

[wjolosht] Mine guitar tabs

Apply machine learning on a collection of guitar tabs to discover common chord patterns.  And genres of music.

[qaxitkjg] Pornographic reality show

Create a pornographic reality show, perhaps in they style of Big Brother.  A bunch of willing participants are instructed to have sex with each other, and the cameras roll constantly, everywhere.

Particularly interesting might be not the sex itself, but the process, vaguely courtship, by which people discover they are compatible, learn to become comfortable with each other, and (optimistically) set aside their differences in order to have good sex.

[kffnzfjy] Portal

Columbus's discovery of the New World and its subsequent settlement by Europeans is an event the likes of which will probably never be repeated again in human history.

Tell a story in which it is repeated.  This is a fairly common plot of science fiction or fantasy.

We discover a portal to another Earth in a parallel universe, populated at most with only an easily genocidable native population.

Thinking much bigger, we discover a way to create an infinite number of portals to an infinite number of such parallel Earths.  What happens when we become a civilization with essentially infinite land area and infinite resources?

Monday, July 14, 2014

[oxrcdchf] Evil real TSP

Physically construct a network of roads such that solving the traveling salesman problem on it solves an interesting problem, perhaps an instance of integer factorization or something cryptographic.

The original idea was to abuse the route planning algorithms in Google Maps solve interesting problems, albeit at rather high cost.

[ordsseav] Great circles dividing the earth

What great circles divide the earth's land area in half?


Monday, July 07, 2014

[gkxbatfk] Hitler as artist

Tell a fictional story in which Hitler never actually gave up his career as an artist: he just switched to a different medium, human blood, on a different canvas, the political landscape of the world.  The key idea is, some of his seemingly political and military decisions were influenced by artistic intent, trying to do something interesting or unprecedented.

Similar in spirit to The Joker in Batman.

Saturday, July 05, 2014

[bcbrnnnt] Spinning machine gun

Worst art project idea: a kinetic sculpture of a machine gun which continuously fires in random directions.  The mechanical engineering challenge is to use the kickback from each bullet firing to reposition the gun to point in a new, different, random direction.

Friday, July 04, 2014

[mvoghuaz] One-dimensional puzzle generator

Here is a one-dimensional jigsaw puzzle generator implemented in Haskell, creating one-dimensional instances of the exact cover problem.

For generation purposes, the one-dimensional field is divided into n blocks each of size b.  Each of the n pieces is roughly centered on a unique block and spans at most p blocks.  The arguments to the program are b p n.

Each generated piece is specified by a list of coordinates offset from its leftmost coordinate.  Each individual piece is typically not contiguous; that would make the puzzle trivial to solve. Solve the puzzle by finding the offset of each piece in the field so that the field is exactly covered by all the pieces.

There is a "edge effect" flaw such that pieces near the edge tend to span less than p blocks.

Example run with parameters 10 5 10:
Pieces are:

Solution is the concatenation of:

Motivation is to generate random inputs to Knuth's Dancing Links DLX algorithm.  What puzzle parameters generate difficult puzzles?

Wednesday, July 02, 2014

[spcidjpu] Compact images

Create a collection of nice looking computer-generated images such that the code to generate them is compact and the amount of computation per pixel is not much more than decoding compressed image file formats such as JPEG or PNG.  (So, no escape time fractals like the Mandelbrot set.)

The images are specified by code, perhaps on a virtual machine.  The images should be scalable to any size.  The images, as code, are compact both in disk space and computation time.

The motivation was an OS distribution wanting to provide a large collection of images for desktop backgrounds, but not wanting to spend a lot of space storing those images.  We also don't want to significantly increase the login or boot time generating the images.