Jump to Content
Roee Engelberg

Roee Engelberg

PhD in Computer Science, Technion.
Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Preview abstract In educational dialogue settings students often provide answers that are incomplete. In other words, there is a gap between the answer the student provides and the perfect answer expected by the teacher. Successful dialogue hinges on the teacher asking about this gap in an effective manner, thus creating a rich and interactive educational experience. Here we focus on the problem of generating such gap-focused questions (GFQ) automatically. We define the task, highlight key desired aspects of a good GFQ, and propose a model that satisfies these. Finally, we provide an evaluation of our generated questions and compare them to manually generated ones, demonstrating competitive performance. View details
    Preview abstract In many computational and economic models of multi-agent interaction, each participant repeatedly "best-responds" to the others' actions. Game theory research on the prominent "best-response dynamics" model typically relies on the premise that the interaction between agents is somehow synchronized. However, in many real-life settings, e.g., internet protocols and large-scale markets, the interaction between participants is asynchronous. We tackle the following important questions: (1) When are best-response dynamics guaranteed to converge to an equilibrium even under asynchrony? (2) What is the (computational and communication) complexity of verifying guaranteed convergence? We show that, in general, verifying guaranteed convergence is intractable. In fact, our main negative result establishes that this task is undecidable. We exhibit, in contrast, positive results for several environments of interest, including complete, computationally-tractable, characterizations of convergent systems. We discuss the algorithmic implications of our results, which extend beyond best-response dynamics to applications such as asynchronous Boolean circuits. View details
    Equilibria in Online Games
    Joseph Seffi Naor
    SIAM Journal on Computing, vol. 45(2) (2016), pp. 232-267
    Weakly-Acyclic (Internet) Routing Games
    Michael Schapira
    Theory Computing Systems, vol. 54(3) (2014), pp. 431-452
    Improved Approximation Algorithms for the Spanning Star Forest Problem
    Ning Chen
    C. Thach Nguyen
    Prasad Raghavendra
    Atri Rudra
    Gyanit Singh
    Algorithmica, vol. 65(3) (2013), pp. 498-516
    Cut Problems in Graphs with a Budget Constraint. Journal of Discrete Algorithms
    Jochen Könemann
    Stefano Leonardi
    Joseph (Seffi) Naor
    J. Discrete Algorithms, vol. 5(2) (2007), pp. 262-279