# Vitaly Feldman

## contact information

Almaden Research Center, San Jose, CA, USA

+14089271013

## links

**Generalization for Adaptively-chosen Estimators via Stable Median**.

V. Feldman and T. Steinke. *Conference on Learning Theory ( COLT)*, 2017.

Also available on arXiv.

**Guilt Free Data Reuse**.

C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth. *Communications of the ACM*, 2017. Research Highlights

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

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

Also available on arXiv.

**On the power of learning from k-wise queries.**.

V. Feldman and B. Ghazi. *Innovations in Theoretical Computer Science ( ITCS)*, 2017.

Also available on arXiv.

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

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

Also available on arXiv.

**Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions**.

V. Feldman, P. Kothari and J. Vondrak. *Algorithmic Learning Theory ( ALT)*, 2017.

Available on arXiv.

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

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

Also available on arXiv.

**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.

Also available on arXiv.

**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.

Also available on arXiv.

**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.

Also available on arXiv.

**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.

Also available on arXiv.

**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.

Also available on arXiv.

**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. *Conference on Learning Theory ( COLT)*, 2014.

*SIAM Journal on Computing*, 2015.

Also available on arXiv.

**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.

Also available on arXiv.

**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.

Also available on arXiv.

**Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy**.

M.F. Balcan and V. Feldman. *Neural Information Processing Systems ( NIPS)*, 2013.

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

Also available on arXiv.

**Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas**.

V. Feldman and J. Vondrak. *IEEE Symposium on Foundations of Computer Science ( FOCS)*, 2013.

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

Also available on arXiv.

**Agnostic Learning of Disjunctions on Symmetric Distributions**.

V. Feldman and P. Kothari. *Journal of Machine Learning Research*, 2016.

Also available on arXiv.

**Learning Coverage Functions and Private Release of Marginals**.

V. Feldman and P. Kothari. *Conference on Learning Theory ( COLT)*, 2014.

Also available on arXiv.

**Learning Using Local Membership Queries**.

P. Awasthi, V. Feldman and V. Kanade. *Conference on Learning Theory ( COLT)*, 2013.

**Best Student Paper award.**

Also available on arXiv.

**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.

Also available on arXiv.

**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*, 2017.

Also available on arXiv and ECCC.

**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. *ACM Symposium on Theory of Computing ( STOC)* : pp. 729-746, 2012.

*Journal of the ACM*, 2014.

**IBM Research 2014 Pat Goldberg Math/CS/EE Best Paper award.**

Also available on arXiv and ECCC.

**Learning DNF Expressions from Fourier Spectrum**.

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

Also available on arXiv.

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

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

Also available on

*arXiv.*

**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.

Also available on

*arXiv.*

**Agnostic Learning of Monomials by Halfspaces is Hard**.

V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu. *IEEE Symposium on Foundations of Computer Science ( FOCS)* : pp. 385-394, 2009.

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

Also available on arXiv and ECCC.

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

V. Feldman. *Journal of Computer and System Sciences* (Special issue on Learning Theory in 2009) .

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

Also available on arXiv and ECCC.

**Sorting and Selection with Imprecise Comparisons**.

M. Ajtai, V. Feldman, A. Hassidim and J. Nelson.

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

*ACM Transactions on Algorithms*, 2016.

Also available on arXiv

**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* 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* 10 : pp. 163-182, 2009.

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

Also available from JMLR website and ECCC.

**Evolvability from Learning Algorithms**.

V. Feldman.

Earlier version in: *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* 410(19) (Special issue on ALT 2007) : pp. 1903-1912, 2009.

Earlier version in: *Algorithmic Learning Theory ( ALT)* : pp. 94-106, 2007. Joint with Neal Wadhwa.

**New Results for Learning Noisy Parities and Halfspaces**.

V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami. *IEEE Symposium on Foundations of Computer Science ( FOCS)* : pp. 563-576, 2006.

Full version of the first two results appears in: On Agnostic Learning of Parities, Monomials and Halfspaces.

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

Also available on ECCC.

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

V. Feldman.

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

Journal version is included in: V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami. On Agnostic Learning of Parities, Monomials and Halfspaces.

*SIAM Journal on Computing*39(2) : pp. 606-645, 2009.

Also available on ECCC.

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

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

Earlier version in: *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* 8 (Special issue on COLT 2005) : pp. 1431-1460, 2007.

Earlier version in: *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* 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* 2 : pp. 359-395, 2002.

Earlier version in: *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.