Vitaly Feldman

From Aug, 2007 I’m a researcher in CS Theory Group at IBM Almaden Research Center.

Before joining the group 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: 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).

Program Committee: Conference on Learning Theory (COLT) 2008.

Recent publications

The Learning Power of Evolution.

With Leslie Valiant

Open Problems/New Directions session of Conference on Learning Theory (COLT), 2008, pp 513-514.

Experience-Induced Neural Circuits That Achieve High Capacity.

With Leslie Valiant

August 2008, Submitted.

On The Power of Membership Queries in Agnostic Learning.

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

Evolvability from Learning Algorithms.

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

Separating Models of Learning with Faulty Teachers (revised Sep 2008).

With Shrenik Shah

To appear in a special issue of Theoretical Computer Science journal on ALT 2007.

On Agnostic Learning of Parities, Monomials and Halfspaces (revised Dec 2007).

With Parikshit Gopalan, Subhash Khot, and Ashok Ponnuswami

To appear in a special issue of SIAM Journal on Computing on FOCS 2006

Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries (revised Jan 2008).

Special issue of the Journal of Computer and System Sciences on Learning Theory papers in 2006 (extended abstract in STOC 2006). 2008.

Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions (revised July 2007)

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

The Complexity of Properly Learning Simple Concept Classes (revised Jan 2007)

With Misha Alekhnovich, Mark Braverman, Adam Klivans, and Toni Pitassi.

Special issue of the Journal of Computer and System Sciences on Learning Theory papers in 2004. 74(1), 2008, pp.16-34 (extended abstract in FOCS 2004)

All journal publications

All conference publications

Ph.D. Thesis. Efficiency and Computational Limitations of Learning Algorithms. Harvard University. January 2007 (revised Jan 2008).

Surveys:

Hardness of Proper Learning.

To appear in The Encyclopedia of Algorithms, Springer-Verlag, 2008.

Statistical Query Learning.

To appear in The Encyclopedia of Algorithms, Springer-Verlag, 2008.

Personal

My favorite hobby is competitive ballroom dancing (aka DanceSport). As usual check the Wikipedia entry for more info about this exciting activity (which incidentally includes a photo of me competing at the MIT Open Competition 2006).

I also enjoy cinema, biking, hiking, skiing, photography, and travel.

Disclaimer.

Void where prohibited. No purchase necessary. Keep out of the reach of children.