default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Prasad Raghavendra
@inproceedings{DBLP:conf/colt/GopalanORSS24,
author = {Parikshit Gopalan and
Princewill Okoroafor and
Prasad Raghavendra and
Abhishek Sherry and
Mihir Singhal},
editor = {Shipra Agrawal and
Aaron Roth},
title = {Omnipredictors for regression and the approximate rank of convex functions},
booktitle = {The Thirty Seventh Annual Conference on Learning Theory, June 30 -
July 3, 2023, Edmonton, Canada},
series = {Proceedings of Machine Learning Research},
volume = {247},
pages = {2027--2070},
publisher = {{PMLR}},
year = {2024},
url = {https://proceedings.mlr.press/v247/gopalan24b.html},
timestamp = {Fri, 05 Jul 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/GopalanORSS24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MohantyRW24,
author = {Sidhanth Mohanty and
Prasad Raghavendra and
David X. Wu},
editor = {Bojan Mohar and
Igor Shinkar and
Ryan O'Donnell},
title = {Robust Recovery for Stochastic Block Models, Simplified and Generalized},
booktitle = {Proceedings of the 56th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2024, Vancouver, BC, Canada, June 24-28, 2024},
pages = {367--374},
publisher = {{ACM}},
year = {2024},
url = {https://doi.org/10.1145/3618260.3649761},
doi = {10.1145/3618260.3649761},
timestamp = {Tue, 18 Jun 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/MohantyRW24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2401-14645,
author = {Parikshit Gopalan and
Princewill Okoroafor and
Prasad Raghavendra and
Abhishek Shetty and
Mihir Singhal},
title = {Omnipredictors for Regression and the Approximate Rank of Convex Functions},
journal = {CoRR},
volume = {abs/2401.14645},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2401.14645},
doi = {10.48550/ARXIV.2401.14645},
eprinttype = {arXiv},
eprint = {2401.14645},
timestamp = {Tue, 06 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2401-14645.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2402-13921,
author = {Sidhanth Mohanty and
Prasad Raghavendra and
David X. Wu},
title = {Robust recovery for stochastic block models, simplified and generalized},
journal = {CoRR},
volume = {abs/2402.13921},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2402.13921},
doi = {10.48550/ARXIV.2402.13921},
eprinttype = {arXiv},
eprint = {2402.13921},
timestamp = {Fri, 22 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2402-13921.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2405-05373,
author = {Venkatesan Guruswami and
Jun{-}Ting Hsieh and
Prasad Raghavendra},
title = {Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond
the {\(\surd\)}n Dimension Threshold},
journal = {CoRR},
volume = {abs/2405.05373},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2405.05373},
doi = {10.48550/ARXIV.2405.05373},
eprinttype = {arXiv},
eprint = {2405.05373},
timestamp = {Thu, 13 Jun 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2405-05373.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2405-20849,
author = {Kuikui Liu and
Sidhanth Mohanty and
Prasad Raghavendra and
Amit Rajaraman and
David X. Wu},
title = {Locally Stationary Distributions: {A} Framework for Analyzing Slow-Mixing
Markov Chains},
journal = {CoRR},
volume = {abs/2405.20849},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2405.20849},
doi = {10.48550/ARXIV.2405.20849},
eprinttype = {arXiv},
eprint = {2405.20849},
timestamp = {Mon, 24 Jun 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2405-20849.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/Raghavendra23,
author = {Prasad Raghavendra},
editor = {Patricia Bouyer and
Srikanth Srinivasan},
title = {On Measuring Average Case Complexity via Sum-Of-Squares Degree (Invited
Talk)},
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 = {2:1--2:1},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2023.2},
doi = {10.4230/LIPICS.FSTTCS.2023.2},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/Raghavendra23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/EldanMR23,
author = {Ronen Eldan and
Dan Mikulincer and
Prasad Raghavendra},
editor = {Barna Saha and
Rocco A. Servedio},
title = {Noise Stability on the Boolean Hypercube via a Renormalized Brownian
Motion},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {661--671},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585118},
doi = {10.1145/3564246.3585118},
timestamp = {Mon, 22 May 2023 13:01:48 +0200},
biburl = {https://dblp.org/rec/conf/stoc/EldanMR23.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/stoc/HopkinsRS22,
author = {Samuel B. Hopkins and
Prasad Raghavendra and
Abhishek Shetty},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {Matrix discrepancy from Quantum communication},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {637--648},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3519954},
doi = {10.1145/3519935.3519954},
timestamp = {Tue, 27 Dec 2022 09:06:31 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HopkinsRS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2208-06508,
author = {Ronen Eldan and
Dan Mikulincer and
Prasad Raghavendra},
title = {Noise stability on the Boolean hypercube via a renormalized Brownian
motion},
journal = {CoRR},
volume = {abs/2208.06508},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2208.06508},
doi = {10.48550/ARXIV.2208.06508},
eprinttype = {arXiv},
eprint = {2208.06508},
timestamp = {Wed, 17 Aug 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2208-06508.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LiuMR21,
author = {Siqi Liu and
Sidhanth Mohanty and
Prasad Raghavendra},
title = {On statistical inference when fixed points of belief propagation are
unstable},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {395--405},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00047},
doi = {10.1109/FOCS52979.2021.00047},
timestamp = {Fri, 12 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/LiuMR21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BanksMR21,
author = {Jess Banks and
Sidhanth Mohanty and
Prasad Raghavendra},
editor = {D{\'{a}}niel Marx},
title = {Local Statistics, Semidefinite Programming, and Community Detection},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {1298--1316},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.79},
doi = {10.1137/1.9781611976465.79},
timestamp = {Thu, 15 Jul 2021 13:48:55 +0200},
biburl = {https://dblp.org/rec/conf/soda/BanksMR21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2101-10882,
author = {Siqi Liu and
Sidhanth Mohanty and
Prasad Raghavendra},
title = {Computational phase transitions in sparse planted problems?},
journal = {CoRR},
volume = {abs/2101.10882},
year = {2021},
url = {https://arxiv.org/abs/2101.10882},
eprinttype = {arXiv},
eprint = {2101.10882},
timestamp = {Fri, 12 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2101-10882.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-10099,
author = {Samuel B. Hopkins and
Prasad Raghavendra and
Abhishek Shetty},
title = {Matrix Discrepancy from Quantum Communication},
journal = {CoRR},
volume = {abs/2110.10099},
year = {2021},
url = {https://arxiv.org/abs/2110.10099},
eprinttype = {arXiv},
eprint = {2110.10099},
timestamp = {Mon, 25 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-10099.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/RaghavendraY20,
author = {Prasad Raghavendra and
Morris Yau},
editor = {Jacob D. Abernethy and
Shivani Agarwal},
title = {List Decodable Subspace Recovery},
booktitle = {Conference on Learning Theory, {COLT} 2020, 9-12 July 2020, Virtual
Event [Graz, Austria]},
series = {Proceedings of Machine Learning Research},
volume = {125},
pages = {3206--3226},
publisher = {{PMLR}},
year = {2020},
url = {http://proceedings.mlr.press/v125/raghavendra20a.html},
timestamp = {Fri, 27 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/RaghavendraY20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RaghavendraY20,
author = {Prasad Raghavendra and
Morris Yau},
editor = {Shuchi Chawla},
title = {List Decodable Learning via Sum of Squares},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
pages = {161--180},
publisher = {{SIAM}},
year = {2020},
url = {https://doi.org/10.1137/1.9781611975994.10},
doi = {10.1137/1.9781611975994.10},
timestamp = {Thu, 15 Jul 2021 13:48:53 +0200},
biburl = {https://dblp.org/rec/conf/soda/RaghavendraY20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Brown-CohenR20,
author = {Jonah Brown{-}Cohen and
Prasad Raghavendra},
editor = {Shuchi Chawla},
title = {Extended Formulation Lower Bounds for Refuting Random CSPs},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
pages = {305--324},
publisher = {{SIAM}},
year = {2020},
url = {https://doi.org/10.1137/1.9781611975994.19},
doi = {10.1137/1.9781611975994.19},
timestamp = {Thu, 15 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/Brown-CohenR20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CherapanamjeriH20,
author = {Yeshwanth Cherapanamjeri and
Samuel B. Hopkins and
Tarun Kathuria and
Prasad Raghavendra and
Nilesh Tripuraneni},
editor = {Konstantin Makarychev and
Yury Makarychev and
Madhur Tulsiani and
Gautam Kamath and
Julia Chuzhoy},
title = {Algorithms for heavy-tailed statistics: regression, covariance estimation,
and beyond},
booktitle = {Proceedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
pages = {601--609},
publisher = {{ACM}},
year = {2020},
url = {https://doi.org/10.1145/3357713.3384329},
doi = {10.1145/3357713.3384329},
timestamp = {Mon, 18 Dec 2023 07:33:37 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CherapanamjeriH20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MohantyRX20,
author = {Sidhanth Mohanty and
Prasad Raghavendra and
Jeff Xu},
editor = {Konstantin Makarychev and
Yury Makarychev and
Madhur Tulsiani and
Gautam Kamath and
Julia Chuzhoy},
title = {Lifting sum-of-squares lower bounds: degree-2 to degree-4},
booktitle = {Proceedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
pages = {840--853},
publisher = {{ACM}},
year = {2020},
url = {https://doi.org/10.1145/3357713.3384319},
doi = {10.1145/3357713.3384319},
timestamp = {Tue, 09 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/MohantyRX20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2002-03004,
author = {Prasad Raghavendra and
Morris Yau},
title = {List Decodable Subspace Recovery},
journal = {CoRR},
volume = {abs/2002.03004},
year = {2020},
url = {https://arxiv.org/abs/2002.03004},
eprinttype = {arXiv},
eprint = {2002.03004},
timestamp = {Wed, 12 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2002-03004.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RaghavendraRSW19,
author = {Prasad Raghavendra and
Nick Ryder and
Nikhil Srivastava and
Benjamin Weitz},
editor = {Timothy M. Chan},
title = {Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity
Cones},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {2322--2332},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.141},
doi = {10.1137/1.9781611975482.141},
timestamp = {Thu, 15 Jul 2021 13:49:01 +0200},
biburl = {https://dblp.org/rec/conf/soda/RaghavendraRSW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1905-04660,
author = {Prasad Raghavendra and
Morris Yau},
title = {List Decodable Learning via Sum of Squares},
journal = {CoRR},
volume = {abs/1905.04660},
year = {2019},
url = {http://arxiv.org/abs/1905.04660},
eprinttype = {arXiv},
eprint = {1905.04660},
timestamp = {Tue, 28 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1905-04660.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-01411,
author = {Sidhanth Mohanty and
Prasad Raghavendra and
Jeff Xu},
title = {Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4},
journal = {CoRR},
volume = {abs/1911.01411},
year = {2019},
url = {http://arxiv.org/abs/1911.01411},
eprinttype = {arXiv},
eprint = {1911.01411},
timestamp = {Mon, 11 Nov 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-01411.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-01960,
author = {Jess Banks and
Sidhanth Mohanty and
Prasad Raghavendra},
title = {Local Statistics, Semidefinite Programming, and Community Detection},
journal = {CoRR},
volume = {abs/1911.01960},
year = {2019},
url = {http://arxiv.org/abs/1911.01960},
eprinttype = {arXiv},
eprint = {1911.01960},
timestamp = {Mon, 11 Nov 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-01960.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-02911,
author = {Jonah Brown{-}Cohen and
Prasad Raghavendra},
title = {Extended Formulation Lower Bounds for Refuting Random CSPs},
journal = {CoRR},
volume = {abs/1911.02911},
year = {2019},
url = {http://arxiv.org/abs/1911.02911},
eprinttype = {arXiv},
eprint = {1911.02911},
timestamp = {Mon, 11 Nov 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-02911.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1912-11071,
author = {Yeshwanth Cherapanamjeri and
Samuel B. Hopkins and
Tarun Kathuria and
Prasad Raghavendra and
Nilesh Tripuraneni},
title = {Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation,
and Beyond},
journal = {CoRR},
volume = {abs/1912.11071},
year = {2019},
url = {http://arxiv.org/abs/1912.11071},
eprinttype = {arXiv},
eprint = {1912.11071},
timestamp = {Tue, 07 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1912-11071.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 = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/talg/HopkinsKPRS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/GhaziKR18,
author = {Badih Ghazi and
Pritish Kamath and
Prasad Raghavendra},
editor = {Rocco A. Servedio},
title = {Dimension Reduction for Polynomials over Gaussian Space and Applications},
booktitle = {33rd Computational Complexity Conference, {CCC} 2018, June 22-24,
2018, San Diego, CA, {USA}},
series = {LIPIcs},
volume = {102},
pages = {28:1--28:37},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.CCC.2018.28},
doi = {10.4230/LIPICS.CCC.2018.28},
timestamp = {Thu, 02 Feb 2023 13:27:04 +0100},
biburl = {https://dblp.org/rec/conf/coco/GhaziKR18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/BecchettiCMNPRT18,
author = {Luca Becchetti and
Andrea Clementi and
Pasin Manurangsi and
Emanuele Natale and
Francesco Pasquale and
Prasad Raghavendra and
Luca Trevisan},
editor = {Yossi Azar and
Hannah Bast and
Grzegorz Herman},
title = {Average Whenever You Meet: Opportunistic Protocols for Community Detection},
booktitle = {26th Annual European Symposium on Algorithms, {ESA} 2018, August 20-22,
2018, Helsinki, Finland},
series = {LIPIcs},
volume = {112},
pages = {7:1--7:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.ESA.2018.7},
doi = {10.4230/LIPICS.ESA.2018.7},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/esa/BecchettiCMNPRT18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1807-11419,
author = {Prasad Raghavendra and
Tselil Schramm and
David Steurer},
title = {High-dimensional estimation via sum-of-squares proofs},
journal = {CoRR},
volume = {abs/1807.11419},
year = {2018},
url = {http://arxiv.org/abs/1807.11419},
eprinttype = {arXiv},
eprint = {1807.11419},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1807-11419.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/BraunBHPRRWZ17,
author = {G{\'{a}}bor Braun and
Jonah Brown{-}Cohen and
Arefin Huq and
Sebastian Pokutta and
Prasad Raghavendra and
Aurko Roy and
Benjamin Weitz and
Daniel Zink},
title = {The matching problem has no small symmetric {SDP}},
journal = {Math. Program.},
volume = {165},
number = {2},
pages = {643--662},
year = {2017},
url = {https://doi.org/10.1007/s10107-016-1098-z},
doi = {10.1007/S10107-016-1098-Z},
timestamp = {Mon, 09 Oct 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/BraunBHPRRWZ17.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 = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/HopkinsKPRSS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ManurangsiR17,
author = {Pasin Manurangsi and
Prasad Raghavendra},
editor = {Ioannis Chatzigiannakis and
Piotr Indyk and
Fabian Kuhn and
Anca Muscholl},
title = {A Birthday Repetition Theorem and Complexity of Approximating Dense
CSPs},
booktitle = {44th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2017, July 10-14, 2017, Warsaw, Poland},
series = {LIPIcs},
volume = {80},
pages = {78:1--78:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.78},
doi = {10.4230/LIPICS.ICALP.2017.78},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/icalp/ManurangsiR17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/RaghavendraW17,
author = {Prasad Raghavendra and
Benjamin Weitz},
editor = {Ioannis Chatzigiannakis and
Piotr Indyk and
Fabian Kuhn and
Anca Muscholl},
title = {On the Bit Complexity of Sum-of-Squares Proofs},
booktitle = {44th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2017, July 10-14, 2017, Warsaw, Poland},
series = {LIPIcs},
volume = {80},
pages = {80:1--80:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.80},
doi = {10.4230/LIPICS.ICALP.2017.80},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/RaghavendraW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/RaghavendraRS17,
author = {Prasad Raghavendra and
Nick Ryder and
Nikhil Srivastava},
editor = {Christos H. Papadimitriou},
title = {Real Stability Testing},
booktitle = {8th Innovations in Theoretical Computer Science Conference, {ITCS}
2017, January 9-11, 2017, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {67},
pages = {5:1--5:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2017.5},
doi = {10.4230/LIPICS.ITCS.2017.5},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/RaghavendraRS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RaghavendraRS17,
author = {Prasad Raghavendra and
Satish Rao and
Tselil Schramm},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Strongly refuting random CSPs below the spectral threshold},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {121--131},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055417},
doi = {10.1145/3055399.3055417},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/RaghavendraRS17.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}
}
@article{DBLP:journals/corr/RaghavendraW17,
author = {Prasad Raghavendra and
Benjamin Weitz},
title = {On the Bit Complexity of Sum-of-Squares Proofs},
journal = {CoRR},
volume = {abs/1702.05139},
year = {2017},
url = {http://arxiv.org/abs/1702.05139},
eprinttype = {arXiv},
eprint = {1702.05139},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/RaghavendraW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BecchettiCNPRT17,
author = {Luca Becchetti and
Andrea Clementi and
Emanuele Natale and
Francesco Pasquale and
Prasad Raghavendra and
Luca Trevisan},
title = {Friend or Foe? Population Protocols can perform Community Detection},
journal = {CoRR},
volume = {abs/1703.05045},
year = {2017},
url = {http://arxiv.org/abs/1703.05045},
eprinttype = {arXiv},
eprint = {1703.05045},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BecchettiCNPRT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1708-03808,
author = {Badih Ghazi and
Pritish Kamath and
Prasad Raghavendra},
title = {Dimension Reduction for Polynomials over Gaussian Space and Applications},
journal = {CoRR},
volume = {abs/1708.03808},
year = {2017},
url = {http://arxiv.org/abs/1708.03808},
eprinttype = {arXiv},
eprint = {1708.03808},
timestamp = {Thu, 08 Aug 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1708-03808.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-11497,
author = {Prasad Raghavendra and
Nick Ryder and
Nikhil Srivastava and
Benjamin Weitz},
title = {Exponential lower bounds on spectrahedral representations of hyperbolicity
cones},
journal = {CoRR},
volume = {abs/1711.11497},
year = {2017},
url = {http://arxiv.org/abs/1711.11497},
eprinttype = {arXiv},
eprint = {1711.11497},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1711-11497.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GhaziKR17,
author = {Badih Ghazi and
Pritish Kamath and
Prasad Raghavendra},
title = {Dimension Reduction for Polynomials over Gaussian Space and Applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-125}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/125},
eprinttype = {ECCC},
eprint = {TR17-125},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GhaziKR17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/ChanLRS16,
author = {Siu On Chan and
James R. Lee and
Prasad Raghavendra and
David Steurer},
title = {Approximate Constraint Satisfaction Requires Large {LP} Relaxations},
journal = {J. {ACM}},
volume = {63},
number = {4},
pages = {34:1--34:22},
year = {2016},
url = {https://doi.org/10.1145/2811255},
doi = {10.1145/2811255},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/ChanLRS16.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/icalp/Brown-CohenR16,
author = {Jonah Brown{-}Cohen and
Prasad Raghavendra},
editor = {Ioannis Chatzigiannakis and
Michael Mitzenmacher and
Yuval Rabani and
Davide Sangiorgi},
title = {Correlation Decay and Tractability of CSPs},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming,
{ICALP} 2016, July 11-15, 2016, Rome, Italy},
series = {LIPIcs},
volume = {55},
pages = {79:1--79:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2016.79},
doi = {10.4230/LIPICS.ICALP.2016.79},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/icalp/Brown-CohenR16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BraunBHPRRWZ16,
author = {G{\'{a}}bor Braun and
Jonah Brown{-}Cohen and
Arefin Huq and
Sebastian Pokutta and
Prasad Raghavendra and
Aurko Roy and
Benjamin Weitz and
Daniel Zink},
editor = {Robert Krauthgamer},
title = {The matching problem has no small symmetric {SDP}},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
pages = {1067--1078},
publisher = {{SIAM}},
year = {2016},
url = {https://doi.org/10.1137/1.9781611974331.ch75},
doi = {10.1137/1.9781611974331.CH75},
timestamp = {Tue, 02 Feb 2021 17:07:56 +0100},
biburl = {https://dblp.org/rec/conf/soda/BraunBHPRRWZ16.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 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/HopkinsKPRS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/RaghavendraRS16,
author = {Prasad Raghavendra and
Satish Rao and
Tselil Schramm},
title = {Strongly Refuting Random CSPs Below the Spectral Threshold},
journal = {CoRR},
volume = {abs/1605.00058},
year = {2016},
url = {http://arxiv.org/abs/1605.00058},
eprinttype = {arXiv},
eprint = {1605.00058},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/RaghavendraRS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ManurangsiR16,
author = {Pasin Manurangsi and
Prasad Raghavendra},
title = {A Birthday Repetition Theorem and Complexity of Approximating Dense
CSPs},
journal = {CoRR},
volume = {abs/1607.02986},
year = {2016},
url = {http://arxiv.org/abs/1607.02986},
eprinttype = {arXiv},
eprint = {1607.02986},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ManurangsiR16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/RaghavendraRS16a,
author = {Prasad Raghavendra and
Nick Ryder and
Nikhil Srivastava},
title = {Real Stability Testing},
journal = {CoRR},
volume = {abs/1610.00209},
year = {2016},
url = {http://arxiv.org/abs/1610.00209},
eprinttype = {arXiv},
eprint = {1610.00209},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/RaghavendraRS16a.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/siamcomp/BarakGHMRS15,
author = {Boaz Barak and
Parikshit Gopalan and
Johan H{\aa}stad and
Raghu Meka and
Prasad Raghavendra and
David Steurer},
title = {Making the Long Code Shorter},
journal = {{SIAM} J. Comput.},
volume = {44},
number = {5},
pages = {1287--1324},
year = {2015},
url = {https://doi.org/10.1137/130929394},
doi = {10.1137/130929394},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BarakGHMRS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BarakMORRSTVWW15,
author = {Boaz Barak and
Ankur Moitra and
Ryan O'Donnell and
Prasad Raghavendra and
Oded Regev and
David Steurer and
Luca Trevisan and
Aravindan Vijayaraghavan and
David Witmer and
John Wright},
editor = {Naveen Garg and
Klaus Jansen and
Anup Rao and
Jos{\'{e}} D. P. Rolim},
title = {Beating the Random Assignment on Constraint Satisfaction Problems
of Bounded Degree},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2015, August 24-26, 2015, Princeton,
NJ, {USA}},
series = {LIPIcs},
volume = {40},
pages = {110--123},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.110},
doi = {10.4230/LIPICS.APPROX-RANDOM.2015.110},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/BarakMORRSTVWW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LeeRS15,
author = {James R. Lee and
Prasad Raghavendra and
David Steurer},
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {Lower Bounds on the Size of Semidefinite Programming Relaxations},
booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
pages = {567--576},
publisher = {{ACM}},
year = {2015},
url = {https://doi.org/10.1145/2746539.2746599},
doi = {10.1145/2746539.2746599},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/LeeRS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Brown-CohenR15,
author = {Jonah Brown{-}Cohen and
Prasad Raghavendra},
title = {Combinatorial Optimization Algorithms via Polymorphisms},
journal = {CoRR},
volume = {abs/1501.01598},
year = {2015},
url = {http://arxiv.org/abs/1501.01598},
eprinttype = {arXiv},
eprint = {1501.01598},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Brown-CohenR15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BraunBHPRRWZ15,
author = {G{\'{a}}bor Braun and
Jonah Brown{-}Cohen and
Arefin Huq and
Sebastian Pokutta and
Prasad Raghavendra and
Aurko Roy and
Benjamin Weitz and
Daniel Zink},
title = {The matching problem has no small symmetric {SDP}},
journal = {CoRR},
volume = {abs/1504.00703},
year = {2015},
url = {http://arxiv.org/abs/1504.00703},
eprinttype = {arXiv},
eprint = {1504.00703},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BraunBHPRRWZ15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BarakMORRSTVWW15,
author = {Boaz Barak and
Ankur Moitra and
Ryan O'Donnell and
Prasad Raghavendra and
Oded Regev and
David Steurer and
Luca Trevisan and
Aravindan Vijayaraghavan and
David Witmer and
John Wright},
title = {Beating the random assignment on constraint satisfaction problems
of bounded degree},
journal = {CoRR},
volume = {abs/1505.03424},
year = {2015},
url = {http://arxiv.org/abs/1505.03424},
eprinttype = {arXiv},
eprint = {1505.03424},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BarakMORRSTVWW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/RaghavendraS15,
author = {Prasad Raghavendra and
Tselil Schramm},
title = {Tight Lower Bounds for Planted Clique in the Degree-4 {SOS} Program},
journal = {CoRR},
volume = {abs/1507.05136},
year = {2015},
url = {http://arxiv.org/abs/1507.05136},
eprinttype = {arXiv},
eprint = {1507.05136},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/RaghavendraS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakMORRSTVWW15,
author = {Boaz Barak and
Ankur Moitra and
Ryan O'Donnell and
Prasad Raghavendra and
Oded Regev and
David Steurer and
Luca Trevisan and
Aravindan Vijayaraghavan and
David Witmer and
John Wright},
title = {Beating the random assignment on constraint satisfaction problems
of bounded degree},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-082}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/082},
eprinttype = {ECCC},
eprint = {TR15-082},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakMORRSTVWW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Brown-CohenR15,
author = {Jonah Brown{-}Cohen and
Prasad Raghavendra},
title = {Combinatorial Optimization Algorithms via Polymorphisms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-007}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/007},
eprinttype = {ECCC},
eprint = {TR15-007},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Brown-CohenR15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/KhanR14,
author = {Arindam Khan and
Prasad Raghavendra},
title = {On mimicking networks representing minimum terminal cuts},
journal = {Inf. Process. Lett.},
volume = {114},
number = {7},
pages = {365--371},
year = {2014},
url = {https://doi.org/10.1016/j.ipl.2014.02.011},
doi = {10.1016/J.IPL.2014.02.011},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/KhanR14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/DiakonikolasRST14,
author = {Ilias Diakonikolas and
Prasad Raghavendra and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Average Sensitivity and Noise Sensitivity of Polynomial Threshold
Functions},
journal = {{SIAM} J. Comput.},
volume = {43},
number = {1},
pages = {231--253},
year = {2014},
url = {https://doi.org/10.1137/110855223},
doi = {10.1137/110855223},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/DiakonikolasRST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/RaghavendraS14,
author = {Prasad Raghavendra and
Tselil Schramm},
editor = {Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Nikhil R. Devanur and
Cristopher Moore},
title = {Gap Amplification for Small-Set Expansion via Random Walks},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2014, September 4-6, 2014, Barcelona,
Spain},
series = {LIPIcs},
volume = {28},
pages = {381--391},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2014},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.381},
doi = {10.4230/LIPICS.APPROX-RANDOM.2014.381},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/RaghavendraS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/LeeRST14,
author = {James R. Lee and
Prasad Raghavendra and
David Steurer and
Ning Tan},
title = {On the Power of Symmetric {LP} and {SDP} Relaxations},
booktitle = {{IEEE} 29th Conference on Computational Complexity, {CCC} 2014, Vancouver,
BC, Canada, June 11-13, 2014},
pages = {13--21},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/CCC.2014.10},
doi = {10.1109/CCC.2014.10},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/LeeRST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/HardtMRW14,
author = {Moritz Hardt and
Raghu Meka and
Prasad Raghavendra and
Benjamin Weitz},
editor = {Maria{-}Florina Balcan and
Vitaly Feldman and
Csaba Szepesv{\'{a}}ri},
title = {Computational Limits for Matrix Completion},
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 = {703--725},
publisher = {JMLR.org},
year = {2014},
url = {http://proceedings.mlr.press/v35/hardt14b.html},
timestamp = {Wed, 29 May 2019 08:41:46 +0200},
biburl = {https://dblp.org/rec/conf/colt/HardtMRW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/HardtMRW14,
author = {Moritz Hardt and
Raghu Meka and
Prasad Raghavendra and
Benjamin Weitz},
title = {Computational Limits for Matrix Completion},
journal = {CoRR},
volume = {abs/1402.2331},
year = {2014},
url = {http://arxiv.org/abs/1402.2331},
eprinttype = {arXiv},
eprint = {1402.2331},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/HardtMRW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/LeeRS14,
author = {James R. Lee and
Prasad Raghavendra and
David Steurer},
title = {Lower bounds on the size of semidefinite programming relaxations},
journal = {CoRR},
volume = {abs/1411.6317},
year = {2014},
url = {http://arxiv.org/abs/1411.6317},
eprinttype = {arXiv},
eprint = {1411.6317},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/LeeRS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/ChenENRRS13,
author = {Ning Chen and
Roee Engelberg and
C. Thach Nguyen and
Prasad Raghavendra and
Atri Rudra and
Gyanit Singh},
title = {Improved Approximation Algorithms for the Spanning Star Forest Problem},
journal = {Algorithmica},
volume = {65},
number = {3},
pages = {498--516},
year = {2013},
url = {https://doi.org/10.1007/s00453-011-9607-1},
doi = {10.1007/S00453-011-9607-1},
timestamp = {Sun, 26 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/ChenENRRS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/ChawlaRR13,
author = {Shuchi Chawla and
Prasad Raghavendra and
Dana Randall},
title = {Foreword to the Special Issue on SODA'11},
journal = {{ACM} Trans. Algorithms},
volume = {9},
number = {3},
pages = {20:1},
year = {2013},
url = {https://doi.org/10.1145/2483699.2483700},
doi = {10.1145/2483699.2483700},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/ChawlaRR13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChanLRS13,
author = {Siu On Chan and
James R. Lee and
Prasad Raghavendra and
David Steurer},
title = {Approximate Constraint Satisfaction Requires Large {LP} Relaxations},
booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2013, 26-29 October, 2013, Berkeley, CA, {USA}},
pages = {350--359},
publisher = {{IEEE} Computer Society},
year = {2013},
url = {https://doi.org/10.1109/FOCS.2013.45},
doi = {10.1109/FOCS.2013.45},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChanLRS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LouisRV13,
author = {Anand Louis and
Prasad Raghavendra and
Santosh S. Vempala},
title = {The Complexity of Approximating Vertex Expansion},
booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2013, 26-29 October, 2013, Berkeley, CA, {USA}},
pages = {360--369},
publisher = {{IEEE} Computer Society},
year = {2013},
url = {https://doi.org/10.1109/FOCS.2013.46},
doi = {10.1109/FOCS.2013.46},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LouisRV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/approx/2013,
editor = {Prasad Raghavendra and
Sofya Raskhodnikova and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim},
title = {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},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-40328-6},
doi = {10.1007/978-3-642-40328-6},
isbn = {978-3-642-40327-9},
timestamp = {Tue, 21 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/2013.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1304-3139,
author = {Anand Louis and
Prasad Raghavendra and
Santosh S. Vempala},
title = {The Complexity of Approximating Vertex Expansion},
journal = {CoRR},
volume = {abs/1304.3139},
year = {2013},
url = {http://arxiv.org/abs/1304.3139},
eprinttype = {arXiv},
eprint = {1304.3139},
timestamp = {Thu, 24 Oct 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1304-3139.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChanLRS13,
author = {Siu On Chan and
James R. Lee and
Prasad Raghavendra and
David Steurer},
title = {Approximate Constraint Satisfaction Requires Large {LP} Relaxations},
journal = {CoRR},
volume = {abs/1309.0563},
year = {2013},
url = {http://arxiv.org/abs/1309.0563},
eprinttype = {arXiv},
eprint = {1309.0563},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChanLRS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/RaghavendraS13,
author = {Prasad Raghavendra and
Tselil Schramm},
title = {Gap Amplification for Small-Set Expansion via Random Walks},
journal = {CoRR},
volume = {abs/1310.1493},
year = {2013},
url = {http://arxiv.org/abs/1310.1493},
eprinttype = {arXiv},
eprint = {1310.1493},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/RaghavendraS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cpc/BhattacharyyaGRS12,
author = {Arnab Bhattacharyya and
Elena Grigorescu and
Prasad Raghavendra and
Asaf Shapira},
title = {Testing Odd-Cycle-Freeness in Boolean Functions},
journal = {Comb. Probab. Comput.},
volume = {21},
number = {6},
pages = {835--855},
year = {2012},
url = {https://doi.org/10.1017/S0963548312000363},
doi = {10.1017/S0963548312000363},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cpc/BhattacharyyaGRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/FeldmanGRW12,
author = {Vitaly Feldman and
Venkatesan Guruswami and
Prasad Raghavendra and
Yi Wu},
title = {Agnostic Learning of Monomials by Halfspaces Is Hard},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {6},
pages = {1558--1590},
year = {2012},
url = {https://doi.org/10.1137/120865094},
doi = {10.1137/120865094},
timestamp = {Wed, 14 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/FeldmanGRW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/RaghavendraST12,
author = {Prasad Raghavendra and
David Steurer and
Madhur Tulsiani},
title = {Reductions between Expansion Problems},
booktitle = {Proceedings of the 27th Conference on Computational Complexity, {CCC}
2012, Porto, Portugal, June 26-29, 2012},
pages = {64--73},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/CCC.2012.43},
doi = {10.1109/CCC.2012.43},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/RaghavendraST12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BarakGHMRS12,
author = {Boaz Barak and
Parikshit Gopalan and
Johan H{\aa}stad and
Raghu Meka and
Prasad Raghavendra and
David Steurer},
title = {Making the Long Code Shorter},
booktitle = {53rd Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2012, New Brunswick, NJ, USA, October 20-23, 2012},
pages = {370--379},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/FOCS.2012.83},
doi = {10.1109/FOCS.2012.83},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BarakGHMRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RaghavendraT12,
author = {Prasad Raghavendra and
Ning Tan},
editor = {Yuval Rabani},
title = {Approximating CSPs with global cardinality constraints using {SDP}
hierarchies},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {373--387},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.33},
doi = {10.1137/1.9781611973099.33},
timestamp = {Tue, 07 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/RaghavendraT12.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 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/GuruswamiRSW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BhattacharyyaGRS12,
author = {Arnab Bhattacharyya and
Elena Grigorescu and
Prasad Raghavendra and
Asaf Shapira},
editor = {Yuval Rabani},
title = {Testing odd-cycle-freeness in Boolean functions},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1140--1149},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.90},
doi = {10.1137/1.9781611973099.90},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BhattacharyyaGRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LouisRTV12,
author = {Anand Louis and
Prasad Raghavendra and
Prasad Tetali and
Santosh S. Vempala},
editor = {Howard J. Karloff and
Toniann Pitassi},
title = {Many sparse cuts via higher eigenvalues},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
pages = {1131--1140},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2213977.2214079},
doi = {10.1145/2213977.2214079},
timestamp = {Thu, 24 Oct 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/LouisRTV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1207-6371,
author = {Arindam Khan and
Prasad Raghavendra and
Prasad Tetali and
L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
title = {On Mimicking Networks Representing Minimum Terminal Cuts},
journal = {CoRR},
volume = {abs/1207.6371},
year = {2012},
url = {http://arxiv.org/abs/1207.6371},
eprinttype = {arXiv},
eprint = {1207.6371},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1207-6371.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/AzarFGMR11,
author = {Yossi Azar and
Uriel Feige and
Iftah Gamzu and
Thomas Moscibroda and
Prasad Raghavendra},
title = {Buffer Management for Colored Packets with Deadlines},
journal = {Theory Comput. Syst.},
volume = {49},
number = {4},
pages = {738--756},
year = {2011},
url = {https://doi.org/10.1007/s00224-011-9346-3},
doi = {10.1007/S00224-011-9346-3},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/AzarFGMR11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GuruswamiHMRC11,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Rajsekar Manokaran and
Prasad Raghavendra and
Moses Charikar},
title = {Beating the Random Ordering Is Hard: Every Ordering {CSP} Is Approximation
Resistant},
journal = {{SIAM} J. Comput.},
volume = {40},
number = {3},
pages = {878--914},
year = {2011},
url = {https://doi.org/10.1137/090756144},
doi = {10.1137/090756144},
timestamp = {Sun, 12 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/GuruswamiHMRC11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GopalanGR11,
author = {Parikshit Gopalan and
Venkatesan Guruswami and
Prasad Raghavendra},
title = {List Decoding Tensor Products and Interleaved Codes},
journal = {{SIAM} J. Comput.},
volume = {40},
number = {5},
pages = {1432--1462},
year = {2011},
url = {https://doi.org/10.1137/090778274},
doi = {10.1137/090778274},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GopalanGR11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/LouisRTV11,
author = {Anand Louis and
Prasad Raghavendra and
Prasad Tetali and
Santosh S. Vempala},
editor = {Leslie Ann Goldberg and
Klaus Jansen and
R. Ravi and
Jos{\'{e}} D. P. Rolim},
title = {Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues
and Partitions},
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 = {315--326},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22935-0\_27},
doi = {10.1007/978-3-642-22935-0\_27},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/LouisRTV11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BarakRS11,
author = {Boaz Barak and
Prasad Raghavendra and
David Steurer},
editor = {Rafail Ostrovsky},
title = {Rounding Semidefinite Programming Hierarchies via Global Correlation},
booktitle = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, {FOCS}
2011, Palm Springs, CA, USA, October 22-25, 2011},
pages = {472--481},
publisher = {{IEEE} Computer Society},
year = {2011},
url = {https://doi.org/10.1109/FOCS.2011.95},
doi = {10.1109/FOCS.2011.95},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BarakRS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/GuruswamiMRSZ11,
author = {Venkatesan Guruswami and
Yury Makarychev and
Prasad Raghavendra and
David Steurer and
Yuan Zhou},
editor = {Bernard Chazelle},
title = {Finding Almost-Perfect Graph Bisections},
booktitle = {Innovations in Computer Science - {ICS} 2011, Tsinghua University,
Beijing, China, January 7-9, 2011. Proceedings},
pages = {321--337},
publisher = {Tsinghua University Press},
year = {2011},
url = {http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/11.html},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/GuruswamiMRSZ11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/Raghavendra11,
author = {Prasad Raghavendra},
editor = {Filip Murlak and
Piotr Sankowski},
title = {Generic Techniques to Round {SDP} Relaxations},
booktitle = {Mathematical Foundations of Computer Science 2011 - 36th International
Symposium, {MFCS} 2011, Warsaw, Poland, August 22-26, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6907},
pages = {34},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22993-0\_5},
doi = {10.1007/978-3-642-22993-0\_5},
timestamp = {Tue, 14 May 2019 10:00:37 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/Raghavendra11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1104-4680,
author = {Boaz Barak and
Prasad Raghavendra and
David Steurer},
title = {Rounding Semidefinite Programming Hierarchies via Global Correlation},
journal = {CoRR},
volume = {abs/1104.4680},
year = {2011},
url = {http://arxiv.org/abs/1104.4680},
eprinttype = {arXiv},
eprint = {1104.4680},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1104-4680.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1105-1325,
author = {Arnab Bhattacharyya and
Elena Grigorescu and
Prasad Raghavendra and
Asaf Shapira},
title = {Testing Odd-Cycle-Freeness in Boolean Functions},
journal = {CoRR},
volume = {abs/1105.1325},
year = {2011},
url = {http://arxiv.org/abs/1105.1325},
eprinttype = {arXiv},
eprint = {1105.1325},
timestamp = {Thu, 07 Feb 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1105-1325.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1110-1064,
author = {Prasad Raghavendra and
Ning Tan},
title = {Approximating CSPs with Global Cardinality Constraints Using {SDP}
Hierarchies},
journal = {CoRR},
volume = {abs/1110.1064},
year = {2011},
url = {http://arxiv.org/abs/1110.1064},
eprinttype = {arXiv},
eprint = {1110.1064},
timestamp = {Tue, 07 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1110-1064.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1111-0405,
author = {Boaz Barak and
Parikshit Gopalan and
Johan H{\aa}stad and
Raghu Meka and
Prasad Raghavendra and
David Steurer},
title = {Making the long code shorter, with applications to the Unique Games
Conjecture},
journal = {CoRR},
volume = {abs/1111.0405},
year = {2011},
url = {http://arxiv.org/abs/1111.0405},
eprinttype = {arXiv},
eprint = {1111.0405},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1111-0405.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1111-0965,
author = {Anand Louis and
Prasad Raghavendra and
Prasad Tetali and
Santosh S. Vempala},
title = {Many Sparse Cuts via Higher Eigenvalues},
journal = {CoRR},
volume = {abs/1111.0965},
year = {2011},
url = {http://arxiv.org/abs/1111.0965},
eprinttype = {arXiv},
eprint = {1111.0965},
timestamp = {Thu, 24 Oct 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1111-0965.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakGHMRS11,
author = {Boaz Barak and
Parikshit Gopalan and
Johan H{\aa}stad and
Raghu Meka and
Prasad Raghavendra and
David Steurer},
title = {Making the long code shorter, with applications to the Unique Games
Conjecture},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-142}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/142},
eprinttype = {ECCC},
eprint = {TR11-142},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakGHMRS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakRS11,
author = {Boaz Barak and
Prasad Raghavendra and
David Steurer},
title = {Rounding Semidefinite Programming Hierarchies via Global Correlation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-065}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/065},
eprinttype = {ECCC},
eprint = {TR11-065},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakRS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhattacharyyaGRS11,
author = {Arnab Bhattacharyya and
Elena Grigorescu and
Prasad Raghavendra and
Asaf Shapira},
title = {Testing Odd-Cycle-Freeness in Boolean Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-075}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/075},
eprinttype = {ECCC},
eprint = {TR11-075},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhattacharyyaGRS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiHMRC11,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Rajsekar Manokaran and
Prasad Raghavendra and
Moses Charikar},
title = {Beating the Random Ordering is Hard: Every ordering {CSP} is approximation
resistant},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-027}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/027},
eprinttype = {ECCC},
eprint = {TR11-027},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiHMRC11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/LeeR10,
author = {James R. Lee and
Prasad Raghavendra},
title = {Coarse Differentiation and Multi-flows in Planar Graphs},
journal = {Discret. Comput. Geom.},
volume = {43},
number = {2},
pages = {346--362},
year = {2010},
url = {https://doi.org/10.1007/s00454-009-9172-4},
doi = {10.1007/S00454-009-9172-4},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dcg/LeeR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ChlamtacKR10,
author = {Eden Chlamtac and
Robert Krauthgamer and
Prasad Raghavendra},
editor = {Maria J. Serna and
Ronen Shaltiel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim},
title = {Approximating Sparsest Cut in Graphs of Bounded Treewidth},
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 = {124--137},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-15369-3\_10},
doi = {10.1007/978-3-642-15369-3\_10},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/ChlamtacKR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DiakonikolasHKMRST10,
author = {Ilias Diakonikolas and
Prahladh Harsha and
Adam R. Klivans and
Raghu Meka and
Prasad Raghavendra and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Leonard J. Schulman},
title = {Bounding the average sensitivity and noise sensitivity of polynomial
threshold functions},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {533--542},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806763},
doi = {10.1145/1806689.1806763},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DiakonikolasHKMRST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RaghavendraST10,
author = {Prasad Raghavendra and
David Steurer and
Prasad Tetali},
editor = {Leonard J. Schulman},
title = {Approximations for the isoperimetric and spectral profile of graphs
and related parameters},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {631--640},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806776},
doi = {10.1145/1806689.1806776},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/RaghavendraST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RaghavendraS10,
author = {Prasad Raghavendra and
David Steurer},
editor = {Leonard J. Schulman},
title = {Graph expansion and the unique games conjecture},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {755--764},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806792},
doi = {10.1145/1806689.1806792},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/RaghavendraS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1006-3970,
author = {Eden Chlamtac and
Robert Krauthgamer and
Prasad Raghavendra},
title = {Approximating Sparsest Cut in Graphs of Bounded Treewidth},
journal = {CoRR},
volume = {abs/1006.3970},
year = {2010},
url = {http://arxiv.org/abs/1006.3970},
eprinttype = {arXiv},
eprint = {1006.3970},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1006-3970.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1011-2586,
author = {Prasad Raghavendra and
David Steurer and
Madhur Tulsiani},
title = {Reductions Between Expansion Problems},
journal = {CoRR},
volume = {abs/1011.2586},
year = {2010},
url = {http://arxiv.org/abs/1011.2586},
eprinttype = {arXiv},
eprint = {1011.2586},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1011-2586.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1012-0729,
author = {Vitaly Feldman and
Venkatesan Guruswami and
Prasad Raghavendra and
Yi Wu},
title = {Agnostic Learning of Monomials by Halfspaces is Hard},
journal = {CoRR},
volume = {abs/1012.0729},
year = {2010},
url = {http://arxiv.org/abs/1012.0729},
eprinttype = {arXiv},
eprint = {1012.0729},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1012-0729.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FeldmanGRW10,
author = {Vitaly Feldman and
Venkatesan Guruswami and
Prasad Raghavendra and
Yi Wu},
title = {Agnostic Learning of Monomials by Halfspaces is Hard},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-185}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/185},
eprinttype = {ECCC},
eprint = {TR10-185},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FeldmanGRW10.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}
}
@article{DBLP:journals/eccc/RaghavendraST10,
author = {Prasad Raghavendra and
David Steurer and
Madhur Tulsiani},
title = {Reductions Between Expansion Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-172}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/172},
eprinttype = {ECCC},
eprint = {TR10-172},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/RaghavendraST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ijact/PatraCRSR09,
author = {Arpita Patra and
Ashish Choudhary and
C. Pandu Rangan and
Kannan Srinathan and
Prasad Raghavendra},
title = {Perfectly reliable and secure message transmission tolerating mobile
adversary},
journal = {Int. J. Appl. Cryptogr.},
volume = {1},
number = {3},
pages = {200--224},
year = {2009},
url = {https://doi.org/10.1504/IJACT.2009.023467},
doi = {10.1504/IJACT.2009.023467},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ijact/PatraCRSR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GuruswamiR09,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
title = {Hardness of Learning Halfspaces with Noise},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {2},
pages = {742--765},
year = {2009},
url = {https://doi.org/10.1137/070685798},
doi = {10.1137/070685798},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GuruswamiR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/GuruswamiR09,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
title = {Hardness of Solving Sparse Overdetermined Linear Systems: {A} 3-Query
{PCP} over Integers},
journal = {{ACM} Trans. Comput. Theory},
volume = {1},
number = {2},
pages = {6:1--6:20},
year = {2009},
url = {https://doi.org/10.1145/1595391.1595393},
doi = {10.1145/1595391.1595393},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/GuruswamiR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/JayramKR09,
author = {T. S. Jayram and
Swastik Kopparty and
Prasad Raghavendra},
title = {On the Communication Complexity of Read-Once AC{\^{}}0 Formulae},
booktitle = {Proceedings of the 24th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2009, Paris, France, 15-18 July 2009},
pages = {329--340},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/CCC.2009.39},
doi = {10.1109/CCC.2009.39},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/JayramKR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FeldmanGRW09,
author = {Vitaly Feldman and
Venkatesan Guruswami and
Prasad Raghavendra and
Yi Wu},
title = {Agnostic Learning of Monomials by Halfspaces Is Hard},
booktitle = {50th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2009, October 25-27, 2009, Atlanta, Georgia, {USA}},
pages = {385--394},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/FOCS.2009.26},
doi = {10.1109/FOCS.2009.26},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FeldmanGRW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RaghavendraS09,
author = {Prasad Raghavendra and
David Steurer},
title = {Integrality Gaps for Strong {SDP} Relaxations of {UNIQUE} {GAMES}},
booktitle = {50th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2009, October 25-27, 2009, Atlanta, Georgia, {USA}},
pages = {575--585},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/FOCS.2009.73},
doi = {10.1109/FOCS.2009.73},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/RaghavendraS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RaghavendraS09a,
author = {Prasad Raghavendra and
David Steurer},
title = {How to Round Any {CSP}},
booktitle = {50th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2009, October 25-27, 2009, Atlanta, Georgia, {USA}},
pages = {586--594},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/FOCS.2009.74},
doi = {10.1109/FOCS.2009.74},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/RaghavendraS09a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RaghavendraS09,
author = {Prasad Raghavendra and
David Steurer},
editor = {Claire Mathieu},
title = {Towards computing the Grothendieck constant},
booktitle = {Proceedings of the Twentieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2009, New York, NY, USA, January 4-6, 2009},
pages = {525--534},
publisher = {{SIAM}},
year = {2009},
url = {https://doi.org/10.1137/1.9781611973068.58},
doi = {10.1137/1.9781611973068.58},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/RaghavendraS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/spaa/AzarFGMR09,
author = {Yossi Azar and
Uriel Feige and
Iftah Gamzu and
Thomas Moscibroda and
Prasad Raghavendra},
editor = {Friedhelm Meyer auf der Heide and
Michael A. Bender},
title = {Buffer management for colored packets with deadlines},
booktitle = {{SPAA} 2009: Proceedings of the 21st Annual {ACM} Symposium on Parallelism
in Algorithms and Architectures, Calgary, Alberta, Canada, August
11-13, 2009},
pages = {319--327},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1583991.1584068},
doi = {10.1145/1583991.1584068},
timestamp = {Wed, 21 Nov 2018 11:15:22 +0100},
biburl = {https://dblp.org/rec/conf/spaa/AzarFGMR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GopalanGR09,
author = {Parikshit Gopalan and
Venkatesan Guruswami and
Prasad Raghavendra},
editor = {Michael Mitzenmacher},
title = {List decoding tensor products and interleaved codes},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {13--22},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536419},
doi = {10.1145/1536414.1536419},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GopalanGR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0909-5011,
author = {Ilias Diakonikolas and
Prasad Raghavendra and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Average sensitivity and noise sensitivity of polynomial threshold
functions},
journal = {CoRR},
volume = {abs/0909.5011},
year = {2009},
url = {http://arxiv.org/abs/0909.5011},
eprinttype = {arXiv},
eprint = {0909.5011},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0909-5011.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiR09,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
title = {Hardness of Solving Sparse Overdetermined Linear Systems: {A} 3-Query
{PCP} over Integers},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-020}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/020},
eprinttype = {ECCC},
eprint = {TR09-020},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/GuruswamiR08,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
editor = {Ashish Goel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Ronitt Rubinfeld},
title = {Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms
and Unique-Games Hardness},
booktitle = {Approximation, Randomization and Combinatorial Optimization. Algorithms
and Techniques, 11th International Workshop, {APPROX} 2008, and 12th
International Workshop, {RANDOM} 2008, Boston, MA, USA, August 25-27,
2008. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5171},
pages = {77--90},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-85363-3\_7},
doi = {10.1007/978-3-540-85363-3\_7},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/GuruswamiR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuruswamiMR08,
author = {Venkatesan Guruswami and
Rajsekar Manokaran and
Prasad Raghavendra},
title = {Beating the Random Ordering is Hard: Inapproximability of Maximum
Acyclic Subgraph},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {573--582},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.51},
doi = {10.1109/FOCS.2008.51},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GuruswamiMR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ManokaranNRS08,
author = {Rajsekar Manokaran and
Joseph Naor and
Prasad Raghavendra and
Roy Schwartz},
editor = {Cynthia Dwork},
title = {Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric
labeling},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {11--20},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374379},
doi = {10.1145/1374376.1374379},
timestamp = {Wed, 23 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ManokaranNRS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Raghavendra08,
author = {Prasad Raghavendra},
editor = {Cynthia Dwork},
title = {Optimal algorithms and inapproximability results for every CSP?},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {245--254},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374414},
doi = {10.1145/1374376.1374414},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Raghavendra08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0811-4395,
author = {Parikshit Gopalan and
Venkatesan Guruswami and
Prasad Raghavendra},
title = {List Decoding Tensor Products and Interleaved Codes},
journal = {CoRR},
volume = {abs/0811.4395},
year = {2008},
url = {http://arxiv.org/abs/0811.4395},
eprinttype = {arXiv},
eprint = {0811.4395},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0811-4395.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GopalanGRR08,
author = {Parikshit Gopalan and
Venkatesan Guruswami and
Prasad Raghavendra},
title = {List Decoding Tensor Products and Interleaved Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR08-105}},
year = {2008},
url = {https://eccc.weizmann.ac.il/eccc-reports/2008/TR08-105/index.html},
eprinttype = {ECCC},
eprint = {TR08-105},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GopalanGRR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiR08,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
title = {Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms
and Unique-Games hardness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR08-008}},
year = {2008},
url = {https://eccc.weizmann.ac.il/eccc-reports/2008/TR08-008/index.html},
eprinttype = {ECCC},
eprint = {TR08-008},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LeeR08,
author = {James R. Lee and
Prasad Raghavendra},
title = {Coarse Differentiation and Multi-flows in Planar Graphs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR08-060}},
year = {2008},
url = {https://eccc.weizmann.ac.il/eccc-reports/2008/TR08-060/index.html},
eprinttype = {ECCC},
eprint = {TR08-060},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LeeR08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/acisp/SrinathanRC07,
author = {Kannan Srinathan and
Prasad Raghavendra and
C. Pandu Rangan},
editor = {Josef Pieprzyk and
Hossein Ghodosi and
Ed Dawson},
title = {On Proactive Perfectly Secure Message Transmission},
booktitle = {Information Security and Privacy, 12th Australasian Conference, {ACISP}
2007, Townsville, Australia, July 2-4, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4586},
pages = {461--473},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-73458-1\_33},
doi = {10.1007/978-3-540-73458-1\_33},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/acisp/SrinathanRC07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ChenENRRS07,
author = {Ning Chen and
Roee Engelberg and
C. Thach Nguyen and
Prasad Raghavendra and
Atri Rudra and
Gyanit Singh},
editor = {Moses Charikar and
Klaus Jansen and
Omer Reingold and
Jos{\'{e}} D. P. Rolim},
title = {Improved Approximation Algorithms for the Spanning Star Forest Problem},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 10th International Workshop, {APPROX} 2007, and 11th
International Workshop, {RANDOM} 2007, Princeton, NJ, USA, August
20-22, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4627},
pages = {44--58},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74208-1\_4},
doi = {10.1007/978-3-540-74208-1\_4},
timestamp = {Sat, 30 Sep 2023 09:34:32 +0200},
biburl = {https://dblp.org/rec/conf/approx/ChenENRRS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/LeeR07,
author = {James R. Lee and
Prasad Raghavendra},
editor = {Moses Charikar and
Klaus Jansen and
Omer Reingold and
Jos{\'{e}} D. P. Rolim},
title = {Coarse Differentiation and Multi-flows in Planar Graphs},
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 = {228--241},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74208-1\_17},
doi = {10.1007/978-3-540-74208-1\_17},
timestamp = {Tue, 23 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/LeeR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuruswamiR07,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
editor = {David S. Johnson and
Uriel Feige},
title = {A 3-query {PCP} over integers},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {198--206},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250819},
doi = {10.1145/1250790.1250819},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GuruswamiR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Raghavendra07,
author = {Prasad Raghavendra},
title = {A Note on Yekhanin's Locally Decodable Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-016}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-016/index.html},
eprinttype = {ECCC},
eprint = {TR07-016},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Raghavendra07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuruswamiR06,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
title = {Hardness of Learning Halfspaces with Noise},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages = {543--552},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/FOCS.2006.33},
doi = {10.1109/FOCS.2006.33},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GuruswamiR06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiR06,
author = {Venkatesan Guruswami and
Prasad Raghavendra},
title = {Hardness of Learning Halfspaces with Noise},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-061}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-061/index.html},
eprinttype = {ECCC},
eprint = {TR06-061},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiR06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
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-08-05 21:23 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:
