Query complexity of sampling and small geometric partitions
Preprint
Abstract
In this paper we study the following problem: Discrete partitioning problem (DPP): Let $\mathbb{F}_q P^n$ denote the $n$-dimensional finite projective space over $\mathbb{F}_q$. For positive integer $k \leq n$, let $\{ A^i\}_{i=1}^N$ be a partition of $(\mathbb{F}_q P^n)^k$ such that (1) for all $i \leq N$, $A^i = \prod_{j=1}^k A^i_j$ (partition into product sets), (2) for all $i \leq N$, there is a $(k-1)$-dimensional subspace $L^i \subseteq \mathbb{F}_q P^n$ such that $A^i \subseteq (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$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Information-theoretic approximations of the nonnegative rankcomputational complexity, 2016
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-DistanceSIAM Journal on Computing, 2012
- On decompositions of complete hypergraphsJournal of Combinatorial Theory, Series A, 2009
- Dispersion of mass and the complexity of randomized geometric algorithmsAdvances in Mathematics, 2008
- On the size of Kakeya sets in finite fieldsJournal of the American Mathematical Society, 2008
- A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointnesscomputational complexity, 2006
- On partitions of discrete boxesDiscrete Mathematics, 2002
- Modern Projective Geometry2000
- Applications of matrix methods to the theory of lower bounds in computational complexityCombinatorica, 1990
- On the Addressing Problem for Loop SwitchingBell System Technical Journal, 1971