Amos Korman

I am a permanent researcher in CNRS located at LIAFA in the University of Paris Diderot. I received a Masters degree in
Mathematics from Stanford University . In 2006, I received a Ph.D. degree in Computer Science from the Weizmann Institute
of Science under the guidance of Prof. David Peleg. My thesis "Static and Dynamic Labeling Schemes" won the Dean's Prize
for Ph.D. Students.

My main research interests include various fundamental aspects of Distributed Computing mostly in the context of Graph
Algorithms and Network Communication Protocols. In particular, I am interested in abstract models that aim to improve our
understanding of the notion of Locality, which is inherent to distributed computing. For example, one of my current goals
is to provide models of computation and structural results that may serve as initial steps towards constructing a rigorous
computational complexity theory for the Locality research subfield.

In addition, recently, I have become particularly intrigued with understanding computational aspects of Distributed Computing
phenomenas that occure in nature. Specifically, in this respect, I am interested in appying ideas and techniques from Theoretical
Distributed Computing studies to improve our understanding of Complex Biological Systems.

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

CV pdf

Publications

Journal Papers

1. Y. Emek and A. Korman.  New Bounds for the Controller Problem.
   Distributed Computing (DC) , 24(3-4), (2011), 177--186. pdf
2. Y. Emek, P. Fraigniaud, A. Korman and A. Rosen.  Online Computation with Advice.
   Theoretical Computer Science (TCS) , 412(24), (2011), 2642--2656. pdf
3. 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), 1120--1123. pdf
4. A. Korman, S. Kutten and D. Peleg.  Proof Labeling Schemes.
   Distributed Computing (DC) 22(4), 2010. pdf
5. P. Fraigniaud, A. Korman and E. Lebhar.  Local MST Computation with Short Advice.
   Theory of Computing Systems (ToCS) , 47(4), (2010), 920--933. pdf

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

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

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

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

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

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

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

14. A. Korman and S. Kutten.  Distributed Verification of Minimum Spanning Trees.
    J. Distributed Computing (DC) 20(4), 2007. pdf
15. A. Korman.  General Compact Labeling Schemes for Dynamic Trees.
    J. Distributed Computing (DC) 20(3) 2007. pdf
16. A. Korman, D. Peleg and Y. Rodeh.  Labeling Schemes for Dynamic Tree Networks.
    Theory of Computing Systems (ToCS) (37) 2004. pdf
17. 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 D. Peleg. Local Distributed Decision. FOCS 2011. pdf
2. 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
   Invited for STOC 2011's special issue in SICOMP.
3. 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.
4. A. Korman, J. S. Sereni, and L. Viennot.  Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge. PODC 2011. pdf
   Invited for PODC 2011's special issue in DC.
5. L. Kor, A. Korman and D. Peleg.  Tight Bounds for Distributed MST Verification. STACS 2011. pdf
   Invited for STACS 2011's special issue in ToCS.
6. Y. Emek, A. Korman and Y. Shavitt.  Approximating the Statistics of various Properties in Randomly Weighted Graphs. SODA 2011. pdf
7. Y. Emek and A. Korman.  Efficient Threshold Detection in a Distributed Environment. PODC 2010. pdf
8. P. Fraigniaud and A. Korman.  An Optimal Ancestry Labeling Scheme and Small Universal Posets. STOC 2010. pdf
9. P. Fraigniaud and A. Korman.  Compact Ancestry Labeling Schemes for XML Trees. SODA 2010. pdf
10. Y. Emek, P. Fraigniaud, A. Korman and A. Rosen.  On the Additive Constant of the k-Server Work Function Algorithm. WAOA 2009. pdf
11. Y. Emek and A. Korman.  New Bounds for the Controller Problem. DISC 2009. pdf
    Accepted for DISC 2009's special issue in DC.
12. P. Fraigniaud and A. Korman.  On Randomized Representations of Graphs Using Short Labels. SPAA 2009. pdf
13. 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.
14. A. Korman.  Compact Routing Schemes for Dynamic Trees in the Fixed Port Model. ICDCN 2009. pdf
    Best paper award.

15. A. Korman.  Improved Compact Routing Schemes for Dynamic Trees. PODC 2008. pdf
16. 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.
17. A. Korman, S. Kutten.  Controller and Estimator for Dynamic Networks. PODC 2007. pdf
18. A. Korman. Labeling Schemes for Vertex Connectivity. ICALP(A) 2007. pdf
19. A. Korman and S. Kutten.   Labeling Schemes with Queries. SIROCCO 2007. pdf
    Selected for SIROCCO 2007's special issue in TCS.
20. 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.
21. A. Korman and S. Kutten.  Distributed Verification of Minimum Spanning Trees. PODC 2006. pdf
    Selected for PODC 2006's special issue in DC.
22. A. Korman, D. Peleg and Y. Rodeh.  Constructing Labeling Schemes through Universal Matrices. ISAAC 2006. pdf
23. A. Korman and D. Peleg.  Dynamic Routing Schemes for General Graphs. ICALP(A) 2006. pdf
24. A. Korman.   General Compact Labeling Schemes for Dynamic Trees. DISC 2005. pdf
    Selected for DISC 2005's special issue in DC.
    Best student paper award.
25. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg.  Labeling Schemes for Tree Representations. IWDC 2005. pdf
26. A. Korman S. Kutten and D. Peleg.  Proof Labeling Schemes. PODC 2005. pdf
27. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg.   Label-Guided Graph Exploration by a Finite Automation. ICALP(A) 2005. pdf ?
28. A. Korman and D. Peleg.  Labeling Schemes for Weighted Dynamic Trees. ICALP(A) 2003. pdf
29. 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.
30. M. Katz, N. Katz, A. Korman and D. Peleg.   Labeling Schemes for Flow and Connectivity. SODA 2002. pdf

Awards and Fellowships

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.

Program Committee Membership

Program committee ICDCS 2012.

Program committee PODC 2011.

Program committee ICDCN 2010.

Program committee IMAGINE 2009-2007.

Program committee DISC 2008.

Junior program committee PODC 2007.

---