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
Contact: vitaly.edu^gmail.com
(note: my 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: COLT 2008, RANDOM 2009.
Recent papers
Agnostic Learning of
Monomials by Halfspaces is Hard.
With Venkatesan
Guruswami, Prasad Raghavendra
and Yi Wu.
Apr 2009 (to appear)
A Complete
Characterization of Statistical Query Learning with Applications to Evolvability.
IEEE Symposium on Foundation of
Computer Science (FOCS), 2009 (to appear)
Sorting and Selection with
Imprecise Comparisons (proceedings version.
Full version coming soon)
With Miklos
Ajtai, Avinatan Hassidim
and Jelani Nelson.
International Colloquium on
Automata, Languages and Programming (ICALP), A.
2009 (to appear).
Conference
on Learning Theory (COLT), 2009.
Experience-Induced Neural Circuits That Achieve High Capacity.
With Leslie Valiant
Neural Computation, 2009
(to appear)
The Learning
Power of Evolution.
With Leslie Valiant
Open Problems/New Directions
session of Conference on
Learning Theory (COLT), 2008, pp
513-514.
On The Power of Membership Queries in
Agnostic Learning
Journal of Machine Learning
Research, 10(Feb):163--182, 2009. Extended
abstract in COLT
2008.
Evolvability from Learning Algorithms.
ACM
Symposium on Theory of Computing (STOC), 2008. pp 619-628.
Separating Models of Learning with Faulty
Teachers
With Shrenik
Shah
Theoretical Computer Science journal, 410(19), 2009, pp. 1903-1912 (Special issue on ALT
2007).
On Agnostic Learning of Parities, Monomials
and Halfspaces
With Parikshit
Gopalan, Subhash Khot, and Ashok Ponnuswami
SIAM Journal on Computing 2009 (Special
issue on FOCS 2006). Extended abstracts in CCC 2006 and FOCS 2006.
Hardness of Approximate Two-level Logic
Minimization and PAC Learning with Membership Queries
Journal of Computer and System
Sciences 75(1), 2009, pp. 13-26 (Special issue
on Learning Theory in 2006). Extended abstract in STOC 2006.
Attribute Efficient and Non-adaptive Learning
of Parities and DNF Expressions
Journal of Machine Learning
Research
8(Jul), 2007, pp.1431-1460 (Special issue on COLT 2005).
The Complexity of Properly Learning
Simple Concept Classes
With Misha
Alekhnovich, Mark Braverman,
Adam Klivans, and Toni Pitassi.
Journal of Computer and System
Sciences 74(1),
2008, pp.16-34 (Special issue on Learning Theory in 2004). Extended abstract in
FOCS 2004.
Ph.D. Thesis. Efficiency and Computational
Limitations of Learning Algorithms. Harvard
University. January 2007 (revised Jan
2008).
Surveys:
The
Encyclopedia of Algorithms, Springer-Verlag,
2008.
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 (which incidentally
includes a photo
of me competing at the MIT Open Competition 2006).
I also enjoy
photography, reading, cinema, biking, hiking, skiing, and travel.
Disclaimer.
Void where prohibited. No purchase necessary.
Keep out of the reach of children.