Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems

TitleLower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
Publication TypeBook Chapters
Year of Publication2006
AuthorsAmbainis A, Gasarch W, Srinivasan A, Utis A
EditorAsano T
Book TitleAlgorithms and ComputationAlgorithms and Computation
Series TitleLecture Notes in Computer Science
Volume4288
Pagination628 - 637
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-49694-6
Abstract

A sub-area of discrepancy theory that has received much attention in computer science re-cently, is that of explicit constructions of low-discrepancy point sets for various types of rectangle
families in high dimension. This research has led to interesting applications in error-control cod-
ing, distributed protocols, Web document filtering, derandomization, and other areas. We give
a short survey of this area here.

URLhttp://dx.doi.org/10.1007/11940128_63