Lower Bounds for Elimination via Weak Regularity

• Type: Article in International Conference Proceedings Book
• Date: 2017

Authors

Chattopadhyay, A (Author) Other; Dvorák, P (Author) Other; Koucký, M (Author) Other; Loff, B (Author) FCUP; Mukhopadhyay, S (Author) Other

Conference proceedings International

Title: 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany

Initial page: 21:1

34th Symposium on Theoretical Aspects of Computer Science, STACS 2017

8 March 2017 through 11 March 2017

Indexing

Scopus - 0 Citations

Other information

Authenticus ID: P-00N-9S9

DOI: 10.4230/lipics.stacs.2017.21

Abstract (EN): We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. [1] and later studied by Beimel et al. [4] for its connection to the famous direct sum question. In this problem, let f: {0, 1}2n ¿ {0,1} be any boolean function. Alice and Bob get k inputs x1,¿, xk and y1,¿, yk respectively, with xi, yi ¿ {0, 1}n. They want to output a k-bit vector v, such that there exists one index i for which vi = f(xi,yi). We prove a general result lower bounding the randomized communication complexity of the elimination problem for f using its discrepancy. Consequently, we obtain strong lower bounds for the functions Inner-Product and Greater-Than, that work for exponentially larger values of k than the best previous bounds. To prove our result, we use a pseudo-random notion called regularity that was first used by Raz and Wigderson [19]. We show that functions with small discrepancy are regular. We also observe that a weaker notion, that we call weak-regularity, already implies hardness of elimination. Finally, we give a different proof, borrowing ideas from Viola [23], to show that Greater-Than is weakly regular. © Arkadev Chattopadhyay, Pavel Dvo¿ák, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay.

Language: English

Type (Professor's evaluation): Scientific