theory retreat


I am a PhD student at MIT, under the supervision of Konstantinos Daskalakis. I received a Bachelor’s and a Master’s degree from the Technion, Israel, under the supervision of Prof. Yuval Filmus.

Research interests

I am interested in theoretical computer science, especially in learning theory and complexity. My recent works are of the topics of information complexity, Huffman codes, multi armed bandits and streaming algorithms.

Contact information


dagan at




  • Dagan, Y., Filmus, Y., Gabizon, A., & Moran, S. (2017, June). Twenty (simple) questions. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (pp. 9-21). ACM. Link
    Invited presentation in Highlights of Algorithms 2018
  • Dagan, Y., Filmus, Y., Hatami, H., & Li, Y. (2017, June). Trading information complexity for error. In 32nd Computational Complexity Conference (pp. 16:1-16:59). Link
    Appears in the journal ToC CCC2017 Special Issue (ACM)
  • Yuval Dagan, Ohad Shamir. Detecting correlations with little memory and communication. Proceedings of the 31st Conference On Learning Theory, PMLR 75:1145-1198, 2018. Link
  • Yuval Dagan, Coby Crammer. A better resource allocation algorithm with semi bandit feedback. Algorithmic learning theory, 2018.
  • Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran. The entropy of lies: playing twenty questions with a liar. Link

Other research work

  • Yuval Dagan and Saar Zehavi. There is no online sparse regressor with sublinear regret. Presents an answer to the main question asked by Dr. Satyen Kale, published in the open problem section of Conference on Learning Theory 2014. We showed that under standard assumptions on hardness of computation, there is no efficient sparse online learning algorithm with sublinear regret. We did not publish our result.  Link
  • Reuven Cohen, Yuval Dagan and Gabi Nakibly. Procative rerouting in network overlays. Suggests a rerouting algorithm for computer networks. Link

Teaching assistance

Role: delivering tutorials, making and checking homework assignments and exams.


  • Introduction to Machine Learning (winter semester 14/15)
  • Automata and Formal Languages (spring semester 14/15, winter semester 15/16)
  • Complexity Theory (spring semester 15/16)