Publications

General Scientific Journals (Biology/Physics/Sociology)

  1. Intermittent inverse-square Lévy walks are optimal for finding targets of all sizes
    • B. Guinard and A. Korman.
      (A. Korman is the corresponding author).
    • Mathematical analysis can be found here.
    • Science Advances, 2021.


  1. Sequential Decision-Making in Ants and Implications to the Evidence Accumulation Decision Model
    • O. Ayalon, Y. Sternklar, E. Fonio, A. Korman, N. S. Gov, and O. Feinerman
    • Frontiers in Applied Mathematics and Statistics| Dynamical Systems, 2021.


  1. On the role of hypocrisy in escaping the tragedy of the commons
    • A. Korman, and R. Vacus
      (A. Korman is the corresponding author).
    • Scientific Reports, 2021.


  1. Ant collective cognition allows for efficient navigation through disordered environments
    • A. Gelblum, E. Fonio, Y. Rodeh, A. Korman, and O. Feinerman.
      (A. Korman and O. Feinerman are joint corresponding authors).
    • eLife, 2020.


  1. Reinforcement Learning Enables Resource-Partitioning in Foraging Bats
    • A. Goldshtein, M. Handel, O. Eitan, A. Bonstein, T. Shaler, S. Collet, S. Greif, R. A. Medellin, Y. Emek, A. Korman, and Y. Yovel.
      (A. Korman and Y. Yovel are joint corresponding authors).
    • Mathematical analysis can be found here.
    • Comments: An article centered around this paper appeared in the daily Israeli newspaper Ynet, as well as on the French INS2I’s website.
    • Current Biology, 2020.


  1. Limits on reliable information flows through stochastic populations

    • L. Boczkowski, E. Natale, O. Feinerman, and A. Korman.
      (A. Korman and O. Feinerman are joint corresponding authors).
    • Mathematical analysis can be found here.
    • PLoS Computational Biology, 2018.


  2. A locally-blazed ant trail achieves efficient collective navigation despite limited information

    • E. Fonio, Y. Heyman, L. Boczkowski, A. Gelblum, A. Kosowski, A. Korman, and O. Feinerman
      (A. Korman and O. Feinerman are joint corresponding authors).
    • Mathematical analysis can be found here.
    • Comments: Articles centered around this paper appeared in Le Monde and Haaretz daily newspapers, as well as in interstices and CNRS News.
    • eLife, 2016.


  1. Individual versus Collective Cognition in Social Insects

    • O. Feinerman and A. Korman.
    • J. of Experimental Biology (JEB), 2017.


  2. Confidence Sharing: an Economic Strategy for Efficient Information Flows in Animal Groups

    • A. Korman, E. Greenwald and O. Feinerman.
    • PLoS Computational Biology 2014.


Publications in Theoretical Computer Science

Search, Foraging, and Navigation

  1. Navigating in Trees with Permanently Noisy Advice

    • L. Boczkowski, U. Feige, A. Korman, and Y. Rodeh.
    • ACM Transactions on Algorithms (TALG), 2021.


  2. Multi-Round Cooperative Search Games with Multiple Players

    • A. Korman, and Y. Rodeh.
    • Journal of Computer and System Sciences (JCSS), 2020.
    • Extended abstract apppeared in ICALP 2019.
    • Comments: Selected to appear on the special issue of ICALP 2019 in JCSS.


  3. Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths

    • B. Guinard, and A. Korman.
    • STACS, 2020.


  4. Parallel Bayesian Search with no Coordination

    • P. Fraigniaud, A. Korman, and Y. Rodeh.
    • Journal of the ACM (J. ACM), 2019.
    • Extended abstracts appeared in SIROCCO 2017 and STOC 2016.


  5. Intense Competition can Drive Selfish Explorers to Optimize Coverage

    • S. Collet and A. Korman.
    • SPAA 2018.

  6. Searching a Tree with Permanently Noisy Advice

    • L. Boczkowski, A. Korman, and Y. Rodeh.
    • ESA 2018.

  7. Random Walks with Multiple Step Lengths
    • L. Boczkowski, B. Guinard, Z. Lotker, M. Renault, and A. Korman.
    • LATIN 2018.

  8. The ANTS Problem

    • O. Feinerman and A. Korman.
    • Distributed Computing (DC), 2017.
    • Extended abstracts appeared in PODC 2012 (together with Z. Lotker and J.S. Sereni) and in DISC 2012.

  9. Label-Guided Graph Exploration by a Finite Automation

    • R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg.
    • ACM Transactions on Algorithms (TALG), 2008.
    • Extended abstract appeared in ICALP 2005.

New Models of Computation under Uncertainty 

  1. The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback
    • A. Korman and Y. Rodeh.
    • ACM Transactions on Algorithms (TALG), 2018.
    • Extended abstract appeared in ICALP(A) 2017.

  2. Limits for Rumor Spreading in Stochastic Populations
    • L. Boczkowski, O. Feinerman, A. Korman, and E. Natale.
    • ITCS 2018.

  3. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits

    • L. Boczkowski, A. Korman, and E. Natale.
    • Distributed Computing, 2019.
    • Extended abstract appeared in SODA 2017.

  4. Breathe before Speaking: Efficient Information Dissemination despite Noisy, Limited and Anonymous Communication

    • O. Feinerman, B. Haeupler, and A. Korman.
    • Distributed Computing (DC), 2017.
    • Extended abstract appeared in PODC 2014.
    • Comments: Selected for the special issue of PODC 2014 in DC.

  5. Online Computation with Advice

    • Y. Emek, P. Fraigniaud, A. Korman and A. Rosen.
    • Theoretical Computer Science (TCS) 412(24), 2011.
    • Extended abstract appeared in ICALP 2009.
    • Comments: Selected to appear on the special issue of ICALP 2009 in TCS.

Distributed Decision

  1. Towards a Complexity Theory for Local Distributed Computing

    • P. Fraigniaud, A. Korman, and D. Peleg.
    • Journal of the ACM (J.ACM), 2013.
    • Extended abstract appeared in FOCS 2011.

  2. Distributed Verification and Hardness of Distributed Approximation

    • A. Das Sharma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg and R. Wattenhofer.
    • SIAM Journal on Computing (SICOMP), 2012.
    • Extended abstract appeared in STOC 2011.
    • Comments: Selected to appear on the special issue of STOC 2011 in SICOMP.

  3. Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST

    • A. Korman, S. Kutten and T. Masuzawa.
    • Distributed Computing (DC), 2015.
    • Extended abstract appeared in PODC 2011.
    • Comments: Selected to appear on the special issue of PODC 2011 in DC.

  4. Tight Bounds for Distributed MST Verification

    • L. Kor, A. Korman and D. Peleg.
    • Theory of Computing Systems (ToCS), 2013.
    • Extended abstract appeared in STACS 2011.
    • Comments: Selected to appear on the special issue of STACS 2011 in ToCS.

  5. Randomized Distributed Decision

    • P. Fraigniaud, M. Goos, A. Korman, M. Parter, and D. Peleg.
    • Distributed Computing (DC), 2014.
    • Extended abstract appeared in DISC 2012.
    • Comments: Selected to appear on the special issue of DISC 2012 in DC.

  6. What can be decided locally without identifiers?

    • P. Fraigniaud, M. Goos, A. Korman and J. Suomela.
    • PODC 2013

  7. Distributed Verification of Minimum Spanning Trees

    • A. Korman and S. Kutten.
    • Distributed Computing (DC), 2007.
    • Extended abstract appeared in PODC 2006.
    • Comments: Selected to appear on the special issue of PODC 2006 in DC.

  8. Proof Labeling Schemes
    • A. Korman, S. Kutten and D. Peleg.
    • Distributed Computing (DC), 2010.
    • Extended abstract appeared in PODC 2005.

Distributed Graph Representations

  1. An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

    • P. Fraigniaud, and A. Korman.
    • Journal of the ACM (J.ACM), 2016.
    • Extended abstract papers appeared in STOC 2010 and SODA 2010.

  2. On Randomized Representations of Graphs Using Short Labels

    • P. Fraigniaud, and A. Korman.
    • SPAA 2009.

  3. Labeling schemes for Vertex Connectivity

    • A. Korman.
    • ACM Transactions on Algorithms (TALG), 2010.
    • Extended abstract appeared in ICALP 2007.

  4. Labeling Schemes for Flow and Connectivity
    • M. Katz, N. Katz, A. Korman and D. Peleg.
    • SIAM Journal on Computing (SICOMP), 2004.
    • Extended abstract appeared in SODA 2002.

Dynamic Network algorithms

  1. Controller and Estimator for Dynamic Networks

    • A. Korman, S. Kutten.
    • Information and Computation (I&C), 2013.
    • Extended abstract appeared in PODC 2007.

  2. New Bounds for the Controller Problem

    • Y. Emek and A. Korman.
    • Distributed Computing (DC), 2011.
    • Extended abstract appeared in DISC 2009.
    • Comments: Selected to appear on the special issue of DISC 2009 in DC.

  3. Efficient Threshold Detection in a Distributed Environment

    • Y. Emek and A. Korman.
    • PODC 2010.

  4. Dynamic Routing Schemes for Graphs with Low Local Density

    • A. Korman and D. Peleg.
    • ACM Transactions on Algorithms (TALG), 2008.
    • Extended abstract appeared in ICALP 2006.

  5. Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes

    • A. Korman and D. Peleg.
    • Distributed Computing (DC), 2008.
    • Extended abstract appeared in DISC 2007.
    • Comments: Selected to appear on the special issue of DISC 2007 in DC.

  6. Labeling Schemes for Weighted Dynamic Trees

    • A. Korman and D. Peleg.
    • Information and Computation (I&C), 2007.
    • Extended abstract appeared in ICALP 2003.

  7. General Compact Labeling Schemes for Dynamic Trees

    • A. Korman.
    • Distributed Computing (DC), 2007.
    • Extended abstract appeared in DISC 2005.
    • Comments:
      • Won the best student paper award.
      • Selected to appear on the special issue of DISC 2005 in DC.

  8. Labeling Schemes for Dynamic Tree Networks
    • A. Korman, D. Peleg and Y. Rodeh.
    • Theory of Computing Systems (ToCS), 2004.
    • Extended abstract appeared in STACS 2002.
    • Comments: Selected to appear on the special issue of STACS 2002 in ToCS.

More Network Algorithms

  1. Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge

    • A. Korman, J. S. Sereni, and L. Viennot.
    • Distributed Computing (DC), 2013.
    • Extended abstract appeared in PODC 2011.
    • Comments: Selected to appear on the special issue of PODC 2011 in DC.

  2. Approximating the Statistics of various Properties in Randomly Weighted Graphs

    • Y. Emek, A. Korman and Y. Shavitt.
    • SODA 2011.

  3. Local MST Computation with Short Advice

    • P. Fraigniaud, A. Korman and E. Lebhar.
    • Theory of Computing Systems (ToCS), 2010.
    • Extended abstract appeared in SPAA 2007.
    • Comments: Selected to appear on the special issue of SPAA 2007 in ToCS.

  4. Notions of Connectivity in Overlay Networks

    • Y. Emek, P. Fraigniaud, A. Korman, S. Kutten, and D. Peleg.
    • Theoretical Computer Science (TCS), to appear.
    • Extended abstract appeared in SIROCCO 2012.
    • Comments: Selected to appear on the special issue of SIROCCO 2012 in TCS.