Integer factorization and graph isomorphism are two common problems for which the best running time algorithm is not known for sure, and more and more complex algorithms achieve better and better running time. This combination of features seems to create a psychological barrier to including some implementation of such algorithms in a standard library. This is a shame because the there are algorithms that are barely super polynomial or work well for small instances.
Tuesday, December 16, 2014
Partition a region into N smaller regions minimizing the norm of a function F evaluated on each region.
Norm could be maximum, L-infinity norm.
F could be the radius of the circumcircle of the region. The center would be a good place to put the state capital.
Radius of the smallest circle which covers 90% of the area of the region. Or of the population.
The maximum distance between any two points in the region.
The same measures could be asked of partitioning a graph: the travel time graph formed by the network of roads, using graph centers and graph diameters. This will capture physical barriers across which travel is slow.
Unlike redistricting, there is no constraint of equal population nor equal area. The idea is a political region is defined by people moving around (or being able to move around) in it. If using the road graph, states will probably reflect the location of highways. Large chunks of the east coast might merge.
Monday, December 15, 2014
How many layers should a government have? Currently usually national, state, county, city.
Is there a principled way to answer this question? What powers should be assigned to each layer?
Federalism wants the things that personally affect you to not be distant government.
Create a sliding blocks app that is more meditative than a puzzle: all identical unit blocks, no goal. Sliding blocks of course works well for touchscreens.
Correlate feature 1 of individuals in a population against feature 2. Interesting is when the plot is not monotonic, e.g., forms a U or bell shape. The extremes are more similar than the middle.
When does this happen in society?
The upper classes feel secure in their position in society; the lower classes are resigned to it. The middle classes live in constant hope for promotion and fear of demotion.
Hypothesize that there will be such a U shaped correlation with attitudes toward sex. In particular, members of the upper and lower classes will remain in their respective social classes no matter whom they have sex with, so this model predicts that rape or consent is not a big deal to them, and it also explains their seemingly insensitive behavior: they are simply acting by the Golden Rule, doing unto others as they would have others do unto them. Meanwhile, those of middle class face drastic consequences of class demotion both for themselves and their descendants depending on whom and especially how much sex they have: "slut" is a label which reeks of low class. Thus this model predicts that those of middle class will care the most about consent and rape, as well as be the most likely to falsely accuse rape.
Consider packing N unit squares into a square of side 2 such that the small squares are orthogonal and centered at coordinates 0.5, 1, or 1.5.
0 squares = 1 possibility
1 square = 9 possibilities
2 squares = 8 + 4 + 2 + 2 = 16 possibilities
3 squares = 4 + 4 = 8 possibilities
4 squares = 1 possibility
Total = 35 ways including empty, a surprisingly large number.
Inspired by recursive characters.
In a column of water taller than 10.3 m and sealed at the top, a vacuum bubble will form at the top.
However, gases, e.g., oxygen, dissolved in the water will come out of solution and fill the vacuum. This will cause the water to become slightly depleted of gases. On the other end, exposed atmospheric air pressure, gases will diffuse into the depleted water.
Over time, the height of the water column will gradually fall as more and more air gets seemingly magically transported into the vacuum.
The vacuum will also get filled by water vapor.
Suppose a distributed social network in which your node obeys other nodes requests to delete mirrored data. Furthermore, let such data not be confined to the social network cache on your computer: you can export it out to your filesystem. Then, when a deletion request arrives, we need to find exported copies and delete them also. There needs to be some source tagging infrastructure built into the operating system or filesystem.
This gets especially hairy if the exported data has been subsequently modified or used to create other works. Should a derived work be deleted also? Automatic image, video, or text matching, or ask the human.
In another field, such thorough remote deletions could be evil, but these are always voluntary, friendly, the basis of the trust upon which the social network is built.
Sunday, December 14, 2014
The racist police are overseen by racist civilian governments which in a democracy have been elected by a racist populace. Trace exactly how mechanisms of power and procedure cause the "just a little bit" of racism of the populace to result in widespread police brutality against African Americans as well as other similar injustices of the justice system, most notably the disproportionate number of minorities incarcerated.
Is it the racism of the 1% of the populace that causes these outcomes, or that of the 99%? That is, if the 1% became not racist but the 99% continued to be so, would the world change? Or, if the 1% remained racist but the 99% became not racist, would the world change?
If it is the fault of the 1%, how do they achieve racist policies and what do they achieve with their racism? I speculate that they don't feel any race is inherently inferior to any other; rather, the 1% seek an orderly society, a maintenance of the status quo that helps them maintain their position in society. Racism is merely a symptom, perhaps an illusion, toward that more fundamental goal.
On the other hand, if it is the fault of the 99%, then this is a very unusual case of democracy obeying the will of the mass of the people, a distributed action achieving a dramatic effect despite no central coordination, no charismatic leader, no vast political movement or organization explicitly working for the goal of oppressing African Americans.
Inspired by hypocrisy of protesting recent police brutality, assuming it is the fault of the 99%. It is very easy to reveal most people's racist attitudes, and if the sum of those attitudes is the root cause of the brutality, then effort might be better spent changing oneself than protesting.
The most important documents are those which help you do something: mere information transforms into actions in the real world. Often it is how to replicate what someone else has done.
Wikihow is arguably more important than Wikipedia, but it is only a start.
Create processes and incentives for the creation of such documents and methods to identify which documents describe "how to" well.
Too often this kind of knowledge is only stored in some human's brain, and often there is incentive to keep it that way: it increases the value of the person who has the knowledge.
How well can a computer compose background, "accompaniment" music? A human gives a timeline of when the music should do what. Select from a library of styles.
Decrease the barrier to entry of creating documentaries. Background music is now fraught with copyright difficulties.
Create a tall cart with very small footprint for moving stuff. Perhaps a pair of six inch diameter wheels.
The goal is a cart the rough shape of a standing person will not have difficulty fitting in places designed for people.
The extremely tricky part is for it not to fall over: use Segway style self balancing. It might also need arms to hold on to things.
Although the self balancing is powered by an internal battery, the primary power of locomotion is a human pushing or pulling it by a handle probably attached to the base. This hopefully decreases the power requirements.
Get it to climb stairs and step over gaps. Perhaps a second set of wheels that move up and down.
Inspired by the difficulty of bringing a wireframe shopping cart on a crowded city bus. With the cargo packed into bags, the cart might look more like a coat rack on wheels.
Manually create an encoding of some data that is difficult for a computer to decode but easy for a human. Unlike the "completely automated" CAPTCHA, this Human Generated PTCHA requires human effort to create (so us not suitable for high volume), but is hopefully much harder for a computer.
"Pictionary" style drawings of a word
"Charades" style video acting of a word
"Taboo" style spoken descriptions of a word
Riddles and puns
Original motivation was to thwart large scale automated copyright lawsuits. Content is encrypted, actually merely obfuscated, with a key that is encoded in a HUPTCHA that is distributed with the content.
Avoid common DMCA takedowns for background music for a video.
The first d10 die is labeled 00 through 09. Another 10 through 19, etc.
It is easy to roll a large number of dice at once from a container, but, unless the dice are ordered in some way, not straightforward how to convert them to a string of digits. For the above set, put them in order numerically by first digit, then use only the last digit.
Coins can be easily ordered by value and with more difficulty by year though the year is often printed only on one side.
The way Chinese characters can be constructed by placing one or more other characters into a frame-like other character is an interesting way to encode arbitrarily large quantities of information, given enough resolution. It's not linear but a tree. Perhaps sentence syntax.
What are the leaves? What are the internal nodes (frames)?
Reminiscent of heraldry.
Various ways of stacking things and dividing up space. Constrain to avoid too extreme aspect ratio.
Consider the problem of launching a projectile as far as possible. A projectile encounters air resistance proportional to its cross sectional area. However, the air resistance affects the projectile as a proportion to its total momentum. Its total momentum is proportional to its mass, or its volume.
Given the difference between volume (growing by the cube of the linear dimension) and area (by the square), for a given velocity, density, and shape, a larger projectile will travel further. A denser projectile will travel further. For a cylindrical projectile that remains facing the correct direction (e.g., stabilizer fins), a longer projectile, having more mass but the same cross sectional area, will travel further.
Motivated by the question, how far can a trebuchet launch something? By the above analysis, there is no upper bound, so long as one can choose the shape and size of the projectile.
Friday, December 12, 2014
Input your (private) decryption key into your computer monitor. The computer sends encrypted data (probably from elsewhere) to the monitor, and the monitor decrypts and displays it. This avoids decrypted data ever being on the computer itself where malware could steal it.
Inspired by end to end encryption.
Monitors would have to function very differently, not merely dumping pixel rasters to the screen. Text only, or perhaps able to decode images specified by code on a virtual machine.
Cut and paste of the plaintext becomes impossible, which is a feature. The user must read the screen and retype the text.
Similar things could be done on the other end with a keyboard holding the (public) encryption key. The keyboard encrypts each keystroke and transmits the ciphertext to the computer. They keyboard is also connected directly to a monitor and transmits to it the plaintext keystroke, which the monitor renders. Because some of the keystrokes are backspace and cursor motion, the monitor must act like a text editor.
The recipient of the encrypted text will also receive all the keystrokes, including backspace and cursor movement, which will have to be rendered.
Essentially these are specialized air gapped computers.
Thursday, December 11, 2014
Suppose we raise the gasoline tax to fight climate change. This causes people to want to commute less, preferring to live in denser neighborhoods near their work, schools, and play.
However, density means you have to put up with other people. Density may bring to the forefront social discord which is currently kept under control by keeping the parties geographically separated. For example, the undesirable lower classes don't have to travel as far to harass the rich; the rich find it impossible to live peaceful lives without the poor intruding. Whites had originally fled to the suburbs to keep their children safe from blacks; if they move back, their children will become less safe in this regard. Pessimistically, such social discord may result in hugely costly conflicts (e.g., civil war, genocide) that outweigh the benefits of decreasing climate change.
How would basketball be different if the rim were higher, high enough that layups and dunks are impossible.
Would tall people's advantage increase or decrease? On one hand, there is no longer a need for a big center to do inside shots. In fact, shots from very close to the basket might become very difficult, requiring shooting straight up. On the other hand, it is remains advantageous to be taller than the other person when shooting or defending.
We could compensate for the higher basket making shots too difficult by making the rim larger.
When specifying a cipher, perhaps for a competition like AES, the submitter should enumerate tweaks to the cipher that are known to weaken it, especially tweaks that might be tempting but cause counterintuitive or non-obvious weaknesses. Other cryptanalysts can discover other such bad tweaks.
All this is a radical departure from current practice which seems to encourage ignorance about why a cipher is constructed the way it is, and implementors are strongly encouraged not to modify a cipher from its accepted design. An attitude of contempt seems to have become acceptable toward implementers making ad hoc modifications to a cipher: you're an idiot, and you're on your own with regards to cryptanalysis of your modified version. This contempt may also be connected to cults of personality around cipher designers. Such an atmosphere is toxic. Modifying a cipher to suit the needs of a given application is a worthwhile goal, so knowing what modifications are safe or unsafe is something the community should facilitate.