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 am a moderator on cstheory.
Google Scholar tracks my publications.
I've started a photostream.
teaching publications talks links vita

Brief bio: Lev Reyzin is a tenure-track Assistant Professor in the MCS group at UIC's mathematics department. His research focuses on computational and statistical learning, but he is more broadly interested in topics ranging from practical issues in machine learning to the theoretical foundations of computer science. Previously, Lev was a Simons Postdoctoral Fellow at Georgia Tech, and before that, an NSF CI-Fellow at Yahoo! Research, where he tackled problems in computational advertising. Lev received his Ph.D. from Yale under Dana Angluin and his undergraduate degree from Princeton. His work has earned awards at ICML, COLT, and AISTATS, as well as several national fellowships.

More details can be found here.

Teaching

Spring 2014 (UIC) MCS 441: Theory of Computation I
Fall 2013 (UIC) MCS 521: Combinatorial Optimization
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.

Preprints

Jeff Cooper, Lev Reyzin
Improved Algorithms for Distributed Boosting
pdf manuscript

Yi Huang, Brian Powers, Lev Reyzin
Training-Time Optimization of a Budgeted Booster
pdf (see workshop version)

Jeremy Kun, Lev Reyzin
On Coloring Resilient Graphs
posted on arXiv:1402.4376, 2014
arXiv

Will Perkins, Lev Reyzin
On the Resilience of Bipartite Networks
posted on arXiv:1306.5720, 2013
arXiv

Journal Publications

Shalev Ben-David, 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 related conference paper)

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

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

Lev Reyzin
On Boosting Sparse Parities
To appear in the Proceedings of the 28th AAAI Conference on Artificial Intelligence (
AAAI 2014)
pdf (to appear with revisions) (see workshop version)

Jeremy Kun, Brian Powers, Lev Reyzin
Anti-Coordination Games and Stable Graph Colorings
In Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT 2013)
pdf arXiv (Jeremy's) slides bibtex

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) (Ying's) slides 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

Lev Reyzin
On Boosting Sparse Parities
In the 13th International Symposium on Artificial Intelligence and Mathematics (
ISAIM 2014)
pdf slides bibtex (see conference version)

Yi Huang, Brian Powers, Lev Reyzin
Training-Time Optimization of a Budgeted Booster
In the NIPS Resource-Efficient Machine Learning Workshop (
NIPSw 2013)
pdf (Brian's) slides (Brian's) poster bibtex

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

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 slides bibtex

Academic Activities

Some Talks

Talks on my work
Spring 2014: Emory MathCS. "Weights and Measures: Prediction in the Era of Big Data." slides
Spring 2014: ITA. "Training-Time Optimization of a Budgeted Booster." slides
Fall 2013: ISAIM. "On Boosting Sparse Parities." slides
Fall 2013: MSR-NYC. "On the Resilience of Biparite Networks." slides
Fall 2013: UIC Math. "On Finding Planted Cliques and Solving Random Linear Equations." slides
Spring 2013: CASSC Plenery Talk. "Bandit Algorithms for Internet-Scale Applications." 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
Fall 2013: UMS Planary Talk. "Three Great Ideas in Computing." slides
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 2014 © by Lev Reyzin. All rights reserved.
The copyright to my publications is held either by me or by their respective publishers.