Lower Bounds for Elimination via Weak Regularity

Authors Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay



PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.21.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Arkadev Chattopadhyay
Pavel Dvorák
Michal Koucký
Bruno Loff
Sagnik Mukhopadhyay

Cite AsGet BibTex

Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Lower Bounds for Elimination via Weak Regularity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.21

Abstract

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. 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 x_1, ..., x_k and y_1, ..., y_k respectively, with x_i,y_i in {0,1}^n. They want to output a k-bit vector v, such that there exists one index i for which v_i is not equal f(x_i,y_i). 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. 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, to show that Greater-Than is weakly regular.
Keywords
  • communication complexity
  • elimination
  • discrepancy
  • regularity
  • greater-than

Metrics

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

References

  1. Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, and Leen Torenvliet. The communication complexity of enumeration, elimination, and selection. Journal of Computer and System Sciences, 63(2):148-185, 2001. Google Scholar
  2. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS), pages 209-218, 2002. Google Scholar
  3. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proceedings of the 42nd Symposium on Theory of Computing (STOC), pages 67-76, 2010. Google Scholar
  4. Amos Beimel, Sebastian Ben Daniel, Eyal Kushilevitz, and Enav Weinreb. Choosing, agreeing, and eliminating in communication complexity. Computational Complexity, 23(1):1-42, 2014. Google Scholar
  5. Mark Braverman and Anup Rao. Information equals amortized communication. In Proceedings of the 52nd Symposium on Foundations of Computer Science (FOCS), pages 748-757, 2011. Google Scholar
  6. Mark Braverman and Omri Weinstein. A discrepancy lower bound for information complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 459-470. Springer, 2012. Google Scholar
  7. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, 2006. Google Scholar
  8. Imre Csiszar and János Körner. Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, 2011. Google Scholar
  9. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. In Proceedings of the 47th Symposium on Theory of Computing (STOC), pages 257-266. ACM, 2015. 0. Google Scholar
  10. R. Jain, H. Klauck, and M. Santha. Optimal direct sum results for deterministic and randomized decision tree complexity. Information Processing Letters, 110(20):893-897, 2010. Google Scholar
  11. T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Proceedings of the 35th Symposium on Theory of Computing (STOC), pages 673-682, 2003. Google Scholar
  12. M. Karchmer, E. Kushilevitz, and N. Nisan. Fractional covers and communication complexity. SIAM Journal on Discrete Mathematics, 8(1):76-92, 1995. Google Scholar
  13. M. Karchmer, R. Raz, and A. Wigderson. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity, 5(3/4):191-204, 1995. Google Scholar
  14. Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255-265, 1990. Google Scholar
  15. Gilat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff. Direct sum fails for zero-error average communication. In Proceedings of the 5th Innovations in Theoretical Computer Science (ITCS), pages 517-522, 2014. Google Scholar
  16. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. 0. Google Scholar
  17. Troy Lee, Adi Shraibman, and Robert Špalek. A direct product theorem for discrepancy. In Proceedings of the 23rd Conference on Computational Complexity (CCC), pages 71-80. IEEE, 2008. Google Scholar
  18. Noam Nisan, Steven Rudich, and Mike Saks. Products and help bits in decision trees. SIAM Journal on Computing, 28(3):1035-1050, 1999. Google Scholar
  19. Ran Raz and Avi Wigderson. Probabilistic communication complexity of boolean relations. In Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS), pages 562-567, 1989. Google Scholar
  20. Alan L. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. In Proceedings of the 6th International Colloquium on Automata, Languages and Programming (ICALP), pages 546-555, 1979. Google Scholar
  21. Ronen Shaltiel. Towards proving strong direct product theorems. In Proceedings of the 16th Conference on Computational Complexity (CCC), pages 107-119, 2001. Google Scholar
  22. Endre Szemerédi. Regular partitions of graphs. Technical report, DTIC Document, 1975. Google Scholar
  23. Emanuele Viola. The communication complexity of addition. Combinatorica, 35(6):703-747, 2015. 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