Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Subhash Khot
@inproceedings{DBLP:conf/focs/BravermanKM23,
author = {Mark Braverman and
Subhash Khot and
Dor Minzer},
title = {Parallel Repetition for the {GHZ} Game: Exponential Decay},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1337--1341},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00080},
doi = {10.1109/FOCS57990.2023.00080},
timestamp = {Tue, 02 Jan 2024 14:56:14 +0100},
biburl = {https://dblp.org/rec/conf/focs/BravermanKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/BravermanKKM23,
author = {Mark Braverman and
Subhash Khot and
Guy Kindler and
Dor Minzer},
editor = {Yael Tauman Kalai},
title = {Improved Monotonicity Testers via Hypercube Embeddings},
booktitle = {14th Innovations in Theoretical Computer Science Conference, {ITCS}
2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, {USA}},
series = {LIPIcs},
volume = {251},
pages = {25:1--25:24},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2023.25},
doi = {10.4230/LIPICS.ITCS.2023.25},
timestamp = {Thu, 02 Feb 2023 12:50:42 +0100},
biburl = {https://dblp.org/rec/conf/innovations/BravermanKKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BhangaleKM23,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
editor = {Barna Saha and
Rocco A. Servedio},
title = {On Approximability of Satisfiable k-CSPs: {II}},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {632--642},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585120},
doi = {10.1145/3564246.3585120},
timestamp = {Mon, 22 May 2023 13:01:48 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BhangaleKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BhangaleKM23a,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
editor = {Barna Saha and
Rocco A. Servedio},
title = {On Approximability of Satisfiable k-CSPs: {III}},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {643--655},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585121},
doi = {10.1145/3564246.3585121},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BhangaleKM23a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2307-16248,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
title = {On Approximability of Satisfiable k-CSPs: {IV}},
journal = {CoRR},
volume = {abs/2307.16248},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2307.16248},
doi = {10.48550/ARXIV.2307.16248},
eprinttype = {arXiv},
eprint = {2307.16248},
timestamp = {Wed, 02 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2307-16248.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2308-06600,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
title = {Effective Bounds for Restricted 3-Arithmetic Progressions in F\({}_{\mbox{p}}\)\({}^{\mbox{n}}\)},
journal = {CoRR},
volume = {abs/2308.06600},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2308.06600},
doi = {10.48550/ARXIV.2308.06600},
eprinttype = {arXiv},
eprint = {2308.06600},
timestamp = {Thu, 24 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2308-06600.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2312-04783,
author = {Amey Bhangale and
Mark Braverman and
Subhash Khot and
Yang P. Liu and
Dor Minzer},
title = {Parallel Repetition of k-Player Projection Games},
journal = {CoRR},
volume = {abs/2312.04783},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2312.04783},
doi = {10.48550/ARXIV.2312.04783},
eprinttype = {arXiv},
eprint = {2312.04783},
timestamp = {Wed, 03 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2312-04783.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleBKLM23,
author = {Amey Bhangale and
Mark Braverman and
Subhash Khot and
Yang P. Liu and
Dor Minzer},
title = {Parallel Repetition of k-Player Projection Games},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-198}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/198},
eprinttype = {ECCC},
eprint = {TR23-198},
timestamp = {Wed, 10 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleBKLM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleKM23,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
title = {On Approximability of Satisfiable \emph{k}-CSPs: {III}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-054}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/054},
eprinttype = {ECCC},
eprint = {TR23-054},
timestamp = {Tue, 13 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleKM23a,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
title = {On Approximability of Satisfiable \emph{k}-CSPs: {II}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-055}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/055},
eprinttype = {ECCC},
eprint = {TR23-055},
timestamp = {Tue, 13 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleKM23a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleKM23b,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
title = {On Approximability of Satisfiable k-CSPs: {IV}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-112}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/112},
eprinttype = {ECCC},
eprint = {TR23-112},
timestamp = {Wed, 30 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleKM23b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleKM23c,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
title = {Effective Bounds for Restricted {\textdollar}3{\textdollar}-Arithmetic
Progressions in {\textdollar}{\textbackslash}mathbb\{F\}{\_}p{\^{}}n{\textdollar}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-116}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/116},
eprinttype = {ECCC},
eprint = {TR23-116},
timestamp = {Wed, 30 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleKM23c.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BhangaleK22,
author = {Amey Bhangale and
Subhash Khot},
title = {UG-hardness to NP-hardness by Losing Half},
journal = {Theory Comput.},
volume = {18},
pages = {1--28},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a005/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/BhangaleK22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/SK22,
author = {{Karthik {C. S.}} and
Subhash Khot},
editor = {Shachar Lovett},
title = {Almost Polynomial Factor Inapproximability for Parameterized k-Clique},
booktitle = {37th Computational Complexity Conference, {CCC} 2022, July 20-23,
2022, Philadelphia, PA, {USA}},
series = {LIPIcs},
volume = {234},
pages = {6:1--6:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.CCC.2022.6},
doi = {10.4230/LIPICS.CCC.2022.6},
timestamp = {Wed, 07 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/SK22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BhangaleKM22,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {On approximability of satisfiable \emph{k}-CSPs: {I}},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {976--988},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3520028},
doi = {10.1145/3519935.3520028},
timestamp = {Tue, 27 Dec 2022 09:06:31 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BhangaleKM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-09229,
author = {Mark Braverman and
Subhash Khot and
Guy Kindler and
Dor Minzer},
title = {Improved Monotonicity Testers via Hypercube Embeddings},
journal = {CoRR},
volume = {abs/2211.09229},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.09229},
doi = {10.48550/ARXIV.2211.09229},
eprinttype = {arXiv},
eprint = {2211.09229},
timestamp = {Wed, 23 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-09229.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-13741,
author = {Mark Braverman and
Subhash Khot and
Dor Minzer},
title = {Parallel Repetition for the {GHZ} Game: Exponential Decay},
journal = {CoRR},
volume = {abs/2211.13741},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.13741},
doi = {10.48550/ARXIV.2211.13741},
eprinttype = {arXiv},
eprint = {2211.13741},
timestamp = {Tue, 29 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-13741.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleKM22,
author = {Amey Bhangale and
Subhash Khot and
Dor Minzer},
title = {On Approximability of Satisfiable \emph{k}-CSPs: {I}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-061}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/061},
eprinttype = {ECCC},
eprint = {TR22-061},
timestamp = {Mon, 11 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleKM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BravermanKM22,
author = {Mark Braverman and
Subhash Khot and
Dor Minzer},
title = {Parallel Repetition for the {GHZ} Game: Exponential Decay},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-167}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/167},
eprinttype = {ECCC},
eprint = {TR22-167},
timestamp = {Fri, 10 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/BravermanKM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BravermanKLM21,
author = {Mark Braverman and
Subhash Khot and
Noam Lifshitz and
Dor Minzer},
title = {An Invariance Principle for the Multi-slice, with Applications},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {228--236},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00030},
doi = {10.1109/FOCS52979.2021.00030},
timestamp = {Wed, 09 Mar 2022 12:12:23 +0100},
biburl = {https://dblp.org/rec/conf/focs/BravermanKLM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/KelmanKKMS21,
author = {Esty Kelman and
Subhash Khot and
Guy Kindler and
Dor Minzer and
Muli Safra},
editor = {James R. Lee},
title = {Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and
Log-Sobolev Inequality},
booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS}
2021, January 6-8, 2021, Virtual Conference},
series = {LIPIcs},
volume = {185},
pages = {26:1--26:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.26},
doi = {10.4230/LIPICS.ITCS.2021.26},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/KelmanKKMS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/BravermanKM21,
author = {Mark Braverman and
Subhash Khot and
Dor Minzer},
editor = {James R. Lee},
title = {On Rich 2-to-1 Games},
booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS}
2021, January 6-8, 2021, Virtual Conference},
series = {LIPIcs},
volume = {185},
pages = {27:1--27:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.27},
doi = {10.4230/LIPICS.ITCS.2021.27},
timestamp = {Thu, 04 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/BravermanKM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BhangaleK21,
author = {Amey Bhangale and
Subhash Khot},
editor = {Samir Khuller and
Virginia Vassilevska Williams},
title = {Optimal inapproximability of satisfiable k-LIN over non-abelian groups},
booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Virtual Event, Italy, June 21-25, 2021},
pages = {1615--1628},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3406325.3451003},
doi = {10.1145/3406325.3451003},
timestamp = {Tue, 22 Jun 2021 19:47:11 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BhangaleK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-10725,
author = {Mark Braverman and
Subhash Khot and
Noam Lifshitz and
Dor Minzer},
title = {An Invariance Principle for the Multi-slice, with Applications},
journal = {CoRR},
volume = {abs/2110.10725},
year = {2021},
url = {https://arxiv.org/abs/2110.10725},
eprinttype = {arXiv},
eprint = {2110.10725},
timestamp = {Thu, 28 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-10725.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-03983,
author = {{Karthik {C. S.}} and
Subhash Khot},
title = {Almost Polynomial Factor Inapproximability for Parameterized k-Clique},
journal = {CoRR},
volume = {abs/2112.03983},
year = {2021},
url = {https://arxiv.org/abs/2112.03983},
eprinttype = {arXiv},
eprint = {2112.03983},
timestamp = {Mon, 13 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-03983.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BhangaleK20,
author = {Amey Bhangale and
Subhash Khot},
editor = {Shubhangi Saraf},
title = {Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut},
booktitle = {35th Computational Complexity Conference, {CCC} 2020, July 28-31,
2020, Saarbr{\"{u}}cken, Germany (Virtual Conference)},
series = {LIPIcs},
volume = {169},
pages = {9:1--9:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.CCC.2020.9},
doi = {10.4230/LIPICS.CCC.2020.9},
timestamp = {Thu, 02 Feb 2023 13:27:04 +0100},
biburl = {https://dblp.org/rec/conf/coco/BhangaleK20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2009-02815,
author = {Amey Bhangale and
Subhash Khot},
title = {Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups},
journal = {CoRR},
volume = {abs/2009.02815},
year = {2020},
url = {https://arxiv.org/abs/2009.02815},
eprinttype = {arXiv},
eprint = {2009.02815},
timestamp = {Thu, 17 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2009-02815.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleK20,
author = {Amey Bhangale and
Subhash Khot},
title = {Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR20-130}},
year = {2020},
url = {https://eccc.weizmann.ac.il/report/2020/130},
eprinttype = {ECCC},
eprint = {TR20-130},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleK20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KelmanKKMS20,
author = {Esty Kelman and
Subhash Khot and
Guy Kindler and
Dor Minzer and
Muli Safra},
title = {Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and
Log-Sobolev Inequality},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR20-009}},
year = {2020},
url = {https://eccc.weizmann.ac.il/report/2020/009},
eprinttype = {ECCC},
eprint = {TR20-009},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KelmanKKMS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/HarshaKLT19,
author = {Prahladh Harsha and
Subhash Khot and
Euiwoong Lee and
Devanathan Thiruvenkatachari},
editor = {Dimitris Achlioptas and
L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
title = {Improved 3LIN Hardness via Linear Label Cover},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2019, September 20-22, 2019, Massachusetts
Institute of Technology, Cambridge, MA, {USA}},
series = {LIPIcs},
volume = {145},
pages = {9:1--9:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.9},
doi = {10.4230/LIPICS.APPROX-RANDOM.2019.9},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/HarshaKLT19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BhangaleK19,
author = {Amey Bhangale and
Subhash Khot},
editor = {Amir Shpilka},
title = {UG-Hardness to NP-Hardness by Losing Half},
booktitle = {34th Computational Complexity Conference, {CCC} 2019, July 18-20,
2019, New Brunswick, NJ, {USA}},
series = {LIPIcs},
volume = {137},
pages = {3:1--3:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.CCC.2019.3},
doi = {10.4230/LIPICS.CCC.2019.3},
timestamp = {Thu, 02 Feb 2023 13:27:04 +0100},
biburl = {https://dblp.org/rec/conf/coco/BhangaleK19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KhotN19,
author = {Subhash Khot and
Assaf Naor},
editor = {Timothy M. Chan},
title = {The Andoni-Krauthgamer-Razenshteyn characterization of sketchable
norms fails for sketchable metrics},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {1814--1824},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.109},
doi = {10.1137/1.9781611975482.109},
timestamp = {Thu, 15 Jul 2021 13:49:01 +0200},
biburl = {https://dblp.org/rec/conf/soda/KhotN19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleK19,
author = {Amey Bhangale and
Subhash Khot},
title = {UG-hardness to NP-hardness by Losing Half},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-004}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/004},
eprinttype = {ECCC},
eprint = {TR19-004},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleK19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleK19a,
author = {Amey Bhangale and
Subhash Khot},
title = {Simultaneous Max-Cut is harder to approximate than Max-Cut},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-148}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/148},
eprinttype = {ECCC},
eprint = {TR19-148},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleK19a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BravermanKM19,
author = {Mark Braverman and
Subhash Khot and
Dor Minzer},
title = {On Rich {\textdollar}2{\textdollar}-to-{\textdollar}1{\textdollar}
Games},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-141}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/141},
eprinttype = {ECCC},
eprint = {TR19-141},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BravermanKM19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/HarshaKLT19,
author = {Prahladh Harsha and
Subhash Khot and
Euiwoong Lee and
Devanathan Thiruvenkatachari},
title = {Improved 3LIN Hardness via Linear Label Cover},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-093}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/093},
eprinttype = {ECCC},
eprint = {TR19-093},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/HarshaKLT19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KhotMS18,
author = {Subhash Khot and
Dor Minzer and
Muli Safra},
title = {On Monotonicity Testing and Boolean Isoperimetric-type Theorems},
journal = {{SIAM} J. Comput.},
volume = {47},
number = {6},
pages = {2238--2276},
year = {2018},
url = {https://doi.org/10.1137/16M1065872},
doi = {10.1137/16M1065872},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KhotMS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotMS18,
author = {Subhash Khot and
Dor Minzer and
Muli Safra},
editor = {Mikkel Thorup},
title = {Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion},
booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2018, Paris, France, October 7-9, 2018},
pages = {592--601},
publisher = {{IEEE} Computer Society},
year = {2018},
url = {https://doi.org/10.1109/FOCS.2018.00062},
doi = {10.1109/FOCS.2018.00062},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/KhotMS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BhangaleKKST18,
author = {Amey Bhangale and
Subhash Khot and
Swastik Kopparty and
Sushant Sachdeva and
Devanathan Thiruvenkatachari},
editor = {Artur Czumaj},
title = {Near-optimal approximation algorithm for simultaneous Max-Cut},
booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
pages = {1407--1425},
publisher = {{SIAM}},
year = {2018},
url = {https://doi.org/10.1137/1.9781611975031.93},
doi = {10.1137/1.9781611975031.93},
timestamp = {Tue, 02 Feb 2021 17:07:58 +0100},
biburl = {https://dblp.org/rec/conf/soda/BhangaleKKST18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DinurKKMS18,
author = {Irit Dinur and
Subhash Khot and
Guy Kindler and
Dor Minzer and
Muli Safra},
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {Towards a proof of the 2-to-1 games conjecture?},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages = {376--389},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3188745.3188804},
doi = {10.1145/3188745.3188804},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DinurKKMS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DinurKKMS18a,
author = {Irit Dinur and
Subhash Khot and
Guy Kindler and
Dor Minzer and
Muli Safra},
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {On non-optimally expanding sets in Grassmann graphs},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages = {940--951},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3188745.3188806},
doi = {10.1145/3188745.3188806},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DinurKKMS18a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1801-04497,
author = {Amey Bhangale and
Subhash Khot and
Swastik Kopparty and
Sushant Sachdeva and
Devanathan Thiruvenkatachari},
title = {Near-optimal approximation algorithm for simultaneous Max-Cut},
journal = {CoRR},
volume = {abs/1801.04497},
year = {2018},
url = {http://arxiv.org/abs/1801.04497},
eprinttype = {arXiv},
eprint = {1801.04497},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1801-04497.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1810-04321,
author = {Subhash Khot and
Assaf Naor},
title = {The Andoni-Krauthgamer-Razenshteyn characterization of sketchable
norms fails for sketchable metrics},
journal = {CoRR},
volume = {abs/1810.04321},
year = {2018},
url = {http://arxiv.org/abs/1810.04321},
eprinttype = {arXiv},
eprint = {1810.04321},
timestamp = {Tue, 30 Oct 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1810-04321.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotMMS18,
author = {Subhash Khot and
Dor Minzer and
Dana Moshkovitz and
Muli Safra},
title = {Small Set Expansion in The Johnson Graph},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-078}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/078},
eprinttype = {ECCC},
eprint = {TR18-078},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotMMS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotMS18,
author = {Subhash Khot and
Dor Minzer and
Muli Safra},
title = {Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-006}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/006},
eprinttype = {ECCC},
eprint = {TR18-006},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotMS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KhotS17,
author = {Subhash Khot and
Rishi Saket},
title = {Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2\({}^{\mbox{(log
n)\({}^{\mbox{{\O}mega(1)}}\)}}\) Colors},
journal = {{SIAM} J. Comput.},
volume = {46},
number = {1},
pages = {235--271},
year = {2017},
url = {https://doi.org/10.1137/15100240X},
doi = {10.1137/15100240X},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KhotS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/BhangaleKT17,
author = {Amey Bhangale and
Subhash Khot and
Devanathan Thiruvenkatachari},
editor = {Satya V. Lokam and
R. Ramanujam},
title = {An Improved Dictatorship Test with Perfect Completeness},
booktitle = {37th {IARCS} Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, {FSTTCS} 2017, December 11-15, 2017,
Kanpur, India},
series = {LIPIcs},
volume = {93},
pages = {15:1--15:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2017.15},
doi = {10.4230/LIPICS.FSTTCS.2017.15},
timestamp = {Fri, 03 Sep 2021 15:00:19 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/BhangaleKT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KhotMS17,
author = {Subhash Khot and
Dor Minzer and
Muli Safra},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {On independent sets, 2-to-2 games, and Grassmann graphs},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {576--589},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055432},
doi = {10.1145/3055399.3055432},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KhotMS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BhangaleKT17,
author = {Amey Bhangale and
Subhash Khot and
Devanathan Thiruvenkatachari},
title = {An Improved Dictatorship Test with Perfect Completeness},
journal = {CoRR},
volume = {abs/1702.04748},
year = {2017},
url = {http://arxiv.org/abs/1702.04748},
eprinttype = {arXiv},
eprint = {1702.04748},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BhangaleKT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhangaleKT17,
author = {Amey Bhangale and
Subhash Khot and
Devanathan Thiruvenkatachari},
title = {An Improved Dictatorship Test with Perfect Completeness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-030}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/030},
eprinttype = {ECCC},
eprint = {TR17-030},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhangaleKT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DinurKKMS17,
author = {Irit Dinur and
Subhash Khot and
Guy Kindler and
Dor Minzer and
Muli Safra},
title = {On Non-Optimally Expanding Sets in Grassmann Graphs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-094}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/094},
eprinttype = {ECCC},
eprint = {TR17-094},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DinurKKMS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KhotS16,
author = {Subhash Khot and
Igor Shinkar},
editor = {Klaus Jansen and
Claire Mathieu and
Jos{\'{e}} D. P. Rolim and
Chris Umans},
title = {An {\textasciitilde}O(n) Queries Adaptive Tester for Unateness},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2016, September 7-9, 2016, Paris,
France},
series = {LIPIcs},
volume = {60},
pages = {37:1--37:7},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.37},
doi = {10.4230/LIPICS.APPROX-RANDOM.2016.37},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/KhotS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/KhotS16,
author = {Subhash Khot and
Rishi Saket},
editor = {Piotr Sankowski and
Christos D. Zaroliagis},
title = {Hardness of Bipartite Expansion},
booktitle = {24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24,
2016, Aarhus, Denmark},
series = {LIPIcs},
volume = {57},
pages = {55:1--55:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.ESA.2016.55},
doi = {10.4230/LIPICS.ESA.2016.55},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/esa/KhotS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/Khot16,
author = {Subhash Khot},
editor = {Ioannis Chatzigiannakis and
Michael Mitzenmacher and
Yuval Rabani and
Davide Sangiorgi},
title = {Hardness of Approximation},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming,
{ICALP} 2016, July 11-15, 2016, Rome, Italy},
series = {LIPIcs},
volume = {55},
pages = {3:1--3:1},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2016.3},
doi = {10.4230/LIPICS.ICALP.2016.3},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/icalp/Khot16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/KhotS16,
author = {Subhash Khot and
Igor Shinkar},
editor = {Madhu Sudan},
title = {On Hardness of Approximating the Parameterized Clique Problem},
booktitle = {Proceedings of the 2016 {ACM} Conference on Innovations in Theoretical
Computer Science, Cambridge, MA, USA, January 14-16, 2016},
pages = {37--45},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2840728.2840733},
doi = {10.1145/2840728.2840733},
timestamp = {Tue, 14 Jun 2022 13:12:41 +0200},
biburl = {https://dblp.org/rec/conf/innovations/KhotS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KhotM16,
author = {Subhash Khot and
Dana Moshkovitz},
editor = {Daniel Wichs and
Yishay Mansour},
title = {Candidate hard unique game},
booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
pages = {63--76},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2897518.2897531},
doi = {10.1145/2897518.2897531},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KhotM16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KhotS16,
author = {Subhash Khot and
Igor Shinkar},
title = {An {\textdollar}{\textbackslash}widetilde\{O\}(n){\textdollar} Queries
Adaptive Tester for Unateness},
journal = {CoRR},
volume = {abs/1608.02451},
year = {2016},
url = {http://arxiv.org/abs/1608.02451},
eprinttype = {arXiv},
eprint = {1608.02451},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KhotS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DinurKKMS16,
author = {Irit Dinur and
Subhash Khot and
Guy Kindler and
Dor Minzer and
Muli Safra},
title = {Towards a Proof of the 2-to-1 Games Conjecture?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-198}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/198},
eprinttype = {ECCC},
eprint = {TR16-198},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DinurKKMS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Khot16,
author = {Subhash Khot and
Dor Minzer and
Muli Safra},
title = {On Independent Sets, 2-to-2 Games and Grassmann Graphs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-124}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/124},
eprinttype = {ECCC},
eprint = {TR16-124},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Khot16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotS16,
author = {Subhash Khot and
Rishi Saket},
title = {Approximating CSPs using {LP} Relaxation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-116}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/116},
eprinttype = {ECCC},
eprint = {TR16-116},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotS16a,
author = {Subhash Khot and
Igor Shinkar},
title = {An {\~{O}}(n) Queries Adaptive Tester for Unateness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-126}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/126},
eprinttype = {ECCC},
eprint = {TR16-126},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotS16a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/KhotV15,
author = {Subhash Khot and
Nisheeth K. Vishnoi},
title = {The Unique Games Conjecture, Integrality Gap for Cut Problems and
Embeddability of Negative-Type Metrics into {\(\mathscr{l}\)}\({}_{\mbox{1}}\)},
journal = {J. {ACM}},
volume = {62},
number = {1},
pages = {8:1--8:39},
year = {2015},
url = {https://doi.org/10.1145/2629614},
doi = {10.1145/2629614},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/KhotV15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotMS15,
author = {Subhash Khot and
Dor Minzer and
Muli Safra},
editor = {Venkatesan Guruswami},
title = {On Monotonicity Testing and Boolean Isoperimetric Type Theorems},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {52--58},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.13},
doi = {10.1109/FOCS.2015.13},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/KhotMS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/KhotS15,
author = {Subhash Khot and
Rishi Saket},
editor = {Magn{\'{u}}s M. Halld{\'{o}}rsson and
Kazuo Iwama and
Naoki Kobayashi and
Bettina Speckmann},
title = {Approximating CSPs Using {LP} Relaxation},
booktitle = {Automata, Languages, and Programming - 42nd International Colloquium,
{ICALP} 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {9134},
pages = {822--833},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-662-47672-7\_67},
doi = {10.1007/978-3-662-47672-7\_67},
timestamp = {Fri, 27 Mar 2020 09:02:59 +0100},
biburl = {https://dblp.org/rec/conf/icalp/KhotS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotMS15,
author = {Subhash Khot and
Dor Minzer and
Muli Safra},
title = {On Monotonicity Testing and Boolean Isoperimetric type Theorems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-011}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/011},
eprinttype = {ECCC},
eprint = {TR15-011},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotMS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotS15,
author = {Subhash Khot and
Igor Shinkar},
title = {On Hardness of Approximating the Parameterized Clique Problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-013}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/013},
eprinttype = {ECCC},
eprint = {TR15-013},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KhotPV14,
author = {Subhash Khot and
Preyas Popat and
Nisheeth K. Vishnoi},
title = {Almost Polynomial Factor Hardness for Closest Vector Problem with
Preprocessing},
journal = {{SIAM} J. Comput.},
volume = {43},
number = {3},
pages = {1184--1205},
year = {2014},
url = {https://doi.org/10.1137/130919623},
doi = {10.1137/130919623},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KhotPV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/AustrinK14,
author = {Per Austrin and
Subhash Khot},
title = {A Simple Deterministic Reduction for the Gap Minimum Distance of Code
Problem},
journal = {{IEEE} Trans. Inf. Theory},
volume = {60},
number = {10},
pages = {6636--6645},
year = {2014},
url = {https://doi.org/10.1109/TIT.2014.2340869},
doi = {10.1109/TIT.2014.2340869},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/AustrinK14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotS14,
author = {Subhash Khot and
Rishi Saket},
title = {Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log{\^{}}\{Omega(1)\}
n) Colors},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {206--215},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.30},
doi = {10.1109/FOCS.2014.30},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/KhotTW14,
author = {Subhash Khot and
Madhur Tulsiani and
Pratik Worah},
editor = {Javier Esparza and
Pierre Fraigniaud and
Thore Husfeldt and
Elias Koutsoupias},
title = {The Complexity of Somewhat Approximation Resistant Predicates},
booktitle = {Automata, Languages, and Programming - 41st International Colloquium,
{ICALP} 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {8572},
pages = {689--700},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-662-43948-7\_57},
doi = {10.1007/978-3-662-43948-7\_57},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/KhotTW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KhotS14,
author = {Subhash Khot and
Rishi Saket},
editor = {Chandra Chekuri},
title = {Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable
Hypergraphs},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {1607--1625},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.117},
doi = {10.1137/1.9781611973402.117},
timestamp = {Tue, 02 Feb 2021 17:07:40 +0100},
biburl = {https://dblp.org/rec/conf/soda/KhotS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KhotTW14,
author = {Subhash Khot and
Madhur Tulsiani and
Pratik Worah},
editor = {David B. Shmoys},
title = {A characterization of strong approximation resistance},
booktitle = {Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA,
May 31 - June 03, 2014},
pages = {634--643},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2591796.2591817},
doi = {10.1145/2591796.2591817},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KhotTW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotM14,
author = {Subhash Khot and
Dana Moshkovitz},
title = {Candidate Lasserre Integrality Gap For Unique Games},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-142}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/142},
eprinttype = {ECCC},
eprint = {TR14-142},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotM14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotS14,
author = {Subhash Khot and
Rishi Saket},
title = {Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2\({}^{\mbox{log
n\({}^{\mbox{{\(\Omega\)}(1)}}\)}}\) Colors},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-051}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/051},
eprinttype = {ECCC},
eprint = {TR14-051},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/KhotN13,
author = {Subhash Khot and
Assaf Naor},
title = {Sharp kernel clustering algorithms and their associated Grothendieck
inequalities},
journal = {Random Struct. Algorithms},
volume = {42},
number = {3},
pages = {269--300},
year = {2013},
url = {https://doi.org/10.1002/rsa.20398},
doi = {10.1002/RSA.20398},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/KhotN13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KhotM13,
author = {Subhash Khot and
Dana Moshkovitz},
title = {\emph{NP}-Hardness of Approximately Solving Linear Equations over
Reals},
journal = {{SIAM} J. Comput.},
volume = {42},
number = {3},
pages = {752--791},
year = {2013},
url = {https://doi.org/10.1137/110846415},
doi = {10.1137/110846415},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KhotM13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KhotS13,
author = {Subhash Khot and
Muli Safra},
title = {A Two-Prover One-Round Game with Strong Soundness},
journal = {Theory Comput.},
volume = {9},
pages = {863--887},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a028},
doi = {10.4086/TOC.2013.V009A028},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KhotS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/Khot13,
author = {Subhash Khot},
editor = {Anil Seth and
Nisheeth K. Vishnoi},
title = {On Approximation Resistance of Predicates (Invited Talk)},
booktitle = {{IARCS} Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, {FSTTCS} 2013, December 12-14, 2013,
Guwahati, India},
series = {LIPIcs},
volume = {24},
pages = {19--19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2013},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2013.19},
doi = {10.4230/LIPICS.FSTTCS.2013.19},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/Khot13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/KhotST13,
author = {Subhash Khot and
Muli Safra and
Madhur Tulsiani},
editor = {Robert D. Kleinberg},
title = {Towards an optimal query efficient PCP?},
booktitle = {Innovations in Theoretical Computer Science, {ITCS} '13, Berkeley,
CA, USA, January 9-12, 2013},
pages = {173--186},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2422436.2422458},
doi = {10.1145/2422436.2422458},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/KhotST13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/AustrinK13,
author = {Per Austrin and
Subhash Khot},
editor = {Robert D. Kleinberg},
title = {A characterization of approximation resistance for even k-partite
CSPs},
booktitle = {Innovations in Theoretical Computer Science, {ITCS} '13, Berkeley,
CA, USA, January 9-12, 2013},
pages = {187--196},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2422436.2422459},
doi = {10.1145/2422436.2422459},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/AustrinK13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1301-2731,
author = {Per Austrin and
Subhash Khot},
title = {A Characterization of Approximation Resistance for Even {\textdollar}k{\textdollar}-Partite
CSPs},
journal = {CoRR},
volume = {abs/1301.2731},
year = {2013},
url = {http://arxiv.org/abs/1301.2731},
eprinttype = {arXiv},
eprint = {1301.2731},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1301-2731.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1305-4581,
author = {Subhash Khot and
Nisheeth K. Vishnoi},
title = {The Unique Games Conjecture, Integrality Gap for Cut Problems and
Embeddability of Negative Type Metrics into {\(\mathscr{l}\)}\({}_{\mbox{1}}\)},
journal = {CoRR},
volume = {abs/1305.4581},
year = {2013},
url = {http://arxiv.org/abs/1305.4581},
eprinttype = {arXiv},
eprint = {1305.4581},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1305-4581.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1305-5500,
author = {Subhash Khot and
Madhur Tulsiani and
Pratik Worah},
title = {A Characterization of Strong Approximation Resistance},
journal = {CoRR},
volume = {abs/1305.5500},
year = {2013},
url = {http://arxiv.org/abs/1305.5500},
eprinttype = {arXiv},
eprint = {1305.5500},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1305-5500.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KhotS13,
author = {Subhash Khot and
Rishi Saket},
title = {Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable
Hypergraphs},
journal = {CoRR},
volume = {abs/1308.3247},
year = {2013},
url = {http://arxiv.org/abs/1308.3247},
eprinttype = {arXiv},
eprint = {1308.3247},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KhotS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotTW13,
author = {Subhash Khot and
Madhur Tulsiani and
Pratik Worah},
title = {A Characterization of Strong Approximation Resistance},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-075}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/075},
eprinttype = {ECCC},
eprint = {TR13-075},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotTW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotTW13a,
author = {Subhash Khot and
Madhur Tulsiani and
Pratik Worah},
title = {A Characterization of Approximation Resistance},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-146}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/146},
eprinttype = {ECCC},
eprint = {TR13-146},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotTW13a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotS12,
author = {Subhash Khot and
Rishi Saket},
title = {Hardness of Finding Independent Sets in Almost q-Colorable Graphs},
booktitle = {53rd Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2012, New Brunswick, NJ, USA, October 20-23, 2012},
pages = {380--389},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/FOCS.2012.75},
doi = {10.1109/FOCS.2012.75},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KhotPV12,
author = {Subhash Khot and
Preyas Popat and
Nisheeth K. Vishnoi},
editor = {Howard J. Karloff and
Toniann Pitassi},
title = {2\({}^{\mbox{log1-{\(\epsilon\)} \emph{n}}}\) hardness for the closest
vector problem with preprocessing},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
pages = {277--288},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2213977.2214004},
doi = {10.1145/2213977.2214004},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KhotPV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotST12,
author = {Subhash Khot and
Muli Safra and
Madhur Tulsiani},
title = {Towards An Optimal Query Efficient PCP?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-109}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/109},
eprinttype = {ECCC},
eprint = {TR12-109},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotST12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotTW12,
author = {Subhash Khot and
Madhur Tulsiani and
Pratik Worah},
title = {The Complexity of Somewhat Approximation Resistant Predicates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-151}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/151},
eprinttype = {ECCC},
eprint = {TR12-151},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotTW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/AlekhnovichKKV11,
author = {Mikhail Alekhnovich and
Subhash Khot and
Guy Kindler and
Nisheeth K. Vishnoi},
title = {Hardness of Approximating the Closest Vector Problem with Pre-Processing},
journal = {Comput. Complex.},
volume = {20},
number = {4},
pages = {741--753},
year = {2011},
url = {https://doi.org/10.1007/s00037-011-0031-3},
doi = {10.1007/S00037-011-0031-3},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/AlekhnovichKKV11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/KhotS11,
author = {Subhash Khot and
Rishi Saket},
title = {On the hardness of learning intersections of two halfspaces},
journal = {J. Comput. Syst. Sci.},
volume = {77},
number = {1},
pages = {129--141},
year = {2011},
url = {https://doi.org/10.1016/j.jcss.2010.06.010},
doi = {10.1016/J.JCSS.2010.06.010},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/KhotS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jgt/ChakrabartiK11,
author = {Amit Chakrabarti and
Subhash Khot},
title = {Combinatorial theorems about embedding trees on the real line},
journal = {J. Graph Theory},
volume = {67},
number = {2},
pages = {153--168},
year = {2011},
url = {https://doi.org/10.1002/jgt.20608},
doi = {10.1002/JGT.20608},
timestamp = {Fri, 02 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jgt/ChakrabartiK11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/AustrinKS11,
author = {Per Austrin and
Subhash Khot and
Muli Safra},
title = {Inapproximability of Vertex Cover and Independent Set in Bounded Degree
Graphs},
journal = {Theory Comput.},
volume = {7},
number = {1},
pages = {27--43},
year = {2011},
url = {https://doi.org/10.4086/toc.2011.v007a003},
doi = {10.4086/TOC.2011.V007A003},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/AustrinKS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotS11,
author = {Subhash Khot and
Muli Safra},
editor = {Rafail Ostrovsky},
title = {A Two Prover One Round Game with Strong Soundness},
booktitle = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, {FOCS}
2011, Palm Springs, CA, USA, October 22-25, 2011},
pages = {648--657},
publisher = {{IEEE} Computer Society},
year = {2011},
url = {https://doi.org/10.1109/FOCS.2011.62},
doi = {10.1109/FOCS.2011.62},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/KhotS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/AustrinK11,
author = {Per Austrin and
Subhash Khot},
editor = {Luca Aceto and
Monika Henzinger and
Jir{\'{\i}} Sgall},
title = {A Simple Deterministic Reduction for the Gap Minimum Distance of Code
Problem},
booktitle = {Automata, Languages and Programming - 38th International Colloquium,
{ICALP} 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6755},
pages = {474--485},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22006-7\_40},
doi = {10.1007/978-3-642-22006-7\_40},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/AustrinK11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KhotM11,
author = {Subhash Khot and
Dana Moshkovitz},
editor = {Lance Fortnow and
Salil P. Vadhan},
title = {NP-hardness of approximately solving linear equations over reals},
booktitle = {Proceedings of the 43rd {ACM} Symposium on Theory of Computing, {STOC}
2011, San Jose, CA, USA, 6-8 June 2011},
pages = {413--420},
publisher = {{ACM}},
year = {2011},
url = {https://doi.org/10.1145/1993636.1993692},
doi = {10.1145/1993636.1993692},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KhotM11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1108-2464,
author = {Subhash Khot and
Assaf Naor},
title = {Grothendieck-type inequalities in combinatorial optimization},
journal = {CoRR},
volume = {abs/1108.2464},
year = {2011},
url = {http://arxiv.org/abs/1108.2464},
eprinttype = {arXiv},
eprint = {1108.2464},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1108-2464.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1109-2176,
author = {Subhash Khot and
Preyas Popat and
Nisheeth K. Vishnoi},
title = {{\textdollar}2{\^{}}\{{\textbackslash}log{\^{}}\{1-{\textbackslash}eps\}
n\}{\textdollar} Hardness for Closest Vector Problem with Preprocessing},
journal = {CoRR},
volume = {abs/1109.2176},
year = {2011},
url = {http://arxiv.org/abs/1109.2176},
eprinttype = {arXiv},
eprint = {1109.2176},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1109-2176.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotPV11,
author = {Subhash Khot and
Preyas Popat and
Nisheeth K. Vishnoi},
title = {2\({}^{\mbox{log\({}^{\mbox{1-{\(\acute{\epsilon}\)}}}\)n}}\) Hardness
for Closest Vector Problem with Preprocessing},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-119}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/119},
eprinttype = {ECCC},
eprint = {TR11-119},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotPV11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GopalanKS10,
author = {Parikshit Gopalan and
Subhash Khot and
Rishi Saket},
title = {Hardness of Reconstructing Multivariate Polynomials over Finite Fields},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {6},
pages = {2598--2621},
year = {2010},
url = {https://doi.org/10.1137/070705258},
doi = {10.1137/070705258},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GopalanKS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KhotPS10,
author = {Subhash Khot and
Preyas Popat and
Rishi Saket},
editor = {Maria J. Serna and
Ronen Shaltiel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim},
title = {Approximate Lasserre Integrality Gap for Unique Games},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 13th International Workshop, {APPROX} 2010, and 14th
International Workshop, {RANDOM} 2010, Barcelona, Spain, September
1-3, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6302},
pages = {298--311},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-15369-3\_23},
doi = {10.1007/978-3-642-15369-3\_23},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/KhotPS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Khot10,
author = {Subhash Khot},
title = {On the Unique Games Conjecture (Invited Survey)},
booktitle = {Proceedings of the 25th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2010, Cambridge, Massachusetts, USA, June 9-12,
2010},
pages = {99--121},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/CCC.2010.19},
doi = {10.1109/CCC.2010.19},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Khot10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DinurKPS10,
author = {Irit Dinur and
Subhash Khot and
Will Perkins and
Muli Safra},
title = {Hardness of Finding Independent Sets in Almost 3-Colorable Graphs},
booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2010, October 23-26, 2010, Las Vegas, Nevada, {USA}},
pages = {212--221},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/FOCS.2010.84},
doi = {10.1109/FOCS.2010.84},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/DinurKPS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/BansalK10,
author = {Nikhil Bansal and
Subhash Khot},
editor = {Samson Abramsky and
Cyril Gavoille and
Claude Kirchner and
Friedhelm Meyer auf der Heide and
Paul G. Spirakis},
title = {Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling
Problems},
booktitle = {Automata, Languages and Programming, 37th International Colloquium,
{ICALP} 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6198},
pages = {250--261},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14165-2\_22},
doi = {10.1007/978-3-642-14165-2\_22},
timestamp = {Tue, 15 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icalp/BansalK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/GuruswamiKOPTW10,
author = {Venkatesan Guruswami and
Subhash Khot and
Ryan O'Donnell and
Preyas Popat and
Madhur Tulsiani and
Yi Wu},
editor = {Samson Abramsky and
Cyril Gavoille and
Claude Kirchner and
Friedhelm Meyer auf der Heide and
Paul G. Spirakis},
title = {{SDP} Gaps for 2-to-1 and Other Label-Cover Variants},
booktitle = {Automata, Languages and Programming, 37th International Colloquium,
{ICALP} 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6198},
pages = {617--628},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14165-2\_52},
doi = {10.1007/978-3-642-14165-2\_52},
timestamp = {Tue, 23 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/GuruswamiKOPTW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KhotN10,
author = {Subhash Khot and
Assaf Naor},
editor = {Moses Charikar},
title = {Sharp Kernel Clustering Algorithms and Their Associated Grothendieck
Inequalities},
booktitle = {Proceedings of the Twenty-First Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2010, Austin, Texas, USA, January 17-19, 2010},
pages = {664--683},
publisher = {{SIAM}},
year = {2010},
url = {https://doi.org/10.1137/1.9781611973075.55},
doi = {10.1137/1.9781611973075.55},
timestamp = {Tue, 02 Feb 2021 17:07:39 +0100},
biburl = {https://dblp.org/rec/conf/soda/KhotN10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:series/isc/Khot10,
author = {Subhash Khot},
editor = {Phong Q. Nguyen and
Brigitte Vall{\'{e}}e},
title = {Inapproximability Results for Computational Problems on Lattices},
booktitle = {The {LLL} Algorithm - Survey and Applications},
series = {Information Security and Cryptography},
pages = {453--473},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-02295-1\_14},
doi = {10.1007/978-3-642-02295-1\_14},
timestamp = {Tue, 16 May 2017 14:24:21 +0200},
biburl = {https://dblp.org/rec/series/isc/Khot10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1002-3864,
author = {Prahladh Harsha and
Moses Charikar and
Matthew Andrews and
Sanjeev Arora and
Subhash Khot and
Dana Moshkovitz and
Lisa Zhang and
Ashkan Aazami and
Dev Desai and
Igor Gorodezky and
Geetha Jagannathan and
Alexander S. Kulikov and
Darakhshan J. Mir and
Alantha Newman and
Aleksandar Nikolov and
David Pritchard and
Gwen Spencer},
title = {Limits of Approximation Algorithms: PCPs and Unique Games {(DIMACS}
Tutorial Lecture Notes)},
journal = {CoRR},
volume = {abs/1002.3864},
year = {2010},
url = {http://arxiv.org/abs/1002.3864},
eprinttype = {arXiv},
eprint = {1002.3864},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1002-3864.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1010-1481,
author = {Per Austrin and
Subhash Khot},
title = {A Simple Deterministic Reduction for the Gap Minimum Distance of Code
Problem},
journal = {CoRR},
volume = {abs/1010.1481},
year = {2010},
url = {http://arxiv.org/abs/1010.1481},
eprinttype = {arXiv},
eprint = {1010.1481},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1010-1481.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KhotM10,
author = {Subhash Khot and
Dana Moshkovitz},
title = {NP-Hardness of Approximately Solving Linear Equations Over Reals},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-112}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/112},
eprinttype = {ECCC},
eprint = {TR10-112},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KhotM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MoshkovitzK10,
author = {Dana Moshkovitz and
Subhash Khot},
title = {Hardness of Approximately Solving Linear Equations Over Reals},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-053}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/053},
eprinttype = {ECCC},
eprint = {TR10-053},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MoshkovitzK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KarloffKMR09,
author = {Howard J. Karloff and
Subhash Khot and
Aranyak Mehta and
Yuval Rabani},
title = {On Earthmover Distance, Metric Labeling, and 0-Extension},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {2},
pages = {371--387},
year = {2009},
url = {https://doi.org/10.1137/070685671},
doi = {10.1137/070685671},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KarloffKMR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/FeldmanGKP09,
author = {Vitaly Feldman and
Parikshit Gopalan and
Subhash Khot and
Ashok Kumar Ponnuswami},
title = {On Agnostic Learning of Parities, Monomials, and Halfspaces},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {2},
pages = {606--645},
year = {2009},
url = {https://doi.org/10.1137/070684914},
doi = {10.1137/070684914},
timestamp = {Wed, 14 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/FeldmanGKP09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KhotO09,
author = {Subhash Khot and
Ryan O'Donnell},
title = {{SDP} Gaps and UGC-hardness for Max-Cut-Gain},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {83--117},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a004},
doi = {10.4086/TOC.2009.V005A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KhotO09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AustrinKS09,
author = {Per Austrin and
Subhash Khot and
Muli Safra},
title = {Inapproximability of Vertex Cover and Independent Set in Bounded Degree
Graphs},
booktitle = {Proceedings of the 24th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2009, Paris, France, 15-18 July 2009},
pages = {74--80},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/CCC.2009.38},
doi = {10.1109/CCC.2009.38},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/AustrinKS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BansalK09,
author = {Nikhil Bansal and
Subhash Khot},
title = {Optimal Long Code Test with One Free Bit},
booktitle = {50th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2009, October 25-27, 2009, Atlanta, Georgia, {USA}},
pages = {453--462},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/FOCS.2009.23},
doi = {10.1109/FOCS.2009.23},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BansalK09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotS09,
author = {Subhash Khot and
Rishi Saket},
title = {{SDP} Integrality Gaps with Local ell{\_}1-Embeddability},
booktitle = {50th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2009, October 25-27, 2009, Atlanta, Georgia, {USA}},
pages = {565--574},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/FOCS.2009.37},
doi = {10.1109/FOCS.2009.37},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0906-4816,
author = {Subhash Khot and
Assaf Naor},
title = {Sharp kernel clustering algorithms and their associated Grothendieck
inequalities},
journal = {CoRR},
volume = {abs/0906.4816},
year = {2009},
url = {http://arxiv.org/abs/0906.4816},
eprinttype = {arXiv},
eprint = {0906.4816},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0906-4816.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/KhotLMM08,
author = {Subhash Khot and
Richard J. Lipton and
Evangelos Markakis and
Aranyak Mehta},
title = {Inapproximability Results for Combinatorial Auctions with Submodular
Utility Functions},
journal = {Algorithmica},
volume = {52},
number = {1},
pages = {3--18},
year = {2008},
url = {https://doi.org/10.1007/s00453-007-9105-7},
doi = {10.1007/S00453-007-9105-7},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/KhotLMM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/KhotR08,
author = {Subhash Khot and
Oded Regev},
title = {Vertex cover might be hard to approximate to within 2-epsilon},
journal = {J. Comput. Syst. Sci.},
volume = {74},
number = {3},
pages = {335--349},
year = {2008},
url = {https://doi.org/10.1016/j.jcss.2007.06.019},
doi = {10.1016/J.JCSS.2007.06.019},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/KhotR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KhotN08,
author = {Subhash Khot and
Assaf Naor},
title = {Linear Equations Modulo 2 and the L\({}_{\mbox{1}}\) Diameter of Convex
Bodies},
journal = {{SIAM} J. Comput.},
volume = {38},
number = {4},
pages = {1448--1463},
year = {2008},
url = {https://doi.org/10.1137/070691140},
doi = {10.1137/070691140},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KhotN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/KhotP08,
author = {Subhash Khot and
Ashok Kumar Ponnuswami},
editor = {Rocco A. Servedio and
Tong Zhang},
title = {Minimizing Wide Range Regret with Time Selection Functions},
booktitle = {21st Annual Conference on Learning Theory - {COLT} 2008, Helsinki,
Finland, July 9-12, 2008},
pages = {81--86},
publisher = {Omnipress},
year = {2008},
url = {http://colt2008.cs.helsinki.fi/papers/83-Khot.pdf},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/KhotP08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotS08,
author = {Subhash Khot and
Rishi Saket},
title = {Hardness of Minimizing and Learning {DNF} Expressions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {231--240},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.37},
doi = {10.1109/FOCS.2008.37},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotN08,
author = {Subhash Khot and
Assaf Naor},
title = {Approximate Kernel Clustering},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {561--570},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.33},
doi = {10.1109/FOCS.2008.33},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AroraKKSTV08,
author = {Sanjeev Arora and
Subhash Khot and
Alexandra Kolla and
David Steurer and
Madhur Tulsiani and
Nisheeth K. Vishnoi},
editor = {Cynthia Dwork},
title = {Unique games on expanding constraint graphs are easy: extended abstract},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {21--28},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374380},
doi = {10.1145/1374376.1374380},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AroraKKSTV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KhotS08,
author = {Subhash Khot and
Rishi Saket},
editor = {Cynthia Dwork},
title = {On hardness of learning intersection of two halfspaces},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {345--354},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374426},
doi = {10.1145/1374376.1374426},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KhotS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0807-4626,
author = {Subhash Khot and
Assaf Naor},
title = {Approximate kernel clustering},
journal = {CoRR},
volume = {abs/0807.4626},
year = {2008},
url = {http://arxiv.org/abs/0807.4626},
eprinttype = {arXiv},
eprint = {0807.4626},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0807-4626.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/ChakrabartiK07,
author = {Amit Chakrabarti and
Subhash Khot},
title = {Improved lower bounds on the randomized complexity of graph properties},
journal = {Random Struct. Algorithms},
volume = {30},
number = {3},
pages = {427--440},
year = {2007},
url = {https://doi.org/10.1002/rsa.20164},
doi = {10.1002/RSA.20164},
timestamp = {Thu, 08 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/ChakrabartiK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KhotKMO07,
author = {Subhash Khot and
Guy Kindler and
Elchanan Mossel and
Ryan O'Donnell},
title = {Optimal Inapproximability Results for {MAX-CUT} and Other 2-Variable
CSPs?},
journal = {{SIAM} J. Comput.},
volume = {37},
number = {1},
pages = {319--357},
year = {2007},
url = {https://doi.org/10.1137/S0097539705447372},
doi = {10.1137/S0097539705447372},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/KhotKMO07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KhotP07,
author = {Subhash Khot and
Ashok Kumar Ponnuswami},
editor = {Moses Charikar and
Klaus Jansen and
Omer Reingold and
Jos{\'{e}} D. P. Rolim},
title = {Approximation Algorithms for the Max-Min Allocation Problem},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 10th International Workshop, {APPROX} 2007, and 11th
International Workshop, {RANDOM} 2007, Princeton, NJ, USA, August
20-22, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4627},
pages = {204--217},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74208-1\_15},
doi = {10.1007/978-3-540-74208-1\_15},
timestamp = {Sat, 30 Sep 2023 09:34:32 +0200},
biburl = {https://dblp.org/rec/conf/approx/KhotP07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KhotS07,
author = {Subhash Khot and
Rishi Saket},
editor = {Moses Charikar and
Klaus Jansen and
Omer Reingold and
Jos{\'{e}} D. P. Rolim},
title = {Hardness of Embedding Metric Spaces of Equal Size},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 10th International Workshop, {APPROX} 2007, and 11th
International Workshop, {RANDOM} 2007, Princeton, NJ, USA, August
20-22, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4627},
pages = {218--227},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74208-1\_16},
doi = {10.1007/978-3-540-74208-1\_16},
timestamp = {Tue, 23 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/KhotS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotN07,
author = {Subhash Khot and
Assaf Naor},
title = {Linear Equations Modulo 2 and the {L1} Diameter of Convex Bodies},
booktitle = {48th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2007), October 20-23, 2007, Providence, RI, USA, Proceedings},
pages = {318--328},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/FOCS.2007.20},
doi = {10.1109/FOCS.2007.20},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotN07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GopalanKS07,
author = {Parikshit Gopalan and
Subhash Khot and
Rishi Saket},
title = {Hardness of Reconstructing Multivariate Polynomials over Finite Fields},
booktitle = {48th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2007), October 20-23, 2007, Providence, RI, USA, Proceedings},
pages = {349--359},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/FOCS.2007.31},
doi = {10.1109/FOCS.2007.31},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GopalanKS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GopalanKS07,
author = {Parikshit Gopalan and
Subhash Khot and
Rishi Saket},
title = {Hardness of Reconstructing Multivariate Polynomials over Finite Fields},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-073}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-073/index.html},
eprinttype = {ECCC},
eprint = {TR07-073},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GopalanKS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Khot06,
author = {Subhash Khot},
title = {Hardness of approximating the Shortest Vector Problem in high \emph{l\({}_{\mbox{p}}\)}
norms},
journal = {J. Comput. Syst. Sci.},
volume = {72},
number = {2},
pages = {206--219},
year = {2006},
url = {https://doi.org/10.1016/j.jcss.2005.07.002},
doi = {10.1016/J.JCSS.2005.07.002},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Khot06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/Khot06,
author = {Subhash Khot},
title = {Ruling Out {PTAS} for Graph Min-Bisection, Dense k-Subgraph, and Bipartite
Clique},
journal = {{SIAM} J. Comput.},
volume = {36},
number = {4},
pages = {1025--1071},
year = {2006},
url = {https://doi.org/10.1137/S0097539705447037},
doi = {10.1137/S0097539705447037},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/Khot06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/KhotS06,
author = {Subhash Khot and
Rishi Saket},
title = {A 3-Query Non-Adaptive {PCP} with Perfect Completeness},
booktitle = {21st Annual {IEEE} Conference on Computational Complexity {(CCC} 2006),
16-20 July 2006, Prague, Czech Republic},
pages = {159--169},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/CCC.2006.5},
doi = {10.1109/CCC.2006.5},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/KhotS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotO06,
author = {Subhash Khot and
Ryan O'Donnell},
title = {{SDP} gaps and UGC-hardness for {MAXCUTGAIN}},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages = {217--226},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/FOCS.2006.67},
doi = {10.1109/FOCS.2006.67},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotO06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FeldmanGKP06,
author = {Vitaly Feldman and
Parikshit Gopalan and
Subhash Khot and
Ashok Kumar Ponnuswami},
title = {New Results for Learning Noisy Parities and Halfspaces},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages = {563--574},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/FOCS.2006.51},
doi = {10.1109/FOCS.2006.51},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FeldmanGKP06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/KhotP06,
author = {Subhash Khot and
Ashok Kumar Ponnuswami},
editor = {Michele Bugliesi and
Bart Preneel and
Vladimiro Sassone and
Ingo Wegener},
title = {Better Inapproximability Results for MaxClique, Chromatic Number and
Min-3Lin-Deletion},
booktitle = {Automata, Languages and Programming, 33rd International Colloquium,
{ICALP} 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {4051},
pages = {226--237},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11786986\_21},
doi = {10.1007/11786986\_21},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/KhotP06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DevanurKSV06,
author = {Nikhil R. Devanur and
Subhash Khot and
Rishi Saket and
Nisheeth K. Vishnoi},
editor = {Jon M. Kleinberg},
title = {Integrality gaps for sparsest cut and minimum linear arrangement problems},
booktitle = {Proceedings of the 38th Annual {ACM} Symposium on Theory of Computing,
Seattle, WA, USA, May 21-23, 2006},
pages = {537--546},
publisher = {{ACM}},
year = {2006},
url = {https://doi.org/10.1145/1132516.1132594},
doi = {10.1145/1132516.1132594},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DevanurKSV06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KarloffKMR06,
author = {Howard J. Karloff and
Subhash Khot and
Aranyak Mehta and
Yuval Rabani},
editor = {Jon M. Kleinberg},
title = {On earthmover distance, metric labeling, and 0-extension},
booktitle = {Proceedings of the 38th Annual {ACM} Symposium on Theory of Computing,
Seattle, WA, USA, May 21-23, 2006},
pages = {547--556},
publisher = {{ACM}},
year = {2006},
url = {https://doi.org/10.1145/1132516.1132595},
doi = {10.1145/1132516.1132595},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KarloffKMR06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FeldmanGKP06,
author = {Vitaly Feldman and
Parikshit Gopalan and
Subhash Khot and
Ashok Kumar Ponnuswami},
title = {New Results for Learning Noisy Parities and Halfspaces},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-059}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-059/index.html},
eprinttype = {ECCC},
eprint = {TR06-059},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FeldmanGKP06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/Khot05,
author = {Subhash Khot},
title = {Hardness of approximating the shortest vector problem in lattices},
journal = {J. {ACM}},
volume = {52},
number = {5},
pages = {789--808},
year = {2005},
url = {https://doi.org/10.1145/1089023.1089027},
doi = {10.1145/1089023.1089027},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/Khot05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/DinurGKR05,
author = {Irit Dinur and
Venkatesan Guruswami and
Subhash Khot and
Oded Regev},
title = {A New Multilayered {PCP} and the Hardness of Hypergraph Vertex Cover},
journal = {{SIAM} J. Comput.},
volume = {34},
number = {5},
pages = {1129--1146},
year = {2005},
url = {https://doi.org/10.1137/S0097539704443057},
doi = {10.1137/S0097539704443057},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/DinurGKR05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sigact/Khot05,
author = {Subhash Khot},
title = {Guest column: inapproximability results via Long Code based PCPs},
journal = {{SIGACT} News},
volume = {36},
number = {2},
pages = {25--42},
year = {2005},
url = {https://doi.org/10.1145/1067309.1067318},
doi = {10.1145/1067309.1067318},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/Khot05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadK05,
author = {Johan H{\aa}stad and
Subhash Khot},
title = {Query Efficient PCPs with Perfect Completeness},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {119--148},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a007},
doi = {10.4086/TOC.2005.V001A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadK05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/GuruswamiK05,
author = {Venkatesan Guruswami and
Subhash Khot},
title = {Hardness of Max 3SAT with No Mixed Clauses},
booktitle = {20th Annual {IEEE} Conference on Computational Complexity {(CCC} 2005),
11-15 June 2005, San Jose, CA, {USA}},
pages = {154--162},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/CCC.2005.10},
doi = {10.1109/CCC.2005.10},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/GuruswamiK05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Khot05,
author = {Subhash Khot},
title = {On the Unique Games Conjecture},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {3},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.61},
doi = {10.1109/SFCS.2005.61},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Khot05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotV05,
author = {Subhash Khot and
Nisheeth K. Vishnoi},
title = {The Unique Games Conjecture, Integrality Gap for Cut Problems and
Embeddability of Negative Type Metrics into l\({}_{\mbox{1}}\)},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {53--62},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.74},
doi = {10.1109/SFCS.2005.74},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotV05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotN05,
author = {Subhash Khot and
Assaf Naor},
title = {Nonembeddability theorems via Fourier analysis},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {101--112},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.54},
doi = {10.1109/SFCS.2005.54},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotN05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AlekhnovichKKV05,
author = {Mikhail Alekhnovich and
Subhash Khot and
Guy Kindler and
Nisheeth K. Vishnoi},
title = {Hardness of Approximating the Closest Vector Problem with Pre-Processing},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {216--225},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.40},
doi = {10.1109/SFCS.2005.40},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AlekhnovichKKV05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wine/KhotLMM05,
author = {Subhash Khot and
Richard J. Lipton and
Evangelos Markakis and
Aranyak Mehta},
editor = {Xiaotie Deng and
Yinyu Ye},
title = {Inapproximability Results for Combinatorial Auctions with Submodular
Utility Functions},
booktitle = {Internet and Network Economics, First International Workshop, {WINE}
2005, Hong Kong, China, December 15-17, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3828},
pages = {92--101},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11600930\_10},
doi = {10.1007/11600930\_10},
timestamp = {Sun, 18 Dec 2022 19:02:44 +0100},
biburl = {https://dblp.org/rec/conf/wine/KhotLMM05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-064,
author = {Howard J. Karloff and
Subhash Khot and
Aranyak Mehta and
Yuval Rabani},
title = {On earthmover distance, metric labeling, and 0-extension},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-064}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-064/index.html},
eprinttype = {ECCC},
eprint = {TR05-064},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-064.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-101,
author = {Guy Kindler and
Ryan O'Donnell and
Subhash Khot and
Elchanan Mossel},
title = {Optimal Inapproximability Results for {MAX-CUT} and Other 2-Variable
CSPs?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-101}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-101/index.html},
eprinttype = {ECCC},
eprint = {TR05-101},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-101.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/JayramKKR04,
author = {T. S. Jayram and
Subhash Khot and
Ravi Kumar and
Yuval Rabani},
title = {Cell-probe lower bounds for the partial match problem},
journal = {J. Comput. Syst. Sci.},
volume = {69},
number = {3},
pages = {435--447},
year = {2004},
url = {https://doi.org/10.1016/j.jcss.2004.04.006},
doi = {10.1016/J.JCSS.2004.04.006},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/JayramKKR04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Khot04,
author = {Subhash Khot},
title = {Hardness of Approximating the Shortest Vector Problem in Lattices},
booktitle = {45th Symposium on Foundations of Computer Science {(FOCS} 2004), 17-19
October 2004, Rome, Italy, Proceedings},
pages = {126--135},
publisher = {{IEEE} Computer Society},
year = {2004},
url = {https://doi.org/10.1109/FOCS.2004.31},
doi = {10.1109/FOCS.2004.31},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Khot04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Khot04a,
author = {Subhash Khot},
title = {Ruling Out {PTAS} for Graph Min-Bisection, Densest Subgraph and Bipartite
Clique},
booktitle = {45th Symposium on Foundations of Computer Science {(FOCS} 2004), 17-19
October 2004, Rome, Italy, Proceedings},
pages = {136--145},
publisher = {{IEEE} Computer Society},
year = {2004},
url = {https://doi.org/10.1109/FOCS.2004.59},
doi = {10.1109/FOCS.2004.59},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Khot04a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotKMO04,
author = {Subhash Khot and
Guy Kindler and
Elchanan Mossel and
Ryan O'Donnell},
title = {Optimal Inapproximability Results for Max-Cut and Other 2-Variable
CSPs?},
booktitle = {45th Symposium on Foundations of Computer Science {(FOCS} 2004), 17-19
October 2004, Rome, Italy, Proceedings},
pages = {146--154},
publisher = {{IEEE} Computer Society},
year = {2004},
url = {https://doi.org/10.1109/FOCS.2004.49},
doi = {10.1109/FOCS.2004.49},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotKMO04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HolmerinK04,
author = {Jonas Holmerin and
Subhash Khot},
editor = {L{\'{a}}szl{\'{o}} Babai},
title = {A new {PCP} outer verifier with applications to homogeneous linear
equations and max-bisection},
booktitle = {Proceedings of the 36th Annual {ACM} Symposium on Theory of Computing,
Chicago, IL, USA, June 13-16, 2004},
pages = {11--20},
publisher = {{ACM}},
year = {2004},
url = {https://doi.org/10.1145/1007352.1007362},
doi = {10.1145/1007352.1007362},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HolmerinK04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/AroraK03,
author = {Sanjeev Arora and
Subhash Khot},
title = {Fitting algebraic curves to noisy data},
journal = {J. Comput. Syst. Sci.},
volume = {67},
number = {2},
pages = {325--340},
year = {2003},
url = {https://doi.org/10.1016/S0022-0000(03)00012-6},
doi = {10.1016/S0022-0000(03)00012-6},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/AroraK03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ChakrabartiKS03,
author = {Amit Chakrabarti and
Subhash Khot and
Xiaodong Sun},
title = {Near-Optimal Lower Bounds on the Multi-Party Communication Complexity
of Set Disjointness},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {107--117},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/CCC.2003.1214414},
doi = {10.1109/CCC.2003.1214414},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ChakrabartiKS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/HolmerinK03,
author = {Jonas Holmerin and
Subhash Khot},
title = {A Strong Inapproximability Gap for a Generalization of Minimum Bisection},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {371--378},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/CCC.2003.1214436},
doi = {10.1109/CCC.2003.1214436},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/HolmerinK03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/KhotR03,
author = {Subhash Khot and
Oded Regev},
title = {Vertex Cover Might be Hard to Approximate to within 2-{\textbackslash}varepsilon},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {379},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/CCC.2003.1214437},
doi = {10.1109/CCC.2003.1214437},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/KhotR03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Khot03,
author = {Subhash Khot},
title = {Hardness of Approximating the Shortest Vector Problem in High L\({}_{\mbox{p}}\)
Norms},
booktitle = {44th Symposium on Foundations of Computer Science {(FOCS} 2003), 11-14
October 2003, Cambridge, MA, USA, Proceedings},
pages = {290--297},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/SFCS.2003.1238203},
doi = {10.1109/SFCS.2003.1238203},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Khot03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DinurGKR03,
author = {Irit Dinur and
Venkatesan Guruswami and
Subhash Khot and
Oded Regev},
editor = {Lawrence L. Larmore and
Michel X. Goemans},
title = {A new multilayered {PCP} and the hardness of hypergraph vertex cover},
booktitle = {Proceedings of the 35th Annual {ACM} Symposium on Theory of Computing,
June 9-11, 2003, San Diego, CA, {USA}},
pages = {595--601},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/780542.780629},
doi = {10.1145/780542.780629},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DinurGKR03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/JayramKKR03,
author = {T. S. Jayram and
Subhash Khot and
Ravi Kumar and
Yuval Rabani},
editor = {Lawrence L. Larmore and
Michel X. Goemans},
title = {Cell-probe lower bounds for the partial match problem},
booktitle = {Proceedings of the 35th Annual {ACM} Symposium on Theory of Computing,
June 9-11, 2003, San Diego, CA, {USA}},
pages = {667--672},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/780542.780639},
doi = {10.1145/780542.780639},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/JayramKKR03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/cs-CC-0304026,
author = {Irit Dinur and
Venkatesan Guruswami and
Subhash Khot and
Oded Regev},
title = {A New Multilayered {PCP} and the Hardness of Hypergraph Vertex Cover},
journal = {CoRR},
volume = {cs.CC/0304026},
year = {2003},
url = {http://arxiv.org/abs/cs/0304026},
timestamp = {Fri, 10 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-CC-0304026.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/KhotR02,
author = {Subhash Khot and
Venkatesh Raman},
title = {Parameterized complexity of finding subgraphs with hereditary properties},
journal = {Theor. Comput. Sci.},
volume = {289},
number = {2},
pages = {997--1008},
year = {2002},
url = {https://doi.org/10.1016/S0304-3975(01)00414-5},
doi = {10.1016/S0304-3975(01)00414-5},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/KhotR02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Khot02,
author = {Subhash Khot},
title = {On the Power of Unique 2-Prover 1-Round Games},
booktitle = {Proceedings of the 17th Annual {IEEE} Conference on Computational
Complexity, Montr{\'{e}}al, Qu{\'{e}}bec, Canada, May 21-24,
2002},
pages = {25},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/CCC.2002.1004334},
doi = {10.1109/CCC.2002.1004334},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Khot02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Khot02,
author = {Subhash Khot},
title = {Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs},
booktitle = {43rd Symposium on Foundations of Computer Science {(FOCS} 2002), 16-19
November 2002, Vancouver, BC, Canada, Proceedings},
pages = {23--32},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/SFCS.2002.1181879},
doi = {10.1109/SFCS.2002.1181879},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Khot02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AroraK02,
author = {Sanjeev Arora and
Subhash Khot},
editor = {John H. Reif},
title = {Fitting algebraic curves to noisy data},
booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing,
May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada},
pages = {162--169},
publisher = {{ACM}},
year = {2002},
url = {https://doi.org/10.1145/509907.509934},
doi = {10.1145/509907.509934},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AroraK02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Khot02,
author = {Subhash Khot},
editor = {John H. Reif},
title = {Hardness results for approximate hypergraph coloring},
booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing,
May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada},
pages = {351--359},
publisher = {{ACM}},
year = {2002},
url = {https://doi.org/10.1145/509907.509962},
doi = {10.1145/509907.509962},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Khot02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Khot02a,
author = {Subhash Khot},
editor = {John H. Reif},
title = {On the power of unique 2-prover 1-round games},
booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing,
May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada},
pages = {767--775},
publisher = {{ACM}},
year = {2002},
url = {https://doi.org/10.1145/509907.510017},
doi = {10.1145/509907.510017},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Khot02a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR02-027,
author = {Irit Dinur and
Venkatesan Guruswami and
Subhash Khot},
title = {Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within
Factor (k-3-epsilon)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR02-027}},
year = {2002},
url = {https://eccc.weizmann.ac.il/eccc-reports/2002/TR02-027/index.html},
eprinttype = {ECCC},
eprint = {TR02-027},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR02-027.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChakrabartiKS01,
author = {Amit Chakrabarti and
Subhash Khot and
Yaoyun Shi},
title = {Evasiveness of Subgraph Containment and Related Properties},
journal = {{SIAM} J. Comput.},
volume = {31},
number = {3},
pages = {866--875},
year = {2001},
url = {https://doi.org/10.1137/S0097539700382005},
doi = {10.1137/S0097539700382005},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/ChakrabartiKS01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Khot01,
author = {Subhash Khot},
title = {Improved Inaproximability Results for MaxClique, Chromatic Number
and Approximate Graph Coloring},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, {FOCS} 2001,
14-17 October 2001, Las Vegas, Nevada, {USA}},
pages = {600--609},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/SFCS.2001.959936},
doi = {10.1109/SFCS.2001.959936},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Khot01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HastadK01,
author = {Johan H{\aa}stad and
Subhash Khot},
title = {Query Efficient PCPs with Perfect Completeness},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, {FOCS} 2001,
14-17 October 2001, Las Vegas, Nevada, {USA}},
pages = {610--619},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/SFCS.2001.959937},
doi = {10.1109/SFCS.2001.959937},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HastadK01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ChakrabartiK01,
author = {Amit Chakrabarti and
Subhash Khot},
editor = {Fernando Orejas and
Paul G. Spirakis and
Jan van Leeuwen},
title = {Improved Lower Bounds on the Randomized Complexity of Graph Properties},
booktitle = {Automata, Languages and Programming, 28th International Colloquium,
{ICALP} 2001, Crete, Greece, July 8-12, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2076},
pages = {285--296},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-48224-5\_24},
doi = {10.1007/3-540-48224-5\_24},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ChakrabartiK01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/ChakrabartiKS01,
author = {Amit Chakrabarti and
Subhash Khot and
Yaoyun Shi},
editor = {Afonso Ferreira and
Horst Reichel},
title = {Evasiveness of Subgraph Containment and Related Properties},
booktitle = {{STACS} 2001, 18th Annual Symposium on Theoretical Aspects of Computer
Science, Dresden, Germany, February 15-17, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2010},
pages = {110--120},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-44693-1\_10},
doi = {10.1007/3-540-44693-1\_10},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/ChakrabartiKS01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/KhotR00,
author = {Subhash Khot and
Venkatesh Raman},
editor = {Ding{-}Zhu Du and
Peter Eades and
Vladimir Estivill{-}Castro and
Xuemin Lin and
Arun Sharma},
title = {Parameterized Complexity of Finding Subgraphs with Hereditary Properties},
booktitle = {Computing and Combinatorics, 6th Annual International Conference,
{COCOON} 2000, Sydney, Australia, July 26-28, 2000, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1858},
pages = {137--147},
publisher = {Springer},
year = {2000},
url = {https://doi.org/10.1007/3-540-44968-X\_14},
doi = {10.1007/3-540-44968-X\_14},
timestamp = {Mon, 16 Mar 2020 17:44:09 +0100},
biburl = {https://dblp.org/rec/conf/cocoon/KhotR00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-25 01:39 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
