Projects per year
Abstract / Description of output
We consider C-compression games, a hybrid model between computational and communication complexity. A C-compression game for a function f : {0, 1}
n → {0, 1} is a two-party communication game, where the first party Alice knows the entire input x but is restricted to use strategies computed by C-circuits, 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 AC0d[p]-compression protocol to compute Majorityn requires communication n/(log n)2d+O(1), where p is prime, and AC0d [p] denotes polynomial size unbounded fan-in 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 fan-in of oracle gates in constant-depth oracle circuits computing Majorityn.
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 r-round AC0 [p]-compression cost of Majorityn is n Θ(1/r). This result implies almost tight lower bounds on the maximum individual fan-in of
oracle gates in certain restricted bounded-depth oracle circuits computing Majorityn. Stronger lower bounds for functions in NP would separate NP from NC1.
Finally, we consider the round separation question for two-party AC0 compression games, and significantly improve known separations between r-round and (r + 1)-round protocols, for any constant r.
n → {0, 1} is a two-party communication game, where the first party Alice knows the entire input x but is restricted to use strategies computed by C-circuits, 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 AC0d[p]-compression protocol to compute Majorityn requires communication n/(log n)2d+O(1), where p is prime, and AC0d [p] denotes polynomial size unbounded fan-in 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 fan-in of oracle gates in constant-depth oracle circuits computing Majorityn.
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 r-round AC0 [p]-compression cost of Majorityn is n Θ(1/r). This result implies almost tight lower bounds on the maximum individual fan-in of
oracle gates in certain restricted bounded-depth oracle circuits computing Majorityn. Stronger lower bounds for functions in NP would separate NP from NC1.
Finally, we consider the round separation question for two-party AC0 compression games, and significantly improve known separations between r-round and (r + 1)-round protocols, for any constant r.
Original language | English |
---|---|
Pages (from-to) | 173-210 |
Number of pages | 37 |
Journal | Electronic Colloquium on Computational Complexity (ECCC) |
Volume | 21 |
Publication status | Published - 13 Dec 2014 |
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