Zobrazeno 1 - 10
of 31
pro vyhledávání: '"Mika Göös"'
Publikováno v:
Theory of Computing. 16:1-30
For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols—or, equivalen
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b57d0ea6625f41481bf03098ceaacb7a
https://doi.org/10.4086/toc.2020.v016a013
https://doi.org/10.4086/toc.2020.v016a013
Publikováno v:
STOC
We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula $F$, 1) It is NP-hard to find a CP refutation of $F$ in time polynomial in the length of the shortest such refutation; and 2)unless Gap-Hitting-Set admits a nont
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::74ba46ed84c7acd4959955004602658f
Publikováno v:
computational complexity. 28:113-144
We prove that the PNP-type query complexity (alternatively, decision list width) of any Boolean function f is quadratically related to the PNP-type communication complexity of a lifted version of f. As an application, we show that a certain “produc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c18216db591436fe5878c703a367bbea
https://doi.org/10.1007/s00037-018-0175-5
https://doi.org/10.1007/s00037-018-0175-5
Publikováno v:
computational complexity. 27:245-304
We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $${\mathsf{P}}$$ and $${\mathsf{PSPACE}}$$ , short of proving lower bounds again
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::64fe6493e9bd75ea53ed8ba55af577bd
https://doi.org/10.1007/s00037-018-0166-6
https://doi.org/10.1007/s00037-018-0166-6
Autor:
Jukka Suomela, Mika Göös
Publikováno v:
Theory of Computing. 12:1-33
This work studies decision problems related to graph properties from the perspective of nondeterministic distributed algorithms. For a yes-instance there must exist a proof that can be verified with a distributed algorithm: all nodes must accept a va
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c9847ab82e9f03b2734d488dcb390a45
https://doi.org/10.4086/toc.2016.v012a019
https://doi.org/10.4086/toc.2016.v012a019
Autor:
Aviad Rubinstein, Mika Göös
Publikováno v:
FOCS
We prove an $N^{2-o(1)}$ lower bound on the randomized communication complexity of finding an $\epsilon$-approximate Nash equilibrium (for constant $\epsilon>0$) in a two-player $N\times N$ game.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::69ce977d14956194439265236d7b74c8
http://arxiv.org/abs/1805.06387
http://arxiv.org/abs/1805.06387
Publikováno v:
computational complexity. 28:543-544
Unfortunately, the inline image was not processed in the original version and the images are updated here. The original article has been corrected.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::12b929d3e52a5c7de033de48c871f3a0
https://doi.org/10.1007/s00037-019-00180-9
https://doi.org/10.1007/s00037-019-00180-9
Publikováno v:
FOCS
For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this me
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::82a8ca87887da70d4377035106849a9f
Publikováno v:
Journal of Computer and System Sciences. 80:297-319
The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular col
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b02036948ce8bbec39b45a63f4b96d0c
https://doi.org/10.1016/j.jcss.2013.08.003
https://doi.org/10.1016/j.jcss.2013.08.003
Autor:
Aleksandrs Belovs, Shalev Ben-David, Troy Lee, Rahul Jain, Miklos Santha, Robin Kothari, Mika Göös, Anurag Anshu
Publikováno v:
FOCS
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), Oct 2016, New Brunswick, United States. pp.555-564, ⟨10.1109/FOCS.2016.66⟩
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), Oct 2016, New Brunswick, United States. pp.555-564, ⟨10.1109/FOCS.2016.66⟩
While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4294c64c7b1e3e710a9c8e3f9fd411d9
https://doi.org/10.1109/focs.2016.66
https://doi.org/10.1109/focs.2016.66