Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Pravesh Kothari
@inproceedings{DBLP:conf/soda/HsiehKPT24,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Lucas Pesenti and
Luca Trevisan},
editor = {David P. Woodruff},
title = {New {SDP} Roundings and Certifiable Approximation for Cubic Optimization},
booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
pages = {2337--2362},
publisher = {{SIAM}},
year = {2024},
url = {https://doi.org/10.1137/1.9781611977912.83},
doi = {10.1137/1.9781611977912.83},
timestamp = {Thu, 04 Apr 2024 19:38:10 +0200},
biburl = {https://dblp.org/rec/conf/soda/HsiehKPT24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2401-11590,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Sidhanth Mohanty and
David Munh{\'{a}} Correia and
Benny Sudakov},
title = {Small Even Covers, Locally Decodable Codes and Restricted Subgraphs
of Edge-Colored Kikuchi Graphs},
journal = {CoRR},
volume = {abs/2401.11590},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2401.11590},
doi = {10.48550/ARXIV.2401.11590},
eprinttype = {arXiv},
eprint = {2401.11590},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2401-11590.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/KothariVWX23,
author = {Pravesh Kothari and
Santosh S. Vempala and
Alexander S. Wein and
Jeff Xu},
editor = {Gergely Neu and
Lorenzo Rosasco},
title = {Is Planted Coloring Easier than Planted Clique?},
booktitle = {The Thirty Sixth Annual Conference on Learning Theory, {COLT} 2023,
12-15 July 2023, Bangalore, India},
series = {Proceedings of Machine Learning Research},
volume = {195},
pages = {5343--5372},
publisher = {{PMLR}},
year = {2023},
url = {https://proceedings.mlr.press/v195/kothari23a.html},
timestamp = {Wed, 06 Sep 2023 17:49:05 +0200},
biburl = {https://dblp.org/rec/conf/colt/KothariVWX23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuruswamiHKM23,
author = {Venkatesan Guruswami and
Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Peter Manohar},
title = {Efficient Algorithms for Semirandom Planted CSPs at the Refutation
Threshold},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {307--327},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00026},
doi = {10.1109/FOCS57990.2023.00026},
timestamp = {Tue, 02 Jan 2024 14:56:14 +0100},
biburl = {https://dblp.org/rec/conf/focs/GuruswamiHKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JiaKV23,
author = {He Jia and
Pravesh K. Kothari and
Santosh S. Vempala},
title = {Beyond Moments: Robustly Learning Affine Transformations with Asymptotically
Optimal Error},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2408--2429},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00147},
doi = {10.1109/FOCS57990.2023.00147},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JiaKV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/HsiehK23,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari},
editor = {Kousha Etessami and
Uriel Feige and
Gabriele Puppis},
title = {Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of
the {FKL} Algorithm},
booktitle = {50th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2023, July 10-14, 2023, Paderborn, Germany},
series = {LIPIcs},
volume = {261},
pages = {77:1--77:7},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2023.77},
doi = {10.4230/LIPICS.ICALP.2023.77},
timestamp = {Wed, 05 Jul 2023 16:19:52 +0200},
biburl = {https://dblp.org/rec/conf/icalp/HsiehK23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/HsiehKPX23,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Aaron Potechin and
Jeff Xu},
editor = {Kousha Etessami and
Uriel Feige and
Gabriele Puppis},
title = {Ellipsoid Fitting up to a Constant},
booktitle = {50th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2023, July 10-14, 2023, Paderborn, Germany},
series = {LIPIcs},
volume = {261},
pages = {78:1--78:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2023.78},
doi = {10.4230/LIPICS.ICALP.2023.78},
timestamp = {Wed, 05 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/HsiehKPX23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HsiehKM23,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Sidhanth Mohanty},
editor = {Nikhil Bansal and
Viswanath Nagarajan},
title = {A simple and sharper proof of the hypergraph Moore bound},
booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2023, Florence, Italy, January 22-25, 2023},
pages = {2324--2344},
publisher = {{SIAM}},
year = {2023},
url = {https://doi.org/10.1137/1.9781611977554.ch89},
doi = {10.1137/1.9781611977554.CH89},
timestamp = {Fri, 17 Feb 2023 09:28:57 +0100},
biburl = {https://dblp.org/rec/conf/soda/HsiehKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AlabiKTVZ23,
author = {Daniel Alabi and
Pravesh K. Kothari and
Pranay Tankala and
Prayaag Venkat and
Fred Zhang},
editor = {Barna Saha and
Rocco A. Servedio},
title = {Privately Estimating a Gaussian: Efficient, Robust, and Optimal},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {483--496},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585194},
doi = {10.1145/3564246.3585194},
timestamp = {Mon, 22 May 2023 13:01:48 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AlabiKTVZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AlrabiahGKM23,
author = {Omar Alrabiah and
Venkatesan Guruswami and
Pravesh K. Kothari and
Peter Manohar},
editor = {Barna Saha and
Rocco A. Servedio},
title = {A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from
Semirandom {CSP} Refutation},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {1438--1448},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585143},
doi = {10.1145/3564246.3585143},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AlrabiahGKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GollakotaKK23,
author = {Aravind Gollakota and
Adam R. Klivans and
Pravesh K. Kothari},
editor = {Barna Saha and
Rocco A. Servedio},
title = {A Moment-Matching Approach to Testable Learning and a New Characterization
of Rademacher Complexity},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {1657--1670},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585206},
doi = {10.1145/3564246.3585206},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GollakotaKK23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BuhaiKS23,
author = {Rares{-}Darius Buhai and
Pravesh K. Kothari and
David Steurer},
editor = {Barna Saha and
Rocco A. Servedio},
title = {Algorithms Approaching the Threshold for Semi-random Planted Clique},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {1918--1926},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585184},
doi = {10.1145/3564246.3585184},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BuhaiKS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tcc/BogdanovKR23,
author = {Andrej Bogdanov and
Pravesh K. Kothari and
Alon Rosen},
editor = {Guy N. Rothblum and
Hoeteck Wee},
title = {Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree
Method},
booktitle = {Theory of Cryptography - 21st International Conference, {TCC} 2023,
Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {14369},
pages = {268--285},
publisher = {Springer},
year = {2023},
url = {https://doi.org/10.1007/978-3-031-48615-9\_10},
doi = {10.1007/978-3-031-48615-9\_10},
timestamp = {Wed, 06 Dec 2023 13:56:14 +0100},
biburl = {https://dblp.org/rec/conf/tcc/BogdanovKR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2302-12289,
author = {He Jia and
Pravesh Kothari and
Santosh S. Vempala},
title = {Beyond Moments: Robustly Learning Affine Transformations with Asymptotically
Optimal Error},
journal = {CoRR},
volume = {abs/2302.12289},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2302.12289},
doi = {10.48550/ARXIV.2302.12289},
eprinttype = {arXiv},
eprint = {2302.12289},
timestamp = {Tue, 28 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2302-12289.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2303-00252,
author = {Pravesh K. Kothari and
Santosh S. Vempala and
Alexander S. Wein and
Jeff Xu},
title = {Is Planted Coloring Easier than Planted Clique?},
journal = {CoRR},
volume = {abs/2303.00252},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2303.00252},
doi = {10.48550/ARXIV.2303.00252},
eprinttype = {arXiv},
eprint = {2303.00252},
timestamp = {Mon, 06 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2303-00252.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2307-05954,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Aaron Potechin and
Jeff Xu},
title = {Ellipsoid Fitting Up to a Constant},
journal = {CoRR},
volume = {abs/2307.05954},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2307.05954},
doi = {10.48550/ARXIV.2307.05954},
eprinttype = {arXiv},
eprint = {2307.05954},
timestamp = {Thu, 27 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2307-05954.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2308-15403,
author = {Omar Alrabiah and
Venkatesan Guruswami and
Pravesh K. Kothari and
Peter Manohar},
title = {A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from
Semirandom {CSP} Refutation},
journal = {CoRR},
volume = {abs/2308.15403},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2308.15403},
doi = {10.48550/ARXIV.2308.15403},
eprinttype = {arXiv},
eprint = {2308.15403},
timestamp = {Mon, 04 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2308-15403.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2309-16897,
author = {Venkatesan Guruswami and
Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Peter Manohar},
title = {Efficient Algorithms for Semirandom Planted CSPs at the Refutation
Threshold},
journal = {CoRR},
volume = {abs/2309.16897},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2309.16897},
doi = {10.48550/ARXIV.2309.16897},
eprinttype = {arXiv},
eprint = {2309.16897},
timestamp = {Tue, 17 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2309-16897.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-00393,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Lucas Pesenti and
Luca Trevisan},
title = {New {SDP} Roundings and Certifiable Approximation for Cubic Optimization},
journal = {CoRR},
volume = {abs/2310.00393},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.00393},
doi = {10.48550/ARXIV.2310.00393},
eprinttype = {arXiv},
eprint = {2310.00393},
timestamp = {Wed, 18 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-00393.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2311-00558,
author = {Pravesh K. Kothari and
Peter Manohar},
title = {An Exponential Lower Bound for Linear 3-Query Locally Correctable
Codes},
journal = {CoRR},
volume = {abs/2311.00558},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2311.00558},
doi = {10.48550/ARXIV.2311.00558},
eprinttype = {arXiv},
eprint = {2311.00558},
timestamp = {Tue, 07 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2311-00558.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BogdanovKR23,
author = {Andrej Bogdanov and
Pravesh Kothari and
Alon Rosen},
title = {Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree
Method},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-098}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/098},
eprinttype = {ECCC},
eprint = {TR23-098},
timestamp = {Wed, 30 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BogdanovKR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KothariM23,
author = {Pravesh Kothari and
Peter Manohar},
title = {An Exponential Lower Bound for Linear 3-Query Locally Correctable
Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-162}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/162},
eprinttype = {ECCC},
eprint = {TR23-162},
timestamp = {Wed, 10 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/KothariM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iacr/BogdanovKR23,
author = {Andrej Bogdanov and
Pravesh Kothari and
Alon Rosen},
title = {Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree
Method},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {1049},
year = {2023},
url = {https://eprint.iacr.org/2023/1049},
timestamp = {Fri, 04 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iacr/BogdanovKR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KothariMR22,
author = {Pravesh K. Kothari and
Raghu Meka and
Prasad Raghavendra},
title = {Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds
for {LP} Relaxations of CSPs},
journal = {{SIAM} J. Comput.},
volume = {51},
number = {2},
pages = {17--305},
year = {2022},
url = {https://doi.org/10.1137/17m1152966},
doi = {10.1137/17M1152966},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KothariMR22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alt/KothariMZ22,
author = {Pravesh K. Kothari and
Peter Manohar and
Brian Hu Zhang},
editor = {Sanjoy Dasgupta and
Nika Haghtalab},
title = {Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance
of Gaussians Optimally},
booktitle = {International Conference on Algorithmic Learning Theory, 29 March
- 1 April 2022, Paris, France},
series = {Proceedings of Machine Learning Research},
volume = {167},
pages = {638--667},
publisher = {{PMLR}},
year = {2022},
url = {https://proceedings.mlr.press/v167/kothari22a.html},
timestamp = {Fri, 10 Mar 2023 11:41:45 +0100},
biburl = {https://dblp.org/rec/conf/alt/KothariMZ22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/GuruswamiKM22,
author = {Venkatesan Guruswami and
Pravesh K. Kothari and
Peter Manohar},
editor = {Amit Chakrabarti and
Chaitanya Swamy},
title = {Bypassing the {XOR} Trick: Stronger Certificates for Hypergraph Clique
Number},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2022, September 19-21, 2022, University
of Illinois, Urbana-Champaign, {USA} (Virtual Conference)},
series = {LIPIcs},
volume = {245},
pages = {42:1--42:7},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.42},
doi = {10.4230/LIPICS.APPROX/RANDOM.2022.42},
timestamp = {Mon, 26 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/GuruswamiKM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/KothariMV22,
author = {Pravesh Kothari and
Pasin Manurangsi and
Ameya Velingker},
editor = {Po{-}Ling Loh and
Maxim Raginsky},
title = {Private Robust Estimation by Stabilizing Convex Relaxations},
booktitle = {Conference on Learning Theory, 2-5 July 2022, London, {UK}},
series = {Proceedings of Machine Learning Research},
volume = {178},
pages = {723--777},
publisher = {{PMLR}},
year = {2022},
url = {https://proceedings.mlr.press/v178/kothari22a.html},
timestamp = {Tue, 12 Jul 2022 17:36:51 +0200},
biburl = {https://dblp.org/rec/conf/colt/KothariMV22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BafnaHKX22,
author = {Mitali Bafna and
Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Jeff Xu},
title = {Polynomial-Time Power-Sum Decomposition of Polynomials},
booktitle = {63rd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2022, Denver, CO, USA, October 31 - November 3, 2022},
pages = {956--967},
publisher = {{IEEE}},
year = {2022},
url = {https://doi.org/10.1109/FOCS54457.2022.00094},
doi = {10.1109/FOCS54457.2022.00094},
timestamp = {Sat, 31 Dec 2022 17:14:50 +0100},
biburl = {https://dblp.org/rec/conf/focs/BafnaHKX22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/hcomp/DhullJKS22,
author = {Komal Dhull and
Steven Jecmen and
Pravesh Kothari and
Nihar B. Shah},
editor = {Jane Hsu and
Ming Yin},
title = {Strategyproofing Peer Assessment via Partitioning: The Price in Terms
of Evaluators' Expertise},
booktitle = {Proceedings of the Tenth {AAAI} Conference on Human Computation and
Crowdsourcing, {HCOMP} 2022, virtual, November 6-10, 2022},
pages = {53--63},
publisher = {{AAAI} Press},
year = {2022},
url = {https://doi.org/10.1609/hcomp.v10i1.21987},
doi = {10.1609/HCOMP.V10I1.21987},
timestamp = {Tue, 05 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/hcomp/DhullJKS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HsiehK22,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {Algorithmic Thresholds for Refuting Random Polynomial Systems},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {1154--1203},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.49},
doi = {10.1137/1.9781611977073.49},
timestamp = {Tue, 12 Apr 2022 11:24:56 +0200},
biburl = {https://dblp.org/rec/conf/soda/HsiehK22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuruswamiKM22,
author = {Venkatesan Guruswami and
Pravesh K. Kothari and
Peter Manohar},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {Algorithms and certificates for Boolean {CSP} refutation: smoothed
is no harder than random},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {678--689},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3519955},
doi = {10.1145/3519935.3519955},
timestamp = {Tue, 27 Dec 2022 09:06:31 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GuruswamiKM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BakshiDJKKV22,
author = {Ainesh Bakshi and
Ilias Diakonikolas and
He Jia and
Daniel M. Kane and
Pravesh K. Kothari and
Santosh S. Vempala},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {Robustly learning mixtures of \emph{k} arbitrary Gaussians},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {1234--1247},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3519953},
doi = {10.1145/3519935.3519953},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BakshiDJKKV22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/IvkovK22,
author = {Misha Ivkov and
Pravesh K. Kothari},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {List-decodable covariance estimation},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {1276--1283},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3520006},
doi = {10.1145/3519935.3520006},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/IvkovK22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2201-10631,
author = {Komal Dhull and
Steven Jecmen and
Pravesh Kothari and
Nihar B. Shah},
title = {The Price of Strategyproofing Peer Assessment},
journal = {CoRR},
volume = {abs/2201.10631},
year = {2022},
url = {https://arxiv.org/abs/2201.10631},
eprinttype = {arXiv},
eprint = {2201.10631},
timestamp = {Tue, 01 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2201-10631.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2205-06739,
author = {Venkatesan Guruswami and
Pravesh K. Kothari and
Peter Manohar},
title = {Bypassing the {XOR} Trick: Stronger Certificates for Hypergraph Clique
Number},
journal = {CoRR},
volume = {abs/2205.06739},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2205.06739},
doi = {10.48550/ARXIV.2205.06739},
eprinttype = {arXiv},
eprint = {2205.06739},
timestamp = {Tue, 17 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2205-06739.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2206-09204,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari},
title = {Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of
the {FKL} Algorithm},
journal = {CoRR},
volume = {abs/2206.09204},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2206.09204},
doi = {10.48550/ARXIV.2206.09204},
eprinttype = {arXiv},
eprint = {2206.09204},
timestamp = {Mon, 27 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2206-09204.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2206-10942,
author = {Misha Ivkov and
Pravesh K. Kothari},
title = {List-Decodable Covariance Estimation},
journal = {CoRR},
volume = {abs/2206.10942},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2206.10942},
doi = {10.48550/ARXIV.2206.10942},
eprinttype = {arXiv},
eprint = {2206.10942},
timestamp = {Mon, 27 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2206-10942.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2207-10850,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Sidhanth Mohanty},
title = {A simple and sharper proof of the hypergraph Moore bound},
journal = {CoRR},
volume = {abs/2207.10850},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2207.10850},
doi = {10.48550/ARXIV.2207.10850},
eprinttype = {arXiv},
eprint = {2207.10850},
timestamp = {Mon, 25 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2207-10850.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2208-00122,
author = {Mitali Bafna and
Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Jeff Xu},
title = {Polynomial-Time Power-Sum Decomposition of Polynomials},
journal = {CoRR},
volume = {abs/2208.00122},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2208.00122},
doi = {10.48550/ARXIV.2208.00122},
eprinttype = {arXiv},
eprint = {2208.00122},
timestamp = {Tue, 09 Aug 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2208-00122.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-13312,
author = {Aravind Gollakota and
Adam R. Klivans and
Pravesh K. Kothari},
title = {A Moment-Matching Approach to Testable Learning and a New Characterization
of Rademacher Complexity},
journal = {CoRR},
volume = {abs/2211.13312},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.13312},
doi = {10.48550/ARXIV.2211.13312},
eprinttype = {arXiv},
eprint = {2211.13312},
timestamp = {Tue, 29 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-13312.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2212-05619,
author = {Rares{-}Darius Buhai and
Pravesh K. Kothari and
David Steurer},
title = {Algorithms approaching the threshold for semi-random planted clique},
journal = {CoRR},
volume = {abs/2212.05619},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2212.05619},
doi = {10.48550/ARXIV.2212.05619},
eprinttype = {arXiv},
eprint = {2212.05619},
timestamp = {Mon, 02 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2212-05619.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2212-08018,
author = {Daniel Alabi and
Pravesh K. Kothari and
Pranay Tankala and
Prayaag Venkat and
Fred Zhang},
title = {Privately Estimating a Gaussian: Efficient, Robust and Optimal},
journal = {CoRR},
volume = {abs/2212.08018},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2212.08018},
doi = {10.48550/ARXIV.2212.08018},
eprinttype = {arXiv},
eprint = {2212.08018},
timestamp = {Mon, 02 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2212-08018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AlrabiahGKM22,
author = {Omar Alrabiah and
Venkatesan Guruswami and
Pravesh Kothari and
Peter Manohar},
title = {A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from
Semirandom {CSP} Refutation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-101}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/101},
eprinttype = {ECCC},
eprint = {TR22-101},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AlrabiahGKM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/GargKLR21,
author = {Sumegha Garg and
Pravesh K. Kothari and
Pengda Liu and
Ran Raz},
editor = {Mary Wootters and
Laura Sanit{\`{a}}},
title = {Memory-Sample Lower Bounds for Learning Parity with Noise},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2021, August 16-18, 2021, University
of Washington, Seattle, Washington, {USA} (Virtual Conference)},
series = {LIPIcs},
volume = {207},
pages = {60:1--60:19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.60},
doi = {10.4230/LIPICS.APPROX/RANDOM.2021.60},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/GargKLR21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/KothariM21,
author = {Pravesh K. Kothari and
Peter Manohar},
editor = {Valentine Kabanets},
title = {A Stress-Free Sum-Of-Squares Lower Bound for Coloring},
booktitle = {36th Computational Complexity Conference, {CCC} 2021, July 20-23,
2021, Toronto, Ontario, Canada (Virtual Conference)},
series = {LIPIcs},
volume = {200},
pages = {23:1--23:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.CCC.2021.23},
doi = {10.4230/LIPICS.CCC.2021.23},
timestamp = {Thu, 02 Feb 2023 13:27:03 +0100},
biburl = {https://dblp.org/rec/conf/coco/KothariM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AbascalGK21,
author = {Jackson Abascal and
Venkatesan Guruswami and
Pravesh K. Kothari},
editor = {D{\'{a}}niel Marx},
title = {Strongly refuting all semi-random Boolean CSPs},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {454--472},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.28},
doi = {10.1137/1.9781611976465.28},
timestamp = {Thu, 15 Jul 2021 13:48:55 +0200},
biburl = {https://dblp.org/rec/conf/soda/AbascalGK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BakshiK21,
author = {Ainesh Bakshi and
Pravesh K. Kothari},
editor = {D{\'{a}}niel Marx},
title = {List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial
Time},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {1279--1297},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.78},
doi = {10.1137/1.9781611976465.78},
timestamp = {Thu, 15 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/BakshiK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BafnaBKSS21,
author = {Mitali Bafna and
Boaz Barak and
Pravesh K. Kothari and
Tselil Schramm and
David Steurer},
editor = {Samir Khuller and
Virginia Vassilevska Williams},
title = {Playing unique games on certified small-set expanders},
booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Virtual Event, Italy, June 21-25, 2021},
pages = {1629--1642},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3406325.3451099},
doi = {10.1145/3406325.3451099},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BafnaBKSS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2105-07517,
author = {Pravesh K. Kothari and
Peter Manohar},
title = {A Stress-Free Sum-of-Squares Lower Bound for Coloring},
journal = {CoRR},
volume = {abs/2105.07517},
year = {2021},
url = {https://arxiv.org/abs/2105.07517},
eprinttype = {arXiv},
eprint = {2105.07517},
timestamp = {Tue, 18 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2105-07517.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2107-02320,
author = {Sumegha Garg and
Pravesh K. Kothari and
Pengda Liu and
Ran Raz},
title = {Memory-Sample Lower Bounds for Learning Parity with Noise},
journal = {CoRR},
volume = {abs/2107.02320},
year = {2021},
url = {https://arxiv.org/abs/2107.02320},
eprinttype = {arXiv},
eprint = {2107.02320},
timestamp = {Wed, 07 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2107-02320.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2109-04415,
author = {Venkatesan Guruswami and
Pravesh K. Kothari and
Peter Manohar},
title = {Algorithms and Certificates for Boolean {CSP} Refutation: "Smoothed
is no harder than Random"},
journal = {CoRR},
volume = {abs/2109.04415},
year = {2021},
url = {https://arxiv.org/abs/2109.04415},
eprinttype = {arXiv},
eprint = {2109.04415},
timestamp = {Tue, 21 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2109-04415.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-08677,
author = {Jun{-}Ting Hsieh and
Pravesh K. Kothari},
title = {Algorithmic Thresholds for Refuting Random Polynomial Systems},
journal = {CoRR},
volume = {abs/2110.08677},
year = {2021},
url = {https://arxiv.org/abs/2110.08677},
eprinttype = {arXiv},
eprint = {2110.08677},
timestamp = {Fri, 22 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-08677.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-11853,
author = {Pravesh K. Kothari and
Peter Manohar and
Brian Hu Zhang},
title = {Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance
of Gaussians Optimally},
journal = {CoRR},
volume = {abs/2110.11853},
year = {2021},
url = {https://arxiv.org/abs/2110.11853},
eprinttype = {arXiv},
eprint = {2110.11853},
timestamp = {Thu, 28 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-11853.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-03548,
author = {Pravesh K. Kothari and
Pasin Manurangsi and
Ameya Velingker},
title = {Private Robust Estimation by Stabilizing Convex Relaxations},
journal = {CoRR},
volume = {abs/2112.03548},
year = {2021},
url = {https://arxiv.org/abs/2112.03548},
eprinttype = {arXiv},
eprint = {2112.03548},
timestamp = {Tue, 14 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-03548.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/FeldmanKV20,
author = {Vitaly Feldman and
Pravesh Kothari and
Jan Vondr{\'{a}}k},
title = {Tight bounds on \emph{{\(\mathscr{l}\)}}\({}_{\mbox{1}}\) approximation
and learning of self-bounding functions},
journal = {Theor. Comput. Sci.},
volume = {808},
pages = {86--98},
year = {2020},
url = {https://doi.org/10.1016/j.tcs.2019.11.013},
doi = {10.1016/J.TCS.2019.11.013},
timestamp = {Fri, 31 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/FeldmanKV20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alt/KothariL20,
author = {Pravesh K. Kothari and
Roi Livni},
editor = {Aryeh Kontorovich and
Gergely Neu},
title = {On the Expressive Power of Kernel Methods and the Efficiency of Kernel
Learning by Association Schemes},
booktitle = {Algorithmic Learning Theory, {ALT} 2020, 8-11 February 2020, San Diego,
CA, {USA}},
series = {Proceedings of Machine Learning Research},
volume = {117},
pages = {422--450},
publisher = {{PMLR}},
year = {2020},
url = {http://proceedings.mlr.press/v117/pravesh20a.html},
timestamp = {Thu, 18 Jun 2020 11:48:49 +0200},
biburl = {https://dblp.org/rec/conf/alt/KothariL20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/GargKR20,
author = {Sumegha Garg and
Pravesh K. Kothari and
Ran Raz},
editor = {Jaroslaw Byrka and
Raghu Meka},
title = {Time-Space Tradeoffs for Distinguishing Distributions and Applications
to Security of Goldreich's {PRG}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2020, August 17-19, 2020, Virtual
Conference},
series = {LIPIcs},
volume = {176},
pages = {21:1--21:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.21},
doi = {10.4230/LIPICS.APPROX/RANDOM.2020.21},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/GargKR20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BakshiDHKKK20,
author = {Ainesh Bakshi and
Ilias Diakonikolas and
Samuel B. Hopkins and
Daniel Kane and
Sushrut Karmalkar and
Pravesh K. Kothari},
editor = {Sandy Irani},
title = {Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures},
booktitle = {61st {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2020, Durham, NC, USA, November 16-19, 2020},
pages = {149--159},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.1109/FOCS46700.2020.00023},
doi = {10.1109/FOCS46700.2020.00023},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BakshiDHKKK20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/dOrsiKNS20,
author = {Tommaso d'Orsi and
Pravesh K. Kothari and
Gleb Novikov and
David Steurer},
editor = {Sandy Irani},
title = {Sparse {PCA:} Algorithms, Adversarial Perturbations and Certificates},
booktitle = {61st {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2020, Durham, NC, USA, November 16-19, 2020},
pages = {553--564},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.1109/FOCS46700.2020.00058},
doi = {10.1109/FOCS46700.2020.00058},
timestamp = {Mon, 25 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/dOrsiKNS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2002-05139,
author = {Ainesh Bakshi and
Pravesh Kothari},
title = {List-Decodable Subspace Recovery via Sum-of-Squares},
journal = {CoRR},
volume = {abs/2002.05139},
year = {2020},
url = {https://arxiv.org/abs/2002.05139},
eprinttype = {arXiv},
eprint = {2002.05139},
timestamp = {Fri, 14 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2002-05139.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2002-07235,
author = {Sumegha Garg and
Pravesh K. Kothari and
Ran Raz},
title = {Time-Space Tradeoffs for Distinguishing Distributions and Applications
to Security of Goldreich's {PRG}},
journal = {CoRR},
volume = {abs/2002.07235},
year = {2020},
url = {https://arxiv.org/abs/2002.07235},
eprinttype = {arXiv},
eprint = {2002.07235},
timestamp = {Mon, 02 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2002-07235.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2005-02970,
author = {Ainesh Bakshi and
Pravesh Kothari},
title = {Outlier-Robust Clustering of Non-Spherical Mixtures},
journal = {CoRR},
volume = {abs/2005.02970},
year = {2020},
url = {https://arxiv.org/abs/2005.02970},
eprinttype = {arXiv},
eprint = {2005.02970},
timestamp = {Sat, 09 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2005-02970.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2006-09969,
author = {Mitali Bafna and
Boaz Barak and
Pravesh Kothari and
Tselil Schramm and
David Steurer},
title = {Playing Unique Games on Certified Small-Set Expanders},
journal = {CoRR},
volume = {abs/2006.09969},
year = {2020},
url = {https://arxiv.org/abs/2006.09969},
eprinttype = {arXiv},
eprint = {2006.09969},
timestamp = {Tue, 23 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2006-09969.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2009-08032,
author = {Jackson Abascal and
Venkatesan Guruswami and
Pravesh K. Kothari},
title = {Strongly refuting all semi-random Boolean CSPs},
journal = {CoRR},
volume = {abs/2009.08032},
year = {2020},
url = {https://arxiv.org/abs/2009.08032},
eprinttype = {arXiv},
eprint = {2009.08032},
timestamp = {Wed, 23 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2009-08032.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2011-06585,
author = {Tommaso d'Orsi and
Pravesh K. Kothari and
Gleb Novikov and
David Steurer},
title = {Sparse {PCA:} Algorithms, Adversarial Perturbations and Certificates},
journal = {CoRR},
volume = {abs/2011.06585},
year = {2020},
url = {https://arxiv.org/abs/2011.06585},
eprinttype = {arXiv},
eprint = {2011.06585},
timestamp = {Wed, 18 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2011-06585.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2012-02119,
author = {Ainesh Bakshi and
Ilias Diakonikolas and
He Jia and
Daniel M. Kane and
Pravesh K. Kothari and
Santosh S. Vempala},
title = {Robustly Learning Mixtures of k Arbitrary Gaussians},
journal = {CoRR},
volume = {abs/2012.02119},
year = {2020},
url = {https://arxiv.org/abs/2012.02119},
eprinttype = {arXiv},
eprint = {2012.02119},
timestamp = {Fri, 04 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2012-02119.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/fttcs/FlemingKP19,
author = {Noah Fleming and
Pravesh Kothari and
Toniann Pitassi},
title = {Semialgebraic Proofs and Efficient Algorithm Design},
journal = {Found. Trends Theor. Comput. Sci.},
volume = {14},
number = {1-2},
pages = {1--221},
year = {2019},
url = {https://doi.org/10.1561/0400000086},
doi = {10.1561/0400000086},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/fttcs/FlemingKP19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BarakHKKMP19,
author = {Boaz Barak and
Samuel B. Hopkins and
Jonathan A. Kelner and
Pravesh K. Kothari and
Ankur Moitra and
Aaron Potechin},
title = {A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem},
journal = {{SIAM} J. Comput.},
volume = {48},
number = {2},
pages = {687--735},
year = {2019},
url = {https://doi.org/10.1137/17M1138236},
doi = {10.1137/17M1138236},
timestamp = {Thu, 23 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BarakHKKMP19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/comad/DeyKN19,
author = {Palash Dey and
Pravesh K. Kothari and
Swaprava Nath},
editor = {Raghu Krishnapuram and
Parag Singla},
title = {The Social Network Effect on Surprise in Elections},
booktitle = {Proceedings of the {ACM} India Joint International Conference on Data
Science and Management of Data, {COMAD/CODS} 2019, Kolkata, India,
January 3-5, 2019},
pages = {1--9},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3297001.3297002},
doi = {10.1145/3297001.3297002},
timestamp = {Sun, 12 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/comad/DeyKN19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/eurocrypt/BarakHJKS19,
author = {Boaz Barak and
Samuel B. Hopkins and
Aayush Jain and
Pravesh Kothari and
Amit Sahai},
editor = {Yuval Ishai and
Vincent Rijmen},
title = {Sum-of-Squares Meets Program Obfuscation, Revisited},
booktitle = {Advances in Cryptology - {EUROCRYPT} 2019 - 38th Annual International
Conference on the Theory and Applications of Cryptographic Techniques,
Darmstadt, Germany, May 19-23, 2019, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {11476},
pages = {226--250},
publisher = {Springer},
year = {2019},
url = {https://doi.org/10.1007/978-3-030-17653-2\_8},
doi = {10.1007/978-3-030-17653-2\_8},
timestamp = {Tue, 14 May 2019 13:47:56 +0200},
biburl = {https://dblp.org/rec/conf/eurocrypt/BarakHJKS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Kothari0MSW19,
author = {Pravesh Kothari and
Sahil Singla and
Divyarthi Mohan and
Ariel Schvartzman and
S. Matthew Weinberg},
editor = {David Zuckerman},
title = {Approximation Schemes for a Unit-Demand Buyer with Independent Items
via Symmetries},
booktitle = {60th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2019, Baltimore, Maryland, USA, November 9-12, 2019},
pages = {220--232},
publisher = {{IEEE} Computer Society},
year = {2019},
url = {https://doi.org/10.1109/FOCS.2019.00023},
doi = {10.1109/FOCS.2019.00023},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Kothari0MSW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/BarakKS19,
author = {Boaz Barak and
Pravesh K. Kothari and
David Steurer},
editor = {Avrim Blum},
title = {Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture},
booktitle = {10th Innovations in Theoretical Computer Science Conference, {ITCS}
2019, January 10-12, 2019, San Diego, California, {USA}},
series = {LIPIcs},
volume = {124},
pages = {9:1--9:12},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2019.9},
doi = {10.4230/LIPICS.ITCS.2019.9},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/BarakKS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/KothariOS19,
author = {Pravesh K. Kothari and
Ryan O'Donnell and
Tselil Schramm},
editor = {Avrim Blum},
title = {{SOS} Lower Bounds with Hard Constraints: Think Global, Act Local},
booktitle = {10th Innovations in Theoretical Computer Science Conference, {ITCS}
2019, January 10-12, 2019, San Diego, California, {USA}},
series = {LIPIcs},
volume = {124},
pages = {49:1--49:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2019.49},
doi = {10.4230/LIPICS.ITCS.2019.49},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/KothariOS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/KarmalkarKK19,
author = {Sushrut Karmalkar and
Adam R. Klivans and
Pravesh Kothari},
editor = {Hanna M. Wallach and
Hugo Larochelle and
Alina Beygelzimer and
Florence d'Alch{\'{e}}{-}Buc and
Emily B. Fox and
Roman Garnett},
title = {List-decodable Linear Regression},
booktitle = {Advances in Neural Information Processing Systems 32: Annual Conference
on Neural Information Processing Systems 2019, NeurIPS 2019, December
8-14, 2019, Vancouver, BC, Canada},
pages = {7423--7432},
year = {2019},
url = {https://proceedings.neurips.cc/paper/2019/hash/7f5fc754c7af0a6370c9bf91314e79f4-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/KarmalkarKK19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1902-04782,
author = {Pravesh K. Kothari and
Roi Livni},
title = {On the Expressive Power of Kernel Methods and the Efficiency of Kernel
Learning by Association Schemes},
journal = {CoRR},
volume = {abs/1902.04782},
year = {2019},
url = {http://arxiv.org/abs/1902.04782},
eprinttype = {arXiv},
eprint = {1902.04782},
timestamp = {Tue, 21 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1902-04782.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1905-05231,
author = {Pravesh Kothari and
Divyarthi Mohan and
Ariel Schvartzman and
Sahil Singla and
S. Matthew Weinberg},
title = {Approximation Schemes for a Buyer with Independent Items via Symmetries},
journal = {CoRR},
volume = {abs/1905.05231},
year = {2019},
url = {http://arxiv.org/abs/1905.05231},
eprinttype = {arXiv},
eprint = {1905.05231},
timestamp = {Thu, 04 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1905-05231.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1905-05679,
author = {Sushrut Karmalkar and
Adam R. Klivans and
Pravesh K. Kothari},
title = {List-Decodable Linear Regression},
journal = {CoRR},
volume = {abs/1905.05679},
year = {2019},
url = {http://arxiv.org/abs/1905.05679},
eprinttype = {arXiv},
eprint = {1905.05679},
timestamp = {Tue, 28 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1905-05679.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FlemingKP19,
author = {Noah Fleming and
Pravesh Kothari and
Toniann Pitassi},
title = {Semialgebraic Proofs and Efficient Algorithm Design},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-106}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/106},
eprinttype = {ECCC},
eprint = {TR19-106},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FlemingKP19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/GhaziKKS18,
author = {Badih Ghazi and
Ilan Komargodski and
Pravesh K. Kothari and
Madhu Sudan},
title = {Communication with Contextual Uncertainty},
journal = {Comput. Complex.},
volume = {27},
number = {3},
pages = {463--509},
year = {2018},
url = {https://doi.org/10.1007/s00037-017-0161-3},
doi = {10.1007/S00037-017-0161-3},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/GhaziKKS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/HopkinsKPRS18,
author = {Samuel B. Hopkins and
Pravesh Kothari and
Aaron Henry Potechin and
Prasad Raghavendra and
Tselil Schramm},
title = {On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique},
journal = {{ACM} Trans. Algorithms},
volume = {14},
number = {3},
pages = {28:1--28:31},
year = {2018},
url = {https://doi.org/10.1145/3178538},
doi = {10.1145/3178538},
timestamp = {Wed, 21 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/HopkinsKPRS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/KlivansKM18,
author = {Adam R. Klivans and
Pravesh K. Kothari and
Raghu Meka},
editor = {S{\'{e}}bastien Bubeck and
Vianney Perchet and
Philippe Rigollet},
title = {Efficient Algorithms for Outlier-Robust Regression},
booktitle = {Conference On Learning Theory, {COLT} 2018, Stockholm, Sweden, 6-9
July 2018},
series = {Proceedings of Machine Learning Research},
volume = {75},
pages = {1420--1430},
publisher = {{PMLR}},
year = {2018},
url = {http://proceedings.mlr.press/v75/klivans18a.html},
timestamp = {Wed, 03 Apr 2019 18:17:23 +0200},
biburl = {https://dblp.org/rec/conf/colt/KlivansKM18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/AroraHK18,
author = {Sanjeev Arora and
Wei Hu and
Pravesh K. Kothari},
editor = {S{\'{e}}bastien Bubeck and
Vianney Perchet and
Philippe Rigollet},
title = {An Analysis of the t-SNE Algorithm for Data Visualization},
booktitle = {Conference On Learning Theory, {COLT} 2018, Stockholm, Sweden, 6-9
July 2018},
series = {Proceedings of Machine Learning Research},
volume = {75},
pages = {1455--1462},
publisher = {{PMLR}},
year = {2018},
url = {http://proceedings.mlr.press/v75/arora18a.html},
timestamp = {Wed, 03 Apr 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/AroraHK18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/eurocrypt/BarakBKK18,
author = {Boaz Barak and
Zvika Brakerski and
Ilan Komargodski and
Pravesh K. Kothari},
editor = {Jesper Buus Nielsen and
Vincent Rijmen},
title = {Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets
Program Obfuscation)},
booktitle = {Advances in Cryptology - {EUROCRYPT} 2018 - 37th Annual International
Conference on the Theory and Applications of Cryptographic Techniques,
Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part {II}},
series = {Lecture Notes in Computer Science},
volume = {10821},
pages = {649--679},
publisher = {Springer},
year = {2018},
url = {https://doi.org/10.1007/978-3-319-78375-8\_21},
doi = {10.1007/978-3-319-78375-8\_21},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/eurocrypt/BarakBKK18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/KothariL18,
author = {Pravesh K. Kothari and
Roi Livni},
editor = {Anna R. Karlin},
title = {Improper Learning by Refuting},
booktitle = {9th Innovations in Theoretical Computer Science Conference, {ITCS}
2018, January 11-14, 2018, Cambridge, MA, {USA}},
series = {LIPIcs},
volume = {94},
pages = {55:1--55:10},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2018.55},
doi = {10.4230/LIPICS.ITCS.2018.55},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/KothariL18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KothariSS18,
author = {Pravesh K. Kothari and
Jacob Steinhardt and
David Steurer},
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {Robust moment estimation and improved clustering via sum of squares},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages = {1035--1046},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3188745.3188970},
doi = {10.1145/3188745.3188970},
timestamp = {Wed, 21 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KothariSS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KothariM18,
author = {Pravesh K. Kothari and
Ruta Mehta},
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {Sum-of-squares meets nash: lower bounds for finding any equilibrium},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages = {1241--1248},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3188745.3188892},
doi = {10.1145/3188745.3188892},
timestamp = {Wed, 21 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KothariM18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1801-10110,
author = {Palash Dey and
Pravesh K. Kothari and
Swaprava Nath},
title = {Surprise in Elections},
journal = {CoRR},
volume = {abs/1801.10110},
year = {2018},
url = {http://arxiv.org/abs/1801.10110},
eprinttype = {arXiv},
eprint = {1801.10110},
timestamp = {Sat, 05 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1801-10110.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1803-01768,
author = {Sanjeev Arora and
Wei Hu and
Pravesh K. Kothari},
title = {An Analysis of the t-SNE Algorithm for Data Visualization},
journal = {CoRR},
volume = {abs/1803.01768},
year = {2018},
url = {http://arxiv.org/abs/1803.01768},
eprinttype = {arXiv},
eprint = {1803.01768},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1803-01768.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1803-03241,
author = {Adam R. Klivans and
Pravesh K. Kothari and
Raghu Meka},
title = {Efficient Algorithms for Outlier-Robust Regression},
journal = {CoRR},
volume = {abs/1803.03241},
year = {2018},
url = {http://arxiv.org/abs/1803.03241},
eprinttype = {arXiv},
eprint = {1803.03241},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1803-03241.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1804-08662,
author = {Boaz Barak and
Pravesh K. Kothari and
David Steurer},
title = {Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture},
journal = {CoRR},
volume = {abs/1804.08662},
year = {2018},
url = {http://arxiv.org/abs/1804.08662},
eprinttype = {arXiv},
eprint = {1804.08662},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1804-08662.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1806-09426,
author = {Pravesh K. Kothari and
Ruta Mehta},
title = {Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium},
journal = {CoRR},
volume = {abs/1806.09426},
year = {2018},
url = {http://arxiv.org/abs/1806.09426},
eprinttype = {arXiv},
eprint = {1806.09426},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1806-09426.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1809-01207,
author = {Pravesh Kothari and
Ryan O'Donnell and
Tselil Schramm},
title = {{SOS} lower bounds with hard constraints: think global, act local},
journal = {CoRR},
volume = {abs/1809.01207},
year = {2018},
url = {http://arxiv.org/abs/1809.01207},
eprinttype = {arXiv},
eprint = {1809.01207},
timestamp = {Fri, 05 Oct 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1809-01207.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakKS18,
author = {Boaz Barak and
Pravesh Kothari and
David Steurer},
title = {Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-077}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/077},
eprinttype = {ECCC},
eprint = {TR18-077},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakKS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KothariM18,
author = {Pravesh Kothari and
Ruta Mehta},
title = {Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-126}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/126},
eprinttype = {ECCC},
eprint = {TR18-126},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KothariM18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iacr/BarakHJKS18,
author = {Boaz Barak and
Samuel B. Hopkins and
Aayush Jain and
Pravesh Kothari and
Amit Sahai},
title = {Sum-of-Squares Meets Program Obfuscation, Revisited},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {1237},
year = {2018},
url = {https://eprint.iacr.org/2018/1237},
timestamp = {Mon, 11 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iacr/BarakHJKS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alt/FeldmanKV17,
author = {Vitaly Feldman and
Pravesh Kothari and
Jan Vondr{\'{a}}k},
editor = {Steve Hanneke and
Lev Reyzin},
title = {Tight Bounds on {\(\mathscr{l}\)}\({}_{\mbox{1}}\) Approximation and
Learning of Self-Bounding Functions},
booktitle = {International Conference on Algorithmic Learning Theory, {ALT} 2017,
15-17 October 2017, Kyoto University, Kyoto, Japan},
series = {Proceedings of Machine Learning Research},
volume = {76},
pages = {540--559},
publisher = {{PMLR}},
year = {2017},
url = {http://proceedings.mlr.press/v76/feldman17a.html},
timestamp = {Wed, 03 Apr 2019 18:17:23 +0200},
biburl = {https://dblp.org/rec/conf/alt/FeldmanKV17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HopkinsKPRSS17,
author = {Samuel B. Hopkins and
Pravesh K. Kothari and
Aaron Potechin and
Prasad Raghavendra and
Tselil Schramm and
David Steurer},
editor = {Chris Umans},
title = {The Power of Sum-of-Squares for Detecting Hidden Structures},
booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2017, Berkeley, CA, USA, October 15-17, 2017},
pages = {720--731},
publisher = {{IEEE} Computer Society},
year = {2017},
url = {https://doi.org/10.1109/FOCS.2017.72},
doi = {10.1109/FOCS.2017.72},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HopkinsKPRSS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KothariMOW17,
author = {Pravesh K. Kothari and
Ryuhei Mori and
Ryan O'Donnell and
David Witmer},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Sum of squares lower bounds for refuting any {CSP}},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {132--145},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055485},
doi = {10.1145/3055399.3055485},
timestamp = {Sun, 02 Jun 2019 21:10:31 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KothariMOW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KothariMR17,
author = {Pravesh K. Kothari and
Raghu Meka and
Prasad Raghavendra},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Approximating rectangles by juntas and weakly-exponential lower bounds
for {LP} relaxations of CSPs},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {590--603},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055438},
doi = {10.1145/3055399.3055438},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KothariMR17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BarakKS17,
author = {Boaz Barak and
Pravesh K. Kothari and
David Steurer},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Quantum entanglement, sum of squares, and the log rank conjecture},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {975--988},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055488},
doi = {10.1145/3055399.3055488},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BarakKS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KothariMOW17,
author = {Pravesh K. Kothari and
Ryuhei Mori and
Ryan O'Donnell and
David Witmer},
title = {Sum of squares lower bounds for refuting any {CSP}},
journal = {CoRR},
volume = {abs/1701.04521},
year = {2017},
url = {http://arxiv.org/abs/1701.04521},
eprinttype = {arXiv},
eprint = {1701.04521},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KothariMOW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BarakKS17,
author = {Boaz Barak and
Pravesh Kothari and
David Steurer},
title = {Quantum entanglement, sum of squares, and the log rank conjecture},
journal = {CoRR},
volume = {abs/1701.06321},
year = {2017},
url = {http://arxiv.org/abs/1701.06321},
eprinttype = {arXiv},
eprint = {1701.06321},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BarakKS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1709-03871,
author = {Pravesh K. Kothari and
Roi Livni},
title = {Learning by Refuting},
journal = {CoRR},
volume = {abs/1709.03871},
year = {2017},
url = {http://arxiv.org/abs/1709.03871},
eprinttype = {arXiv},
eprint = {1709.03871},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1709-03871.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1710-05017,
author = {Samuel B. Hopkins and
Pravesh K. Kothari and
Aaron Potechin and
Prasad Raghavendra and
Tselil Schramm and
David Steurer},
title = {The power of sum-of-squares for detecting hidden structures},
journal = {CoRR},
volume = {abs/1710.05017},
year = {2017},
url = {http://arxiv.org/abs/1710.05017},
eprinttype = {arXiv},
eprint = {1710.05017},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1710-05017.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1711-07465,
author = {Pravesh K. Kothari and
Jacob Steinhardt},
title = {Better Agnostic Clustering Via Relaxed Tensor Norms},
journal = {CoRR},
volume = {abs/1711.07465},
year = {2017},
url = {http://arxiv.org/abs/1711.07465},
eprinttype = {arXiv},
eprint = {1711.07465},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1711-07465.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1711-11581,
author = {Pravesh K. Kothari and
David Steurer},
title = {Outlier-robust moment-estimation via sum-of-squares},
journal = {CoRR},
volume = {abs/1711.11581},
year = {2017},
url = {http://arxiv.org/abs/1711.11581},
eprinttype = {arXiv},
eprint = {1711.11581},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1711-11581.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakBKK17,
author = {Boaz Barak and
Zvika Brakerski and
Ilan Komargodski and
Pravesh Kothari},
title = {Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets
Program Obfuscation)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-060}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/060},
eprinttype = {ECCC},
eprint = {TR17-060},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakBKK17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakKS17,
author = {Boaz Barak and
Pravesh Kothari and
David Steurer},
title = {Quantum entanglement, sum of squares, and the log rank conjecture},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-011}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/011},
eprinttype = {ECCC},
eprint = {TR17-011},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakKS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iacr/BarakBKK17,
author = {Boaz Barak and
Zvika Brakerski and
Ilan Komargodski and
Pravesh K. Kothari},
title = {Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets
Program Obfuscation)},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {312},
year = {2017},
url = {http://eprint.iacr.org/2017/312},
timestamp = {Mon, 11 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iacr/BarakBKK17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BarakHKKMP16,
author = {Boaz Barak and
Samuel B. Hopkins and
Jonathan A. Kelner and
Pravesh Kothari and
Ankur Moitra and
Aaron Potechin},
editor = {Irit Dinur},
title = {A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem},
booktitle = {{IEEE} 57th Annual Symposium on Foundations of Computer Science, {FOCS}
2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey,
{USA}},
pages = {428--437},
publisher = {{IEEE} Computer Society},
year = {2016},
url = {https://doi.org/10.1109/FOCS.2016.53},
doi = {10.1109/FOCS.2016.53},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BarakHKKMP16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HopkinsKPRS16,
author = {Samuel B. Hopkins and
Pravesh Kothari and
Aaron Henry Potechin and
Prasad Raghavendra and
Tselil Schramm},
editor = {Robert Krauthgamer},
title = {On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
pages = {1079--1095},
publisher = {{SIAM}},
year = {2016},
url = {https://doi.org/10.1137/1.9781611974331.ch76},
doi = {10.1137/1.9781611974331.CH76},
timestamp = {Tue, 02 Feb 2021 17:07:56 +0100},
biburl = {https://dblp.org/rec/conf/soda/HopkinsKPRS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GhaziKKS16,
author = {Badih Ghazi and
Ilan Komargodski and
Pravesh Kothari and
Madhu Sudan},
editor = {Robert Krauthgamer},
title = {Communication with Contextual Uncertainty},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
pages = {2072--2085},
publisher = {{SIAM}},
year = {2016},
url = {https://doi.org/10.1137/1.9781611974331.ch144},
doi = {10.1137/1.9781611974331.CH144},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/GhaziKKS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BarakHKKMP16,
author = {Boaz Barak and
Samuel B. Hopkins and
Jonathan A. Kelner and
Pravesh Kothari and
Ankur Moitra and
Aaron Potechin},
title = {A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem},
journal = {CoRR},
volume = {abs/1604.03084},
year = {2016},
url = {http://arxiv.org/abs/1604.03084},
eprinttype = {arXiv},
eprint = {1604.03084},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BarakHKKMP16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KothariMR16,
author = {Pravesh Kothari and
Raghu Meka and
Prasad Raghavendra},
title = {Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds
for {LP} Relaxations of CSPs},
journal = {CoRR},
volume = {abs/1610.02704},
year = {2016},
url = {http://arxiv.org/abs/1610.02704},
eprinttype = {arXiv},
eprint = {1610.02704},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KothariMR16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakHKKMP16,
author = {Boaz Barak and
Samuel B. Hopkins and
Jonathan A. Kelner and
Pravesh Kothari and
Ankur Moitra and
Aaron Potechin},
title = {A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-058}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/058},
eprinttype = {ECCC},
eprint = {TR16-058},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakHKKMP16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jmlr/FeldmanK15,
author = {Vitaly Feldman and
Pravesh Kothari},
title = {Agnostic learning of disjunctions on symmetric distributions},
journal = {J. Mach. Learn. Res.},
volume = {16},
pages = {3455--3467},
year = {2015},
url = {https://dl.acm.org/doi/10.5555/2789272.2912108},
doi = {10.5555/2789272.2912108},
timestamp = {Thu, 02 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/FeldmanK15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BarakCK15,
author = {Boaz Barak and
Siu On Chan and
Pravesh K. Kothari},
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {Sum of Squares Lower Bounds from Pairwise Independence},
booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
pages = {97--106},
publisher = {{ACM}},
year = {2015},
url = {https://doi.org/10.1145/2746539.2746625},
doi = {10.1145/2746539.2746625},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BarakCK15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KothariM15,
author = {Pravesh K. Kothari and
Raghu Meka},
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {Almost Optimal Pseudorandom Generators for Spherical Caps: Extended
Abstract},
booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
pages = {247--256},
publisher = {{ACM}},
year = {2015},
url = {https://doi.org/10.1145/2746539.2746611},
doi = {10.1145/2746539.2746611},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KothariM15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BarakCK15,
author = {Boaz Barak and
Siu On Chan and
Pravesh Kothari},
title = {Sum of Squares Lower Bounds from Pairwise Independence},
journal = {CoRR},
volume = {abs/1501.00734},
year = {2015},
url = {http://arxiv.org/abs/1501.00734},
eprinttype = {arXiv},
eprint = {1501.00734},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BarakCK15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KomargodskiKS15,
author = {Ilan Komargodski and
Pravesh Kothari and
Madhu Sudan},
title = {Communication with Contextual Uncertainty},
journal = {CoRR},
volume = {abs/1504.04813},
year = {2015},
url = {http://arxiv.org/abs/1504.04813},
eprinttype = {arXiv},
eprint = {1504.04813},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KomargodskiKS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/HopkinsKP15,
author = {Samuel B. Hopkins and
Pravesh K. Kothari and
Aaron Potechin},
title = {SoS and Planted Clique: Tight Analysis of {MPW} Moments at all Degrees
and an Optimal Lower Bound at Degree Four},
journal = {CoRR},
volume = {abs/1507.05230},
year = {2015},
url = {http://arxiv.org/abs/1507.05230},
eprinttype = {arXiv},
eprint = {1507.05230},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/HopkinsKP15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KomargodskiKS15,
author = {Ilan Komargodski and
Pravesh Kothari and
Madhu Sudan},
title = {Communication with Contextual Uncertainty},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-064}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/064},
eprinttype = {ECCC},
eprint = {TR15-064},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KomargodskiKS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KlivansK14,
author = {Adam R. Klivans and
Pravesh Kothari},
editor = {Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Nikhil R. Devanur and
Cristopher Moore},
title = {Embedding Hard Learning Problems Into Gaussian Space},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2014, September 4-6, 2014, Barcelona,
Spain},
series = {LIPIcs},
volume = {28},
pages = {793--809},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2014},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.793},
doi = {10.4230/LIPICS.APPROX-RANDOM.2014.793},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/KlivansK14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/FeldmanK14,
author = {Vitaly Feldman and
Pravesh Kothari},
editor = {Maria{-}Florina Balcan and
Vitaly Feldman and
Csaba Szepesv{\'{a}}ri},
title = {Learning Coverage Functions and Private Release of Marginals},
booktitle = {Proceedings of The 27th Conference on Learning Theory, {COLT} 2014,
Barcelona, Spain, June 13-15, 2014},
series = {{JMLR} Workshop and Conference Proceedings},
volume = {35},
pages = {679--702},
publisher = {JMLR.org},
year = {2014},
url = {http://proceedings.mlr.press/v35/feldman14a.html},
timestamp = {Wed, 29 May 2019 08:41:46 +0200},
biburl = {https://dblp.org/rec/conf/colt/FeldmanK14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/Chakrabarty0K14,
author = {Deeparnab Chakrabarty and
Prateek Jain and
Pravesh Kothari},
editor = {Zoubin Ghahramani and
Max Welling and
Corinna Cortes and
Neil D. Lawrence and
Kilian Q. Weinberger},
title = {Provable Submodular Minimization using Wolfe's Algorithm},
booktitle = {Advances in Neural Information Processing Systems 27: Annual Conference
on Neural Information Processing Systems 2014, December 8-13 2014,
Montreal, Quebec, Canada},
pages = {802--809},
year = {2014},
url = {https://proceedings.neurips.cc/paper/2014/hash/7bcdf75ad237b8e02e301f4091fb6bc8-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/Chakrabarty0K14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KothariNOW14,
author = {Pravesh Kothari and
Amir Nayyeri and
Ryan O'Donnell and
Chenggang Wu},
editor = {Chandra Chekuri},
title = {Testing Surface Area},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {1204--1214},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.89},
doi = {10.1137/1.9781611973402.89},
timestamp = {Tue, 02 Feb 2021 17:07:40 +0100},
biburl = {https://dblp.org/rec/conf/soda/KothariNOW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/FeldmanKV14,
author = {Vitaly Feldman and
Pravesh Kothari and
Jan Vondr{\'{a}}k},
title = {Nearly Tight Bounds on {\(\mathscr{l}\)}\({}_{\mbox{1}}\) Approximation
of Self-Bounding Functions},
journal = {CoRR},
volume = {abs/1404.4702},
year = {2014},
url = {http://arxiv.org/abs/1404.4702},
eprinttype = {arXiv},
eprint = {1404.4702},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/FeldmanKV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/FeldmanK14,
author = {Vitaly Feldman and
Pravesh Kothari},
title = {Agnostic Learning of Disjunctions on Symmetric Distributions},
journal = {CoRR},
volume = {abs/1405.6791},
year = {2014},
url = {http://arxiv.org/abs/1405.6791},
eprinttype = {arXiv},
eprint = {1405.6791},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/FeldmanK14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Chakrabarty0K14,
author = {Deeparnab Chakrabarty and
Prateek Jain and
Pravesh Kothari},
title = {Provable Submodular Minimization using Wolfe's Algorithm},
journal = {CoRR},
volume = {abs/1411.0095},
year = {2014},
url = {http://arxiv.org/abs/1411.0095},
eprinttype = {arXiv},
eprint = {1411.0095},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Chakrabarty0K14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KothariM14,
author = {Pravesh Kothari and
Raghu Meka},
title = {Almost Optimal Pseudorandom Generators for Spherical Caps},
journal = {CoRR},
volume = {abs/1411.6299},
year = {2014},
url = {http://arxiv.org/abs/1411.6299},
eprinttype = {arXiv},
eprint = {1411.6299},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KothariM14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KlivansK14,
author = {Adam R. Klivans and
Pravesh Kothari},
title = {Embedding Hard Learning Problems into Gaussian Space},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-063}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/063},
eprinttype = {ECCC},
eprint = {TR14-063},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KlivansK14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/KlivansKO13,
author = {Adam R. Klivans and
Pravesh Kothari and
Igor C. Oliveira},
title = {Constructing Hard Functions Using Learning Algorithms},
booktitle = {Proceedings of the 28th Conference on Computational Complexity, {CCC}
2013, K.lo Alto, California, USA, 5-7 June, 2013},
pages = {86--97},
publisher = {{IEEE} Computer Society},
year = {2013},
url = {https://doi.org/10.1109/CCC.2013.18},
doi = {10.1109/CCC.2013.18},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/KlivansKO13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/FeldmanKV13,
author = {Vitaly Feldman and
Pravesh Kothari and
Jan Vondr{\'{a}}k},
editor = {Shai Shalev{-}Shwartz and
Ingo Steinwart},
title = {Representation, Approximation and Learning of Submodular Functions
Using Low-rank Decision Trees},
booktitle = {{COLT} 2013 - The 26th Annual Conference on Learning Theory, June
12-14, 2013, Princeton University, NJ, {USA}},
series = {{JMLR} Workshop and Conference Proceedings},
volume = {30},
pages = {711--740},
publisher = {JMLR.org},
year = {2013},
url = {http://proceedings.mlr.press/v30/Feldman13.html},
timestamp = {Wed, 29 May 2019 08:41:46 +0200},
biburl = {https://dblp.org/rec/conf/colt/FeldmanKV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1304-0730,
author = {Vitaly Feldman and
Pravesh Kothari and
Jan Vondr{\'{a}}k},
title = {Representation, Approximation and Learning of Submodular Functions
Using Low-rank Decision Trees},
journal = {CoRR},
volume = {abs/1304.0730},
year = {2013},
url = {http://arxiv.org/abs/1304.0730},
eprinttype = {arXiv},
eprint = {1304.0730},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1304-0730.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1304-2079,
author = {Vitaly Feldman and
Pravesh Kothari},
title = {Learning Coverage Functions},
journal = {CoRR},
volume = {abs/1304.2079},
year = {2013},
url = {http://arxiv.org/abs/1304.2079},
eprinttype = {arXiv},
eprint = {1304.2079},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1304-2079.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KlivansKO13,
author = {Adam R. Klivans and
Pravesh Kothari and
Igor C. Oliveira},
title = {Constructing Hard Functions from Learning Algorithms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-129}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/129},
eprinttype = {ECCC},
eprint = {TR13-129},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KlivansKO13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ChattopadhyayKK12,
author = {Eshan Chattopadhyay and
Adam R. Klivans and
Pravesh Kothari},
editor = {Anupam Gupta and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Rocco A. Servedio},
title = {An Explicit VC-Theorem for Low-Degree Polynomials},
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 = {495--504},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32512-0\_42},
doi = {10.1007/978-3-642-32512-0\_42},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/ChattopadhyayKK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CheraghchiKKL12,
author = {Mahdi Cheraghchi and
Adam R. Klivans and
Pravesh Kothari and
Homin K. Lee},
editor = {Yuval Rabani},
title = {Submodular functions are noise stable},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1586--1592},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.126},
doi = {10.1137/1.9781611973099.126},
timestamp = {Tue, 02 Feb 2021 17:07:31 +0100},
biburl = {https://dblp.org/rec/conf/soda/CheraghchiKKL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:journals/jmlr/JainKT12,
author = {Prateek Jain and
Pravesh Kothari and
Abhradeep Thakurta},
editor = {Shie Mannor and
Nathan Srebro and
Robert C. Williamson},
title = {Differentially Private Online Learning},
booktitle = {{COLT} 2012 - The 25th Annual Conference on Learning Theory, June
25-27, 2012, Edinburgh, Scotland},
series = {{JMLR} Proceedings},
volume = {23},
pages = {24.1--24.34},
publisher = {JMLR.org},
year = {2012},
url = {http://proceedings.mlr.press/v23/jain12/jain12.pdf},
timestamp = {Wed, 29 May 2019 08:41:46 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/JainKT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChattopadhyayKK12,
author = {Eshan Chattopadhyay and
Adam R. Klivans and
Pravesh Kothari},
title = {An Explicit VC-Theorem for Low-Degree Polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-127}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/127},
eprinttype = {ECCC},
eprint = {TR12-127},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChattopadhyayKK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1106-0518,
author = {Mahdi Cheraghchi and
Adam R. Klivans and
Pravesh Kothari and
Homin K. Lee},
title = {Submodular Functions Are Noise Stable},
journal = {CoRR},
volume = {abs/1106.0518},
year = {2011},
url = {http://arxiv.org/abs/1106.0518},
eprinttype = {arXiv},
eprint = {1106.0518},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1106-0518.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1109-0105,
author = {Prateek Jain and
Pravesh Kothari and
Abhradeep Thakurta},
title = {Differentially Private Online Learning},
journal = {CoRR},
volume = {abs/1109.0105},
year = {2011},
url = {http://arxiv.org/abs/1109.0105},
eprinttype = {arXiv},
eprint = {1109.0105},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1109-0105.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CheraghchiKKL11,
author = {Mahdi Cheraghchi and
Adam R. Klivans and
Pravesh Kothari and
Homin K. Lee},
title = {Submodular Functions Are Noise Stable},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-090}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/090},
eprinttype = {ECCC},
eprint = {TR11-090},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CheraghchiKKL11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/asplos/BurckhardtKMN10,
author = {Sebastian Burckhardt and
Pravesh Kothari and
Madanlal Musuvathi and
Santosh Nagarakatte},
editor = {James C. Hoe and
Vikram S. Adve},
title = {A randomized scheduler with probabilistic guarantees of finding bugs},
booktitle = {Proceedings of the 15th International Conference on Architectural
Support for Programming Languages and Operating Systems, {ASPLOS}
2010, Pittsburgh, Pennsylvania, USA, March 13-17, 2010},
pages = {167--178},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1736020.1736040},
doi = {10.1145/1736020.1736040},
timestamp = {Wed, 07 Jul 2021 13:23:08 +0200},
biburl = {https://dblp.org/rec/conf/asplos/BurckhardtKMN10.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-05-03 00:10 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:
