nhaliday + conference   43

CSRankings: Computer Science Rankings (beta)
some missing venues: ITCS, QCRYPT, QIP, COLT (last has some big impact on the margins)
data  higher-ed  grad-school  phd  cs  tcs  list  schools  🎓  top-n  database  conference  ranking  publishing  fall-2016  network-structure  academia  objective-measure  let-me-see  nibble  reference 
july 2016 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  stoc  focs 
june 2016 by nhaliday

bundles : meta

related tags

aaronson  academia  accretion  acm  acmtariat  adversarial  ai  ai-control  albion  algorithms  announcement  apollonian-dionysian  automation  bandits  bangbang  bayesian  behavioral-econ  behavioral-gen  best-practices  biodet  biophysical-econ  blockchain  boolean-analysis  business  chicago  class  complexity  computer-vision  concentration-of-measure  concept  conceptual-vocab  conference  convexity-curvature  critique  crypto  cryptocurrency  cs  curvature  data  database  debate  decentralized  deep-learning  deepgoog  dimensionality  direction  economics  econotariat  events  experiment  expert  expert-experience  fall-2015  fall-2016  focs  frontier  generalization  genetics  geometry  gotchas  grad-school  ground-up  hci  hi-order-bits  higher-ed  hmm  human-capital  icml  inequality  internet  interpretability  intersection  intersection-connectedness  isotropy  learning-theory  lectures  lens  let-me-see  liner-notes  links  list  local-global  luca-trevisan  machine-learning  markets  markov  math  math.CA  math.MG  mechanism-design  metabuch  microbiz  microfoundations  mit  mobility  models  monte-carlo  mrtz  multi  network-structure  nibble  nips  nl-and-so-can-you  objective-measure  off-convex  online-learning  openai  optimization  org:anglo  org:bleg  org:edu  org:med  org:ngo  organization  p:*  papadimitriou  papers  phd  philosophy  policy  pragmatic  presentation  programming  protocol  publishing  quantum  quantum-info  quixotic  ranking  ratty  reduction  reference  reflection  reinforcement  repo  research  research-program  rhetoric  rigorous-crypto  risk  sanjeev-arora  schools  search  sebastien-bubeck  signal-noise  skunkworks  slides  smart-contracts  spatial  spectral  ssc  stanford  startups  stats  stoc  study  summary  summer-2016  sv  szabo  talks  tcs  tcstariat  tech  tensors  the-prices  thinking  tools  top-n  UGC  unit  unsupervised  values  video  web  wonkish  workshop  worrydream  yvain  🌞  🎓  🎩  🖥 

Copy this bookmark:



description:


tags: