The catalog

All problems

Every statement in the catalog, readable in place. Filters apply instantly; search covers names, IDs, and the LaTeX statements themselves.

Showing 11 of 280 problems in Information theory

DG-018

High-Dimensional Sphere-Packing Exponent

LandmarkOpen problemc. 1900

Let

Δ_{d}

be the supremal density of a packing of congruent balls in

R^{d}

. Determine the exponential asymptotics of

Δ_{d}

, equivalently determine

d \to \infty lim inf \frac{1}{d} lo g_{2} Δ_{d} and d \to \infty lim sup \frac{1}{d} lo g_{2} Δ_{d},

and decide whether these two quantities are equal.

DG-012

Five-Dimensional Kissing Number

MajorExact constant problemUnknown

Let

S^{4} = {x \in R^{5} : ∥ x ∥_{2} = 1}

. Determine

τ_{5} = max {∣ X ∣ : X \subset S^{4}, ⟨ x, y ⟩ \leq \frac{1}{2} for all distinct x, y \in X} .

Equivalently,

τ_{5}

is the maximum number of nonoverlapping unit

5

-balls that can simultaneously touch a fixed unit

5

-ball.

TCS-013

Existence of One-Way Functions

LandmarkOpen problem1976

Does there exist a polynomial-time computable, length-preserving function family

f_{n} : {0, 1}^{n} \to {0, 1}^{n}

such that, for every probabilistic polynomial-time algorithm

A

that outputs an

n

-bit string (or failure), and every polynomial

p

, for all sufficiently large

n

x \leftarrow {0, 1}^{n}, A Pr [f_{n} (A (1^{n}, f_{n} (x))) = f_{n} (x)] < \frac{1}{p ( n )} ?

TCS-015

Quantum Parallel Repetition Conjecture

MajorConjecture2004

For every finite two-player one-round game

G

whose entangled value satisfies

ω^{*} (G) < 1

, there is a constant

c_{G} > 0

such that the entangled value of the

n

-fold parallel repetition obeys

ω^{*} (G^{\otimes n}) \leq e^{- c_{G} n} (n \geq 1) .

INFO-004

Main Conjecture for MDS Codes

LandmarkConjecture1955

Let

q

be a prime power and

2 \leq k \leq q - 1

. If

C \subseteq F_{q}^{n}

is a

k

-dimensional linear code whose minimum Hamming distance is

n - k + 1

, then

n \leq q + 1,

except that, when

q

is even and

k \in {3, q - 1}

, the asserted bound is

n \leq q + 2

. The Hamming distance between two words is the number of coordinates in which they differ; a code meeting the general bound

n - k + 1

is called maximum-distance separable (MDS).

INFO-001

Shannon capacity of the seven-cycle

MajorExact constant problem1956

For finite simple graphs

G, H

, define their strong product to have vertex set

V (G) \times V (H)

, with distinct

(g, h)

and

(g^{'}, h^{'})

adjacent exactly when, in each coordinate, the entries are equal or adjacent and in at least one coordinate they are adjacent. Write

G^{⊠ k}

for the

k

-fold strong product and

α (G)

for the maximum size of an independent vertex set. Determine exactly

Θ (C_{7}) := k \geq 1 sup α (C_{7}^{⊠ k})^{1/ k},

where

C_{7}

is the cycle on seven vertices.

INFO-002

Capacity of the binary deletion channel

MajorExact constant problemc. 1961

Fix

d \in (0, 1)

. On input

x = (x_{1}, \dots, x_{n}) \in {0, 1}^{n}

, independently delete each coordinate with probability

d

and output the undeleted bits in their original order, without deletion markers. Let

M_{n} (d, ε)

be the largest cardinality of a code

C \subseteq {0, 1}^{n}

for which some decoder has average error at most

ε

under a uniformly selected codeword. Determine, for every

d \in (0, 1)

C_{del} (d) = ε ↓ 0 lim n \to \infty lim sup \frac{1}{n} lo g_{2} M_{n} (d, ε) .

INFO-003

Binary asymptotic rate–distance improvement problem

MajorOpen problem1952–1957

For

0 < δ < 1/2

, let

A_{2} (n, d)

be the largest cardinality of a set

C \subseteq {0, 1}^{n}

whose distinct words have Hamming distance at least

d

, and define

R_{2} (δ) = n \to \infty lim sup \frac{1}{n} lo g_{2} A_{2} (n, ⌈ δ n ⌉) .

Decide whether there exists

δ \in (0, 1/2)

for which

R_{2} (δ) > 1 - H_{2} (δ), H_{2} (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t) .

INFO-005

Asymptotic Spherical-Code Rate

MajorOpen problem1959

For

- 1 < s < 1

, let

A_{S} (d, s)

be the largest number of unit vectors in

R^{d}

whose pairwise inner products are at most

s

. Determine the asymptotic rate

R_{S} (s) = d \to \infty lim sup \frac{1}{d} lo g_{2} A_{S} (d, s)

for every fixed

s

, and determine where the corresponding limit exists.

INFO-006

Li–Li Undirected Network Coding Conjecture

MajorConjecture2004

For every finite undirected capacitated network with any finite collection of unicast source--sink pairs, the maximum common rate achievable by arbitrary network coding equals the maximum common rate achievable by fractional multicommodity routing.