Projects per year
Abstract / Description of output
We consider Ccompression games, a hybrid model between computational and communication complexity. A Ccompression game for a function f:{0,1}^n > {0,1} is a twoparty communication game, where the first party Alice knows the entire input x but is restricted to use strategies computed by Ccircuits, while the second party Bob initially has no information about the input, but is computationally unbounded. The parties implement an interactive communication protocol to decide the value of f(x), and the communication cost of the protocol is the maximum number of bits sent by Alice as a function of n = x. We show that any AC_d[p]compression protocol to compute Majority_n requires communication n / (log(n))^(2d + O(1)), where p is prime, and AC_d[p] denotes polynomial size unbounded fanin depthd Boolean circuits extended with modulo p gates. This bound is essentially optimal, and settles a question of Chattopadhyay and Santhanam (2012). This result has a number of consequences, and yields a tight lower bound on the total fanin of oracle gates in constantdepth oracle circuits computing Majority_n. We define multiparty compression games, where Alice interacts in parallel with a polynomial number of players that are not allowed to communicate with each other, and communication cost is defined as the sum of the lengths of the longest messages sent by Alice during each round. In this setting, we prove that the randomized rround AC^0[p]compression cost of Majority_n is n^(Theta(1/r)). This result implies almost tight lower bounds on the maximum individual fanin of oracle gates in certain restricted boundeddepth oracle circuits computing Majority_n. Stronger lower bounds for functions in NP would separate NP from NC^1. Finally, we consider the round separation question for twoparty ACcompression games, and significantly improve known separations between rround and (r+1)round protocols, for any constant r.
Original language  English 

Title of host publication  30th Conference on Computational Complexity (CCC 2015) 
Editors  David Zuckerman 
Place of Publication  Dagstuhl, Germany 
Publisher  Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany 
Pages  124157 
Number of pages  34 
DOIs  
Publication status  Published  2015 
Publication series
Name  Leibniz International Proceedings in Informatics (LIPIcs) 

Publisher  Schloss DagstuhlLeibnizZentrum fuer Informatik 
Volume  33 
Fingerprint
Dive into the research topics of 'Majority is Incompressible by AC^{0}[p] Circuits'. Together they form a unique fingerprint.Projects
 1 Finished

ALUnif  Algorithms and Lower Bounds: A Unified Approach
Santhanam, R.
1/03/14 → 28/02/19
Project: Research