nhaliday + tcstariat   157

If Quantum Computers are not Possible Why are Classical Computers Possible? | Combinatorics and more
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
"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


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 
june 2017 by nhaliday
- 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

- 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 
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 
may 2017 by nhaliday
inequalities - Is the Jaccard distance a distance? - MathOverflow
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 
february 2017 by nhaliday
Lecture 11
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
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
Shtetl-Optimized » Blog Archive » Logicians on safari
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 
january 2017 by nhaliday
Dvoretzky's theorem - Wikipedia
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.

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 
january 2017 by nhaliday
Shtetl-Optimized » Blog Archive » First they came for the Iranians
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
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 
january 2017 by nhaliday
Computational Complexity: Favorite Theorems: The Yao Principle
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 
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
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
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
Shtetl-Optimized » Blog Archive » Why I Am Not An Integrated Information Theorist (or, The Unconscious Expander)
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 
january 2017 by nhaliday
gt.geometric topology - Intuitive crutches for higher dimensional thinking - MathOverflow
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 
december 2016 by nhaliday
« earlier      
per page:    204080120160

bundles : academemetapeepspubtcs

related tags

2016-election  :/  aaronson  abstraction  academia  accretion  acm  acmtariat  additive-combo  adversarial  advice  aesthetics  ai  albion  alg-combo  algebra  algebraic-complexity  algorithms  altruism  ama  analogy  anarcho-tyranny  anglosphere  announcement  anthropic  anthropology  antidemos  aphorism  api  apollonian-dionysian  applications  approximation  arrows  asia  atmosphere  atoms  attention  authoritarianism  automata  automation  average-case  axelrod  axioms  backup  bare-hands  bayesian  beauty  behavioral-gen  being-right  berkeley  better-explained  big-list  big-peeps  big-picture  big-surf  bio  biodet  bitcoin  bits  blockchain  blog  blowhards  boaz-barak  bonferroni  books  boolean-analysis  bounded-cognition  business  business-models  calculation  canon  capitalism  career  cartoons  causation  censorship  chaining  characterization  chart  cheatsheet  checklists  chemistry  christianity  circuits  civil-liberty  clarity  class-warfare  classic  climate-change  clown-world  coalitions  coding-theory  cog-psych  cohesion  cold-war  coloring  commentary  communication-complexity  communism  commutativity  comparison  competition  complex-systems  complexity  composition-decomposition  computation  computational-geometry  concentration-of-measure  concept  conceptual-vocab  concrete  conference  confluence  confusion  constraint-satisfaction  contradiction  contrarianism  convexity-curvature  cool  cooperate-defect  coordination  correlation  counter-revolution  counterexample  counting  courage  course  creative  critique  crypto  cryptocurrency  cs  cultural-dynamics  culture-war  curiosity  current-events  curvature  cybernetics  cynicism-idealism  darwinian  data-structures  database  death  debate  deep-learning  definition  degrees-of-freedom  democracy  dennett  dependence-independence  differential-privacy  dimensionality  direction  discovery  discrete  discussion  distribution  diversity  domestication  DP  duality  duty  dynamic  dynamical  dysgenics  early-modern  eastern-europe  economics  effect-size  elections  electromag  embedded-cognition  embeddings  embodied  emergent  empirical  ems  engineering  enlightenment-renaissance-restoration-reformation  entanglement  entropy-like  environment  epistemic  equilibrium  erdos  ergodic  error  essay  estimate  europe  events  evolution  examples  existence  exit-voice  exocortex  expanders  expectancy  expert  expert-experience  explanans  explanation  exploration-exploitation  exposition  extrema  fashun  feynman  fiber  fiction  fields  finiteness  fixed-point  food  forms-instances  fourier  frequentist  frontier  futurism  game-theory  games  gaussian-processes  gedanken  generalization  genetics  genomics  geoengineering  geometry  giants  gnon  gnosis-logos  government  gowers  grad-school  graph-theory  graphs  greedy  ground-up  group-level  growth  GT-101  gtd  guide  GWAS  habit  hamming  hanson  hardness  harvard  hashing  hci  hi-order-bits  hidden-motives  hierarchy  high-dimension  high-variance  history  hmm  homepage  homo-hetero  hsu  huge-data-the-biggest  humility  hypothesis-testing  ideas  identity-politics  ideology  idk  iidness  illusion  impact  impetus  individualism-collectivism  info-dynamics  info-foraging  information-theory  init  inner-product  innovation  insight  instinct  integral  intel  intelligence  interdisciplinary  internet  intersection  intersection-connectedness  interview  intricacy  intuition  iron-age  is-ought  isteveish  iteration-recursion  jargon  journos-pundits  knowledge  kumbaya-kult  labor  lattice  learning  learning-theory  lecture-notes  lectures  left-wing  len:long  len:short  lens  lesswrong  let-me-see  levers  leviathan  life-history  lifts-projections  limits  linear-algebra  linear-programming  liner-notes  links  list  lived-experience  local-global  logic  lol  long-short-run  long-term  low-hanging  lower-bounds  luca-trevisan  machine-learning  magnitude  malaise  malthus  managerial-state  manifolds  marginal  markov  math  math.CA  math.CO  math.CV  math.DS  math.FA  math.GR  math.MG  math.NT  mathtariat  matrix-factorization  measure  measurement  mechanics  media  mediterranean  MENA  meta:math  meta:research  meta:science  metabuch  metameta  methodology  metric-space  metrics  michael-nielsen  migration  mihai  minimum-viable  missing-heritability  mit  mixing  models  moments  monotonicity  monte-carlo  morality  mostly-modern  motivation  msr  multi  multiplicative  mystic  n-factor  nascent-state  nationalism-globalism  naturality  nature  network-structure  networking  neuro  neurons  news  nibble  nitty-gritty  no-go  noble-lie  norms  notation  novelty  number  obama  objektbuch  occident  oceans  oly  online-learning  open-problems  operational  optimism  optimization  order-disorder  org:bleg  org:edge  org:edu  org:inst  org:junk  org:local  org:mag  org:mat  org:nat  org:sci  organization  organizing  orient  orourke  orwellian  oscillation  overflow  p:*  p:**  p:someday  p:whenever  paleocon  papadimitriou  papers  parable  paradox  path-dependence  patience  pcp  pdf  people  pessimism  phase-transition  phd  philosophy  physics  pigeonhole-markov  poast  polarization  policy  polisci  politics  polynomials  popsci  population-genetics  positivity  postmortem  postrat  power  pragmatic  prediction  preference-falsification  preimage  preprint  presentation  princeton  prioritizing  probabilistic-method  probability  problem-solving  productivity  prof  profile  programming  project  proof-systems  proofs  propaganda  properties  protocol  prudence  pseudorandomness  psychology  publishing  puzzles  q-n-a  qra  quantifiers-sums  quantitative-qualitative  quantum  quantum-info  quantum-money  questions  quixotic  quotes  rand-approx  rand-complexity  random  random-matrices  rationality  ratty  reading  realness  reason  rec-math  recommendations  reddit  reduction  reference  reflection  regularity  relativization  relaxation  religion  research  retention  retrofit  review  revolution  rhetoric  rigidity  rigor  rigorous-crypto  risk  roots  rot  rounding  russia  ryan-odonnell  s:*  s:**  s:***  s:null  sampling  sanctity-degradation  sanjeev-arora  sapiens  scale  scaling-tech  schelling  scholar  scholar-pack  science  scifi-fantasy  scitariat  SDP  search  sensitivity  separation  shannon  shift  signal-noise  signaling  signum  similarity  simulation  singularity  sinosphere  skeleton  skunkworks  sleuthin  slides  slippery-slope  smoothness  social  social-choice  social-psych  social-structure  society  soft-question  software  solzhenitsyn  space-complexity  sparsity  spatial  spearhead  spectral  speculation  speedometer  ssc  stanford  stat-mech  state  stats  status  stochastic-processes  stock-flow  stories  strategy  straussian  stream  street-fighting  strings  stripe  structure  studying  subculture  subjective-objective  sublinear  submodular  success  sum-of-squares  summary  survey  symmetry  synthesis  systematic-ad-hoc  tactics  tails  talks  tcs  tcstariat  teaching  tech  technology  techtariat  the-basilisk  the-classics  the-great-west-whale  the-self  the-trenches  the-watchers  the-world-is-just-atoms  theos  things  thinking  thurston  tidbits  tim-roughgarden  time  time-complexity  todo  tools  top-n  topics  topology  toxoplasmosis  track-record  trade  travel  trends  tribalism  tricki  trump  truth  turing  tutorial  twitter  UGC  ui  unaffiliated  unintended-consequences  uniqueness  unit  urban  urban-rural  us-them  usa  ux  vague  valiant  video  virtu  visual-understanding  visualization  visuo  volo-avolo  walls  washington  water  waves  web  west-hunter  westminster  whole-partial-many  wigderson  wiki  wire-guided  within-without  wordlessness  workflow  workshop  world  wormholes  worrydream  writing  yak-shaving  yarvin  yoga  yvain  zeitgeist  🎓  👳  🔬  🖥 

Copy this bookmark: