Vitaly Feldman


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

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

A General Characterization of the Statistical Query Complexity
V. Feldman
Conference on Learning Theory (COLT), 2017.

On the power of learning from k-wise queries
V. Feldman and B. Ghazi
Innovations in Theoretical Computer Science (ITCS), 2017.

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