publications

My research spans the theory and practice of machine learning, network and data science, and optimization. I often find it helpful to browse, ask, and answer research-related questions on cstheory.stackexchange.com, a theoretical computer science Q&A site where I am also a moderator.

My papers are listed below in reverse chronological order by year. Note that authors on all of my publications appear alphabetically. Citations to my papers can be found on Google Scholar. Paper tags are colored as follows: journal article conference article editorial work manuscript .

2024+

  1. arXiv

2024

  1. ALT
    Slowly Changing Adversarial Bandit Algorithms are Provably Efficient for Discounted MDPs
    Ian A. Kash, Lev Reyzin, Zishun Yu
    In 35th International Conference on Algorithmic Learning Theory. 2024
  2. ISAIM
    On Sample Reuse Methods for Answering k-wise Statistical Queries
    Lev Reyzin, Duan Tu
    In 18th International Symposium on Artificial Intelligence and Mathematics. 2024
  3. ISAIM
    A Model for Optimizing Recalculation Schedules to Minimize Regret
    Bethany Austhof, Lev Reyzin
    In 18th International Symposium on Artificial Intelligence and Mathematics. 2024

2023

  1. JMPAG
    In memory of Yuri Ilyich Lyubich
    Genrich Belitskii, Alexander Blokh, Michael Brin, Yuri Brudnyi, Vladimir Drinfeld, Alexandre Eremenko, Gennadiy Feldman, Svetlana Jitomirskaya, Alexandre A. Kirillov Sr., Valery Kirzhner, Peter Kuchment, Yuri Latushkin, Vladimir Lin, Mikhail Lyubich, Volodymyr A. Marchenko, Alexander Markus, Vitali Milman, Boris Mityagin, Nikolai K. Nikolski, Leonid A. Pastur, Yehuda Pinchover, Svetlana Pokrovsky, Valery L. Pokrovsky, Simeon Reich, Lev Reyzin, Oksana Shatalov, Mikhail Sodin, Ilya M. Spitkovsky, Yuri Tomilov, Anatoly M. Vershik, Mikhail Zaidenberg, Michail Zhitomirskii, Yakov I. Zhitomirskii
    J. Math. Phys. Anal. Geom. 2023
  2. Allerton
    A Unified Analysis of Dynamic Interactive Learning
    Xing Gao, Thomas Maranzatto, Lev Reyzin
    In 59th Annual Allerton Conference on Communication, Control, and Computing. 2023

2022

  1. CCCG
    On the Geometry of Stable Steiner Tree Instances
    James Freitag, Neshat Mohammadi, Aditya Potukuchi, Lev Reyzin
    In 34th Canadian Conference on Computational Geometry. 2022
  2. Allerton
    On Learning a Hidden Directed Graph with Path Queries
    Mano Vikash Janardhanan, Lev Reyzin
    In 58th Annual Allerton Conference on Communication, Control, and Computing. 2022
  3. Allerton
    An Interactive Search Game with Two Agents
    Xing Gao, Lev Reyzin
    In 58th Annual Allerton Conference on Communication, Control, and Computing. 2022
  4. AMAI
    Special Issue on ISAIM 2020
    Lev Reyzin
    Ann. Math. Artif. Intell. 2022

2021

  1. AAAI
    Communication-Aware Collaborative Learning
    Avrim Blum, Shelby Heinecke, Lev Reyzin
    In 35th AAAI Conference on Artificial Intelligence. 2021

2020

  1. arXiv
  2. AMAI
    On biased random walks, corrupted intervals, and learning under adversarial design
    Daniel Berend, Aryeh Kontorovich, Lev Reyzin, Thomas Robinson
    Ann. Math. Artif. Intell. 2020
  3. JAIR
    On the Complexity of Learning a Class Ratio from Unlabeled Data
    Benjamin Fish, Lev Reyzin
    J. Artif. Intell. Res. 2020
  4. ALT
    Sampling Without Compromising Accuracy in Adaptive Data Analysis
    Benjamin Fish, Lev Reyzin, Benjamin I. P. Rubinstein
    In 31st International Conference on Algorithmic Learning Theory. 2020
  5. TCS
    Special issue on ALT 2017
    Steve Hanneke, Lev Reyzin
    Theor. Comput. Sci. 2020

2019

  1. Nature invited review
    article
    Unprovability comes to machine learning
    Lev Reyzin
    Nature. 2019
  2. HCOMP
    Crowdsourced PAC Learning under Classification Noise
    Shelby Heinecke, Lev Reyzin
    In 7th AAAI Conference on Human Computation and Crowdsourcing. 2019

2018

  1. Allerton
    On the Resilience of Bipartite Networks
    Shelby Heinecke, Will Perkins, Lev Reyzin
    In 56th Annual Allerton Conference on Communication, Control, and Computing. 2018

2017

  1. JACM
    Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
    Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao
    J. ACM. 2017
  2. SM
    A simple spectral algorithm for recovering planted partitions
    Sam Cole, Shmuel Friedland, Lev Reyzin
    Special Matrices. 2017
  3. Allerton
    Improved algorithms for distributed boosting
    Jeff Cooper, Lev Reyzin
    In 55th Annual Allerton Conference on Communication, Control, and Computing. 2017
  4. COLT
    Open Problem: Meeting Times for Learning Random Automata
    Benjamin Fish, Lev Reyzin
    In 30th Annual Conference on Learning Theory. 2017
  5. FSTTCS
    Network Construction with Ordered Constraints
    Yi Huang, Mano Vikash Janardhanan, Lev Reyzin
    In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. 2017
  6. IJCAI
    On the Complexity of Learning from Label Proportions
    Benjamin Fish, Lev Reyzin
    In 26th International Joint Conference on Artificial Intelligence. 2017
  7. ALT
    ALT 2017 Proceedings
    Steve Hanneke, Lev Reyzin
    In Proceedings of Machine Learning Research. 2017
  8. AMAI
    Special Issue on ISAIM 2014
    Lisa Hellerstein, Lev Reyzin, György Turán
    Ann. Math. Artif. Intell. 2017

2016

  1. JCN
    Network installation under convex costs
    Alexander Gutfraind, Jeremy Kun, Ádám D. Lelkes, Lev Reyzin
    J. Complex Networks. 2016
  2. AAMAS
    Recovering Social Networks by Observing Votes
    Benjamin Fish, Yi Huang, Lev Reyzin
    In 15th International Conference on Autonomous Agents & Multiagent Systems. 2016

2015

  1. JOCO
    Network construction with subgraph connectivity constraints
    Dana Angluin, James Aspnes, Lev Reyzin
    J. Comb. Optim. 2015
  2. AAAI
    Shift-Pessimistic Active Learning Using Robust Bias-Aware Prediction
    Anqi Liu, Lev Reyzin, Brian D. Ziebart
    In 25th AAAI Conference on Artificial Intelligence. 2015
  3. ALT
    Interactive Clustering of Linear Classes and Cryptographic Lower Bounds
    Ádám D. Lelkes, Lev Reyzin
    In 26th International Conference on Algorithmic Learning Theory. 2015
  4. COLT
    Open Problem: Learning Quantum Circuits with Queries
    Jeremy Kun, Lev Reyzin
    In 28th Annual Conference on Learning Theory. 2015
  5. IJCAI
    Training-Time Optimization of a Budgeted Booster
    Yi Huang, Brian Powers, Lev Reyzin
    In 24th International Joint Conference on Artificial Intelligence. 2015
  6. DISC
    On the Computational Complexity of MapReduce
    Benjamin Fish, Jeremy Kun, Ádám D. Lelkes, Lev Reyzin, György Turán
    In 29th International Symposium on Distributed Computing. 2015

2014

  1. TCS special issue
    for ALT 2012
    Data stability in clustering: A closer look
    Shalev Ben-David, Lev Reyzin
    Theor. Comput. Sci. 2014
  2. AAAI
    On Boosting Sparse Parities
    Lev Reyzin
    In 28th AAAI Conference on Artificial Intelligence. 2014
  3. MFCS
    On Coloring Resilient Graphs
    Jeremy Kun, Lev Reyzin
    In 39th International Symposium on Mathematical Foundations of Computer Science. 2014

2013

  1. STOC
    Statistical algorithms and a lower bound for detecting planted cliques
    Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao
    In 45th Symposium on Theory of Computing Conference. 2013
  2. SAGT
    Anti-coordination Games and Stable Graph Colorings
    Jeremy Kun, Brian Powers, Lev Reyzin
    In 6th International Symposium on Algorithmic Game Theory. 2013

2012

  1. ALT
    Data Stability in Clustering: A Closer Look
    Lev Reyzin
    In 23rd International Conference on Algorithmic Learning Theory. 2012

2011

  1. SIGACT
  2. ALT
    On Noise-Tolerant Learning of Sparse Parities and Related Problems
    Elena Grigorescu, Lev Reyzin, Santosh S. Vempala
    In 22nd International Conference on Algorithmic Learning Theory. 2011
  3. ICML
    Boosting on a Budget: Sampling for Feature-Efficient Prediction
    Lev Reyzin
    In 28th International Conference on Machine Learning. 2011
  4. UAI
    Efficient Optimal Learning for Contextual Bandits
    Miroslav Dudı́k, Daniel J. Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang
    In 27th Conference on Uncertainty in Artificial Intelligence. 2011
  5. AISTATS notable paper
    award
    Contextual Bandit Algorithms with Supervised Learning Guarantees
    Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, Robert E. Schapire
    In 14th International Conference on Artificial Intelligence and Statistics. 2011
  6. AISTATS
    Contextual Bandits with Linear Payoff Functions
    Wei Chu, Lihong Li, Lev Reyzin, Robert E. Schapire
    In 14th International Conference on Artificial Intelligence and Statistics. 2011

2010

  1. TCS special issue
    for ALT 2008
    Optimally learning social networks with activations and suppressions
    Dana Angluin, James Aspnes, Lev Reyzin
    Theor. Comput. Sci. 2010
  2. SIGACT
    Questions answered. in theory.: http://cstheory.stackexchange.com/
    Dave Clarke, David Eppstein, Kaveh Ghasemloo, Lev Reyzin, András Z. Salamon, Peter W. Shor, Aaron Sterling, Suresh Venkatasubramanian
    SIGACT News. 2010
  3. ALT
    Inferring Social Networks from Outbreaks
    Dana Angluin, James Aspnes, Lev Reyzin
    In 21st International Conference on Algorithmic Learning Theory. 2010
  4. ALT
    Lower Bounds on Learning Random Structures with Statistical Queries
    Dana Angluin, David Eisenstat, Leonid Kontorovich, Lev Reyzin
    In 21st International Conference on Algorithmic Learning Theory. 2010
  5. NIPS
    Non-Stochastic Bandit Slate Problems
    Satyen Kale, Lev Reyzin, Robert E. Schapire
    In 24th Annual Conference on Neural Information Processing Systems. 2010

2009

  1. thesis
    Active Learning of Interaction Networks
    Lev Reyzin
    Yale University Doctoral Dissertation. 2009
  2. JMLR
    Learning Acyclic Probabilistic Circuits Using Test Paths
    Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, Lev Reyzin
    J. Mach. Learn. Res. 2009
  3. ALT
    Learning Finite Automata Using Label Queries
    Dana Angluin, Leonor Becerra-Bonache, Adrian-Horia Dediu, Lev Reyzin
    In 20th International Conference on Algorithmic Learning Theory. 2009

2008

  1. MLJ special issue
    for COLT 2007
    Learning large-alphabet and analog circuits with value injection queries
    Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin
    Mach. Learn. 2008
  2. ALT
    Optimallly Learning Social Networks with Activations and Suppressions
    Dana Angluin, James Aspnes, Lev Reyzin
    In 19th International Conference on Algorithmic Learning Theory. 2008
  3. COLT
    Learning Acyclic Probabilistic Circuits Using Test Paths
    Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, Lev Reyzin
    In 21st Annual Conference on Learning Theory. 2008

2007

  1. IPL
    On the longest path algorithm for reconstructing trees from distance matrices
    Lev Reyzin, Nikhil Srivastava
    Inf. Process. Lett. 2007
  2. COLT best student
    paper award
    Learning Large-Alphabet and Analog Circuits with Value Injection Queries
    Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin
    In 20th Annual Conference on Learning Theory. 2007
  3. ALT
    Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
    Lev Reyzin, Nikhil Srivastava
    In 18th International Conference on Algorithmic Learning Theory. 2007

2006

  1. ICML best student
    paper award
    How boosting the margin can also boost classifier complexity
    Lev Reyzin, Robert E. Schapire
    In 23rd International Conference on Machine Learning. 2006