Zobrazeno 1 - 10
of 35
pro vyhledávání: '"Madhur Tulsiani"'
Publikováno v:
SIAM Journal on Computing. 52:132-155
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7bd7e8c437f247ed001ec0e8498b0763
https://doi.org/10.1137/18m1233418
https://doi.org/10.1137/18m1233418
Autor:
Goutham Rajendran, Madhur Tulsiani
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e566f2e1f5dc33b8283e87bca2a89d44
https://doi.org/10.1137/1.9781611977554.ch138
https://doi.org/10.1137/1.9781611977554.ch138
Publikováno v:
STOC
The Gilbert–Varshamov bound non-constructively establishes the existence of binary codes of distance 1/2−є/2 and rate Ω(є2). In a breakthrough result, Ta-Shma [STOC 2017] constructed the first explicit family of nearly optimal binary codes wit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3f219ca1fa93aae8df840332548eb732
https://doi.org/10.1145/3406325.3451126
https://doi.org/10.1145/3406325.3451126
The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantees for a wide array of problems. In the average case setting, SoS lower bounds provide strong evidence
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::232a756f47a6cdc91c7cbcfcaea99002
Publikováno v:
FOCS
The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance $1/2-\varepsilon$ and rate $\Omega(\varepsilon^{2})$ (where an upper bound of $O(\varepsilon^{2}\log(1/\varepsilon))$ is known). Ta-Shma [STOC 2017
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::61e2dc58d3d0bd627272112647a63d21
https://doi.org/10.1109/focs46700.2020.00048
https://doi.org/10.1109/focs46700.2020.00048
Autor:
Mrinalkanti Ghosh, Madhur Tulsiani
Publikováno v:
Theory of Computing. 14:1-33
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2d9f990d68e7a359fcb32e7b40ea79bb
https://doi.org/10.4086/toc.2018.v014a010
https://doi.org/10.4086/toc.2018.v014a010
Autor:
Vedat Levi Alev, Shashank Srivastava, Dylan Quintana, Fernando Granha Jeronimo, Madhur Tulsiani
Publikováno v:
SODA
We consider families of codes obtained by "lifting" a base code C through operations such as k-XOR applied to "local views" of codewords of C, according to a suitable k-uniform hypergraph. The k-XOR operation yields the direct sum encoding used in wo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::66c15f1cb5e5a0dd9fbd54e78916db98
https://doi.org/10.1137/1.9781611975994.85
https://doi.org/10.1137/1.9781611975994.85
Autor:
Madhur Tulsiani, Julia Wolf
Publikováno v:
FOCS
Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Gold Reich-Levin algorithm
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::73f6f6f18898fbf80a696b35dd3a46cb
https://doi.org/10.1137/12086827x
https://doi.org/10.1137/12086827x