Vitaly Feldman

According to our database1, Vitaly Feldman authored at least 81 papers between 2000 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Tight bounds on 1 approximation and learning of self-bounding functions.
Theor. Comput. Sci., 2020

Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation.
CoRR, 2020

2019
PAC learning with stable and private predictions.
CoRR, 2019

Interaction is necessary for distributed learning with privacy or communication constraints.
CoRR, 2019

Does Learning Require Memorization? A Short Tale about a Long Tail.
CoRR, 2019

Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Locally Private Learning without Interaction Requires Separation.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Private Stochastic Convex Optimization with Optimal Rates.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

The advantages of multiple classes for reducing overfitting from test set reuse.
Proceedings of the 36th International Conference on Machine Learning, 2019

High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.
Proceedings of the Conference on Learning Theory, 2019

Open Problem: How fast can a multiclass test set be overfit?
Proceedings of the Conference on Learning Theory, 2019

Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning?
Proceedings of the Conference on Learning Theory, 2019

2018
Learning without Interaction Requires Separation.
CoRR, 2018

The Everlasting Database: Statistical Validity at a Fair Price.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Generalization Bounds for Uniformly Stable Algorithms.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Privacy Amplification by Iteration.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Calibrating Noise to Variance in Adaptive Data Analysis.
Proceedings of the Conference On Learning Theory, 2018

Privacy-preserving Prediction.
Proceedings of the Conference On Learning Theory, 2018

2017
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.
J. ACM, 2017

Guilt-free data reuse.
Commun. ACM, 2017

Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On the Power of Learning from k-Wise Queries.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Generalization for Adaptively-chosen Estimators via Stable Median.
Proceedings of the 30th Conference on Learning Theory, 2017

A General Characterization of the Statistical Query Complexity.
Proceedings of the 30th Conference on Learning Theory, 2017

Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017

Dealing with Range Anxiety in Mean Estimation via Statistical Queries.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016
Statistical Query Learning.
Encyclopedia of Algorithms, 2016

Hardness of Proper Learning.
Encyclopedia of Algorithms, 2016

Sorting and Selection with Imprecise Comparisons.
ACM Trans. Algorithms, 2016

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
SIAM J. Comput., 2016

Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Conference on Learning Theory 2016: Preface.
Proceedings of the 29th Conference on Learning Theory, 2016

2015
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity.
SIAM J. Comput., 2015

Agnostic learning of disjunctions on symmetric distributions.
J. Mach. Learn. Res., 2015

Statistical Query Algorithms for Stochastic Convex Optimization.
CoRR, 2015

Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy.
Algorithmica, 2015

Preserving Statistical Validity in Adaptive Data Analysis.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate resilience, monotonicity, and the complexity of agnostic learning.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Generalization in Adaptive Data Analysis and Holdout Reuse.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces.
J. ACM, 2014

On the Complexity of Random Satisfiability Problems with Planted Solutions.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's.
CoRR, 2014

Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions.
CoRR, 2014

Learning Coverage Functions and Private Release of Marginals.
Proceedings of The 27th Conference on Learning Theory, 2014

Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces.
Proceedings of The 27th Conference on Learning Theory, 2014

2013
Structure and learning of valuation functions.
SIGecom Exchanges, 2013

Learning Coverage Functions
CoRR, 2013

Provenance-based dictionary refinement in information extraction.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2013

Statistical Active Learning Algorithms.
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Cognitive computing building block: A versatile and efficient digital neuron model for neurosynaptic cores.
Proceedings of the 2013 International Joint Conference on Neural Networks, 2013

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.
Proceedings of the COLT 2013, 2013

Learning Using Local Membership Queries.
Proceedings of the COLT 2013, 2013

2012
Computational Bounds on Statistical Query Learning.
Proceedings of the COLT 2012, 2012

Learning DNF Expressions from Fourier Spectrum.
Proceedings of the COLT 2012, 2012

A complete characterization of statistical query learning with applications to evolvability.
J. Comput. Syst. Sci., 2012

Statistical Algorithms and a Lower Bound for Planted Clique.
Electronic Colloquium on Computational Complexity (ECCC), 2012

The Complexity of Statistical Algorithms
CoRR, 2012

2011
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.
Proceedings of the COLT 2011, 2011

Distribution-Independent Evolvability of Linear Threshold Functions.
Proceedings of the COLT 2011, 2011

2010
Agnostic Learning of Monomials by Halfspaces is Hard.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Distribution-Specific Agnostic Boosting.
Proceedings of the Innovations in Computer Science, 2010

2009
Separating models of learning with faulty teachers.
Theor. Comput. Sci., 2009

On Agnostic Learning of Parities, Monomials, and Halfspaces.
SIAM J. Comput., 2009

Experience-Induced Neural Circuits That Achieve High Capacity.
Neural Computation, 2009

On The Power of Membership Queries in Agnostic Learning.
J. Mach. Learn. Res., 2009

Hardness of approximate two-level logic minimization and PAC learning with membership queries.
J. Comput. Syst. Sci., 2009

Robustness of Evolvability.
Proceedings of the COLT 2009, 2009

2008
Statistical Query Learning.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Hardness of Proper Learning.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

The complexity of properly learning simple concept classes.
J. Comput. Syst. Sci., 2008

Evolvability from learning algorithms.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The Learning Power of Evolution.
Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007
Attribute-Efficient and Non-adaptive Learning of Parities and DNF Expressions.
J. Mach. Learn. Res., 2007

Separating Models of Learning with Faulty Teachers.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006
New Results for Learning Noisy Parities and Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Optimal Hardness Results for Maximizing Agreements with Monomials.
Electronic Colloquium on Computational Complexity (ECCC), 2006

2004
Learnability and Automatizability.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2002
On Using Extended Statistical Queries to Avoid Membership Queries.
J. Mach. Learn. Res., 2002

2000
Sealed calls in Java packages.
Proceedings of the 2000 ACM SIGPLAN Conference on Object-Oriented Programming Systems, 2000


  Loading...