Yaron Singer
| Yaron Singer | |
|---|---|
| Born | |
| 🎓 Alma mater | UC Berkeley |
| 💼 Occupation | |
| Known for | Submodular optimization, robust machine learning, mechanism design |
Yaron Singer is a professor of computer science at Harvard University.[1]
He received in his Ph.D. in 2011 from the UC Berkeley with thesis Incentives, Computation, and Networks: Limitations and Possibilities of Algorithmic Mechanism Design under the supervision of Christos Papadimitriou. Before joining Harvard, Singer spent two years in the Algorithms team at Google AI from 2011 to 2013.
Singer is known for breakthrough results in Algorithms,[2] machine learning,[3] algorithmic game theory and mechanism design[4] and social and information networks.[5]
In 2018, together with his student Eric Balkanski, Singer has shown how to design exponentially faster algorithms for submodular maximization. For over 40 years the best known algorithms for submodular maximization had parallel runtime that was linear in the size of the data and improving on this runtime was conjectured to be impossible. Balkanski and Singer showed that constant factor and optimal approximation guarantees are achievable in parallel runtime that is logarithmic in the size of the data.[6][7][8]
References[edit]
- ↑ "Yaron Singer, homepage". yaronsinger.
- ↑ Balkanski, Eric; Singer, Yaron (2018). "The Adaptive Complexity of Maximizing a Submodular Function". Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2018. STOC 2018. pp. 1138–1151. doi:10.1145/3188745.3188752. ISBN 9781450355599. Unknown parameter
|s2cid=ignored (help) Search this book on
- ↑ Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron (2017). "The Limitations of Optimization from Samples". Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017. STOC 2017. pp. 1016–1027. arXiv:1512.06238. doi:10.1145/3055399.3055406. ISBN 9781450345286. Unknown parameter
|s2cid=ignored (help) Search this book on
- ↑ Papadimitriou, Christos; Schapira, Michael; Singer, Yaron (2008). "On the Hardness of Being Truthful". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2008. pp. 250–259. doi:10.1109/FOCS.2008.54. ISBN 978-0-7695-3436-7. Unknown parameter
|s2cid=ignored (help) Search this book on
- ↑ Seeman, Lior; Singer, Yaron (2013). The Adaptive Seeding in Social Networks. FOCS 2013. pp. 459–468. doi:10.1109/FOCS.2013.56. ISBN 978-0-7695-5135-7. Unknown parameter
|s2cid=ignored (help) Search this book on
- ↑ "Best of Last Year—The top Tech Xplore articles of 2018". Tech Xplore.
- ↑ "New Optimization Algorithm Exponentially Speeds Computation". IEEE Spectrum.
- ↑ "Solving problems by computer just got a lot faster". Science News.
This article "Yaron Singer" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Yaron Singer. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
