☰

Rocco A. Servedio, Ph.D. - Publications

Affiliations: 
Computer Science Columbia University, New York, NY 
 2001 Harvard University, Cambridge, MA, United States 
Area:
Computational Complexity Theory, Randomness in Computing, Computational Learning Theory, Sublinear-time Algorithms
Tree Info Similar researchers PubMed Report error

58 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2019 De A, O’Donnell R, Servedio RA. Optimal mean-based algorithms for trace reconstruction Annals of Applied Probability. 29: 851-874. DOI: 10.1214/18-Aap1394  0.321
2019 Liu Z, Chen X, Servedio RA, Sheng Y, Xie J. Distribution-free Junta Testing Acm Transactions On Algorithms. 15: 1-23. DOI: 10.1145/3264434  0.385
2018 Chen X, Servedio RA, Tan L, Waingarten E, Xie J. Settling the Query Complexity of Non-adaptive Junta Testing Journal of the Acm. 65: 1-18. DOI: 10.1145/3213772  0.588
2018 De A, Servedio RA. A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting Probability Theory and Related Fields. 171: 981-1044. DOI: 10.1007/S00440-017-0804-Y  0.48
2017 Chen X, Servedio RA, Tan L, Waingarten E, Xie J. Settling the Query Complexity of Non-Adaptive Junta Testing Electronic Colloquium On Computational Complexity. 24: 19. DOI: 10.4230/Lipics.Ccc.2017.26  0.587
2017 Håstad J, Rossman B, Servedio RA, Tan L. An Average-Case Depth Hierarchy Theorem for Boolean Circuits Journal of the Acm. 64: 35. DOI: 10.1145/3095799  0.598
2017 De A, Diakonikolas I, Servedio RA. The Inverse Shapley value problem Games and Economic Behavior. 105: 122-147. DOI: 10.1016/J.Geb.2017.06.004  0.366
2016 De A, Diakonikolas I, Servedio RA. A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry Siam Journal On Discrete Mathematics. 30: 1058-1094. DOI: 10.1137/130919143  0.417
2015 Diakonikolas I, Jaiswal R, Servedio RA, Tan L, Wan A. Noise Stable Halfspaces are Close to Very Small Juntas Chicago Journal of Theoretical Computer Science. 2015: 1-13. DOI: 10.4086/Cjtcs.2015.004  0.567
2015 Rossman B, Servedio RA, Tan L. Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits Sigact News. 46: 50-68. DOI: 10.1145/2852040.2852052  0.574
2015 Canonne CL, Ron D, Servedio RA. Testing probability distributions using conditional samples Siam Journal On Computing. 44: 540-616. DOI: 10.1137/130945508  0.347
2015 Daskalakis C, Diakonikolas I, Servedio RA. Learning Poisson Binomial Distributions Algorithmica. 72: 316-357. DOI: 10.1007/S00453-015-9971-3  0.487
2015 Ron D, Servedio RA. Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities Algorithmica. 72: 400-429. DOI: 10.1007/S00453-013-9858-0  0.508
2014 Daskalakis C, Diakonikolas I, Servedio RA. Learning k-Modal Distributions via Testing Theory of Computing. 10: 535-570. DOI: 10.4086/Toc.2014.V010A020  0.374
2014 Diakonikolas I, Servedio RA, Tan L, Wan A. A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions Theory of Computing. 10: 27-53. DOI: 10.4086/Toc.2014.V010A002  0.57
2014 De A, Diakonikolas I, Feldman V, Servedio RA. Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces Journal of the Acm. 61. DOI: 10.1145/2590772  0.73
2014 Long PM, Servedio RA. On the weight of halfspaces over hamming balls Siam Journal On Discrete Mathematics. 28: 1035-1061. DOI: 10.1137/120868402  0.383
2014 Diakonikolas I, Raghavendra P, Servedio RA, Tan LY. Average sensitivity and noise sensitivity of polynomial threshold functions Siam Journal On Computing. 43: 231-253. DOI: 10.1137/110855223  0.638
2013 De A, Diakonikolas I, Servedio RA. Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions. Electronic Colloquium On Computational Complexity. 20: 172. DOI: 10.14288/1.0043373  0.462
2013 Diakonikolas I, Servedio RA. Improved Approximation of Linear Threshold Functions Computational Complexity. 22: 623-677. DOI: 10.1007/S00037-012-0045-5  0.449
2011 Gopalan P, O'Donnell R, Servedio RA, Shpilka A, Wimmer K. Testing fourier dimensionality and sparsity Siam Journal On Computing. 40: 1075-1100. DOI: 10.1137/100785429  0.472
2011 Jackson JC, Lee HK, Servedio RA, Wan A. Learning random monotone DNF Discrete Applied Mathematics. 159: 259-271. DOI: 10.1016/J.Dam.2010.08.022  0.664
2011 Diakonikolas I, Lee HK, Matulef K, Servedio RA, Wan A. Efficiently testing sparse GF(2) polynomials Algorithmica (New York). 61: 580-605. DOI: 10.1007/S00453-010-9426-9  0.659
2010 Diakonikolas I, Gopalan P, Jaiswal R, Servedio RA, Viola E. Bounded independence fools halfspaces Siam Journal On Computing. 39: 3441-3462. DOI: 10.1137/100783030  0.406
2010 Matulef K, O'Donnell R, Rubinfeld R, Servedio RA. Testing Halfspaces Siam Journal On Computing. 39: 2004-2047. DOI: 10.1137/070707890  0.463
2010 Long PM, Servedio RA. Random classification noise defeats all convex potential boosters Machine Learning. 78: 287-304. DOI: 10.1007/S10994-009-5165-Z  0.393
2010 O’Donnell R, Servedio RA. New degree bounds for polynomial threshold functions Combinatorica. 30: 327-358. DOI: 10.1007/S00493-010-2173-3  0.46
2009 Glasner D, Servedio RA. Distribution-Free Testing Lower Bound for Basic Boolean Functions Theory of Computing. 5: 191-216. DOI: 10.4086/Toc.2009.V005A010  0.329
2009 Rubinfeld R, Servedio RA. Testing monotone high-dimensional distributions Random Structures and Algorithms. 34: 24-44. DOI: 10.1002/Rsa.V34:1  0.358
2008 Dachman-Soled D, Lee HK, Malkin T, Servedio RA, Wan A, Wee H. Optimal cryptographic hardness of learning monotone functions Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5125: 36-47. DOI: 10.4086/Toc.2009.V005A013  0.654
2008 O'Donnell R, Servedio RA. The Chow parameters problem Proceedings of the Annual Acm Symposium On Theory of Computing. 517-526. DOI: 10.1137/090756466  0.538
2008 Feldman J, O'Donnell R, Servedio RA. Learning Mixtures of Product Distributions over Discrete Domains Siam Journal On Computing. 37: 1536-1564. DOI: 10.1137/060670705  0.501
2008 Kalai AT, Klivans AR, Mansour Y, Servedio RA. Agnostically Learning Halfspaces Siam Journal On Computing. 37: 1777-1805. DOI: 10.1137/060649057  0.498
2008 Atici A, Servedio RA. Learning unions of ω (1)-dimensional rectangles Theoretical Computer Science. 405: 209-222. DOI: 10.1016/J.Tcs.2008.06.036  0.682
2007 O'Donnell R, Servedio RA. Learning Monotone Decision Trees in Polynomial Time Siam Journal On Computing. 37: 827-844. DOI: 10.1137/060669309  0.458
2007 Long PM, Servedio RA, Simon HU. Discriminative learning can succeed where generative learning fails Information Processing Letters. 103: 131-135. DOI: 10.1016/J.Ipl.2007.03.004  0.437
2007 Atici A, Servedio RA. Quantum algorithms for learning and testing juntas Quantum Information Processing. 6: 323-348. DOI: 10.1007/S11128-007-0061-6  0.67
2007 Lee HK, Servedio RA, Wan A. DNF are teachable in the average case Machine Learning. 69: 79-96. DOI: 10.1007/S10994-007-5007-9  0.594
2007 Servedio RA. Every Linear Threshold Function has a Low-Weight Approximator Computational Complexity. 16: 180-209. DOI: 10.1007/S00037-007-0228-7  0.496
2006 Jackson JC, Servedio RA. On Learning Random DNF Formulas Under the Uniform Distribution Theory of Computing. 2: 147-172. DOI: 10.4086/Toc.2006.V002A008  0.386
2006 Arias M, Feigelson A, Khardon R, Servedio RA. Polynomial certificates for propositional classes Information and Computation. 204: 816-834. DOI: 10.1016/J.Ic.2006.03.001  0.427
2005 Khardon R, Roth D, Servedio RA. Efficiency versus convergence of Boolean kernels for on-line learning algorithms Journal of Artificial Intelligence Research. 24: 341-356. DOI: 10.1613/Jair.1655  0.705
2005 Jackson JC, Servedio RA. Learning Random Log-Depth Decision Trees under Uniform Distribution Siam Journal On Computing. 34: 1107-1128. DOI: 10.1137/S0097539704444555  0.43
2005 Servedio RA, Wan A. Computing sparse permanents faster Information Processing Letters. 96: 89-92. DOI: 10.1016/J.Ipl.2005.06.007  0.394
2005 Atici A, Servedio RA. Improved bounds on quantum learning algorithms Quantum Information Processing. 4: 355-386. DOI: 10.1007/S11128-005-0001-2  0.655
2005 Khardon R, Servedio RA. Maximum Margin Algorithms with Boolean Kernels Journal of Machine Learning Research. 6: 1405-1429. DOI: 10.1007/978-3-540-45167-9_8  0.512
2004 Servedio RA, Gortler SJ. Equivalences and Separations Between Quantum and Classical Learnability Siam Journal On Computing. 33: 1067-1092. DOI: 10.1137/S0097539704412910  0.425
2004 Klivans AR, Servedio RA. Learning intersections of halfspaces with a margin Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science). 3120: 348-362. DOI: 10.1016/J.Jcss.2007.04.012  0.492
2004 Mossel E, O'Donnell R, Servedio RA. Learning functions of k relevant variables Journal of Computer and System Sciences. 69: 421-434. DOI: 10.1016/J.Jcss.2004.04.002  0.516
2004 Klivans AR, Servedio RA. Learning DNF in time 2Õ(n(1/3)) Journal of Computer and System Sciences. 68: 303-318. DOI: 10.1016/J.Jcss.2003.07.007  0.505
2004 Servedio RA. On learning monotone DNF under product distributions Information & Computation. 193: 57-74. DOI: 10.1016/J.Ic.2004.04.003  0.481
2004 Servedio RA. Monotone Boolean formulas can approximate monotone linear threshold functions Discrete Applied Mathematics. 142: 181-187. DOI: 10.1016/J.Dam.2004.02.003  0.393
2003 Servedio RA. Smooth boosting and learning with malicious noise Journal of Machine Learning Research. 4: 633-648. DOI: 10.1162/153244304773936072  0.448
2003 Klivans AR, Servedio RA. Boosting and hard-core set construction Machine Learning. 51: 217-238. DOI: 10.1023/A:1022949332276  0.443
2003 Kalai A, Servedio RA. Boosting in the presence of noise Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 196-205. DOI: 10.1016/J.Jcss.2004.10.015  0.441
2002 Servedio RA. Perceptron, Winnow, and PAC Learning Siam Journal On Computing. 31: 1358-1369. DOI: 10.1137/S0097539798340928  0.51
2002 Servedio R. PAC Analogues of Perceptron and Winnow Via Boosting the Margin Machine Learning. 47: 133-151. DOI: 10.1023/A:1013633619373  0.465
2000 Servedio RA. Computational Sample Complexity and Attribute-Efficient Learning Journal of Computer and System Sciences. 60: 161-178. DOI: 10.1006/Jcss.1999.1666  0.452
Show low-probability matches.