**14**

votes

**1**answer

898 views

### How to keep subsets disjoint?

Given positive integers $n$ and $k\le 2^n$, how to choose a subset $C\subset\{0,1\}^n$ of size $|C|=k$ to maximize the number of pairs $(c_1,c_2)\in C\times C$ with the supports of $c_1$ and $c_2$ ...

**1**

vote

**1**answer

280 views

### Large subgroups of the Hamming cube

Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube).
Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set ...

**7**

votes

**4**answers

1k views

### “sparse graphs are locally tree-like”

I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree ...

**1**

vote

**1**answer

410 views

### Matrix version of Berlekamp Massey algorithm

What are the most obvious generalizations of Berlekamp Massey algorithm [1] to matrix sequences?
[1] Massey, J. L., "Shift-register synthesis and BCH decoding", IEEE Trans. Information Theory ...

**2**

votes

**1**answer

273 views

### Optimal binary code for points in a metric+probability space

Does anyone know of any results on this topic?
Basically I'm considering this problem. You have some space $X$ from which you can draw points $x$ and $y$, a distance metric $d(x,y)$, and a ...

**4**

votes

**4**answers

620 views

### how to find vector $(\pm 1, \pm 1, \pm 1, … \pm 1)$ which is most close to given vector (r_1,…r_l) ? Is it NP-problem ? What algorithms are available ?

Given:
some vector $R=(r_1...r_l)$ - real numbers,
and a set of distinct vectors with $+1$ or $-1$ coordinates
$$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\\
V_2=(c_{2,1} ... c_{2,l}),\\\
...

**10**

votes

**3**answers

581 views

### MacWilliams Identity for Asymptotic Weight Spectrum of a Code

Introduction
Let $C$ be a code of block length $n$ having $A_i^C$ words of Hamming weight $i$, for $i\in [n]$, where $[n]:=\{0,\ldots,n\}$. Then, the sequence $\{ A_i^C \}_{i \in [n]} $ is called the ...

**4**

votes

**2**answers

369 views

### A Boolean function that is not constant on affine subspaces of large enough dimension

I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of ...

**7**

votes

**1**answer

2k views

### 12 balls weighing puzzle

In an article describing the twelve balls weighing problem, the author mentions a solution that involves the finite projective plane of order 3, discovered by Rick Wilson. Does anyone know what this ...

**1**

vote

**1**answer

322 views

### Algorithm for generating a size k error-correcting code on n bits

I want to generate a code on n bits for k different inputs that I want to classify. The main requirement of this code is the error-correcting criteria: that the minimum pairwise distance between any ...

**5**

votes

**2**answers

544 views

### Binary codes with large distance

Suppose $C \subset \lbrace 0,1\rbrace^{n}$ is a binary code with distance $\delta * n$, for $1/2 < \delta < 1$. Can $|C|$ be arbitrarily large (if I allow n to be arbitrarily large)? Note that ...