Publications of Lev Reyzin
Network construction with subgraph connectivity constraints.
J. Comb. Optim.,
29(2):1-15, 2015.
Shift-pessimistic active learning using robust bias-aware prediction.
In Proceedings of the 29th conference on artificial intelligence,
pages 2764-2770. American Association for Artificial Intelligence, 2015. (AAAI).
Training-time optimization of a budgeted booster.
In Proceedings of the 24th international joint conference on artificial intelligence,
pages 3583-3589. 2015. (IJCAI).
Open problem: learning quantum circuits with queries.
In Proceedings of the 28th annual conference on learning theory ,
pages 1767--1769. Journal of Machine Learning Research, 2015. (COLT).
Interactive clustering of linear classes and cryptographic lower bounds.
In Proceedings of the 26th international conference on algorithmic learning theory,
pages 165-176. Springer, 2015. (ALT).
On the computational complexity of mapreduce.
In Proceedings of the 29th international symposium on distributed computing,
pages 1-15. 2015.
Data stability in clustering: a closer look.
Theoret. Comput. Sci.,
558:51--61, 2014. ALT 2012 special issue.
MR3273277
On boosting sparse parities.
In Proceedings of the 28th conference on artificial intelligence,
pages 2055-2016. American Association for Artificial Intelligence, 2014. (AAAI).
On coloring resilient graphs.
In Proceedings of the 39th symposium on the mathematical foundations of computer science,
pages 517-528. Springer, 2014. (MFCS).
Anti-coordination games and stable graph colorings.
In Algorithmic game theory,
pages 122--133. Springer, Heidelberg, 2013. (SAGT).
MR3143312
Statistical algorithms and a lower bound for detecting planted cliques.
In STOC'13---Proceedings of the 2013 ACM Symposium on Theory of Computing,
pages 655-664. ACM, New York, 2013. (STOC).
MR3210827
Data stability in clustering: a closer look.
In Algorithmic learning theory,
pages 184--198. Springer, Heidelberg, 2012. (ALT).
MR3042890
Contextual bandit algorithms with supervised learning guarantees.
Journal of Machine Learning Research - Proceedings Track,
15:19-26, 2011. (AISTATS) Notable paper award.
Contextual bandits with linear payoff functions.
Journal of Machine Learning Research - Proceedings Track,
15:208-214, 2011. (AISTATS).
On noise-tolerant learning of sparse parities and related problems.
In Proceedings of the 22nd international conference on algorithmic learning theory,
pages 413-424. Springer, 2011. (ALT).
Boosting on a budget: sampling for feature-efficient prediction.
In Proceedings of the 28th international conference on machine learning,
pages 529-536. ACM Press, 2011. (ICML).
Efficient optimal learning for contextual bandits.
In Proceedings of the twenty-seventh conference annual conference on uncertainty in artificial intelligence,
pages 169-178. AUAI Press, 2011. (UAI).
Review of famous puzzles of great mathematicians by miodrag s. petkovi&\#231;.
SIGACT News,
42(3):36-39, 2011. Book review.
Optimally learning social networks with activations and suppressions.
Theoret. Comput. Sci.,
411(29-30):2729--2740, 2010. ALT 2008 special issue.
MR2666288
Inferring social networks from outbreaks.
In Algorithmic learning theory,
pages 104--118. Springer, Berlin, 2010. (ALT).
MR2755799
Lower bounds on learning random structures with statistical queries.
In Algorithmic learning theory,
pages 194--208. Springer, Berlin, 2010. (ALT).
MR2755805
Non-stochastic bandit slate problems.
In Advances in neural information processing systems,
pages 1045--1053. 2010. (NIPS).
Questions answered. in theory.: http: //cstheory.stackexchange.com/.
SIGACT News,
41(4):58-60, 2010. Announcement.
Learning acyclic probabilistic circuits using test paths.
J. Mach. Learn. Res.,
10:1881--1911, 2009.
MR2540780
Learning finite automata using label queries.
In Algorithmic learning theory,
pages 171--185. Springer, Berlin, 2009. (ALT).
MR2564226
Optimally learning social networks with activations and suppressions.
In Algorithmic learning theory,
pages 272--286. Springer, Berlin, 2008. (ALT).
MR2540664
Learning acyclic probabilistic circuits using test paths.
In Proceedings of the 21st annual conference on learning theory,
pages 169-179. Omicron, 2008. (COLT).
Learning large-alphabet and analog circuits with value injection queries.
Machine Learning,
72(1-2):113-138, 2008. COLT 2007 special issue.
Learning and verifying graphs using queries with a focus on edge counting.
In Proceedings of the 18th international conference on algorithmic learning theory,
pages 285-297. Springer, 2007. (ALT).
Learning large-alphabet and analog circuits with value injection queries.
In Twentieth annual conference on learning theory,
pages 51-65. Springer, 2007. (COLT) Best student paper award.
On the longest path algorithm for reconstructing trees from distance matrices.
Inf. Process. Lett.,
101(3):98-100, 2007.
How boosting the margin can also boost classifier complexity.
In Proceedings of the 23rd international conference on machine learning,
pages 753--760. ACM Press, 2006. (ICML) Best student paper award.