Zobrazeno 1 - 10
of 48
pro vyhledávání: '"Theory of computation ��� Communication complexity"'
Autor:
Haviv, Ishay, Parnas, Michal
Publikováno v:
Journal of Computer and System Sciences. 134:73-86
A $0,1$ matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers $k$, there exists a square regular $0,1$ matrix with binary rank $k$, such that the Boolean rank of its compl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::112d78c1b1baea7558cf33a86394465e
https://doi.org/10.1016/j.jcss.2023.01.005
https://doi.org/10.1016/j.jcss.2023.01.005
Much of today’s communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric f-c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b0c38e81ef82f75381e1d61ec0fab01e
Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the n participating parties may decide to broadcast a message to all the others, potentially causing coll
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9477d1529fbbef9534c57f365ec324a2
Agreement protocols for partially synchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine fau
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b4d134281aa3bcfeb0f54dcc52d30752
Autor:
Arunachalam, Srinivasan, Girish, Uma
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on n bits for which reducing the enta
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8c3e614f3e4d57bb335066670af0e382
In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate γ₂-
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1df2dfa9f80e770a4eb69fd245a4c3ed
Autor:
Alman, Josh, Błasiok, Jarosław
Three-player Number On the Forehead communication may be thought of as a three-player Number In the Hand promise model, in which each player is given the inputs that are supposedly on the other two players' heads, and promised that they are consisten
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::214f0713d05f66624791779f8f0a7bad
Autor:
Oshman, Rotem, Roth, Tal
We consider a multiparty setting where k parties have private inputs X_1,…,X_k ⊆ [n] and wish to compute the intersection ⋂_{𝓁 =1}^k X_𝓁 of their sets, using as little communication as possible. This task generalizes the well-known proble
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7d2f228f365d6e1f1c533f6694b5870b
It is well-known that randomized communication protocols are more powerful than deterministic protocols. In particular the Equality function requires Ω(n) deterministic communication complexity but has efficient randomized protocols. Previous work o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::19c0ff151bc3885a1a7afffea6478df0
Publikováno v:
13th Innovations in Theoretical Computer Science Conference: ITCS 2022, January 31-February 3, 2022, Berkeley, CA, USA
13th Innovations in Theoretical Computer Science Conference
ITCS 2022-13th Innovations in Theoretical Computer Science Conference
ITCS 2022-13th Innovations in Theoretical Computer Science Conference, Jan 2022, Berkeley, United States. pp.1-2410, ⟨10.4230/LIPIcs.ITCS.2022.48⟩
Christandl, M, Fawzi, O, Ta, H & Zuiddam, J 2022, Larger Corner-Free Sets from Combinatorial Degenerations . in 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) ., 48, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, vol. 215, pp. 1-20, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Virtuel, 31/01/2022 . https://doi.org/10.4230/LIPIcs.ITCS.2022.48
13th Innovations in Theoretical Computer Science Conference
ITCS 2022-13th Innovations in Theoretical Computer Science Conference
ITCS 2022-13th Innovations in Theoretical Computer Science Conference, Jan 2022, Berkeley, United States. pp.1-2410, ⟨10.4230/LIPIcs.ITCS.2022.48⟩
Christandl, M, Fawzi, O, Ta, H & Zuiddam, J 2022, Larger Corner-Free Sets from Combinatorial Degenerations . in 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) ., 48, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, vol. 215, pp. 1-20, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Virtuel, 31/01/2022 . https://doi.org/10.4230/LIPIcs.ITCS.2022.48
There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8899b556002db43adc30f0797998cf5d
https://hdl.handle.net/11245.1/5c8e1f24-3e61-499b-987a-621569cd8301
https://hdl.handle.net/11245.1/5c8e1f24-3e61-499b-987a-621569cd8301