Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Majority is incompressible by AC0P circuits

Tools
- Tools
+ Tools

Oliveira, Igor C. and Santhanam, Rahul (2015) Majority is incompressible by AC0P circuits. In: Proceedings of the 30th Conference on Computational Complexity, Portland, Oregon, USA., 17-19 Jun 2015. Published in: Leibniz International Proceedings in Informatics (LIPIcs) pp. 124-157. ISSN 1868-8969. doi:10.4230/LIPIcs.CCC.2015.124

[img]
Preview
PDF
WRAP-majority-incompressible-AC0P-circuits-Oliveira-2015.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution.

Download (767Kb) | Preview
Official URL: https://doi.org/10.4230/LIPIcs.CCC.2015.124

Request Changes to record.

Abstract

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 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 fan-in depth-d 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 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 r-round AC^0[p]-compression cost of Majority_n is n^(Theta(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 Majority_n. Stronger lower bounds for functions in NP would separate NP from NC^1. Finally, we consider the round separation question for two-party AC-compression games, and significantly improve known separations between r-round and (r+1)-round protocols, for any constant r.

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Data compression (Computer science), Computational complexity, Computer science -- Mathematics, Logic, Symbolic and mathematical
Journal or Publication Title: Leibniz International Proceedings in Informatics (LIPIcs)
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Place of Publication: Germany
ISSN: 1868-8969
Official Date: 2015
Dates:
DateEvent
2015Published
8 June 2015Accepted
Page Range: pp. 124-157
DOI: 10.4230/LIPIcs.CCC.2015.124
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
615075Seventh Framework Programmehttp://dx.doi.org/10.13039/100011102
CCF-1116702National Science Foundationhttp://dx.doi.org/10.13039/501100008982
CCF-1115703National Science Foundationhttp://dx.doi.org/10.13039/501100008982
Conference Paper Type: Paper
Title of Event: Proceedings of the 30th Conference on Computational Complexity
Type of Event: Conference
Location of Event: Portland, Oregon, USA.
Date(s) of Event: 17-19 Jun 2015

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us