Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Ryan O'Donnell
@article{DBLP:journals/theoretics/BadescuO24,
author = {Costin Badescu and
Ryan O'Donnell},
title = {Improved quantum data analysis},
journal = {TheoretiCS},
volume = {3},
year = {2024},
url = {https://doi.org/10.46298/theoretics.24.7},
doi = {10.46298/THEORETICS.24.7},
timestamp = {Tue, 02 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/theoretics/BadescuO24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HaahKOT23,
author = {Jeongwan Haah and
Robin Kothari and
Ryan O'Donnell and
Ewin Tang},
title = {Query-optimal estimation of unitary channels in diamond distance},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {363--390},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00028},
doi = {10.1109/FOCS57990.2023.00028},
timestamp = {Tue, 02 Jan 2024 14:56:14 +0100},
biburl = {https://dblp.org/rec/conf/focs/HaahKOT23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ODonnellS023,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Pedro Paredes},
title = {Explicit orthogonal and unitary designs},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1240--1260},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00073},
doi = {10.1109/FOCS57990.2023.00073},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ODonnellS023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KothariO23,
author = {Robin Kothari and
Ryan O'Donnell},
editor = {Nikhil Bansal and
Viswanath Nagarajan},
title = {Mean estimation when you have the source code; or, quantum Monte Carlo
methods},
booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2023, Florence, Italy, January 22-25, 2023},
pages = {1186--1215},
publisher = {{SIAM}},
year = {2023},
url = {https://doi.org/10.1137/1.9781611977554.ch44},
doi = {10.1137/1.9781611977554.CH44},
timestamp = {Fri, 17 Feb 2023 09:28:57 +0100},
biburl = {https://dblp.org/rec/conf/soda/KothariO23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2302-14066,
author = {Jeongwan Haah and
Robin Kothari and
Ryan O'Donnell and
Ewin Tang},
title = {Query-optimal estimation of unitary channels in diamond distance},
journal = {CoRR},
volume = {abs/2302.14066},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2302.14066},
doi = {10.48550/ARXIV.2302.14066},
eprinttype = {arXiv},
eprint = {2302.14066},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2302-14066.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2305-18519,
author = {Steven T. Flammia and
Ryan O'Donnell},
title = {Quantum chi-squared tomography and mutual information testing},
journal = {CoRR},
volume = {abs/2305.18519},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2305.18519},
doi = {10.48550/ARXIV.2305.18519},
eprinttype = {arXiv},
eprint = {2305.18519},
timestamp = {Tue, 06 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2305-18519.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-13597,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Pedro Paredes},
title = {Explicit orthogonal and unitary designs},
journal = {CoRR},
volume = {abs/2310.13597},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.13597},
doi = {10.48550/ARXIV.2310.13597},
eprinttype = {arXiv},
eprint = {2310.13597},
timestamp = {Fri, 27 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-13597.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/ODonnellST22,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Fooling Polytopes},
journal = {J. {ACM}},
volume = {69},
number = {2},
pages = {9:1--9:37},
year = {2022},
url = {https://doi.org/10.1145/3460532},
doi = {10.1145/3460532},
timestamp = {Wed, 13 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/ODonnellST22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/MohantyOP22,
author = {Sidhanth Mohanty and
Ryan O'Donnell and
Pedro Paredes},
title = {Explicit Near-Ramanujan Graphs of Every Degree},
journal = {{SIAM} J. Comput.},
volume = {51},
number = {3},
pages = {20--1},
year = {2022},
url = {https://doi.org/10.1137/20m1342112},
doi = {10.1137/20M1342112},
timestamp = {Fri, 12 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/MohantyOP22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnellP22,
author = {Ryan O'Donnell and
Kevin Pratt},
editor = {Shachar Lovett},
title = {High-Dimensional Expanders from Chevalley Groups},
booktitle = {37th Computational Complexity Conference, {CCC} 2022, July 20-23,
2022, Philadelphia, PA, {USA}},
series = {LIPIcs},
volume = {234},
pages = {18:1--18:26},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.CCC.2022.18},
doi = {10.4230/LIPICS.CCC.2022.18},
timestamp = {Tue, 12 Jul 2022 17:25:23 +0200},
biburl = {https://dblp.org/rec/conf/coco/ODonnellP22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/ChenLO22,
author = {Sitan Chen and
Jerry Li and
Ryan O'Donnell},
editor = {Po{-}Ling Loh and
Maxim Raginsky},
title = {Toward Instance-Optimal State Certification With Incoherent Measurements},
booktitle = {Conference on Learning Theory, 2-5 July 2022, London, {UK}},
series = {Proceedings of Machine Learning Research},
volume = {178},
pages = {2541--2596},
publisher = {{PMLR}},
year = {2022},
url = {https://proceedings.mlr.press/v178/chen22b.html},
timestamp = {Tue, 12 Jul 2022 17:36:51 +0200},
biburl = {https://dblp.org/rec/conf/colt/ChenLO22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/MusipatlaOSW22,
author = {Amulya Musipatla and
Ryan O'Donnell and
Tselil Schramm and
Xinyu Wu},
editor = {Mikolaj Bojanczyk and
Emanuela Merelli and
David P. Woodruff},
title = {The {SDP} Value of Random 2CSPs},
booktitle = {49th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2022, July 4-8, 2022, Paris, France},
series = {LIPIcs},
volume = {229},
pages = {97:1--97:19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2022.97},
doi = {10.4230/LIPICS.ICALP.2022.97},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icalp/MusipatlaOSW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/JeronimoMO0T22,
author = {Fernando Granha Jeronimo and
Tushant Mittal and
Ryan O'Donnell and
Pedro Paredes and
Madhur Tulsiani},
editor = {Mark Braverman},
title = {Explicit Abelian Lifts and Quantum {LDPC} Codes},
booktitle = {13th Innovations in Theoretical Computer Science Conference, {ITCS}
2022, January 31 - February 3, 2022, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {215},
pages = {88:1--88:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2022.88},
doi = {10.4230/LIPICS.ITCS.2022.88},
timestamp = {Wed, 26 Jan 2022 14:33:51 +0100},
biburl = {https://dblp.org/rec/conf/innovations/JeronimoMO0T22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sosa/ODonnellV22,
author = {Ryan O'Donnell and
Ramgopal Venkateswaran},
editor = {Karl Bringmann and
Timothy M. Chan},
title = {The Quantum Union Bound made easy},
booktitle = {5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual
Conference, January 10-11, 2022},
pages = {314--320},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977066.25},
doi = {10.1137/1.9781611977066.25},
timestamp = {Sat, 19 Aug 2023 18:10:48 +0200},
biburl = {https://dblp.org/rec/conf/sosa/ODonnellV22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HastingsO22,
author = {Matthew B. Hastings and
Ryan O'Donnell},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {Optimizing strongly interacting fermionic Hamiltonians},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {776--789},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3519960},
doi = {10.1145/3519935.3519960},
timestamp = {Tue, 27 Dec 2022 09:06:31 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HastingsO22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2203-03705,
author = {Ryan O'Donnell and
Kevin Pratt},
title = {High-Dimensional Expanders from Chevalley Groups},
journal = {CoRR},
volume = {abs/2203.03705},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2203.03705},
doi = {10.48550/ARXIV.2203.03705},
eprinttype = {arXiv},
eprint = {2203.03705},
timestamp = {Wed, 16 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2203-03705.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2208-07544,
author = {Robin Kothari and
Ryan O'Donnell},
title = {Mean estimation when you have the source code; or, quantum Monte Carlo
methods},
journal = {CoRR},
volume = {abs/2208.07544},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2208.07544},
doi = {10.48550/ARXIV.2208.07544},
eprinttype = {arXiv},
eprint = {2208.07544},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2208-07544.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/quantum/FlammiaO21,
author = {Steven T. Flammia and
Ryan O'Donnell},
title = {Pauli error estimation via Population Recovery},
journal = {Quantum},
volume = {5},
pages = {549},
year = {2021},
url = {https://doi.org/10.22331/q-2021-09-23-549},
doi = {10.22331/Q-2021-09-23-549},
timestamp = {Mon, 26 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/quantum/FlammiaO21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ODonnellS21,
author = {Ryan O'Donnell and
Tselil Schramm},
title = {Sherali-Adams Strikes Back},
journal = {Theory Comput.},
volume = {17},
pages = {1--30},
year = {2021},
url = {https://theoryofcomputing.org/articles/v017a009/},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ODonnellS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/DeOS21,
author = {Anindya De and
Ryan O'Donnell and
Rocco A. Servedio},
editor = {Mikhail Belkin and
Samory Kpotufe},
title = {Learning sparse mixtures of permutations from noisy information},
booktitle = {Conference on Learning Theory, {COLT} 2021, 15-19 August 2021, Boulder,
Colorado, {USA}},
series = {Proceedings of Machine Learning Research},
volume = {134},
pages = {1429--1466},
publisher = {{PMLR}},
year = {2021},
url = {http://proceedings.mlr.press/v134/de21b.html},
timestamp = {Wed, 25 Aug 2021 17:11:16 +0200},
biburl = {https://dblp.org/rec/conf/colt/DeOS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/VenkateswaranO21,
author = {Ramgopal Venkateswaran and
Ryan O'Donnell},
editor = {Markus Bl{\"{a}}ser and
Benjamin Monmege},
title = {Quantum Approximate Counting with Nonadaptive Grover Iterations},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science,
{STACS} 2021, March 16-19, 2021, Saarbr{\"{u}}cken, Germany (Virtual
Conference)},
series = {LIPIcs},
volume = {187},
pages = {59:1--59:12},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.STACS.2021.59},
doi = {10.4230/LIPICS.STACS.2021.59},
timestamp = {Thu, 11 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stacs/VenkateswaranO21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HastingsHO21,
author = {Matthew B. Hastings and
Jeongwan Haah and
Ryan O'Donnell},
editor = {Samir Khuller and
Virginia Vassilevska Williams},
title = {Fiber bundle codes: breaking the \emph{n}\({}^{\mbox{1/2}}\) polylog(\emph{n})
barrier for Quantum {LDPC} codes},
booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Virtual Event, Italy, June 21-25, 2021},
pages = {1276--1288},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3406325.3451005},
doi = {10.1145/3406325.3451005},
timestamp = {Tue, 22 Jun 2021 19:47:11 +0200},
biburl = {https://dblp.org/rec/conf/stoc/HastingsHO21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BadescuO21,
author = {Costin Badescu and
Ryan O'Donnell},
editor = {Samir Khuller and
Virginia Vassilevska Williams},
title = {Improved Quantum data analysis},
booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Virtual Event, Italy, June 21-25, 2021},
pages = {1398--1411},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3406325.3451109},
doi = {10.1145/3406325.3451109},
timestamp = {Tue, 22 Jun 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BadescuO21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tqc/FlammiaO21,
author = {Steven T. Flammia and
Ryan O'Donnell},
editor = {Min{-}Hsiu Hsieh},
title = {Pauli Error Estimation via Population Recovery},
booktitle = {16th Conference on the Theory of Quantum Computation, Communication
and Cryptography, {TQC} 2021, July 5-8, 2021, Virtual Conference},
series = {LIPIcs},
volume = {197},
pages = {8:1--8:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.TQC.2021.8},
doi = {10.4230/LIPICS.TQC.2021.8},
timestamp = {Tue, 22 Jun 2021 15:41:08 +0200},
biburl = {https://dblp.org/rec/conf/tqc/FlammiaO21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2102-13098,
author = {Sitan Chen and
Jerry Li and
Ryan O'Donnell},
title = {Toward Instance-Optimal State Certification With Incoherent Measurements},
journal = {CoRR},
volume = {abs/2102.13098},
year = {2021},
url = {https://arxiv.org/abs/2102.13098},
eprinttype = {arXiv},
eprint = {2102.13098},
timestamp = {Tue, 02 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2102-13098.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2103-07809,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Li{-}Yang Tan and
Daniel Kane},
title = {Fooling Gaussian PTFs via Local Hyperconcentration},
journal = {CoRR},
volume = {abs/2103.07809},
year = {2021},
url = {https://arxiv.org/abs/2103.07809},
eprinttype = {arXiv},
eprint = {2103.07809},
timestamp = {Tue, 09 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2103-07809.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2105-10386,
author = {Ryan O'Donnell},
title = {Analysis of Boolean Functions},
journal = {CoRR},
volume = {abs/2105.10386},
year = {2021},
url = {https://arxiv.org/abs/2105.10386},
eprinttype = {arXiv},
eprint = {2105.10386},
timestamp = {Mon, 31 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2105-10386.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2108-01038,
author = {Amulya Musipatla and
Ryan O'Donnell and
Tselil Schramm and
Xinyu Wu},
title = {The {SDP} value of random 2CSPs},
journal = {CoRR},
volume = {abs/2108.01038},
year = {2021},
url = {https://arxiv.org/abs/2108.01038},
eprinttype = {arXiv},
eprint = {2108.01038},
timestamp = {Thu, 05 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2108-01038.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-10701,
author = {Matthew B. Hastings and
Ryan O'Donnell},
title = {Optimizing Strongly Interacting Fermionic Hamiltonians},
journal = {CoRR},
volume = {abs/2110.10701},
year = {2021},
url = {https://arxiv.org/abs/2110.10701},
eprinttype = {arXiv},
eprint = {2110.10701},
timestamp = {Fri, 29 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-10701.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-01647,
author = {Fernando Granha Jeronimo and
Tushant Mittal and
Ryan O'Donnell and
Pedro Paredes and
Madhur Tulsiani},
title = {Explicit Abelian Lifts and Quantum {LDPC} Codes},
journal = {CoRR},
volume = {abs/2112.01647},
year = {2021},
url = {https://arxiv.org/abs/2112.01647},
eprinttype = {arXiv},
eprint = {2112.01647},
timestamp = {Tue, 07 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-01647.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DeOS20,
author = {Anindya De and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Sharp Bounds for Population Recovery},
journal = {Theory Comput.},
volume = {16},
pages = {1--20},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a006},
doi = {10.4086/TOC.2020.V016A006},
timestamp = {Wed, 10 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/DeOS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/ODonnell20,
author = {Ryan O'Donnell},
title = {Editorial from the New Editor-in-Chief},
journal = {{ACM} Trans. Comput. Theory},
volume = {12},
number = {1},
pages = {1e:1},
year = {2020},
url = {https://doi.org/10.1145/3381517},
doi = {10.1145/3381517},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/ODonnell20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ODonnellW20,
author = {Ryan O'Donnell and
Xinyu Wu},
editor = {Sandy Irani},
title = {Explicit near-fully X-Ramanujan graphs},
booktitle = {61st {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2020, Durham, NC, USA, November 16-19, 2020},
pages = {1045--1056},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.1109/FOCS46700.2020.00101},
doi = {10.1109/FOCS46700.2020.00101},
timestamp = {Wed, 15 Dec 2021 10:49:16 +0100},
biburl = {https://dblp.org/rec/conf/focs/ODonnellW20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/BadescuO20,
author = {Costin Badescu and
Ryan O'Donnell},
editor = {Yoshiharu Kohayakawa and
Fl{\'{a}}vio Keidi Miyazawa},
title = {Lower Bounds for Testing Complete Positivity and Quantum Separability},
booktitle = {{LATIN} 2020: Theoretical Informatics - 14th Latin American Symposium,
S{\~{a}}o Paulo, Brazil, January 5-8, 2021, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {12118},
pages = {375--386},
publisher = {Springer},
year = {2020},
url = {https://doi.org/10.1007/978-3-030-61792-9\_30},
doi = {10.1007/978-3-030-61792-9\_30},
timestamp = {Thu, 03 Dec 2020 14:27:45 +0100},
biburl = {https://dblp.org/rec/conf/latin/BadescuO20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MohantyO20,
author = {Sidhanth Mohanty and
Ryan O'Donnell},
editor = {Shuchi Chawla},
title = {\emph{X}-Ramanujan graphs},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
pages = {1226--1243},
publisher = {{SIAM}},
year = {2020},
url = {https://doi.org/10.1137/1.9781611975994.75},
doi = {10.1137/1.9781611975994.75},
timestamp = {Thu, 15 Jul 2021 13:48:53 +0200},
biburl = {https://dblp.org/rec/conf/soda/MohantyO20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/MohantyO020,
author = {Sidhanth Mohanty and
Ryan O'Donnell and
Pedro Paredes},
editor = {Christophe Paul and
Markus Bl{\"{a}}ser},
title = {The {SDP} Value for Random Two-Eigenvalue CSPs},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science,
{STACS} 2020, March 10-13, 2020, Montpellier, France},
series = {LIPIcs},
volume = {154},
pages = {50:1--50:45},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.STACS.2020.50},
doi = {10.4230/LIPICS.STACS.2020.50},
timestamp = {Thu, 05 Mar 2020 10:56:55 +0100},
biburl = {https://dblp.org/rec/conf/stacs/MohantyO020.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MohantyO020,
author = {Sidhanth Mohanty and
Ryan O'Donnell and
Pedro Paredes},
editor = {Konstantin Makarychev and
Yury Makarychev and
Madhur Tulsiani and
Gautam Kamath and
Julia Chuzhoy},
title = {Explicit near-Ramanujan graphs of every degree},
booktitle = {Proceedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
pages = {510--523},
publisher = {{ACM}},
year = {2020},
url = {https://doi.org/10.1145/3357713.3384231},
doi = {10.1145/3357713.3384231},
timestamp = {Mon, 18 Dec 2023 07:33:37 +0100},
biburl = {https://dblp.org/rec/conf/stoc/MohantyO020.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellST20,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Konstantin Makarychev and
Yury Makarychev and
Madhur Tulsiani and
Gautam Kamath and
Julia Chuzhoy},
title = {Fooling Gaussian PTFs via local hyperconcentration},
booktitle = {Proceedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
pages = {1170--1183},
publisher = {{ACM}},
year = {2020},
url = {https://doi.org/10.1145/3357713.3384281},
doi = {10.1145/3357713.3384281},
timestamp = {Tue, 09 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellST20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2009-02595,
author = {Ryan O'Donnell and
Xinyu Wu},
title = {Explicit near-fully X-Ramanujan graphs},
journal = {CoRR},
volume = {abs/2009.02595},
year = {2020},
url = {https://arxiv.org/abs/2009.02595},
eprinttype = {arXiv},
eprint = {2009.02595},
timestamp = {Fri, 18 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2009-02595.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2009-03921,
author = {Matthew B. Hastings and
Jeongwan Haah and
Ryan O'Donnell},
title = {Fiber Bundle Codes: Breaking the N\({}^{\mbox{1/2}}\) polylog(N) Barrier
for Quantum {LDPC} Codes},
journal = {CoRR},
volume = {abs/2009.03921},
year = {2020},
url = {https://arxiv.org/abs/2009.03921},
eprinttype = {arXiv},
eprint = {2009.03921},
timestamp = {Fri, 18 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2009-03921.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2011-10908,
author = {Costin Badescu and
Ryan O'Donnell},
title = {Improved quantum data analysis},
journal = {CoRR},
volume = {abs/2011.10908},
year = {2020},
url = {https://doi.org/10.48550/arXiv.2011.10908},
doi = {10.48550/ARXIV.2011.10908},
eprinttype = {arXiv},
eprint = {2011.10908},
timestamp = {Fri, 07 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2011-10908.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnellS19,
author = {Ryan O'Donnell and
Tselil Schramm},
editor = {Amir Shpilka},
title = {Sherali - Adams Strikes Back},
booktitle = {34th Computational Complexity Conference, {CCC} 2019, July 18-20,
2019, New Brunswick, NJ, {USA}},
series = {LIPIcs},
volume = {137},
pages = {8:1--8:30},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.CCC.2019.8},
doi = {10.4230/LIPICS.CCC.2019.8},
timestamp = {Thu, 02 Feb 2023 13:27:04 +0100},
biburl = {https://dblp.org/rec/conf/coco/ODonnellS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/FilmusOW19,
author = {Yuval Filmus and
Ryan O'Donnell and
Xinyu Wu},
editor = {Avrim Blum},
title = {A Log-Sobolev Inequality for the Multislice, with Applications},
booktitle = {10th Innovations in Theoretical Computer Science Conference, {ITCS}
2019, January 10-12, 2019, San Diego, California, {USA}},
series = {LIPIcs},
volume = {124},
pages = {34:1--34:12},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2019.34},
doi = {10.4230/LIPICS.ITCS.2019.34},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/FilmusOW19.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/soda/DeshpandeMOSS19,
author = {Yash Deshpande and
Andrea Montanari and
Ryan O'Donnell and
Tselil Schramm and
Subhabrata Sen},
editor = {Timothy M. Chan},
title = {The threshold for SDP-refutation of random regular {NAE-3SAT}},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {2305--2321},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.140},
doi = {10.1137/1.9781611975482.140},
timestamp = {Thu, 15 Jul 2021 13:49:01 +0200},
biburl = {https://dblp.org/rec/conf/soda/DeshpandeMOSS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BadescuO019,
author = {Costin Badescu and
Ryan O'Donnell and
John Wright},
editor = {Moses Charikar and
Edith Cohen},
title = {Quantum state certification},
booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019},
pages = {503--514},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3313276.3316344},
doi = {10.1145/3313276.3316344},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BadescuO019.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellST19,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Moses Charikar and
Edith Cohen},
title = {Fooling polytopes},
booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019},
pages = {614--625},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3313276.3316321},
doi = {10.1145/3313276.3316321},
timestamp = {Sat, 22 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellST19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-03500,
author = {Sidhanth Mohanty and
Ryan O'Donnell},
title = {X-Ramanujan Graphs},
journal = {CoRR},
volume = {abs/1904.03500},
year = {2019},
url = {http://arxiv.org/abs/1904.03500},
eprinttype = {arXiv},
eprint = {1904.03500},
timestamp = {Fri, 26 Apr 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-03500.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1906-06732,
author = {Sidhanth Mohanty and
Ryan O'Donnell and
Pedro Paredes},
title = {The {SDP} value for random two-eigenvalue CSPs},
journal = {CoRR},
volume = {abs/1906.06732},
year = {2019},
url = {http://arxiv.org/abs/1906.06732},
eprinttype = {arXiv},
eprint = {1906.06732},
timestamp = {Mon, 04 Nov 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1906-06732.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1909-06988,
author = {Sidhanth Mohanty and
Ryan O'Donnell and
Pedro Paredes},
title = {Explicit near-Ramanujan graphs of every degree},
journal = {CoRR},
volume = {abs/1909.06988},
year = {2019},
url = {http://arxiv.org/abs/1909.06988},
eprinttype = {arXiv},
eprint = {1909.06988},
timestamp = {Mon, 04 Nov 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1909-06988.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LovettO18,
author = {Shachar Lovett and
Ryan O'Donnell},
title = {Special Issue: {CCC} 2017: Guest Editor's Foreword},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--2},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a002},
doi = {10.4086/TOC.2018.V014A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LovettO18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/ODonnellS18,
author = {Ryan O'Donnell and
A. C. Cem Say},
title = {The Weakness of {CTC} Qubits and the Power of Approximate Counting},
journal = {{ACM} Trans. Comput. Theory},
volume = {10},
number = {2},
pages = {5:1--5:22},
year = {2018},
url = {https://doi.org/10.1145/3196832},
doi = {10.1145/3196832},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/ODonnellS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ODonnellZ18,
author = {Ryan O'Donnell and
Yu Zhao},
editor = {Eric Blais and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
David Steurer},
title = {On Closeness to k-Wise Uniformity},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2018, August 20-22, 2018 - Princeton,
NJ, {USA}},
series = {LIPIcs},
volume = {116},
pages = {54:1--54:19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.54},
doi = {10.4230/LIPICS.APPROX-RANDOM.2018.54},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/ODonnellZ18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1804-05230,
author = {Yash Deshpande and
Andrea Montanari and
Ryan O'Donnell and
Tselil Schramm and
Subhabrata Sen},
title = {The threshold for SDP-refutation of random regular {NAE-3SAT}},
journal = {CoRR},
volume = {abs/1804.05230},
year = {2018},
url = {http://arxiv.org/abs/1804.05230},
eprinttype = {arXiv},
eprint = {1804.05230},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1804-05230.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1806-03569,
author = {Ryan O'Donnell and
Yu Zhao},
title = {On closeness to k-wise uniformity},
journal = {CoRR},
volume = {abs/1806.03569},
year = {2018},
url = {http://arxiv.org/abs/1806.03569},
eprinttype = {arXiv},
eprint = {1806.03569},
timestamp = {Wed, 26 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1806-03569.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1808-04035,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Fooling Polytopes},
journal = {CoRR},
volume = {abs/1808.04035},
year = {2018},
url = {http://arxiv.org/abs/1808.04035},
eprinttype = {arXiv},
eprint = {1808.04035},
timestamp = {Sun, 02 Sep 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1808-04035.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/corr/abs-1809-03546,
author = {Yuval Filmus and
Ryan O'Donnell and
Xinyu Wu},
title = {A log-Sobolev inequality for the multislice, with applications},
journal = {CoRR},
volume = {abs/1809.03546},
year = {2018},
url = {http://arxiv.org/abs/1809.03546},
eprinttype = {arXiv},
eprint = {1809.03546},
timestamp = {Fri, 05 Oct 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1809-03546.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1811-01216,
author = {Anindya De and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning sparse mixtures of rankings from noisy information},
journal = {CoRR},
volume = {abs/1811.01216},
year = {2018},
url = {http://arxiv.org/abs/1811.01216},
eprinttype = {arXiv},
eprint = {1811.01216},
timestamp = {Thu, 22 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1811-01216.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1812-09967,
author = {Ryan O'Donnell and
Tselil Schramm},
title = {Sherali-Adams Strikes Back},
journal = {CoRR},
volume = {abs/1812.09967},
year = {2018},
url = {http://arxiv.org/abs/1812.09967},
eprinttype = {arXiv},
eprint = {1812.09967},
timestamp = {Wed, 02 Jan 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1812-09967.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ODonnellST18,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Fooling Polytopes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-145}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/145},
eprinttype = {ECCC},
eprint = {TR18-145},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ODonnellST18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sigact/ODonnellW17,
author = {Ryan O'Donnell and
John Wright},
title = {Guest Column: {A} Primer on the Statistics of Longest Increasing Subsequences
and Quantum States (Shortened Version)},
journal = {{SIGACT} News},
volume = {48},
number = {3},
pages = {37--59},
year = {2017},
url = {https://doi.org/10.1145/3138860.3138869},
doi = {10.1145/3138860.3138869},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/sigact/ODonnellW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadHMOW17,
author = {Johan H{\aa}stad and
Sangxia Huang and
Rajsekar Manokaran and
Ryan O'Donnell and
John Wright},
title = {Improved NP-Inapproximability for 2-Variable Linear Equations},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--51},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a019},
doi = {10.4086/TOC.2017.V013A019},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadHMOW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/KindlerO17,
author = {Guy Kindler and
Ryan O'Donnell},
editor = {Ioannis Chatzigiannakis and
Piotr Indyk and
Fabian Kuhn and
Anca Muscholl},
title = {Quantum Automata Cannot Detect Biased Coins, Even in the Limit},
booktitle = {44th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2017, July 10-14, 2017, Warsaw, Poland},
series = {LIPIcs},
volume = {80},
pages = {15:1--15:8},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.15},
doi = {10.4230/LIPICS.ICALP.2017.15},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/icalp/KindlerO17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/ODonnell17,
author = {Ryan O'Donnell},
editor = {Christos H. Papadimitriou},
title = {{SOS} Is Not Obviously Automatizable, Even Approximately},
booktitle = {8th Innovations in Theoretical Computer Science Conference, {ITCS}
2017, January 9-11, 2017, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {67},
pages = {59:1--59:10},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2017.59},
doi = {10.4230/LIPICS.ITCS.2017.59},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/ODonnell17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/spaa/LiO17,
author = {Jason Li and
Ryan O'Donnell},
editor = {Christian Scheideler and
Mohammad Taghi Hajiaghayi},
title = {Bounding Laconic Proof Systems by Solving CSPs in Parallel},
booktitle = {Proceedings of the 29th {ACM} Symposium on Parallelism in Algorithms
and Architectures, {SPAA} 2017, Washington DC, USA, July 24-26, 2017},
pages = {95--100},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3087556.3087557},
doi = {10.1145/3087556.3087557},
timestamp = {Thu, 24 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/spaa/LiO17.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/ODonnellW17,
author = {Ryan O'Donnell and
John Wright},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Efficient quantum tomography {II}},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {962--974},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055454},
doi = {10.1145/3055399.3055454},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DeOS17,
author = {Anindya De and
Ryan O'Donnell and
Rocco A. Servedio},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Optimal mean-based algorithms for trace reconstruction},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {1047--1056},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055450},
doi = {10.1145/3055399.3055450},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DeOS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/coco/2017,
editor = {Ryan O'Donnell},
title = {32nd Computational Complexity Conference, {CCC} 2017, July 6-9, 2017,
Riga, Latvia},
series = {LIPIcs},
volume = {79},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {http://www.dagstuhl.de/dagpub/978-3-95977-040-8},
isbn = {978-3-95977-040-8},
timestamp = {Thu, 02 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/2017.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/DeOS17,
author = {Anindya De and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Sharp bounds for population recovery},
journal = {CoRR},
volume = {abs/1703.01474},
year = {2017},
url = {http://arxiv.org/abs/1703.01474},
eprinttype = {arXiv},
eprint = {1703.01474},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/DeOS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1708-06002,
author = {Costin Badescu and
Ryan O'Donnell and
John Wright},
title = {Quantum state certification},
journal = {CoRR},
volume = {abs/1708.06002},
year = {2017},
url = {http://arxiv.org/abs/1708.06002},
eprinttype = {arXiv},
eprint = {1708.06002},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1708-06002.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnellZ16,
author = {Ryan O'Donnell and
Yu Zhao},
editor = {Ran Raz},
title = {Polynomial Bounds for Decoupling, with Applications},
booktitle = {31st Conference on Computational Complexity, {CCC} 2016, May 29 to
June 1, 2016, Tokyo, Japan},
series = {LIPIcs},
volume = {50},
pages = {24:1--24:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.CCC.2016.24},
doi = {10.4230/LIPICS.CCC.2016.24},
timestamp = {Thu, 02 Feb 2023 13:27:05 +0100},
biburl = {https://dblp.org/rec/conf/coco/ODonnellZ16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellW16,
author = {Ryan O'Donnell and
John Wright},
editor = {Daniel Wichs and
Yishay Mansour},
title = {Efficient quantum tomography},
booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
pages = {899--912},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2897518.2897544},
doi = {10.1145/2897518.2897544},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KindlerO16,
author = {Guy Kindler and
Ryan O'Donnell},
title = {Quantum automata cannot detect biased coins, even in the limit},
journal = {CoRR},
volume = {abs/1610.03543},
year = {2016},
url = {http://arxiv.org/abs/1610.03543},
eprinttype = {arXiv},
eprint = {1610.03543},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KindlerO16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ODonnellW16,
author = {Ryan O'Donnell and
John Wright},
title = {Efficient quantum tomography {II}},
journal = {CoRR},
volume = {abs/1612.00034},
year = {2016},
url = {http://arxiv.org/abs/1612.00034},
eprinttype = {arXiv},
eprint = {1612.00034},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ODonnellW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/DeOS16,
author = {Anindya De and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Optimal mean-based algorithms for trace reconstruction},
journal = {CoRR},
volume = {abs/1612.03148},
year = {2016},
url = {http://arxiv.org/abs/1612.03148},
eprinttype = {arXiv},
eprint = {1612.03148},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/DeOS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LiO16,
author = {Jason Li and
Ryan O'Donnell},
title = {Bounding laconic proof systems by solving CSPs in parallel},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-142}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/142},
eprinttype = {ECCC},
eprint = {TR16-142},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LiO16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ODonnell16,
author = {Ryan O'Donnell},
title = {{SOS} is not obviously automatizable, even approximately},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-141}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/141},
eprinttype = {ECCC},
eprint = {TR16-141},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ODonnell16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ODonnellS16,
author = {Ryan O'Donnell and
A. C. Cem Say},
title = {The weakness of {CTC} qubits and the power of approximate counting},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-147}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/147},
eprinttype = {ECCC},
eprint = {TR16-147},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ODonnellS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/ODonnellWZ15,
author = {Ryan O'Donnell and
Yi Wu and
Yuan Zhou},
title = {Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large
Cyclic Groups},
journal = {{ACM} Trans. Comput. Theory},
volume = {7},
number = {2},
pages = {9:1--9:16},
year = {2015},
url = {https://doi.org/10.1145/2751322},
doi = {10.1145/2751322},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/ODonnellWZ15.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 = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/BarakMORRSTVWW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/HastadHMOW15,
author = {Johan H{\aa}stad and
Sangxia Huang and
Rajsekar Manokaran and
Ryan O'Donnell and
John Wright},
editor = {Naveen Garg and
Klaus Jansen and
Anup Rao and
Jos{\'{e}} D. P. Rolim},
title = {Improved NP-Inapproximability for 2-Variable Linear Equations},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2015, August 24-26, 2015, Princeton,
NJ, {USA}},
series = {LIPIcs},
volume = {40},
pages = {341--360},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.341},
doi = {10.4230/LIPICS.APPROX-RANDOM.2015.341},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/HastadHMOW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AllenOW15,
author = {Sarah R. Allen and
Ryan O'Donnell and
David Witmer},
editor = {Venkatesan Guruswami},
title = {How to Refute a Random {CSP}},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {689--708},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.48},
doi = {10.1109/FOCS.2015.48},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AllenOW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/itw/AllenO15,
author = {Sarah R. Allen and
Ryan O'Donnell},
title = {Conditioning and covariance on caterpillars},
booktitle = {2015 {IEEE} Information Theory Workshop, {ITW} 2015, Jerusalem, Israel,
April 26 - May 1, 2015},
pages = {1--5},
publisher = {{IEEE}},
year = {2015},
url = {https://doi.org/10.1109/ITW.2015.7133115},
doi = {10.1109/ITW.2015.7133115},
timestamp = {Wed, 16 Oct 2019 14:14:51 +0200},
biburl = {https://dblp.org/rec/conf/itw/AllenO15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/CaferovKOS15,
author = {Cafer Caferov and
Baris Kaya and
Ryan O'Donnell and
A. C. Cem Say},
editor = {Giuseppe F. Italiano and
Giovanni Pighizzini and
Donald Sannella},
title = {Optimal Bounds for Estimating Entropy with {PMF} Queries},
booktitle = {Mathematical Foundations of Computer Science 2015 - 40th International
Symposium, {MFCS} 2015, Milan, Italy, August 24-28, 2015, Proceedings,
Part {II}},
series = {Lecture Notes in Computer Science},
volume = {9235},
pages = {187--198},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-662-48054-0\_16},
doi = {10.1007/978-3-662-48054-0\_16},
timestamp = {Tue, 14 May 2019 10:00:37 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/CaferovKOS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sagt/DughmiIOT15,
author = {Shaddin Dughmi and
Nicole Immorlica and
Ryan O'Donnell and
Li{-}Yang Tan},
editor = {Martin Hoefer},
title = {Algorithmic Signaling of Features in Auction Design},
booktitle = {Algorithmic Game Theory - 8th International Symposium, {SAGT} 2015,
Saarbr{\"{u}}cken, Germany, September 28-30, 2015, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9347},
pages = {150--162},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-662-48433-3\_12},
doi = {10.1007/978-3-662-48433-3\_12},
timestamp = {Fri, 26 Mar 2021 08:28:34 +0100},
biburl = {https://dblp.org/rec/conf/sagt/DughmiIOT15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellW15,
author = {Ryan O'Donnell and
John Wright},
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {Quantum Spectrum Testing},
booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
pages = {529--538},
publisher = {{ACM}},
year = {2015},
url = {https://doi.org/10.1145/2746539.2746582},
doi = {10.1145/2746539.2746582},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellW15.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/AllenOW15,
author = {Sarah R. Allen and
Ryan O'Donnell and
David Witmer},
title = {How to refute a random {CSP}},
journal = {CoRR},
volume = {abs/1505.04383},
year = {2015},
url = {http://arxiv.org/abs/1505.04383},
eprinttype = {arXiv},
eprint = {1505.04383},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AllenOW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KindlerOW15,
author = {Guy Kindler and
Ryan O'Donnell and
David Witmer},
title = {Continuous analogues of the Most Informative Function problem},
journal = {CoRR},
volume = {abs/1506.03167},
year = {2015},
url = {http://arxiv.org/abs/1506.03167},
eprinttype = {arXiv},
eprint = {1506.03167},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KindlerOW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ODonnellW15,
author = {Ryan O'Donnell and
John Wright},
title = {Efficient quantum tomography},
journal = {CoRR},
volume = {abs/1508.01907},
year = {2015},
url = {http://arxiv.org/abs/1508.01907},
eprinttype = {arXiv},
eprint = {1508.01907},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ODonnellW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ODonnellZ15,
author = {Ryan O'Donnell and
Yu Zhao},
title = {Polynomial bounds for decoupling, with applications},
journal = {CoRR},
volume = {abs/1512.01603},
year = {2015},
url = {http://arxiv.org/abs/1512.01603},
eprinttype = {arXiv},
eprint = {1512.01603},
timestamp = {Wed, 26 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ODonnellZ15.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}
}
@book{DBLP:books/daglib/0033652,
author = {Ryan O'Donnell},
title = {Analysis of Boolean Functions},
publisher = {Cambridge University Press},
year = {2014},
url = {http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/analysis-boolean-functions},
isbn = {978-1-10-703832-5},
timestamp = {Mon, 01 Sep 2014 01:00:00 +0200},
biburl = {https://dblp.org/rec/books/daglib/0033652.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/LauMOT14,
author = {Lap Chi Lau and
Tal Malkin and
Ryan O'Donnell and
Luca Trevisan},
title = {Special Section on the Fifty-First Annual {IEEE} Symposium on Foundations
of Computer Science {(FOCS} 2010)},
journal = {{SIAM} J. Comput.},
volume = {43},
number = {1},
pages = {255},
year = {2014},
url = {https://doi.org/10.1137/140973608},
doi = {10.1137/140973608},
timestamp = {Fri, 02 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/LauMOT14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/AustrinOTW14,
author = {Per Austrin and
Ryan O'Donnell and
Li{-}Yang Tan and
John Wright},
title = {New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover},
journal = {{ACM} Trans. Comput. Theory},
volume = {6},
number = {1},
pages = {2:1--2:20},
year = {2014},
url = {https://doi.org/10.1145/2537800},
doi = {10.1145/2537800},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/AustrinOTW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/ODonnellWZ14,
author = {Ryan O'Donnell and
Yi Wu and
Yuan Zhou},
title = {Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q
is Tiny)},
journal = {{ACM} Trans. Comput. Theory},
volume = {6},
number = {1},
pages = {5:1--5:13},
year = {2014},
url = {https://doi.org/10.1145/2578221},
doi = {10.1145/2578221},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/ODonnellWZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnellW14,
author = {Ryan O'Donnell and
David Witmer},
title = {Goldreich's {PRG:} Evidence for Near-Optimal Polynomial Stretch},
booktitle = {{IEEE} 29th Conference on Computational Complexity, {CCC} 2014, Vancouver,
BC, Canada, June 11-13, 2014},
pages = {1--12},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/CCC.2014.9},
doi = {10.1109/CCC.2014.9},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ODonnellW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnellWZST14,
author = {Ryan O'Donnell and
John Wright and
Yu Zhao and
Xiaorui Sun and
Li{-}Yang Tan},
title = {A Composition Theorem for Parity Kill Number},
booktitle = {{IEEE} 29th Conference on Computational Complexity, {CCC} 2014, Vancouver,
BC, Canada, June 11-13, 2014},
pages = {144--154},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/CCC.2014.22},
doi = {10.1109/CCC.2014.22},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ODonnellWZST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/ODonnellS14,
author = {Ryan O'Donnell and
A. C. Cem Say},
editor = {Venkatesh Raman and
S. P. Suresh},
title = {One Time-traveling Bit is as Good as Logarithmically Many},
booktitle = {34th International Conference on Foundation of Software Technology
and Theoretical Computer Science, {FSTTCS} 2014, December 15-17, 2014,
New Delhi, India},
series = {LIPIcs},
volume = {29},
pages = {469--480},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2014},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2014.469},
doi = {10.4230/LIPICS.FSTTCS.2014.469},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/ODonnellS14.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}
}
@inproceedings{DBLP:conf/soda/KauersOTZ14,
author = {Manuel Kauers and
Ryan O'Donnell and
Li{-}Yang Tan and
Yuan Zhou},
editor = {Chandra Chekuri},
title = {Hypercontractive inequalities via SOS, and the Frankl-R{\"{o}}dl
graph},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {1644--1658},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.119},
doi = {10.1137/1.9781611973402.119},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KauersOTZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ODonnellWWZ14,
author = {Ryan O'Donnell and
John Wright and
Chenggang Wu and
Yuan Zhou},
editor = {Chandra Chekuri},
title = {Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry
of Random Graphs},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {1659--1677},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.120},
doi = {10.1137/1.9781611973402.120},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ODonnellWWZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ODonnellWWZ14,
author = {Ryan O'Donnell and
John Wright and
Chenggang Wu and
Yuan Zhou},
title = {Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry
of random graphs},
journal = {CoRR},
volume = {abs/1401.2436},
year = {2014},
url = {http://arxiv.org/abs/1401.2436},
eprinttype = {arXiv},
eprint = {1401.2436},
timestamp = {Tue, 18 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ODonnellWWZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AllenO14,
author = {Sarah R. Allen and
Ryan O'Donnell},
title = {Conditioning and covariance on caterpillars},
journal = {CoRR},
volume = {abs/1407.4423},
year = {2014},
url = {http://arxiv.org/abs/1407.4423},
eprinttype = {arXiv},
eprint = {1407.4423},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AllenO14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ODonnell14,
author = {Ryan O'Donnell},
title = {Social choice, computational complexity, Gaussian geometry, and Boolean
functions},
journal = {CoRR},
volume = {abs/1407.7763},
year = {2014},
url = {http://arxiv.org/abs/1407.7763},
eprinttype = {arXiv},
eprint = {1407.7763},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ODonnell14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ODonnellS14,
author = {Ryan O'Donnell and
A. C. Cem Say},
title = {One time-travelling bit is as good as logarithmically many},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-091}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/091},
eprinttype = {ECCC},
eprint = {TR14-091},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ODonnellS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ODonnellW13,
author = {Ryan O'Donnell and
Karl Wimmer},
title = {KKL, Kruskal-Katona, and Monotone Nets},
journal = {{SIAM} J. Comput.},
volume = {42},
number = {6},
pages = {2375--2399},
year = {2013},
url = {https://doi.org/10.1137/100787325},
doi = {10.1137/100787325},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ODonnellW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/MosselO13,
author = {Elchanan Mossel and
Ryan O'Donnell},
title = {Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword},
journal = {Theory Comput.},
volume = {9},
pages = {579--585},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a016},
doi = {10.4086/TOC.2013.V009A016},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/MosselO13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DaskalakisDOST13,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Ryan O'Donnell and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Learning Sums of Independent Integer Random Variables},
booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2013, 26-29 October, 2013, Berkeley, CA, {USA}},
pages = {217--226},
publisher = {{IEEE} Computer Society},
year = {2013},
url = {https://doi.org/10.1109/FOCS.2013.31},
doi = {10.1109/FOCS.2013.31},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DaskalakisDOST13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ODonnellT13,
author = {Ryan O'Donnell and
Li{-}Yang Tan},
editor = {Fedor V. Fomin and
Rusins Freivalds and
Marta Z. Kwiatkowska and
David Peleg},
title = {A Composition Theorem for the Fourier Entropy-Influence Conjecture},
booktitle = {Automata, Languages, and Programming - 40th International Colloquium,
{ICALP} 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7965},
pages = {780--791},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-39206-1\_66},
doi = {10.1007/978-3-642-39206-1\_66},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ODonnellT13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ODonnellZ13,
author = {Ryan O'Donnell and
Yuan Zhou},
editor = {Sanjeev Khanna},
title = {Approximability and proof complexity},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
2013},
pages = {1537--1556},
publisher = {{SIAM}},
year = {2013},
url = {https://doi.org/10.1137/1.9781611973105.111},
doi = {10.1137/1.9781611973105.111},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ODonnellZ13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1304-1347,
author = {Ryan O'Donnell and
Li{-}Yang Tan},
title = {A composition theorem for the Fourier Entropy-Influence conjecture},
journal = {CoRR},
volume = {abs/1304.1347},
year = {2013},
url = {http://arxiv.org/abs/1304.1347},
eprinttype = {arXiv},
eprint = {1304.1347},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1304-1347.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ODonnellSTWZ13,
author = {Ryan O'Donnell and
Xiaorui Sun and
Li{-}Yang Tan and
John Wright and
Yu Zhao},
title = {A composition theorem for parity kill number},
journal = {CoRR},
volume = {abs/1312.2143},
year = {2013},
url = {http://arxiv.org/abs/1312.2143},
eprinttype = {arXiv},
eprint = {1312.2143},
timestamp = {Wed, 26 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ODonnellSTWZ13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cacm/KindlerROW12,
author = {Guy Kindler and
Anup Rao and
Ryan O'Donnell and
Avi Wigderson},
title = {Spherical cubes: optimal foams from computational hardness amplification},
journal = {Commun. {ACM}},
volume = {55},
number = {10},
pages = {90--97},
year = {2012},
url = {https://doi.org/10.1145/2347736.2347757},
doi = {10.1145/2347736.2347757},
timestamp = {Mon, 07 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cacm/KindlerROW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/MoitraO12,
author = {Ankur Moitra and
Ryan O'Donnell},
title = {Pareto Optimal Solutions for Smoothed Analysts},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {5},
pages = {1266--1284},
year = {2012},
url = {https://doi.org/10.1137/110851833},
doi = {10.1137/110851833},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/MoitraO12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/AustrinOW12,
author = {Per Austrin and
Ryan O'Donnell and
John Wright},
editor = {Anupam Gupta and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Rocco A. Servedio},
title = {A New Point of NP-Hardness for 2-to-1 Label Cover},
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 = {1--12},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32512-0\_1},
doi = {10.1007/978-3-642-32512-0\_1},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/AustrinOW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/KindlerO12,
author = {Guy Kindler and
Ryan O'Donnell},
title = {Gaussian Noise Sensitivity and Fourier Tails},
booktitle = {Proceedings of the 27th Conference on Computational Complexity, {CCC}
2012, Porto, Portugal, June 26-29, 2012},
pages = {137--147},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/CCC.2012.35},
doi = {10.1109/CCC.2012.35},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/KindlerO12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/KunOTYZ12,
author = {G{\'{a}}bor Kun and
Ryan O'Donnell and
Suguru Tamaki and
Yuichi Yoshida and
Yuan Zhou},
editor = {Shafi Goldwasser},
title = {Linear programming, width-1 CSPs, and robust satisfaction},
booktitle = {Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA,
January 8-10, 2012},
pages = {484--495},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2090236.2090274},
doi = {10.1145/2090236.2090274},
timestamp = {Mon, 24 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/KunOTYZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellW12,
author = {Ryan O'Donnell and
John Wright},
editor = {Howard J. Karloff and
Toniann Pitassi},
title = {A new point of NP-hardness for unique games},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
pages = {289--306},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2213977.2214005},
doi = {10.1145/2213977.2214005},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-4688,
author = {Ryan O'Donnell and
David Witmer},
title = {Improved small-set expansion from higher eigenvalues},
journal = {CoRR},
volume = {abs/1204.4688},
year = {2012},
url = {http://arxiv.org/abs/1204.4688},
eprinttype = {arXiv},
eprint = {1204.4688},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-4688.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-5666,
author = {Per Austrin and
Ryan O'Donnell and
John Wright},
title = {A new point of NP-hardness for 2-to-1 Label Cover},
journal = {CoRR},
volume = {abs/1204.5666},
year = {2012},
url = {http://arxiv.org/abs/1204.5666},
eprinttype = {arXiv},
eprint = {1204.5666},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-5666.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-6447,
author = {Ryan O'Donnell},
title = {Open Problems in Analysis of Boolean Functions},
journal = {CoRR},
volume = {abs/1204.6447},
year = {2012},
url = {http://arxiv.org/abs/1204.6447},
eprinttype = {arXiv},
eprint = {1204.6447},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-6447.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1210-5648,
author = {Per Austrin and
Ryan O'Donnell and
Li{-}Yang Tan and
John Wright},
title = {New NP-hardness results for 3-Coloring and 2-to-1 Label Cover},
journal = {CoRR},
volume = {abs/1210.5648},
year = {2012},
url = {http://arxiv.org/abs/1210.5648},
eprinttype = {arXiv},
eprint = {1210.5648},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1210-5648.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1211-1958,
author = {Ryan O'Donnell and
Yuan Zhou},
title = {Approximability and proof complexity},
journal = {CoRR},
volume = {abs/1211.1958},
year = {2012},
url = {http://arxiv.org/abs/1211.1958},
eprinttype = {arXiv},
eprint = {1211.1958},
timestamp = {Mon, 24 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1211-1958.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1212-5324,
author = {Manuel Kauers and
Ryan O'Donnell and
Li{-}Yang Tan and
Yuan Zhou},
title = {Hypercontractive inequalities via SOS, with an application to Vertex-Cover},
journal = {CoRR},
volume = {abs/1212.5324},
year = {2012},
url = {http://arxiv.org/abs/1212.5324},
eprinttype = {arXiv},
eprint = {1212.5324},
timestamp = {Mon, 24 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1212-5324.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ODonnellS11,
author = {Ryan O'Donnell and
Rocco A. Servedio},
title = {The Chow Parameters Problem},
journal = {{SIAM} J. Comput.},
volume = {40},
number = {1},
pages = {165--199},
year = {2011},
url = {https://doi.org/10.1137/090756466},
doi = {10.1137/090756466},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ODonnellS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GopalanOSSW11,
author = {Parikshit Gopalan and
Ryan O'Donnell and
Rocco A. Servedio and
Amir Shpilka and
Karl Wimmer},
title = {Testing Fourier Dimensionality and Sparsity},
journal = {{SIAM} J. Comput.},
volume = {40},
number = {4},
pages = {1075--1100},
year = {2011},
url = {https://doi.org/10.1137/100785429},
doi = {10.1137/100785429},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GopalanOSSW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnellWZ11,
author = {Ryan O'Donnell and
Yi Wu and
Yuan Zhou},
title = {Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large
Cyclic Groups},
booktitle = {Proceedings of the 26th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2011, San Jose, California, USA, June 8-10, 2011},
pages = {23--33},
publisher = {{IEEE} Computer Society},
year = {2011},
url = {https://doi.org/10.1109/CCC.2011.37},
doi = {10.1109/CCC.2011.37},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ODonnellWZ11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ODonnellWZ11,
author = {Ryan O'Donnell and
John Wright and
Yuan Zhou},
editor = {Luca Aceto and
Monika Henzinger and
Jir{\'{\i}} Sgall},
title = {The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean
Functions},
booktitle = {Automata, Languages and Programming - 38th International Colloquium,
{ICALP} 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6755},
pages = {330--341},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22006-7\_28},
doi = {10.1007/978-3-642-22006-7\_28},
timestamp = {Thu, 11 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ODonnellWZ11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/ODonnellWZ11,
author = {Ryan O'Donnell and
Yi Wu and
Yuan Zhou},
editor = {Bernard Chazelle},
title = {Optimal lower bounds for locality sensitive hashing (except when q
is tiny)},
booktitle = {Innovations in Computer Science - {ICS} 2011, Tsinghua University,
Beijing, China, January 7-9, 2011. Proceedings},
pages = {275--283},
publisher = {Tsinghua University Press},
year = {2011},
url = {http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/2.html},
timestamp = {Mon, 23 Mar 2020 08:26:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/ODonnellWZ11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DiakonikolasOSW11,
author = {Ilias Diakonikolas and
Ryan O'Donnell and
Rocco A. Servedio and
Yi Wu},
editor = {Dana Randall},
title = {Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold
Functions},
booktitle = {Proceedings of the Twenty-Second Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2011, San Francisco, California, USA, January 23-25,
2011},
pages = {1590--1606},
publisher = {{SIAM}},
year = {2011},
url = {https://doi.org/10.1137/1.9781611973082.123},
doi = {10.1137/1.9781611973082.123},
timestamp = {Tue, 02 Feb 2021 17:07:23 +0100},
biburl = {https://dblp.org/rec/conf/soda/DiakonikolasOSW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MoitraO11,
author = {Ankur Moitra and
Ryan O'Donnell},
editor = {Lance Fortnow and
Salil P. Vadhan},
title = {Pareto optimal solutions for smoothed analysts},
booktitle = {Proceedings of the 43rd {ACM} Symposium on Theory of Computing, {STOC}
2011, San Jose, CA, USA, 6-8 June 2011},
pages = {225--234},
publisher = {{ACM}},
year = {2011},
url = {https://doi.org/10.1145/1993636.1993667},
doi = {10.1145/1993636.1993667},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/MoitraO11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/ODonnellS10,
author = {Ryan O'Donnell and
Rocco A. Servedio},
title = {New degree bounds for polynomial threshold functions},
journal = {Comb.},
volume = {30},
number = {3},
pages = {327--358},
year = {2010},
url = {https://doi.org/10.1007/s00493-010-2173-3},
doi = {10.1007/S00493-010-2173-3},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/ODonnellS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ml/BlaisOW10,
author = {Eric Blais and
Ryan O'Donnell and
Karl Wimmer},
title = {Polynomial regression under arbitrary product distributions},
journal = {Mach. Learn.},
volume = {80},
number = {2-3},
pages = {273--294},
year = {2010},
url = {https://doi.org/10.1007/s10994-010-5179-6},
doi = {10.1007/S10994-010-5179-6},
timestamp = {Mon, 02 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ml/BlaisOW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/MatulefORS10,
author = {Kevin Matulef and
Ryan O'Donnell and
Ronitt Rubinfeld and
Rocco A. Servedio},
title = {Testing Halfspaces},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {5},
pages = {2004--2047},
year = {2010},
url = {https://doi.org/10.1137/070707890},
doi = {10.1137/070707890},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/MatulefORS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/algosensors/AspnesBDORU10,
author = {James Aspnes and
Eric Blais and
Murat Demirbas and
Ryan O'Donnell and
Atri Rudra and
Steve Uurtamo},
editor = {Christian Scheideler},
title = {k\({}^{\mbox{ + }}\) Decision Trees - (Extended Abstract)},
booktitle = {Algorithms for Sensor Systems - 6th International Workshop on Algorithms
for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile
Entities, {ALGOSENSORS} 2010, Bordeaux, France, July 5, 2010, Revised
Selected Papers},
series = {Lecture Notes in Computer Science},
volume = {6451},
pages = {74--88},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-16988-5\_7},
doi = {10.1007/978-3-642-16988-5\_7},
timestamp = {Tue, 14 May 2019 10:00:36 +0200},
biburl = {https://dblp.org/rec/conf/algosensors/AspnesBDORU10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/GopalanOWZ10,
author = {Parikshit Gopalan and
Ryan O'Donnell and
Yi Wu and
David Zuckerman},
title = {Fooling Functions of Halfspaces under Product Distributions},
booktitle = {Proceedings of the 25th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2010, Cambridge, Massachusetts, USA, June 9-12,
2010},
pages = {223--234},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/CCC.2010.29},
doi = {10.1109/CCC.2010.29},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/GopalanOWZ10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BlaisO10,
author = {Eric Blais and
Ryan O'Donnell},
title = {Lower Bounds for Testing Function Isomorphism},
booktitle = {Proceedings of the 25th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2010, Cambridge, Massachusetts, USA, June 9-12,
2010},
pages = {235--246},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/CCC.2010.30},
doi = {10.1109/CCC.2010.30},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BlaisO10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/GuruswamiKOPTW10,
author = {Venkatesan Guruswami and
Subhash Khot and
Ryan O'Donnell and
Preyas Popat and
Madhur Tulsiani and
Yi Wu},
editor = {Samson Abramsky and
Cyril Gavoille and
Claude Kirchner and
Friedhelm Meyer auf der Heide and
Paul G. Spirakis},
title = {{SDP} Gaps for 2-to-1 and Other Label-Cover Variants},
booktitle = {Automata, Languages and Programming, 37th International Colloquium,
{ICALP} 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6198},
pages = {617--628},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14165-2\_52},
doi = {10.1007/978-3-642-14165-2\_52},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/GuruswamiKOPTW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:conf/propertytesting/MatulefORS10,
author = {Kevin Matulef and
Ryan O'Donnell and
Ronitt Rubinfeld and
Rocco A. Servedio},
editor = {Oded Goldreich},
title = {Testing (Subclasses of) Halfspaces},
booktitle = {Property Testing - Current Research and Surveys},
series = {Lecture Notes in Computer Science},
volume = {6390},
pages = {334--340},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-16367-8\_27},
doi = {10.1007/978-3-642-16367-8\_27},
timestamp = {Tue, 01 Jun 2021 15:22:56 +0200},
biburl = {https://dblp.org/rec/conf/propertytesting/MatulefORS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1001-1593,
author = {Parikshit Gopalan and
Ryan O'Donnell and
Yi Wu and
David Zuckerman},
title = {Fooling functions of halfspaces under product distributions},
journal = {CoRR},
volume = {abs/1001.1593},
year = {2010},
url = {http://arxiv.org/abs/1001.1593},
eprinttype = {arXiv},
eprint = {1001.1593},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1001-1593.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1010-3484,
author = {Ilias Diakonikolas and
Ryan O'Donnell and
Rocco A. Servedio and
Yi Wu},
title = {Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold
Functions},
journal = {CoRR},
volume = {abs/1010.3484},
year = {2010},
url = {http://arxiv.org/abs/1010.3484},
eprinttype = {arXiv},
eprint = {1010.3484},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1010-3484.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1011-2249,
author = {Ankur Moitra and
Ryan O'Donnell},
title = {Pareto Optimal Solutions for Smoothed Analysts},
journal = {CoRR},
volume = {abs/1011.2249},
year = {2010},
url = {http://arxiv.org/abs/1011.2249},
eprinttype = {arXiv},
eprint = {1011.2249},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1011-2249.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/WuOZG10,
author = {Yi Wu and
Ryan O'Donnell and
David Zuckerman and
Parikshit Gopalan},
title = {Fooling functions of halfspaces under product distributions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-006}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/006},
eprinttype = {ECCC},
eprint = {TR10-006},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/WuOZG10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KhotO09,
author = {Subhash Khot and
Ryan O'Donnell},
title = {{SDP} Gaps and UGC-hardness for Max-Cut-Gain},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {83--117},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a004},
doi = {10.4086/TOC.2009.V005A004},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/KhotO09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/MatulefORS09,
author = {Kevin Matulef and
Ryan O'Donnell and
Ronitt Rubinfeld and
Rocco A. Servedio},
editor = {Irit Dinur and
Klaus Jansen and
Joseph Naor and
Jos{\'{e}} D. P. Rolim},
title = {Testing {\(\pm\)}1-weight halfspace},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 12th International Workshop, {APPROX} 2009, and 13th
International Workshop, {RANDOM} 2009, Berkeley, CA, USA, August 21-23,
2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5687},
pages = {646--657},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-03685-9\_48},
doi = {10.1007/978-3-642-03685-9\_48},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/MatulefORS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ODonnellW09,
author = {Ryan O'Donnell and
Karl Wimmer},
title = {KKL, Kruskal-Katona, and Monotone Nets},
booktitle = {50th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2009, October 25-27, 2009, Atlanta, Georgia, {USA}},
pages = {725--734},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/FOCS.2009.78},
doi = {10.1109/FOCS.2009.78},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ODonnellW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/GopalanOSSW09,
author = {Parikshit Gopalan and
Ryan O'Donnell and
Rocco A. Servedio and
Amir Shpilka and
Karl Wimmer},
editor = {Susanne Albers and
Alberto Marchetti{-}Spaccamela and
Yossi Matias and
Sotiris E. Nikoletseas and
Wolfgang Thomas},
title = {Testing Fourier Dimensionality and Sparsity},
booktitle = {Automata, Languages and Programming, 36th International Colloquium,
{ICALP} 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {5555},
pages = {500--512},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02927-1\_42},
doi = {10.1007/978-3-642-02927-1\_42},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/GopalanOSSW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MatulefORS09,
author = {Kevin Matulef and
Ryan O'Donnell and
Ronitt Rubinfeld and
Rocco A. Servedio},
editor = {Claire Mathieu},
title = {Testing halfspaces},
booktitle = {Proceedings of the Twentieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2009, New York, NY, USA, January 4-6, 2009},
pages = {256--264},
publisher = {{SIAM}},
year = {2009},
url = {https://doi.org/10.1137/1.9781611973068.29},
doi = {10.1137/1.9781611973068.29},
timestamp = {Mon, 12 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/MatulefORS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ODonnellW09,
author = {Ryan O'Donnell and
Yi Wu},
editor = {Claire Mathieu},
title = {3-bit dictator testing: 1 vs. 5/8},
booktitle = {Proceedings of the Twentieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2009, New York, NY, USA, January 4-6, 2009},
pages = {365--373},
publisher = {{SIAM}},
year = {2009},
url = {https://doi.org/10.1137/1.9781611973068.41},
doi = {10.1137/1.9781611973068.41},
timestamp = {Mon, 12 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ODonnellW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellW09,
author = {Ryan O'Donnell and
Yi Wu},
editor = {Michael Mitzenmacher},
title = {Conditional hardness for satisfiable 3-CSPs},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {493--502},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536482},
doi = {10.1145/1536414.1536482},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0912-0250,
author = {Ryan O'Donnell and
Yi Wu and
Yuan Zhou},
title = {Optimal lower bounds for locality sensitive hashing (except when q
is tiny)},
journal = {CoRR},
volume = {abs/0912.0250},
year = {2009},
url = {http://arxiv.org/abs/0912.0250},
eprinttype = {arXiv},
eprint = {0912.0250},
timestamp = {Mon, 24 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0912-0250.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ODonnellWZ09,
author = {Ryan O'Donnell and
Yi Wu and
Yuan Zhou},
title = {Optimal lower bounds for locality sensitive hashing (except when q
is tiny)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-130}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/130},
eprinttype = {ECCC},
eprint = {TR09-130},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ODonnellWZ09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/BollobasKLO08,
author = {B{\'{e}}la Bollob{\'{a}}s and
Guy Kindler and
Imre Leader and
Ryan O'Donnell},
title = {Eliminating Cycles in the Discrete Torus},
journal = {Algorithmica},
volume = {50},
number = {4},
pages = {446--454},
year = {2008},
url = {https://doi.org/10.1007/s00453-007-9095-5},
doi = {10.1007/S00453-007-9095-5},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/BollobasKLO08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/ODonnellS08,
author = {Ryan O'Donnell and
Rocco A. Servedio},
title = {Extremal properties of polynomial threshold functions},
journal = {J. Comput. Syst. Sci.},
volume = {74},
number = {3},
pages = {298--312},
year = {2008},
url = {https://doi.org/10.1016/j.jcss.2007.06.021},
doi = {10.1016/J.JCSS.2007.06.021},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/ODonnellS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/FeldmanOS08,
author = {Jon Feldman and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning Mixtures of Product Distributions over Discrete Domains},
journal = {{SIAM} J. Comput.},
volume = {37},
number = {5},
pages = {1536--1564},
year = {2008},
url = {https://doi.org/10.1137/060670705},
doi = {10.1137/060670705},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/FeldmanOS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/BlaisOW08,
author = {Eric Blais and
Ryan O'Donnell and
Karl Wimmer},
editor = {Rocco A. Servedio and
Tong Zhang},
title = {Polynomial Regression under Arbitrary Product Distributions},
booktitle = {21st Annual Conference on Learning Theory - {COLT} 2008, Helsinki,
Finland, July 9-12, 2008},
pages = {193--204},
publisher = {Omnipress},
year = {2008},
url = {http://colt2008.cs.helsinki.fi/papers/78-Blais.pdf},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/BlaisOW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KindlerORW08,
author = {Guy Kindler and
Ryan O'Donnell and
Anup Rao and
Avi Wigderson},
title = {Spherical Cubes and Rounding in High Dimensions},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {189--198},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.50},
doi = {10.1109/FOCS.2008.50},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KindlerORW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KlivansOS08,
author = {Adam R. Klivans and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning Geometric Concepts via Gaussian Surface Area},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {541--550},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.64},
doi = {10.1109/FOCS.2008.64},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KlivansOS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellW08,
author = {Ryan O'Donnell and
Yi Wu},
editor = {Cynthia Dwork},
title = {An optimal sdp algorithm for max-cut, and equally optimal long code
tests},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {335--344},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374425},
doi = {10.1145/1374376.1374425},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellS08,
author = {Ryan O'Donnell and
Rocco A. Servedio},
editor = {Cynthia Dwork},
title = {The chow parameters problem},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {517--526},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374450},
doi = {10.1145/1374376.1374450},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnell08,
author = {Ryan O'Donnell},
editor = {Cynthia Dwork},
title = {Some topics in analysis of boolean functions},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {569--578},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374458},
doi = {10.1145/1374376.1374458},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ODonnell08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ODonnell08,
author = {Ryan O'Donnell},
title = {Some Topics in Analysis of Boolean Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR08-055}},
year = {2008},
url = {https://eccc.weizmann.ac.il/eccc-reports/2008/TR08-055/index.html},
eprinttype = {ECCC},
eprint = {TR08-055},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ODonnell08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KhotKMO07,
author = {Subhash Khot and
Guy Kindler and
Elchanan Mossel and
Ryan O'Donnell},
title = {Optimal Inapproximability Results for {MAX-CUT} and Other 2-Variable
CSPs?},
journal = {{SIAM} J. Comput.},
volume = {37},
number = {1},
pages = {319--357},
year = {2007},
url = {https://doi.org/10.1137/S0097539705447372},
doi = {10.1137/S0097539705447372},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/KhotKMO07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ODonnellS07,
author = {Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning Monotone Decision Trees in Polynomial Time},
journal = {{SIAM} J. Comput.},
volume = {37},
number = {3},
pages = {827--844},
year = {2007},
url = {https://doi.org/10.1137/060669309},
doi = {10.1137/060669309},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ODonnellS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/FeigeKO07,
author = {Uriel Feige and
Guy Kindler and
Ryan O'Donnell},
title = {Understanding Parallel Repetition Requires Understanding Foams},
booktitle = {22nd Annual {IEEE} Conference on Computational Complexity {(CCC} 2007),
13-16 June 2007, San Diego, California, {USA}},
pages = {179--192},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/CCC.2007.39},
doi = {10.1109/CCC.2007.39},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/FeigeKO07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ODonnellW07,
author = {Ryan O'Donnell and
Karl Wimmer},
editor = {Lars Arge and
Christian Cachin and
Tomasz Jurdzinski and
Andrzej Tarlecki},
title = {Approximation by {DNF:} Examples and Counterexamples},
booktitle = {Automata, Languages and Programming, 34th International Colloquium,
{ICALP} 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4596},
pages = {195--206},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-73420-8\_19},
doi = {10.1007/978-3-540-73420-8\_19},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ODonnellW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FeigeKO07,
author = {Uriel Feige and
Guy Kindler and
Ryan O'Donnell},
title = {Understanding Parallel Repetition Requires Understanding Foams},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-043}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-043/index.html},
eprinttype = {ECCC},
eprint = {TR07-043},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FeigeKO07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/MatulefORS07,
author = {Kevin Matulef and
Ryan O'Donnell and
Ronitt Rubinfeld and
Rocco A. Servedio},
title = {Testing Halfspaces},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-128}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-128/index.html},
eprinttype = {ECCC},
eprint = {TR07-128},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/MatulefORS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnellS06,
author = {Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning Monotone Decision Trees in Polynomial Time},
booktitle = {21st Annual {IEEE} Conference on Computational Complexity {(CCC} 2006),
16-20 July 2006, Prague, Czech Republic},
pages = {213--225},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/CCC.2006.25},
doi = {10.1109/CCC.2006.25},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ODonnellS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/FeldmanSO06,
author = {Jon Feldman and
Rocco A. Servedio and
Ryan O'Donnell},
editor = {G{\'{a}}bor Lugosi and
Hans Ulrich Simon},
title = {{PAC} Learning Axis-Aligned Mixtures of Gaussians with No Separation
Assumption},
booktitle = {Learning Theory, 19th Annual Conference on Learning Theory, {COLT}
2006, Pittsburgh, PA, USA, June 22-25, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4005},
pages = {20--34},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11776420\_5},
doi = {10.1007/11776420\_5},
timestamp = {Fri, 08 Sep 2023 21:18:17 +0200},
biburl = {https://dblp.org/rec/conf/colt/FeldmanSO06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotO06,
author = {Subhash Khot and
Ryan O'Donnell},
title = {{SDP} gaps and UGC-hardness for {MAXCUTGAIN}},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages = {217--226},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/FOCS.2006.67},
doi = {10.1109/FOCS.2006.67},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotO06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/BollobasKLO06,
author = {B{\'{e}}la Bollob{\'{a}}s and
Guy Kindler and
Imre Leader and
Ryan O'Donnell},
editor = {Jos{\'{e}} R. Correa and
Alejandro Hevia and
Marcos A. Kiwi},
title = {Eliminating Cycles in the Discrete Torus},
booktitle = {{LATIN} 2006: Theoretical Informatics, 7th Latin American Symposium,
Valdivia, Chile, March 20-24, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3887},
pages = {202--210},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11682462\_22},
doi = {10.1007/11682462\_22},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/latin/BollobasKLO06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DinurFKO06,
author = {Irit Dinur and
Ehud Friedgut and
Guy Kindler and
Ryan O'Donnell},
editor = {Jon M. Kleinberg},
title = {On the fourier tails of bounded functions over the discrete cube},
booktitle = {Proceedings of the 38th Annual {ACM} Symposium on Theory of Computing,
Seattle, WA, USA, May 21-23, 2006},
pages = {437--446},
publisher = {{ACM}},
year = {2006},
url = {https://doi.org/10.1145/1132516.1132580},
doi = {10.1145/1132516.1132580},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DinurFKO06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-cs-0609093,
author = {Jon Feldman and
Ryan O'Donnell and
Rocco A. Servedio},
title = {{PAC} Learning Mixtures of Axis-Aligned Gaussians with No Separation
Assumption},
journal = {CoRR},
volume = {abs/cs/0609093},
year = {2006},
url = {http://arxiv.org/abs/cs/0609093},
eprinttype = {arXiv},
eprint = {cs/0609093},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0609093.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/BshoutyMOS05,
author = {Nader H. Bshouty and
Elchanan Mossel and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning {DNF} from random walks},
journal = {J. Comput. Syst. Sci.},
volume = {71},
number = {3},
pages = {250--265},
year = {2005},
url = {https://doi.org/10.1016/j.jcss.2004.10.010},
doi = {10.1016/J.JCSS.2004.10.010},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/BshoutyMOS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/MosselO05,
author = {Elchanan Mossel and
Ryan O'Donnell},
title = {Coin flipping from a cosmic source: On error correction of truly random
bits},
journal = {Random Struct. Algorithms},
volume = {26},
number = {4},
pages = {418--436},
year = {2005},
url = {https://doi.org/10.1002/rsa.20062},
doi = {10.1002/RSA.20062},
timestamp = {Thu, 08 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/MosselO05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MosselOO05,
author = {Elchanan Mossel and
Ryan O'Donnell and
Krzysztof Oleszkiewicz},
title = {Noise stability of functions with low in.uences invariance and optimality},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {21--30},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.53},
doi = {10.1109/SFCS.2005.53},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MosselOO05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ODonnellSS05,
author = {Ryan O'Donnell and
Michael E. Saks and
Oded Schramm and
Rocco A. Servedio},
title = {Every decision tree has an in.uential variable},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {31--39},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.34},
doi = {10.1109/SFCS.2005.34},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ODonnellSS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/SandlerOS05,
author = {Jon Feldman and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning mixtures of product distributions over discrete domains},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {501--510},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.46},
doi = {10.1109/SFCS.2005.46},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/SandlerOS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-cs-0508071,
author = {Ryan O'Donnell and
Michael E. Saks and
Oded Schramm and
Rocco A. Servedio},
title = {Every decision tree has an influential variable},
journal = {CoRR},
volume = {abs/cs/0508071},
year = {2005},
url = {http://arxiv.org/abs/cs/0508071},
eprinttype = {arXiv},
eprint = {cs/0508071},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0508071.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-math-0503503,
author = {Elchanan Mossel and
Ryan O'Donnell and
Krzysztof Oleszkiewicz},
title = {Noise stability of functions with low influences: invariance and optimality},
journal = {CoRR},
volume = {abs/math/0503503},
year = {2005},
url = {http://arxiv.org/abs/math/0503503},
eprinttype = {arXiv},
eprint = {math/0503503},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-math-0503503.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-101,
author = {Guy Kindler and
Ryan O'Donnell and
Subhash Khot and
Elchanan Mossel},
title = {Optimal Inapproximability Results for {MAX-CUT} and Other 2-Variable
CSPs?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-101}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-101/index.html},
eprinttype = {ECCC},
eprint = {TR05-101},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-101.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/KlivansOS04,
author = {Adam R. Klivans and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning intersections and thresholds of halfspaces},
journal = {J. Comput. Syst. Sci.},
volume = {68},
number = {4},
pages = {808--840},
year = {2004},
url = {https://doi.org/10.1016/j.jcss.2003.11.002},
doi = {10.1016/J.JCSS.2003.11.002},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/KlivansOS04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/ODonnell04,
author = {Ryan O'Donnell},
title = {Hardness amplification within \({}_{\mbox{NP}}\)},
journal = {J. Comput. Syst. Sci.},
volume = {69},
number = {1},
pages = {68--94},
year = {2004},
url = {https://doi.org/10.1016/j.jcss.2004.01.001},
doi = {10.1016/J.JCSS.2004.01.001},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/ODonnell04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/MosselOS04,
author = {Elchanan Mossel and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning functions of k relevant variables},
journal = {J. Comput. Syst. Sci.},
volume = {69},
number = {3},
pages = {421--434},
year = {2004},
url = {https://doi.org/10.1016/j.jcss.2004.04.002},
doi = {10.1016/J.JCSS.2004.04.002},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/MosselOS04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KhotKMO04,
author = {Subhash Khot and
Guy Kindler and
Elchanan Mossel and
Ryan O'Donnell},
title = {Optimal Inapproximability Results for Max-Cut and Other 2-Variable
CSPs?},
booktitle = {45th Symposium on Foundations of Computer Science {(FOCS} 2004), 17-19
October 2004, Rome, Italy, Proceedings},
pages = {146--154},
publisher = {{IEEE} Computer Society},
year = {2004},
url = {https://doi.org/10.1109/FOCS.2004.49},
doi = {10.1109/FOCS.2004.49},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KhotKMO04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/MosselO03,
author = {Elchanan Mossel and
Ryan O'Donnell},
title = {On the noise sensitivity of monotone functions},
journal = {Random Struct. Algorithms},
volume = {23},
number = {3},
pages = {333--350},
year = {2003},
url = {https://doi.org/10.1002/rsa.10097},
doi = {10.1002/RSA.10097},
timestamp = {Thu, 08 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/MosselO03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnellS03,
author = {Ryan O'Donnell and
Rocco A. Servedio},
title = {Extremal properties of polynomial threshold functions},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {3--12},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/CCC.2003.1214406},
doi = {10.1109/CCC.2003.1214406},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ODonnellS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BshoutyMOS03,
author = {Nader H. Bshouty and
Elchanan Mossel and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning {DNF} from Random Walks},
booktitle = {44th Symposium on Foundations of Computer Science {(FOCS} 2003), 11-14
October 2003, Cambridge, MA, USA, Proceedings},
pages = {189--198},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/SFCS.2003.1238193},
doi = {10.1109/SFCS.2003.1238193},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BshoutyMOS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/MosselOS03,
author = {Elchanan Mossel and
Ryan O'Donnell and
Rocco A. Servedio},
editor = {Lawrence L. Larmore and
Michel X. Goemans},
title = {Learning juntas},
booktitle = {Proceedings of the 35th Annual {ACM} Symposium on Theory of Computing,
June 9-11, 2003, San Diego, CA, {USA}},
pages = {206--212},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/780542.780574},
doi = {10.1145/780542.780574},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/MosselOS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnellS03,
author = {Ryan O'Donnell and
Rocco A. Servedio},
editor = {Lawrence L. Larmore and
Michel X. Goemans},
title = {New degree bounds for polynomial threshold functions},
booktitle = {Proceedings of the 35th Annual {ACM} Symposium on Theory of Computing,
June 9-11, 2003, San Diego, CA, {USA}},
pages = {325--334},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/780542.780592},
doi = {10.1145/780542.780592},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ODonnell02,
author = {Ryan O'Donnell},
title = {Hardness Amplification within {NP}},
booktitle = {Proceedings of the 17th Annual {IEEE} Conference on Computational
Complexity, Montr{\'{e}}al, Qu{\'{e}}bec, Canada, May 21-24,
2002},
pages = {23},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/CCC.2002.1004332},
doi = {10.1109/CCC.2002.1004332},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ODonnell02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KlivansOS02,
author = {Adam R. Klivans and
Ryan O'Donnell and
Rocco A. Servedio},
title = {Learning Intersections and Thresholds of Halfspaces},
booktitle = {43rd Symposium on Foundations of Computer Science {(FOCS} 2002), 16-19
November 2002, Vancouver, BC, Canada, Proceedings},
pages = {177--186},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/SFCS.2002.1181894},
doi = {10.1109/SFCS.2002.1181894},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KlivansOS02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/EngebretsenIO02,
author = {Lars Engebretsen and
Piotr Indyk and
Ryan O'Donnell},
editor = {David Eppstein},
title = {Derandomized dimensionality reduction with applications},
booktitle = {Proceedings of the Thirteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, January 6-8, 2002, San Francisco, CA, {USA}},
pages = {705--712},
publisher = {{ACM/SIAM}},
year = {2002},
url = {http://dl.acm.org/citation.cfm?id=545381.545476},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/EngebretsenIO02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ODonnell02,
author = {Ryan O'Donnell},
editor = {John H. Reif},
title = {Hardness amplification within {NP}},
booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing,
May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada},
pages = {751--760},
publisher = {{ACM}},
year = {2002},
url = {https://doi.org/10.1145/509907.510015},
doi = {10.1145/509907.510015},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ODonnell02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-10 21:02 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:
