coding-theory   62
[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….
https://gnxp.nofe.me/2017/06/27/genome-sequencing-for-the-people-is-near/
https://gnxp.nofe.me/2017/07/11/23andme-ancestry-only-is-49-99-for-prime-day/
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.
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
basically:
- 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

Copy this bookmark:

description:

tags: