Lev Reyzin


Assistant Professor
Mathematical Computer Science
Department of Mathematics and
Department of Computer Science (courtesy)
University of Illinois at Chicago (UIC)


Consider applying to our Ph.D. program.
We have a strong department in a great city.
Visit my blog.
You should follow me on twitter here.
Occasionally, I post on Google+.
I participate on cstheory.
Google Scholar tracks my publications.
I've started a photostream.
teaching publications talks links vita
Brief bio: I am a tenure-track Assistant Professor at the MSCS department at UIC; I also have a courtesy appointment in Computer Science. Previously, I was a Simons Postdoc at ARC at Georgia Tech, where I was hosted by Santosh Vempala. Before that, I visited John Langford in the machine learning group at Yahoo! Research in New York on an NSF CI-Fellowship. I completed my Ph.D. in the Computer Science department at Yale University in Connecticut, where I was on an NSF Graduate Fellowship. My advisor was Professor Dana Angluin. My alma mater is 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.

My research lies in the theory and practice of machine learning. More details about me and my research are in my cv.

Teaching

Spring 2013 (UIC) MCS 441: Theory of Computation I
Spring 2012 (Georgia Tech) CS 8803/MATH 8833: Discrete Fourier Analysis and Applications

Research

Authors are ordered alphabetically by last name.
Note that in computer science, conferenences constitute the main publication venue.

Ph.D. Dissertation

Lev Reyzin
Active Learning of Interaction Networks
Yale University Doctoral Dissertation, December 2009
nominated by Yale for the 2009 ACM doctoral dissertation award
pdf bibtex slides

Journal Publications

Lev Reyzin
Data Stability in Clustering: A Closer Look
Invited to the ALT 2012 Special Issue of Theoretical Computer Science (TCS)
pdf, revisions forthcoming, (see conference version)

Dana Angluin, James Aspnes, Lev Reyzin
Network Construction with Subgraph Connectivity Constraints
Accepted to the Journal of Combinatorial Optimization (JOCO)
pdf, revisions forthcoming, (see related conference version)

Dana Angluin, James Aspnes, Lev Reyzin
Optimally Learning Social Networks with Activations and Suppressions
In the ALT 2008 Special Issue of Theoretical Computer Science, Volume 411, Issues 29-30 (TCS 2010)
pdf bibtex (see conference version)

Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, Lev Reyzin
Learning Acyclic Probabilistic Circuits Using Test Paths
In the Journal of Machine Learning Research, Volume 10 (JMLR 2009)
pdf bibtex (see conference version)

Dana Angluin, James Aspnes, Jiang Chen, 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 2008)
pdf bibtex (see conference version)

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

Conference Publications

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
In Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC 2013)
pdf eccc arXiv (full version) bibtex

Lev Reyzin
Data Stability in Clustering: A Closer Look
In Proceedings of the 23rd International Conference on Algorithmic Learning Theory (ALT 2012)
pdf arXiv slides bibtex (see journal version)

Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang
Efficient Optimal Learning for Contextual Bandits
In Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011)
pdf arXiv (Nikos's) poster bibtex (see workshop version)

Lev Reyzin
Boosting on a Budget: Sampling for Feature-Efficient Prediction
In Proceedings of the 28th International Conference on Machine Learning (ICML 2011)
pdf slides poster video bibtex (see workshop version)

Elena Grigorescu, Lev Reyzin, Santosh Vempala
On Noise-Tolerant Learning of Sparse Parities and Related Problems
In Proceedings of the 22nd International Conference on Algorithmic Learning Theory (ALT 2011)
pdf slides bibtex

Wei Chu, Lihong Li, Lev Reyzin, Robert E. Schapire
Contextual Bandits with Linear Payoff Functions
In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS 2011)
pdf poster bibtex

Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, Robert E. Schapire
Contextual Bandit Algorithms with Supervised Learning Guarantees
In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS 2011)
notable paper award (see H. Brendan McMahan's discussion paper)
pdf supplement arXiv slides video bibtex

Satyen Kale, Lev Reyzin, Robert E. Schapire
Non-Stochastic Bandit Slate Problems
In Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS 2010)
pdf supplement poster bibtex

Dana Angluin, David Eisenstat, Leonid Kontorovich, Lev Reyzin
Lower Bounds on Learning Random Structures with Statistical Queries
In Proceedings of the 21st International Conference on Algorithmic Learning Theory (ALT 2010)
pdf slides bibtex

Dana Angluin, James Aspnes, Lev Reyzin
Inferring Social Networks from Outbreaks
In Proceedings of the 21st International Conference on Algorithmic Learning Theory (ALT 2010)
pdf slides bibtex (see related journal version)

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

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

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

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

Lev Reyzin, 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 2007)
pdf (Nikhil's) slides bibtex

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

Refereed Workshop Papers

Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang
Efficient Optimal Learning for Contextual Bandits
In the ICML Online Trading off Exploration and Exploitation 2 Workshop (ICMLw 2011)
pdf (Miro's) slides bibtex (see conference version)

Alina Beygelzimer, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin
Aggressive Learning for Contextual Bandits
In the Snowbird Learning Workshop (Snowbird 2011)
pdf (John's) slides bibtex

Lev Reyzin
Boosting on a Feature Budget
In the ICML/COLT Budgeted Learning Workshop (ICMLw 2010)
pdf slides bibtex (see conference version)

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

Miscellaneous

Lev Reyzin
A Review of Famous Puzzles of Great Mathematicians by Miodrag S. Petkoviç
In SIGACT News, Volume 42, Issue 3 (SIGACT 2011)
pdf bibtex

Dave Clarke, David Eppstein, Kaveh Ghasemloo, Lev Reyzin, András Salamon, Peter Shor, Aaron Sterling, Suresh Venkatasubramanian
Questions Answered. In Theory.
In SIGACT News, Volume 41, Issue 4 (SIGACT 2010)
pdf bibtex

Lev Reyzin
Lower Bounds on the VC Dimension of Unions of Concept Classes
Yale University Technical Report YALEU/DCS/TR-1349, April 2006
pdf bibtex

Academic Activities

Some Talks

Talks on my work
Spring 2013: CASSC Plenery Talk. slides
Spring 2013: TTI. "New Algorithms for Contextual Bandits." slides
Summer 2012: Stony Brook, MSR-NYC. "Statistical Algorithms and the Planted Clique Problem" slides
Spring/Summer/Fall 2012: CMU, Google Research, UAlberta, UIC. "New Algorithms for Contextual Bandits." slides
Spring 2012: UIC MSCS. "The Complexity of Statistical Algorithms." slides
Spring 2012: Sandia Labs, Bell Labs, William & Mary, MIT-LL. "From Queries to Bandits: Learning by Interacting." slides
Fall 2011: ALT. "On Noise-Tolerant Learning of Sparse Parities and Related Problems." slides
Fall 2011: UPenn, Yale, Georgia Tech. "The Complexity of Statistical Algorithms." (updated) slides
Summer 2011: ICML. "Boosting on a Budget: Sampling for Feature-Efficient Prediction." slides
Spring 2011: AISTATS. "Contextual Bandit Algorithms with Supervised Learning Guarantees." slides
Fall 2010: ALT. "Lower Bounds on Learning Random Structures with Statistical Queries." slides
Fall 2010: ALT. "Inferring Social Networks from Outbreaks." slides
Summer 2010: Ben Gurion Univ., Yahoo! Research, Georgia Tech. "New Algorithms for Contextual Bandits." slides
Summer 2010: ICML/COLT Budgeted Learning Workshop. "Boosting on a Feature Budget." slides
Spring 2010: ARC at Georgia Tech. "Active Learning of Interaction Networks." slides
Spring 2010: Santa Fe Institute. "Learning Social Networks, Actively and Passively." slides
Spring 2010: IBM TJ Watson. "Learning Analog Circuits, Graphical Models, and Social Networks by Injecting Values." slides
Fall 2009: ALT. "Learning Finite Automata Using Label Queries." slides
Summer 2009: Thesis Defense. "Active Learning of Interaction Networks." slides
Fall 2008: ALT. "Optimally Learning Social Networks with Activations and Suppressions." slides
Summer 2008: COLT. "Learning Acyclic Probabilistic Circuits Using Test Paths." slides
Spring 2008: Yahoo! Research NY. "Learning Hidden Circuits and (Social) Networks by Injecting Values." slides
Fall 2007: Machine Learning Lunch at UMass Amherst. "Learning Hidden Graphs and Circuits with Query Access." slides
Summer 2007: COLT. "Learning Large-Alphabet and Analog Circuits with Value Injection Queries." slides
Fall 2006: Yale. "Learning Graphs with Queries."slides
Summer/Fall 2006: ICML, Princeton Univ., NYAS, Yale. "How Boosting the Margin Can Also Boost Classifier Complexity." slides

Talks on work that is mostly or completely not mine
 Spring 2013: UIC. "Introduction to Boosting" on work mostly by Freund and Schapire. slides
Spring 2007: Yale. "Hardness Results for Learning DNF" on papers by Alekhnovich, Braverman, Feldman, Klivans and Pitassi. slides
Spring 2007: Yale. "Boosting the Margin" on 4 papers authored among Freund, Schapire, Bartlett, Lee, Breiman, and Reyzin. slides
Spring 2006: Yale. "Go is PSPACE Hard" by Lichtenstein and Sipser. slides

Links

UIC Mathematical Computer Science
The CS Theory Q&A Site
ARC at Georgia Tech
Georgia Tech's Computer Science Theory Group
Machine Learning at Yahoo!
Yahoo!'s New York Research Lab
Yahoo! Research
Theoretical Computer Science at Yale
Yale's Graduate Student Theory Group, Clique
Princeton's Computer Science Department
The Association for Computational Learning
The International Machine Learning Society
Sigma Xi, a Scientific Research Society
ACM, the Association for Computing Machinery
SIGACT, ACM's Special Interest Group in Algorithms and Theory

Other

Some of my unpublished research.
I sometimes take photos.
My Erdös number is 3.
I have a math genealogy entry.
Here's my DBLP and my Google Scholar page.

Copyright 2013 © by Lev Reyzin. All rights reserved.
The copyright to my publications is held either by me or by their respective publishers.