**5**

votes

**1**answer

413 views

### Is this graph 3-colorable?

Consider the permutations of $0,1,1,2,2,3,3.$ Each permutation is corresponding to a vertex in graph $G$. So, the graph $G$ has $630$ vertices.
Each vertex has exactly 6 neighbors. $P$ is connected ...

**5**

votes

**1**answer

144 views

### Finite field analogue of Chebotaryov theorem on roots of unity?

Chebotarev's theorem on roots of unity says that all the minors of a prime-length DFT matrix over the complex numbers are nonzero. I was wondering if there was an analogue for finite fields.
More ...

**2**

votes

**0**answers

123 views

### capacity of a channel with random phase rotation

Consider a wireless channel $h=e^{j\theta}$, where $\theta$ is a uniform random variable in $[0,2\pi]$ independent of the input messages and the independent of the noise. The channel randomly rotates ...

**0**

votes

**0**answers

32 views

### transform a matrix into block circulant form

What's known about transforming a matrix into block circulant form?
Given an $K \times N$ matrix $M$ (over GF(2) for now although the case
over ${\mathbb C}$ or ${\mathbb R}$ are also of interest), ...

**6**

votes

**0**answers

80 views

### irregular LDPC code construction algorithm

I want to construct a sparse random binary matrix ${{\bf{H}}_{m \times n}}$ that has the following properties
1- Faction of columns of weight $i$ is ${v_i}$ .
2- Fraction of rows of weight ...

**0**

votes

**2**answers

72 views

### Binary Codes and its distance [closed]

Find n binary codes of length n such that distance between each pair is n/2 , where n is a even number , if possible?How to generate all codes? for example if n=4 we have 1110,1101,1011,0111 each pair ...

**3**

votes

**1**answer

91 views

### Effects of many degree-2 variable nodes in the Tanner graph during the decoding of LDPC codes

Suppose that we have a LDPC code $C$ with a $(n -k )\times n $ parity check matrix $H$, and there exist approximately $ \sqrt n$ numbers of degree-2 columns. It means that there are approximately ...

**1**

vote

**1**answer

64 views

### Optimal covering and CSPNG

Consider a function $f: \{0,1\}^n \to \{0,1\}^{cn}$, where $c>1$.
A random $f$ with high probability generates optimal covering of $\{0,1\}^{cn}$,
i. e.:
$\forall x \in \{0,1\}^{cn}$ $\exists y ...

**13**

votes

**3**answers

1k views

### A question on representation of graphs

Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...

**3**

votes

**0**answers

95 views

### Rank of a particular matrix

Denote $P_{2n}$ to be collection of homogeneous total degree $2$ real polynomials in exactly $2n$ variables such that coefficient of every monomial is either $1$ or $-1$.
Split variable set into ...

**4**

votes

**0**answers

117 views

### Application of finding shortest paths on Cayley graphs

For a fixed integer number $m$, Consider Cayley graph defined by all m-cycles in Symmetric group $Sym(n)$.
I know that for $m=2$,
there are some applications of finding shortest paths (or distance ...

**2**

votes

**0**answers

77 views

### The significance of the Parvaresh-Vardy curve

Even though this seems like a computer science question, it is purely mathematical and concerns polynomials and curves over finite fields.
Consider the Parvaresh-Vardy list decoder.
As I understand ...

**2**

votes

**1**answer

120 views

### Probability of Hamming weight

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$.
Denote $v_j\cap v_j$ to be ...

**3**

votes

**1**answer

115 views

### Maximal neighbour-full partition of $\{0,1\}^n$

What is the largest complete minor of the $n$-dimensional hypercube? (which we call $k(n)$)
Alternatively, what is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that ...

**2**

votes

**0**answers

221 views

### Hamming weight probability of projections

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick $2^{n^t}$ random vectors $\{v_i\}_{i=1}^{2^{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$.
If $v_i^\perp$ is ...

**1**

vote

**0**answers

68 views

### How do you use the bits you get back from Bits Back Coding?

Bits Back coding is a scheme to transmit an observation x.
You can read about it here [1]. To my understanding, it works like this:
The encoder samples a message z from a distribution Q(z|x) that it ...

**0**

votes

**1**answer

95 views

### Information theoretic common sequence agreement (not secret key)

Supposing Alice and Bob share $\rho$-correlated sequences in $\{0,1\}^n$, what coding theory based schemes are available for Alice and Bod to extract sequences $A,B\in\{0,1\}^n$ respectively such that ...

**6**

votes

**1**answer

151 views

### lower bound on A(k,4,floor(k/2))

A(k,4,r) is the independence number of the Johnson graph J(k,r).
What is the best known asymptotic lower bound on A(k,4,floor(k/2)) ?
I only obtained ...

**3**

votes

**1**answer

166 views

### Parity-check matrix for code with variable block size and minimum distance

Consider a linear error-correcting code with symbols in $GF(q)$, with codewords of length $k$ generated from messages of length $n$ and minimum distance $d+1 = k-n+1$. In the cases of interest, $q = ...

**11**

votes

**2**answers

481 views

### “The Two Sheriffs” puzzle -2: threshold for security

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects.
...

**29**

votes

**1**answer

2k views

### “The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.
Two sheriffs in neighboring towns are on the track of a killer, in a
case involving eight ...

**1**

vote

**1**answer

60 views

### Bound on the weight of the minimum weight generator of [n,k] cyclic codes?

I'm looking at creating sparse generator matrices for cyclic codes of a given length and dimension. A generator matrix of an [n,k] cyclic code can be expressed as
$G = \begin{bmatrix}g_0 & g_1 ...

**1**

vote

**1**answer

89 views

### Optimal covering

Let consider a problem of optimal covering of Hamming space.
So we have Hamming space $\{0,1\}^n$ and some integer $r$. We want to find a set $A \subseteq \{0,1\}^n$ such that any point from ...

**2**

votes

**0**answers

168 views

### PRNG and coding theory

Let $k, n \in \mathbb{N}$, $k = (1 - \epsilon)n$ where $1 >\epsilon > 0$.
I want to find $f: \{0,1\}^k \to \{0, 1\}^n$
such that:
1) $f(a) \not= f(b)$ if $a \not=b $
2) for any $x \in ...

**3**

votes

**2**answers

216 views

### Picking codewords that are close

I posted this question in http://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.
Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...

**3**

votes

**3**answers

100 views

### Block error-correcting codes over inhomogeneous alphabets

For $n := (n_1,\dots,n_N) \in \mathbb{N}_{>1}^N$, let $X_n := \prod_{j=1}^N [n_j]$, where as usual $[m] := \{1,\dots,m\}$.
Are there any known generic constructions for (Hamming) sphere ...

**0**

votes

**0**answers

120 views

### Minimum-size spanning group using hamming distance

For given natural numbers $N$ and $D$, we will define $F$ as all the non-negative integers less than $2^N$. A group $A \subseteq F$ will be "spanning", if and only if every number $x$ in $F$ satisfies ...

**1**

vote

**1**answer

251 views

### Correlation between two continuous-time stochastic processes

Consider two continous-time stochastic processes $\{A(t)\}_{t \ge 0}$ and $\{B(t)\}_{t \ge 0}$ with $A(t)=t$ and $B(t)=t$. Each process starts at $t=0$ and emits "ticks" at increasing time slots. For ...

**1**

vote

**0**answers

191 views

### Polynomial existence over finite field

Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$.
Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$).
Denote ...

**2**

votes

**0**answers

88 views

### On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$.
Denote concatenated pair $[uv]$.
Denote
$$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$
collection of pairs with Hamming distance $1$ from $[uv]$ string ...

**2**

votes

**2**answers

334 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**2**

votes

**2**answers

168 views

### Hamming graph and independent sets

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) ...

**3**

votes

**1**answer

125 views

### Balanced binary code that “resists” local decoding?

I am looking for a construction that can be stated as the following coding problem: a binary code with good distance ($d = \Omega(n)$ where codeword length is $n$) that "resists local decoding" in the ...

**13**

votes

**1**answer

619 views

### Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...

**32**

votes

**1**answer

581 views

### What measurable quantity can constrain the number of odors human can discriminate?

This is not a very typical MO question, but I hope you bear with me. It concerns a recent disagreement in the biology literature about how many different odors humans can discriminate. The authors of ...

**0**

votes

**2**answers

125 views

### Form of the Shannon capacity for Heptagon?

Is the $0$-error capacity of $7$-cycle:
$(1)$ known to be of form $7^q$ for some $q\in \mathbb Q$?

**1**

vote

**1**answer

109 views

### Coding for channels with concentrated error

Can we implement a reduced-error transmission over a channel with error frequency having $\liminf<\frac{1}{2}$ and $\limsup>\frac{1}{2}$?
We know that if a channel with error flips (in the ...

**-1**

votes

**1**answer

113 views

### Noise reduction in capacity-0 channels

Suppose we have a binary symmetric channel with $p=\frac{1}{3}$; that is, a communications channel in which each bit is flipped with independent probability $\frac{1}{3}$. I know that there is a code ...

**3**

votes

**0**answers

157 views

### On a problem of sphere-packing for Reed-Solomon codes

Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...

**3**

votes

**0**answers

118 views

### Applications of list decoding

This is citation from http://en.wikipedia.org/wiki/List_decoding:
Algorithms developed for list decoding of several interesting code families have found interesting applications in computational ...

**2**

votes

**1**answer

133 views

### Mutual information staying constant under composition of channels

Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Denote by $p(x)$ the input probability distribution.
The mutual information between the input and the output of ...

**3**

votes

**1**answer

839 views

### “Codes” in which a group of words are pairwise different at a certain position

I read the following problem, claimed to be in the IMO shortlist in 1988:
A test consists of four multiple choice problems, each with three options, and the students should give an unique answer ...

**4**

votes

**2**answers

155 views

### Another formulation of error-correcting coding problem

Consider classic error-correcting problem:
there is finite set $A$ and string $a_1...a_n$, $a_i \in A$ in the begin.
in the end we have $b_1...b_n$. Set places of errors $E = \{i| a_i\not= b_i \}$, ...

**1**

vote

**1**answer

107 views

### Group action of $G<\mathbb Z^\infty_2$ over the Golden mean shif [closed]

I'm am looking for an action of an infinite subgroup of $\mathbb Z^\infty_2$ over the golden mean shift space $$X=\{x\in \{0,1\}^\mathbb N : x_i=1\Rightarrow x_{i+1}=0\}$$ such that any element of $G$ ...

**1**

vote

**0**answers

109 views

### How can I decode efficiently a triple-error-correcting binary BCH code?

In a given $\mathrm{BCH}(N,K)$, $T=3$ code over $\mathrm{GF}(2^m)$, there are ways to find the error locations in a given $N$-bit codeword directly from the syndromes without going through the normal ...

**1**

vote

**1**answer

55 views

### Function field Towers of larger depth of recursion

A function field tower is a sequence of function fields
$$\mathcal{F}_0 \subset \mathcal{F}_1 \subset \mathcal{F}_2 \dots \subset \mathcal{F}_{n} \subset \mathcal{F}_{n+1} \subset \dots $$
over a base ...

**6**

votes

**3**answers

349 views

### On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$

Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows
$$ S=\left[\begin{array}{ccccccc}
0 & ...

**3**

votes

**0**answers

111 views

### Certain subgroup of automorphism groups of binary codes

Suppose that $C$ is an binary linear code of length $n$ and dimension $k$ (i.e. it's a $k$-dimensional linear subspace of $\mathbb{F}_2^n$). As usual, the automorphism group of $C$ is the subgroup of ...

**1**

vote

**2**answers

136 views

### Designing almost orthogonal vectors in a deterministic manner

Consider the vector space $\mathbb{R}^n$, the standard inner product $\langle \cdot,\cdot \rangle:\mathbb{R}^n\times\mathbb{R}^n\rightarrow \mathbb{R}$, and some $0<\epsilon\leq ...

**3**

votes

**0**answers

148 views

### Fully Homomorphic Error Correction?

Consider a field $F$. Suppose we have two vectors $a,b\in F^n$, and an invertible matrix $G\in F^{n\times n}$. Let $c\in F^n$ be the point-wise product of $a$ and $b$, that is, $c_i=a_ib_i$. Let ...