Selected publications

Algorithmic Biology

  1. 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).
    • eLife, November 2016.
    • Mathematical analysis of the model 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.

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

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

  2. Individual versus Collective Cognition in Social Insects

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


  3. 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.

  1. Parallel Exhaustive Search without Coordination
    • P. Fraigniaud, A. Korman, and Y. Rodeh.
    • STOC 2016.

Computing in Unreliable Environments

  1. Searching on Trees with Noisy Memory

    • L. Boczkowski, A. Korman, and Y. Rodeh.
    • submitted.

  2. The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback

    • A. Korman and Y. Rodeh.
    • ICALP(A) 2017.

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

    • L. Boczkowski, A. Korman, and E. Natale.
    • 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), to appear.
    • Extended abstract appeared in PODC 2014.
    • Comments: Selected for the special issue of PODC 2014 in DC.

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.

Online and Dynamic Network algorithms

  1. 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.

  2. Controller and Estimator for Dynamic Networks

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

  3. 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.

  4. Efficient Threshold Detection in a Distributed Environment

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

  5. 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.

  6. 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.

  7. Labeling Schemes for Weighted Dynamic Trees

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

  8. 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.

  9. 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.

  10. On the additive constant of the k-server Work Function Algorithm

    • Y. Emek, P. Fraigniaud, A. Korman, and A. Rosén.
    • Information Processing Letters (IPL), 2010.
    • Extended abstract appeared in WAOA 2009.

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. 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.

  4. 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.

  5. 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.