Hyperuniformity Found in Birds, Math and Physics | Quanta Magazine

news org:mag org:sci popsci ideas concept conceptual-vocab discrete lattice nature visuo structure order-disorder distribution constraint-satisfaction embodied tcstariat moments chemistry interdisciplinary nibble org:inst physics

november 2017 by nhaliday

news org:mag org:sci popsci ideas concept conceptual-vocab discrete lattice nature visuo structure order-disorder distribution constraint-satisfaction embodied tcstariat moments chemistry interdisciplinary nibble org:inst physics

november 2017 by nhaliday

If Quantum Computers are not Possible Why are Classical Computers Possible? | Combinatorics and more

november 2017 by nhaliday

As most of my readers know, I regard quantum computing as unrealistic. You can read more about it in my Notices AMS paper and its extended version (see also this post) and in the discussion of Puzzle 4 from my recent puzzles paper (see also this post). The amazing progress and huge investment in quantum computing (that I presented and update routinely in this post) will put my analysis to test in the next few years.

tcstariat
mathtariat
org:bleg
nibble
tcs
cs
computation
quantum
volo-avolo
no-go
contrarianism
frontier
links
quantum-info
analogy
comparison
synthesis
hi-order-bits
speedometer
questions
signal-noise
november 2017 by nhaliday

::.Václav Havel.:: The Power of the Powerless/Havel's greengrocer

june 2017 by nhaliday

"The Power of the Powerless" (October 1978) was originally written ("quickly," Havel said later) as a discussion piece for a projected joint Polish Czechoslovak volume of essays on the subject of freedom and power. All the participants were to receive Havel's essay, and then respond to it in writing. Twenty participants were chosen on both sides, but only the Czechoslovak side was completed. Meanwhile, in May 1979, some of the Czechoslovak contributors who were also members of VONS (the Committee to Defend the Unjustly Prosecuted), including Havel, were arrested, and it was decided to go ahead and "publish" the Czechoslovak contributions separately.

Havel's essay has had a profound impact on Eastern Europe. Here is what Zbygniew Bujak, a Solidarity activist, told me: "This essay reached us in the Ursus factory in 1979 at a point when we felt we were at the end of the road. Inspired by KOR [the Polish Workers' Defense Committee], we had been speaking on the shop floor, talking to people, participating in public meetings, trying to speak the truth about the factory, the country, and politics. There came a moment when people thought we were crazy. Why were we doing this? Why were we taking such risks? Not seeing any immediate and tangible results, we began to doubt the purposefulness of what we were doing. Shouldn’t we be coming up with other methods, other ways?

"Then came the essay by Havel. Reading it gave us the theoretical underpinnings for our activity. It maintained our spirits; we did not give up, and a year later—in August 1980—it became clear that the party apparatus and the factory management were afraid of us. We mattered. And the rank and file saw us as leaders of the movement. When I look at the victories of Solidarity, and of Charter 77, I see in them an astonishing fulfillment of the prophecies and knowledge contained in Havel's essay."

Translated by Paul Wilson, "The Power of the Powerless" has appeared several times in English, foremost in The Power of the Powerless: Citizens Against the State in Central-Eastern Europe, edited by John Keane, with an Introduction by Steven Lukes (London: Hutchinson, 1985). That volume includes a selection of nine other essays from the original Czech and Slovak collection.

...

THE MANAGER of a fruit-and-vegetable shop places in his window, among the onions and carrots, the slogan: "Workers of the world, unite!" Why does he do it? What is he trying to communicate to the world? Is he genuinely enthusiastic about the idea of unity among the workers of the world? Is his enthusiasm so great that he feels an irrepressible impulse to acquaint the public with his ideals? Has he really given more than a moment's thought to how such a unification might occur and what it would mean?

I think it can safely be assumed that the overwhelming majority of shopkeepers never think about the slogans they put in their windows, nor do they use them to express their real opinions. That poster was delivered to our greengrocer from the enterprise headquarters along with the onions and carrots. He put them all into the window simply because it has been done that way for years, because everyone does it, and because that is the way it has to be. If he were to refuse, there could be trouble. He could be reproached for not having the proper decoration in his window; someone might even accuse him of disloyalty. He does it because these things must be done if one is to get along in life. It is one of the thousands of details that guarantee him a relatively tranquil life "in harmony with society," as they say.

Obviously the greengrocer is indifferent to the semantic content of the slogan on exhibit; he does not put the slogan in his window from any personal desire to acquaint the public with the ideal it expresses. This, of course, does not mean that his action has no motive or significance at all, or that the slogan communicates nothing to anyone. The slogan is really a sign, and as such it contains a subliminal but very definite message. Verbally, it might be expressed this way: "I, the greengrocer XY, live here and I know what I must do. I behave in the manner expected of me. I can be depended upon and am beyond reproach. I am obedient and therefore I have the right to be left in peace." This message, of course, has an addressee: it is directed above, to the greengrocer's superior, and at the same time it is a shield that protects the greengrocer from potential informers. The slogan's real meaning, therefore, is rooted firmly in the greengrocer's existence. It reflects his vital interests. But what are those vital interests?

...

Individuals need not believe all these mystifications, but they must behave as though they did, or they must at least tolerate them in silence, or get along well with those who work with them. For this reason, however, they must live within a lie. They need not accept the lie. It is enough for them to have accepted their life with it and in it. For by this very fact, individuals confirm the system, fulfill the system, make the system, are the system.

Live Not By Lies: http://www.orthodoxytoday.org/articles/SolhenitsynLies.php

- Alexander Solzhenitsyn

We do not exhort ourselves. We have not sufficiently matured to march into the squares and shout the truth our loud or to express aloud what we think. It's not necessary.

It's dangerous. But let us refuse to say that which we do not think.

This is our path, the easiest and most accessible one, which takes into account out inherent cowardice, already well rooted. And it is much easier—it's dangerous even to say this—than the sort of civil disobedience which Gandhi advocated.

Our path is to talk away fro the gangrenous boundary. If we did not paste together the dead bones and scales of ideology, if we did not sew together the rotting rags, we would be astonished how quickly the lies would be rendered helpless and subside.

That which should be naked would then really appear naked before the whole world.

So in our timidity, let each of us make a choice: Whether consciously, to remain a servant of falsehood—of course, it is not out of inclination, but to feed one's family, that one raises his children in the spirit of lies—or to shrug off the lies and become an honest man worthy of respect both by one's children and contemporaries.

The Kolmogorov option: http://www.scottaaronson.com/blog/?p=3376

As far as I can tell, the answer is simply: because Kolmogorov knew better than to pick fights he couldn’t win. He judged that he could best serve the cause of truth by building up an enclosed little bubble of truth, and protecting that bubble from interference by the Soviet system, and even making the bubble useful to the system wherever he could—rather than futilely struggling to reform the system, and simply making martyrs of himself and all his students for his trouble.

I don't really agree w/ this

http://www.orthodoxytoday.org/articles7/SolzhenitsynWarning.php

http://www.catholicworldreport.com/2015/07/08/revisiting-aleksandr-solzhenitsyns-warnings-to-the-west/

At first regarded as a hero by Americans, he eventually found his popularity waning, thanks in part to his controversial 1978 commencement address at Harvard University.

...

"Without any censorship, in the West fashionable trends of thought and ideas are carefully separated from those which are not fashionable; nothing is forbidden, but what is not fashionable will hardly ever find its way into periodicals or books or be heard in colleges. Legally your researchers are free, but they are conditioned by the fashion of the day. There is no open violence such as in the East; however, a selection dictated by fashion and the need to match mass standards frequently prevents independent-minded people from giving their contribution to public life."

“The press has become the greatest power within the Western countries,” he also insisted, “more powerful than the legislature, the executive and the judiciary. One would then like to ask: by what law has it been elected and to whom is it responsible?”

Our Culture, What’s Left Of It: http://archive.frontpagemag.com/readArticle.aspx?ARTID=7445

FP: You mention how 19th century French aristocrat, the Marquis de Custine, made several profound observations on how border guards in Russia wasted his time pushing their weight around in stupid and pointless ways, and that this is connected to the powerlessness that humans live under authoritarianism. Tell us a bit more of how this dynamic works in Russia.

Dalrymple: With regard to Russia, I am not an expert, but I have an interest in the country. I believe that it is necessary to study 19th century Russian history to understand the modern world. I suspect that the characteristic of Russian authoritarianism precedes the Soviet era (if you read Custine, you will be astonished by how much of what he observed prefigured the Soviet era, which of course multiplied the tendencies a thousand times).

...

FP: You make the shrewd observation of how political correctness engenders evil because of “the violence that it does to people’s souls by forcing them to say or imply what they do not believe, but must not question.” Can you talk about this a bit?

Dalrymple: Political correctness is communist propaganda writ small. In my study of communist societies, I came to the conclusion that the purpose of communist propaganda was not to persuade or convince, nor to inform, but to humiliate; and therefore, the less it corresponded to reality the better. When people are forced to remain silent when they are being told the most obvious lies, or even worse when they are forced to repeat the lies themselves, they lose once and for all their sense of probity. To assent to obvious lies is to co-operate with evil, and in some small way to become evil oneself. One's standing to resist anything is thus eroded, and even destroyed. A society of emasculated liars is easy to control. I think if you examine political correctness, it has the same effect and is … [more]

classic
politics
polisci
history
mostly-modern
eastern-europe
authoritarianism
communism
antidemos
revolution
essay
org:junk
government
power
reflection
clown-world
quotes
lived-experience
nascent-state
truth
info-dynamics
realness
volo-avolo
class-warfare
multi
domestication
courage
humility
virtu
individualism-collectivism
n-factor
academia
giants
cold-war
tcstariat
aaronson
org:bleg
nibble
russia
science
parable
civil-liberty
exit-voice
big-peeps
censorship
media
propaganda
gnon
isteveish
albion
identity-politics
westminster
track-record
interview
wiki
reference
jargon
aphorism
anarcho-tyranny
managerial-state
zeitgeist
rot
path-dependence
paleocon
orwellian
solzhenitsyn
fashun
status
usa
labor
left-wing
organization
intel
capitalism
competition
long-short-run
patience
food
death
Havel's essay has had a profound impact on Eastern Europe. Here is what Zbygniew Bujak, a Solidarity activist, told me: "This essay reached us in the Ursus factory in 1979 at a point when we felt we were at the end of the road. Inspired by KOR [the Polish Workers' Defense Committee], we had been speaking on the shop floor, talking to people, participating in public meetings, trying to speak the truth about the factory, the country, and politics. There came a moment when people thought we were crazy. Why were we doing this? Why were we taking such risks? Not seeing any immediate and tangible results, we began to doubt the purposefulness of what we were doing. Shouldn’t we be coming up with other methods, other ways?

"Then came the essay by Havel. Reading it gave us the theoretical underpinnings for our activity. It maintained our spirits; we did not give up, and a year later—in August 1980—it became clear that the party apparatus and the factory management were afraid of us. We mattered. And the rank and file saw us as leaders of the movement. When I look at the victories of Solidarity, and of Charter 77, I see in them an astonishing fulfillment of the prophecies and knowledge contained in Havel's essay."

Translated by Paul Wilson, "The Power of the Powerless" has appeared several times in English, foremost in The Power of the Powerless: Citizens Against the State in Central-Eastern Europe, edited by John Keane, with an Introduction by Steven Lukes (London: Hutchinson, 1985). That volume includes a selection of nine other essays from the original Czech and Slovak collection.

...

THE MANAGER of a fruit-and-vegetable shop places in his window, among the onions and carrots, the slogan: "Workers of the world, unite!" Why does he do it? What is he trying to communicate to the world? Is he genuinely enthusiastic about the idea of unity among the workers of the world? Is his enthusiasm so great that he feels an irrepressible impulse to acquaint the public with his ideals? Has he really given more than a moment's thought to how such a unification might occur and what it would mean?

I think it can safely be assumed that the overwhelming majority of shopkeepers never think about the slogans they put in their windows, nor do they use them to express their real opinions. That poster was delivered to our greengrocer from the enterprise headquarters along with the onions and carrots. He put them all into the window simply because it has been done that way for years, because everyone does it, and because that is the way it has to be. If he were to refuse, there could be trouble. He could be reproached for not having the proper decoration in his window; someone might even accuse him of disloyalty. He does it because these things must be done if one is to get along in life. It is one of the thousands of details that guarantee him a relatively tranquil life "in harmony with society," as they say.

Obviously the greengrocer is indifferent to the semantic content of the slogan on exhibit; he does not put the slogan in his window from any personal desire to acquaint the public with the ideal it expresses. This, of course, does not mean that his action has no motive or significance at all, or that the slogan communicates nothing to anyone. The slogan is really a sign, and as such it contains a subliminal but very definite message. Verbally, it might be expressed this way: "I, the greengrocer XY, live here and I know what I must do. I behave in the manner expected of me. I can be depended upon and am beyond reproach. I am obedient and therefore I have the right to be left in peace." This message, of course, has an addressee: it is directed above, to the greengrocer's superior, and at the same time it is a shield that protects the greengrocer from potential informers. The slogan's real meaning, therefore, is rooted firmly in the greengrocer's existence. It reflects his vital interests. But what are those vital interests?

...

Individuals need not believe all these mystifications, but they must behave as though they did, or they must at least tolerate them in silence, or get along well with those who work with them. For this reason, however, they must live within a lie. They need not accept the lie. It is enough for them to have accepted their life with it and in it. For by this very fact, individuals confirm the system, fulfill the system, make the system, are the system.

Live Not By Lies: http://www.orthodoxytoday.org/articles/SolhenitsynLies.php

- Alexander Solzhenitsyn

We do not exhort ourselves. We have not sufficiently matured to march into the squares and shout the truth our loud or to express aloud what we think. It's not necessary.

It's dangerous. But let us refuse to say that which we do not think.

This is our path, the easiest and most accessible one, which takes into account out inherent cowardice, already well rooted. And it is much easier—it's dangerous even to say this—than the sort of civil disobedience which Gandhi advocated.

Our path is to talk away fro the gangrenous boundary. If we did not paste together the dead bones and scales of ideology, if we did not sew together the rotting rags, we would be astonished how quickly the lies would be rendered helpless and subside.

That which should be naked would then really appear naked before the whole world.

So in our timidity, let each of us make a choice: Whether consciously, to remain a servant of falsehood—of course, it is not out of inclination, but to feed one's family, that one raises his children in the spirit of lies—or to shrug off the lies and become an honest man worthy of respect both by one's children and contemporaries.

The Kolmogorov option: http://www.scottaaronson.com/blog/?p=3376

As far as I can tell, the answer is simply: because Kolmogorov knew better than to pick fights he couldn’t win. He judged that he could best serve the cause of truth by building up an enclosed little bubble of truth, and protecting that bubble from interference by the Soviet system, and even making the bubble useful to the system wherever he could—rather than futilely struggling to reform the system, and simply making martyrs of himself and all his students for his trouble.

I don't really agree w/ this

http://www.orthodoxytoday.org/articles7/SolzhenitsynWarning.php

http://www.catholicworldreport.com/2015/07/08/revisiting-aleksandr-solzhenitsyns-warnings-to-the-west/

At first regarded as a hero by Americans, he eventually found his popularity waning, thanks in part to his controversial 1978 commencement address at Harvard University.

...

"Without any censorship, in the West fashionable trends of thought and ideas are carefully separated from those which are not fashionable; nothing is forbidden, but what is not fashionable will hardly ever find its way into periodicals or books or be heard in colleges. Legally your researchers are free, but they are conditioned by the fashion of the day. There is no open violence such as in the East; however, a selection dictated by fashion and the need to match mass standards frequently prevents independent-minded people from giving their contribution to public life."

“The press has become the greatest power within the Western countries,” he also insisted, “more powerful than the legislature, the executive and the judiciary. One would then like to ask: by what law has it been elected and to whom is it responsible?”

Our Culture, What’s Left Of It: http://archive.frontpagemag.com/readArticle.aspx?ARTID=7445

FP: You mention how 19th century French aristocrat, the Marquis de Custine, made several profound observations on how border guards in Russia wasted his time pushing their weight around in stupid and pointless ways, and that this is connected to the powerlessness that humans live under authoritarianism. Tell us a bit more of how this dynamic works in Russia.

Dalrymple: With regard to Russia, I am not an expert, but I have an interest in the country. I believe that it is necessary to study 19th century Russian history to understand the modern world. I suspect that the characteristic of Russian authoritarianism precedes the Soviet era (if you read Custine, you will be astonished by how much of what he observed prefigured the Soviet era, which of course multiplied the tendencies a thousand times).

...

FP: You make the shrewd observation of how political correctness engenders evil because of “the violence that it does to people’s souls by forcing them to say or imply what they do not believe, but must not question.” Can you talk about this a bit?

Dalrymple: Political correctness is communist propaganda writ small. In my study of communist societies, I came to the conclusion that the purpose of communist propaganda was not to persuade or convince, nor to inform, but to humiliate; and therefore, the less it corresponded to reality the better. When people are forced to remain silent when they are being told the most obvious lies, or even worse when they are forced to repeat the lies themselves, they lose once and for all their sense of probity. To assent to obvious lies is to co-operate with evil, and in some small way to become evil oneself. One's standing to resist anything is thus eroded, and even destroyed. A society of emasculated liars is easy to control. I think if you examine political correctness, it has the same effect and is … [more]

june 2017 by nhaliday

Edge.org: 2017 : WHAT SCIENTIFIC TERM OR CONCEPT OUGHT TO BE MORE WIDELY KNOWN?

may 2017 by nhaliday

highlights:

- the genetic book of the dead [Dawkins]

- complementarity [Frank Wilczek]

- relative information

- effective theory [Lisa Randall]

- affordances [Dennett]

- spontaneous symmetry breaking

- relatedly, equipoise [Nicholas Christakis]

- case-based reasoning

- population reasoning (eg, common law)

- criticality [Cesar Hidalgo]

- Haldan's law of the right size (!SCALE!)

- polygenic scores

- non-ergodic

- ansatz

- state [Aaronson]: http://www.scottaaronson.com/blog/?p=3075

- transfer learning

- effect size

- satisficing

- scaling

- the breeder's equation [Greg Cochran]

- impedance matching

soft:

- reciprocal altruism

- life history [Plomin]

- intellectual honesty [Sam Harris]

- coalitional instinct (interesting claim: building coalitions around "rationality" actually makes it more difficult to update on new evidence as it makes you look like a bad person, eg, the Cathedral)

basically same: https://twitter.com/ortoiseortoise/status/903682354367143936

more: https://www.edge.org/conversation/john_tooby-coalitional-instincts

interesting timing. how woke is this dude?

org:edge
2017
technology
discussion
trends
list
expert
science
top-n
frontier
multi
big-picture
links
the-world-is-just-atoms
metameta
🔬
scitariat
conceptual-vocab
coalitions
q-n-a
psychology
social-psych
anthropology
instinct
coordination
duty
power
status
info-dynamics
cultural-dynamics
being-right
realness
cooperate-defect
westminster
chart
zeitgeist
rot
roots
epistemic
rationality
meta:science
analogy
physics
electromag
geoengineering
environment
atmosphere
climate-change
waves
information-theory
bits
marginal
quantum
metabuch
homo-hetero
thinking
sapiens
genetics
genomics
evolution
bio
GT-101
low-hanging
minimum-viable
dennett
philosophy
cog-psych
neurons
symmetry
humility
life-history
social-structure
GWAS
behavioral-gen
biodet
missing-heritability
ergodic
machine-learning
generalization
west-hunter
population-genetics
methodology
blowhards
spearhead
group-level
scale
magnitude
business
scaling-tech
tech
business-models
optimization
effect-size
aaronson
state
bare-hands
problem-solving
politics
- the genetic book of the dead [Dawkins]

- complementarity [Frank Wilczek]

- relative information

- effective theory [Lisa Randall]

- affordances [Dennett]

- spontaneous symmetry breaking

- relatedly, equipoise [Nicholas Christakis]

- case-based reasoning

- population reasoning (eg, common law)

- criticality [Cesar Hidalgo]

- Haldan's law of the right size (!SCALE!)

- polygenic scores

- non-ergodic

- ansatz

- state [Aaronson]: http://www.scottaaronson.com/blog/?p=3075

- transfer learning

- effect size

- satisficing

- scaling

- the breeder's equation [Greg Cochran]

- impedance matching

soft:

- reciprocal altruism

- life history [Plomin]

- intellectual honesty [Sam Harris]

- coalitional instinct (interesting claim: building coalitions around "rationality" actually makes it more difficult to update on new evidence as it makes you look like a bad person, eg, the Cathedral)

basically same: https://twitter.com/ortoiseortoise/status/903682354367143936

more: https://www.edge.org/conversation/john_tooby-coalitional-instincts

interesting timing. how woke is this dude?

may 2017 by nhaliday

Talks

may 2017 by nhaliday

Quantum Supremacy: Office of Science and Technology Policy QIS Forum, Eisenhower Executive Office Building, White House Complex, Washington DC, October 18, 2016. Another version at UTCS Faculty Lunch, October 26, 2016. Another version at UT Austin Physics Colloquium, Austin, TX, November 9, 2016.

Complexity-Theoretic Foundations of Quantum Supremacy Experiments: Quantum Algorithms Workshop, Aspen Center for Physics, Aspen, CO, March 25, 2016

When Exactly Do Quantum Computers Provide A Speedup?: Yale Quantum Institute Seminar, Yale University, New Haven, CT, October 10, 2014. Another version at UT Austin Physics Colloquium, Austin, TX, November 19, 2014; Applied and Interdisciplinary Mathematics Seminar, Northeastern University, Boston, MA, November 25, 2014; Hebrew University Physics Colloquium, Jerusalem, Israel, January 5, 2015; Computer Science Colloquium, Technion, Haifa, Israel, January 8, 2015; Stanford University Physics Colloquium, January 27, 2015

tcstariat
aaronson
tcs
complexity
quantum
quantum-info
talks
list
slides
accretion
algorithms
applications
physics
nibble
frontier
computation
volo-avolo
speedometer
questions
Complexity-Theoretic Foundations of Quantum Supremacy Experiments: Quantum Algorithms Workshop, Aspen Center for Physics, Aspen, CO, March 25, 2016

When Exactly Do Quantum Computers Provide A Speedup?: Yale Quantum Institute Seminar, Yale University, New Haven, CT, October 10, 2014. Another version at UT Austin Physics Colloquium, Austin, TX, November 19, 2014; Applied and Interdisciplinary Mathematics Seminar, Northeastern University, Boston, MA, November 25, 2014; Hebrew University Physics Colloquium, Jerusalem, Israel, January 5, 2015; Computer Science Colloquium, Technion, Haifa, Israel, January 8, 2015; Stanford University Physics Colloquium, January 27, 2015

may 2017 by nhaliday

Clathrate gun hypothesis - Wikipedia

april 2017 by nhaliday

https://www.reddit.com/r/askscience/comments/4uus54/how_worried_should_we_be_about_the_clathrate_gun/

http://www.motherjones.com/environment/2013/08/arctic-methane-hydrate-catastrophe

http://nymag.com/daily/intelligencer/2017/07/climate-change-earth-too-hot-for-humans.html

https://www.theatlantic.com/science/archive/2017/07/is-the-earth-really-that-doomed/533112/

http://www.scottaaronson.com/blog/?p=3336

http://lesswrong.com/r/discussion/lw/on8/gas_hydrate_breakdown_unlikely_to_cause_clathrate/

http://www.realclimate.org/index.php/archives/2012/01/an-arctic-methane-worst-case-scenario/comment-page-2/

climate-change
environment
slippery-slope
complex-systems
hmm
oceans
wiki
reference
multi
q-n-a
reddit
social
discussion
news
org:mag
left-wing
science
org:nat
epistemic
prediction
critique
debate
futurism
risk
world
atmosphere
optimism
pessimism
tcstariat
aaronson
commentary
tails
extrema
adversarial
ratty
lesswrong
scitariat
org:bleg
nibble
org:local
http://www.motherjones.com/environment/2013/08/arctic-methane-hydrate-catastrophe

http://nymag.com/daily/intelligencer/2017/07/climate-change-earth-too-hot-for-humans.html

https://www.theatlantic.com/science/archive/2017/07/is-the-earth-really-that-doomed/533112/

http://www.scottaaronson.com/blog/?p=3336

http://lesswrong.com/r/discussion/lw/on8/gas_hydrate_breakdown_unlikely_to_cause_clathrate/

http://www.realclimate.org/index.php/archives/2012/01/an-arctic-methane-worst-case-scenario/comment-page-2/

april 2017 by nhaliday

Path integral formulation - Wikipedia

february 2017 by nhaliday

Scott Aaronson compared this w/ Schrodinger perspective in time complexity during that presentation on quantum supremacy

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-845-quantum-complexity-theory-fall-2010/lecture-notes/MIT6_845F10_lec04.pdf

physics
quantum
models
integral
feynman
mechanics
wiki
reference
nibble
multi
aaronson
tcstariat
time-complexity
simulation
quantum-info
ideas
tcs
volo-avolo
speedometer
questions
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-845-quantum-complexity-theory-fall-2010/lecture-notes/MIT6_845F10_lec04.pdf

february 2017 by nhaliday

mg.metric geometry - What is the best way to peel fruit? - MathOverflow

q-n-a overflow nibble math acm sublinear metrics metric-space proofs math.CO tcstariat arrows reduction measure math.MG similarity multi papers survey computational-geometry cs algorithms pdf positivity msr tidbits intersection curvature convexity-curvature intersection-connectedness signum

february 2017 by nhaliday

q-n-a overflow nibble math acm sublinear metrics metric-space proofs math.CO tcstariat arrows reduction measure math.MG similarity multi papers survey computational-geometry cs algorithms pdf positivity msr tidbits intersection curvature convexity-curvature intersection-connectedness signum

february 2017 by nhaliday

inequalities - Is the Jaccard distance a distance? - MathOverflow

february 2017 by nhaliday

Steinhaus Transform

the referenced survey: http://kenclarkson.org/nn_survey/p.pdf

It's known that this transformation produces a metric from a metric. Now if you take as the base metric D the symmetric difference between two sets, what you end up with is the Jaccard distance (which actually is known by many other names as well).

q-n-a
overflow
nibble
math
acm
sublinear
metrics
metric-space
proofs
math.CO
tcstariat
arrows
reduction
measure
math.MG
similarity
multi
papers
survey
computational-geometry
cs
algorithms
pdf
positivity
msr
tidbits
intersection
curvature
convexity-curvature
intersection-connectedness
signum
the referenced survey: http://kenclarkson.org/nn_survey/p.pdf

It's known that this transformation produces a metric from a metric. Now if you take as the base metric D the symmetric difference between two sets, what you end up with is the Jaccard distance (which actually is known by many other names as well).

february 2017 by nhaliday

big list - Overarching reasons why problems are in P or BPP - Theoretical Computer Science Stack Exchange

q-n-a overflow nibble tcs complexity algorithms linear-algebra polynomials markov monte-carlo DP math.CO greedy math.NT synthesis list big-list hi-order-bits big-picture aaronson tcstariat graphs graph-theory proofs structure tricki yoga mathtariat time-complexity top-n metabuch metameta skeleton s:*** chart knowledge curvature convexity-curvature

february 2017 by nhaliday

q-n-a overflow nibble tcs complexity algorithms linear-algebra polynomials markov monte-carlo DP math.CO greedy math.NT synthesis list big-list hi-order-bits big-picture aaronson tcstariat graphs graph-theory proofs structure tricki yoga mathtariat time-complexity top-n metabuch metameta skeleton s:*** chart knowledge curvature convexity-curvature

february 2017 by nhaliday

cc.complexity theory - The complexity of sampling (approximately) the Fourier transform of a Boolean function - Theoretical Computer Science Stack Exchange

q-n-a overflow tcs complexity quantum quantum-info sampling fourier boolean-analysis research aaronson tcstariat mathtariat hierarchy rand-complexity open-problems counting nibble questions

february 2017 by nhaliday

q-n-a overflow tcs complexity quantum quantum-info sampling fourier boolean-analysis research aaronson tcstariat mathtariat hierarchy rand-complexity open-problems counting nibble questions

february 2017 by nhaliday

COS 522: Complexity Theory - Spring 2007.

princeton course tcs complexity lecture-notes 👳 rand-approx approximation pcp rand-complexity coding-theory proof-systems random relativization boaz-barak tcstariat wigderson pseudorandomness crypto rigorous-crypto expanders boolean-analysis space-complexity unit p:** quixotic

february 2017 by nhaliday

princeton course tcs complexity lecture-notes 👳 rand-approx approximation pcp rand-complexity coding-theory proof-systems random relativization boaz-barak tcstariat wigderson pseudorandomness crypto rigorous-crypto expanders boolean-analysis space-complexity unit p:** quixotic

february 2017 by nhaliday

Lecture 11

january 2017 by nhaliday

In which we prove that the Edmonds-Karp algorithm for maximum flow is a strongly polynomial time algorithm, and we begin to talk about the push-relabel approach.

pdf
lecture-notes
exposition
optimization
algorithms
linear-programming
graphs
stanford
luca-trevisan
nibble
direction
stock-flow
tcs
constraint-satisfaction
tcstariat
january 2017 by nhaliday

Lecture 16

january 2017 by nhaliday

In which we define a multi-commodity flow problem, and we see that its dual is the relaxation of a useful graph partitioning problem. The relaxation can be rounded to yield an approximate graph partitioning algorithm.

pdf
lecture-notes
exposition
optimization
linear-programming
graphs
graph-theory
algorithms
duality
rounding
stanford
approximation
rand-approx
luca-trevisan
relaxation
nibble
stock-flow
constraint-satisfaction
tcs
tcstariat
january 2017 by nhaliday

computational complexity - What is the easiest randomized algorithm to motivate to the layperson? - MathOverflow

january 2017 by nhaliday

- volume of shape in R^n

- polynomial identity testing

q-n-a
overflow
tcs
algorithms
rand-approx
random
motivation
list
examples
aaronson
tcstariat
gowers
spatial
geometry
polynomials
teaching
nibble
- polynomial identity testing

january 2017 by nhaliday

cc.complexity theory - What's the "real" reason that IP=PSPACE is non-relativizing? - Theoretical Computer Science Stack Exchange

january 2017 by nhaliday

A: arithmetization

q-n-a
overflow
tcs
complexity
relativization
proof-systems
synthesis
tcstariat
algebraic-complexity
aaronson
no-go
space-complexity
nibble
january 2017 by nhaliday

Shtetl-Optimized » Blog Archive » Logicians on safari

january 2017 by nhaliday

So what are they then? Maybe it’s helpful to think of them as “quantitative epistemology”: discoveries about the capacities of finite beings like ourselves to learn mathematical truths. On this view, the theoretical computer scientist is basically a mathematical logician on a safari to the physical world: someone who tries to understand the universe by asking what sorts of mathematical questions can and can’t be answered within it. Not whether the universe is a computer, but what kind of computer it is! Naturally, this approach to understanding the world tends to appeal most to people for whom math (and especially discrete math) is reasonably clear, whereas physics is extremely mysterious.

the sequel: http://www.scottaaronson.com/blog/?p=153

tcstariat
aaronson
tcs
computation
complexity
aphorism
examples
list
reflection
philosophy
multi
summary
synthesis
hi-order-bits
interdisciplinary
lens
big-picture
survey
nibble
org:bleg
applications
big-surf
s:*
p:whenever
ideas
the sequel: http://www.scottaaronson.com/blog/?p=153

january 2017 by nhaliday

Dvoretzky's theorem - Wikipedia

january 2017 by nhaliday

In mathematics, Dvoretzky's theorem is an important structural theorem about normed vector spaces proved by Aryeh Dvoretzky in the early 1960s, answering a question of Alexander Grothendieck. In essence, it says that every sufficiently high-dimensional normed vector space will have low-dimensional subspaces that are approximately Euclidean. Equivalently, every high-dimensional bounded symmetric convex set has low-dimensional sections that are approximately ellipsoids.

http://mathoverflow.net/questions/143527/intuitive-explanation-of-dvoretzkys-theorem

http://mathoverflow.net/questions/46278/unexpected-applications-of-dvoretzkys-theorem

math
math.FA
inner-product
levers
characterization
geometry
math.MG
concentration-of-measure
multi
q-n-a
overflow
intuition
examples
proofs
dimensionality
gowers
mathtariat
tcstariat
quantum
quantum-info
norms
nibble
high-dimension
wiki
reference
curvature
convexity-curvature
tcs
http://mathoverflow.net/questions/143527/intuitive-explanation-of-dvoretzkys-theorem

http://mathoverflow.net/questions/46278/unexpected-applications-of-dvoretzkys-theorem

january 2017 by nhaliday

soft question - What notions are used but not clearly defined in modern mathematics? - MathOverflow

q-n-a overflow math list big-list discussion mathtariat tcstariat conceptual-vocab vague rigor nibble thinking definition clarity physics quantum iteration-recursion algebra fields math.CA math.NT structure logic proofs math.DS

january 2017 by nhaliday

q-n-a overflow math list big-list discussion mathtariat tcstariat conceptual-vocab vague rigor nibble thinking definition clarity physics quantum iteration-recursion algebra fields math.CA math.NT structure logic proofs math.DS

january 2017 by nhaliday

Shtetl-Optimized » Blog Archive » First they came for the Iranians

january 2017 by nhaliday

pretty damn shite situation

edit: Scott Aaronson got into a lengthy argument w/ Curtis Yarvin (Boldmug), lmao

Ratchets Within Ratchets: http://infoproc.blogspot.com/2017/02/ratchets-within-ratchets.html

https://twitter.com/turrible_tao/status/914583517157347328

https://archive.is/aBs6i

i remember on I think scott aaronsons blog? after trump won in the comment section mm was arguing w/ ppl and his most bombastic point was

if you dropped 19th century america in the ocean next to us and gave them wikipedia they would conquer us within the decade

which I remember being hilarious because it was p literally true

tcstariat
aaronson
academia
grad-school
policy
migration
trump
:/
yarvin
debate
poast
MENA
nibble
org:bleg
history
politics
polisci
culture-war
gnon
ideology
current-events
enlightenment-renaissance-restoration-reformation
identity-politics
multi
hsu
scitariat
commentary
links
quotes
dysgenics
straussian
twitter
social
discussion
backup
aphorism
gedanken
time
early-modern
usa
anglosphere
reflection
edit: Scott Aaronson got into a lengthy argument w/ Curtis Yarvin (Boldmug), lmao

Ratchets Within Ratchets: http://infoproc.blogspot.com/2017/02/ratchets-within-ratchets.html

https://twitter.com/turrible_tao/status/914583517157347328

https://archive.is/aBs6i

i remember on I think scott aaronsons blog? after trump won in the comment section mm was arguing w/ ppl and his most bombastic point was

if you dropped 19th century america in the ocean next to us and gave them wikipedia they would conquer us within the decade

which I remember being hilarious because it was p literally true

january 2017 by nhaliday

mg.metric geometry - How to explain the concentration-of-measure phenomenon intuitively? - MathOverflow

q-n-a overflow soft-question math geometry probability intuition tcstariat orourke concentration-of-measure dimensionality tcs math.MG random pigeonhole-markov nibble paradox novelty high-dimension s:** spatial

january 2017 by nhaliday

q-n-a overflow soft-question math geometry probability intuition tcstariat orourke concentration-of-measure dimensionality tcs math.MG random pigeonhole-markov nibble paradox novelty high-dimension s:** spatial

january 2017 by nhaliday

Computational Complexity: Favorite Theorems: The Yao Principle

january 2017 by nhaliday

The Yao Principle applies when we don't consider the algorithmic complexity of the players. For example in communication complexity we have two players who each have a separate half of an input string and they want to compute some function of the input with the minimum amount of communication between them. The Yao principle states that the best probabilistic strategies for the players will achieve exactly the communication bounds as the best deterministic strategy over a worst-case distribution of inputs.

The Yao Principle plays a smaller role where we measure the running time of an algorithm since applying the Principle would require solving an extremely large linear program. But since so many of our bounds are in information-based models like communication and decision-tree complexity, the Yao Principle, though not particularly complicated, plays an important role in lower bounds in a large number of results in our field.

tcstariat
tcs
complexity
adversarial
rand-approx
algorithms
game-theory
yoga
levers
communication-complexity
random
lower-bounds
average-case
nibble
org:bleg
The Yao Principle plays a smaller role where we measure the running time of an algorithm since applying the Principle would require solving an extremely large linear program. But since so many of our bounds are in information-based models like communication and decision-tree complexity, the Yao Principle, though not particularly complicated, plays an important role in lower bounds in a large number of results in our field.

january 2017 by nhaliday

ca.analysis and odes - Why do functions in complex analysis behave so well? (as opposed to functions in real analysis) - MathOverflow

january 2017 by nhaliday

Well, real-valued analytic functions are just as rigid as their complex-valued counterparts. The true question is why complex smooth (or complex differentiable) functions are automatically complex analytic, whilst real smooth (or real differentiable) functions need not be real analytic.

q-n-a
overflow
math
math.CA
math.CV
synthesis
curiosity
gowers
oly
mathtariat
tcstariat
comparison
rigidity
smoothness
singularity
regularity
nibble
january 2017 by nhaliday

(Gil Kalai) The weak epsilon-net problem | What's new

january 2017 by nhaliday

This is a problem in discrete and convex geometry. It seeks to quantify the intuitively obvious fact that large convex bodies are so “fat” that they cannot avoid “detection” by a small number of observation points.

gowers
mathtariat
tcstariat
tcs
math
concept
rounding
linear-programming
research
open-problems
geometry
math.CO
magnitude
probabilistic-method
math.MG
discrete
nibble
org:bleg
questions
curvature
pigeonhole-markov
convexity-curvature
january 2017 by nhaliday

fa.functional analysis - Almost orthogonal vectors - MathOverflow

january 2017 by nhaliday

- you can pick exp(Θ(nε^2)) ε-almost orthogonal unit vectors in R^n w/ probabilistic method

- can also use Johnson-Lindenstrauss

q-n-a
overflow
math
tidbits
intuition
geometry
spatial
cartoons
dimensionality
linear-algebra
magnitude
gowers
mathtariat
tcstariat
math.CO
probabilistic-method
embeddings
math.MG
random
separation
inner-product
nibble
relaxation
paradox
novelty
high-dimension
direction
shift
- can also use Johnson-Lindenstrauss

january 2017 by nhaliday

big list - Rigour leading to insight - Theoretical Computer Science Stack Exchange

q-n-a overflow tcs soft-question big-list list research confusion aaronson tcstariat synthesis rigor meta:math proofs liner-notes nibble quantum quantum-info the-trenches insight info-dynamics reason

january 2017 by nhaliday

q-n-a overflow tcs soft-question big-list list research confusion aaronson tcstariat synthesis rigor meta:math proofs liner-notes nibble quantum quantum-info the-trenches insight info-dynamics reason

january 2017 by nhaliday

Shtetl-Optimized » Blog Archive » Why I Am Not An Integrated Information Theorist (or, The Unconscious Expander)

january 2017 by nhaliday

In my opinion, how to construct a theory that tells us which physical systems are conscious and which aren’t—giving answers that agree with “common sense” whenever the latter renders a verdict—is one of the deepest, most fascinating problems in all of science. Since I don’t know a standard name for the problem, I hereby call it the Pretty-Hard Problem of Consciousness. Unlike with the Hard Hard Problem, I don’t know of any philosophical reason why the Pretty-Hard Problem should be inherently unsolvable; but on the other hand, humans seem nowhere close to solving it (if we had solved it, then we could reduce the abortion, animal rights, and strong AI debates to “gentlemen, let us calculate!”).

Now, I regard IIT as a serious, honorable attempt to grapple with the Pretty-Hard Problem of Consciousness: something concrete enough to move the discussion forward. But I also regard IIT as a failed attempt on the problem. And I wish people would recognize its failure, learn from it, and move on.

In my view, IIT fails to solve the Pretty-Hard Problem because it unavoidably predicts vast amounts of consciousness in physical systems that no sane person would regard as particularly “conscious” at all: indeed, systems that do nothing but apply a low-density parity-check code, or other simple transformations of their input data. Moreover, IIT predicts not merely that these systems are “slightly” conscious (which would be fine), but that they can be unboundedly more conscious than humans are.

To justify that claim, I first need to define Φ. Strikingly, despite the large literature about Φ, I had a hard time finding a clear mathematical definition of it—one that not only listed formulas but fully defined the structures that the formulas were talking about. Complicating matters further, there are several competing definitions of Φ in the literature, including ΦDM (discrete memoryless), ΦE (empirical), and ΦAR (autoregressive), which apply in different contexts (e.g., some take time evolution into account and others don’t). Nevertheless, I think I can define Φ in a way that will make sense to theoretical computer scientists. And crucially, the broad point I want to make about Φ won’t depend much on the details of its formalization anyway.

We consider a discrete system in a state x=(x1,…,xn)∈Sn, where S is a finite alphabet (the simplest case is S={0,1}). We imagine that the system evolves via an “updating function” f:Sn→Sn. Then the question that interests us is whether the xi‘s can be partitioned into two sets A and B, of roughly comparable size, such that the updates to the variables in A don’t depend very much on the variables in B and vice versa. If such a partition exists, then we say that the computation of f does not involve “global integration of information,” which on Tononi’s theory is a defining aspect of consciousness.

aaronson
tcstariat
philosophy
dennett
interdisciplinary
critique
nibble
org:bleg
within-without
the-self
neuro
psychology
cog-psych
metrics
nitty-gritty
composition-decomposition
complex-systems
cybernetics
bits
information-theory
entropy-like
forms-instances
empirical
walls
arrows
math.DS
structure
causation
quantitative-qualitative
number
extrema
optimization
abstraction
explanation
summary
degrees-of-freedom
whole-partial-many
network-structure
systematic-ad-hoc
tcs
complexity
hardness
no-go
computation
measurement
intricacy
examples
counterexample
coding-theory
linear-algebra
fields
graphs
graph-theory
expanders
math
math.CO
properties
local-global
intuition
error
definition
Now, I regard IIT as a serious, honorable attempt to grapple with the Pretty-Hard Problem of Consciousness: something concrete enough to move the discussion forward. But I also regard IIT as a failed attempt on the problem. And I wish people would recognize its failure, learn from it, and move on.

In my view, IIT fails to solve the Pretty-Hard Problem because it unavoidably predicts vast amounts of consciousness in physical systems that no sane person would regard as particularly “conscious” at all: indeed, systems that do nothing but apply a low-density parity-check code, or other simple transformations of their input data. Moreover, IIT predicts not merely that these systems are “slightly” conscious (which would be fine), but that they can be unboundedly more conscious than humans are.

To justify that claim, I first need to define Φ. Strikingly, despite the large literature about Φ, I had a hard time finding a clear mathematical definition of it—one that not only listed formulas but fully defined the structures that the formulas were talking about. Complicating matters further, there are several competing definitions of Φ in the literature, including ΦDM (discrete memoryless), ΦE (empirical), and ΦAR (autoregressive), which apply in different contexts (e.g., some take time evolution into account and others don’t). Nevertheless, I think I can define Φ in a way that will make sense to theoretical computer scientists. And crucially, the broad point I want to make about Φ won’t depend much on the details of its formalization anyway.

We consider a discrete system in a state x=(x1,…,xn)∈Sn, where S is a finite alphabet (the simplest case is S={0,1}). We imagine that the system evolves via an “updating function” f:Sn→Sn. Then the question that interests us is whether the xi‘s can be partitioned into two sets A and B, of roughly comparable size, such that the updates to the variables in A don’t depend very much on the variables in B and vice versa. If such a partition exists, then we say that the computation of f does not involve “global integration of information,” which on Tononi’s theory is a defining aspect of consciousness.

january 2017 by nhaliday

Patrick Collison on Twitter: "What's an obscure outlet or information source that you consistently find very interesting/valuable?"

twitter discussion social sleuthin tech stripe attention internet top-n list michael-nielsen 🖥 exploration-exploitation info-foraging techtariat signal-noise tcstariat

december 2016 by nhaliday

twitter discussion social sleuthin tech stripe attention internet top-n list michael-nielsen 🖥 exploration-exploitation info-foraging techtariat signal-noise tcstariat

december 2016 by nhaliday

gt.geometric topology - Intuitive crutches for higher dimensional thinking - MathOverflow

december 2016 by nhaliday

Terry Tao:

I can't help you much with high-dimensional topology - it's not my field, and I've not picked up the various tricks topologists use to get a grip on the subject - but when dealing with the geometry of high-dimensional (or infinite-dimensional) vector spaces such as R^n, there are plenty of ways to conceptualise these spaces that do not require visualising more than three dimensions directly.

For instance, one can view a high-dimensional vector space as a state space for a system with many degrees of freedom. A megapixel image, for instance, is a point in a million-dimensional vector space; by varying the image, one can explore the space, and various subsets of this space correspond to various classes of images.

One can similarly interpret sound waves, a box of gases, an ecosystem, a voting population, a stream of digital data, trials of random variables, the results of a statistical survey, a probabilistic strategy in a two-player game, and many other concrete objects as states in a high-dimensional vector space, and various basic concepts such as convexity, distance, linearity, change of variables, orthogonality, or inner product can have very natural meanings in some of these models (though not in all).

It can take a bit of both theory and practice to merge one's intuition for these things with one's spatial intuition for vectors and vector spaces, but it can be done eventually (much as after one has enough exposure to measure theory, one can start merging one's intuition regarding cardinality, mass, length, volume, probability, cost, charge, and any number of other "real-life" measures).

For instance, the fact that most of the mass of a unit ball in high dimensions lurks near the boundary of the ball can be interpreted as a manifestation of the law of large numbers, using the interpretation of a high-dimensional vector space as the state space for a large number of trials of a random variable.

More generally, many facts about low-dimensional projections or slices of high-dimensional objects can be viewed from a probabilistic, statistical, or signal processing perspective.

Scott Aaronson:

Here are some of the crutches I've relied on. (Admittedly, my crutches are probably much more useful for theoretical computer science, combinatorics, and probability than they are for geometry, topology, or physics. On a related note, I personally have a much easier time thinking about R^n than about, say, R^4 or R^5!)

1. If you're trying to visualize some 4D phenomenon P, first think of a related 3D phenomenon P', and then imagine yourself as a 2D being who's trying to visualize P'. The advantage is that, unlike with the 4D vs. 3D case, you yourself can easily switch between the 3D and 2D perspectives, and can therefore get a sense of exactly what information is being lost when you drop a dimension. (You could call this the "Flatland trick," after the most famous literary work to rely on it.)

2. As someone else mentioned, discretize! Instead of thinking about R^n, think about the Boolean hypercube {0,1}^n, which is finite and usually easier to get intuition about. (When working on problems, I often find myself drawing {0,1}^4 on a sheet of paper by drawing two copies of {0,1}^3 and then connecting the corresponding vertices.)

3. Instead of thinking about a subset S⊆R^n, think about its characteristic function f:R^n→{0,1}. I don't know why that trivial perspective switch makes such a big difference, but it does ... maybe because it shifts your attention to the process of computing f, and makes you forget about the hopeless task of visualizing S!

4. One of the central facts about R^n is that, while it has "room" for only n orthogonal vectors, it has room for exp(n) almost-orthogonal vectors. Internalize that one fact, and so many other properties of R^n (for example, that the n-sphere resembles a "ball with spikes sticking out," as someone mentioned before) will suddenly seem non-mysterious. In turn, one way to internalize the fact that R^n has so many almost-orthogonal vectors is to internalize Shannon's theorem that there exist good error-correcting codes.

5. To get a feel for some high-dimensional object, ask questions about the behavior of a process that takes place on that object. For example: if I drop a ball here, which local minimum will it settle into? How long does this random walk on {0,1}^n take to mix?

Gil Kalai:

This is a slightly different point, but Vitali Milman, who works in high-dimensional convexity, likes to draw high-dimensional convex bodies in a non-convex way. This is to convey the point that if you take the convex hull of a few points on the unit sphere of R^n, then for large n very little of the measure of the convex body is anywhere near the corners, so in a certain sense the body is a bit like a small sphere with long thin "spikes".

q-n-a
intuition
math
visual-understanding
list
discussion
thurston
tidbits
aaronson
tcs
geometry
problem-solving
yoga
👳
big-list
metabuch
tcstariat
gowers
mathtariat
acm
overflow
soft-question
levers
dimensionality
hi-order-bits
insight
synthesis
thinking
models
cartoons
coding-theory
information-theory
probability
concentration-of-measure
magnitude
linear-algebra
boolean-analysis
analogy
arrows
lifts-projections
measure
markov
sampling
shannon
conceptual-vocab
nibble
degrees-of-freedom
worrydream
neurons
retrofit
oscillation
paradox
novelty
tricki
concrete
high-dimension
s:***
manifolds
direction
curvature
convexity-curvature
I can't help you much with high-dimensional topology - it's not my field, and I've not picked up the various tricks topologists use to get a grip on the subject - but when dealing with the geometry of high-dimensional (or infinite-dimensional) vector spaces such as R^n, there are plenty of ways to conceptualise these spaces that do not require visualising more than three dimensions directly.

For instance, one can view a high-dimensional vector space as a state space for a system with many degrees of freedom. A megapixel image, for instance, is a point in a million-dimensional vector space; by varying the image, one can explore the space, and various subsets of this space correspond to various classes of images.

One can similarly interpret sound waves, a box of gases, an ecosystem, a voting population, a stream of digital data, trials of random variables, the results of a statistical survey, a probabilistic strategy in a two-player game, and many other concrete objects as states in a high-dimensional vector space, and various basic concepts such as convexity, distance, linearity, change of variables, orthogonality, or inner product can have very natural meanings in some of these models (though not in all).

It can take a bit of both theory and practice to merge one's intuition for these things with one's spatial intuition for vectors and vector spaces, but it can be done eventually (much as after one has enough exposure to measure theory, one can start merging one's intuition regarding cardinality, mass, length, volume, probability, cost, charge, and any number of other "real-life" measures).

For instance, the fact that most of the mass of a unit ball in high dimensions lurks near the boundary of the ball can be interpreted as a manifestation of the law of large numbers, using the interpretation of a high-dimensional vector space as the state space for a large number of trials of a random variable.

More generally, many facts about low-dimensional projections or slices of high-dimensional objects can be viewed from a probabilistic, statistical, or signal processing perspective.

Scott Aaronson:

Here are some of the crutches I've relied on. (Admittedly, my crutches are probably much more useful for theoretical computer science, combinatorics, and probability than they are for geometry, topology, or physics. On a related note, I personally have a much easier time thinking about R^n than about, say, R^4 or R^5!)

1. If you're trying to visualize some 4D phenomenon P, first think of a related 3D phenomenon P', and then imagine yourself as a 2D being who's trying to visualize P'. The advantage is that, unlike with the 4D vs. 3D case, you yourself can easily switch between the 3D and 2D perspectives, and can therefore get a sense of exactly what information is being lost when you drop a dimension. (You could call this the "Flatland trick," after the most famous literary work to rely on it.)

2. As someone else mentioned, discretize! Instead of thinking about R^n, think about the Boolean hypercube {0,1}^n, which is finite and usually easier to get intuition about. (When working on problems, I often find myself drawing {0,1}^4 on a sheet of paper by drawing two copies of {0,1}^3 and then connecting the corresponding vertices.)

3. Instead of thinking about a subset S⊆R^n, think about its characteristic function f:R^n→{0,1}. I don't know why that trivial perspective switch makes such a big difference, but it does ... maybe because it shifts your attention to the process of computing f, and makes you forget about the hopeless task of visualizing S!

4. One of the central facts about R^n is that, while it has "room" for only n orthogonal vectors, it has room for exp(n) almost-orthogonal vectors. Internalize that one fact, and so many other properties of R^n (for example, that the n-sphere resembles a "ball with spikes sticking out," as someone mentioned before) will suddenly seem non-mysterious. In turn, one way to internalize the fact that R^n has so many almost-orthogonal vectors is to internalize Shannon's theorem that there exist good error-correcting codes.

5. To get a feel for some high-dimensional object, ask questions about the behavior of a process that takes place on that object. For example: if I drop a ball here, which local minimum will it settle into? How long does this random walk on {0,1}^n take to mix?

Gil Kalai:

This is a slightly different point, but Vitali Milman, who works in high-dimensional convexity, likes to draw high-dimensional convex bodies in a non-convex way. This is to convey the point that if you take the convex hull of a few points on the unit sphere of R^n, then for large n very little of the measure of the convex body is anywhere near the corners, so in a certain sense the body is a bit like a small sphere with long thin "spikes".

december 2016 by nhaliday

**related tags**

Copy this bookmark: