Lev Reyzin

PhD Candidate
Department of Computer Science
Yale University



left. A picture of me on a bridge at Cornell
publications talks links vita (updated 6/18/09)
I am a 4th year Ph.D. student in the Computer Science department at Yale University in Connecticut, on an NSF Graduate Fellowship. Before starting grad school, I graduated from Princeton University where I got a B.S.E. degree in Computer Science and a certificate in Applied Math. I have also spent two summers doing research at Google in California. I am interested in theoretical computer science and machine learning, especially computational learning theory. My advisor is Professor Dana Angluin.

My current research focus within learning theory lies in learning hidden structures such as circuits, networks, and graphs. I am interested in creating and analyzing query models that are motivated by real-world problems, often from biology or systems. I have also done work on boosting and online learning, and I am interested in many other areas in machine learning and theoretical computer science.

Papers

Working Papers

Dana Angluin, James Aspnes, and Lev Reyzin
Network Construction with Subgraph Connectivity Constraints
pdf

Journal Publications

Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, and Lev Reyzin
Learning Acyclic Probabilistic Circuits Using Test Paths
To appear with revisions in the Journal of Machine Learning Research (JMLR)
pdf (see conference version)

Dana Angluin, James Aspnes, and Lev Reyzin
Optimally Learning Social Networks with Activations and Suppressions
To appear in the ALT 2008 Special Issue of Theoretical Computer Science (TCS)
pdf (see conference version)

Dana Angluin, James Aspnes, Jiang Chen, and Lev Reyzin
Learning Large-Alphabet and Analog Circuits with Value Injection Queries
In the COLT 2007 Special Issue of Machine Learning, Volume 72, Issues 1-2 (MLJ), March 2008
pdf bibtex (see conference version)

Lev Reyzin and Nikhil Srivastava
On the Longest Path Algorithm for Reconstructing Trees from Distance Matrices
In Information Processing Letters, Volume 101, Issue 3 (IPL), February 2007
pdf bibtex

Conference Publications

Dana Angluin, Leonor Becerra-Bonache, Adrian Horia Dediu, and Lev Reyzin
Learning Finite Automata Using Label Queries
In Proceedings of the 20th International Conference on Algorithmic Learning Theory (ALT), October 2009
pdf (to appear with revisions)

Dana Angluin, James Aspnes, and Lev Reyzin
Optimally Learning Social Networks with Activations and Suppressions
In Proceedings of the 19th International Conference on Algorithmic Learning Theory (ALT), October 2008
pdf slides bibtex (see journal version)

Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, and Lev Reyzin
Learning Acyclic Probabilistic Circuits Using Test Paths
In Proceedings of the 21st Annual Conference on Learning Theory (COLT), July 2008
pdf slides bibtex (see journal version)

Lev Reyzin and Nikhil Srivastava
Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
In Proceedings of the 18th International Conference on Algorithmic Learning Theory (ALT), October 2007
pdf (co-author's) slides bibtex

Dana Angluin, James Aspnes, Jiang Chen, and Lev Reyzin
Learning Large-Alphabet and Analog Circuits with Value Injection Queries
In Proceedings of the 20th Annual Conference on Learning Theory (COLT), June 2007
won the best student paper award
pdf slides bibtex (see journal version)

Lev Reyzin and Robert E. Schapire
How Boosting the Margin Can Also Boost Classifier Complexity
In Proceedings of the 23rd International Conference on Machine Learning (ICML), June 2006
won the best student paper award and named one of three "outstanding papers"
pdf slides bibtex

Workshop Papers

Lev Reyzin
2 Player Tetris is PSPACE Hard
In the Abstracts of the 16th Annual Fall Workshop on Computational Geometry (FWCG), November 2006
pdf bibtex

Academic Activities

Talks

Fall 2008: ALT 2008. "Optimally Learning Social Networks with Activations and Suppressions" by Angluin, Aspnes, and Reyzin. slides
Summer 2008: COLT 2008. "Learning Acyclic Probabilistic Circuits Using Test Paths" by Angluin, Aspnes, Chen, Eisenstat, and Reyzin. slides
Spring 2008: Yahoo! Research, NY. "Learning Hidden Circuits and (Social) Networks by Injecting Values" by Angluin, Aspnes, and Reyzin. slides
Fall 2007: Machine Learning Lunch, UMass Amherst. "Learning Hidden Graphs and Circuits with Query Access" on AACR'07 and RS'07. slides
Summer 2007: COLT 2007. "Learning Large-Alphabet and Analog Circuits with Value Injection Queries" by Angluin, Aspnes, Chen, and Reyzin. slides
Spring 2007: Clique, Yale University. "Hardness Results for Learning DNF" on papers by Alekhnovich, Braverman, Feldman, Klivans and Pitassi. slides
Spring 2007: Clique, Yale University. "Boosting the Margin" on 4 papers authored among Freund, Schapire, Bartlett, Lee, Breiman, and Reyzin. slides
Fall 2006: Clique, Yale University. "Learning Graphs with Queries" on works authored among Angluin, Chen, Reyzin, and Srivastava slides
Summer/Fall 2006: ICML 2006, Princeton, NYAS. "How Boosting the Margin Can Also Boost Classifier Complexity" by Reyzin and Schapire. slides
Spring 2006: Clique, Yale University. "Go is PSPACE Hard" by Lichtenstein and Sipser. slides
Fall 2005: Clique, Yale University. A talk on boosting results by Reyzin and Schapire. slides

Links

Theoretical Computer Science at Yale
Yale's Graduate Student Theory Group, Clique
The Association for Computational Learning
Sigma Xi, a Scientific Research Society
ACM, the Association for Computing Machinery
SIGACT, ACM's Theory Group

Other

My unpublished research
I sometimes take photos.
My Erdös number is 3.
Check out my DBLP entry
vita