Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Rishi Saket
@article{DBLP:journals/corr/abs-2403-19401,
author = {Venkatesan Guruswami and
Rishi Saket},
title = {Hardness of Learning Boolean Functions from Label Proportions},
journal = {CoRR},
volume = {abs/2403.19401},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2403.19401},
doi = {10.48550/ARXIV.2403.19401},
eprinttype = {arXiv},
eprint = {2403.19401},
timestamp = {Wed, 10 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2403-19401.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cikm/NandyCSR23,
author = {Jay Nandy and
Jatin Chauhan and
Rishi Saket and
Aravindan Raghuveer},
editor = {Ingo Frommholz and
Frank Hopfgartner and
Mark Lee and
Michael Oakes and
Mounia Lalmas and
Min Zhang and
Rodrygo L. T. Santos},
title = {Non-Uniform Adversarial Perturbations for Discrete Tabular Datasets},
booktitle = {Proceedings of the 32nd {ACM} International Conference on Information
and Knowledge Management, {CIKM} 2023, Birmingham, United Kingdom,
October 21-25, 2023},
pages = {1887--1896},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3583780.3614992},
doi = {10.1145/3583780.3614992},
timestamp = {Fri, 27 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cikm/NandyCSR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/GuruswamiS23,
author = {Venkatesan Guruswami and
Rishi Saket},
editor = {Patricia Bouyer and
Srikanth Srinivasan},
title = {Hardness of Learning Boolean Functions from Label Proportions},
booktitle = {43rd {IARCS} Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, {FSTTCS} 2023, December 18-20, 2023,
{IIIT} Hyderabad, Telangana, India},
series = {LIPIcs},
volume = {284},
pages = {37:1--37:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2023.37},
doi = {10.4230/LIPICS.FSTTCS.2023.37},
timestamp = {Wed, 13 Dec 2023 14:08:06 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/GuruswamiS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/BrahmbhattSR23,
author = {Anand Brahmbhatt and
Rishi Saket and
Aravindan Raghuveer},
editor = {Alice Oh and
Tristan Naumann and
Amir Globerson and
Kate Saenko and
Moritz Hardt and
Sergey Levine},
title = {{PAC} Learning Linear Thresholds from Label Proportions},
booktitle = {Advances in Neural Information Processing Systems 36: Annual Conference
on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans,
LA, USA, December 10 - 16, 2023},
year = {2023},
url = {http://papers.nips.cc/paper\_files/paper/2023/hash/d1d3cdc9e28b0c67b9df90fca4d1c1b3-Abstract-Conference.html},
timestamp = {Fri, 01 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/BrahmbhattSR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-10092,
author = {Anand Brahmbhatt and
Rishi Saket and
Shreyas Havaldar and
Anshul Nasery and
Aravindan Raghuveer},
title = {Label Differential Privacy via Aggregation},
journal = {CoRR},
volume = {abs/2310.10092},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.10092},
doi = {10.48550/ARXIV.2310.10092},
eprinttype = {arXiv},
eprint = {2310.10092},
timestamp = {Wed, 25 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-10092.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-10096,
author = {Anand Brahmbhatt and
Mohith Pokala and
Rishi Saket and
Aravindan Raghuveer},
title = {LLP-Bench: {A} Large Scale Tabular Benchmark for Learning from Label
Proportions},
journal = {CoRR},
volume = {abs/2310.10096},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.10096},
doi = {10.48550/ARXIV.2310.10096},
eprinttype = {arXiv},
eprint = {2310.10096},
timestamp = {Wed, 25 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-10096.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-10098,
author = {Anand Brahmbhatt and
Rishi Saket and
Aravindan Raghuveer},
title = {{PAC} Learning Linear Thresholds from Label Proportions},
journal = {CoRR},
volume = {abs/2310.10098},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.10098},
doi = {10.48550/ARXIV.2310.10098},
eprinttype = {arXiv},
eprint = {2310.10098},
timestamp = {Wed, 25 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-10098.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aistats/SaketRR22,
author = {Rishi Saket and
Aravindan Raghuveer and
Balaraman Ravindran},
editor = {Gustau Camps{-}Valls and
Francisco J. R. Ruiz and
Isabel Valera},
title = {On Combining Bags to Better Learn from Label Proportions},
booktitle = {International Conference on Artificial Intelligence and Statistics,
{AISTATS} 2022, 28-30 March 2022, Virtual Event},
series = {Proceedings of Machine Learning Research},
volume = {151},
pages = {5913--5927},
publisher = {{PMLR}},
year = {2022},
url = {https://proceedings.mlr.press/v151/saket22a.html},
timestamp = {Sat, 30 Sep 2023 09:34:08 +0200},
biburl = {https://dblp.org/rec/conf/aistats/SaketRR22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cikm/NandySJCRR22,
author = {Jay Nandy and
Rishi Saket and
Prateek Jain and
Jatin Chauhan and
Balaraman Ravindran and
Aravindan Raghuveer},
editor = {Mohammad Al Hasan and
Li Xiong},
title = {Domain-Agnostic Contrastive Representations for Learning from Label
Proportions},
booktitle = {Proceedings of the 31st {ACM} International Conference on Information
{\&} Knowledge Management, Atlanta, GA, USA, October 17-21, 2022},
pages = {1542--1551},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3511808.3557293},
doi = {10.1145/3511808.3557293},
timestamp = {Wed, 19 Oct 2022 12:52:00 +0200},
biburl = {https://dblp.org/rec/conf/cikm/NandySJCRR22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/kdd/ChauhanRSNR22,
author = {Jatin Chauhan and
Aravindan Raghuveer and
Rishi Saket and
Jay Nandy and
Balaraman Ravindran},
editor = {Aidong Zhang and
Huzefa Rangwala},
title = {Multi-Variate Time Series Forecasting on Variable Subsets},
booktitle = {{KDD} '22: The 28th {ACM} {SIGKDD} Conference on Knowledge Discovery
and Data Mining, Washington, DC, USA, August 14 - 18, 2022},
pages = {76--86},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3534678.3539394},
doi = {10.1145/3534678.3539394},
timestamp = {Mon, 28 Aug 2023 21:17:29 +0200},
biburl = {https://dblp.org/rec/conf/kdd/ChauhanRSNR22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/Saket22,
author = {Rishi Saket},
editor = {Sanmi Koyejo and
S. Mohamed and
A. Agarwal and
Danielle Belgrave and
K. Cho and
A. Oh},
title = {Algorithms and Hardness for Learning Linear Thresholds from Label
Proportions},
booktitle = {Advances in Neural Information Processing Systems 35: Annual Conference
on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans,
LA, USA, November 28 - December 9, 2022},
year = {2022},
url = {http://papers.nips.cc/paper\_files/paper/2022/hash/08a9e28c96d016dd63903ab51cd085b0-Abstract-Conference.html},
timestamp = {Mon, 08 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/Saket22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2206-12626,
author = {Jatin Chauhan and
Aravindan Raghuveer and
Rishi Saket and
Jay Nandy and
Balaraman Ravindran},
title = {Multi-Variate Time Series Forecasting on Variable Subsets},
journal = {CoRR},
volume = {abs/2206.12626},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2206.12626},
doi = {10.48550/ARXIV.2206.12626},
eprinttype = {arXiv},
eprint = {2206.12626},
timestamp = {Mon, 04 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2206-12626.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/Saket21,
author = {Rishi Saket},
editor = {Marc'Aurelio Ranzato and
Alina Beygelzimer and
Yann N. Dauphin and
Percy Liang and
Jennifer Wortman Vaughan},
title = {Learnability of Linear Thresholds from Label Proportions},
booktitle = {Advances in Neural Information Processing Systems 34: Annual Conference
on Neural Information Processing Systems 2021, NeurIPS 2021, December
6-14, 2021, virtual},
pages = {6555--6566},
year = {2021},
url = {https://proceedings.neurips.cc/paper/2021/hash/33b3214d792caf311e1f00fd22b392c5-Abstract.html},
timestamp = {Tue, 03 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/nips/Saket21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GhoshalS21,
author = {Suprovat Ghoshal and
Rishi Saket},
editor = {Samir Khuller and
Virginia Vassilevska Williams},
title = {Hardness of learning DNFs using halfspaces},
booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Virtual Event, Italy, June 21-25, 2021},
pages = {467--480},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3406325.3451067},
doi = {10.1145/3406325.3451067},
timestamp = {Tue, 22 Jun 2021 19:47:11 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GhoshalS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icbc2/SaketSDP20,
author = {Rishi Saket and
Nitin Singh and
Pankaj Dayama and
Vinayaka Pandit},
title = {Smart Contract Protocol for Authenticity and Compliance with Anonymity
on Hyperledger Fabric},
booktitle = {{IEEE} International Conference on Blockchain and Cryptocurrency,
{ICBC} 2020, Toronto, ON, Canada, May 2-6, 2020},
pages = {1--9},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.1109/ICBC48266.2020.9169401},
doi = {10.1109/ICBC48266.2020.9169401},
timestamp = {Sat, 12 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icbc2/SaketSDP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-06358,
author = {Suprovat Ghoshal and
Rishi Saket},
title = {Hardness of Learning DNFs using Halfspaces},
journal = {CoRR},
volume = {abs/1911.06358},
year = {2019},
url = {http://arxiv.org/abs/1911.06358},
eprinttype = {arXiv},
eprint = {1911.06358},
timestamp = {Mon, 02 Dec 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-06358.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GhoshalS19,
author = {Suprovat Ghoshal and
Rishi Saket},
title = {Hardness of Learning DNFs using Halfspaces},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-161}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/161},
eprinttype = {ECCC},
eprint = {TR19-161},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GhoshalS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/BhattacharyyaGS18,
author = {Arnab Bhattacharyya and
Suprovat Ghoshal and
Rishi Saket},
editor = {S{\'{e}}bastien Bubeck and
Vianney Perchet and
Philippe Rigollet},
title = {Hardness of Learning Noisy Halfspaces using Polynomial Thresholds},
booktitle = {Conference On Learning Theory, {COLT} 2018, Stockholm, Sweden, 6-9
July 2018},
series = {Proceedings of Machine Learning Research},
volume = {75},
pages = {876--917},
publisher = {{PMLR}},
year = {2018},
url = {http://proceedings.mlr.press/v75/bhattacharyya18a.html},
timestamp = {Wed, 03 Apr 2019 18:17:23 +0200},
biburl = {https://dblp.org/rec/conf/colt/BhattacharyyaGS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/KenkrePPS17,
author = {Sreyash Kenkre and
Vinayaka Pandit and
Manish Purohit and
Rishi Saket},
title = {On the Approximability of Digraph Ordering},
journal = {Algorithmica},
volume = {78},
number = {4},
pages = {1182--1205},
year = {2017},
url = {https://doi.org/10.1007/s00453-016-0227-7},
doi = {10.1007/S00453-016-0227-7},
timestamp = {Mon, 17 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/KenkrePPS17.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}
}
@article{DBLP:journals/toc/Briet0S17,
author = {Jop Bri{\"{e}}t and
Oded Regev and
Rishi Saket},
title = {Tight Hardness of the Non-Commutative Grothendieck Problem},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--24},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a015},
doi = {10.4086/TOC.2017.V013A015},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Briet0S17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/EneNS17,
author = {Alina Ene and
Viswanath Nagarajan and
Rishi Saket},
editor = {Satya V. Lokam and
R. Ramanujam},
title = {Approximation Algorithms for Stochastic k-TSP},
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 = {27:27--27:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2017.27},
doi = {10.4230/LIPICS.FSTTCS.2017.27},
timestamp = {Fri, 03 Sep 2021 15:00:19 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/EneNS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/GuruswamiS17,
author = {Venkatesan Guruswami and
Rishi Saket},
editor = {Satya V. Lokam and
R. Ramanujam},
title = {Hardness of Rainbow Coloring Hypergraphs},
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 = {33:33--33:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2017.33},
doi = {10.4230/LIPICS.FSTTCS.2017.33},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/GuruswamiS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BhattacharyyaGS17,
author = {Arnab Bhattacharyya and
Suprovat Ghoshal and
Rishi Saket},
title = {Hardness of learning noisy halfspaces using polynomial thresholds},
journal = {CoRR},
volume = {abs/1707.01795},
year = {2017},
url = {http://arxiv.org/abs/1707.01795},
eprinttype = {arXiv},
eprint = {1707.01795},
timestamp = {Thu, 07 Feb 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/BhattacharyyaGS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhattacharyyaGS17,
author = {Arnab Bhattacharyya and
Suprovat Ghoshal and
Rishi Saket},
title = {Hardness of learning noisy halfspaces using polynomial thresholds},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-115}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/115},
eprinttype = {ECCC},
eprint = {TR17-115},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhattacharyyaGS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiS17,
author = {Venkatesan Guruswami and
Rishi Saket},
title = {Hardness of Rainbow Coloring Hypergraphs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-147}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/147},
eprinttype = {ECCC},
eprint = {TR17-147},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/GuruswamiRS016,
author = {Venkatesan Guruswami and
Prasad Raghavendra and
Rishi Saket and
Yi Wu},
title = {Bypassing {UGC} from Some Optimal Geometric Inapproximability Results},
journal = {{ACM} Trans. Algorithms},
volume = {12},
number = {1},
pages = {6:1--6:25},
year = {2016},
url = {https://doi.org/10.1145/2737729},
doi = {10.1145/2737729},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/GuruswamiRS016.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/BhattacharyyaGG16,
author = {Arnab Bhattacharyya and
Ameet Gadekar and
Suprovat Ghoshal and
Rishi Saket},
editor = {Piotr Sankowski and
Christos D. Zaroliagis},
title = {On the Hardness of Learning Sparse Parities},
booktitle = {24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24,
2016, Aarhus, Denmark},
series = {LIPIcs},
volume = {57},
pages = {11:1--11:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.ESA.2016.11},
doi = {10.4230/LIPICS.ESA.2016.11},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/esa/BhattacharyyaGG16.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 = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/esa/KhotS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/EneNS16,
author = {Alina Ene and
Viswanath Nagarajan and
Rishi Saket},
title = {Approximation Algorithms for Stochastic k-TSP},
journal = {CoRR},
volume = {abs/1610.01058},
year = {2016},
url = {http://arxiv.org/abs/1610.01058},
eprinttype = {arXiv},
eprint = {1610.01058},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/EneNS16.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/siamdm/GuruswamiSS15,
author = {Venkatesan Guruswami and
Sushant Sachdeva and
Rishi Saket},
title = {Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs},
journal = {{SIAM} J. Discret. Math.},
volume = {29},
number = {1},
pages = {36--58},
year = {2015},
url = {https://doi.org/10.1137/130919416},
doi = {10.1137/130919416},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/GuruswamiSS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/KenkrePPS15,
author = {Sreyash Kenkre and
Vinayaka Pandit and
Manish Purohit and
Rishi Saket},
editor = {Nikhil Bansal and
Irene Finocchi},
title = {On the Approximability of Digraph Ordering},
booktitle = {Algorithms - {ESA} 2015 - 23rd Annual European Symposium, Patras,
Greece, September 14-16, 2015, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9294},
pages = {792--803},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-662-48350-3\_66},
doi = {10.1007/978-3-662-48350-3\_66},
timestamp = {Tue, 15 Feb 2022 07:54:27 +0100},
biburl = {https://dblp.org/rec/conf/esa/KenkrePPS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BrietRS15,
author = {Jop Bri{\"{e}}t and
Oded Regev and
Rishi Saket},
editor = {Venkatesan Guruswami},
title = {Tight Hardness of the Non-commutative Grothendieck Problem},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {1108--1122},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.72},
doi = {10.1109/FOCS.2015.72},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BrietRS15.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/corr/KenkrePPS15,
author = {Sreyash Kenkre and
Vinayaka Pandit and
Manish Purohit and
Rishi Saket},
title = {On the Approximability of Digraph Ordering},
journal = {CoRR},
volume = {abs/1507.00662},
year = {2015},
url = {http://arxiv.org/abs/1507.00662},
eprinttype = {arXiv},
eprint = {1507.00662},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KenkrePPS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BhattacharyyaGG15,
author = {Arnab Bhattacharyya and
Ameet Gadekar and
Suprovat Ghoshal and
Rishi Saket},
title = {On the hardness of learning sparse parities},
journal = {CoRR},
volume = {abs/1511.08270},
year = {2015},
url = {http://arxiv.org/abs/1511.08270},
eprinttype = {arXiv},
eprint = {1511.08270},
timestamp = {Thu, 07 Feb 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/BhattacharyyaGG15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhattacharyyaGG15,
author = {Arnab Bhattacharyya and
Ameet Gadekar and
Suprovat Ghoshal and
Rishi Saket},
title = {On the hardness of learning sparse parities},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-193}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/193},
eprinttype = {ECCC},
eprint = {TR15-193},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhattacharyyaGG15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Saket14,
author = {Rishi Saket},
title = {Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and
of Satisfiable CSPs},
booktitle = {{IEEE} 29th Conference on Computational Complexity, {CCC} 2014, Vancouver,
BC, Canada, June 11-13, 2014},
pages = {78--89},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/CCC.2014.16},
doi = {10.1109/CCC.2014.16},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Saket14.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/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}
}
@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}
}
@inproceedings{DBLP:conf/approx/GuptaKNSS13,
author = {Anupam Gupta and
Satyen Kale and
Viswanath Nagarajan and
Rishi Saket and
Baruch Schieber},
editor = {Prasad Raghavendra and
Sofya Raskhodnikova and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim},
title = {The Approximability of the Binary Paintshop Problem},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 16th International Workshop, {APPROX} 2013, and 17th
International Workshop, {RANDOM} 2013, Berkeley, CA, USA, August 21-23,
2013. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8096},
pages = {205--217},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-40328-6\_15},
doi = {10.1007/978-3-642-40328-6\_15},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/GuptaKNSS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/SachdevaS13,
author = {Sushant Sachdeva and
Rishi Saket},
title = {Optimal Inapproximability for Scheduling Problems via Structural Hardness
for Hypergraph Vertex Cover},
booktitle = {Proceedings of the 28th Conference on Computational Complexity, {CCC}
2013, K.lo Alto, California, USA, 5-7 June, 2013},
pages = {219--229},
publisher = {{IEEE} Computer Society},
year = {2013},
url = {https://doi.org/10.1109/CCC.2013.30},
doi = {10.1109/CCC.2013.30},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/SachdevaS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Saket13,
author = {Rishi Saket},
title = {A {PTAS} for the Classical Ising Spin Glass Problem on the Chimera
Graph Structure},
journal = {CoRR},
volume = {abs/1306.6943},
year = {2013},
url = {http://arxiv.org/abs/1306.6943},
eprinttype = {arXiv},
eprint = {1306.6943},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Saket13.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/corr/Saket13a,
author = {Rishi Saket},
title = {Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and
of Satisfiable CSPs},
journal = {CoRR},
volume = {abs/1312.2915},
year = {2013},
url = {http://arxiv.org/abs/1312.2915},
eprinttype = {arXiv},
eprint = {1312.2915},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Saket13a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiSS13,
author = {Venkatesan Guruswami and
Sushant Sachdeva and
Rishi Saket},
title = {Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-071}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/071},
eprinttype = {ECCC},
eprint = {TR13-071},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiSS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/SaketS12,
author = {Rishi Saket and
Maxim Sviridenko},
editor = {Anupam Gupta and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Rocco A. Servedio},
title = {New and Improved Bounds for the Minimum Set Cover Problem},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 15th International Workshop, {APPROX} 2012, and 16th
International Workshop, {RANDOM} 2012, Cambridge, MA, USA, August
15-17, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7408},
pages = {288--300},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32512-0\_25},
doi = {10.1007/978-3-642-32512-0\_25},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/SaketS12.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/icalp/GortzNS12,
author = {Inge Li G{\o}rtz and
Viswanath Nagarajan and
Rishi Saket},
editor = {Artur Czumaj and
Kurt Mehlhorn and
Andrew M. Pitts and
Roger Wattenhofer},
title = {Stochastic Vehicle Routing with Recourse},
booktitle = {Automata, Languages, and Programming - 39th International Colloquium,
{ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7391},
pages = {411--423},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31594-7\_35},
doi = {10.1007/978-3-642-31594-7\_35},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/GortzNS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GuruswamiRSW12,
author = {Venkatesan Guruswami and
Prasad Raghavendra and
Rishi Saket and
Yi Wu},
editor = {Yuval Rabani},
title = {Bypassing {UGC} from some optimal geometric inapproximability results},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {699--717},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.58},
doi = {10.1137/1.9781611973099.58},
timestamp = {Tue, 02 Feb 2021 17:07:31 +0100},
biburl = {https://dblp.org/rec/conf/soda/GuruswamiRSW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1202-5797,
author = {Inge Li G{\o}rtz and
Viswanath Nagarajan and
Rishi Saket},
title = {Stochastic Vehicle Routing with Recourse},
journal = {CoRR},
volume = {abs/1202.5797},
year = {2012},
url = {http://arxiv.org/abs/1202.5797},
eprinttype = {arXiv},
eprint = {1202.5797},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1202-5797.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}
}
@inproceedings{DBLP:conf/approx/SachdevaS11,
author = {Sushant Sachdeva and
Rishi Saket},
editor = {Leslie Ann Goldberg and
Klaus Jansen and
R. Ravi and
Jos{\'{e}} D. P. Rolim},
title = {Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite
Hypergraphs},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 14th International Workshop, {APPROX} 2011, and 15th
International Workshop, {RANDOM} 2011, Princeton, NJ, USA, August
17-19, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6845},
pages = {327--338},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22935-0\_28},
doi = {10.1007/978-3-642-22935-0\_28},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/SachdevaS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1105-4175,
author = {Sushant Sachdeva and
Rishi Saket},
title = {Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite
Hypergraphs},
journal = {CoRR},
volume = {abs/1105.4175},
year = {2011},
url = {http://arxiv.org/abs/1105.4175},
eprinttype = {arXiv},
eprint = {1105.4175},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1105-4175.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/fsttcs/Saket10,
author = {Rishi Saket},
editor = {Kamal Lodaya and
Meena Mahajan},
title = {Quasi-Random {PCP} and Hardness of 2-Catalog Segmentation},
booktitle = {{IARCS} Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, {FSTTCS} 2010, December 15-18, 2010,
Chennai, India},
series = {LIPIcs},
volume = {8},
pages = {447--458},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2010},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2010.447},
doi = {10.4230/LIPICS.FSTTCS.2010.447},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/Saket10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/GuruswamiS10,
author = {Venkatesan Guruswami and
Rishi Saket},
editor = {Samson Abramsky and
Cyril Gavoille and
Claude Kirchner and
Friedhelm Meyer auf der Heide and
Paul G. Spirakis},
title = {On the Inapproximability of Vertex Cover on \emph{k}-Partite \emph{k}-Uniform
Hypergraphs},
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 = {360--371},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14165-2\_31},
doi = {10.1007/978-3-642-14165-2\_31},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/GuruswamiS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiRSW10,
author = {Venkatesan Guruswami and
Prasad Raghavendra and
Rishi Saket and
Yi Wu},
title = {Bypassing {UGC} from some optimal geometric inapproximability results},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-177}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/177},
eprinttype = {ECCC},
eprint = {TR10-177},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiRSW10.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}
}
@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/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}
}
@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 = {Sat, 30 Sep 2023 09:34:32 +0200},
biburl = {https://dblp.org/rec/conf/approx/KhotS07.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/jec/SaketN06,
author = {Rishi Saket and
Nicolas Navet},
title = {Frame packing algorithms for automotive applications},
journal = {J. Embed. Comput.},
volume = {2},
number = {1},
pages = {93--102},
year = {2006},
url = {http://content.iospress.com/articles/journal-of-embedded-computing/jec00063},
timestamp = {Fri, 07 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jec/SaketN06.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/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}
}
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-21 18:06 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:
