nhaliday + mathtariat   215

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
gn.general topology - Pair of curves joining opposite corners of a square must intersect---proof? - MathOverflow
In his 'Ordinary Differential Equations' (sec. 1.2) V.I. Arnold says "... every pair of curves in the square joining different pairs of opposite corners must intersect".

This is obvious geometrically but I was wondering how one could go about proving this rigorously. I have thought of a proof using Brouwer's Fixed Point Theorem which I describe below. I would greatly appreciate the group's comments on whether this proof is right and if a simpler proof is possible.


Since the full Jordan curve theorem is quite subtle, it might be worth pointing out that theorem in question reduces to the Jordan curve theorem for polygons, which is easier.

Suppose on the contrary that the curves A,BA,B joining opposite corners do not meet. Since A,BA,B are closed sets, their minimum distance apart is some ε>0ε>0. By compactness, each of A,BA,B can be partitioned into finitely many arcs, each of which lies in a disk of diameter <ε/3<ε/3. Then, by a homotopy inside each disk we can replace A,BA,B by polygonal paths A′,B′A′,B′ that join the opposite corners of the square and are still disjoint.

Also, we can replace A′,B′A′,B′ by simple polygonal paths A″,B″A″,B″ by omitting loops. Now we can close A″A″ to a polygon, and B″B″ goes from its "inside" to "outside" without meeting it, contrary to the Jordan curve theorem for polygons.

- John Stillwell
nibble  q-n-a  overflow  math  geometry  topology  tidbits  intricacy  intersection  proofs  gotchas  oly  mathtariat  fixed-point  math.AT  manifolds  intersection-connectedness 
october 2017 by nhaliday
GOP tax plan would provide major gains for richest 1%, uneven benefits for the middle class, report says - The Washington Post
Trump tweets: For his voters.
Tax plan: Something else entirely.
This is appallingly stupid if accurate


Treasury Removes Paper at Odds With Mnuchin’s Take on Corporate-Tax Cut’s Winners: https://www.wsj.com/articles/treasury-removes-paper-at-odds-with-mnuchins-take-on-corporate-tax-cuts-winners-1506638463

Tax changes for graduate students under the Tax Cuts and Jobs Act: https://bcide.gitlab.io/post/gop-tax-plan/
H.R.1 – 155th Congress (Tax Cuts and Jobs Act) 1 proposes changes to the US Tax Code that threatens to destroy the finances of STEM graduate students nationwide. The offending provision, 1204(a)(3), strikes section 117(d) 2 of the US Tax Code. This means that under the proposal, tuition waivers are considered taxable income.

For graduate students, this means an increase of thousands of dollars in owed federal taxes. Below I show a calculation for my own situation. The short of it is this: My federal taxes increase from ~7.5% of my income to ~31%. I will owe about $6300 more in federal taxes under this legislation. Like many other STEM students, my choices would be limited to taking on significant debt or quitting my program entirely.

The Republican War on College: https://www.theatlantic.com/business/archive/2017/11/republican-college/546308/

Trump's plan to tax colleges will harm higher education — but it's still a good idea: http://www.businessinsider.com/trump-tax-plan-taxing-colleges-is-a-good-idea-2017-11
- James Miller

The Republican Tax Plan Is a Disaster for Families With Children: http://www.motherjones.com/kevin-drum/2017/11/the-republican-tax-plan-is-a-disaster-for-families-with-children/
- Kevin Drum

The gains from cutting corporate tax rates: http://marginalrevolution.com/marginalrevolution/2017/11/corporate-taxes-2.html
I’ve been reading in this area on and off since the 1980s, and I really don’t think these are phony results.

Entrepreneurship and State Taxation: https://www.federalreserve.gov/econres/feds/files/2018003pap.pdf
We find that new firm employment is negatively—and disproportionately—affected by corporate tax rates. We find little evidence of an effect of personal and sales taxes on entrepreneurial outcomes.

nobody in the comments section seems to have even considered the comparison with universities

The GOP Tax Bills Are Infrastructure Bills Too. Here’s Why.: http://www.governing.com/topics/transportation-infrastructure/gov-republican-tax-bills-impact-infrastructure.html
news  org:rec  trump  current-events  wonkish  policy  taxes  data  analysis  visualization  money  monetary-fiscal  compensation  class  hmm  :/  coalitions  multi  twitter  social  commentary  gnon  unaffiliated  right-wing  backup  class-warfare  redistribution  elite  vampire-squid  crooked  journos-pundits  tactics  strategy  politics  increase-decrease  pro-rata  labor  capital  distribution  corporation  corruption  anomie  counter-revolution  higher-ed  academia  nascent-state  mathtariat  phd  grad-school  org:mag  left-wing  econotariat  marginal-rev  links  study  summary  economics  econometrics  endogenous-exogenous  natural-experiment  longitudinal  regularizer  religion  christianity  org:gov  infrastructure  transportation  cracker-econ  org:lite  org:biz  crosstab  dynamic  let-me-see  cost-benefit  entrepreneurialism  branches  geography  usa  within-group 
september 2017 by nhaliday
Correlated Equilibria in Game Theory | Azimuth
Given this, it’s not surprising that Nash equilibria can be hard to find. Last September a paper came out making this precise, in a strong way:

• Yakov Babichenko and Aviad Rubinstein, Communication complexity of approximate Nash equilibria.

The authors show there’s no guaranteed method for players to find even an approximate Nash equilibrium unless they tell each other almost everything about their preferences. This makes finding the Nash equilibrium prohibitively difficult to find when there are lots of players… in general. There are particular games where it’s not difficult, and that makes these games important: for example, if you’re trying to run a government well. (A laughable notion these days, but still one can hope.)

Klarreich’s article in Quanta gives a nice readable account of this work and also a more practical alternative to the concept of Nash equilibrium. It’s called a ‘correlated equilibrium’, and it was invented by the mathematician Robert Aumann in 1974. You can see an attempt to define it here:
baez  org:bleg  nibble  mathtariat  commentary  summary  news  org:mag  org:sci  popsci  equilibrium  GT-101  game-theory  acm  conceptual-vocab  concept  definition  thinking  signaling  coordination  tcs  complexity  communication-complexity  lower-bounds  no-go  liner-notes  big-surf  papers  research  algorithmic-econ  volo-avolo 
july 2017 by nhaliday
Peter Norvig, the meaning of polynomials, debugging as psychotherapy | Quomodocumque
He briefly showed a demo where, given values of a polynomial, a machine can put together a few lines of code that successfully computes the polynomial. But the code looks weird to a human eye. To compute some quadratic, it nests for-loops and adds things up in a funny way that ends up giving the right output. So has it really ”learned” the polynomial? I think in computer science, you typically feel you’ve learned a function if you can accurately predict its value on a given input. For an algebraist like me, a function determines but isn’t determined by the values it takes; to me, there’s something about that quadratic polynomial the machine has failed to grasp. I don’t think there’s a right or wrong answer here, just a cultural difference to be aware of. Relevant: Norvig’s description of “the two cultures” at the end of this long post on natural language processing (which is interesting all the way through!)
mathtariat  org:bleg  nibble  tech  ai  talks  summary  philosophy  lens  comparison  math  cs  tcs  polynomials  nlp  debugging  psychology  cog-psych  complex-systems  deep-learning  analogy  legibility  interpretability 
march 2017 by nhaliday
254A, Supplement 4: Probabilistic models and heuristics for the primes (optional) | What's new
among others, the Cramér model for the primes (basically kinda looks like primality is independently distributed w/ Pr[n is prime] = 1/log n)
gowers  mathtariat  lecture-notes  exposition  math  math.NT  probability  heuristic  models  cartoons  nibble  org:bleg  pseudorandomness  borel-cantelli  concentration-of-measure  multiplicative 
february 2017 by nhaliday
A brief philosophical discussion:
Measure theory, as much as any branch of mathematics, is an area where it is important to be acquainted with the basic notions and statements, but not desperately important to be acquainted with the detailed proofs, which are often rather unilluminating. One should always have in a mind a place where one could go and look if one ever did need to understand a proof: for me, that place is Rudin’s Real and Complex Analysis (Rudin’s “red book”).
gowers  pdf  math  math.CA  math.FA  philosophy  measure  exposition  synthesis  big-picture  hi-order-bits  ergodic  ground-up  summary  roadmap  mathtariat  proofs  nibble  unit  integral  zooming  p:whenever 
february 2017 by nhaliday
Could I be using proof by contradiction too much? - Mathematics Stack Exchange
One general reason to avoid proof by contradiction is the following. When you prove something by contradiction, all you learn is that the statement you wanted to prove is true. When you prove something directly, you learn every intermediate implication you had to prove along the way.
q-n-a  overflow  math  proofs  contradiction  oly  mathtariat  nibble 
february 2017 by nhaliday
Information Geometry (Part 16) | Azimuth
While preparing this talk, I discovered a cool fact. I doubt it’s new, but I haven’t exactly seen it elsewhere. I came up with it while trying to give a precise and general statement of ‘Fisher’s fundamental theorem of natural selection’. I won’t start by explaining that theorem, since my version looks rather different than Fisher’s, and I came up with mine precisely because I had trouble understanding his. I’ll say a bit more about this at the end.

Here’s my version:
The square of the rate at which a population learns information is the variance of its fitness.
baez  mathtariat  evolution  bio  genetics  population-genetics  bits  interdisciplinary  models  exposition  math.DS  giants  information-theory  entropy-like  org:bleg  nibble  fisher  EGT  dynamical 
february 2017 by nhaliday
The Brunn-Minkowski Inequality | The n-Category Café
For instance, this happens in the plane when A is a horizontal line segment and B is a vertical line segment. There’s obviously no hope of getting an equation for Vol(A+B) in terms of Vol(A) and Vol(B). But this example suggests that we might be able to get an inequality, stating that Vol(A+B) is at least as big as some function of Vol(A) and Vol(B).

The Brunn-Minkowski inequality does this, but it’s really about linearized volume, Vol^{1/n}, rather than volume itself. If length is measured in metres then so is Vol^{1/n}.


Nice post, Tom. To readers whose background isn’t in certain areas of geometry and analysis, it’s not obvious that the Brunn–Minkowski inequality is more than a curiosity, the proof of the isoperimetric inequality notwithstanding. So let me add that Brunn–Minkowski is an absolutely vital tool in many parts of geometry, analysis, and probability theory, with extremely diverse applications. Gardner’s survey is a great place to start, but by no means exhaustive.

I’ll also add a couple remarks about regularity issues. You point out that Brunn–Minkowski holds “in the vast generality of measurable sets”, but it may not be initially obvious that this needs to be interpreted as “when A, B, and A+B are all Lebesgue measurable”, since A+B need not be measurable when A and B are (although you can modify the definition of A+B to work for arbitrary measurable A and B; this is discussed by Gardner).
mathtariat  math  estimate  exposition  geometry  math.MG  measure  links  regularity  survey  papers  org:bleg  nibble  homogeneity  brunn-minkowski  curvature  convexity-curvature 
february 2017 by nhaliday
general topology - What should be the intuition when working with compactness? - Mathematics Stack Exchange

The situation with compactness is sort of like the above. It turns out that finiteness, which you think of as one concept (in the same way that you think of "Foo" as one concept above), is really two concepts: discreteness and compactness. You've never seen these concepts separated before, though. When people say that compactness is like finiteness, they mean that compactness captures part of what it means to be finite in the same way that shortness captures part of what it means to be Foo.


As many have said, compactness is sort of a topological generalization of finiteness. And this is true in a deep sense, because topology deals with open sets, and this means that we often "care about how something behaves on an open set", and for compact spaces this means that there are only finitely many possible behaviors.


Compactness does for continuous functions what finiteness does for functions in general.

If a set A is finite then every function f:A→R has a max and a min, and every function f:A→R^n is bounded. If A is compact, the every continuous function from A to R has a max and a min and every continuous function from A to R^n is bounded.

If A is finite then every sequence of members of A has a subsequence that is eventually constant, and "eventually constant" is the only kind of convergence you can talk about without talking about a topology on the set. If A is compact, then every sequence of members of A has a convergent subsequence.
q-n-a  overflow  math  topology  math.GN  concept  finiteness  atoms  intuition  oly  mathtariat  multi  discrete  gowers  motivation  synthesis  hi-order-bits  soft-question  limits  things  nibble  definition  convergence  abstraction 
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
cv.complex variables - Absolute value inequality for complex numbers - MathOverflow
In general, once you've proven an inequality like this in R it holds automatically in any Euclidean space (including C) by averaging over projections. ("Inequality like this" = inequality where every term is the length of some linear combination of variable vectors in the space; here the vectors are a, b, c).

I learned this trick at MOP 30+ years ago, and don't know or remember who discovered it.
q-n-a  overflow  math  math.CV  estimate  tidbits  yoga  oly  mathtariat  math.FA  metabuch  inner-product  calculation  norms  nibble  tricki 
january 2017 by nhaliday
« earlier      
per page:    204080120160

bundles : mathpeeps

related tags

2016-election  :/  aaronson  absolute-relative  abstraction  academia  accretion  acm  acmtariat  additive  additive-combo  adversarial  advice  aesthetics  aggregator  ai  alg-combo  algebra  algebraic-complexity  algorithmic-econ  algorithms  allodium  AMT  analogy  analysis  analytical-holistic  announcement  anomie  anthropology  aphorism  applications  arrows  art  ascetic  atoms  aversion  axioms  backup  baez  bayesian  beauty  ben-recht  better-explained  biases  big-list  big-picture  big-surf  bio  bits  blog  boaz-barak  boltzmann  books  boolean-analysis  borel-cantelli  borjas  bounded-cognition  branches  brexit  brunn-minkowski  calculation  capital  career  cartoons  characterization  chart  checklists  chemistry  christianity  clarity  class  class-warfare  clever-rats  cliometrics  closure  coalitions  coarse-fine  coding-theory  cog-psych  cold-war  combo-optimization  commentary  communication  communication-complexity  communism  community  commutativity  comparison  compensation  complex-systems  complexity  compressed-sensing  compression  computation  concentration-of-measure  concept  conceptual-vocab  concrete  confluence  confusion  constraint-satisfaction  contradiction  contrarianism  convergence  convexity-curvature  cool  coordination  core-rats  corporation  correlation  corruption  cost-benefit  counter-revolution  counterexample  counting  courage  course  cracker-econ  creative  crooked  crosstab  crypto  cs  culture  curiosity  current-events  curvature  data  data-science  database  debate  debugging  decision-making  deep-learning  definition  degrees-of-freedom  dennett  dependence-independence  differential  dimensionality  direction  discipline  discovery  discrete  discussion  distribution  DP  draft  duty  dynamic  dynamical  econometrics  economics  econotariat  education  EGT  elections  electromag  elite  embeddings  emotion  encyclopedic  endogenous-exogenous  entrepreneurialism  entropy-like  epistemic  equilibrium  erdos  ergodic  error  essay  estimate  evolution  examples  existence  exocortex  expectancy  experiment  expert  expert-experience  explanation  explore-exploit  exposition  extra-introversion  extrema  facebook  fedja  feynman  fiction  fields  film  finiteness  fire  fisher  fixed-point  flexibility  fluid  fourier  frontier  game-theory  games  gedanken  genetics  geography  geometry  giants  gnon  gotchas  gowers  grad-school  graph-theory  graphs  greedy  ground-up  growth  GT-101  gtd  hamming  hanson  heuristic  hi-order-bits  hierarchy  high-dimension  higher-ed  history  hmm  homepage  homogeneity  humility  ideas  identity  IEEE  iidness  increase-decrease  individualism-collectivism  induction  info-dynamics  info-foraging  information-theory  infrastructure  init  inner-product  innovation  insight  integral  interdisciplinary  interpretability  intersection  intersection-connectedness  intervention  interview  intricacy  intuition  invariance  isotropy  iteration-recursion  jargon  journos-pundits  kernels  knowledge  labor  language  latent-variables  latex  lattice  learning  lecture-notes  lectures  left-wing  legibility  lens  lesswrong  let-me-see  levers  lifts-projections  limits  linear-algebra  linear-programming  linearity  liner-notes  links  list  literature  local-global  logic  lol  long-term  longitudinal  lower-bounds  machine-learning  magnitude  manifolds  marginal  marginal-rev  markov  matching  math  math.AC  math.AG  math.AT  math.CA  math.CO  math.CT  math.CV  math.DS  math.FA  math.GN  math.GR  math.MG  math.NT  math.RT  mathtariat  matrix-factorization  measure  mechanics  mental-math  meta:math  meta:research  meta:rhetoric  meta:science  metabuch  metameta  methodology  metric-space  michael-nielsen  migration  minimum-viable  miri-cfar  mit  ML-MAP-E  models  moments  monetary-fiscal  money  monte-carlo  mostly-modern  motivation  multi  multiplicative  narrative  nascent-state  natural-experiment  naturality  nature  neurons  news  nibble  nitty-gritty  nlp  no-go  nonlinearity  norms  notation  notetaking  novelty  numerics  objektbuch  occam  off-convex  oly  online-learning  open-problems  operational  optics  optimate  optimization  orders  org:biz  org:bleg  org:edu  org:gov  org:junk  org:lite  org:mag  org:mat  org:rec  org:sci  orourke  oscillation  overflow  oxbridge  p:**  p:someday  p:whenever  papers  parable  paradox  pareto  pdf  people  persuasion  phase-transition  phd  philosophy  photography  physics  pic  pigeonhole-markov  pinker  planning  plots  policy  politics  polynomials  popsci  population-genetics  positivity  power-law  practice  preprint  princeton  prioritizing  pro-rata  probabilistic-method  probability  problem-solving  productivity  prof  profile  progression  proof-systems  proofs  pseudorandomness  psychology  publishing  puzzles  q-n-a  qra  quantifiers-sums  quantitative-qualitative  quantum  quantum-info  questions  quixotic  quotes  rand-complexity  random  random-matrices  rationality  ratty  reading  rec-math  recommendations  redistribution  reduction  reference  reflection  regression-to-mean  regularity  regularizer  relativity  relaxation  religion  repo  research  retention  retrofit  review  rhetoric  right-wing  rigidity  rigor  rigorous-crypto  risk  roadmap  robust  rounding  russia  ryan-odonnell  s-factor  s:*  s:**  s:***  s:null  sampling  scale  scholar  scholar-pack  science  scitariat  seminar  sensitivity  separation  serene  series  shannon  shift  signal-noise  signaling  signum  simplex  singularity  skeleton  smoothness  social  social-choice  social-psych  soft-question  software  space  sparsity  spatial  spectral  speed  speedometer  spock  ssc  stamina  stat-mech  stats  status  stirling  stochastic-processes  stories  strategy  stream  street-fighting  structure  students  study  studying  subculture  success  summary  survey  symmetry  synthesis  systematic-ad-hoc  tactics  talks  taxes  tcs  tcstariat  teaching  tech  technology  techtariat  tensors  the-monster  the-trenches  the-world-is-just-atoms  thermo  things  thinking  thurston  tidbits  tightness  time  time-complexity  todo  tools  top-n  topics  topology  toxoplasmosis  tradeoffs  transitions  transportation  trees  tricki  tricks  trump  turing  twitter  unaffiliated  uniqueness  unit  usa  vague  vampire-squid  video  virtu  visual-understanding  visualization  vitality  volo-avolo  von-neumann  wiki  wild-ideas  wire-guided  wisdom  within-group  within-without  wonkish  wordlessness  workflow  wormholes  worrydream  writing  yak-shaving  yoga  yvain  zooming  🎓  🎩  👳  🔬  🖥  🤖  🦉 

Copy this bookmark: