Skip to main content

All Questions

Filter by
Sorted by
Tagged with
3 votes
2 answers
233 views

Lower bounding decoding error in a noisy adversarial channel

Problem description Suppose we have a finite alphabet $\mathcal{X}$, where each letter $X \in \mathcal{X}$ indexes into some fixed set of distributions, $\{P_{1},\ldots,P_{|\mathcal{X}|}\}$. For ...
user124784's user avatar
3 votes
0 answers
68 views

Does this information theoretical thought experiment have a name or corresponding area of research?

I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
exfret's user avatar
  • 509
3 votes
0 answers
299 views

Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from https://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The ...
user16007's user avatar
  • 800
1 vote
0 answers
62 views

Cramer Rao bound for relative estimation

I have an observed vector ${\bf y}$ from which I would like to estimate a parameter vector ${\bf c}$ (denote the estimate $\hat{{\bf c}}$). A feature of our estimation problem is that the involved ...
Sancho Panza's user avatar
0 votes
0 answers
52 views

Classifier-specific lower bounds on the misclassification rate in binary classification

Consider a binary classification problem for $(X,Y)$, and let $\hat{f}$ be a proposed classifier. We wish to bound the misclassification rate $P(\hat{f}(X)\ne Y)$. There are many known lower bounds on ...
tim523's user avatar
  • 13