average-case   11

Complexity no Bar to AI - Gwern.net
Critics of AI risk suggest diminishing returns to computing (formalized asymptotically) means AI will be weak; this argument relies on a large number of questionable premises and ignoring additional resources, constant factors, and nonlinear returns to small intelligence advantages, and is highly unlikely. (computer science, transhumanism, AI, R)
created: 1 June 2014; modified: 01 Feb 2018; status: finished; confidence: likely; importance: 10
ratty  gwern  analysis  faq  ai  risk  speedometer  intelligence  futurism  cs  computation  complexity  tcs  linear-algebra  nonlinearity  convexity-curvature  average-case  adversarial  article  time-complexity  singularity  iteration-recursion  magnitude  multiplicative  lower-bounds  no-go  performance  hardware  humanity  psychology  cog-psych  psychometrics  iq  distribution  moments  complement-substitute  hanson  ems  enhancement  parable  detail-architecture  universalism-particularism  neuro  ai-control  environment  climate-change  threat-modeling  security  theory-practice  hacker  academia  realness  crypto  rigorous-crypto  usa  government 
april 2018 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

related tags

academia  acm  acmtariat  adversarial  ai-control  ai  algorithms  analysis  ankur-moitra  article  bandits  best-practices  bits  blog  circuits  clever-rats  climate-change  cog-psych  communication-complexity  complement-substitute  complexity  computation  confidence  convexity-curvature  course  crypto  cs  data-science  data-structures  descriptive  detail-architecture  distribution  distributional  duality  elegance  ems  engineering  enhancement  ensembles  entropy-like  environment  evan-miller  explanation  exploration-exploitation  explore-exploit  exposition  faq  futurism  game-theory  government  gradient-descent  graph-theory  graphs  gwern  hacker  hanson  hardware  harvard  hashing  hierarchy  homepage  humanity  iidness  information-theory  init  intelligence  interpretability  iq  iteration-recursion  iterative-methods  latent-variables  learning-theory  lecture-notes  levers  linear-algebra  linear-programming  linearity  liner-notes  local-global  lower-bounds  machine-learning  magnitude  metabuch  mit  moments  multiplicative  neuro  nibble  no-go  nonlinearity  online-learning  open-closed  optimization  org:bleg  org:edu  org:junk  org:mat  org:med  p:***  p:**  p:*  papers  parable  pcp  performance  perturbation  pragmatic  princeton  proof-systems  psychology  psychometrics  quixotic  rand-approx  rand-complexity  random-matrices  random-networks  random  ratty  realness  reference  regularizer  relativization  research-program  research  rhetoric  rigorous-crypto  risk  rounding  salil-vadhan  sdp  sebastien-bubeck  security  singularity  space-complexity  speedometer  strategy  stream  sublinear  submodular  tcs  tcstariat  tech  techtariat  theory-practice  threat-modeling  tidbits  time-complexity  toolkit  unit  universalism-particularism  usa  values  yoga  👳 

Copy this bookmark: