default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRocco A. Servedio
Person information
- affiliation: Columbia University, New York City, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c145]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio:
Trace Reconstruction from Local Statistical Queries. APPROX/RANDOM 2024: 52:1-52:24- [c144]Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Testing Intersecting and Union-Closed Families. ITCS 2024: 33:1-33:23 - [c143]Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. SODA 2024: 4321-4337 - [c142]Anindya De
, Huan Li, Shivam Nadimpalli, Rocco A. Servedio:
Detecting Low-Degree Truncation. STOC 2024: 1027-1038 - [i109]Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir:
Testing Sumsets is Hard. CoRR abs/2401.07242 (2024) - [i108]Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio:
Detecting Low-Degree Truncation. CoRR abs/2402.08133 (2024) - [i107]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio:
Trace reconstruction from local statistical queries. CoRR abs/2407.11177 (2024) - 2023
- [c141]Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Subset Sum in Time 2n/2 / poly(n). APPROX/RANDOM 2023: 39:1-39:18 - [c140]Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes:
Explicit orthogonal and unitary designs. FOCS 2023: 1240-1260 - [c139]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Approximate Trace Reconstruction from a Single Trace. SODA 2023: 605-637 - [c138]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Testing Convex Truncation. SODA 2023: 4050-4082 - [e6]Barna Saha, Rocco A. Servedio:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023. ACM 2023, ISBN 978-1-4503-9913-5 [contents] - [i106]Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Subset Sum in Time 2n/2/poly(n). CoRR abs/2301.07134 (2023) - [i105]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Testing Convex Truncation. CoRR abs/2305.03146 (2023) - [i104]Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. CoRR abs/2309.12513 (2023) - [i103]Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes:
Explicit orthogonal and unitary designs. CoRR abs/2310.13597 (2023) - [i102]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Gaussian Approximation of Convex Sets by Intersections of Halfspaces. CoRR abs/2311.08575 (2023) - [i101]Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Testing Intersecting and Union-Closed Families. CoRR abs/2311.11119 (2023) - 2022
- [j73]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. J. ACM 69(2): 9:1-9:37 (2022) - [j72]Philip M. Long, Rocco A. Servedio:
The Perils of Being Unhinged: On the Accuracy of Classifiers Minimizing a Noise-Robust Convex Loss. Neural Comput. 34(6): 1488-1499 (2022) - [j71]Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun:
A Lower Bound on Cycle-Finding in Sparse Digraphs. ACM Trans. Algorithms 18(4): 31:1-31:23 (2022) - [j70]Rocco A. Servedio, Li-Yang Tan:
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas. Theory Comput. 18: 1-46 (2022) - [c137]Daniel J. Hsu, Clayton Hendrick Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis:
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. COLT 2022: 283-312 - [c136]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Convex Influences. ITCS 2022: 53:1-53:21 - [c135]Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Average-Case Subset Balancing Problems. SODA 2022: 743-778 - [c134]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. SODA 2022: 779-821 - [c133]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Approximating Sumset Size. SODA 2022: 2339-2357 - [i100]Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis:
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. CoRR abs/2202.05096 (2022) - [i99]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Approximate Trace Reconstruction from a Single Trace. CoRR abs/2211.03292 (2022) - 2021
- [c132]Rocco A. Servedio, Li-Yang Tan:
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. APPROX-RANDOM 2021: 37:1-37:18 - [c131]Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola:
Fourier Growth of Structured 𝔽2-Polynomials and Applications. APPROX-RANDOM 2021: 53:1-53:20 - [c130]Huck Bennett, Anindya De, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis:
Reconstructing weighted voting schemes from partial information about their power indices. COLT 2021: 500-565 - [c129]Anindya De, Rocco A. Servedio:
Weak learning convex sets under normal distributions. COLT 2021: 1399-1428 - [c128]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Learning sparse mixtures of permutations from noisy information. COLT 2021: 1429-1466 - [c127]Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis:
On the Approximation Power of Two-Layer Networks of Random ReLUs. COLT 2021: 2423-2461 - [c126]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. ITCS 2021: 20:1-20:20 - [c125]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Quantitative Correlation Inequalities via Semigroup Interpolation. ITCS 2021: 69:1-69:20 - [c124]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-time trace reconstruction in the smoothed complexity model. SODA 2021: 54-73 - [i98]Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis:
On the Approximation Power of Two-Layer Networks of Random ReLUs. CoRR abs/2102.02336 (2021) - [i97]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane:
Fooling Gaussian PTFs via Local Hyperconcentration. CoRR abs/2103.07809 (2021) - [i96]Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola:
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. CoRR abs/2107.10797 (2021) - [i95]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. CoRR abs/2107.11530 (2021) - [i94]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Approximating Sumset Size. CoRR abs/2107.12367 (2021) - [i93]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Convex Influences. CoRR abs/2109.03107 (2021) - [i92]Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Average-Case Subset Balancing Problems. CoRR abs/2110.14607 (2021) - [i91]Philip M. Long, Rocco A. Servedio:
The perils of being unhinged: On the accuracy of classifiers minimizing a noise-robust convex loss. CoRR abs/2112.04590 (2021) - [i90]Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola:
Fourier growth of structured 𝔽2-polynomials and applications. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j69]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Sharp Bounds for Population Recovery. Theory Comput. 16: 1-20 (2020) - [c123]Clément L. Canonne, Anindya De, Rocco A. Servedio:
Learning from satisfying assignments under continuous distributions. SODA 2020: 82-101 - [c122]Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun:
A Lower Bound on Cycle-Finding in Sparse Digraphs. SODA 2020: 2936-2952 - [c121]Xue Chen, Anindya De, Rocco A. Servedio:
Testing noisy linear functions for sparsity. STOC 2020: 610-623 - [c120]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Gaussian PTFs via local hyperconcentration. STOC 2020: 1170-1183 - [i89]Huck Bennett, Anindya De, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis:
Reconstructing weighted voting schemes from partial information about their power indices. CoRR abs/2007.09599 (2020) - [i88]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-time trace reconstruction in the smoothed complexity model. CoRR abs/2008.12386 (2020) - [i87]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-time trace reconstruction in the low deletion rate regime. CoRR abs/2012.02844 (2020) - [i86]Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Quantitative Correlation Inequalities via Semigroup Interpolation. CoRR abs/2012.12216 (2020)
2010 – 2019
- 2019
- [j68]Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie:
Distribution-free Junta Testing. ACM Trans. Algorithms 15(1): 1:1-1:23 (2019) - [c119]Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha:
Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. APPROX-RANDOM 2019: 44:1-44:18 - [c118]Rocco A. Servedio, Li-Yang Tan:
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. APPROX-RANDOM 2019: 45:1-45:23 - [c117]Eshan Chattopadhyay, Anindya De, Rocco A. Servedio:
Simple and Efficient Pseudorandom Generators from Gaussian Processes. CCC 2019: 4:1-4:33 - [c116]Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha:
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. FOCS 2019: 745-768 - [c115]Anindya De, Philip M. Long, Rocco A. Servedio:
Density Estimation for Shift-Invariant Multidimensional Distributions. ITCS 2019: 28:1-28:20 - [c114]Rocco A. Servedio, Li-Yang Tan:
Pseudorandomness for read-k DNF formulas. SODA 2019: 621-638 - [c113]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling polytopes. STOC 2019: 614-625 - [i85]Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha:
Beyond trace reconstruction: Population recovery from the deletion channel. CoRR abs/1904.05532 (2019) - [i84]Clément L. Canonne, Anindya De, Rocco A. Servedio:
Learning from satisfying assignments under continuous distributions. CoRR abs/1907.01619 (2019) - [i83]Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha:
Efficient average-case population recovery in the presence of insertions and deletions. CoRR abs/1907.05964 (2019) - [i82]Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun:
A Lower Bound on Cycle-Finding in Sparse Digraphs. CoRR abs/1907.12106 (2019) - [i81]Anindya De, Rocco A. Servedio:
Kruskal-Katona for convex sets, with applications. CoRR abs/1911.00178 (2019) - [i80]Xue Chen, Anindya De, Rocco A. Servedio:
Testing noisy linear functions for sparsity. CoRR abs/1911.00911 (2019) - 2018
- [j67]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the Query Complexity of Non-adaptive Junta Testing. J. ACM 65(6): 40:1-40:18 (2018) - [c112]Rocco A. Servedio, Li-Yang Tan:
Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. APPROX-RANDOM 2018: 56:1-56:20 - [c111]Anindya De, Philip M. Long, Rocco A. Servedio:
Learning Sums of Independent Random Variables with Sparse Collective Support. FOCS 2018: 297-308 - [c110]Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie:
Distribution-free junta testing. STOC 2018: 749-759 - [e5]Rocco A. Servedio:
33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA. LIPIcs 102, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-069-9 [contents] - [i79]Rocco A. Servedio, Li-Yang Tan:
Deterministic search for CNF satisfying assignments in almost polynomial time. CoRR abs/1801.03588 (2018) - [i78]Rocco A. Servedio, Li-Yang Tan:
Improved pseudorandom generators from pseudorandom multi-switching lemmas. CoRR abs/1801.03590 (2018) - [i77]Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, Jinyu Xie:
Distribution-free Junta Testing. CoRR abs/1802.04859 (2018) - [i76]Rocco A. Servedio, Li-Yang Tan:
Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits. CoRR abs/1803.04553 (2018) - [i75]Anindya De, Philip M. Long, Rocco A. Servedio:
Learning Sums of Independent Random Variables with Sparse Collective Support. CoRR abs/1807.07013 (2018) - [i74]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. CoRR abs/1808.04035 (2018) - [i73]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Learning sparse mixtures of rankings from noisy information. CoRR abs/1811.01216 (2018) - [i72]Anindya De, Philip M. Long, Rocco A. Servedio:
Density estimation for shift-invariant multidimensional distributions. CoRR abs/1811.03744 (2018) - [i71]Eshan Chattopadhyay, Anindya De, Rocco A. Servedio:
Simple and efficient pseudorandom generators from Gaussian processes. Electron. Colloquium Comput. Complex. TR18 (2018) - [i70]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j66]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
The Inverse Shapley value problem. Games Econ. Behav. 105: 122-147 (2017) - [j65]Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. J. ACM 64(5): 35:1-35:27 (2017) - [c109]Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun:
Sample-Based High-Dimensional Convexity Testing. APPROX-RANDOM 2017: 37:1-37:20 - [c108]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten:
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM 2017: 38:1-38:21 - [c107]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the Query Complexity of Non-Adaptive Junta Testing. CCC 2017: 26:1-26:19 - [c106]Rocco A. Servedio, Li-Yang Tan:
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. FOCS 2017: 813-823 - [c105]Rocco A. Servedio, Li-Yang Tan:
Fooling Intersections of Low-Weight Halfspaces. FOCS 2017: 824-835 - [c104]Rocco A. Servedio, Li-Yang Tan:
What Circuit Classes Can Be Learned with Non-Trivial Savings?. ITCS 2017: 30:1-30:21 - [c103]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Optimal mean-based algorithms for trace reconstruction. STOC 2017: 1047-1056 - [c102]Xi Chen, Igor C. Oliveira, Rocco A. Servedio:
Addition is exponentially harder than counting for shallow monotone circuits. STOC 2017: 1232-1245 - [i69]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Sharp bounds for population recovery. CoRR abs/1703.01474 (2017) - [i68]Rocco A. Servedio, Li-Yang Tan:
Fooling intersections of low-weight halfspaces. CoRR abs/1704.04855 (2017) - [i67]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the query complexity of non-adaptive junta testing. CoRR abs/1704.06314 (2017) - [i66]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten:
Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR abs/1706.05556 (2017) - [i65]Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun:
Sample-based high-dimensional convexity testing. CoRR abs/1706.09362 (2017) - [i64]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the query complexity of non-adaptive junta testing. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j64]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry. SIAM J. Discret. Math. 30(2): 1058-1094 (2016) - [c101]Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson:
Degree and Sensitivity: Tails of Two Distributions. CCC 2016: 13:1-13:23 - [c100]Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson:
Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions. ITCS 2016: 59-70 - [c99]Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Near-optimal small-depth lower bounds for small distance connectivity. STOC 2016: 612-625 - [c98]Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
Poly-logarithmic Frege depth lower bounds via an expander switching lemma. STOC 2016: 644-657 - [i63]Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson:
Degree and Sensitivity: tails of two distributions. CoRR abs/1604.07432 (2016) - [i62]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Optimal mean-based algorithms for trace reconstruction. CoRR abs/1612.03148 (2016) - [i61]Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson:
Degree and Sensitivity: tails of two distributions. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j63]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning Poisson Binomial Distributions. Algorithmica 72(1): 316-357 (2015) - [j62]Dana Ron, Rocco A. Servedio:
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. Algorithmica 72(2): 400-429 (2015) - [j61]Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
Noise Stable Halfspaces are Close to Very Small Juntas. Chic. J. Theor. Comput. Sci. 2015 (2015) - [j60]Clément L. Canonne, Dana Ron, Rocco A. Servedio:
Testing Probability Distributions using Conditional Samples. SIAM J. Comput. 44(3): 540-616 (2015) - [j59]Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits. SIGACT News 46(4): 50-68 (2015) - [c97]Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning Circuits with few Negations. APPROX-RANDOM 2015: 512-527 - [c96]Rocco A. Servedio, Li-Yang Tan, John Wright:
Adaptivity Helps for Testing Juntas. CCC 2015: 264-279 - [c95]Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. FOCS 2015: 1030-1048 - [c94]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Learning from satisfying assignments. SODA 2015: 478-497 - [c93]Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan:
Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries. STOC 2015: 519-528 - [e4]Rocco A. Servedio, Ronitt Rubinfeld:
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. ACM 2015, ISBN 978-1-4503-3536-2 [contents] - [i60]Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An average-case depth hierarchy theorem for Boolean circuits. CoRR abs/1504.03398 (2015) - [i59]Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson:
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. CoRR abs/1508.02420 (2015) - [i58]Xi Chen, Igor C. Oliveira, Rocco A. Servedio:
Addition is exponentially harder than counting for shallow monotone circuits. CoRR abs/1508.03061 (2015) - [i57]Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Near-optimal small-depth lower bounds for small distance connectivity. CoRR abs/1509.07476 (2015) - [i56]Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio:
Addition is exponentially harder than counting for shallow monotone circuits. Electron. Colloquium Comput. Complex. TR15 (2015) - [i55]Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson:
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. Electron. Colloquium Comput. Complex. TR15 (2015) - [i54]Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
An average-case depth hierarchy theorem for Boolean circuits. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j58]Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces. J. ACM 61(2): 11:1-11:36 (2014) - [j57]Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan:
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions. SIAM J. Comput. 43(1): 231-253 (2014) - [j56]Philip M. Long, Rocco A. Servedio:
On the Weight of Halfspaces over Hamming Balls. SIAM J. Discret. Math. 28(3): 1035-1061 (2014) - [j55]Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions. Theory Comput. 10: 27-53 (2014) - [j54]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning k-Modal Distributions via Testing. Theory Comput. 10: 535-570 (2014) - [c92]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions. CCC 2014: 229-240 - [c91]Xi Chen, Rocco A. Servedio, Li-Yang Tan:
New Algorithms and Lower Bounds for Monotonicity Testing. FOCS 2014: 286-295 - [c90]Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan:
On DNF Approximators for Monotone Boolean Functions. ICALP (1) 2014: 235-246 - [c89]Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun:
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms. NIPS 2014: 1844-1852 - [c88]Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio:
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. SODA 2014: 628-644 - [c87]Clément L. Canonne, Dana Ron, Rocco A. Servedio:
Testing equivalence between distributions using conditional samples. SODA 2014: 1174-1192 - [c86]Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun:
Efficient density estimation via piecewise polynomial approximation. STOC 2014: 604-613 - [c85]Anindya De, Rocco A. Servedio:
Efficient deterministic approximate counting for low-degree polynomial threshold functions. STOC 2014: 832-841 - [i53]Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning circuits with few negations. CoRR abs/1410.8420 (2014) - [i52]Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun:
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms. CoRR abs/1411.0169 (2014) - [i51]Xi Chen, Rocco A. Servedio, Li-Yang Tan:
New algorithms and lower bounds for monotonicity testing. CoRR abs/1412.5655 (2014) - [i50]Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan:
Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries. CoRR abs/1412.5657 (2014) - [i49]Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning circuits with few negations. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j53]Ilias Diakonikolas, Rocco A. Servedio:
Improved Approximation of Linear Threshold Functions. Comput. Complex. 22(3): 623-677 (2013) - [j52]Philip M. Long, Rocco A. Servedio:
Algorithms and hardness results for parallel large margin learning. J. Mach. Learn. Res. 14(1): 3105-3128 (2013) - [c84]Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Learning Sums of Independent Integer Random Variables. FOCS 2013: 217-226 - [c83]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry. ICALP (1) 2013: 376-387 - [c82]Philip M. Long, Rocco A. Servedio:
Consistency versus Realizable H-Consistency for Multiclass Classification. ICML (3) 2013: 801-809 - [c81]Philip M. Long, Rocco A. Servedio:
Low-weight halfspaces for sparse boolean vectors. ITCS 2013: 21-36 - [c80]Dana Ron, Rocco A. Servedio:
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. SODA 2013: 1319-1336 - [c79]Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun:
Learning mixtures of structured distributions over discrete domains. SODA 2013: 1380-1394 - [c78]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant:
Testing k-Modal Distributions: Optimal Algorithms via Reductions. SODA 2013: 1833-1852 - [i48]Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun:
Efficient Density Estimation via Piecewise Polynomial Approximation. CoRR abs/1305.3207 (2013) - [i47]Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio:
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. CoRR abs/1307.3621 (2013) - [i46]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions. CoRR abs/1311.7105 (2013) - [i45]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions. CoRR abs/1311.7115 (2013) - [i44]Anindya De, Rocco A. Servedio:
Efficient deterministic approximate counting for low-degree polynomial threshold functions. CoRR abs/1311.7178 (2013) - [i43]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions. Electron. Colloquium Comput. Complex. TR13 (2013) - [i42]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions. Electron. Colloquium Comput. Complex. TR13 (2013) - [i41]Anindya De, Rocco A. Servedio:
Efficient deterministic approximate counting for low degree polynomial threshold functions. Electron. Colloquium Comput. Complex. TR13 (2013) - [i40]Dana Ron, Rocco A. Servedio:
Exponentially improved algorithms and lower bounds for testing signed majorities. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j51]Rocco A. Servedio:
A high-dimensional surprise: technical perspective. Commun. ACM 55(10): 89 (2012) - [j50]Nicole Immorlica, Jonathan Katz, Michael Mitzenmacher, Rocco A. Servedio, Chris Umans:
Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009). SIAM J. Comput. 41(6): 1591-1592 (2012) - [c77]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
The Inverse Shapley Value Problem. ICALP (1) 2012: 266-277 - [c76]Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio:
Private data release via learning thresholds. SODA 2012: 168-187 - [c75]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning k-modal distributions via testing. SODA 2012: 1371-1385 - [c74]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning poisson binomial distributions. STOC 2012: 709-728 - [c73]Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. STOC 2012: 729-746 - [c72]Rocco A. Servedio, Li-Yang Tan, Justin Thaler:
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. COLT 2012: 14.1-14.19 - [c71]Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio:
Tight Bounds on Proper Equivalence Query Learning of DNF. COLT 2012: 31.1-31.18 - [e3]Anupam Gupta, Klaus Jansen, José D. P. Rolim, Rocco A. Servedio:
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. Lecture Notes in Computer Science 7408, Springer 2012, ISBN 978-3-642-32511-3 [contents] - [i39]Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
On the Distribution of the Fourier Spectrum of Halfspaces. CoRR abs/1202.6680 (2012) - [i38]Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. CoRR abs/1206.0985 (2012) - [i37]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry. CoRR abs/1207.2229 (2012) - [i36]Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun:
Learning mixtures of structured distributions over discrete domains. CoRR abs/1210.0864 (2012) - [i35]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Inverse problems in approximate uniform generation. CoRR abs/1211.1722 (2012) - [i34]Clément L. Canonne, Dana Ron, Rocco A. Servedio:
Testing probability distributions using conditional samples. CoRR abs/1211.2664 (2012) - [i33]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
The Inverse Shapley Value Problem. CoRR abs/1212.5132 (2012) - [i32]Clément L. Canonne, Dana Ron, Rocco A. Servedio:
Testing probability distributions using conditional samples. Electron. Colloquium Comput. Complex. TR12 (2012) - [i31]Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. Electron. Colloquium Comput. Complex. TR12 (2012) - [i30]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Inverse Problems in Approximate Uniform Generation. Electron. Colloquium Comput. Complex. TR12 (2012) - [i29]Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
The Inverse Shapley Value Problem. Electron. Colloquium Comput. Complex. TR12 (2012) - [i28]Rocco A. Servedio, Li-Yang Tan, Justin Thaler:
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. Electron. Colloquium Comput. Complex. TR12 (2012) - [i27]Rocco A. Servedio, Emanuele Viola:
On a special case of rigidity. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j49]Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan:
Efficiently Testing Sparse GF(2) Polynomials. Algorithmica 61(3): 580-605 (2011) - [j48]Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
Learning random monotone DNF. Discret. Appl. Math. 159(5): 259-271 (2011) - [j47]Ryan O'Donnell, Rocco A. Servedio:
The Chow Parameters Problem. SIAM J. Comput. 40(1): 165-199 (2011) - [j46]Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer:
Testing Fourier Dimensionality and Sparsity. SIAM J. Comput. 40(4): 1075-1100 (2011) - [c70]Dana Dachman-Soled, Rocco A. Servedio:
A Canonical Form for Testing Boolean Function Properties. APPROX-RANDOM 2011: 460-471 - [c69]Philip M. Long, Rocco A. Servedio:
Learning large-margin halfspaces with more malicious noise. NIPS 2011: 91-99 - [c68]Rocco A. Servedio, Philip M. Long:
Algorithms and hardness results for parallel large margin learning. NIPS 2011: 1314-1322 - [c67]Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu:
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. SODA 2011: 1590-1606 - [c66]Vitaly Feldman, Homin K. Lee, Rocco A. Servedio:
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas. COLT 2011: 273-292 - [i26]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning transformed product distributions. CoRR abs/1103.0598 (2011) - [i25]Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio:
Private Data Release via Learning Thresholds. CoRR abs/1107.2444 (2011) - [i24]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning $k$-Modal Distributions via Testing. CoRR abs/1107.2700 (2011) - [i23]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning Poisson Binomial Distributions. CoRR abs/1107.2702 (2011) - [i22]Roni Khardon, Dan Roth, Rocco A. Servedio:
Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms. CoRR abs/1109.2141 (2011) - [i21]Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio:
Tight Bounds on Proper Equivalence Query Learning of DNF. CoRR abs/1111.1124 (2011) - [i20]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant:
Testing $k$-Modal Distributions: Optimal Algorithms via Reductions. CoRR abs/1112.5659 (2011) - 2010
- [j45]Ryan O'Donnell, Rocco A. Servedio:
New degree bounds for polynomial threshold functions. Comb. 30(3): 327-358 (2010) - [j44]Philip M. Long, Rocco A. Servedio:
Random classification noise defeats all convex potential boosters. Mach. Learn. 78(3): 287-304 (2010) - [j43]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing Halfspaces. SIAM J. Comput. 39(5): 2004-2047 (2010) - [j42]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. SIAM J. Comput. 39(8): 3441-3462 (2010) - [c65]Parikshit Gopalan, Rocco A. Servedio:
Learning and Lower Bounds for AC0 with Threshold Gates. APPROX-RANDOM 2010: 588-601 - [c64]Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions. CCC 2010: 211-222 - [c63]Philip M. Long, Rocco A. Servedio:
Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate. ICML 2010: 703-710 - [c62]Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan:
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. STOC 2010: 533-542 - [p2]Rocco A. Servedio:
Testing by Implicit Learning: A Brief Survey. Property Testing 2010: 197-210 - [p1]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing (Subclasses of) Halfspaces. Property Testing 2010: 334-340 - [i19]Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu:
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. CoRR abs/1010.3484 (2010) - [i18]Vitaly Feldman, Homin K. Lee, Rocco A. Servedio:
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas. Electron. Colloquium Comput. Complex. TR10 (2010) - [i17]Parikshit Gopalan, Rocco A. Servedio:
Learning and Lower Bounds for AC0 with Threshold Gates. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j41]Adam R. Klivans, Philip M. Long, Rocco A. Servedio:
Learning Halfspaces with Malicious Noise. J. Mach. Learn. Res. 10: 2715-2740 (2009) - [j40]Ronitt Rubinfeld, Rocco A. Servedio:
Testing monotone high-dimensional distributions. Random Struct. Algorithms 34(1): 24-44 (2009) - [j39]Marcus Hutter, Rocco A. Servedio:
Preface. Theor. Comput. Sci. 410(19): 1747-1748 (2009) - [j38]Dana Glasner, Rocco A. Servedio:
Distribution-Free Testing Lower Bound for Basic Boolean Functions. Theory Comput. 5(1): 191-216 (2009) - [j37]Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee:
Optimal Cryptographic Hardness of Learning Monotone Functions. Theory Comput. 5(1): 257-282 (2009) - [c61]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing ±1-weight halfspace. APPROX-RANDOM 2009: 646-657 - [c60]Ilias Diakonikolas, Rocco A. Servedio:
Improved Approximation of Linear Threshold Functions. CCC 2009: 161-172 - [c59]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. FOCS 2009: 171-180 - [c58]Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer:
Testing Fourier Dimensionality and Sparsity. ICALP (1) 2009: 500-512 - [c57]Adam R. Klivans, Philip M. Long, Rocco A. Servedio:
Learning Halfspaces with Malicious Noise. ICALP (1) 2009: 609-621 - [c56]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing halfspaces. SODA 2009: 256-264 - [i16]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. CoRR abs/0902.3757 (2009) - [i15]Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions. CoRR abs/0909.4727 (2009) - [i14]Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan:
Average sensitivity and noise sensitivity of polynomial threshold functions. CoRR abs/0909.5011 (2009) - [i13]Ilias Diakonikolas, Rocco A. Servedio:
Improved Approximation of Linear Threshold Functions. CoRR abs/0910.3719 (2009) - [i12]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j36]Adam R. Klivans, Rocco A. Servedio:
Learning intersections of halfspaces with a margin. J. Comput. Syst. Sci. 74(1): 35-48 (2008) - [j35]Ryan O'Donnell, Rocco A. Servedio:
Extremal properties of polynomial threshold functions. J. Comput. Syst. Sci. 74(3): 298-312 (2008) - [j34]Jon Feldman, Ryan O'Donnell, Rocco A. Servedio:
Learning Mixtures of Product Distributions over Discrete Domains. SIAM J. Comput. 37(5): 1536-1564 (2008) - [j33]Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio:
Agnostically Learning Halfspaces. SIAM J. Comput. 37(6): 1777-1805 (2008) - [j32]Alp Atici, Rocco A. Servedio:
Learning unions of omega(1)-dimensional rectangles. Theor. Comput. Sci. 405(3): 209-222 (2008) - [c55]Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
Learning Random Monotone DNF. APPROX-RANDOM 2008: 483-497 - [c54]Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio:
Learning Geometric Concepts via Gaussian Surface Area. FOCS 2008: 541-550 - [c53]Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee:
Optimal Cryptographic Hardness of Learning Monotone Functions. ICALP (1) 2008: 36-47 - [c52]Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan:
Efficiently Testing Sparse GF(2) Polynomials. ICALP (1) 2008: 502-514 - [c51]Philip M. Long, Rocco A. Servedio:
Random classification noise defeats all convex potential boosters. ICML 2008: 608-615 - [c50]Philip M. Long, Rocco A. Servedio:
Adaptive Martingale Boosting. NIPS 2008: 977-984 - [c49]Ryan O'Donnell, Rocco A. Servedio:
The chow parameters problem. STOC 2008: 517-526 - [e2]Rocco A. Servedio, Tong Zhang:
21st Annual Conference on Learning Theory - COLT 2008, Helsinki, Finland, July 9-12, 2008. Omnipress 2008 [contents] - [r1]Rocco A. Servedio:
Learning Constant-Depth Circuits. Encyclopedia of Algorithms 2008 - [i11]Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan:
Efficiently Testing Sparse GF(2) Polynomials. CoRR abs/0805.1765 (2008) - 2007
- [j31]Rocco A. Servedio:
Every Linear Threshold Function has a Low-Weight Approximator. Comput. Complex. 16(2): 180-209 (2007) - [j30]Philip M. Long, Rocco A. Servedio, Hans Ulrich Simon:
Discriminative learning can succeed where generative learning fails. Inf. Process. Lett. 103(4): 131-135 (2007) - [j29]Ariel Elbaz, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
Separating Models of Learning from Correlated and Uncorrelated Data. J. Mach. Learn. Res. 8: 277-290 (2007) - [j28]Homin K. Lee, Rocco A. Servedio, Andrew Wan:
DNF are teachable in the average case. Mach. Learn. 69(2-3): 79-96 (2007) - [j27]Alp Atici, Rocco A. Servedio:
Quantum Algorithms for Learning and Testing Juntas. Quantum Inf. Process. 6(5): 323-348 (2007) - [j26]Ryan O'Donnell, Rocco A. Servedio:
Learning Monotone Decision Trees in Polynomial Time. SIAM J. Comput. 37(3): 827-844 (2007) - [j25]Lisa Hellerstein, Rocco A. Servedio:
On PAC learning algorithms for rich Boolean function classes. Theor. Comput. Sci. 384(1): 66-76 (2007) - [j24]Jon Feldman, Tal Malkin, Rocco A. Servedio, Clifford Stein, Martin J. Wainwright:
LP Decoding Corrects a Constant Fraction of Errors. IEEE Trans. Inf. Theory 53(1): 82-89 (2007) - [c48]Marcus Hutter, Rocco A. Servedio, Eiji Takimoto:
Editors' Introduction. ALT 2007: 1-8 - [c47]Dana Glasner, Rocco A. Servedio:
Distribution-Free Testing Lower Bounds for Basic Boolean Functions. APPROX-RANDOM 2007: 494-508 - [c46]Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan:
Testing for Concise Representations. FOCS 2007: 549-558 - [c45]Michael O. Rabin, Rocco A. Servedio, Christopher Thorpe:
Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations and Applications. LICS 2007: 63-76 - [c44]Zafer Barutçuoglu, Philip M. Long, Rocco A. Servedio:
One-Pass Boosting. NIPS 2007: 73-80 - [c43]Philip M. Long, Rocco A. Servedio:
Boosting the Area under the ROC Curve. NIPS 2007: 945-952 - [e1]Marcus Hutter, Rocco A. Servedio, Eiji Takimoto:
Algorithmic Learning Theory, 18th International Conference, ALT 2007, Sendai, Japan, October 1-4, 2007, Proceedings. Lecture Notes in Computer Science 4754, Springer 2007, ISBN 978-3-540-75224-0 [contents] - [i10]Alp Atici, Rocco A. Servedio:
Quantum Algorithms for Learning and Testing Juntas. CoRR abs/0707.3479 (2007) - [i9]Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan:
Testing for Concise Representations. Electron. Colloquium Comput. Complex. TR07 (2007) - [i8]Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
Learning Random Monotone DNF. Electron. Colloquium Comput. Complex. TR07 (2007) - [i7]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing Halfspaces. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j23]Marta Arias, Aaron Feigelson, Roni Khardon, Rocco A. Servedio:
Polynomial certificates for propositional classes. Inf. Comput. 204(5): 816-834 (2006) - [j22]Adam R. Klivans, Rocco A. Servedio:
Toward Attribute Efficient Learning of Decision Lists and Parities. J. Mach. Learn. Res. 7: 587-602 (2006) - [j21]Rocco A. Servedio:
On learning embedded midbit functions. Theor. Comput. Sci. 350(1): 13-23 (2006) - [j20]Jeffrey C. Jackson, Rocco A. Servedio:
On Learning Random DNF Formulas Under the Uniform Distribution. Theory Comput. 2(8): 147-172 (2006) - [c42]Alp Atici, Rocco A. Servedio:
Learning Unions of omega(1)-Dimensional Rectangles. ALT 2006: 32-47 - [c41]Rocco A. Servedio:
Every Linear Threshold Function has a Low-Weight Approximator. CCC 2006: 18-32 - [c40]Ryan O'Donnell, Rocco A. Servedio:
Learning Monotone Decision Trees in Polynomial Time. CCC 2006: 213-225 - [c39]Jon Feldman, Rocco A. Servedio, Ryan O'Donnell:
PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption. COLT 2006: 20-34 - [c38]Homin K. Lee, Rocco A. Servedio, Andrew Wan:
DNF Are Teachable in the Average Case. COLT 2006: 214-228 - [c37]Philip M. Long, Rocco A. Servedio:
Discriminative Learning Can Succeed Where Generative Learning Fails. COLT 2006: 319-334 - [c36]Philip M. Long, Rocco A. Servedio:
Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions. NIPS 2006: 921-928 - [c35]Rocco A. Servedio:
On PAC Learning Algorithms for Rich Boolean Function Classes. TAMC 2006: 442-451 - [i6]Jon Feldman, Ryan O'Donnell, Rocco A. Servedio:
PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption. CoRR abs/cs/0609093 (2006) - 2005
- [j19]Rocco A. Servedio, Andrew Wan:
Computing sparse permanents faster. Inf. Process. Lett. 96(3): 89-92 (2005) - [j18]Roni Khardon, Dan Roth, Rocco A. Servedio:
Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms. J. Artif. Intell. Res. 24: 341-356 (2005) - [j17]Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio:
Learning DNF from random walks. J. Comput. Syst. Sci. 71(3): 250-265 (2005) - [j16]Adam Tauman Kalai, Rocco A. Servedio:
Boosting in the presence of noise. J. Comput. Syst. Sci. 71(3): 266-290 (2005) - [j15]Roni Khardon, Rocco A. Servedio:
Maximum Margin Algorithms with Boolean Kernels. J. Mach. Learn. Res. 6: 1405-1429 (2005) - [j14]Alp Atici, Rocco A. Servedio:
Improved Bounds on Quantum Learning Algorithms. Quantum Inf. Process. 4(5): 355-386 (2005) - [j13]Jeffrey C. Jackson, Rocco A. Servedio:
Learning Random Log-Depth Decision Trees under Uniform Distribution. SIAM J. Comput. 34(5): 1107-1128 (2005) - [c34]Jeffrey C. Jackson, Rocco A. Servedio:
On Learning Random DNF Formulas Under the Uniform Distribution. APPROX-RANDOM 2005: 342-353 - [c33]Philip M. Long, Rocco A. Servedio:
Martingale Boosting. COLT 2005: 79-94 - [c32]Ariel Elbaz, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
Separating Models of Learning from Correlated and Uncorrelated Data. COLT 2005: 637-651 - [c31]Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio:
Agnostically Learning Halfspaces. FOCS 2005: 11-20 - [c30]Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio:
Every decision tree has an in.uential variable. FOCS 2005: 31-39 - [c29]Jon Feldman, Ryan O'Donnell, Rocco A. Servedio:
Learning mixtures of product distributions over discrete domains. FOCS 2005: 501-510 - [c28]Philip M. Long, Vinay Varadan, Sarah Gilman, Mark Treshock, Rocco A. Servedio:
Unsupervised evidence integration. ICML 2005: 521-528 - [c27]Ronitt Rubinfeld, Rocco A. Servedio:
Testing monotone high-dimensional distributions. STOC 2005: 147-156 - [i5]Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio:
Every decision tree has an influential variable. CoRR abs/cs/0508071 (2005) - [i4]Alp Atici, Rocco A. Servedio:
Learning Unions of $\omega(1)$-Dimensional Rectangles. CoRR abs/cs/0510038 (2005) - 2004
- [j12]Rocco A. Servedio:
Monotone Boolean formulas can approximate monotone linear threshold functions. Discret. Appl. Math. 142(1-3): 181-187 (2004) - [j11]Rocco A. Servedio:
On learning monotone DNF under product distributions. Inf. Comput. 193(1): 57-74 (2004) - [j10]Adam R. Klivans, Rocco A. Servedio:
Learning DNF in time 2Õ(n1/3). J. Comput. Syst. Sci. 68(2): 303-318 (2004) - [j9]Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio:
Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci. 68(4): 808-840 (2004) - [j8]Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio:
Learning functions of k relevant variables. J. Comput. Syst. Sci. 69(3): 421-434 (2004) - [j7]Rocco A. Servedio, Steven J. Gortler:
Equivalences and Separations Between Quantum and Classical Learnability. SIAM J. Comput. 33(5): 1067-1092 (2004) - [c26]Adam R. Klivans, Rocco A. Servedio:
Toward Attribute Efficient Learning of Decision Lists and Parities. COLT 2004: 224-238 - [c25]Adam R. Klivans, Rocco A. Servedio:
Learning Intersections of Halfspaces with a Margin. COLT 2004: 348-362 - [c24]Adam R. Klivans, Rocco A. Servedio:
Perceptron-Like Performance for Intersections of Halfspaces. COLT 2004: 639-640 - [c23]Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright:
LP decoding corrects a constant fraction of errors. ISIT 2004: 68 - [i3]Alp Atici, Rocco A. Servedio:
Improved Bounds on Quantum Learning Algorithms. CoRR quant-ph/0411140 (2004) - 2003
- [j6]Rocco A. Servedio:
Smooth Boosting and Learning with Malicious Noise. J. Mach. Learn. Res. 4: 633-648 (2003) - [j5]Adam R. Klivans, Rocco A. Servedio:
Boosting and Hard-Core Set Construction. Mach. Learn. 51(3): 217-238 (2003) - [c22]Ryan O'Donnell, Rocco A. Servedio:
Extremal properties of polynomial threshold functions. CCC 2003: 3-12 - [c21]Roni Khardon, Rocco A. Servedio:
Maximum Margin Algorithms with Boolean Kernels. COLT 2003: 87-101 - [c20]Marta Arias, Roni Khardon, Rocco A. Servedio:
Polynomial Certificates for Propositional Classes. COLT 2003: 537-551 - [c19]Jeffrey C. Jackson, Rocco A. Servedio:
Learning Random Log-Depth Decision Trees under the Uniform Distribution. COLT 2003: 610-624 - [c18]Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio:
Learning DNF from Random Walks. FOCS 2003: 189-198 - [c17]Adam Kalai, Rocco A. Servedio:
Boosting in the presence of noise. STOC 2003: 195-205 - [c16]Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio:
Learning juntas. STOC 2003: 206-212 - [c15]Ryan O'Donnell, Rocco A. Servedio:
New degree bounds for polynomial threshold functions. STOC 2003: 325-334 - [i2]Adam R. Klivans, Rocco A. Servedio:
Toward Attribute Efficient Learning Algorithms. CoRR cs.LG/0311042 (2003) - 2002
- [j4]Rocco A. Servedio:
PAC Analogues of Perceptron and Winnow Via Boosting the Margin. Mach. Learn. 47(2-3): 133-151 (2002) - [j3]Rocco A. Servedio:
Perceptron, Winnow, and PAC Learning. SIAM J. Comput. 31(5): 1358-1369 (2002) - [c14]Rocco A. Servedio:
On Learning Embedded Midbit Functions. ALT 2002: 69-82 - [c13]Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio:
Learnability beyond AC0. CCC 2002: 26 - [c12]Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio:
Learning Intersections and Thresholds of Halfspaces. FOCS 2002: 177-186 - [c11]Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio:
Learnability beyond AC0. STOC 2002: 776-784 - 2001
- [j2]Rocco A. Servedio:
On the limits of efficient teachability. Inf. Process. Lett. 79(6): 267-272 (2001) - [c10]Rocco A. Servedio, Steven J. Gortler:
Quantum versus Classical Learnability. CCC 2001: 138-148 - [c9]Rocco A. Servedio:
Smooth Boosting and Learning with Malicious Noise. COLT/EuroCOLT 2001: 473-489 - [c8]Rocco A. Servedio:
On Learning Monotone DNF under Product Distributions. COLT/EuroCOLT 2001: 558-573 - [c7]Rocco A. Servedio:
Separating Quantum and Classical Learning. ICALP 2001: 1065-1080 - [c6]Roni Khardon, Dan Roth, Rocco A. Servedio:
Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms. NIPS 2001: 423-430 - [c5]Adam R. Klivans, Rocco A. Servedio:
Learning DNF in time 2Õ(n1/3). STOC 2001: 258-265 - [i1]Rocco A. Servedio:
On Learning Monotone DNF under Product Distributions. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j1]Rocco A. Servedio:
Computational Sample Complexity and Attribute-Efficient Learning. J. Comput. Syst. Sci. 60(1): 161-178 (2000) - [c4]Rocco A. Servedio:
PAC Analogues of Perceptron and Winnow via Boosting the Margin. COLT 2000: 148-157
1990 – 1999
- 1999
- [c3]Rocco A. Servedio:
On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm. COLT 1999: 296-307 - [c2]Adam R. Klivans, Rocco A. Servedio:
Boosting and Hard-Core Sets. FOCS 1999: 624-633 - [c1]Rocco A. Servedio:
Computational Sample Complexity and Attribute-Efficient Learning. STOC 1999: 701-710
Coauthor Index
[c145] [c144] [c143] [c142] [i108] [i107] [c139] [c138] [i105] [i104] [i102] [i101] [c136] [c134] [c133] [i99] [c130] [c129] [c128] [c126] [c125] [c124] [i95] [i94] [i93] [j69] [c123] [c121] [i89] [i88] [i87] [i86] [c117] [c115] [i84] [i81] [i80] [c111] [i75] [i73] [i72] [i71] [j66] [c103] [i69] [j64] [i62] [c94] [c93] [j58] [c92] [c88] [c85] [i50] [c83] [i47] [i46] [i45] [i44] [i43] [i42] [i41] [c77] [c73] [i38] [i37] [i35] [i33] [i31] [i30] [i29]
[j66] [j64] [j63] [j61] [c94] [j58] [j57] [j55] [j54] [c92] [c89] [c88] [c86] [i52] [j53] [c84] [c83] [c79] [c78] [i48] [i47] [i46] [i45] [i43] [i42] [c77] [c75] [c74] [c73] [i39] [i38] [i37] [i36] [i35] [i33] [i31] [i30] [i29] [j49] [c67] [i26] [i24] [i23] [i20] [j42] [c64] [c62] [i19] [c60] [c59] [i16] [i15] [i14] [i13] [i12] [c52] [i11] [c46] [i9]
[j73] [j70] [c132] [i97] [c120] [c118] [c114] [c113] [j67] [c112] [i79] [i78] [i76] [i74] [i70] [j65] [c108] [c107] [c106] [c105] [c104] [i68] [i67] [i66] [i64] [c99] [c98] [j61] [j59] [c97] [c96] [c95] [c93] [i60] [i57] [i54] [j57] [j55] [c91] [c90] [i53] [i51] [i50] [i49] [c84] [c72] [i39] [i28] [c64] [c62] [i15] [i14]
Emmanouil V. Vlatakis-Gkaragkounis
aka: Emmanouil-Vasileios Vlatakis-Gkaragkounis
aka: Emmanouil-Vasileios Vlatakis-Gkaragkounis
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.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:11 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:
