mathtariat   213

« earlier    

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
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

« earlier    

related tags

2016-election  aaronson  absolute-relative  abstraction  academia  accretion  acm  additive-combo  additive  advice  ai  alg-combo  algebra  algebraic-complexity  algorithmic-econ  algorithms  amt  analogy  anthropology  applications  arrows  atoms  axioms  baez  bayesian  better-explained  big-list  big-picture  big-surf  bio  bits  blog  boaz-barak  boltzmann  books  boolean-analysis  borel-cantelli  borjas  brexit  brunn-minkowski  calculation  career  cartoons  characterization  chart  clarity  cliometrics  closure  coarse-fine  coding-theory  cog-psych  cold-war  combo-optimization  commentary  communication-complexity  communication  communism  commutativity  comparison  complex-systems  complexity  compressed-sensing  compression  computation  concentration-of-measure  concept  conceptual-vocab  confluence  confusion  constraint-satisfaction  contradiction  contrarianism  convergence  convexity-curvature  coordination  core-rats  counterexample  counting  courage  course  creative  crypto  cs  curiosity  curvature  data-science  database  debate  debugging  deep-learning  definition  degrees-of-freedom  differential  dimensionality  direction  discovery  discrete  discussion  distribution  dp  draft  duty  dynamical  egt  electromag  embeddings  entropy-like  epistemic  equilibrium  erdos  ergodic  error  essay  estimate  evolution  examples  existence  experiment  expert-experience  expert  explanation  exposition  extrema  facebook  feynman  fiction  fields  finiteness  fisher  fixed-point  flexibility  fluid  fourier  frontier  game-theory  games  gedanken  genetics  geometry  giants  gotchas  gowers  grad-school  graph-theory  graphs  greedy  ground-up  gt-101  hamming  heuristic  hi-order-bits  hierarchy  high-dimension  history  hmm  homogeneity  ideas  identity  ieee  iidness  info-dynamics  information-theory  inner-product  innovation  insight  integral  interdisciplinary  interpretability  intersection-connectedness  intersection  intervention  intricacy  intuition  invariance  iteration-recursion  jargon  knowledge  latent-variables  lattice  learning  lecture-notes  lectures  legibility  lens  lesswrong  levers  lifts-projections  limits  linear-algebra  linear-programming  linearity  liner-notes  links  list  local-global  logic  lower-bounds  machine-learning  magnitude  manifolds  marginal  markov  matching  math.ct  math.ds  math.fa  math.nt  math.rt  math  matrix-factorization  measure  mechanics  mental-math  meta:math  meta:research  meta:rhetoric  meta:science  metabuch  metameta  methodology  metric-space  michael-nielsen  migration  ml-map-e  models  moments  monte-carlo  mostly-modern  motivation  multi  multiplicative  narrative  naturality  neurons  news  nibble  nitty-gritty  nlp  no-go  norms  notation  novelty  numerics  occam  oly  online-learning  open-problems  optimization  orders  org:bleg  org:edu  org:junk  org:mag  org:mat  org:sci  oscillation  overflow  oxbridge  p:someday  p:whenever  papers  parable  paradox  pareto  pdf  persuasion  phase-transition  philosophy  photography  physics  pic  pigeonhole-markov  pinker  planning  politics  polynomials  popsci  population-genetics  positivity  power-law  probabilistic-method  probability  problem-solving  progression  proof-systems  proofs  pseudorandomness  psychology  puzzles  q-n-a  qra  quantifiers-sums  quantum-info  quantum  questions  quixotic  quotes  rand-complexity  random-matrices  random  rationality  ratty  recommendations  reduction  reference  reflection  regularity  relativity  relaxation  research  retention  rhetoric  rigidity  rigor  rigorous-crypto  roadmap  robust  rounding  russia  ryan-odonnell  s:***  s:**  s:*  sampling  scale  scholar  science  separation  series  shift  signal-noise  signaling  signum  simplex  singularity  skeleton  smoothness  social-psych  social  soft-question  space  sparsity  spatial  speed  speedometer  spock  ssc  stat-mech  stats  stories  stream  street-fighting  structure  study  studying  summary  survey  symmetry  synthesis  systematic-ad-hoc  talks  tcs  tcstariat  teaching  tech  technology  techtariat  tensors  the-trenches  the-world-is-just-atoms  thermo  things  thinking  thurston  tidbits  tightness  time-complexity  time  top-n  topology  toxoplasmosis  tradeoffs  transitions  tricki  tricks  trump  turing  uniqueness  unit  usa  vague  visual-understanding  volo-avolo  wiki  wild-ideas  wire-guided  within-without  wormholes  yak-shaving  yoga  yvain  zooming  🎓  🎩  👳  🔬  🖥 

Copy this bookmark: