3 years ago

Simultaneous Multiparty Communication Complexity of Composed Functions.

Yassine Hamoudi

In the Number On the Forehead (NOF) multiparty communication model, $k$ players want to evaluate a function $F : X_1 \times\cdots\times X_k\rightarrow Y$ on some input $(x_1,\dots,x_k)$ by broadcasting bits according to a predetermined protocol. The input is distributed in such a way that each player $i$ sees all of it except $x_i$. In the simultaneous setting, the players cannot speak to each other but instead send information to a referee. The referee does not know the players' input, and cannot give any information back. At the end, the referee must be able to recover $F(x_1,\dots,x_k)$ from what she obtained.

A central open question, called the $\log n$ barrier, is to find a function which is hard to compute for $polylog(n)$ or more players (where the $x_i

s have size $poly(n)$) in the simultaneous NOF model. This has important applications in circuit complexity, as it could help to separate $ACC^0$ from other complexity classes. One of the candidates belongs to the family of composed functions. The input to these functions is represented by a $k\times (t\cdot n)$ boolean matrix $M$, whose row $i$ is the input $x_i$ and $t$ is a block-width parameter. A symmetric composed function acting on $M$ is specified by two symmetric $n$- and $kt$-variate functions $f$ and $g$, that output $f\circ g(M)=f(g(B_1),\dots,g(B_n))$ where $B_j$ is the $j$-th block of width $t$ of $M$. As the majority function $MAJ$ is conjectured to be outside of $ACC^0$, Babai et. al. suggested to study $MAJ\circ MAJ_t$, with $t$ large enough.

So far, it was only known that $t=1$ is not enough for $MAJ\circ MAJ_t$ to break the $\log n$ barrier in the simultaneous deterministic NOF model. In this paper, we extend this result to any constant block-width $t>1$, by giving a protocol of cost $2^{O(2^t)}\log^{2^{t+1}}(n)$ for any symmetric composed function when there are $2^{\Omega(2^t)}\log n$ players.

Publisher URL: http://arxiv.org/abs/1710.01969

DOI: arXiv:1710.01969v2

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.

s\nhave size $poly(n)$) in the simultaneous NOF model. This has important\napplications in circuit complexity, as it could help to separate $ACC^0$ from\nother complexity classes. One of the candidates belongs to the family of\ncomposed functions. The input to these functions is represented by a $k\\times\n(t\\cdot n)$ boolean matrix $M$, whose row $i$ is the input $x_i$ and $t$ is a\nblock-width parameter. A symmetric composed function acting on $M$ is specified\nby two symmetric $n$- and $kt$-variate functions $f$ and $g$, that output\n$f\\circ g(M)=f(g(B_1),\\dots,g(B_n))$ where $B_j$ is the $j$-th block of width\n$t$ of $M$. As the majority function $MAJ$ is conjectured to be outside of\n$ACC^0$, Babai et. al. suggested to study $MAJ\\circ MAJ_t$, with $t$ large\nenough.\n

\n

So far, it was only known that $t=1$ is not enough for $MAJ\\circ MAJ_t$ to\nbreak the $\\log n$ barrier in the simultaneous deterministic NOF model. In this\npaper, we extend this result to any constant block-width $t>1$, by giving a\nprotocol of cost $2^{O(2^t)}\\log^{2^{t+1}}(n)$ for any symmetric composed\nfunction when there are $2^{\\Omega(2^t)}\\log n$ players.\n

","htmlAbstract":null,"createdDate":"2019-10-03T09:40:29.000Z","media":null,"settings":null,"pdfUrl":"https://arxiv.org/pdf/1710.01969","openAccessUrl":null,"authors":{"type":"json","json":["Yassine Hamoudi"]},"contentType":null,"actionButton":null,"journal":{"type":"id","generated":false,"id":"Journal:1156","typename":"Journal"},"headlineImage":null,"__typename":"V4Paper","doi":"arXiv:1710.01969v2","paperUrl":"http://arxiv.org/abs/1710.01969","metrics":{"type":"id","generated":true,"id":"$V4Paper:283247.metrics","typename":"Metrics"}},"Journal:1156":{"id":"1156","name":"arXiv Computer Science","cover":{"type":"id","generated":true,"id":"$Journal:1156.cover","typename":"Image"},"__typename":"Journal"},"$Journal:1156.cover":{"baseURL":"https://s3-eu-west-1.amazonaws.com/stackademic/assets/journal_cover_arxviv.png","__typename":"Image"},"$V4Paper:283247.metrics":{"selectedCount":0,"viewedCount":5,"bookmarkedCount":0,"__typename":"Metrics"}}; window.__REDUX_STATE__ = {"feed":{"scrollPos":0,"openAccess":false,"performRefetch":{}},"history":{"historyChanges":0},"onboarding":{"stepsList":[{"stepId":"type","stepName":"What kind of researcher are you?","stepDesc":"","options":[]},{"stepId":"Role","stepName":"What role describes you the best?","stepDesc":"","options":[]},{"stepId":"Org","stepName":"Where do you work or study?","stepDesc":""},{"stepId":"ra","stepName":"Research Areas","stepDesc":"Select the research areas you are interested in","options":[]},{"stepId":"topics","stepName":"Topics","stepDesc":"Select the topics you are interested in","options":[]},{"stepId":"publications","stepName":"Publications","stepDesc":"We have selected some popular publications for you to follow","options":[]},{"stepId":"feeds","stepName":"Feeds","stepDesc":"We have created this feed based on your interests, you can edit and add more from the side menu","options":[]}],"step":1,"loading":false,"loadingText":"Loading...","selections":[{"name":"type","selection":null,"type":"single","mandatory":true},{"name":"role","selection":null,"type":"single","mandatory":true},{"name":"work_study","selection":null,"type":"single","mandatory":false},{"name":"ra","selection":[],"type":"multiple","mandatory":true},{"name":"topics","selection":[],"type":"multiple","mandatory":true},{"name":"publications","selection":[],"type":"multiple","mandatory":false},{"name":"feeds","selection":[],"type":"multiple","mandatory":false}],"topicsNextCursor":null,"topicsFetchingNext":false}};
3 years ago

Simultaneous Multiparty Communication Complexity of Composed Functions.

Yassine Hamoudi

In the Number On the Forehead (NOF) multiparty communication model, $k$ players want to evaluate a function $F : X_1 \times\cdots\times X_k\rightarrow Y$ on some input $(x_1,\dots,x_k)$ by broadcasting bits according to a predetermined protocol. The input is distributed in such a way that each player $i$ sees all of it except $x_i$. In the simultaneous setting, the players cannot speak to each other but instead send information to a referee. The referee does not know the players' input, and cannot give any information back. At the end, the referee must be able to recover $F(x_1,\dots,x_k)$ from what she obtained.

A central open question, called the $\log n$ barrier, is to find a function which is hard to compute for $polylog(n)$ or more players (where the $x_i

s have size $poly(n)$) in the simultaneous NOF model. This has important applications in circuit complexity, as it could help to separate $ACC^0$ from other complexity classes. One of the candidates belongs to the family of composed functions. The input to these functions is represented by a $k\times (t\cdot n)$ boolean matrix $M$, whose row $i$ is the input $x_i$ and $t$ is a block-width parameter. A symmetric composed function acting on $M$ is specified by two symmetric $n$- and $kt$-variate functions $f$ and $g$, that output $f\circ g(M)=f(g(B_1),\dots,g(B_n))$ where $B_j$ is the $j$-th block of width $t$ of $M$. As the majority function $MAJ$ is conjectured to be outside of $ACC^0$, Babai et. al. suggested to study $MAJ\circ MAJ_t$, with $t$ large enough.

So far, it was only known that $t=1$ is not enough for $MAJ\circ MAJ_t$ to break the $\log n$ barrier in the simultaneous deterministic NOF model. In this paper, we extend this result to any constant block-width $t>1$, by giving a protocol of cost $2^{O(2^t)}\log^{2^{t+1}}(n)$ for any symmetric composed function when there are $2^{\Omega(2^t)}\log n$ players.

Publisher URL: http://arxiv.org/abs/1710.01969

DOI: arXiv:1710.01969v2

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.