Vitaly Feldman

I'm a research scientist in CS Theory Group at IBM Almaden Research Center.

Before joining the group in Aug 2007 I spent 5 very enjoyable years at Harvard University (as a PhD student advised by Prof. Leslie Valiant and as a postdoc)

Contact: vitaly.edu^gmail.com (note: my_name at us.ibm.com address is for IBM related matters only)

Research

My research interests are primarily in Computational Learning Theory (Wikipedia entry) and Computational Complexity. Recently, I have also been working on understanding of natural learning systems: learning by the brain and evolution as learning. This work is based on the models pioneered by Leslie Valiant (brain, evolvability).

Here are some of my recent works, Ph.D. thesis and surveys, and the complete list of publications (with abstracts).

I've served on the program committees of COLT 2008 and RANDOM 2009.

Recent work

  1. Distribution-Specific Agnostic Boosting.
    ICS 2010.
  2. Agnostic Learning of Monomials by Halfspaces is Hard.
    With Venkatesan Guruswami, Prasad Raghavendra and Yi Wu. FOCS 2009.
  3. A Complete Characterization of Statistical Query Learning with Applications to Evolvability.
    FOCS 2009.
  4. Sorting and Selection with Imprecise Comparisons.
    With Miklos Ajtai, Avinatan Hassidim and Jelani Nelson. ICALP A, 2009.
  5. Robustness of Evolvability.
    COLT 2009.
  6. Experience-Induced Neural Circuits That Achieve High Capacity..
    With Leslie Valiant. Neural Computation 21:10, 2009.
  7. On The Power of Membership Queries in Agnostic Learning.
    COLT 2008; JMLR 10, 2009
  8. Evolvability from Learning Algorithms.
    STOC 2008.
  9. Separating Models of Learning with Faulty Teachers.
    With Shrenik Shah. ALT 2007; TCS 410(19), 2009.
  10. New Results for Learning Noisy Parities and Halfspaces.
    With Parikshit Gopalan, Subhash Khot, and Ashok Ponnuswami. FOCS 2006; SICOMP 39(2), 2009
  11. Optimal Hardness Results for Maximizing Agreements with Monomials.
    CCC 2006; SICOMP 39(2), 2009
  12. Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries.
    STOC 2006; JCSS 75(1), 2009
  13. Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
    COLT 2005; JMLR 8, 2007
  14. The Complexity of Properly Learning Simple Concept Classes.
    With Misha Alekhnovich, Mark Braverman, Adam Klivans, and Toni Pitassi.
    FOCS 2004; JCSS 74(1), 2008

Ph.D. thesis. Efficiency and Computational Limitations of Learning Algorithms. Harvard University. January 2007

Surveys:

  1. The Learning Power of Evolution.
    With Leslie Valiant. Open Problems/New Directions at COLT 2008.
  2. Hardness of Proper Learning.
    The Encyclopedia of Algorithms. Springer-Verlag, 2008
  3. Statistical Query Learning.
    The Encyclopedia of Algorithms. Springer-Verlag, 2008

Personal

I'm married to Polina, a consultant at Blu Skye.

My favorite hobby is competitive ballroom dancing (aka DanceSport). As usual check the Wikipedia entry for more info about this exciting activity. I also enjoy photography, reading, cinema, biking, hiking, skiing, and travel.