Query Complexity of Sampling and Small Geometric Partitions
From MaRDI portal
Publication:5364254
DOI10.1017/S0963548314000704zbMath1371.68097arXiv1411.3799MaRDI QIDQ5364254
Navin Goyal, Luis Rademacher, Santosh Vempala
Publication date: 4 October 2017
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1411.3799
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial structures in finite projective spaces (51E20)
Cites Work
- Unnamed Item
- Unnamed Item
- Dispersion of mass and the complexity of randomized geometric algorithms
- On decompositions of complete hypergraphs
- Geometric algorithms and combinatorial optimization
- Decomposition of the complete r-graph into complete r-partite r-graphs
- On partitions of discrete boxes
- Information-theoretic approximations of the nonnegative rank
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- Applications of matrix methods to the theory of lower bounds in computational complexity
- On the size of Kakeya sets in finite fields
- Communication Complexity
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- On the Addressing Problem for Loop Switching
- Solving convex programs by random walks
This page was built for publication: Query Complexity of Sampling and Small Geometric Partitions
