Amos Korman

I am a permanent researcher in CNRS located at IRIF in the Paris Diderot University. I received a Ph.D. degree in Computer Science in 2006 from the Weizmann Institute of Science
under the guidance of Prof. David Peleg. In 2015, I recieved my Habilitation from Paris Diderot University.

I am interested in various fundamental aspects of computation under uncertainly. This finds relevance in a variety of domains of computer science, including distributed computing,
online algorithms, decision theory, and search algorithms. Recently, I have become particularly intrigued with understanding fundamental computational aspects in nature.
My main goal in this respect is to apply an algorithmic perspective to the study of collective animal behaviour, by combining theoretical investigations with biological experiments.
So far, I have been mostly focusing on studying model organisms such as ants or bats.

My extracurricular interests include North Indian Classical music (both theory and practice). I am a tabla exponent of the Farrukhabad gharana and a "Ganda-Bandhan"
disciple of Pandit Nayan Ghosh.

 

~~~~~~~~~~~~ Supported by the ERC Consolidator grant "Distributed Biological Algorithms" (DBA): Now recruiting PhD students and Postdocs ~~~~~~~~~~~~

 

Program Committee Memberships

PODC 2015, 2013, 2011, 2007.

ICALP 2016, 2013.

DISC 2015, 2008.

ICDCN 2010.

ICDCS 2012.

 

Chair Positions

1st workshop on Advances on Distributed Graph Algorithms (ADGA 2012), October 19, 2012, Salvador, Brazil, in conjunction with DISC 2012.

1st Workshop on Biological Distributed Algorithms (BDA 2013), October 14, 2013, Jerusalem, Israel, in conjunction with DISC 2013 (co-chair).

2nd Workshop on Biological Distributed Algorithms (BDA 2014), October 11-12, 2014, Austin, Texas, USA, in conjunction with DISC 2014 (co-chair).

16th ACM International Conference on Distributed Computing and Networks (ICDCN 2015), January 4-7, 2015, Goa, India (co-chair).

 

Ph.D students

Lucas Boczkowski, co-advised with Iordanis Kerenidis.

Simon Collet, co-advised with Pierre Fraigniaud.

 

Publications

Journal Papers

  1. P. Fraigniaud, and A. Korman.  An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets.
    Journal of the ACM (J.ACM) , 63(1): 6, 2016. pdf
  2. O.Feinerman, A. Korman, S. Kutten, and Y. Rodeh.  Fast Rendezvous on a Cycle by Agents with Different Speeds.
    Theoretical Computer Science (TCS) , to appear. pdf
  3. O. Feinerman, B. Haeupler, and A. Korman.  Breathe before Speaking: Efficient Information Dissemination despite Noisy, Limited and Anonymous Communication.
    Distributed Computing (DC) , to appear. pdf
  4. A. Korman, Shay Kutten, and Toshimitsu Masuzawa.  Fast and compact self stabilizing verification, computation, and fault detection of an MST.
    Distributed Computing (DC) , 28(4), 253-295, 2015. pdf
  5. A. Korman, E. Greenwald and O. Feinerman.  Confidence Sharing: an Economic Strategy for Efficient Information Flows in Animal Groups.
    PLoS Computational Biology (PCOMPBIOL) , 10(10), 2014: e1003862. pdf
  6. P. Fraigniaud, A. Korman, and D. Peleg.  Towards a Complexity Theory for Local Distributed Computing.
    Journal of the ACM (J.ACM) , 60(5): 35, 2013. pdf
  7. P. Fraigniaud, M. Goos, A. Korman, M. Parter, and D. Peleg.  Randomized Distributed Decision.
    Distributed Computing (DC) , 27(6), 419-434, 2014. pdf
  8. A. Korman, J. S. Sereni, and L. Viennot.  Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge.
    Distributed Computing (DC) , 26(5-6), 289-308, 2013. pdf
  9. L. Kor, A. Korman and D. Peleg.  Tight Bounds For Distributed MST Verification.
    Theory of Computing Systems (ToCS) , 52(2), 2013. pdf
  10. A. Korman, S. Kutten.  Controller and Estimator for Dynamic Networks.
    Information and Computation (I&C) 223, 2013. pdf
  11. A. Das Sharma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg and R. Wattenhofer. 
    Distributed Verification and Hardness of Distributed Approximation.
    SIAM Journal on Compouting (SICOMP) 41(5), 2012. pdf

  12. Y. Emek and A. Korman.  New Bounds for the Controller Problem.
    Distributed Computing (DC) 24(3-4), 2011. pdf
  13. Y. Emek, P. Fraigniaud, A. Korman and A. Rosen.  Online Computation with Advice.
    Theoretical Computer Science (TCS) 412(24), 2011. pdf
  14. Y. Emek, P. Fraigniaud, A. Korman, and A. Rosen.  On the Additive Constant of the k-Server Work Function Algorithm.
    Information Processing Letters (IPL) 110(24), 2010. pdf
  15. A. Korman, S. Kutten and D. Peleg.  Proof Labeling Schemes.
    Distributed Computing (DC) 22(4), 2010. pdf
  16. P. Fraigniaud, A. Korman and E. Lebhar.  Local MST Computation with Short Advice.
    Theory of Computing Systems (ToCS) 47(4), 2010. pdf

  17. A. Korman.  Labeling schemes for Vertex Connectivity.
    ACM Transactions on Algorithms (TALG) 6(2), 2010. pdf

  18. A. Korman, D. Peleg and Y. Rodeh.  Constructing Labeling Schemes through Universal Matrices.
    Algorithmica 57(4), 2010. pdf

  19. A. Korman and S. Kutten.   A Note on Models for Graph Representations.
    Theoretical Computer Science (TCS) 410(14), 2009. pdf
  20. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg.   Labeling Schemes for Tree Representations.
    Algorithmica 53(1), 2009. pdf

  21. A. Korman and D. Peleg.  Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes.
    J. Distributed Computing (DC) 21(2), 2008. pdf

  22. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg.  Label-Guided Graph Exploration by a Finite Automation.
    ACM Transactions on Algorithms (TALG) 4(4), 2008. pdf

  23. A. Korman and D. Peleg.  Dynamic Routing Schemes for Graphs with Low Local Density.
    ACM Transactions on Algorithms (TALG) 4(4), 2008. pdf

  24. A. Korman and D. Peleg.  Labeling Schemes for Weighted Dynamic Trees.
    Information and Computation (I&C) 205(12), 2007. pdf

  25. A. Korman and S. Kutten.  Distributed Verification of Minimum Spanning Trees.
    J. Distributed Computing (DC) 20(4), 2007. pdf
  26. A. Korman.  General Compact Labeling Schemes for Dynamic Trees.
    J. Distributed Computing (DC) 20(3), 2007. pdf
  27. A. Korman, D. Peleg and Y. Rodeh.  Labeling Schemes for Dynamic Tree Networks.
    Theory of Computing Systems (ToCS) (37), 2004. pdf
  28. M. Katz, N. Katz, A. Korman and D. Peleg.  Labeling Schemes for Flow and Connectivity.
    SIAM Journal on Computing (SICOMP) (34), 2004. pdf

 

Conference Proceedings

  1. P. Fraigniaud, A. Korman, and Y. Rodeh. Parallel Exhaustive Search without Coordination. STOC 2016. pdf
  2. O. Feinerman, B. Haeupler, and A. Korman. Breathe before Speaking: Efficient Information Dissemination despite Noisy, Limited and Anonymous Communication. PODC 2014. pdf
  3. Invited for PODC 2014's special issue in DC.

  4. P. Fraigniaud, M. Goos, A. Korman and J. Suomela. What can be decided locally without identifiers? PODC 2013. pdf
  5. O. Feinerman and A. Korman. Theoretical Distributed Computing Meets Biology: A Review. ICDCIT 2013. pdf
  6. O. Feinerman and A. Korman. Memory Lower Bounds for Randomized Collaborative Search and Implications to Biology. DISC 2012. pdf
  7. P. Fraigniaud, A. Korman, M. Parter and D. Peleg. Randomized Distributed Decision. DISC 2012. pdf
    Invited for DISC 2012's special issue in DC.
  8. P. Fraigniaud, M.M. Halldorsson and A. Korman. On the Impact of Identifiers on Local Decision. OPODIS 2012. pdf
  9. O. Feinerman, A. Korman, Z. Lotker and J.S Sereni. Collaborative Search on the Plane without Communication. PODC 2012. pdf
  10. E. Emek, P. Fraigniaud, A. Korman, S. Kutten and D. Peleg. Notions of Connectivity in Overlay Networks. SIROCCO 2012, to appear. pdf
  11. P. Fraigniaud, A. Korman and D. Peleg. Local Distributed Decision. FOCS 2011. pdf
  12. A. Das Sharma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg and R. Wattenhofer. 
    Distributed Verification and Hardness of Distributed Approximation. STOC 2011. pdf

    Selected for STOC 2011's special issue in SICOMP.
  13. A. Korman, S. Kutten and T. Masuzawa .  Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST. PODC 2011. pdf
    Invited for PODC 2011's special issue in DC.
  14. A. Korman, J. S. Sereni, and L. Viennot.  Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge. PODC 2011. pdf
    Selected for PODC 2011's special issue in DC.
  15. L. Kor, A. Korman and D. Peleg.  Tight Bounds for Distributed MST Verification. STACS 2011. pdf
    Selected for STACS 2011's special issue in ToCS.
  16. Y. Emek, A. Korman and Y. Shavitt.  Approximating the Statistics of various Properties in Randomly Weighted Graphs. SODA 2011. pdf
  17. Y. Emek and A. Korman.  Efficient Threshold Detection in a Distributed Environment. PODC 2010. pdf
  18. P. Fraigniaud and A. Korman.  An Optimal Ancestry Labeling Scheme and Small Universal Posets. STOC 2010. pdf
  19. P. Fraigniaud and A. Korman.  Compact Ancestry Labeling Schemes for XML Trees. SODA 2010. pdf
  20. Y. Emek, P. Fraigniaud, A. Korman and A. Rosen.  On the Additive Constant of the k-Server Work Function Algorithm. WAOA 2009. pdf
  21. Y. Emek and A. Korman.  New Bounds for the Controller Problem. DISC 2009. pdf
    Selected for DISC 2009's special issue in DC.
  22. P. Fraigniaud and A. Korman.  On Randomized Representations of Graphs Using Short Labels. SPAA 2009. pdf
  23. Y. Emek, P. Fraigniaud, A. Korman and A. Rosen.  Online Computation with Advice. ICALP(A) 2009. pdf
    Selected for ICALP 2009's special issue in TCS.
  24. A. Korman.  Compact Routing Schemes for Dynamic Trees in the Fixed Port Model. ICDCN 2009. pdf
    Won the best paper award.

  25. A. Korman.  Improved Compact Routing Schemes for Dynamic Trees. PODC 2008. pdf
  26. A. Korman, D. Peleg.  Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes. DISC 2007. pdf
    Selected for DISC 2007's special issue in DC.
  27. A. Korman, S. Kutten.  Controller and Estimator for Dynamic Networks. PODC 2007. pdf
  28. A. Korman. Labeling Schemes for Vertex Connectivity. ICALP(A) 2007. pdf
  29. A. Korman and S. Kutten.   Labeling Schemes with Queries. SIROCCO 2007. pdf
    Selected for SIROCCO 2007's special issue in TCS.
  30. P. Fraigniaud, A. Korman and E. Lebhar.  Local MST Computation with Short Advice. SPAA 2007. pdf
    Selected for SPAA 2007's special issue in ToCS.
  31. A. Korman and S. Kutten.  Distributed Verification of Minimum Spanning Trees. PODC 2006. pdf
    Selected for PODC 2006's special issue in DC.
  32. A. Korman, D. Peleg and Y. Rodeh.  Constructing Labeling Schemes through Universal Matrices. ISAAC 2006. pdf
  33. A. Korman and D. Peleg.  Dynamic Routing Schemes for General Graphs. ICALP(A) 2006. pdf
  34. A. Korman.   General Compact Labeling Schemes for Dynamic Trees. DISC 2005. pdf
    Selected for DISC 2005's special issue in DC.
    Won the best student paper award.
  35. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg.  Labeling Schemes for Tree Representations. IWDC 2005. pdf
  36. A. Korman S. Kutten and D. Peleg.  Proof Labeling Schemes. PODC 2005. pdf
  37. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg.   Label-Guided Graph Exploration by a Finite Automation. ICALP(A) 2005. pdf ?
  38. A. Korman and D. Peleg.  Labeling Schemes for Weighted Dynamic Trees. ICALP(A) 2003. pdf
  39. A. Korman, D. Peleg and Y. Rodeh.  Labeling Schemes for Dynamic Tree Networks. STACS 2002. pdf
    Selected for STACS 2002's special issue in ToCS.
  40. M. Katz, N. Katz, A. Korman and D. Peleg.   Labeling Schemes for Flow and Connectivity. SODA 2002. pdf

 

Awards and Fellowships

Received the Prime d'excellence scientific (PES) award, 2011.

Won the 2009 ICDCN best paper award.

Won the Dean's Prize for Ph.D. Students in Weizmann Institute.

Won the 2005 DISC best student paper award.

Supported in part at the Technion by an Aly Kaufman fellowship.

Received the Vatat Scholarship for outstanding Ph.D. students, 2000-2005, Weizmann Institute.

Graduated at the Hebrew University with exceptional honors: Magna Cum Lauda.

Was on the Dean's list in 1995, 1997.

 

Recent Invited Talks

SIROCCO 2015, Montserrat, Spain, July. 2015.

BDA 2014, Austin, Texax, USA, Oct. 2014.

ADGA 2014, Austin, Texax, USA, Oct. 2014.

BDA 2013, Jerusalem, Israel, Oct. 2013.

Natural Algorithms and the Sciences , Princeton, USA, May. 2013.

ICDCIT 2013, Bhubaneswar, India, Feb. 2013.

TADDS 2012, Rome, Italy, Dec. 2012.