Document Open Access Logo

Majority is Incompressible by AC^0[p] Circuits

Authors Igor Carboni Oliveira, Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.124.pdf
  • Filesize: 0.74 MB
  • 34 pages

Document Identifiers

Author Details

Igor Carboni Oliveira
Rahul Santhanam

Cite As Get BibTex

Igor Carboni Oliveira and Rahul Santhanam. Majority is Incompressible by AC^0[p] Circuits. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 124-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CCC.2015.124

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.

Subject Classification

Keywords
  • interactive communication
  • compression
  • circuit lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. Transactions on Computation Theory (TOCT), 1(1), 2009. Google Scholar
  2. Miklós Ajtai. ∑₁¹-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. Google Scholar
  3. Miklós Ajtai and Michael Ben-Or. A theorem on probabilistic constant depth computations. In Symposium on Theory of Computing (STOC), pages 471-474, 1984. Google Scholar
  4. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3), 2010. Google Scholar
  5. Noga Alon and Ravi B. Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1-22, 1987. Google Scholar
  6. Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley, New York, 1992. Google Scholar
  7. Alexander E. Andreev. On a method for obtaining lower bounds for the complexity of individual monotone functions. Soviet Math. Dokl, 31(3):530-534, 1985. Google Scholar
  8. Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press, Cambridge, 2009. Google Scholar
  9. Theodore P. Baker, John Gill, and Robert Solovay. Relativizatons of the 𝖯 = ? NP Question. SIAM J. Comput., 4(4):431-442, 1975. Google Scholar
  10. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. Google Scholar
  11. Allan Borodin. Horner’s rule is uniquely optimal. In International Symposium on the Theory of Machines and Computations, pages 45-57, 1971. Google Scholar
  12. Harry Buhrman and John M. Hitchcock. NP-hard sets are exponentially dense unless coNP ⊆ NP/poly. In Conference on Computational Complexity (CCC), pages 1-7, 2008. Google Scholar
  13. Arkadev Chattopadhyay and Rahul Santhanam. Lower bounds on interactive compressibility by constant-depth circuits. In Symposium on Foundations of Computer Science (FOCS), pages 619-628, 2012. Google Scholar
  14. Holger Dell. A simple proof that AND-compression of NP-complete problems is hard. ECCC Report TR14-75, 2014. Google Scholar
  15. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM, 61(4):23, 2014. Google Scholar
  16. Andrew Drucker. New limits to classical and quantum instance compression. In Symposium on Foundations of Computer Science (FOCS), pages 609-618, 2012. Google Scholar
  17. Bella Dubrov and Yuval Ishai. On the randomness complexity of efficient sampling. In Symposium on Theory of Computing (STOC), pages 711-720, 2006. Google Scholar
  18. Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, and Vinod Vaikuntanathan. Protecting circuits from leakage: the computationally-bounded and noisy cases. In International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 135-156, 2010. Google Scholar
  19. William Feller. Generalization of a probability limit theorem of Cramér. Transactions of the American Mathematical Society, 54(3):361-372, 1943. Google Scholar
  20. Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci., 65(4):612-625, 2002. Google Scholar
  21. Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans-Ulrich Simon. Relations between communication complexity, linear arrangements, and computational complexity. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 171-182, 2001. Google Scholar
  22. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct pcps for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. Google Scholar
  23. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  24. Parikshit Gopalan and Rocco A. Servedio. Learning and lower bounds for AC^0 with threshold gates. In International Workshop on Randomization and Computation (RANDOM), pages 588-601, 2010. Google Scholar
  25. András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold circuits of bounded depth. J. Comput. Syst. Sci., 46(2):129-154, 1993. Google Scholar
  26. Danny Harnik and Moni Naor. On the compressibility of NP instances and cryptographic applications. SIAM J. Comput., 39(5):1667-1713, 2010. Google Scholar
  27. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Symposium on Theory of Computing (STOC), pages 6-20, 1986. Google Scholar
  28. V. M. Khrapchenko. A method of determining lower bounds for the complexity of π-schemes. Math. Notes Acad. of Sci. (USSR), 10(1):474-479, 1971. Google Scholar
  29. Swastik Kopparty and Srikanth Srinivasan. Certifying polynomials for AC^0(⊕) circuits, with applications. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 36-47, 2012. Google Scholar
  30. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  31. Jiří Matoušek and Jan Vondrák. Lecture notes on the probabilistic method, 2008. Google Scholar
  32. Eduard I. Nečiporuk. On a Boolean function. Soviet Math. Dokl., 7(4):999-1000, 1966. Google Scholar
  33. Igor C. Oliveira. Algorithms versus circuit lower bounds. ECCC Report TR13-117, 2013. Google Scholar
  34. Christos H. Papadimitriou and Michael Sipser. Communication complexity. J. Comput. Syst. Sci., 28(2):260-269, 1984. Google Scholar
  35. Alexander A. Razborov. Lower bounds on monotone complexity of the logical permanent. Mathematical Notes, 37(6):485-493, 1985. Google Scholar
  36. Alexander A. Razborov. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41(4):598-607, 1987. Google Scholar
  37. Alexander A. Razborov and Steven Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. Google Scholar
  38. Steven Rudich and Leonard Berman. Optimal circuits and transitive automorphism groups. In International Colloquium on Automata, Languages and Programming (ICALP), pages 516-524, 1988. Google Scholar
  39. Rahul Santhanam. Ironic complicity: Satisfiability algorithms and circuit lower bounds. Bulletin of the EATCS, 106:31-52, 2012. Google Scholar
  40. Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Symposium on Theory of Computing (STOC), pages 77-82, 1987. Google Scholar
  41. Srikanth Srinivasan. On improved degree lower bounds for polynomial approximation. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 201-212, 2013. Google Scholar
  42. Jun Tarui. Smallest formulas for the parity of 2^k variables are essentially unique. Theor. Comput. Sci., 411(26-28):2623-2627, 2010. Google Scholar
  43. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science (MFCS), pages 162-176, 1977. Google Scholar
  44. Leslie G. Valiant. Exponential lower bounds for restricted monotone circuits. In Symposium on Theory of Computing (STOC), pages 110-117, 1983. Google Scholar
  45. Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1-72, 2009. Google Scholar
  46. Ryan Williams. Algorithms for circuits and circuits for algorithms (Invited Talk). In Conference on Computational Complexity (CCC), pages 248-261, 2014. Google Scholar
  47. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Symposium on Theory of Computing (STOC), pages 664-673, 2014. Google Scholar
  48. Ryan Williams. Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2, 2014. Google Scholar
  49. Andrew Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In Symposium on Foundations of Computer Science (FOCS), pages 1-10, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact