nhaliday + rigorous-crypto   33

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
Merkle tree - Wikipedia
In cryptography and computer science, a hash tree or Merkle tree is a tree in which every non-leaf node is labelled with the hash of the labels or values (in case of leaves) of its child nodes.
concept  cs  data-structures  bitcoin  cryptocurrency  blockchain  atoms  protocol  wiki  reference  nibble  hashing  ideas  crypto  rigorous-crypto 
june 2017 by nhaliday
6.896: Essential Coding Theory
- probabilistic method and Chernoff bound for Shannon coding
- probabilistic method for asymptotically good Hamming codes (Gilbert coding)
- sparsity used for LDPC codes
mit  course  yoga  tcs  complexity  coding-theory  math.AG  fields  polynomials  pigeonhole-markov  linear-algebra  probabilistic-method  lecture-notes  bits  sparsity  concentration-of-measure  linear-programming  linearity  expanders  hamming  pseudorandomness  crypto  rigorous-crypto  communication-complexity  no-go  madhu-sudan  shannon  unit  p:** 
february 2017 by nhaliday
Cryptography at STOC/FOCS | in theory
On Sunday I also attended a cryptography session. One thing that impressed me was the lively discussion at the end of the talks, very different from the stunned silence that usually follows when the session chair asks if there are any questions. The other thing I noticed was that the session was attended almost exclusively by cryptographers.

Why is that? A first guess is that the field has become very technical. But this cannot be the point; after all, a typical paper on PCP is also very technical, but the audience is not made exclusively of PCP technicians. Maybe the point is that even, or especially, definitions are very technical in cryptography. One can go to a talk showing that sparsest cut does not have a constant-factor approximation assuming the Unique Games Conjecture, and be fairly satisfied that he understands what it would mean for sparsest cut to have a constant-factor approximation and what it would mean for the Unique Games Conjecture to be false. Then one sees some slides with clouds of vertices connected in various ways, one hears mentions of Gaussian distributions, influence of variables, and invariance principles, and one gets lost, but with an idea that there is a reduction that needs certain complicated mathematical techniques to be analyzed.

In a cryptography talk, however, one may get started with the problem of realizing primitive X under assumptions Y1 and Y2, according to security requirement Z, with no set-up assumptions, and it would require quite some expertise to realize that requirement Z is considerably harder to achieve than similarly sounding Z’, which was known to be achievable under assumptions of Y1 and Y’2, where Y’2 is incomparable to Y2, but intuitively stronger, and so on. Consider the recent breakthrough on the long-standing very clear-cut question to achieve statistically hiding commitments assuming only one-way functions. This is a statement that is an order of magnitude simpler than the typical result in cryptography, probably the most basic question that was still open in the 2000s, but even to unpack such a statement is not easy and requires to see various examples, discussion of applications and so on.
crypto  rigorous-crypto  research  thinking  tcs  critique  reflection  tcstariat  conference  lens  UGC  boolean-analysis  reduction  conceptual-vocab  ground-up  luca-trevisan  nibble  org:bleg 
june 2016 by nhaliday

bundles : tcs

related tags

aaronson  academia  adversarial  ai  ai-control  algebraic-complexity  algorithmic-econ  algorithms  analysis  announcement  approximation  arrows  article  atoms  average-case  berkeley  big-picture  big-surf  bitcoin  bits  blockchain  boaz-barak  boolean-analysis  caltech  carmack  circuits  climate-change  coding-theory  cog-psych  commentary  communication-complexity  complement-substitute  complexity  computation  concentration-of-measure  concept  conceptual-vocab  conference  contrarianism  convexity-curvature  cornell  counting  course  critique  crypto  cryptocurrency  cs  dana-moshkovitz  data-structures  database  decentralized  decision-theory  deep-learning  detail-architecture  dimensionality  discovery  distributed  distribution  duality  ems  engineering  enhancement  environment  equilibrium  error  essay  expanders  expert  expert-experience  explanation  faq  fields  frontier  futurism  game-theory  government  gowers  gradient-descent  ground-up  gwern  hacker  hamming  hanson  hard-core  hardness  hardware  harvard  hashing  heuristic  high-dimension  hn  homepage  huge-data-the-biggest  humanity  ideas  information-theory  init  innovation  insight  intelligence  iq  iteration-recursion  jargon  learning-theory  lecture-notes  lectures  lens  linear-algebra  linear-programming  linearity  liner-notes  links  list  lower-bounds  luca-trevisan  machine-learning  madhu-sudan  magnitude  markov  math.AG  math.GR  math.NT  mathtariat  matrix-factorization  metabuch  minimum-viable  mit  models  moments  motivation  multiplicative  naturality  neuro  nibble  no-go  nonlinearity  novelty  ocw  oly  online-learning  open-problems  operational  org:bleg  org:edu  org:junk  overflow  p2p  p:**  p:***  p:someday  p:whenever  papers  parable  pcp  performance  pigeonhole-markov  polynomials  postmortem  pragmatic  princeton  probabilistic-method  proof-systems  protocol  pseudorandomness  psychology  psychometrics  publishing  q-n-a  quantum  quantum-info  quantum-money  questions  rand-approx  rand-complexity  random  ratty  realness  reduction  reference  reflection  relativization  research  rhetoric  rigorous-crypto  risk  roots  ryan-odonnell  salil-vadhan  sampling  sanjeev-arora  scholar  SDP  security  shannon  shipping  singularity  space-complexity  sparsity  spectral  speedometer  stanford  stream  synthesis  szabo  talks  tcs  tcstariat  technology  theory-practice  thinking  threat-modeling  tidbits  time-complexity  toolkit  top-n  topics  turing  UGC  unit  universalism-particularism  usa  valiant  wigderson  wiki  yoga  👳 

Copy this bookmark: