**High probability generalization bounds for uniformly stable algorithms with nearly optimal rate**V. Feldman and J. Vondrak

**Learning without Interaction Requires Separation**A. Daniely and V. Feldman

**Amplification by Shuffling: From Local to Central Differential Privacy**U. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, A. Thakurta

*ACM-SIAM Symposium on Discrete Algorithms (***SODA**),
2019.

**Generalization Bounds for Uniformly Stable Algorithms**V. Feldman and J. Vondrak

*Neural Information Processing Systems (***NIPS**),
2018.

**Privacy Amplification by Iteration**V. Feldman, I. Mironov, K. Talwar, A. Thakurta

*IEEE Symposium on Foundations of Computer Science (***FOCS**),
2018.

**Privacy-preserving Prediction**C. Dwork and V. Feldman

*Conference on Learning Theory (***COLT**),
2018.

**The Everlasting Database: Statistical Validity at a Fair Price**B. Woodworth, V. Feldman, S. Rosset and N. Srebro

*Neural Information Processing Systems (***NIPS**),
2018.

**Calibrating Noise to Variance in Adaptive Data Analysis**V. Feldman and T. Steinke

*Conference on Learning Theory (***COLT**),
2018.

**Dealing with Range Anxiety in Mean Estimation via Statistical Queries**V. Feldman

*Algorithmic Learning Theory (***ALT**),
2017.

**Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions**V. Feldman, P. Kothari and J. Vondrak

*Algorithmic Learning Theory (***ALT**),
2017.

**Generalization for Adaptively-chosen Estimators via Stable Median**V. Feldman and T. Steinke

*Conference on Learning Theory (***COLT**),
2017.

**Guilt Free Data Reuse**C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth

*Communications of the ACM
(***CACM**)
,
2017.

Research Highlights

**On the power of learning from k-wise queries**V. Feldman and B. Ghazi

*Innovations in Theoretical Computer Science (***ITCS**),
2017.

**A General Characterization of the Statistical Query Complexity**V. Feldman

*Conference on Learning Theory (***COLT**),
2017.

**Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back**V. Feldman

*Neural Information Processing Systems (***NIPS**),
2016.

**Statistical Query Algorithms for Mean Estimation and Stochastic Convex Optimization**V. Feldman, C. Guzman and S. Vempala

*ACM-SIAM Symposium on Discrete Algorithms (***SODA**),
2017.

**The reusable holdout: Preserving validity in adaptive data analysis**

C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth

*Science* 349(6248)
: pp. 636-638,
2015.
**IBM Research 2015 Pat Goldberg Math/CS/EE Best Paper award.**

Available directly from Science (unfortunately paywalled; email me for a copy).

Supplemental Material (with corrections) and

code.
Detailed versions appear on arXiv:

part I and

part II.

**Generalization in Adaptive Data Analysis and Holdout Reuse**C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth

*Neural Information Processing Systems (***NIPS**),
2015.

**Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS Functions**V. Feldman and J. Vondrak

*IEEE Symposium on Foundations of Computer Science (***FOCS**),
2015.

**Preserving Statistical Validity in Adaptive Data Analysis**C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth

*ACM Symposium on Theory of Computing (***STOC**),
2015.

**Approximate resilience, monotonicity, and the complexity of agnostic learning **D. Dachman-Soled, V. Feldman, L. Tan, A. Wan and K. Wimmer

*ACM-SIAM Symposium on Discrete Algorithms (***SODA**),
2015.

**The Statistical Query Complexity of Learning Sparse Halfspaces**V. Feldman

Open Problem in:

*Conference on Learning Theory (***COLT**),
2014.

**Sample Complexity Bounds on Differentially Private Learning via Communication Complexity**V. Feldman and D. Xiao

*SIAM Journal on Computing
(***SICOMP**)
,
2015.

*Conference on Learning Theory (***COLT**),
2014.

**Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's**V. Feldman, W. Perkins and S. Vempala

*Neural Information Processing Systems (***NIPS**),
2015.

**On the Complexity of Random Satisfiability Problems with Planted Solutions**V. Feldman, W. Perkins and S. Vempala

*ACM Symposium on Theory of Computing (***STOC**),
2015.

**Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy**M.F. Balcan and V. Feldman

*Algorithmica* 72(1)
(Special Issue on New Theoretical Challenges in Machine Learning)
: pp. 282-315,
2015.

*Neural Information Processing Systems (***NIPS**),
2013.

**Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas**V. Feldman and J. Vondrak

*SIAM Journal on Computing
(***SICOMP**)
45(3)
(Special issue on FOCS 2013)
: pp. 1129-1170,
2016.

*IEEE Symposium on Foundations of Computer Science (***FOCS**),
2013.

**Agnostic Learning of Disjunctions on Symmetric Distributions**V. Feldman and P. Kothari

*Journal of Machine Learning Research
(***JMLR**)
,
2016.

**Learning Coverage Functions and Private Release of Marginals**V. Feldman and P. Kothari

*Conference on Learning Theory (***COLT**),
2014.

**Learning Using Local Membership Queries**P. Awasthi, V. Feldman and V. Kanade

*Conference on Learning Theory (***COLT**),
2013.

**Best Student Paper award.**

**Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees**V. Feldman, P. Kothari and J. Vondrak

*Conference on Learning Theory (***COLT**),
2013.

**Provenance-based Dictionary Refinement in Information Extraction**S. Roy, L. Chiticariu, V. Feldman, F. Reiss and H. Zhu

*ACM SIGMOD International Conference on Management of Data (***SIGMOD**),
2013.

**Statistical Algorithms and a Lower Bound for Detecting Planted Cliques**V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala and Y. Xiao

*ACM Symposium on Theory of Computing (***STOC**),
2013.

*Journal of the ACM
(***JACM**)
,
2017.

**Computational Bounds on Statistical Query Learning**V. Feldman and V. Kanade

*Conference on Learning Theory (***COLT**),
2012.

**Nearly Optimal Solutions for the Chow Parameters Problem and Low-weight Approximation of Halfspaces**A. De, I. Diakonikolas, V. Feldman and R. Servedio

*Journal of the ACM
(***JACM**)
,
2014.

**IBM Research 2014 Pat Goldberg Math/CS/EE Best Paper award.***ACM Symposium on Theory of Computing (***STOC**)
: pp. 729-746,
2012.

**Learning DNF Expressions from Fourier Spectrum**V. Feldman

*Conference on Learning Theory (***COLT**),
2012.

**Distribution-Independent Evolvability of Linear Threshold Functions**V. Feldman

*Conference on Learning Theory (***COLT**),
2011.

**Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas**V. Feldman, H. Lee and R. Servedio

*Conference on Learning Theory (***COLT**),
2011.

Also available on

ECCC.

**Distribution-Specific Agnostic Boosting**V. Feldman

*Innovations in Computer Science (***ICS**)
: pp. 241-250,
2010.

**Agnostic Learning of Monomials by Halfspaces is Hard**V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu

*SIAM Journal on Computing
(***SICOMP**)
41(6)
: pp. 1558-1590,
2012.

*IEEE Symposium on Foundations of Computer Science (***FOCS**)
: pp. 385-394,
2009.

**A Complete Characterization of Statistical Query Learning with Applications to Evolvability**V. Feldman

*Journal of Computer and System Sciences
(***JCSS**)
78(5)
(Special issue on Learning Theory in 2009)
: pp. 1444-1459,
2012.

*IEEE Symposium on Foundations of Computer Science (***FOCS**)
: pp. 375-384,
2009.

**Sorting and Selection with Imprecise Comparisons**M. Ajtai, V. Feldman, A. Hassidim and J. Nelson

*International Colloquium on Automata, Languages and Programming (***ICALP**) A
: pp. 37-48,
2009.

*ACM Transactions on Algorithms
(***TALG**)
,
2016.

**Robustness of Evolvability**V. Feldman

*Conference on Learning Theory (***COLT**)
: pp. 277-292,
2009.

**Experience-Induced Neural Circuits That Achieve High Capacity**V. Feldman and L. Valiant

*Neural Computation
(***NeCo**)
21:10
: pp. 2715-2754,
2009.

Also available from

NECO website.

**On The Power of Membership Queries in Agnostic Learning**V. Feldman

*Journal of Machine Learning Research
(***JMLR**)
10
: pp. 163-182,
2009.

*Conference on Learning Theory (***COLT**)
: pp. 147-156,
2008.

Also available from

JMLR website and

ECCC.

**Evolvability from Learning Algorithms**V. Feldman

*ACM Symposium on Theory of Computing (***STOC**)
: pp. 619-628,
2008.

**Separating Models of Learning with Faulty Teachers**V. Feldman and S. Shah

*Theoretical Computer Science
(***TCS**)
410(19)
(Special issue on ALT 2007)
: pp. 1903-1912,
2009.

*Algorithmic Learning Theory (***ALT**)
: pp. 94-106,
2007.

Joint with Neal Wadhwa.

**On Agnostic Learning of Parities, Monomials and Halfspaces**V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami

*SIAM Journal on Computing
(***SICOMP**)
39(2)
(Special issue on FOCS 2006)
: pp. 606-645,
2009.

Includes the results from:

*IEEE Symposium on Foundations of Computer Science (***FOCS**)
: pp. 563-576,
2006.

Also available on

ECCC.

**Optimal Hardness Results for Maximizing Agreement with Monomials**V. Feldman

*IEEE Computational Complexity Conference (***CCC**)
: pp. 226-236,
2006.

Also available on

ECCC. Journal version was merged into the SICOMP paper above.

**Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries**V. Feldman

*Journal of Computer and System Sciences
(***JCSS**)
75(1)
(Special issue on Learning Theory in 2006)
: pp. 13-26,
2009.

*ACM Symposium on Theory of Computing (***STOC**)
: pp. 363-372,
2006.

Also available on

ECCC.

**Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions**V. Feldman

*Journal of Machine Learning Research
(***JMLR**)
8
(Special issue on COLT 2005)
: pp. 1431-1460,
2007.

*Conference on Learning Theory (***COLT**)
: pp. 576-590,
2005.

**Best Student Paper award.**Also available from

JMLR.

**The Complexity of Properly Learning Simple Concept Classes**M. Alekhnovich, M. Braverman, V. Feldman, A. Klivans, and T. Pitassi

*Journal of Computer and System Sciences
(***JCSS**)
74(1)
(Special issue on Learning Theory in 2004)
: pp. 16-34,
2008.

Earlier version:
(Learnability and Automizability).

*IEEE Symposium on Foundations of Computer Science (***FOCS**)
: pp. 521-530,
2004.

**On Using Extended Statistical Queries to Avoid Membership Queries**N. Bshouty and V. Feldman

*Journal of Machine Learning Research
(***JMLR**)
2
: pp. 359-395,
2002.

*Conference on Computational Learning Theory (***COLT**)
: pp. 529-545,
2001.

Also available from

JMLR website.

**Sealed Calls in Java Packages**A. Zaks, V. Feldman and N. Aizikowitz

*ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages & Applications (***OOPSLA**)
: pp. 83-92,
2000.