Query complexity of sampling and small geometric partitions

Abstract: In this paper we study the following problem: Discrete partitioning problem (DPP): Let

m a t h b b F_{q} P^{n}

denote the

n

-dimensional finite projective space over

m a t h b b F_{q}

. For positive integer

k l e q n

, let

{A^{i}}_{i = 1}^{N}

be a partition of

(m a t h b b F_{q} P^{n})^{k}

such that (1) for all

i l e q N

,

A^{i} = p r o d_{j = 1}^{k} A_{j}^{i}

(partition into product sets), (2) for all

i l e q N

, there is a

(k - 1)

-dimensional subspace

L^{i} s u b s e t e q m a t h b b F_{q} P^{n}

such that

A^{i} s u b s e t e q (L^{i})^{k}

. What is the minimum value of

N

as a function of

q, n, k

? We will be mainly interested in the case

k = n

.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Query complexity of sampling and small geometric partitions