Zobrazeno 1 - 10
of 13
pro vyhledávání: '"Amey Bhangale"'
Publikováno v:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f4d89ee248b78e51c8cf1d80d78a0c43
https://doi.org/10.1145/3564246.3585120
https://doi.org/10.1145/3564246.3585120
Publikováno v:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::35b22439db7edd96832b401f52b2c56e
https://doi.org/10.1145/3564246.3585121
https://doi.org/10.1145/3564246.3585121
Publikováno v:
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5114c74500f2375cbbfa28de7b9834a4
https://doi.org/10.1145/3519935.3520028
https://doi.org/10.1145/3519935.3520028
Publikováno v:
Theory of Computing. 16:1-30
We continue the study of covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Hastad and Sudan [SIAM J. Computing, 31(6):1663--1686, 2002] and Dinur and Kol [In Proc. $28$th IEEE Conference on Computational Complexit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9103d2cfb2ac3058a0fb3f78a2ac10ed
https://doi.org/10.4086/toc.2020.v016a016
https://doi.org/10.4086/toc.2020.v016a016
Publikováno v:
Theory of Cryptography ISBN: 9783031223174
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4923113c563eb72160d797a8a2b2a81e
https://doi.org/10.1007/978-3-031-22318-1_16
https://doi.org/10.1007/978-3-031-22318-1_16
Publikováno v:
Advances in Cryptology – ASIACRYPT 2022 ISBN: 9783031229626
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3d3306540e6bf2a9bbb5ac686a70482a
https://doi.org/10.1007/978-3-031-22963-3_17
https://doi.org/10.1007/978-3-031-22963-3_17
Publikováno v:
FOCS
We introduce a variant of PCPs, that we refer to as rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the row of each query and the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::aecc756cacd679b2a4d93ff5729bf407
https://doi.org/10.1109/focs46700.2020.00084
https://doi.org/10.1109/focs46700.2020.00084
Autor:
Amey Bhangale, Subhash Khot
Publikováno v:
STOC
A seminal result of H��stad [J. ACM, 48(4):798--859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::89eaf1afe61fe73c5906e50429f38ba1
http://arxiv.org/abs/2009.02815
http://arxiv.org/abs/2009.02815
Publikováno v:
SODA
A rainbow q-coloring of a k-uniform hypergraph is a q-coloring of the vertex set such that every hyperedge contains all q colors. We prove that given a rainbow [MATH HERE]-colorable k-uniform hypergraph, it is NP-hard to find a normal 2-coloring. Pre
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0ee4ce2eb812f66d07af5a442b95a567
https://doi.org/10.1137/1.9781611975994.90
https://doi.org/10.1137/1.9781611975994.90
Publikováno v:
SIAM Journal on Discrete Mathematics. 31:2626-2646
We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and such that every edge $e$ belongs to either the graph induced by $A
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a6adcf6dbf7add078ca820d5e4a5761d
https://doi.org/10.1137/16m1082421
https://doi.org/10.1137/16m1082421