Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Rocco A. Servedio
@inproceedings{DBLP:conf/innovations/0001D0NS24,
author = {Xi Chen and
Anindya De and
Yuhao Li and
Shivam Nadimpalli and
Rocco A. Servedio},
editor = {Venkatesan Guruswami},
title = {Testing Intersecting and Union-Closed Families},
booktitle = {15th Innovations in Theoretical Computer Science Conference, {ITCS}
2024, January 30 to February 2, 2024, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {287},
pages = {33:1--33:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2024.33},
doi = {10.4230/LIPICS.ITCS.2024.33},
timestamp = {Wed, 24 Jan 2024 15:25:09 +0100},
biburl = {https://dblp.org/rec/conf/innovations/0001D0NS24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenDLNS24,
author = {Xi Chen and
Anindya De and
Yuhao Li and
Shivam Nadimpalli and
Rocco A. Servedio},
editor = {David P. Woodruff},
title = {Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity,
Unateness, and Juntas},
booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
pages = {4321--4337},
publisher = {{SIAM}},
year = {2024},
url = {https://doi.org/10.1137/1.9781611977912.151},
doi = {10.1137/1.9781611977912.151},
timestamp = {Thu, 04 Apr 2024 19:38:10 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenDLNS24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2401-07242,
author = {Xi Chen and
Shivam Nadimpalli and
Tim Randolph and
Rocco A. Servedio and
Or Zamir},
title = {Testing Sumsets is Hard},
journal = {CoRR},
volume = {abs/2401.07242},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2401.07242},
doi = {10.48550/ARXIV.2401.07242},
eprinttype = {arXiv},
eprint = {2401.07242},
timestamp = {Thu, 01 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2401-07242.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2402-08133,
author = {Anindya De and
Huan Li and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Detecting Low-Degree Truncation},
journal = {CoRR},
volume = {abs/2402.08133},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2402.08133},
doi = {10.48550/ARXIV.2402.08133},
eprinttype = {arXiv},
eprint = {2402.08133},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2402-08133.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/0001J0S23,
author = {Xi Chen and
Yaonan Jin and
Tim Randolph and
Rocco A. Servedio},
editor = {Nicole Megow and
Adam D. Smith},
title = {Subset Sum in Time 2\({}^{\mbox{n/2}}\) / poly(n)},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2023, September 11-13, 2023, Atlanta,
Georgia, {USA}},
series = {LIPIcs},
volume = {275},
pages = {39:1--39:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.39},
doi = {10.4230/LIPICS.APPROX/RANDOM.2023.39},
timestamp = {Sat, 09 Sep 2023 00:04:38 +0200},
biburl = {https://dblp.org/rec/conf/approx/0001J0S23.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 14:56:14 +0100},
biburl = {https://dblp.org/rec/conf/focs/ODonnellS023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/0001DLSS23,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
editor = {Nikhil Bansal and
Viswanath Nagarajan},
title = {Approximate Trace Reconstruction from a Single Trace},
booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2023, Florence, Italy, January 22-25, 2023},
pages = {605--637},
publisher = {{SIAM}},
year = {2023},
url = {https://doi.org/10.1137/1.9781611977554.ch27},
doi = {10.1137/1.9781611977554.CH27},
timestamp = {Fri, 17 Feb 2023 09:28:57 +0100},
biburl = {https://dblp.org/rec/conf/soda/0001DLSS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DeNS23,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
editor = {Nikhil Bansal and
Viswanath Nagarajan},
title = {Testing Convex Truncation},
booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2023, Florence, Italy, January 22-25, 2023},
pages = {4050--4082},
publisher = {{SIAM}},
year = {2023},
url = {https://doi.org/10.1137/1.9781611977554.ch155},
doi = {10.1137/1.9781611977554.CH155},
timestamp = {Fri, 17 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DeNS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/2023,
editor = {Barna Saha and
Rocco A. Servedio},
title = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246},
doi = {10.1145/3564246},
isbn = {978-1-4503-9913-5},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/2023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2301-07134,
author = {Xi Chen and
Yaonan Jin and
Tim Randolph and
Rocco A. Servedio},
title = {Subset Sum in Time 2\({}^{\mbox{n/2}}\)/poly(n)},
journal = {CoRR},
volume = {abs/2301.07134},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2301.07134},
doi = {10.48550/ARXIV.2301.07134},
eprinttype = {arXiv},
eprint = {2301.07134},
timestamp = {Mon, 30 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2301-07134.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2305-03146,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Testing Convex Truncation},
journal = {CoRR},
volume = {abs/2305.03146},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2305.03146},
doi = {10.48550/ARXIV.2305.03146},
eprinttype = {arXiv},
eprint = {2305.03146},
timestamp = {Wed, 10 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2305-03146.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2309-12513,
author = {Xi Chen and
Anindya De and
Yuhao Li and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity,
Unateness, and Juntas},
journal = {CoRR},
volume = {abs/2309.12513},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2309.12513},
doi = {10.48550/ARXIV.2309.12513},
eprinttype = {arXiv},
eprint = {2309.12513},
timestamp = {Wed, 04 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2309-12513.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/corr/abs-2311-08575,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Gaussian Approximation of Convex Sets by Intersections of Halfspaces},
journal = {CoRR},
volume = {abs/2311.08575},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2311.08575},
doi = {10.48550/ARXIV.2311.08575},
eprinttype = {arXiv},
eprint = {2311.08575},
timestamp = {Tue, 21 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2311-08575.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2311-11119,
author = {Xi Chen and
Anindya De and
Yuhao Li and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Testing Intersecting and Union-Closed Families},
journal = {CoRR},
volume = {abs/2311.11119},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2311.11119},
doi = {10.48550/ARXIV.2311.11119},
eprinttype = {arXiv},
eprint = {2311.11119},
timestamp = {Thu, 23 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2311-11119.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/neco/LongS22,
author = {Philip M. Long and
Rocco A. Servedio},
title = {The Perils of Being Unhinged: On the Accuracy of Classifiers Minimizing
a Noise-Robust Convex Loss},
journal = {Neural Comput.},
volume = {34},
number = {6},
pages = {1488--1499},
year = {2022},
url = {https://doi.org/10.1162/neco\_a\_01502},
doi = {10.1162/NECO\_A\_01502},
timestamp = {Thu, 23 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/neco/LongS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/ChenRSS22,
author = {Xi Chen and
Tim Randolph and
Rocco A. Servedio and
Timothy Sun},
title = {A Lower Bound on Cycle-Finding in Sparse Digraphs},
journal = {{ACM} Trans. Algorithms},
volume = {18},
number = {4},
pages = {31:1--31:23},
year = {2022},
url = {https://doi.org/10.1145/3417979},
doi = {10.1145/3417979},
timestamp = {Mon, 05 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/ChenRSS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ServedioT22,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
title = {Improved Pseudorandom Generators from Pseudorandom Multi-switching
Lemmas},
journal = {Theory Comput.},
volume = {18},
pages = {1--46},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a004/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/ServedioT22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/HsuSSV22,
author = {Daniel J. Hsu and
Clayton Hendrick Sanford and
Rocco A. Servedio and
Emmanouil{-}Vasileios Vlatakis{-}Gkaragkounis},
editor = {Po{-}Ling Loh and
Maxim Raginsky},
title = {Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals},
booktitle = {Conference on Learning Theory, 2-5 July 2022, London, {UK}},
series = {Proceedings of Machine Learning Research},
volume = {178},
pages = {283--312},
publisher = {{PMLR}},
year = {2022},
url = {https://proceedings.mlr.press/v178/hsu22a.html},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/HsuSSV22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/DeNS22,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
editor = {Mark Braverman},
title = {Convex Influences},
booktitle = {13th Innovations in Theoretical Computer Science Conference, {ITCS}
2022, January 31 - February 3, 2022, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {215},
pages = {53:1--53:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2022.53},
doi = {10.4230/LIPICS.ITCS.2022.53},
timestamp = {Wed, 26 Jan 2022 14:33:51 +0100},
biburl = {https://dblp.org/rec/conf/innovations/DeNS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenJRS22,
author = {Xi Chen and
Yaonan Jin and
Tim Randolph and
Rocco A. Servedio},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {Average-Case Subset Balancing Problems},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {743--778},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.33},
doi = {10.1137/1.9781611977073.33},
timestamp = {Tue, 22 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenJRS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenDLSS22,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {Near-Optimal Average-Case Approximate Trace Reconstruction from Few
Traces},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {779--821},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.34},
doi = {10.1137/1.9781611977073.34},
timestamp = {Tue, 12 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenDLSS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DeNS22,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {Approximating Sumset Size},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {2339--2357},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.94},
doi = {10.1137/1.9781611977073.94},
timestamp = {Tue, 12 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/DeNS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2202-05096,
author = {Daniel Hsu and
Clayton Sanford and
Rocco A. Servedio and
Emmanouil V. Vlatakis{-}Gkaragkounis},
title = {Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals},
journal = {CoRR},
volume = {abs/2202.05096},
year = {2022},
url = {https://arxiv.org/abs/2202.05096},
eprinttype = {arXiv},
eprint = {2202.05096},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2202-05096.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-03292,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
title = {Approximate Trace Reconstruction from a Single Trace},
journal = {CoRR},
volume = {abs/2211.03292},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.03292},
doi = {10.48550/ARXIV.2211.03292},
eprinttype = {arXiv},
eprint = {2211.03292},
timestamp = {Mon, 30 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-03292.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ServedioT21,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Mary Wootters and
Laura Sanit{\`{a}}},
title = {Deterministic Approximate Counting of Polynomial Threshold Functions
via a Derandomized Regularity Lemma},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2021, August 16-18, 2021, University
of Washington, Seattle, Washington, {USA} (Virtual Conference)},
series = {LIPIcs},
volume = {207},
pages = {37:1--37:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.37},
doi = {10.4230/LIPICS.APPROX/RANDOM.2021.37},
timestamp = {Tue, 21 Sep 2021 09:36:32 +0200},
biburl = {https://dblp.org/rec/conf/approx/ServedioT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BlasiokIJLSV21,
author = {Jaroslaw Blasiok and
Peter Ivanov and
Yaonan Jin and
Chin Ho Lee and
Rocco A. Servedio and
Emanuele Viola},
editor = {Mary Wootters and
Laura Sanit{\`{a}}},
title = {Fourier Growth of Structured {\(\mathbb{F}\)}\({}_{\mbox{2}}\)-Polynomials
and Applications},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2021, August 16-18, 2021, University
of Washington, Seattle, Washington, {USA} (Virtual Conference)},
series = {LIPIcs},
volume = {207},
pages = {53:1--53:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.53},
doi = {10.4230/LIPICS.APPROX/RANDOM.2021.53},
timestamp = {Tue, 21 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/BlasiokIJLSV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/BennettDSV21,
author = {Huck Bennett and
Anindya De and
Rocco A. Servedio and
Emmanouil{-}Vasileios Vlatakis{-}Gkaragkounis},
editor = {Mikhail Belkin and
Samory Kpotufe},
title = {Reconstructing weighted voting schemes from partial information about
their power indices},
booktitle = {Conference on Learning Theory, {COLT} 2021, 15-19 August 2021, Boulder,
Colorado, {USA}},
series = {Proceedings of Machine Learning Research},
volume = {134},
pages = {500--565},
publisher = {{PMLR}},
year = {2021},
url = {http://proceedings.mlr.press/v134/bennett21a.html},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/BennettDSV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/DeS21,
author = {Anindya De and
Rocco A. Servedio},
editor = {Mikhail Belkin and
Samory Kpotufe},
title = {Weak learning convex sets under normal distributions},
booktitle = {Conference on Learning Theory, {COLT} 2021, 15-19 August 2021, Boulder,
Colorado, {USA}},
series = {Proceedings of Machine Learning Research},
volume = {134},
pages = {1399--1428},
publisher = {{PMLR}},
year = {2021},
url = {http://proceedings.mlr.press/v134/de21a.html},
timestamp = {Wed, 25 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/DeS21.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 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/DeOS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/HsuSSV21,
author = {Daniel Hsu and
Clayton Sanford and
Rocco A. Servedio and
Emmanouil V. Vlatakis{-}Gkaragkounis},
editor = {Mikhail Belkin and
Samory Kpotufe},
title = {On the Approximation Power of Two-Layer Networks of Random ReLUs},
booktitle = {Conference on Learning Theory, {COLT} 2021, 15-19 August 2021, Boulder,
Colorado, {USA}},
series = {Proceedings of Machine Learning Research},
volume = {134},
pages = {2423--2461},
publisher = {{PMLR}},
year = {2021},
url = {http://proceedings.mlr.press/v134/hsu21a.html},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/HsuSSV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/0001DLSS21,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
editor = {James R. Lee},
title = {Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime},
booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS}
2021, January 6-8, 2021, Virtual Conference},
series = {LIPIcs},
volume = {185},
pages = {20:1--20:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.20},
doi = {10.4230/LIPICS.ITCS.2021.20},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/0001DLSS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/DeNS21,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
editor = {James R. Lee},
title = {Quantitative Correlation Inequalities via Semigroup Interpolation},
booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS}
2021, January 6-8, 2021, Virtual Conference},
series = {LIPIcs},
volume = {185},
pages = {69:1--69:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.69},
doi = {10.4230/LIPICS.ITCS.2021.69},
timestamp = {Thu, 04 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/DeNS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenDLSS21,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
editor = {D{\'{a}}niel Marx},
title = {Polynomial-time trace reconstruction in the smoothed complexity model},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {54--73},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.5},
doi = {10.1137/1.9781611976465.5},
timestamp = {Thu, 15 Jul 2021 13:48:55 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenDLSS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2102-02336,
author = {Daniel Hsu and
Clayton Sanford and
Rocco A. Servedio and
Emmanouil V. Vlatakis{-}Gkaragkounis},
title = {On the Approximation Power of Two-Layer Networks of Random ReLUs},
journal = {CoRR},
volume = {abs/2102.02336},
year = {2021},
url = {https://arxiv.org/abs/2102.02336},
eprinttype = {arXiv},
eprint = {2102.02336},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2102-02336.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-2107-10797,
author = {Jaroslaw Blasiok and
Peter Ivanov and
Yaonan Jin and
Chin Ho Lee and
Rocco A. Servedio and
Emanuele Viola},
title = {Fourier growth of structured {\textdollar}{\textbackslash}mathbb\{F\}{\_}2{\textdollar}-polynomials
and applications},
journal = {CoRR},
volume = {abs/2107.10797},
year = {2021},
url = {https://arxiv.org/abs/2107.10797},
eprinttype = {arXiv},
eprint = {2107.10797},
timestamp = {Thu, 29 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2107-10797.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2107-11530,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
title = {Near-Optimal Average-Case Approximate Trace Reconstruction from Few
Traces},
journal = {CoRR},
volume = {abs/2107.11530},
year = {2021},
url = {https://arxiv.org/abs/2107.11530},
eprinttype = {arXiv},
eprint = {2107.11530},
timestamp = {Thu, 29 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2107-11530.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2107-12367,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Approximating Sumset Size},
journal = {CoRR},
volume = {abs/2107.12367},
year = {2021},
url = {https://arxiv.org/abs/2107.12367},
eprinttype = {arXiv},
eprint = {2107.12367},
timestamp = {Fri, 30 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2107-12367.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2109-03107,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Convex Influences},
journal = {CoRR},
volume = {abs/2109.03107},
year = {2021},
url = {https://arxiv.org/abs/2109.03107},
eprinttype = {arXiv},
eprint = {2109.03107},
timestamp = {Mon, 20 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2109-03107.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-14607,
author = {Xi Chen and
Yaonan Jin and
Tim Randolph and
Rocco A. Servedio},
title = {Average-Case Subset Balancing Problems},
journal = {CoRR},
volume = {abs/2110.14607},
year = {2021},
url = {https://arxiv.org/abs/2110.14607},
eprinttype = {arXiv},
eprint = {2110.14607},
timestamp = {Tue, 22 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-14607.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-04590,
author = {Philip M. Long and
Rocco A. Servedio},
title = {The perils of being unhinged: On the accuracy of classifiers minimizing
a noise-robust convex loss},
journal = {CoRR},
volume = {abs/2112.04590},
year = {2021},
url = {https://arxiv.org/abs/2112.04590},
eprinttype = {arXiv},
eprint = {2112.04590},
timestamp = {Mon, 13 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-04590.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BlasiokIJLSV21,
author = {Jaroslaw Blasiok and
Peter Ivanov and
Yaonan Jin and
Chin Ho Lee and
Rocco A. Servedio and
Emanuele Viola},
title = {Fourier growth of structured {\(\mathbb{F}\)}\({}_{\mbox{2}}\)-polynomials
and applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR21-110}},
year = {2021},
url = {https://eccc.weizmann.ac.il/report/2021/110},
eprinttype = {ECCC},
eprint = {TR21-110},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BlasiokIJLSV21.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}
}
@inproceedings{DBLP:conf/soda/CanonneDS20,
author = {Cl{\'{e}}ment L. Canonne and
Anindya De and
Rocco A. Servedio},
editor = {Shuchi Chawla},
title = {Learning from satisfying assignments under continuous distributions},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
pages = {82--101},
publisher = {{SIAM}},
year = {2020},
url = {https://doi.org/10.1137/1.9781611975994.6},
doi = {10.1137/1.9781611975994.6},
timestamp = {Thu, 15 Jul 2021 13:48:53 +0200},
biburl = {https://dblp.org/rec/conf/soda/CanonneDS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenRSS20,
author = {Xi Chen and
Tim Randolph and
Rocco A. Servedio and
Timothy Sun},
editor = {Shuchi Chawla},
title = {A Lower Bound on Cycle-Finding in Sparse Digraphs},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
pages = {2936--2952},
publisher = {{SIAM}},
year = {2020},
url = {https://doi.org/10.1137/1.9781611975994.178},
doi = {10.1137/1.9781611975994.178},
timestamp = {Tue, 22 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenRSS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/0001DS20,
author = {Xue Chen and
Anindya De and
Rocco A. Servedio},
editor = {Konstantin Makarychev and
Yury Makarychev and
Madhur Tulsiani and
Gautam Kamath and
Julia Chuzhoy},
title = {Testing noisy linear functions for sparsity},
booktitle = {Proceedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
pages = {610--623},
publisher = {{ACM}},
year = {2020},
url = {https://doi.org/10.1145/3357713.3384239},
doi = {10.1145/3357713.3384239},
timestamp = {Mon, 18 Dec 2023 07:33:37 +0100},
biburl = {https://dblp.org/rec/conf/stoc/0001DS20.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-2007-09599,
author = {Huck Bennett and
Anindya De and
Rocco A. Servedio and
Emmanouil{-}Vasileios Vlatakis{-}Gkaragkounis},
title = {Reconstructing weighted voting schemes from partial information about
their power indices},
journal = {CoRR},
volume = {abs/2007.09599},
year = {2020},
url = {https://arxiv.org/abs/2007.09599},
eprinttype = {arXiv},
eprint = {2007.09599},
timestamp = {Tue, 28 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2007-09599.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2008-12386,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
title = {Polynomial-time trace reconstruction in the smoothed complexity model},
journal = {CoRR},
volume = {abs/2008.12386},
year = {2020},
url = {https://arxiv.org/abs/2008.12386},
eprinttype = {arXiv},
eprint = {2008.12386},
timestamp = {Thu, 04 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2008-12386.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2012-02844,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
title = {Polynomial-time trace reconstruction in the low deletion rate regime},
journal = {CoRR},
volume = {abs/2012.02844},
year = {2020},
url = {https://arxiv.org/abs/2012.02844},
eprinttype = {arXiv},
eprint = {2012.02844},
timestamp = {Thu, 04 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2012-02844.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2012-12216,
author = {Anindya De and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Quantitative Correlation Inequalities via Semigroup Interpolation},
journal = {CoRR},
volume = {abs/2012.12216},
year = {2020},
url = {https://arxiv.org/abs/2012.12216},
eprinttype = {arXiv},
eprint = {2012.12216},
timestamp = {Tue, 05 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2012-12216.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/LiuCSSX19,
author = {Zhengyang Liu and
Xi Chen and
Rocco A. Servedio and
Ying Sheng and
Jinyu Xie},
title = {Distribution-free Junta Testing},
journal = {{ACM} Trans. Algorithms},
volume = {15},
number = {1},
pages = {1:1--1:23},
year = {2019},
url = {https://doi.org/10.1145/3264434},
doi = {10.1145/3264434},
timestamp = {Fri, 17 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/LiuCSSX19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/Ban0SS19,
author = {Frank Ban and
Xi Chen and
Rocco A. Servedio and
Sandip Sinha},
editor = {Dimitris Achlioptas and
L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
title = {Efficient Average-Case Population Recovery in the Presence of Insertions
and Deletions},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2019, September 20-22, 2019, Massachusetts
Institute of Technology, Cambridge, MA, {USA}},
series = {LIPIcs},
volume = {145},
pages = {44:1--44:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.44},
doi = {10.4230/LIPICS.APPROX-RANDOM.2019.44},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/Ban0SS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ServedioT19,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Dimitris Achlioptas and
L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
title = {Improved Pseudorandom Generators from Pseudorandom Multi-Switching
Lemmas},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2019, September 20-22, 2019, Massachusetts
Institute of Technology, Cambridge, MA, {USA}},
series = {LIPIcs},
volume = {145},
pages = {45:1--45:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.45},
doi = {10.4230/LIPICS.APPROX-RANDOM.2019.45},
timestamp = {Tue, 17 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/ServedioT19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ChattopadhyayDS19,
author = {Eshan Chattopadhyay and
Anindya De and
Rocco A. Servedio},
editor = {Amir Shpilka},
title = {Simple and Efficient Pseudorandom Generators from Gaussian Processes},
booktitle = {34th Computational Complexity Conference, {CCC} 2019, July 18-20,
2019, New Brunswick, NJ, {USA}},
series = {LIPIcs},
volume = {137},
pages = {4:1--4:33},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.CCC.2019.4},
doi = {10.4230/LIPICS.CCC.2019.4},
timestamp = {Thu, 02 Feb 2023 13:27:04 +0100},
biburl = {https://dblp.org/rec/conf/coco/ChattopadhyayDS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ban0FSS19,
author = {Frank Ban and
Xi Chen and
Adam Freilich and
Rocco A. Servedio and
Sandip Sinha},
editor = {David Zuckerman},
title = {Beyond Trace Reconstruction: Population Recovery from the Deletion
Channel},
booktitle = {60th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2019, Baltimore, Maryland, USA, November 9-12, 2019},
pages = {745--768},
publisher = {{IEEE} Computer Society},
year = {2019},
url = {https://doi.org/10.1109/FOCS.2019.00050},
doi = {10.1109/FOCS.2019.00050},
timestamp = {Tue, 07 Jan 2020 13:25:31 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ban0FSS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/DeLS19,
author = {Anindya De and
Philip M. Long and
Rocco A. Servedio},
editor = {Avrim Blum},
title = {Density Estimation for Shift-Invariant Multidimensional Distributions},
booktitle = {10th Innovations in Theoretical Computer Science Conference, {ITCS}
2019, January 10-12, 2019, San Diego, California, {USA}},
series = {LIPIcs},
volume = {124},
pages = {28:1--28:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2019.28},
doi = {10.4230/LIPICS.ITCS.2019.28},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/DeLS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ServedioT19,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Timothy M. Chan},
title = {Pseudorandomness for read-k {DNF} formulas},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {621--638},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.39},
doi = {10.1137/1.9781611975482.39},
timestamp = {Thu, 15 Jul 2021 13:49:01 +0200},
biburl = {https://dblp.org/rec/conf/soda/ServedioT19.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 17:42:26 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ODonnellST19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-05532,
author = {Frank Ban and
Xi Chen and
Adam Freilich and
Rocco A. Servedio and
Sandip Sinha},
title = {Beyond trace reconstruction: Population recovery from the deletion
channel},
journal = {CoRR},
volume = {abs/1904.05532},
year = {2019},
url = {http://arxiv.org/abs/1904.05532},
eprinttype = {arXiv},
eprint = {1904.05532},
timestamp = {Sat, 23 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-05532.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-01619,
author = {Cl{\'{e}}ment L. Canonne and
Anindya De and
Rocco A. Servedio},
title = {Learning from satisfying assignments under continuous distributions},
journal = {CoRR},
volume = {abs/1907.01619},
year = {2019},
url = {http://arxiv.org/abs/1907.01619},
eprinttype = {arXiv},
eprint = {1907.01619},
timestamp = {Mon, 08 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-01619.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-05964,
author = {Frank Ban and
Xi Chen and
Rocco A. Servedio and
Sandip Sinha},
title = {Efficient average-case population recovery in the presence of insertions
and deletions},
journal = {CoRR},
volume = {abs/1907.05964},
year = {2019},
url = {http://arxiv.org/abs/1907.05964},
eprinttype = {arXiv},
eprint = {1907.05964},
timestamp = {Tue, 07 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-05964.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-12106,
author = {Xi Chen and
Tim Randolph and
Rocco A. Servedio and
Timothy Sun},
title = {A Lower Bound on Cycle-Finding in Sparse Digraphs},
journal = {CoRR},
volume = {abs/1907.12106},
year = {2019},
url = {http://arxiv.org/abs/1907.12106},
eprinttype = {arXiv},
eprint = {1907.12106},
timestamp = {Tue, 22 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-12106.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-00178,
author = {Anindya De and
Rocco A. Servedio},
title = {Kruskal-Katona for convex sets, with applications},
journal = {CoRR},
volume = {abs/1911.00178},
year = {2019},
url = {http://arxiv.org/abs/1911.00178},
eprinttype = {arXiv},
eprint = {1911.00178},
timestamp = {Mon, 11 Nov 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-00178.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-00911,
author = {Xue Chen and
Anindya De and
Rocco A. Servedio},
title = {Testing noisy linear functions for sparsity},
journal = {CoRR},
volume = {abs/1911.00911},
year = {2019},
url = {http://arxiv.org/abs/1911.00911},
eprinttype = {arXiv},
eprint = {1911.00911},
timestamp = {Sat, 02 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-00911.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/ChenSTWX18,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten and
Jinyu Xie},
title = {Settling the Query Complexity of Non-adaptive Junta Testing},
journal = {J. {ACM}},
volume = {65},
number = {6},
pages = {40:1--40:18},
year = {2018},
url = {https://doi.org/10.1145/3213772},
doi = {10.1145/3213772},
timestamp = {Thu, 09 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/ChenSTWX18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ServedioT18,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Eric Blais and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
David Steurer},
title = {Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and
Pseudorandom Generators for Depth-Two Circuits},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2018, August 20-22, 2018 - Princeton,
NJ, {USA}},
series = {LIPIcs},
volume = {116},
pages = {56:1--56:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.56},
doi = {10.4230/LIPICS.APPROX-RANDOM.2018.56},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/ServedioT18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DeLS18,
author = {Anindya De and
Philip M. Long and
Rocco A. Servedio},
editor = {Mikkel Thorup},
title = {Learning Sums of Independent Random Variables with Sparse Collective
Support},
booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2018, Paris, France, October 7-9, 2018},
pages = {297--308},
publisher = {{IEEE} Computer Society},
year = {2018},
url = {https://doi.org/10.1109/FOCS.2018.00036},
doi = {10.1109/FOCS.2018.00036},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DeLS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LiuCSSX18,
author = {Zhengyang Liu and
Xi Chen and
Rocco A. Servedio and
Ying Sheng and
Jinyu Xie},
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {Distribution-free junta testing},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages = {749--759},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3188745.3188842},
doi = {10.1145/3188745.3188842},
timestamp = {Fri, 17 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LiuCSSX18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/coco/2018,
editor = {Rocco A. Servedio},
title = {33rd Computational Complexity Conference, {CCC} 2018, June 22-24,
2018, San Diego, CA, {USA}},
series = {LIPIcs},
volume = {102},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {http://www.dagstuhl.de/dagpub/978-3-95977-069-9},
isbn = {978-3-95977-069-9},
timestamp = {Thu, 02 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/2018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1801-03588,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
title = {Deterministic search for {CNF} satisfying assignments in almost polynomial
time},
journal = {CoRR},
volume = {abs/1801.03588},
year = {2018},
url = {http://arxiv.org/abs/1801.03588},
eprinttype = {arXiv},
eprint = {1801.03588},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1801-03588.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1801-03590,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
title = {Improved pseudorandom generators from pseudorandom multi-switching
lemmas},
journal = {CoRR},
volume = {abs/1801.03590},
year = {2018},
url = {http://arxiv.org/abs/1801.03590},
eprinttype = {arXiv},
eprint = {1801.03590},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1801-03590.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1802-04859,
author = {Xi Chen and
Zhengyang Liu and
Rocco A. Servedio and
Ying Sheng and
Jinyu Xie},
title = {Distribution-free Junta Testing},
journal = {CoRR},
volume = {abs/1802.04859},
year = {2018},
url = {http://arxiv.org/abs/1802.04859},
eprinttype = {arXiv},
eprint = {1802.04859},
timestamp = {Fri, 17 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1802-04859.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1803-04553,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
title = {Luby-Veli{\v{c}}kovi{\'{c}}-Wigderson revisited: Improved correlation
bounds and pseudorandom generators for depth-two circuits},
journal = {CoRR},
volume = {abs/1803.04553},
year = {2018},
url = {http://arxiv.org/abs/1803.04553},
eprinttype = {arXiv},
eprint = {1803.04553},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1803-04553.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1807-07013,
author = {Anindya De and
Philip M. Long and
Rocco A. Servedio},
title = {Learning Sums of Independent Random Variables with Sparse Collective
Support},
journal = {CoRR},
volume = {abs/1807.07013},
year = {2018},
url = {http://arxiv.org/abs/1807.07013},
eprinttype = {arXiv},
eprint = {1807.07013},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1807-07013.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-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-1811-03744,
author = {Anindya De and
Philip M. Long and
Rocco A. Servedio},
title = {Density estimation for shift-invariant multidimensional distributions},
journal = {CoRR},
volume = {abs/1811.03744},
year = {2018},
url = {http://arxiv.org/abs/1811.03744},
eprinttype = {arXiv},
eprint = {1811.03744},
timestamp = {Fri, 23 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1811-03744.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChattopadhyayDS18,
author = {Eshan Chattopadhyay and
Anindya De and
Rocco A. Servedio},
title = {Simple and efficient pseudorandom generators from Gaussian processes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-100}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/100},
eprinttype = {ECCC},
eprint = {TR18-100},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChattopadhyayDS18.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/geb/DeDS17,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {The Inverse Shapley value problem},
journal = {Games Econ. Behav.},
volume = {105},
pages = {122--147},
year = {2017},
url = {https://doi.org/10.1016/j.geb.2017.06.004},
doi = {10.1016/J.GEB.2017.06.004},
timestamp = {Sat, 22 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/geb/DeDS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/HastadRST17,
author = {Johan H{\aa}stad and
Benjamin Rossman and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {An Average-Case Depth Hierarchy Theorem for Boolean Circuits},
journal = {J. {ACM}},
volume = {64},
number = {5},
pages = {35:1--35:27},
year = {2017},
url = {https://doi.org/10.1145/3095799},
doi = {10.1145/3095799},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/HastadRST17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/0001FSS17,
author = {Xi Chen and
Adam Freilich and
Rocco A. Servedio and
Timothy Sun},
editor = {Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
David Williamson and
Santosh S. Vempala},
title = {Sample-Based High-Dimensional Convexity Testing},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2017, August 16-18, 2017, Berkeley,
CA, {USA}},
series = {LIPIcs},
volume = {81},
pages = {37:1--37:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.37},
doi = {10.4230/LIPICS.APPROX-RANDOM.2017.37},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/0001FSS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/0001STW17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten},
editor = {Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
David Williamson and
Santosh S. Vempala},
title = {Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2017, August 16-18, 2017, Berkeley,
CA, {USA}},
series = {LIPIcs},
volume = {81},
pages = {38:1--38:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.38},
doi = {10.4230/LIPICS.APPROX-RANDOM.2017.38},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/0001STW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ChenSTWX17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten and
Jinyu Xie},
editor = {Ryan O'Donnell},
title = {Settling the Query Complexity of Non-Adaptive Junta Testing},
booktitle = {32nd Computational Complexity Conference, {CCC} 2017, July 6-9, 2017,
Riga, Latvia},
series = {LIPIcs},
volume = {79},
pages = {26:1--26:19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.CCC.2017.26},
doi = {10.4230/LIPICS.CCC.2017.26},
timestamp = {Thu, 02 Feb 2023 13:27:05 +0100},
biburl = {https://dblp.org/rec/conf/coco/ChenSTWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ServedioT17,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Chris Umans},
title = {Deterministic Search for {CNF} Satisfying Assignments in Almost Polynomial
Time},
booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2017, Berkeley, CA, USA, October 15-17, 2017},
pages = {813--823},
publisher = {{IEEE} Computer Society},
year = {2017},
url = {https://doi.org/10.1109/FOCS.2017.80},
doi = {10.1109/FOCS.2017.80},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ServedioT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ServedioT17a,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Chris Umans},
title = {Fooling Intersections of Low-Weight Halfspaces},
booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2017, Berkeley, CA, USA, October 15-17, 2017},
pages = {824--835},
publisher = {{IEEE} Computer Society},
year = {2017},
url = {https://doi.org/10.1109/FOCS.2017.81},
doi = {10.1109/FOCS.2017.81},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ServedioT17a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/ServedioT17,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Christos H. Papadimitriou},
title = {What Circuit Classes Can Be Learned with Non-Trivial Savings?},
booktitle = {8th Innovations in Theoretical Computer Science Conference, {ITCS}
2017, January 9-11, 2017, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {67},
pages = {30:1--30:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2017.30},
doi = {10.4230/LIPICS.ITCS.2017.30},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/ServedioT17.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 = {Sun, 02 Jun 2019 21:10:31 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DeOS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenOS17,
author = {Xi Chen and
Igor C. Oliveira and
Rocco A. Servedio},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Addition is exponentially harder than counting for shallow monotone
circuits},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {1232--1245},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055425},
doi = {10.1145/3055399.3055425},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenOS17.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/ServedioT17,
author = {Rocco A. Servedio and
Li{-}Yang Tan},
title = {Fooling intersections of low-weight halfspaces},
journal = {CoRR},
volume = {abs/1704.04855},
year = {2017},
url = {http://arxiv.org/abs/1704.04855},
eprinttype = {arXiv},
eprint = {1704.04855},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ServedioT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenSTWX17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten and
Jinyu Xie},
title = {Settling the query complexity of non-adaptive junta testing},
journal = {CoRR},
volume = {abs/1704.06314},
year = {2017},
url = {http://arxiv.org/abs/1704.06314},
eprinttype = {arXiv},
eprint = {1704.06314},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenSTWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/0001STW17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten},
title = {Adaptivity is exponentially powerful for testing monotonicity of halfspaces},
journal = {CoRR},
volume = {abs/1706.05556},
year = {2017},
url = {http://arxiv.org/abs/1706.05556},
eprinttype = {arXiv},
eprint = {1706.05556},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/0001STW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenFSS17,
author = {Xi Chen and
Adam Freilich and
Rocco A. Servedio and
Timothy Sun},
title = {Sample-based high-dimensional convexity testing},
journal = {CoRR},
volume = {abs/1706.09362},
year = {2017},
url = {http://arxiv.org/abs/1706.09362},
eprinttype = {arXiv},
eprint = {1706.09362},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenFSS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenSTWX17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten and
Jinyu Xie},
title = {Settling the query complexity of non-adaptive junta testing},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-068}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/068},
eprinttype = {ECCC},
eprint = {TR17-068},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenSTWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/DeDS16,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {A Robust Khintchine Inequality, and Algorithms for Computing Optimal
Constants in Fourier Analysis and High-Dimensional Geometry},
journal = {{SIAM} J. Discret. Math.},
volume = {30},
number = {2},
pages = {1058--1094},
year = {2016},
url = {https://doi.org/10.1137/130919143},
doi = {10.1137/130919143},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/DeDS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/GopalanSW16,
author = {Parikshit Gopalan and
Rocco A. Servedio and
Avi Wigderson},
editor = {Ran Raz},
title = {Degree and Sensitivity: Tails of Two Distributions},
booktitle = {31st Conference on Computational Complexity, {CCC} 2016, May 29 to
June 1, 2016, Tokyo, Japan},
series = {LIPIcs},
volume = {50},
pages = {13:1--13:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.CCC.2016.13},
doi = {10.4230/LIPICS.CCC.2016.13},
timestamp = {Thu, 02 Feb 2023 13:27:05 +0100},
biburl = {https://dblp.org/rec/conf/coco/GopalanSW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/GopalanNSTW16,
author = {Parikshit Gopalan and
Noam Nisan and
Rocco A. Servedio and
Kunal Talwar and
Avi Wigderson},
editor = {Madhu Sudan},
title = {Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity
Functions},
booktitle = {Proceedings of the 2016 {ACM} Conference on Innovations in Theoretical
Computer Science, Cambridge, MA, USA, January 14-16, 2016},
pages = {59--70},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2840728.2840738},
doi = {10.1145/2840728.2840738},
timestamp = {Tue, 14 Jun 2022 13:12:41 +0200},
biburl = {https://dblp.org/rec/conf/innovations/GopalanNSTW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenOST16,
author = {Xi Chen and
Igor C. Oliveira and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Daniel Wichs and
Yishay Mansour},
title = {Near-optimal small-depth lower bounds for small distance connectivity},
booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
pages = {612--625},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2897518.2897534},
doi = {10.1145/2897518.2897534},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenOST16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/PitassiRST16,
author = {Toniann Pitassi and
Benjamin Rossman and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Daniel Wichs and
Yishay Mansour},
title = {Poly-logarithmic Frege depth lower bounds via an expander switching
lemma},
booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
pages = {644--657},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2897518.2897637},
doi = {10.1145/2897518.2897637},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/PitassiRST16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/GopalanSTW16,
author = {Parikshit Gopalan and
Rocco A. Servedio and
Avishay Tal and
Avi Wigderson},
title = {Degree and Sensitivity: tails of two distributions},
journal = {CoRR},
volume = {abs/1604.07432},
year = {2016},
url = {http://arxiv.org/abs/1604.07432},
eprinttype = {arXiv},
eprint = {1604.07432},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/GopalanSTW16.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/GopalanSTW16,
author = {Parikshit Gopalan and
Rocco A. Servedio and
Avishay Tal and
Avi Wigderson},
title = {Degree and Sensitivity: tails of two distributions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-069}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/069},
eprinttype = {ECCC},
eprint = {TR16-069},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GopalanSTW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/DaskalakisDS15,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Learning Poisson Binomial Distributions},
journal = {Algorithmica},
volume = {72},
number = {1},
pages = {316--357},
year = {2015},
url = {https://doi.org/10.1007/s00453-015-9971-3},
doi = {10.1007/S00453-015-9971-3},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/DaskalakisDS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/RonS15,
author = {Dana Ron and
Rocco A. Servedio},
title = {Exponentially Improved Algorithms and Lower Bounds for Testing Signed
Majorities},
journal = {Algorithmica},
volume = {72},
number = {2},
pages = {400--429},
year = {2015},
url = {https://doi.org/10.1007/s00453-013-9858-0},
doi = {10.1007/S00453-013-9858-0},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/RonS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cjtcs/DiakonikolasJST16,
author = {Ilias Diakonikolas and
Ragesh Jaiswal and
Rocco A. Servedio and
Li{-}Yang Tan and
Andrew Wan},
title = {Noise Stable Halfspaces are Close to Very Small Juntas},
journal = {Chic. J. Theor. Comput. Sci.},
volume = {2015},
year = {2015},
url = {http://cjtcs.cs.uchicago.edu/articles/2015/4/contents.html},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cjtcs/DiakonikolasJST16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CanonneRS15,
author = {Cl{\'{e}}ment L. Canonne and
Dana Ron and
Rocco A. Servedio},
title = {Testing Probability Distributions using Conditional Samples},
journal = {{SIAM} J. Comput.},
volume = {44},
number = {3},
pages = {540--616},
year = {2015},
url = {https://doi.org/10.1137/130945508},
doi = {10.1137/130945508},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CanonneRS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sigact/RossmanST15,
author = {Benjamin Rossman and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles,
and Boolean Circuits},
journal = {{SIGACT} News},
volume = {46},
number = {4},
pages = {50--68},
year = {2015},
url = {https://doi.org/10.1145/2852040.2852052},
doi = {10.1145/2852040.2852052},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/RossmanST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BlaisCOST15,
author = {Eric Blais and
Cl{\'{e}}ment L. Canonne and
Igor C. Oliveira and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Naveen Garg and
Klaus Jansen and
Anup Rao and
Jos{\'{e}} D. P. Rolim},
title = {Learning Circuits with few Negations},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2015, August 24-26, 2015, Princeton,
NJ, {USA}},
series = {LIPIcs},
volume = {40},
pages = {512--527},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.512},
doi = {10.4230/LIPICS.APPROX-RANDOM.2015.512},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/BlaisCOST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ServedioTW15,
author = {Rocco A. Servedio and
Li{-}Yang Tan and
John Wright},
editor = {David Zuckerman},
title = {Adaptivity Helps for Testing Juntas},
booktitle = {30th Conference on Computational Complexity, {CCC} 2015, June 17-19,
2015, Portland, Oregon, {USA}},
series = {LIPIcs},
volume = {33},
pages = {264--279},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.CCC.2015.264},
doi = {10.4230/LIPICS.CCC.2015.264},
timestamp = {Thu, 02 Feb 2023 13:27:06 +0100},
biburl = {https://dblp.org/rec/conf/coco/ServedioTW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RossmanST15,
author = {Benjamin Rossman and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Venkatesan Guruswami},
title = {An Average-Case Depth Hierarchy Theorem for Boolean Circuits},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {1030--1048},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.67},
doi = {10.1109/FOCS.2015.67},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/RossmanST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DeDS15,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
editor = {Piotr Indyk},
title = {Learning from satisfying assignments},
booktitle = {Proceedings of the Twenty-Sixth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2015, San Diego, CA, USA, January 4-6, 2015},
pages = {478--497},
publisher = {{SIAM}},
year = {2015},
url = {https://doi.org/10.1137/1.9781611973730.33},
doi = {10.1137/1.9781611973730.33},
timestamp = {Tue, 02 Feb 2021 17:07:30 +0100},
biburl = {https://dblp.org/rec/conf/soda/DeDS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenDST15,
author = {Xi Chen and
Anindya De and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {Boolean Function Monotonicity Testing Requires (Almost) n\({}^{\mbox{1/2}}\)
Non-adaptive Queries},
booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
pages = {519--528},
publisher = {{ACM}},
year = {2015},
url = {https://doi.org/10.1145/2746539.2746570},
doi = {10.1145/2746539.2746570},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChenDST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/2015,
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
publisher = {{ACM}},
year = {2015},
url = {http://dl.acm.org/citation.cfm?id=2746539},
isbn = {978-1-4503-3536-2},
timestamp = {Wed, 10 Jun 2015 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/2015.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/RossmanST15,
author = {Benjamin Rossman and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {An average-case depth hierarchy theorem for Boolean circuits},
journal = {CoRR},
volume = {abs/1504.03398},
year = {2015},
url = {http://arxiv.org/abs/1504.03398},
eprinttype = {arXiv},
eprint = {1504.03398},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/RossmanST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/GopalanNSTW15,
author = {Parikshit Gopalan and
Noam Nisan and
Rocco A. Servedio and
Kunal Talwar and
Avi Wigderson},
title = {Smooth Boolean functions are easy: efficient algorithms for low-sensitivity
functions},
journal = {CoRR},
volume = {abs/1508.02420},
year = {2015},
url = {http://arxiv.org/abs/1508.02420},
eprinttype = {arXiv},
eprint = {1508.02420},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/GopalanNSTW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenOS15,
author = {Xi Chen and
Igor C. Oliveira and
Rocco A. Servedio},
title = {Addition is exponentially harder than counting for shallow monotone
circuits},
journal = {CoRR},
volume = {abs/1508.03061},
year = {2015},
url = {http://arxiv.org/abs/1508.03061},
eprinttype = {arXiv},
eprint = {1508.03061},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenOS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenOST15,
author = {Xi Chen and
Igor C. Oliveira and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Near-optimal small-depth lower bounds for small distance connectivity},
journal = {CoRR},
volume = {abs/1509.07476},
year = {2015},
url = {http://arxiv.org/abs/1509.07476},
eprinttype = {arXiv},
eprint = {1509.07476},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenOST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenOS15,
author = {Xi Chen and
Igor Carboni Oliveira and
Rocco A. Servedio},
title = {Addition is exponentially harder than counting for shallow monotone
circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-123}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/123},
eprinttype = {ECCC},
eprint = {TR15-123},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenOS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GopalanNSTW15,
author = {Parikshit Gopalan and
Noam Nisan and
Rocco A. Servedio and
Kunal Talwar and
Avi Wigderson},
title = {Smooth Boolean functions are easy: efficient algorithms for low-sensitivity
functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-131}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/131},
eprinttype = {ECCC},
eprint = {TR15-131},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GopalanNSTW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/RossmanST15,
author = {Benjamin Rossman and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {An average-case depth hierarchy theorem for Boolean circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-065}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/065},
eprinttype = {ECCC},
eprint = {TR15-065},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/RossmanST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/DeDFS14,
author = {Anindya De and
Ilias Diakonikolas and
Vitaly Feldman and
Rocco A. Servedio},
title = {Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight
Approximation of Halfspaces},
journal = {J. {ACM}},
volume = {61},
number = {2},
pages = {11:1--11:36},
year = {2014},
url = {https://doi.org/10.1145/2590772},
doi = {10.1145/2590772},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/DeDFS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/DiakonikolasRST14,
author = {Ilias Diakonikolas and
Prasad Raghavendra and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Average Sensitivity and Noise Sensitivity of Polynomial Threshold
Functions},
journal = {{SIAM} J. Comput.},
volume = {43},
number = {1},
pages = {231--253},
year = {2014},
url = {https://doi.org/10.1137/110855223},
doi = {10.1137/110855223},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/DiakonikolasRST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/LongS14,
author = {Philip M. Long and
Rocco A. Servedio},
title = {On the Weight of Halfspaces over Hamming Balls},
journal = {{SIAM} J. Discret. Math.},
volume = {28},
number = {3},
pages = {1035--1061},
year = {2014},
url = {https://doi.org/10.1137/120868402},
doi = {10.1137/120868402},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/LongS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DiakonikolasSTW14,
author = {Ilias Diakonikolas and
Rocco A. Servedio and
Li{-}Yang Tan and
Andrew Wan},
title = {A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial
Threshold Functions},
journal = {Theory Comput.},
volume = {10},
pages = {27--53},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a002},
doi = {10.4086/TOC.2014.V010A002},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DiakonikolasSTW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/DaskalakisDS14,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Learning \emph{k}-Modal Distributions via Testing},
journal = {Theory Comput.},
volume = {10},
pages = {535--570},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a020},
doi = {10.4086/TOC.2014.V010A020},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/DaskalakisDS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/DeDS14,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Deterministic Approximate Counting for Juntas of Degree-2 Polynomial
Threshold Functions},
booktitle = {{IEEE} 29th Conference on Computational Complexity, {CCC} 2014, Vancouver,
BC, Canada, June 11-13, 2014},
pages = {229--240},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/CCC.2014.31},
doi = {10.1109/CCC.2014.31},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/DeDS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenST14,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {New Algorithms and Lower Bounds for Monotonicity Testing},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {286--295},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.38},
doi = {10.1109/FOCS.2014.38},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/BlaisHST14,
author = {Eric Blais and
Johan H{\aa}stad and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Javier Esparza and
Pierre Fraigniaud and
Thore Husfeldt and
Elias Koutsoupias},
title = {On {DNF} Approximators for Monotone Boolean Functions},
booktitle = {Automata, Languages, and Programming - 41st International Colloquium,
{ICALP} 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {8572},
pages = {235--246},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-662-43948-7\_20},
doi = {10.1007/978-3-662-43948-7\_20},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/BlaisHST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/ChanDSS14,
author = {Siu On Chan and
Ilias Diakonikolas and
Rocco A. Servedio and
Xiaorui Sun},
editor = {Zoubin Ghahramani and
Max Welling and
Corinna Cortes and
Neil D. Lawrence and
Kilian Q. Weinberger},
title = {Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width
Histograms},
booktitle = {Advances in Neural Information Processing Systems 27: Annual Conference
on Neural Information Processing Systems 2014, December 8-13 2014,
Montreal, Quebec, Canada},
pages = {1844--1852},
year = {2014},
url = {https://proceedings.neurips.cc/paper/2014/hash/287e03db1d99e0ec2edb90d079e142f3-Abstract.html},
timestamp = {Thu, 14 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/nips/ChanDSS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DaskalakisDDMS14,
author = {Constantinos Daskalakis and
Anindya De and
Ilias Diakonikolas and
Ankur Moitra and
Rocco A. Servedio},
editor = {Chandra Chekuri},
title = {A Polynomial-time Approximation Scheme for Fault-tolerant Distributed
Storage},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {628--644},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.48},
doi = {10.1137/1.9781611973402.48},
timestamp = {Tue, 02 Feb 2021 17:07:40 +0100},
biburl = {https://dblp.org/rec/conf/soda/DaskalakisDDMS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CanonneRS14,
author = {Cl{\'{e}}ment L. Canonne and
Dana Ron and
Rocco A. Servedio},
editor = {Chandra Chekuri},
title = {Testing equivalence between distributions using conditional samples},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {1174--1192},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.87},
doi = {10.1137/1.9781611973402.87},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/CanonneRS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChanDSS14,
author = {Siu On Chan and
Ilias Diakonikolas and
Rocco A. Servedio and
Xiaorui Sun},
editor = {David B. Shmoys},
title = {Efficient density estimation via piecewise polynomial approximation},
booktitle = {Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA,
May 31 - June 03, 2014},
pages = {604--613},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2591796.2591848},
doi = {10.1145/2591796.2591848},
timestamp = {Thu, 14 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChanDSS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DeS14,
author = {Anindya De and
Rocco A. Servedio},
editor = {David B. Shmoys},
title = {Efficient deterministic approximate counting for low-degree polynomial
threshold functions},
booktitle = {Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA,
May 31 - June 03, 2014},
pages = {832--841},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2591796.2591800},
doi = {10.1145/2591796.2591800},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DeS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BlaisCOST14,
author = {Eric Blais and
Cl{\'{e}}ment L. Canonne and
Igor C. Oliveira and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Learning circuits with few negations},
journal = {CoRR},
volume = {abs/1410.8420},
year = {2014},
url = {http://arxiv.org/abs/1410.8420},
eprinttype = {arXiv},
eprint = {1410.8420},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BlaisCOST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChanDSS14,
author = {Siu On Chan and
Ilias Diakonikolas and
Rocco A. Servedio and
Xiaorui Sun},
title = {Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width
Histograms},
journal = {CoRR},
volume = {abs/1411.0169},
year = {2014},
url = {http://arxiv.org/abs/1411.0169},
eprinttype = {arXiv},
eprint = {1411.0169},
timestamp = {Thu, 14 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChanDSS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenST14,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {New algorithms and lower bounds for monotonicity testing},
journal = {CoRR},
volume = {abs/1412.5655},
year = {2014},
url = {http://arxiv.org/abs/1412.5655},
eprinttype = {arXiv},
eprint = {1412.5655},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenDST14,
author = {Xi Chen and
Anindya De and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Boolean function monotonicity testing requires (almost) n\({}^{\mbox{1/2}}\)
non-adaptive queries},
journal = {CoRR},
volume = {abs/1412.5657},
year = {2014},
url = {http://arxiv.org/abs/1412.5657},
eprinttype = {arXiv},
eprint = {1412.5657},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenDST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BlaisCOST14,
author = {Eric Blais and
Cl{\'{e}}ment L. Canonne and
Igor Carboni Oliveira and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Learning circuits with few negations},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-144}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/144},
eprinttype = {ECCC},
eprint = {TR14-144},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BlaisCOST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/DiakonikolasS13,
author = {Ilias Diakonikolas and
Rocco A. Servedio},
title = {Improved Approximation of Linear Threshold Functions},
journal = {Comput. Complex.},
volume = {22},
number = {3},
pages = {623--677},
year = {2013},
url = {https://doi.org/10.1007/s00037-012-0045-5},
doi = {10.1007/S00037-012-0045-5},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/DiakonikolasS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jmlr/LongS13,
author = {Philip M. Long and
Rocco A. Servedio},
title = {Algorithms and hardness results for parallel large margin learning},
journal = {J. Mach. Learn. Res.},
volume = {14},
number = {1},
pages = {3105--3128},
year = {2013},
url = {https://dl.acm.org/doi/10.5555/2567709.2567760},
doi = {10.5555/2567709.2567760},
timestamp = {Thu, 02 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/LongS13.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/DeDS13,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
editor = {Fedor V. Fomin and
Rusins Freivalds and
Marta Z. Kwiatkowska and
David Peleg},
title = {A Robust Khintchine Inequality, and Algorithms for Computing Optimal
Constants in Fourier Analysis and High-Dimensional Geometry},
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 = {376--387},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-39206-1\_32},
doi = {10.1007/978-3-642-39206-1\_32},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/DeDS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icml/LongS13,
author = {Philip M. Long and
Rocco A. Servedio},
title = {Consistency versus Realizable H-Consistency for Multiclass Classification},
booktitle = {Proceedings of the 30th International Conference on Machine Learning,
{ICML} 2013, Atlanta, GA, USA, 16-21 June 2013},
series = {{JMLR} Workshop and Conference Proceedings},
volume = {28},
pages = {801--809},
publisher = {JMLR.org},
year = {2013},
url = {http://proceedings.mlr.press/v28/long13.html},
timestamp = {Wed, 29 May 2019 08:41:45 +0200},
biburl = {https://dblp.org/rec/conf/icml/LongS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/LongS13,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {Robert D. Kleinberg},
title = {Low-weight halfspaces for sparse boolean vectors},
booktitle = {Innovations in Theoretical Computer Science, {ITCS} '13, Berkeley,
CA, USA, January 9-12, 2013},
pages = {21--36},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2422436.2422440},
doi = {10.1145/2422436.2422440},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/LongS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RonS13,
author = {Dana Ron and
Rocco A. Servedio},
editor = {Sanjeev Khanna},
title = {Exponentially Improved Algorithms and Lower Bounds for Testing Signed
Majorities},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
2013},
pages = {1319--1336},
publisher = {{SIAM}},
year = {2013},
url = {https://doi.org/10.1137/1.9781611973105.96},
doi = {10.1137/1.9781611973105.96},
timestamp = {Tue, 02 Feb 2021 17:07:29 +0100},
biburl = {https://dblp.org/rec/conf/soda/RonS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChanDSS13,
author = {Siu On Chan and
Ilias Diakonikolas and
Rocco A. Servedio and
Xiaorui Sun},
editor = {Sanjeev Khanna},
title = {Learning mixtures of structured distributions over discrete domains},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
2013},
pages = {1380--1394},
publisher = {{SIAM}},
year = {2013},
url = {https://doi.org/10.1137/1.9781611973105.100},
doi = {10.1137/1.9781611973105.100},
timestamp = {Thu, 14 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChanDSS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DaskalakisDSVV13,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio and
Gregory Valiant and
Paul Valiant},
editor = {Sanjeev Khanna},
title = {Testing \emph{k}-Modal Distributions: Optimal Algorithms via Reductions},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
2013},
pages = {1833--1852},
publisher = {{SIAM}},
year = {2013},
url = {https://doi.org/10.1137/1.9781611973105.131},
doi = {10.1137/1.9781611973105.131},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DaskalakisDSVV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1305-3207,
author = {Siu On Chan and
Ilias Diakonikolas and
Rocco A. Servedio and
Xiaorui Sun},
title = {Efficient Density Estimation via Piecewise Polynomial Approximation},
journal = {CoRR},
volume = {abs/1305.3207},
year = {2013},
url = {http://arxiv.org/abs/1305.3207},
eprinttype = {arXiv},
eprint = {1305.3207},
timestamp = {Thu, 14 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1305-3207.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/DaskalakisDDMS13,
author = {Constantinos Daskalakis and
Anindya De and
Ilias Diakonikolas and
Ankur Moitra and
Rocco A. Servedio},
title = {A Polynomial-time Approximation Scheme for Fault-tolerant Distributed
Storage},
journal = {CoRR},
volume = {abs/1307.3621},
year = {2013},
url = {http://arxiv.org/abs/1307.3621},
eprinttype = {arXiv},
eprint = {1307.3621},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/DaskalakisDDMS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/DeDS13,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Deterministic Approximate Counting for Degree-{\textdollar}2{\textdollar}
Polynomial Threshold Functions},
journal = {CoRR},
volume = {abs/1311.7105},
year = {2013},
url = {http://arxiv.org/abs/1311.7105},
eprinttype = {arXiv},
eprint = {1311.7105},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/DeDS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/DeDS13a,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Deterministic Approximate Counting for Juntas of Degree-{\textdollar}2{\textdollar}
Polynomial Threshold Functions},
journal = {CoRR},
volume = {abs/1311.7115},
year = {2013},
url = {http://arxiv.org/abs/1311.7115},
eprinttype = {arXiv},
eprint = {1311.7115},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/DeDS13a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/DeS13,
author = {Anindya De and
Rocco A. Servedio},
title = {Efficient deterministic approximate counting for low-degree polynomial
threshold functions},
journal = {CoRR},
volume = {abs/1311.7178},
year = {2013},
url = {http://arxiv.org/abs/1311.7178},
eprinttype = {arXiv},
eprint = {1311.7178},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/DeS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeDS13,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Deterministic Approximate Counting for Juntas of Degree-2 Polynomial
Threshold Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-171}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/171},
eprinttype = {ECCC},
eprint = {TR13-171},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeDS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeDS13a,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Deterministic Approximate Counting for Degree-2 Polynomial Threshold
Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-172}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/172},
eprinttype = {ECCC},
eprint = {TR13-172},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeDS13a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeS13,
author = {Anindya De and
Rocco A. Servedio},
title = {Efficient deterministic approximate counting for low degree polynomial
threshold functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-173}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/173},
eprinttype = {ECCC},
eprint = {TR13-173},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/RonS13,
author = {Dana Ron and
Rocco A. Servedio},
title = {Exponentially improved algorithms and lower bounds for testing signed
majorities},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-096}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/096},
eprinttype = {ECCC},
eprint = {TR13-096},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/RonS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cacm/Servedio12,
author = {Rocco A. Servedio},
title = {A high-dimensional surprise: technical perspective},
journal = {Commun. {ACM}},
volume = {55},
number = {10},
pages = {89},
year = {2012},
url = {https://doi.org/10.1145/2347736.2347756},
doi = {10.1145/2347736.2347756},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cacm/Servedio12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ImmorlicaKMSU12,
author = {Nicole Immorlica and
Jonathan Katz and
Michael Mitzenmacher and
Rocco A. Servedio and
Chris Umans},
title = {Special Section on the Forty-First Annual {ACM} Symposium on Theory
of Computing {(STOC} 2009)},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {6},
pages = {1591--1592},
year = {2012},
url = {https://doi.org/10.1137/120973305},
doi = {10.1137/120973305},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ImmorlicaKMSU12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/DeDS12,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
editor = {Artur Czumaj and
Kurt Mehlhorn and
Andrew M. Pitts and
Roger Wattenhofer},
title = {The Inverse Shapley Value Problem},
booktitle = {Automata, Languages, and Programming - 39th International Colloquium,
{ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7391},
pages = {266--277},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31594-7\_23},
doi = {10.1007/978-3-642-31594-7\_23},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/DeDS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HardtRS12,
author = {Moritz Hardt and
Guy N. Rothblum and
Rocco A. Servedio},
editor = {Yuval Rabani},
title = {Private data release via learning thresholds},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {168--187},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.15},
doi = {10.1137/1.9781611973099.15},
timestamp = {Tue, 02 Feb 2021 17:07:31 +0100},
biburl = {https://dblp.org/rec/conf/soda/HardtRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DaskalakisDS12,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
editor = {Yuval Rabani},
title = {Learning \emph{k}-modal distributions via testing},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1371--1385},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.108},
doi = {10.1137/1.9781611973099.108},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DaskalakisDS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DaskalakisDS12,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
editor = {Howard J. Karloff and
Toniann Pitassi},
title = {Learning poisson binomial distributions},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
pages = {709--728},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2213977.2214042},
doi = {10.1145/2213977.2214042},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DaskalakisDS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DeDFS12,
author = {Anindya De and
Ilias Diakonikolas and
Vitaly Feldman and
Rocco A. Servedio},
editor = {Howard J. Karloff and
Toniann Pitassi},
title = {Nearly optimal solutions for the chow parameters problem and low-weight
approximation of halfspaces},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
pages = {729--746},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2213977.2214043},
doi = {10.1145/2213977.2214043},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DeDFS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:journals/jmlr/ServedioTT12,
author = {Rocco A. Servedio and
Li{-}Yang Tan and
Justin Thaler},
editor = {Shie Mannor and
Nathan Srebro and
Robert C. Williamson},
title = {Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial
Threshold Functions},
booktitle = {{COLT} 2012 - The 25th Annual Conference on Learning Theory, June
25-27, 2012, Edinburgh, Scotland},
series = {{JMLR} Proceedings},
volume = {23},
pages = {14.1--14.19},
publisher = {JMLR.org},
year = {2012},
url = {http://proceedings.mlr.press/v23/servedio12/servedio12.pdf},
timestamp = {Wed, 29 May 2019 08:41:46 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/ServedioTT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:journals/jmlr/HellersteinKSS12,
author = {Lisa Hellerstein and
Devorah Kletenik and
Linda Sellie and
Rocco A. Servedio},
editor = {Shie Mannor and
Nathan Srebro and
Robert C. Williamson},
title = {Tight Bounds on Proper Equivalence Query Learning of {DNF}},
booktitle = {{COLT} 2012 - The 25th Annual Conference on Learning Theory, June
25-27, 2012, Edinburgh, Scotland},
series = {{JMLR} Proceedings},
volume = {23},
pages = {31.1--31.18},
publisher = {JMLR.org},
year = {2012},
url = {http://proceedings.mlr.press/v23/hellerstein12/hellerstein12.pdf},
timestamp = {Wed, 29 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/HellersteinKSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/approx/2012,
editor = {Anupam Gupta and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Rocco A. Servedio},
title = {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},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32512-0},
doi = {10.1007/978-3-642-32512-0},
isbn = {978-3-642-32511-3},
timestamp = {Tue, 21 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/2012.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1202-6680,
author = {Ilias Diakonikolas and
Ragesh Jaiswal and
Rocco A. Servedio and
Li{-}Yang Tan and
Andrew Wan},
title = {On the Distribution of the Fourier Spectrum of Halfspaces},
journal = {CoRR},
volume = {abs/1202.6680},
year = {2012},
url = {http://arxiv.org/abs/1202.6680},
eprinttype = {arXiv},
eprint = {1202.6680},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1202-6680.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1206-0985,
author = {Anindya De and
Ilias Diakonikolas and
Vitaly Feldman and
Rocco A. Servedio},
title = {Nearly optimal solutions for the Chow Parameters Problem and low-weight
approximation of halfspaces},
journal = {CoRR},
volume = {abs/1206.0985},
year = {2012},
url = {http://arxiv.org/abs/1206.0985},
eprinttype = {arXiv},
eprint = {1206.0985},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1206-0985.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1207-2229,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {A robust Khintchine inequality, and algorithms for computing optimal
constants in Fourier analysis and high-dimensional geometry},
journal = {CoRR},
volume = {abs/1207.2229},
year = {2012},
url = {http://arxiv.org/abs/1207.2229},
eprinttype = {arXiv},
eprint = {1207.2229},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1207-2229.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1210-0864,
author = {Siu On Chan and
Ilias Diakonikolas and
Rocco A. Servedio and
Xiaorui Sun},
title = {Learning mixtures of structured distributions over discrete domains},
journal = {CoRR},
volume = {abs/1210.0864},
year = {2012},
url = {http://arxiv.org/abs/1210.0864},
eprinttype = {arXiv},
eprint = {1210.0864},
timestamp = {Thu, 14 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1210-0864.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1211-1722,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Inverse problems in approximate uniform generation},
journal = {CoRR},
volume = {abs/1211.1722},
year = {2012},
url = {http://arxiv.org/abs/1211.1722},
eprinttype = {arXiv},
eprint = {1211.1722},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1211-1722.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1211-2664,
author = {Cl{\'{e}}ment L. Canonne and
Dana Ron and
Rocco A. Servedio},
title = {Testing probability distributions using conditional samples},
journal = {CoRR},
volume = {abs/1211.2664},
year = {2012},
url = {http://arxiv.org/abs/1211.2664},
eprinttype = {arXiv},
eprint = {1211.2664},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1211-2664.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1212-5132,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {The Inverse Shapley Value Problem},
journal = {CoRR},
volume = {abs/1212.5132},
year = {2012},
url = {http://arxiv.org/abs/1212.5132},
eprinttype = {arXiv},
eprint = {1212.5132},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1212-5132.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CanonneRS12,
author = {Cl{\'{e}}ment L. Canonne and
Dana Ron and
Rocco A. Servedio},
title = {Testing probability distributions using conditional samples},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-155}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/155},
eprinttype = {ECCC},
eprint = {TR12-155},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CanonneRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeDFS12,
author = {Anindya De and
Ilias Diakonikolas and
Vitaly Feldman and
Rocco A. Servedio},
title = {Nearly optimal solutions for the Chow Parameters Problem and low-weight
approximation of halfspaces},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-072}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/072},
eprinttype = {ECCC},
eprint = {TR12-072},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeDFS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeDS12,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Inverse Problems in Approximate Uniform Generation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-152}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/152},
eprinttype = {ECCC},
eprint = {TR12-152},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeDS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DeDS12a,
author = {Anindya De and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {The Inverse Shapley Value Problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-181}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/181},
eprinttype = {ECCC},
eprint = {TR12-181},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DeDS12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ServedioTT12,
author = {Rocco A. Servedio and
Li{-}Yang Tan and
Justin Thaler},
title = {Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial
Threshold Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-056}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/056},
eprinttype = {ECCC},
eprint = {TR12-056},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ServedioTT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ServedioV12,
author = {Rocco A. Servedio and
Emanuele Viola},
title = {On a special case of rigidity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-144}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/144},
eprinttype = {ECCC},
eprint = {TR12-144},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ServedioV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/DiakonikolasLMSW11,
author = {Ilias Diakonikolas and
Homin K. Lee and
Kevin Matulef and
Rocco A. Servedio and
Andrew Wan},
title = {Efficiently Testing Sparse \emph{GF}(2) Polynomials},
journal = {Algorithmica},
volume = {61},
number = {3},
pages = {580--605},
year = {2011},
url = {https://doi.org/10.1007/s00453-010-9426-9},
doi = {10.1007/S00453-010-9426-9},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/DiakonikolasLMSW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dam/JacksonLSW11,
author = {Jeffrey C. Jackson and
Homin K. Lee and
Rocco A. Servedio and
Andrew Wan},
title = {Learning random monotone {DNF}},
journal = {Discret. Appl. Math.},
volume = {159},
number = {5},
pages = {259--271},
year = {2011},
url = {https://doi.org/10.1016/j.dam.2010.08.022},
doi = {10.1016/J.DAM.2010.08.022},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dam/JacksonLSW11.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/approx/Dachman-SoledS11,
author = {Dana Dachman{-}Soled and
Rocco A. Servedio},
editor = {Leslie Ann Goldberg and
Klaus Jansen and
R. Ravi and
Jos{\'{e}} D. P. Rolim},
title = {A Canonical Form for Testing Boolean Function Properties},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 14th International Workshop, {APPROX} 2011, and 15th
International Workshop, {RANDOM} 2011, Princeton, NJ, USA, August
17-19, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6845},
pages = {460--471},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22935-0\_39},
doi = {10.1007/978-3-642-22935-0\_39},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/Dachman-SoledS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/LongS11,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {John Shawe{-}Taylor and
Richard S. Zemel and
Peter L. Bartlett and
Fernando C. N. Pereira and
Kilian Q. Weinberger},
title = {Learning large-margin halfspaces with more malicious noise},
booktitle = {Advances in Neural Information Processing Systems 24: 25th Annual
Conference on Neural Information Processing Systems 2011. Proceedings
of a meeting held 12-14 December 2011, Granada, Spain},
pages = {91--99},
year = {2011},
url = {https://proceedings.neurips.cc/paper/2011/hash/98dce83da57b0395e163467c9dae521b-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/LongS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/ServedioL11,
author = {Rocco A. Servedio and
Philip M. Long},
editor = {John Shawe{-}Taylor and
Richard S. Zemel and
Peter L. Bartlett and
Fernando C. N. Pereira and
Kilian Q. Weinberger},
title = {Algorithms and hardness results for parallel large margin learning},
booktitle = {Advances in Neural Information Processing Systems 24: 25th Annual
Conference on Neural Information Processing Systems 2011. Proceedings
of a meeting held 12-14 December 2011, Granada, Spain},
pages = {1314--1322},
year = {2011},
url = {https://proceedings.neurips.cc/paper/2011/hash/b7ee6f5f9aa5cd17ca1aea43ce848496-Abstract.html},
timestamp = {Thu, 21 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/ServedioL11.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:journals/jmlr/FeldmanLS11,
author = {Vitaly Feldman and
Homin K. Lee and
Rocco A. Servedio},
editor = {Sham M. Kakade and
Ulrike von Luxburg},
title = {Lower Bounds and Hardness Amplification for Learning Shallow Monotone
Formulas},
booktitle = {{COLT} 2011 - The 24th Annual Conference on Learning Theory, June
9-11, 2011, Budapest, Hungary},
series = {{JMLR} Proceedings},
volume = {19},
pages = {273--292},
publisher = {JMLR.org},
year = {2011},
url = {http://proceedings.mlr.press/v19/feldman11a/feldman11a.pdf},
timestamp = {Wed, 29 May 2019 08:41:47 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/FeldmanLS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1103-0598,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Learning transformed product distributions},
journal = {CoRR},
volume = {abs/1103.0598},
year = {2011},
url = {http://arxiv.org/abs/1103.0598},
eprinttype = {arXiv},
eprint = {1103.0598},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1103-0598.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1107-2444,
author = {Moritz Hardt and
Guy N. Rothblum and
Rocco A. Servedio},
title = {Private Data Release via Learning Thresholds},
journal = {CoRR},
volume = {abs/1107.2444},
year = {2011},
url = {http://arxiv.org/abs/1107.2444},
eprinttype = {arXiv},
eprint = {1107.2444},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1107-2444.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1107-2700,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Learning {\textdollar}k{\textdollar}-Modal Distributions via Testing},
journal = {CoRR},
volume = {abs/1107.2700},
year = {2011},
url = {http://arxiv.org/abs/1107.2700},
eprinttype = {arXiv},
eprint = {1107.2700},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1107-2700.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1107-2702,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
title = {Learning Poisson Binomial Distributions},
journal = {CoRR},
volume = {abs/1107.2702},
year = {2011},
url = {http://arxiv.org/abs/1107.2702},
eprinttype = {arXiv},
eprint = {1107.2702},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1107-2702.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1109-2141,
author = {Roni Khardon and
Dan Roth and
Rocco A. Servedio},
title = {Efficiency versus Convergence of Boolean Kernels for On-Line Learning
Algorithms},
journal = {CoRR},
volume = {abs/1109.2141},
year = {2011},
url = {http://arxiv.org/abs/1109.2141},
eprinttype = {arXiv},
eprint = {1109.2141},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1109-2141.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1111-1124,
author = {Lisa Hellerstein and
Devorah Kletenik and
Linda Sellie and
Rocco A. Servedio},
title = {Tight Bounds on Proper Equivalence Query Learning of {DNF}},
journal = {CoRR},
volume = {abs/1111.1124},
year = {2011},
url = {http://arxiv.org/abs/1111.1124},
eprinttype = {arXiv},
eprint = {1111.1124},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1111-1124.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1112-5659,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio and
Gregory Valiant and
Paul Valiant},
title = {Testing {\textdollar}k{\textdollar}-Modal Distributions: Optimal Algorithms
via Reductions},
journal = {CoRR},
volume = {abs/1112.5659},
year = {2011},
url = {http://arxiv.org/abs/1112.5659},
eprinttype = {arXiv},
eprint = {1112.5659},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1112-5659.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/LongS10,
author = {Philip M. Long and
Rocco A. Servedio},
title = {Random classification noise defeats all convex potential boosters},
journal = {Mach. Learn.},
volume = {78},
number = {3},
pages = {287--304},
year = {2010},
url = {https://doi.org/10.1007/s10994-009-5165-z},
doi = {10.1007/S10994-009-5165-Z},
timestamp = {Mon, 02 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ml/LongS10.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}
}
@article{DBLP:journals/siamcomp/DiakonikolasGJSV10,
author = {Ilias Diakonikolas and
Parikshit Gopalan and
Ragesh Jaiswal and
Rocco A. Servedio and
Emanuele Viola},
title = {Bounded Independence Fools Halfspaces},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {8},
pages = {3441--3462},
year = {2010},
url = {https://doi.org/10.1137/100783030},
doi = {10.1137/100783030},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/DiakonikolasGJSV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/GopalanS10,
author = {Parikshit Gopalan and
Rocco A. Servedio},
editor = {Maria J. Serna and
Ronen Shaltiel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim},
title = {Learning and Lower Bounds for AC\({}^{\mbox{0}}\) with Threshold Gates},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 13th International Workshop, {APPROX} 2010, and 14th
International Workshop, {RANDOM} 2010, Barcelona, Spain, September
1-3, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6302},
pages = {588--601},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-15369-3\_44},
doi = {10.1007/978-3-642-15369-3\_44},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/GopalanS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/DiakonikolasSTW10,
author = {Ilias Diakonikolas and
Rocco A. Servedio and
Li{-}Yang Tan and
Andrew Wan},
title = {A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial
Threshold Functions},
booktitle = {Proceedings of the 25th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2010, Cambridge, Massachusetts, USA, June 9-12,
2010},
pages = {211--222},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/CCC.2010.28},
doi = {10.1109/CCC.2010.28},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/DiakonikolasSTW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icml/LongS10,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {Johannes F{\"{u}}rnkranz and
Thorsten Joachims},
title = {Restricted Boltzmann Machines are Hard to Approximately Evaluate or
Simulate},
booktitle = {Proceedings of the 27th International Conference on Machine Learning
(ICML-10), June 21-24, 2010, Haifa, Israel},
pages = {703--710},
publisher = {Omnipress},
year = {2010},
url = {https://icml.cc/Conferences/2010/papers/115.pdf},
timestamp = {Wed, 03 Apr 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icml/LongS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DiakonikolasHKMRST10,
author = {Ilias Diakonikolas and
Prahladh Harsha and
Adam R. Klivans and
Raghu Meka and
Prasad Raghavendra and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Leonard J. Schulman},
title = {Bounding the average sensitivity and noise sensitivity of polynomial
threshold functions},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {533--542},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806763},
doi = {10.1145/1806689.1806763},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/DiakonikolasHKMRST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:conf/propertytesting/Servedio10,
author = {Rocco A. Servedio},
editor = {Oded Goldreich},
title = {Testing by Implicit Learning: {A} Brief Survey},
booktitle = {Property Testing - Current Research and Surveys},
series = {Lecture Notes in Computer Science},
volume = {6390},
pages = {197--210},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-16367-8\_11},
doi = {10.1007/978-3-642-16367-8\_11},
timestamp = {Tue, 01 Jun 2021 15:22:56 +0200},
biburl = {https://dblp.org/rec/conf/propertytesting/Servedio10.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 = {Wed, 01 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/propertytesting/MatulefORS10.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/eccc/FeldmanLS10,
author = {Vitaly Feldman and
Homin K. Lee and
Rocco A. Servedio},
title = {Lower Bounds and Hardness Amplification for Learning Shallow Monotone
Formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-022}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/022},
eprinttype = {ECCC},
eprint = {TR10-022},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FeldmanLS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GopalanS10,
author = {Parikshit Gopalan and
Rocco A. Servedio},
title = {Learning and Lower Bounds for AC\({}^{\mbox{0}}\) with Threshold Gates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-074}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/074},
eprinttype = {ECCC},
eprint = {TR10-074},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GopalanS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jmlr/KlivansLS09,
author = {Adam R. Klivans and
Philip M. Long and
Rocco A. Servedio},
title = {Learning Halfspaces with Malicious Noise},
journal = {J. Mach. Learn. Res.},
volume = {10},
pages = {2715--2740},
year = {2009},
url = {https://dl.acm.org/doi/10.5555/1577069.1755877},
doi = {10.5555/1577069.1755877},
timestamp = {Thu, 02 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/KlivansLS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/RubinfeldS09,
author = {Ronitt Rubinfeld and
Rocco A. Servedio},
title = {Testing monotone high-dimensional distributions},
journal = {Random Struct. Algorithms},
volume = {34},
number = {1},
pages = {24--44},
year = {2009},
url = {https://doi.org/10.1002/rsa.20247},
doi = {10.1002/RSA.20247},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/RubinfeldS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/HutterS09,
author = {Marcus Hutter and
Rocco A. Servedio},
title = {Preface},
journal = {Theor. Comput. Sci.},
volume = {410},
number = {19},
pages = {1747--1748},
year = {2009},
url = {https://doi.org/10.1016/j.tcs.2009.01.008},
doi = {10.1016/J.TCS.2009.01.008},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/HutterS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/GlasnerS09,
author = {Dana Glasner and
Rocco A. Servedio},
title = {Distribution-Free Testing Lower Bound for Basic Boolean Functions},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {191--216},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a010},
doi = {10.4086/TOC.2009.V005A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/GlasnerS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Dachman-SoledLMSWW09,
author = {Dana Dachman{-}Soled and
Homin K. Lee and
Tal Malkin and
Rocco A. Servedio and
Andrew Wan and
Hoeteck Wee},
title = {Optimal Cryptographic Hardness of Learning Monotone Functions},
journal = {Theory Comput.},
volume = {5},
number = {1},
pages = {257--282},
year = {2009},
url = {https://doi.org/10.4086/toc.2009.v005a013},
doi = {10.4086/TOC.2009.V005A013},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Dachman-SoledLMSWW09.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/coco/DiakonikolasS09,
author = {Ilias Diakonikolas and
Rocco A. Servedio},
title = {Improved Approximation of Linear Threshold Functions},
booktitle = {Proceedings of the 24th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2009, Paris, France, 15-18 July 2009},
pages = {161--172},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/CCC.2009.8},
doi = {10.1109/CCC.2009.8},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/DiakonikolasS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DiakonikolasGJSV09,
author = {Ilias Diakonikolas and
Parikshit Gopalan and
Ragesh Jaiswal and
Rocco A. Servedio and
Emanuele Viola},
title = {Bounded Independence Fools Halfspaces},
booktitle = {50th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2009, October 25-27, 2009, Atlanta, Georgia, {USA}},
pages = {171--180},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/FOCS.2009.68},
doi = {10.1109/FOCS.2009.68},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DiakonikolasGJSV09.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/icalp/KlivansLS09,
author = {Adam R. Klivans and
Philip M. Long and
Rocco A. Servedio},
editor = {Susanne Albers and
Alberto Marchetti{-}Spaccamela and
Yossi Matias and
Sotiris E. Nikoletseas and
Wolfgang Thomas},
title = {Learning Halfspaces with Malicious Noise},
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 = {609--621},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02927-1\_51},
doi = {10.1007/978-3-642-02927-1\_51},
timestamp = {Tue, 23 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/KlivansLS09.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}
}
@article{DBLP:journals/corr/abs-0902-3757,
author = {Ilias Diakonikolas and
Parikshit Gopalan and
Ragesh Jaiswal and
Rocco A. Servedio and
Emanuele Viola},
title = {Bounded Independence Fools Halfspaces},
journal = {CoRR},
volume = {abs/0902.3757},
year = {2009},
url = {http://arxiv.org/abs/0902.3757},
eprinttype = {arXiv},
eprint = {0902.3757},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0902-3757.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0909-4727,
author = {Ilias Diakonikolas and
Rocco A. Servedio and
Li{-}Yang Tan and
Andrew Wan},
title = {A regularity lemma, and low-weight approximators, for low-degree polynomial
threshold functions},
journal = {CoRR},
volume = {abs/0909.4727},
year = {2009},
url = {http://arxiv.org/abs/0909.4727},
eprinttype = {arXiv},
eprint = {0909.4727},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0909-4727.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0909-5011,
author = {Ilias Diakonikolas and
Prasad Raghavendra and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Average sensitivity and noise sensitivity of polynomial threshold
functions},
journal = {CoRR},
volume = {abs/0909.5011},
year = {2009},
url = {http://arxiv.org/abs/0909.5011},
eprinttype = {arXiv},
eprint = {0909.5011},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0909-5011.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0910-3719,
author = {Ilias Diakonikolas and
Rocco A. Servedio},
title = {Improved Approximation of Linear Threshold Functions},
journal = {CoRR},
volume = {abs/0910.3719},
year = {2009},
url = {http://arxiv.org/abs/0910.3719},
eprinttype = {arXiv},
eprint = {0910.3719},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0910-3719.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DiakonikolasGJSV09,
author = {Ilias Diakonikolas and
Parikshit Gopalan and
Ragesh Jaiswal and
Rocco A. Servedio and
Emanuele Viola},
title = {Bounded Independence Fools Halfspaces},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-016}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/016},
eprinttype = {ECCC},
eprint = {TR09-016},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DiakonikolasGJSV09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/KlivansS08,
author = {Adam R. Klivans and
Rocco A. Servedio},
title = {Learning intersections of halfspaces with a margin},
journal = {J. Comput. Syst. Sci.},
volume = {74},
number = {1},
pages = {35--48},
year = {2008},
url = {https://doi.org/10.1016/j.jcss.2007.04.012},
doi = {10.1016/J.JCSS.2007.04.012},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/KlivansS08.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}
}
@article{DBLP:journals/siamcomp/KalaiKMS08,
author = {Adam Tauman Kalai and
Adam R. Klivans and
Yishay Mansour and
Rocco A. Servedio},
title = {Agnostically Learning Halfspaces},
journal = {{SIAM} J. Comput.},
volume = {37},
number = {6},
pages = {1777--1805},
year = {2008},
url = {https://doi.org/10.1137/060649057},
doi = {10.1137/060649057},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KalaiKMS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/AticiS08,
author = {Alp Atici and
Rocco A. Servedio},
title = {Learning unions of omega(1)-dimensional rectangles},
journal = {Theor. Comput. Sci.},
volume = {405},
number = {3},
pages = {209--222},
year = {2008},
url = {https://doi.org/10.1016/j.tcs.2008.06.036},
doi = {10.1016/J.TCS.2008.06.036},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/AticiS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/JacksonLSW08,
author = {Jeffrey C. Jackson and
Homin K. Lee and
Rocco A. Servedio and
Andrew Wan},
editor = {Ashish Goel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Ronitt Rubinfeld},
title = {Learning Random Monotone {DNF}},
booktitle = {Approximation, Randomization and Combinatorial Optimization. Algorithms
and Techniques, 11th International Workshop, {APPROX} 2008, and 12th
International Workshop, {RANDOM} 2008, Boston, MA, USA, August 25-27,
2008. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5171},
pages = {483--497},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-85363-3\_38},
doi = {10.1007/978-3-540-85363-3\_38},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/JacksonLSW08.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/icalp/Dachman-SoledLMSWW08,
author = {Dana Dachman{-}Soled and
Homin K. Lee and
Tal Malkin and
Rocco A. Servedio and
Andrew Wan and
Hoeteck Wee},
editor = {Luca Aceto and
Ivan Damg{\aa}rd and
Leslie Ann Goldberg and
Magn{\'{u}}s M. Halld{\'{o}}rsson and
Anna Ing{\'{o}}lfsd{\'{o}}ttir and
Igor Walukiewicz},
title = {Optimal Cryptographic Hardness of Learning Monotone Functions},
booktitle = {Automata, Languages and Programming, 35th International Colloquium,
{ICALP} 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part
{I:} Tack {A:} Algorithms, Automata, Complexity, and Games},
series = {Lecture Notes in Computer Science},
volume = {5125},
pages = {36--47},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-70575-8\_4},
doi = {10.1007/978-3-540-70575-8\_4},
timestamp = {Fri, 27 Mar 2020 09:02:59 +0100},
biburl = {https://dblp.org/rec/conf/icalp/Dachman-SoledLMSWW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/DiakonikolasLMSW08,
author = {Ilias Diakonikolas and
Homin K. Lee and
Kevin Matulef and
Rocco A. Servedio and
Andrew Wan},
editor = {Luca Aceto and
Ivan Damg{\aa}rd and
Leslie Ann Goldberg and
Magn{\'{u}}s M. Halld{\'{o}}rsson and
Anna Ing{\'{o}}lfsd{\'{o}}ttir and
Igor Walukiewicz},
title = {Efficiently Testing Sparse {GF(2)} Polynomials},
booktitle = {Automata, Languages and Programming, 35th International Colloquium,
{ICALP} 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part
{I:} Tack {A:} Algorithms, Automata, Complexity, and Games},
series = {Lecture Notes in Computer Science},
volume = {5125},
pages = {502--514},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-70575-8\_41},
doi = {10.1007/978-3-540-70575-8\_41},
timestamp = {Tue, 23 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/DiakonikolasLMSW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icml/LongS08,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {William W. Cohen and
Andrew McCallum and
Sam T. Roweis},
title = {Random classification noise defeats all convex potential boosters},
booktitle = {Machine Learning, Proceedings of the Twenty-Fifth International Conference
{(ICML} 2008), Helsinki, Finland, June 5-9, 2008},
series = {{ACM} International Conference Proceeding Series},
volume = {307},
pages = {608--615},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1390156.1390233},
doi = {10.1145/1390156.1390233},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icml/LongS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/LongS08,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {Daphne Koller and
Dale Schuurmans and
Yoshua Bengio and
L{\'{e}}on Bottou},
title = {Adaptive Martingale Boosting},
booktitle = {Advances in Neural Information Processing Systems 21, Proceedings
of the Twenty-Second Annual Conference on Neural Information Processing
Systems, Vancouver, British Columbia, Canada, December 8-11, 2008},
pages = {977--984},
publisher = {Curran Associates, Inc.},
year = {2008},
url = {https://proceedings.neurips.cc/paper/2008/hash/38b3eff8baf56627478ec76a704e9b52-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/LongS08.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}
}
@proceedings{DBLP:conf/colt/2008,
editor = {Rocco A. Servedio and
Tong Zhang},
title = {21st Annual Conference on Learning Theory - {COLT} 2008, Helsinki,
Finland, July 9-12, 2008},
publisher = {Omnipress},
year = {2008},
timestamp = {Fri, 19 Apr 2013 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/2008.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/Servedio08,
author = {Rocco A. Servedio},
editor = {Ming{-}Yang Kao},
title = {Learning Constant-Depth Circuits},
booktitle = {Encyclopedia of Algorithms - 2008 Edition},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-0-387-30162-4\_195},
doi = {10.1007/978-0-387-30162-4\_195},
timestamp = {Thu, 27 Jun 2019 16:25:31 +0200},
biburl = {https://dblp.org/rec/reference/algo/Servedio08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0805-1765,
author = {Ilias Diakonikolas and
Homin K. Lee and
Kevin Matulef and
Rocco A. Servedio and
Andrew Wan},
title = {Efficiently Testing Sparse {GF(2)} Polynomials},
journal = {CoRR},
volume = {abs/0805.1765},
year = {2008},
url = {http://arxiv.org/abs/0805.1765},
eprinttype = {arXiv},
eprint = {0805.1765},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0805-1765.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/Servedio07,
author = {Rocco A. Servedio},
title = {Every Linear Threshold Function has a Low-Weight Approximator},
journal = {Comput. Complex.},
volume = {16},
number = {2},
pages = {180--209},
year = {2007},
url = {https://doi.org/10.1007/s00037-007-0228-7},
doi = {10.1007/S00037-007-0228-7},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/Servedio07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/LongSS07,
author = {Philip M. Long and
Rocco A. Servedio and
Hans Ulrich Simon},
title = {Discriminative learning can succeed where generative learning fails},
journal = {Inf. Process. Lett.},
volume = {103},
number = {4},
pages = {131--135},
year = {2007},
url = {https://doi.org/10.1016/j.ipl.2007.03.004},
doi = {10.1016/J.IPL.2007.03.004},
timestamp = {Fri, 08 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/LongSS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jmlr/ElbazLSW07,
author = {Ariel Elbaz and
Homin K. Lee and
Rocco A. Servedio and
Andrew Wan},
title = {Separating Models of Learning from Correlated and Uncorrelated Data},
journal = {J. Mach. Learn. Res.},
volume = {8},
pages = {277--290},
year = {2007},
url = {http://jmlr.org/papers/v8/elbaz07a.html},
timestamp = {Wed, 10 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/ElbazLSW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ml/LeeSW07,
author = {Homin K. Lee and
Rocco A. Servedio and
Andrew Wan},
title = {{DNF} are teachable in the average case},
journal = {Mach. Learn.},
volume = {69},
number = {2-3},
pages = {79--96},
year = {2007},
url = {https://doi.org/10.1007/s10994-007-5007-9},
doi = {10.1007/S10994-007-5007-9},
timestamp = {Mon, 02 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ml/LeeSW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/qip/AticiS07,
author = {Alp Atici and
Rocco A. Servedio},
title = {Quantum Algorithms for Learning and Testing Juntas},
journal = {Quantum Inf. Process.},
volume = {6},
number = {5},
pages = {323--348},
year = {2007},
url = {https://doi.org/10.1007/s11128-007-0061-6},
doi = {10.1007/S11128-007-0061-6},
timestamp = {Thu, 16 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/qip/AticiS07.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}
}
@article{DBLP:journals/tcs/HellersteinS07,
author = {Lisa Hellerstein and
Rocco A. Servedio},
title = {On {PAC} learning algorithms for rich Boolean function classes},
journal = {Theor. Comput. Sci.},
volume = {384},
number = {1},
pages = {66--76},
year = {2007},
url = {https://doi.org/10.1016/j.tcs.2007.05.018},
doi = {10.1016/J.TCS.2007.05.018},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/HellersteinS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/FeldmanMSSW07,
author = {Jon Feldman and
Tal Malkin and
Rocco A. Servedio and
Clifford Stein and
Martin J. Wainwright},
title = {{LP} Decoding Corrects a Constant Fraction of Errors},
journal = {{IEEE} Trans. Inf. Theory},
volume = {53},
number = {1},
pages = {82--89},
year = {2007},
url = {https://doi.org/10.1109/TIT.2006.887523},
doi = {10.1109/TIT.2006.887523},
timestamp = {Mon, 17 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tit/FeldmanMSSW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alt/HutterST07,
author = {Marcus Hutter and
Rocco A. Servedio and
Eiji Takimoto},
editor = {Marcus Hutter and
Rocco A. Servedio and
Eiji Takimoto},
title = {Editors' Introduction},
booktitle = {Algorithmic Learning Theory, 18th International Conference, {ALT}
2007, Sendai, Japan, October 1-4, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4754},
pages = {1--8},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-75225-7\_1},
doi = {10.1007/978-3-540-75225-7\_1},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/alt/HutterST07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/GlasnerS07,
author = {Dana Glasner and
Rocco A. Servedio},
editor = {Moses Charikar and
Klaus Jansen and
Omer Reingold and
Jos{\'{e}} D. P. Rolim},
title = {Distribution-Free Testing Lower Bounds for Basic Boolean Functions},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 10th International Workshop, {APPROX} 2007, and 11th
International Workshop, {RANDOM} 2007, Princeton, NJ, USA, August
20-22, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4627},
pages = {494--508},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74208-1\_36},
doi = {10.1007/978-3-540-74208-1\_36},
timestamp = {Sat, 30 Sep 2023 09:34:32 +0200},
biburl = {https://dblp.org/rec/conf/approx/GlasnerS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DiakonikolasLMORSW07,
author = {Ilias Diakonikolas and
Homin K. Lee and
Kevin Matulef and
Krzysztof Onak and
Ronitt Rubinfeld and
Rocco A. Servedio and
Andrew Wan},
title = {Testing for Concise Representations},
booktitle = {48th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2007), October 20-23, 2007, Providence, RI, USA, Proceedings},
pages = {549--558},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/FOCS.2007.32},
doi = {10.1109/FOCS.2007.32},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DiakonikolasLMORSW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lics/RabinST07,
author = {Michael O. Rabin and
Rocco A. Servedio and
Christopher Thorpe},
title = {Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations
and Applications},
booktitle = {22nd {IEEE} Symposium on Logic in Computer Science {(LICS} 2007),
10-12 July 2007, Wroclaw, Poland, Proceedings},
pages = {63--76},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/LICS.2007.24},
doi = {10.1109/LICS.2007.24},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/lics/RabinST07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/BarutcuogluLS07,
author = {Zafer Barut{\c{c}}uoglu and
Philip M. Long and
Rocco A. Servedio},
editor = {John C. Platt and
Daphne Koller and
Yoram Singer and
Sam T. Roweis},
title = {One-Pass Boosting},
booktitle = {Advances in Neural Information Processing Systems 20, Proceedings
of the Twenty-First Annual Conference on Neural Information Processing
Systems, Vancouver, British Columbia, Canada, December 3-6, 2007},
pages = {73--80},
publisher = {Curran Associates, Inc.},
year = {2007},
url = {https://proceedings.neurips.cc/paper/2007/hash/a9a6653e48976138166de32772b1bf40-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/BarutcuogluLS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/LongS07,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {John C. Platt and
Daphne Koller and
Yoram Singer and
Sam T. Roweis},
title = {Boosting the Area under the {ROC} Curve},
booktitle = {Advances in Neural Information Processing Systems 20, Proceedings
of the Twenty-First Annual Conference on Neural Information Processing
Systems, Vancouver, British Columbia, Canada, December 3-6, 2007},
pages = {945--952},
publisher = {Curran Associates, Inc.},
year = {2007},
url = {https://proceedings.neurips.cc/paper/2007/hash/c5ff2543b53f4cc0ad3819a36752467b-Abstract.html},
timestamp = {Thu, 21 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/LongS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/alt/2007,
editor = {Marcus Hutter and
Rocco A. Servedio and
Eiji Takimoto},
title = {Algorithmic Learning Theory, 18th International Conference, {ALT}
2007, Sendai, Japan, October 1-4, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4754},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-75225-7},
doi = {10.1007/978-3-540-75225-7},
isbn = {978-3-540-75224-0},
timestamp = {Tue, 14 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/alt/2007.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0707-3479,
author = {Alp Atici and
Rocco A. Servedio},
title = {Quantum Algorithms for Learning and Testing Juntas},
journal = {CoRR},
volume = {abs/0707.3479},
year = {2007},
url = {http://arxiv.org/abs/0707.3479},
eprinttype = {arXiv},
eprint = {0707.3479},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0707-3479.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/DiakonikolasLMORSW07,
author = {Ilias Diakonikolas and
Homin K. Lee and
Kevin Matulef and
Krzysztof Onak and
Ronitt Rubinfeld and
Rocco A. Servedio and
Andrew Wan},
title = {Testing for Concise Representations},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-077}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-077/index.html},
eprinttype = {ECCC},
eprint = {TR07-077},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/DiakonikolasLMORSW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/JacksonLSW07,
author = {Jeffrey C. Jackson and
Homin K. Lee and
Rocco A. Servedio and
Andrew Wan},
title = {Learning Random Monotone {DNF}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-129}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-129/index.html},
eprinttype = {ECCC},
eprint = {TR07-129},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/JacksonLSW07.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}
}
@article{DBLP:journals/iandc/AriasFKS06,
author = {Marta Arias and
Aaron Feigelson and
Roni Khardon and
Rocco A. Servedio},
title = {Polynomial certificates for propositional classes},
journal = {Inf. Comput.},
volume = {204},
number = {5},
pages = {816--834},
year = {2006},
url = {https://doi.org/10.1016/j.ic.2006.03.001},
doi = {10.1016/J.IC.2006.03.001},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/AriasFKS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jmlr/KlivansS06,
author = {Adam R. Klivans and
Rocco A. Servedio},
title = {Toward Attribute Efficient Learning of Decision Lists and Parities},
journal = {J. Mach. Learn. Res.},
volume = {7},
pages = {587--602},
year = {2006},
url = {http://jmlr.org/papers/v7/klivans06a.html},
timestamp = {Wed, 10 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/KlivansS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Servedio06,
author = {Rocco A. Servedio},
title = {On learning embedded midbit functions},
journal = {Theor. Comput. Sci.},
volume = {350},
number = {1},
pages = {13--23},
year = {2006},
url = {https://doi.org/10.1016/j.tcs.2005.10.013},
doi = {10.1016/J.TCS.2005.10.013},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Servedio06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/JacksonS06,
author = {Jeffrey C. Jackson and
Rocco A. Servedio},
title = {On Learning Random {DNF} Formulas Under the Uniform Distribution},
journal = {Theory Comput.},
volume = {2},
number = {8},
pages = {147--172},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a008},
doi = {10.4086/TOC.2006.V002A008},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/JacksonS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alt/AticiS06,
author = {Alp Atici and
Rocco A. Servedio},
editor = {Jos{\'{e}} L. Balc{\'{a}}zar and
Philip M. Long and
Frank Stephan},
title = {Learning Unions of \emph{omega}(1)-Dimensional Rectangles},
booktitle = {Algorithmic Learning Theory, 17th International Conference, {ALT}
2006, Barcelona, Spain, October 7-10, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4264},
pages = {32--47},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11894841\_7},
doi = {10.1007/11894841\_7},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/alt/AticiS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Servedio06,
author = {Rocco A. Servedio},
title = {Every Linear Threshold Function has a Low-Weight Approximator},
booktitle = {21st Annual {IEEE} Conference on Computational Complexity {(CCC} 2006),
16-20 July 2006, Prague, Czech Republic},
pages = {18--32},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/CCC.2006.18},
doi = {10.1109/CCC.2006.18},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Servedio06.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/colt/LeeSW06,
author = {Homin K. Lee and
Rocco A. Servedio and
Andrew Wan},
editor = {G{\'{a}}bor Lugosi and
Hans Ulrich Simon},
title = {{DNF} Are Teachable in the Average Case},
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 = {214--228},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11776420\_18},
doi = {10.1007/11776420\_18},
timestamp = {Sun, 21 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/LeeSW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/LongS06,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {G{\'{a}}bor Lugosi and
Hans Ulrich Simon},
title = {Discriminative Learning Can Succeed Where Generative Learning Fails},
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 = {319--334},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11776420\_25},
doi = {10.1007/11776420\_25},
timestamp = {Sun, 21 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/LongS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/LongS06,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {Bernhard Sch{\"{o}}lkopf and
John C. Platt and
Thomas Hofmann},
title = {Attribute-efficient learning of decision lists and linear threshold
functions under unconcentrated distributions},
booktitle = {Advances in Neural Information Processing Systems 19, Proceedings
of the Twentieth Annual Conference on Neural Information Processing
Systems, Vancouver, British Columbia, Canada, December 4-7, 2006},
pages = {921--928},
publisher = {{MIT} Press},
year = {2006},
url = {https://proceedings.neurips.cc/paper/2006/hash/a724b9124acc7b5058ed75a31a9c2919-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/LongS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tamc/Servedio06,
author = {Rocco A. Servedio},
editor = {Jin{-}yi Cai and
S. Barry Cooper and
Angsheng Li},
title = {On {PAC} Learning Algorithms for Rich Boolean Function Classes},
booktitle = {Theory and Applications of Models of Computation, Third International
Conference, {TAMC} 2006, Beijing, China, May 15-20, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3959},
pages = {442--451},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11750321\_42},
doi = {10.1007/11750321\_42},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/tamc/Servedio06.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/ipl/ServedioW05,
author = {Rocco A. Servedio and
Andrew Wan},
title = {Computing sparse permanents faster},
journal = {Inf. Process. Lett.},
volume = {96},
number = {3},
pages = {89--92},
year = {2005},
url = {https://doi.org/10.1016/j.ipl.2005.06.007},
doi = {10.1016/J.IPL.2005.06.007},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/ServedioW05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jair/KhardonRS05,
author = {Roni Khardon and
Dan Roth and
Rocco A. Servedio},
title = {Efficiency versus Convergence of Boolean Kernels for On-Line Learning
Algorithms},
journal = {J. Artif. Intell. Res.},
volume = {24},
pages = {341--356},
year = {2005},
url = {https://doi.org/10.1613/jair.1655},
doi = {10.1613/JAIR.1655},
timestamp = {Mon, 21 Jan 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jair/KhardonRS05.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/jcss/KalaiS05,
author = {Adam Tauman Kalai and
Rocco A. Servedio},
title = {Boosting in the presence of noise},
journal = {J. Comput. Syst. Sci.},
volume = {71},
number = {3},
pages = {266--290},
year = {2005},
url = {https://doi.org/10.1016/j.jcss.2004.10.015},
doi = {10.1016/J.JCSS.2004.10.015},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/KalaiS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jmlr/KhardonS05,
author = {Roni Khardon and
Rocco A. Servedio},
title = {Maximum Margin Algorithms with Boolean Kernels},
journal = {J. Mach. Learn. Res.},
volume = {6},
pages = {1405--1429},
year = {2005},
url = {http://jmlr.org/papers/v6/khardon05a.html},
timestamp = {Wed, 10 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/KhardonS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/qip/AticiS05,
author = {Alp Atici and
Rocco A. Servedio},
title = {Improved Bounds on Quantum Learning Algorithms},
journal = {Quantum Inf. Process.},
volume = {4},
number = {5},
pages = {355--386},
year = {2005},
url = {https://doi.org/10.1007/s11128-005-0001-2},
doi = {10.1007/S11128-005-0001-2},
timestamp = {Thu, 16 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/qip/AticiS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/JacksonS05,
author = {Jeffrey C. Jackson and
Rocco A. Servedio},
title = {Learning Random Log-Depth Decision Trees under Uniform Distribution},
journal = {{SIAM} J. Comput.},
volume = {34},
number = {5},
pages = {1107--1128},
year = {2005},
url = {https://doi.org/10.1137/S0097539704444555},
doi = {10.1137/S0097539704444555},
timestamp = {Wed, 14 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/JacksonS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/JacksonS05,
author = {Jeffrey C. Jackson and
Rocco A. Servedio},
editor = {Chandra Chekuri and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Luca Trevisan},
title = {On Learning Random {DNF} Formulas Under the Uniform Distribution},
booktitle = {Approximation, Randomization and Combinatorial Optimization, Algorithms
and Techniques, 8th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems, {APPROX} 2005 and 9th InternationalWorkshop
on Randomization and Computation, {RANDOM} 2005, Berkeley, CA, USA,
August 22-24, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3624},
pages = {342--353},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11538462\_29},
doi = {10.1007/11538462\_29},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/JacksonS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/LongS05,
author = {Philip M. Long and
Rocco A. Servedio},
editor = {Peter Auer and
Ron Meir},
title = {Martingale Boosting},
booktitle = {Learning Theory, 18th Annual Conference on Learning Theory, {COLT}
2005, Bertinoro, Italy, June 27-30, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3559},
pages = {79--94},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11503415\_6},
doi = {10.1007/11503415\_6},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/colt/LongS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/ElbazLSW05,
author = {Ariel Elbaz and
Homin K. Lee and
Rocco A. Servedio and
Andrew Wan},
editor = {Peter Auer and
Ron Meir},
title = {Separating Models of Learning from Correlated and Uncorrelated Data},
booktitle = {Learning Theory, 18th Annual Conference on Learning Theory, {COLT}
2005, Bertinoro, Italy, June 27-30, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3559},
pages = {637--651},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11503415\_43},
doi = {10.1007/11503415\_43},
timestamp = {Sun, 21 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/ElbazLSW05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KalaiKMS05,
author = {Adam Tauman Kalai and
Adam R. Klivans and
Yishay Mansour and
Rocco A. Servedio},
title = {Agnostically Learning Halfspaces},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {11--20},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.13},
doi = {10.1109/SFCS.2005.13},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KalaiKMS05.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}
}
@inproceedings{DBLP:conf/icml/LongVGTS05,
author = {Philip M. Long and
Vinay Varadan and
Sarah Gilman and
Mark Treshock and
Rocco A. Servedio},
editor = {Luc De Raedt and
Stefan Wrobel},
title = {Unsupervised evidence integration},
booktitle = {Machine Learning, Proceedings of the Twenty-Second International Conference
{(ICML} 2005), Bonn, Germany, August 7-11, 2005},
series = {{ACM} International Conference Proceeding Series},
volume = {119},
pages = {521--528},
publisher = {{ACM}},
year = {2005},
url = {https://doi.org/10.1145/1102351.1102417},
doi = {10.1145/1102351.1102417},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icml/LongVGTS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/RubinfeldS05,
author = {Ronitt Rubinfeld and
Rocco A. Servedio},
editor = {Harold N. Gabow and
Ronald Fagin},
title = {Testing monotone high-dimensional distributions},
booktitle = {Proceedings of the 37th Annual {ACM} Symposium on Theory of Computing,
Baltimore, MD, USA, May 22-24, 2005},
pages = {147--156},
publisher = {{ACM}},
year = {2005},
url = {https://doi.org/10.1145/1060590.1060613},
doi = {10.1145/1060590.1060613},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/RubinfeldS05.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-cs-0510038,
author = {Alp Atici and
Rocco A. Servedio},
title = {Learning Unions of {\textdollar}{\textbackslash}omega(1){\textdollar}-Dimensional
Rectangles},
journal = {CoRR},
volume = {abs/cs/0510038},
year = {2005},
url = {http://arxiv.org/abs/cs/0510038},
eprinttype = {arXiv},
eprint = {cs/0510038},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0510038.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dam/Servedio04,
author = {Rocco A. Servedio},
title = {Monotone Boolean formulas can approximate monotone linear threshold
functions},
journal = {Discret. Appl. Math.},
volume = {142},
number = {1-3},
pages = {181--187},
year = {2004},
url = {https://doi.org/10.1016/j.dam.2004.02.003},
doi = {10.1016/J.DAM.2004.02.003},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dam/Servedio04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/Servedio04,
author = {Rocco A. Servedio},
title = {On learning monotone {DNF} under product distributions},
journal = {Inf. Comput.},
volume = {193},
number = {1},
pages = {57--74},
year = {2004},
url = {https://doi.org/10.1016/j.ic.2004.04.003},
doi = {10.1016/J.IC.2004.04.003},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/Servedio04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/KlivansS04,
author = {Adam R. Klivans and
Rocco A. Servedio},
title = {Learning {DNF} in time 2\({}^{\mbox{{\~{O}}(n\({}^{\mbox{1/3}}\))}}\)},
journal = {J. Comput. Syst. Sci.},
volume = {68},
number = {2},
pages = {303--318},
year = {2004},
url = {https://doi.org/10.1016/j.jcss.2003.07.007},
doi = {10.1016/J.JCSS.2003.07.007},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/KlivansS04.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/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}
}
@article{DBLP:journals/siamcomp/ServedioG04,
author = {Rocco A. Servedio and
Steven J. Gortler},
title = {Equivalences and Separations Between Quantum and Classical Learnability},
journal = {{SIAM} J. Comput.},
volume = {33},
number = {5},
pages = {1067--1092},
year = {2004},
url = {https://doi.org/10.1137/S0097539704412910},
doi = {10.1137/S0097539704412910},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ServedioG04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/KlivansS04b,
author = {Adam R. Klivans and
Rocco A. Servedio},
editor = {John Shawe{-}Taylor and
Yoram Singer},
title = {Toward Attribute Efficient Learning of Decision Lists and Parities},
booktitle = {Learning Theory, 17th Annual Conference on Learning Theory, {COLT}
2004, Banff, Canada, July 1-4, 2004, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3120},
pages = {224--238},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-27819-1\_16},
doi = {10.1007/978-3-540-27819-1\_16},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/colt/KlivansS04b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/KlivansS04,
author = {Adam R. Klivans and
Rocco A. Servedio},
editor = {John Shawe{-}Taylor and
Yoram Singer},
title = {Learning Intersections of Halfspaces with a Margin},
booktitle = {Learning Theory, 17th Annual Conference on Learning Theory, {COLT}
2004, Banff, Canada, July 1-4, 2004, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3120},
pages = {348--362},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-27819-1\_24},
doi = {10.1007/978-3-540-27819-1\_24},
timestamp = {Sun, 21 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/KlivansS04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/KlivansS04a,
author = {Adam R. Klivans and
Rocco A. Servedio},
editor = {John Shawe{-}Taylor and
Yoram Singer},
title = {Perceptron-Like Performance for Intersections of Halfspaces},
booktitle = {Learning Theory, 17th Annual Conference on Learning Theory, {COLT}
2004, Banff, Canada, July 1-4, 2004, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3120},
pages = {639--640},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-27819-1\_44},
doi = {10.1007/978-3-540-27819-1\_44},
timestamp = {Sun, 21 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/KlivansS04a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isit/FeldmanMSSW04,
author = {Jon Feldman and
Tal Malkin and
Rocco A. Servedio and
Cliff Stein and
Martin J. Wainwright},
title = {{LP} decoding corrects a constant fraction of errors},
booktitle = {Proceedings of the 2004 {IEEE} International Symposium on Information
Theory, {ISIT} 2004, Chicago Downtown Marriott, Chicago, Illinois,
USA, June 27 - July 2, 2004},
pages = {68},
publisher = {{IEEE}},
year = {2004},
url = {https://doi.org/10.1109/ISIT.2004.1365106},
doi = {10.1109/ISIT.2004.1365106},
timestamp = {Thu, 27 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/isit/FeldmanMSSW04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/quant-ph-0411140,
author = {Alp Atici and
Rocco A. Servedio},
title = {Improved Bounds on Quantum Learning Algorithms},
journal = {CoRR},
volume = {quant-ph/0411140},
year = {2004},
url = {http://arxiv.org/abs/quant-ph/0411140},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/quant-ph-0411140.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jmlr/Servedio03,
author = {Rocco A. Servedio},
title = {Smooth Boosting and Learning with Malicious Noise},
journal = {J. Mach. Learn. Res.},
volume = {4},
pages = {633--648},
year = {2003},
url = {http://jmlr.org/papers/v4/servedio03a.html},
timestamp = {Wed, 10 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jmlr/Servedio03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ml/KlivansS03,
author = {Adam R. Klivans and
Rocco A. Servedio},
title = {Boosting and Hard-Core Set Construction},
journal = {Mach. Learn.},
volume = {51},
number = {3},
pages = {217--238},
year = {2003},
url = {https://doi.org/10.1023/A:1022949332276},
doi = {10.1023/A:1022949332276},
timestamp = {Mon, 02 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ml/KlivansS03.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/colt/KhardonS03,
author = {Roni Khardon and
Rocco A. Servedio},
editor = {Bernhard Sch{\"{o}}lkopf and
Manfred K. Warmuth},
title = {Maximum Margin Algorithms with Boolean Kernels},
booktitle = {Computational Learning Theory and Kernel Machines, 16th Annual Conference
on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel
2003, Washington, DC, USA, August 24-27, 2003, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2777},
pages = {87--101},
publisher = {Springer},
year = {2003},
url = {https://doi.org/10.1007/978-3-540-45167-9\_8},
doi = {10.1007/978-3-540-45167-9\_8},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/colt/KhardonS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/AriasKS03,
author = {Marta Arias and
Roni Khardon and
Rocco A. Servedio},
editor = {Bernhard Sch{\"{o}}lkopf and
Manfred K. Warmuth},
title = {Polynomial Certificates for Propositional Classes},
booktitle = {Computational Learning Theory and Kernel Machines, 16th Annual Conference
on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel
2003, Washington, DC, USA, August 24-27, 2003, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2777},
pages = {537--551},
publisher = {Springer},
year = {2003},
url = {https://doi.org/10.1007/978-3-540-45167-9\_39},
doi = {10.1007/978-3-540-45167-9\_39},
timestamp = {Sun, 21 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/AriasKS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/JacksonS03,
author = {Jeffrey C. Jackson and
Rocco A. Servedio},
editor = {Bernhard Sch{\"{o}}lkopf and
Manfred K. Warmuth},
title = {Learning Random Log-Depth Decision Trees under the Uniform Distribution},
booktitle = {Computational Learning Theory and Kernel Machines, 16th Annual Conference
on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel
2003, Washington, DC, USA, August 24-27, 2003, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2777},
pages = {610--624},
publisher = {Springer},
year = {2003},
url = {https://doi.org/10.1007/978-3-540-45167-9\_44},
doi = {10.1007/978-3-540-45167-9\_44},
timestamp = {Sun, 21 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/JacksonS03.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/KalaiS03,
author = {Adam Kalai and
Rocco A. Servedio},
editor = {Lawrence L. Larmore and
Michel X. Goemans},
title = {Boosting in the presence of noise},
booktitle = {Proceedings of the 35th Annual {ACM} Symposium on Theory of Computing,
June 9-11, 2003, San Diego, CA, {USA}},
pages = {195--205},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/780542.780573},
doi = {10.1145/780542.780573},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KalaiS03.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}
}
@article{DBLP:journals/corr/cs-LG-0311042,
author = {Adam R. Klivans and
Rocco A. Servedio},
title = {Toward Attribute Efficient Learning Algorithms},
journal = {CoRR},
volume = {cs.LG/0311042},
year = {2003},
url = {http://arxiv.org/abs/cs/0311042},
timestamp = {Fri, 10 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-LG-0311042.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ml/Servedio02,
author = {Rocco A. Servedio},
title = {{PAC} Analogues of Perceptron and Winnow Via Boosting the Margin},
journal = {Mach. Learn.},
volume = {47},
number = {2-3},
pages = {133--151},
year = {2002},
url = {https://doi.org/10.1023/A:1013633619373},
doi = {10.1023/A:1013633619373},
timestamp = {Mon, 02 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ml/Servedio02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/Servedio02,
author = {Rocco A. Servedio},
title = {Perceptron, Winnow, and {PAC} Learning},
journal = {{SIAM} J. Comput.},
volume = {31},
number = {5},
pages = {1358--1369},
year = {2002},
url = {https://doi.org/10.1137/S0097539798340928},
doi = {10.1137/S0097539798340928},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/Servedio02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alt/Servedio02,
author = {Rocco A. Servedio},
editor = {Nicol{\`{o}} Cesa{-}Bianchi and
Masayuki Numao and
R{\"{u}}diger Reischuk},
title = {On Learning Embedded Midbit Functions},
booktitle = {Algorithmic Learning Theory, 13th International Conference, {ALT}
2002, L{\"{u}}beck, Germany, November 24-26, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2533},
pages = {69--82},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-36169-3\_8},
doi = {10.1007/3-540-36169-3\_8},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/alt/Servedio02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/JacksonKS02,
author = {Jeffrey C. Jackson and
Adam R. Klivans and
Rocco A. Servedio},
title = {Learnability beyond {AC0}},
booktitle = {Proceedings of the 17th Annual {IEEE} Conference on Computational
Complexity, Montr{\'{e}}al, Qu{\'{e}}bec, Canada, May 21-24,
2002},
pages = {26},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/CCC.2002.1004335},
doi = {10.1109/CCC.2002.1004335},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/JacksonKS02.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/stoc/JacksonKS02,
author = {Jeffrey C. Jackson and
Adam R. Klivans and
Rocco A. Servedio},
editor = {John H. Reif},
title = {Learnability beyond {AC0}},
booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing,
May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada},
pages = {776--784},
publisher = {{ACM}},
year = {2002},
url = {https://doi.org/10.1145/509907.510018},
doi = {10.1145/509907.510018},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/JacksonKS02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Servedio01,
author = {Rocco A. Servedio},
title = {On the limits of efficient teachability},
journal = {Inf. Process. Lett.},
volume = {79},
number = {6},
pages = {267--272},
year = {2001},
url = {https://doi.org/10.1016/S0020-0190(01)00137-5},
doi = {10.1016/S0020-0190(01)00137-5},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/Servedio01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ServedioG01,
author = {Rocco A. Servedio and
Steven J. Gortler},
title = {Quantum versus Classical Learnability},
booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational
Complexity, Chicago, Illinois, USA, June 18-21, 2001},
pages = {138--148},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/CCC.2001.933881},
doi = {10.1109/CCC.2001.933881},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ServedioG01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/Servedio01,
author = {Rocco A. Servedio},
editor = {David P. Helmbold and
Robert C. Williamson},
title = {Smooth Boosting and Learning with Malicious Noise},
booktitle = {Computational Learning Theory, 14th Annual Conference on Computational
Learning Theory, {COLT} 2001 and 5th European Conference on Computational
Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19,
2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2111},
pages = {473--489},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-44581-1\_31},
doi = {10.1007/3-540-44581-1\_31},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/colt/Servedio01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/Servedio01a,
author = {Rocco A. Servedio},
editor = {David P. Helmbold and
Robert C. Williamson},
title = {On Learning Monotone {DNF} under Product Distributions},
booktitle = {Computational Learning Theory, 14th Annual Conference on Computational
Learning Theory, {COLT} 2001 and 5th European Conference on Computational
Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19,
2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2111},
pages = {558--573},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-44581-1\_37},
doi = {10.1007/3-540-44581-1\_37},
timestamp = {Sun, 21 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/Servedio01a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/Servedio01,
author = {Rocco A. Servedio},
editor = {Fernando Orejas and
Paul G. Spirakis and
Jan van Leeuwen},
title = {Separating Quantum and Classical Learning},
booktitle = {Automata, Languages and Programming, 28th International Colloquium,
{ICALP} 2001, Crete, Greece, July 8-12, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2076},
pages = {1065--1080},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-48224-5\_86},
doi = {10.1007/3-540-48224-5\_86},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/Servedio01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/KhardonRS01,
author = {Roni Khardon and
Dan Roth and
Rocco A. Servedio},
editor = {Thomas G. Dietterich and
Suzanna Becker and
Zoubin Ghahramani},
title = {Efficiency versus Convergence of Boolean Kernels for On-Line Learning
Algorithms},
booktitle = {Advances in Neural Information Processing Systems 14 [Neural Information
Processing Systems: Natural and Synthetic, {NIPS} 2001, December 3-8,
2001, Vancouver, British Columbia, Canada]},
pages = {423--430},
publisher = {{MIT} Press},
year = {2001},
url = {https://proceedings.neurips.cc/paper/2001/hash/2cad8fa47bbef282badbb8de5374b894-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/KhardonRS01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KlivansS01a,
author = {Adam R. Klivans and
Rocco A. Servedio},
editor = {Jeffrey Scott Vitter and
Paul G. Spirakis and
Mihalis Yannakakis},
title = {Learning {DNF} in time 2\({}^{\mbox{{\~{O}}(n\({}^{\mbox{1/3}}\))}}\)},
booktitle = {Proceedings on 33rd Annual {ACM} Symposium on Theory of Computing,
July 6-8, 2001, Heraklion, Crete, Greece},
pages = {258--265},
publisher = {{ACM}},
year = {2001},
url = {https://doi.org/10.1145/380752.380809},
doi = {10.1145/380752.380809},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KlivansS01a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR01-006,
author = {Rocco A. Servedio},
title = {On Learning Monotone {DNF} under Product Distributions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR01-006}},
year = {2001},
url = {https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-006/index.html},
eprinttype = {ECCC},
eprint = {TR01-006},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR01-006.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Servedio00,
author = {Rocco A. Servedio},
title = {Computational Sample Complexity and Attribute-Efficient Learning},
journal = {J. Comput. Syst. Sci.},
volume = {60},
number = {1},
pages = {161--178},
year = {2000},
url = {https://doi.org/10.1006/jcss.1999.1666},
doi = {10.1006/JCSS.1999.1666},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Servedio00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/Servedio00,
author = {Rocco A. Servedio},
editor = {Nicol{\`{o}} Cesa{-}Bianchi and
Sally A. Goldman},
title = {{PAC} Analogues of Perceptron and Winnow via Boosting the Margin},
booktitle = {Proceedings of the Thirteenth Annual Conference on Computational Learning
Theory {(COLT} 2000), June 28 - July 1, 2000, Palo Alto, California,
{USA}},
pages = {148--157},
publisher = {Morgan Kaufmann},
year = {2000},
timestamp = {Wed, 20 Jun 2018 17:06:15 +0200},
biburl = {https://dblp.org/rec/conf/colt/Servedio00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/Servedio99,
author = {Rocco A. Servedio},
editor = {Shai Ben{-}David and
Philip M. Long},
title = {On {PAC} Learning Using Winnow, Perceptron, and a Perceptron-like
Algorithm},
booktitle = {Proceedings of the Twelfth Annual Conference on Computational Learning
Theory, {COLT} 1999, Santa Cruz, CA, USA, July 7-9, 1999},
pages = {296--307},
publisher = {{ACM}},
year = {1999},
url = {https://doi.org/10.1145/307400.307474},
doi = {10.1145/307400.307474},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/Servedio99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KlivansS99,
author = {Adam R. Klivans and
Rocco A. Servedio},
title = {Boosting and Hard-Core Sets},
booktitle = {40th Annual Symposium on Foundations of Computer Science, {FOCS} '99,
17-18 October, 1999, New York, NY, {USA}},
pages = {624--633},
publisher = {{IEEE} Computer Society},
year = {1999},
url = {https://doi.org/10.1109/SFFCS.1999.814638},
doi = {10.1109/SFFCS.1999.814638},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KlivansS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Servedio99,
author = {Rocco A. Servedio},
editor = {Jeffrey Scott Vitter and
Lawrence L. Larmore and
Frank Thomson Leighton},
title = {Computational Sample Complexity and Attribute-Efficient Learning},
booktitle = {Proceedings of the Thirty-First Annual {ACM} Symposium on Theory of
Computing, May 1-4, 1999, Atlanta, Georgia, {USA}},
pages = {701--710},
publisher = {{ACM}},
year = {1999},
url = {https://doi.org/10.1145/301250.301437},
doi = {10.1145/301250.301437},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Servedio99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-25 01:43 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:
