Lower Bounds for Elimination via Weak Regularity

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2017

Autores

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

Ata de Conferência Internacional

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

Página Inicial: 21:1

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

8 March 2017 through 11 March 2017

Indexação

Scopus - 0 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica