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
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 (revised Sep 2008)
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)
Ph.D. Thesis. Efficiency and Computational
Limitations of Learning Algorithms. Harvard
University. January 2007 (revised Jan
2008).
Surveys:
To
appear in The Encyclopedia of Algorithms, Springer-Verlag, 2008.
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.