coding-theory   62

« earlier    

[1512.01625] Coded MapReduce
Feels, at first glance, a lot like the 'sudoku' methods in genomics, and uses of codes in experimental designs
mapreduce  arxiv  computerscience  research-article  code  coding-theory 
november 2018 by arthegall
Is the human brain analog or digital? - Quora
The brain is neither analog nor digital, but works using a signal processing paradigm that has some properties in common with both.
Unlike a digital computer, the brain does not use binary logic or binary addressable memory, and it does not perform binary arithmetic. Information in the brain is represented in terms of statistical approximations and estimations rather than exact values. The brain is also non-deterministic and cannot replay instruction sequences with error-free precision. So in all these ways, the brain is definitely not "digital".
At the same time, the signals sent around the brain are "either-or" states that are similar to binary. A neuron fires or it does not. These all-or-nothing pulses are the basic language of the brain. So in this sense, the brain is computing using something like binary signals. Instead of 1s and 0s, or "on" and "off", the brain uses "spike" or "no spike" (referring to the firing of a neuron).
q-n-a  qra  expert-experience  neuro  neuro-nitgrit  analogy  deep-learning  nature  discrete  smoothness  IEEE  bits  coding-theory  communication  trivia  bio  volo-avolo  causation  random  order-disorder  ems  models  methodology  abstraction  nitty-gritty  computation  physics  electromag  scale  coarse-fine 
april 2018 by nhaliday
What Does a “Normal” Human Genome Look Like? | Science
So, what have our first glimpses of variation in the genomes of generally healthy people taught us? First, balancing selection, the evolutionary process that favors genetic diversification rather than the fixation of a single “best” variant, appears to play a minor role outside the immune system. Local adaptation, which accounts for variation in traits such as pigmentation, dietary specialization, and susceptibility to particular pathogens is also a second-tier player. What is on the top tier? Increasingly, the answer appears to be mutations that are “deleterious” by biochemical or standard evolutionary criteria. These mutations, as has long been appreciated, overwhelmingly make up the most abundant form of nonneutral variation in all genomes. A model for human genetic individuality is emerging in which there actually is a “wild-type” human genome—one in which most genes exist in an evolutionarily optimized form. There just are no “wild-type” humans: We each fall short of this Platonic ideal in our own distinctive ways.
article  essay  org:nat  🌞  bio  biodet  genetics  genomics  mutation  genetic-load  QTL  evolution  sapiens  survey  summary  coding-theory  enhancement  signal-noise  egalitarianism-hierarchy  selection  tradeoffs  immune  recent-selection  perturbation  nibble  ideas  forms-instances 
november 2017 by nhaliday
My Old Boss | West Hunter
Back in those days, there was interest in finding better ways to communicate with a submerged submarine.  One method under consideration used an orbiting laser to send pulses of light over the ocean, using a special wavelength, for which there was a very good detector.  Since even the people running the laser might not know the boomer’s exact location, while weather and such might also interfere,  my old boss was trying to figure out methods of reliably transmitting messages when some pulses were randomly lost – which is of course a well-developed subject,  error-correcting codes. But he didn’t know that.  Hadn’t even heard of it.

Around this time, my old boss was flying from LA to Washington, and started talking with his seatmate about this  submarine communication problem.  His seatmate – Irving S. Reed – politely said that he had done a little work on some similar problems.  During this conversation, my informant, a fellow minion sitting behind my old boss, was doggedly choking back hysterical laughter, not wanting to interrupt this very special conversation.
west-hunter  scitariat  stories  reflection  working-stiff  engineering  dirty-hands  electromag  communication  coding-theory  giants  bits  management  signal-noise 
september 2017 by nhaliday
10 million DTC dense marker genotypes by end of 2017? – Gene Expression
Ultimately I do wonder if I was a bit too optimistic that 50% of the US population will be sequenced at 30x by 2025. But the dynamic is quite likely to change rapidly because of a technological shift as the sector goes through a productivity uptick. We’re talking about exponential growth, which humans have weak intuition about….
gnxp  scitariat  commentary  biotech  scaling-up  genetics  genomics  scale  bioinformatics  multi  toys  measurement  duplication  signal-noise  coding-theory 
june 2017 by nhaliday
[1512.02673] Speeding Up Distributed Machine Learning Using Codes
odes are widely used in many engineering applications to offer some form of reliability and fault tolerance. The high-level idea of coding is to exploit resource redundancy to deliver higher robustness against system noise. In large-scale systems there are several types of "noise" that can affect the performance of distributed machine learning algorithms: straggler nodes, system failures, or communication bottlenecks. Moreover, redundancy is abundant: a plethora of nodes, a lot of spare storage, etc.
In this work, scratching the surface of "codes for distributed computation," we provide theoretical insights on how coded solutions can achieve significant gains compared to uncoded ones. We focus on two of the most basic building blocks of distributed learning algorithms: matrix multiplication and data shuffling. For matrix multiplication, we use codes to leverage the plethora of nodes and alleviate the effects of stragglers. We show that if the number of workers is $n$, and the runtime of each subtask has an exponential tail, the optimal coded matrix multiplication is $\Theta(\log n)$ times faster than the uncoded matrix multiplication. In data shuffling, we use codes to exploit the excess in storage and reduce communication bottlenecks. We show that when $\alpha$ is the fraction of the data matrix that can be cached at each worker, and $n$ is the number of workers, coded shuffling reduces the communication cost by a factor $\Theta(\alpha \gamma(n))$ compared to uncoded shuffling, where $\gamma(n)$ is the ratio of the cost of unicasting $n$ messages to $n$ users to broadcasting a common message (of the same size) to $n$ users. Our synthetic and Open MPI experiments on Amazon EC2 show that coded distributed algorithms can achieve significant speedups of up to 40% compared to uncoded distributed algorithms.
papers  to-read  distributed-systems  machine-learning  coding-theory 
march 2017 by mraginsky
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:**  quixotic 
february 2017 by nhaliday
What is the relationship between information theory and Coding theory? - Quora
- finite vs. asymptotic
- combinatorial vs. probabilistic (lotsa overlap their)
- worst-case (Hamming) vs. distributional (Shannon)

Information and coding theory most often appear together in the subject of error correction over noisy channels. Historically, they were born at almost exactly the same time - both Richard Hamming and Claude Shannon were working at Bell Labs when this happened. Information theory tends to heavily use tools from probability theory (together with an "asymptotic" way of thinking about the world), while traditional "algebraic" coding theory tends to employ mathematics that are much more finite sequence length/combinatorial in nature, including linear algebra over Galois Fields. The emergence in the late 90s and first decade of 2000 of codes over graphs blurred this distinction though, as code classes such as low density parity check codes employ both asymptotic analysis and random code selection techniques which have counterparts in information theory.

They do not subsume each other. Information theory touches on many other aspects that coding theory does not, and vice-versa. Information theory also touches on compression (lossy & lossless), statistics (e.g. large deviations), modeling (e.g. Minimum Description Length). Coding theory pays a lot of attention to sphere packing and coverings for finite length sequences - information theory addresses these problems (channel & lossy source coding) only in an asymptotic/approximate sense.
q-n-a  qra  math  acm  tcs  information-theory  coding-theory  big-picture  comparison  confusion  explanation  linear-algebra  polynomials  limits  finiteness  math.CO  hi-order-bits  synthesis  probability  bits  hamming  shannon  intricacy  nibble  s:null  signal-noise 
february 2017 by nhaliday

« earlier    

related tags

aaronson  abstraction  accretion  acm  acmtariat  adna  advice  alg-combo  algebra  algebraic-complexity  algorithm  algorithms  analogy  applications  approximation  archaeology  archaics  arrows  article  arxiv  bayesian  bch-code  behavioral-gen  big-list  big-picture  bio  biodet  bioinformatics  biotech  bits  blogs  boaz-barak  book  books  boolean-analysis  cartoons  causation  channel-coding  circuits  classic  coarse-fine  cocktail  code  codes  coding  combinatorics  commentary  communication-complexity  communication  communications  comparison  complexity  compressed-sensing  compression  computation  computer-science  computerscience  concentration-of-measure  concept  conceptual-vocab  concrete  confusion  convexity-curvature  cool  counting  course  crypto  cryptography  curvature  dana-moshkovitz  data  decision-theory  deep-learning  degrees-of-freedom  differential-privacy  dimensionality  direction  dirty-hands  discrete  discussion  distributed-systems  distribution  dna  draft  duality  duplication  ebook  egalitarianism-hierarchy  electromag  embeddings  embodied  ems  encoding  engineering  enhancement  entropy-like  erasure-code  erasure-coding  error  essay  estimate  evolution  expanders  expert-experience  explanation  exposition  fields  finite-field  finiteness  flux-stasis  forms-instances  fourier  frontier  galois-field  game-theory  gedanken  genetic-load  genetics  genomics  geometry  giants  gnxp  gowers  gradient-descent  graph-theory  graphical-models  graphs  ground-up  group-testing  hamming  hashing  have-read  heuristic  hi-order-bits  high-dimension  history  homepages  hsu  huge-data-the-biggest  humor  ideas  ieee  immune  impact  index  information-theory  information  infotheory  init  insight  interdisciplinary  intersection-connectedness  intersection  intricacy  intuition  ising  iteration-recursion  jargon  knowledge  learning-theory  lecture-notes  lectures  lens  levers  lifts-projections  limits  linear-algebra  linear-programming  linearity  list  log-sobolev  long-short-run  lower-bounds  luca-trevisan  machine-learning  madhu-sudan  magnitude  management  manifolds  mapreduce  markov  math.nt  math.rt  math  mathematics  mathtariat  matrix-factorization  maxim-gun  measure  measurement  metabuch  methodology  metric-space  mit  models  moments  monte-carlo  motivation  multi  multiplicative  mutation  nature  network-coding  networking  neuro-nitgrit  neuro  neurons  nibble  nitty-gritty  no-go  notes  novelty  nudge-targets  oly  online-learning  optimization  order-disorder  org:bleg  org:edu  org:mat  org:nat  oscillation  overflow  p:***  p:**  p:*  p:someday  papers  paradox  paternal-age  pcp  pdf  people  perturbation  phase-transition  philosophy  physics  pigeonhole-markov  polar-codes  polynomials  preprint  princeton  probabilistic-method  probability  problem-solving  programming  proof-systems  proofs  pseudorandomness  q-n-a  qra  qtl  quantum-info  quantum  questions  quixotic  quotes  rand-approx  rand-complexity  random  rather-interesting  reading  recent-selection  recommendations  reed-solomon  reference  reflection  relativization  representation  research-article  research  retrofit  rigidity  rigorous-crypto  robust  rounding  s:***  s:null  sage  sampling  sanjeev-arora  sapiens  scale  scaling-up  science  scitariat  sdp  security  selection  sensor-networks  shannon  signal-noise  signal-processing  similarity  slides  smoothness  society  soft-question  solomon-code  space-complexity  sparsity  speculation  stackex  stanford  stat-mech  statistics  stories  study  sublinear  summary  survey  synthesis  talks  tcs  tcstariat  techtariat  the-trenches  thermo  thinking  thurston  tidbits  time  to-read  toolkit  topics  toys  traces  tradeoffs  tricki  trivia  turbo-codes-alternative  ugc  unintended-consequences  unit  valiant  video  visual-understanding  volo-avolo  von-neumann  washington  west-hunter  wigderson  wiki  wikipedia  wild-ideas  wire-guided  working-stiff  wormholes  worrydream  yoga  🌞  🎓  👳  🔬 

Copy this bookmark: